Codeforces1005(Div2 A-D)

A. Brogramming Contest

题目链接:https://codeforces.com/contest/2064/problem/A

如果 s 是以 0 开头那么我们每次只要找到 0, 1 交界的地方进行操作即可;

如果 s 是以 1 开头那么我们需要多进行一次操作把字符串变成以 0 开头的.

void solve() {
    int n;
    string s;
    cin >> n >> s;

    int ans = 0;
    for (int i = 0;i < n - 1;i++) {
        if (s[i] != s[i + 1]) ans++;
    }

    if (s[0] == '0') cout << ans << '\n';
    else cout << ans + 1 << '\n';
}

B. Variety is Discouraged

题目链接:https://codeforces.com/contest/2064/problem/B

删除元素的同时数组长度也会变小;

假设现在某种元素的个数只有 1 个, 我们将其删掉后数组中元素种类和数组长度都减少 1 对于得分其实没有影响;

所以在不操作时的得分已经是最大得分了, 那么我们只需在得分不变的情况下尽可能减少数组长度;

基于上面第一个判断, 我们只要找到一个最大的连续片段, 这个片段中所有元素的个数都为 1;

注意特判一下所有元素个数都为 1 和不为 1 的情况即可.

void solve() {
    int n;
    cin >> n;
    vector<int> v(n + 1);
    map<int, int> mp;
    for (int i = 1;i <= n;i++) {
        cin >> v[i];
        mp[v[i]] ++;
    }

    int mxl = 0;
    int l = 0, r = 0, now = 0;
    for (int i = 1;i <= n;i++) {
        if (mp[v[i]] == 1) {
            if (!now) now = i;
        } else {
            if (now) {
                int len = i - now;
                if (len > mxl) {
                    mxl = len;
                    l = now;
                    r = i - 1;
                }

                now = 0;
            }
        }
    }

    if (now) {
        int len = n - now + 1;
        if (len > mxl) {
            mxl = len;
            l = now;
            r = n;
        }
    }

    if (mxl == 0) cout << 0 << '\n';
    else cout << l << " " << r << '\n';
}

C. Remove the Ends

题目链接:https://codeforces.com/contest/2064/problem/C

现在假设我们任取一个位置 i, 根据题目可以判断:

-这个位置之前的所有负数我们都不能取, 而所有正数都能取到;

-这个位置之后的所有正数我们都不能取, 而所有负数都能取到;

所以我们对数组中的正数做前缀和处理, 负数做后缀和处理, 然后枚举每个位置取 max 即可.

void solve() {
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1;i <= n;i++) cin >> v[i];

    vector<ll> pref(n + 3), prez(n + 3);
    for (int i = 1;i <= n;i++) prez[i] = prez[i - 1] + max(0, v[i]);
    for (int i = n;i >= 1;i--) pref[i] = pref[i + 1] + max(0, -v[i]);

    ll ans = 0;
    for (int i = 1;i <= n;i++) ans = max(ans, pref[i] + prez[i]);

    cout << ans << '\n';
}

D. Eating

题目链接:https://codeforces.com/contest/2064/problem/D

首先如果两个数最高位相同, 那么异或后最高位会被消掉否则最高位会被保留;

其次是异或运算满足结合律, 即 (a ^ b) ^ c = (a ^ c) ^ b ;

所以如果某个数的最高位比 x 低显然我们是可以将其吃掉的, 同时 x 的最高位依然会被保留;

于是我们只要从前找到一个最高位和 x 相等的最大值和 x 进行比较, 如果 x 小于这个数显然不能再往前走了反之继续;

当然这里 x 需要和这个最大值之后的所有元素进行异或, 利用到结合律我们可以预处理出前缀异或数组来计算;

对于找到某个最高位的最大值我们也可以预处理出一个二维 dp 数组 dp[i][j] 表示前 i 个数 最高位至少为 j 的最大值的位置.

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> w(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> w[i];
        pre[i] = w[i] ^ pre[i - 1];
    }

    // 前 i 个数中最高位至少为 j 的最大位置
    vector<vector<int>> dp(n + 1, vector<int> (30));
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j < 30;j++) {
            if ((1 << j) <= w[i]) dp[i][j] = i;
            else dp[i][j] = dp[i - 1][j];
        }
    }

    // 得到某个数的最高位
    auto find = [&] (int x) {
        int ans = -1;
        for (int i = 0;i < 30;i++) if ((1 << i) & x) ans = i;

        return ans;
    };

    while (q--) {
        int x;
        cin >> x;

        int now = n + 1;
        int posmax = find(x);
        while (true) {
            if (posmax == -1) break;

            int pos = dp[now - 1][posmax];
            if (pos == 0) {
                now = 1;
                break;
            }

            // 相等元素异或为 0 而任意数和 0 异或为本身所以重叠部分可以消掉
            x ^= (pre[now - 1] ^ pre[pos]);
            if (x  < w[pos]) {
                now = pos + 1;
                break;
            }

            x ^= w[pos];
            now = pos;
            posmax = find(x);
        }

        cout << n + 1 - now << " ";
    }
    cout << '\n';
}