题解：CF608B Hamming Distance Sum

czh___ · 2025-12-03 19:36:23 · 题解

题解

像这种求一堆区间的某些值的和的，常常考虑成每个位置对最终答案的贡献的和，所以就考虑每个位置的贡献，稍加推算就能知道每个位置的 a 最终会对应哪一段的 b，这个位置如果是 1，那么做出的贡献就是对应区间的 0 的数量，反之亦然。所以只要先统计一下 b 的前缀和，然后扫一遍 a 就可以得出答案了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200100;
char a[N],b[N];
long long a0[N],a1[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    gets(a+1);
    gets(b+1);
    int n=strlen(a+1),m=strlen(b+1);
    long long ans=0;
    for(int i=1;i<=m;i++)
        if(b[i]=='1')
            a1[i]=a1[i-1]+1,
            a0[i]=a0[i-1];
        else
            a0[i]=a0[i-1]+1,
            a1[i]=a1[i-1];
    for(int i=1;i<=n;i++)
        if(a[i]=='1')
            ans+=a0[m-n+i]-a0[i-1];
        else
            ans+=a1[m-n+i]-a1[i-1];
    cout<<ans;
    return 0;
}

拜拜！