Codeforces Round 814 div.1 ABC

录播讲解链接(AB)

A2. Burenka and Traditions (hard version)

只会进行长度为2或1的区间操作，因为更大的可以分解成小的且不会更劣。

考虑从左到右依次两两进行异或操作，每次都使得左侧数变为0，那么总操作次数最多是 \(n\)

如果其中包含一段异或和为0的区间，就可以省下一次操作，且仅有这种方式可以省操作，故目标变为划分出最多的异或为0的子段个数，异或前缀和+set即可。

int n, m;
int a[maxn];
void solve() {
    cin >> n;
    int ans = n;
    for(int i=1;i<=n;i++) cin >> a[i];
    set<int> pre;
    pre.insert(0);
    int s = 0;
    for(int i=1;i<=n;i++){
        s ^= a[i];
        if(pre.count(s)){
            pre.clear();
            s = 0;
            ans--;
        }
        pre.insert(s);
    }
    cout << ans << '\n';
}

B. Fibonacci Strings

齐肯多夫定理：任意正整数都可以唯一分解成若干不连续的斐波那契数列项之和（不包括第一个1）。

分解方式也很简单，令 \(n\) 不断减去最大的比 \(n\) 小的斐波那契项即可。

这题我在写的时候还不知道这个定理，所以采用了一种贪心的方式诈胡了，即将所有的 \(c_i\) 放入优先队列，从大到小枚举斐波那契项，每次取出最大的那个 \(c_i\) 减去此项。

int n, m;
ll f[75], s[75];
void solve() {
    f[1] = f[2] = 1;
    s[1] = 1; s[2] = 2;
    for(int i=3;i<=70;i++){
        f[i] = f[i-1] + f[i-2];
        s[i] = s[i-1] + f[i];
    }
    priority_queue<pair<ll, int>> q;
    cin >> n;
    ll tot = 0;
    for(int i=1;i<=n;i++){
        ll x; cin >> x;
        q.push({x, i});
        tot += x;
    }
    for(int i=1;i<=70;i++){
        if(s[i] > tot) break;
        if(tot == s[i]){
            int uid = -1;
            vector<pair<ll, int>> tmp;
            for(int j=i;j>=1;j--){
                if(q.empty()){
                    cout << "NO\n";
                    return;
                }
                auto u = q.top();
                q.pop();
                if(u.second == uid){
                    tmp.push_back(u);
                    if(q.empty()){
                        cout << "NO\n";
                        return;
                    }
                    u = q.top();
                    q.pop();
                }
                uid = u.second;
                u.first -= f[j];
                if(u.first < 0){
                    cout << "NO\n";
                    return;
                }else if(u.first != 0){
                    q.push(u);
                }
                if(!tmp.empty()){
                    q.push(tmp.back());
                    tmp.pop_back();
                }
            }
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
    return;
}

C. Tonya and Burenka-179

首先能想到，如果以 \(n\) 的某个因数 \(p\) 为步长去跳，会构成一个循环，每个数会重复 \(p\) 次，因为任选起点，重复的一定比不重复的好（可以选取较大的部分重复）。

若 \(kp\) 仍为 \(n\) 的因数，以 \(kp\) 为步长去跳显然会更好，因为涉及的元素严格为按 \(p\) 跳的子集，可以选取较大部分的子集来重复。

故最终可选取的步长仅有 \(n/p\)，其中 \(p\) 为 \(n\) 的质因数。

不同质因数的数量很少，就可以暴力set乱搞了。

ll pri[30];
ll sum[30][maxn], a[maxn];
 
void solve() {
    int n, q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++) cin >> a[i];
    ll tmp = n, h = 0;
    for(int i = 2;tmp > 1;i++) {
        if(tmp % i == 0) {
            while(tmp % i == 0) tmp /= i;
            pri[++h] = i;
            for(int j = 0;j <= n;j++) sum[h][j] = 0;
            int d = n / i;
            for(int j = 1;j <= n;j++) {
                sum[h][j % d] += a[j];  
            }
        }
    }
    multiset<ll> st[h + 1];
    for(int i = 1;i <= h;i++) {
        for(int j = 0;j < n / pri[i];j++) {
            st[i].insert(sum[i][j]);
        }
    }
    ll ans = 0;
    for(int i = 1;i <= h;i++) ans = max(ans, *(st[i].rbegin()) * n / pri[i]);
    cout << ans << '\n';
    while(q-- > 0) {
        ll x, y; cin >> x >> y;
        ans = 0;
        for(int i = 1;i <= h;i++) {
            ll d = n / pri[i];
            st[i].erase(st[i].find(sum[i][x % d]));
            sum[i][x % d] += -a[x] + y;
            st[i].insert(sum[i][x % d]);
            ans = max(ans, *(st[i].rbegin()) * d);
        }
        a[x] = y;
        cout << ans << '\n';
    }
}