某島

… : "…アッカリ~ン . .. . " .. .
August 17, 2022

Codeforces Round #814

傳送門

感覺掉了近 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

我肯定是很久很久以前在 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. …