CSP-J2022

A 乘方

直接把 \(a=1\) 特判掉，开 \(\mathrm{long~long}\) 暴力乘。

void solve() {
    ll s = 1, a, b;
    cin >> a >> b;
    if(a == 1) {
        cout << 1 << endl;
        return;
    }
    REP(i, b) {
        s *= a;
        if(s > 1e9) {
            cout << -1 << endl;
            return;
        }
    }
    cout << s << endl;
}

B 解密

解一个一元二次方程即可。

void solve() {
    ll n, e, d, m;
    cin >> n >> e >> d;
    m = e * d;
    ll B = n - m + 2;
    ll D = B * B - 4 * n;
    ll S = sqrt(D);
    if(D < 0 || S * S != D) {
        cout << "NO" << endl;
        return;
    }
    if(B - S <= 0 || (B - S) % 2) {
        cout << "NO" << endl;
        return;
    }
    cout << (B - S) / 2 << " " << (B + S) / 2 << endl;
}

C 逻辑表达式

性质题。
首先题目中说与运算比或预算优先级高，这个条件可以消除掉。
假如有式子 \(a|b\&c\)。
如果 \(a\) 为 \(0\)，那么对结果没有影响。
如果 \(a\) 为 \(1\)，那么直接短路。
所以优先级不重要。
考虑从头开始扫。
如果有或运算的短路，那么把之后连续的与运算跳过即可。
如果有与运算的短路，就也是把之后连续的与运算跳过。

void solve() {
    int n;
    string s;
    cin >> s; n = s.size();
    int res = 0, A = 0, B = 0, F = 0;
    REP(i, n) {
        if(F) {
            if(s[i] == '(') {
                int cnt = 1;
                while(cnt) {
                    i++;
                    if(s[i] == '(') cnt++;
                    if(s[i] == ')') cnt--;
                }
            }
            else if(F == 1 && s[i] == '|') {
                F = 0;
            }
            else if(s[i] == ')') {
                F = 0;
            }
            else if(F == 1 && s[i] == '&') {
                A++;
            }
            else if(F == 2 && s[i] == '|') {
                B++;
            }
        }
        else {
            if(s[i] == '1') res = 1;
            if(s[i] == '0') res = 0;
            if(s[i] == '&' && !res) {
                F = 1;
                A++;
            }
            if(s[i] == '|' && res) {
                F = 2;
                B++;
            }
        }
    }
    cout << res << endl << A << " " << B << endl; 
}

D 上升点列

设置状态 \(f_{i, j}\) 为第 \(i\) 个点为连线终点，还剩 \(j\) 个自由点可以用的最长长度。
直接 \(O(n^2k)\) 转移即可。

void solve() {
    int n, k;
    cin >> n >> k;
    vector<PII> a(n);
    REP(i, n) cin >> FI(a[i]) >> SE(a[i]);
    sort(ALL(a));
    vector<vector<int>> f(n, vector<int>(k + 1));
    REP(i, n) {
        f[i][k] = 1;
        REP(j, i) {
            if(SE(a[j]) <= SE(a[i])) {
                int len = SE(a[i]) - SE(a[j]) + FI(a[i]) - FI(a[j]) - 1;
                FOR(l, 0, k) {
                    int r = l + len;
                    if(r > k) break;
                    chmax(f[i][l], f[j][r] + len + 1);
                }
            }
        }
    }
    int ans = 0;
    REP(i, n) {
        FOR(j, 0, k) {
            chmax(ans, f[i][j] + j);
        }
    }
    cout << ans << endl;
}