专栏文章

题解：CF2131F Unjust Binary Life

CClaire0918
CF2131F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minweqhw
此快照首次捕获于
2025/12/02 09:27
3 个月前
此快照最后确认于
2025/12/02 09:27
3 个月前
查看原文
我们注意到 ax⊕by=0a_x \oplus b_y = 0 当且仅当 ax=bya_x = b_y，所以能从 (1,1)(1, 1) 走到 (x,y)(x, y) 当且仅当
a1=a2=…=ax=b1=b2…bya_1 = a_2 = \ldots = a_x = b_1 = b_2 \ldots b_y
分类讨论这个值是 00 还是 11。我们记 si=∑k=1iak,ti=∑k=1ibks_i = \sum_{k = 1}^{i} a_k, t_i = \sum_{k = 1}^{i} b_k，那么这个值为 00 时 f(x,y)=sx+tyf(x, y) = s_x + t_y，为 11 时 f(x,y)=(x−sx)+(y−ty)f(x, y) = (x - s_x) + (y - t_y)，于是 f(x,y)=min⁡{sx+ty,x+y−sx−ty}f(x, y) = \min\{s_x + t_y, x + y - s_x - t_y\}，答案即求
∑x=1n∑y=1nmin⁡{sx+ty,x+y−sx−ty}\sum_{x = 1}^{n} \sum_{y = 1}^{n} \min\{s_x + t_y, x + y - s_x - t_y\}
我们考虑是否有 sx+ty>x+y−sx−tys_x + t_y > x + y - s_x - t_y，即 2ty−y>x−2sx2t_y - y > x - 2s_x。将 xx 和 yy 的贡献拆开，一个 yy 在所有满足该条件的 xx 上贡献 y−tyy - t_y，否则贡献 tyt_y。我们设一个 xx 中有 kk 个 yy 满足条件，那么 xx 就有 kk 次贡献 x−sxx - s_x，n−kn - k 次贡献 sxs_x。我们仅需对于任何 xx 维护所有满足条件的 yy 的 ∑y1,∑yy,∑yty\sum_y 1, \sum_y y, \sum_y t_y 即可。我们注意到 2ty−y2t_y - y 和 x−2sxx - 2s_x 都是 O(n)\mathcal{O}(n) 的，于是我们直接差分即可维护，时间复杂度 O(n)\mathcal{O}(n)。
Code：
CPP
#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10;

int t, n;
long long res;
int a[maxn], b[maxn], prea[maxn], preb[maxn], pd[maxn << 1], *d = pd + maxn;
long long pspos[maxn << 1], psval[maxn << 1], *spos = pspos + maxn, *sval = psval + maxn;

int main(){
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n), getchar(), res = 0;
        for (int i = -n; i <= n + 1; i++){
            d[i] = spos[i] = sval[i] = 0;
        }
        for (int i = 1; i <= n; i++){
            prea[i] = prea[i - 1] + (a[i] = getchar() - '0');
        }
        getchar();
        long long sum = 0;
        for (int i = 1; i <= n; i++){
            sum += (preb[i] = preb[i - 1] + (b[i] = getchar() - '0'));
            const int p = (preb[i] << 1) - i;
            d[p]++, spos[p] += i, sval[p] += preb[i];
        }
        for (int i = n; i >= -n; i--){
            d[i] += d[i + 1], spos[i] += spos[i + 1], sval[i] += sval[i + 1];
        }
        for (int i = 1; i <= n; i++){
            const long long p = i - (prea[i] << 1), k = d[p];
            res += k * (i - prea[i]) + (n - k) * prea[i] + spos[p] - sval[p] + (sum - sval[p]);
        }
        printf("%lld\n", res);
    }

return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...