传送门

• https://codeforces.com/contest/1718
• https://zhuanlan.zhihu.com/p/554786501

感觉掉了近 100 分。QAQ。。
题目还是非常不错的。。。特别是 D 题~~

比赛时先开了 A2 但是写得非常有问题。。然后就只能先去写 A1 拿分。。。结果 A1 还写错了 1 次，并且 A2 就一直没 debug。。。
然后开 B 给的贪心也很失败。。需要特判很多情况。。。最后虽然发现了错误的 case。。。但是最后 debug 的时候居然写错了。。导致一直以为是 case 没找对。。。

Problem A. Burenka and Traditions

题意：有一个数组a，每次可以选择一个区间 [l,r] 和一个整数 x，将 al, al+1, …, ar 中与 x 异或，代价为 \ceil((r-l+1)/2)
问至少需要多少代价，数组所有元素均变为 0。

A1, n, ai <= 5000.
A2, n <= 1e5, ai <= 1e9,

。。最好就不要看 A1。。。（A1 dp 写完浪费时间不说，还容易数组开小导致写错。。）
首先选长度 >= 2 的区间是没有意义的，我们只需要用一些长度为 1、2 的区间拼成连续的操作序列即可。。
考察下面的情况。。。
3
1 2 3
显然，操作序列应该是。。。
1 2 3 -> 0 3 3 -> 0 0 0
也就是我们要找到前缀的 xor 等于当前数的情况。
这个只需要用一个 set 维护，发现出现重复数字就说明出现了一种上述的情况，此时可以答案 -1，并把当前 set 清空。

Problem B. Fibonacci Strings

• https://oi-wiki.org/math/fibonacci/

我肯定是很久很久以前在 cf 做过类似的题，（好像也是 B。。。）
那么既然可以唯一斐波那契分解，所以理论上就可以随便做了。
有问题的是这个题有两个 1，可能会有冲突，可以枚举这多出的 1 分给哪，然后继续硬做。。
但是这样非常不优雅，好的贪心设计是不需要特判的。

Problem C. Tonya and Burenka-179

先不考虑修改。
那么我们首先考虑 n 是素数的情况，那么显然无论 (s,k) 怎么选，f(s, k) 都是一样的，序列的和。
当 n 不是素数的时候，就会根据每个 n 的因子 d，分成一些长度为 n/d, 间隔为 d，每个位置根据 %d 的结果进行分类，每类求和并乘以 d 就是 f(s, k) 的值。
那么一个重要的结论就是对于 d1 | d2，我们只需要考察 d1 即可，因为 d1 所张成的集合是 d2 的真子集，且一定存在一个均值更高的子集，其所对应的 f(s, k) 的值也更高。

因此只需要因子分解 n，预处理出所有不同的 f(s, k) 即可。。。
最后考虑修改，显然需要搞个数据结构维护最值。。。
这里只有单点修改，所以开两个堆维护即可。

#include<lastweapon/io>
using namespace lastweapon;

const int PMAX = 31623;
VI P; bitset<PMAX> isC;
#define ii (i*P[j])
void sieve(){
    FOR(i, 2, PMAX){
        if (!isC[i]) P.PB(i);
        for (int j=0;j<SZ(P)&&ii<PMAX;++j){
            isC[ii]=1; if (!(i%P[j])) break;
        }
    }
}
#undef ii

const int N = int(2e5) + 9;
int a[N], n, q;

void solve() {
    RD(n, q); REP(i, n) RD(a[i]);

    VI fac; int x = n; REP(i, SZ(P)) {
        int p = P[i]; if (p*p > x) break;
        if (x % p) continue;
        x /= p; while (x % p == 0) x /= p;
        fac.PB(n/p);
    }
    if (x != 1) fac.PB(n/x);

    vector<vector<LL>> s(SZ(fac));
    priority_queue<LL> Q, D;

    REP(i, SZ(fac)) {
        int p = fac[i]; s[i].resize(p);
        REP(j, n) s[i][j%p] += a[j];
        REP(j, p) Q.push(s[i][j] * p);
    }

    auto modify = [&](int x, int d) {
        REP(i, SZ(fac)) {
            int p = fac[i], j = x % p;
            D.push(s[i][j] * p); s[i][j] += d;
            Q.push(s[i][j] * p);
        }
        while (!D.empty() && D.top() == Q.top()) {
            D.pop(), Q.pop();
        }
    };

    printf("%lld\n", Q.top()); DO(q) {
        int p, v; RD(p, v); --p;
        modify(p, v-a[p]); a[p] = v;
        printf("%lld\n", Q.top());
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    sieve(); Rush solve();
}

Problem D. …

• https://t.me/algorithm_daily_of_minako/6067