Codeforces Round 882 (Div. 2) A-E

A. The Man who became a God

题意

定义一个区间的\(f(l,r)\)为\(f(l,r)=|a_l-a_{l+1}|+|a_{l+1}-a_{l+2}|+...+|a_{r-1}-a_r|\)，让求把\(n\)个数的序列分成\(k\)个连续子区间时，最大的\(f\)和。

思路

由于\(f(1,n)=|a_1-a_2|+|a_2-a_3|+...+|a_{n-1}-a_n|\)，假如一个分割处的下标在\(x\)和\(x+1\)之间，就相当于在总和里减去了\(|a_x-a_{x+1}|\)，也就是说，\(k\)个连续子区间实际上就是减去\(k-1\)个绝对值。所以把所有绝对值排一下序，取前\((n-1)-(k-1)=n-k\)个就行。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;

int a[maxn];

void sol() {
    int n, k;
    cin >> n >> k;
    int tmp;
    cin >> tmp;
    for (int i = 1; i <= n - 1; ++i) {
        int x;
        cin >> x;
        a[i] = abs(tmp - x);
        tmp = x;
    }
    sort(a + 1, a + n);
    int ans = 0;
    for (int i = 1; i <= n - k; ++i) {
        ans += a[i];
    }
    cout << ans << endl;
}

int main() {
    int _;
    cin >> _;
    while (_--) sol();
    return 0;
}

B. Hamon Odyssey

题意

定义一个区间的\(f(l,r)\)为\(f(l,r)=a_l\&a_{l+1}\&a_{l+2}\&...\&a_r\)，让求分割连续子区间时，能够使让子区间的\(f\)值之和达到最小的最大的子区间个数。

思路

由于\(f_{min}=f(1,n)\)，所以当\(f(1,n)≠0\)时答案只能为\(1\)。所以当\(f(1,n)=0\)时，贪心一遍就行。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

int a[maxn];

void sol() {
    int n;
    cin >> n;
    int tmp;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if (i == 1) tmp = a[i];
        tmp &= a[i];
    }
    if (tmp != 0) {
        cout << 1 << endl;
        return;
    }
    int t = a[1], ans = 0;
    for (int i = 1; i <= n; ++i) {
        t &= a[i];
        if (t == tmp) {
            ans += 1;
            t = a[i + 1];
        }
    }
    cout << ans << endl;
}

int main() {
    int _;
    cin >> _;
    while (_--) sol();
    return 0;
}

C. Vampiric Powers, anyone?

题意

设原数组为\(a[i]\)，\(b[i] = max_{j=1}^{i}(a[j]\bigoplus a[j+1]\bigoplus a[j+1]\bigoplus...\bigoplus a[i])\)，让求最大的\(b[i]\)。

思路

这题很容易想到暴力，但是\(n\leq 1e5\)，直接两重循环会爆时间，但是由于\(a[i]<2^8\)这里可以暴力所有异或的值，时间复杂度为\(O(2^8n)=2e7\)。当然，用Trie树也可做。

代码

#include <bits/stdc++.h>
using namespace std;
const int m = (1 << 8) - 1, maxn = 1e5 + 5;
bool vis[m + 1];
int a[maxn];

void sol() {
    int n, ans = -1;
    cin >> n;
    for (int i = 0; i <= m; ++i) vis[i] = false;
    vis[0] = true;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int x = 0;
    for (int i = 1; i <= n; ++i) {
        x ^= a[i];
        for (int j = 0; j <= m; ++j) {
            if (vis[j]) ans = max(ans, j ^ x);
        }
        vis[x] = true;
    }
    cout << ans << endl;
}

int main() {
    int _;
    cin >> _;
    while (_--) sol();
    return 0;
}

D. Professor Higashikata

题意

\(s\)为一个只包含\('0'\)和\('1'\)的字符串。定义\(t(s)=t_1+t_2+...+t_m\)，其中\(t_i=s[l_i,r_i]\)。定义一次操作为交换任意两个\(s\)里的元素。定义每次更新为把\(s_{x_i}\)置反。

对于每次更新后的\(s\)，要求输出至少需要操作多少次才能让\(t(s)\)的字典序最大。

思路

对于\(s\)，\('1'\)应该存在于尽可能靠前的\(t_i\)中，且在\(t_i\)中的位置也应该尽可能靠前。对于一个元素\(s_i\)，如果他存在于\(t_j\)中，那么他就不需要再放入\(t_k(k>j)\)当中了，因为\('1'\)是尽可能靠前放的，如果\(t_j\)中的\(s_i\)已置为\('1'\)，那么\(t_k\)中的\(s_i\)也已经为\('1'\)了，不需要再考虑；而如果\('1'\)的数量少。不足以放到\(t_j\)中的\(s_i\)，那么更不可能放到\(t_k\)当中。所以一个\(s_i\)要么在\(t(s)\)中有一个对映，要么没对应。

我们需要记录下标从\(s\)到\(t(s)\)的对应关系，然后对\(t(s)\)建一个树状数组。这样的话，对于每次更新，维护\(s\)中\('1'\)的个数，那么结果实际上就是\(min(t的长度, s中'1'的个数) - query(min(t的长度, s中'1'的个数))\)。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

char s[maxn], ss[maxn];
int a[maxn], g = 0, idx[maxn];
vector<int> v[maxn], vv[maxn];
set<int> se;

int tree[maxn];

int lowbit(int x) { return x & -x; }

void add(int x, int d) {
    while (x <= g) {
        tree[x] += d;
        x += lowbit(x);
    }
}

int query(int x) {
    int sum = 0;
    while (x > 0) {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}

void sol() {
    int n, m, q, sum = 0;
    cin >> n >> m >> q;
    cin >> (s + 1);
    for (int i = 1; i <= n; ++i)
        if (s[i] == '1') sum += 1;
    for (int i = 1; i <= m; ++i) {
        int l, r;
        cin >> l >> r;
        v[l].push_back(i);
        v[r + 1].push_back(-i);
    }
    for (int i = 1; i <= n; ++i) {
        for (int x : v[i]) {
            if (x < 0)
                se.erase(se.lower_bound(-x));
            else
                se.insert(x);
        }
        if (se.empty())
            a[i] = 0;
        else
            a[i] = *se.begin(), vv[*se.begin()].push_back(i);
    }
    for (int i = 1; i <= m; ++i)
        for (int x : vv[i]) {
            ss[++g] = s[x];
            idx[x] = g;
        }
    for (int i = 1; i <= g; ++i)
        if (ss[i] == '1') add(i, 1);
    for (int i = 1; i <= q; ++i) {
        int x;
        cin >> x;
        if (s[x] == '1') {
            s[x] = '0';
            if (idx[x] != 0) add(idx[x], -1);
            sum -= 1;
        } else {
            s[x] = '1';
            if (idx[x] != 0) add(idx[x], 1);
            sum += 1;
        }
        cout << min(g, sum) - query(min(g, sum)) << endl;
    }
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    sol();
    return 0;
}