题解：AT_abc418_d [ABC418D] XNOR Operation

· · 题解

AT_abc418_d [ABC418D] XNOR Operation题解

题目传送门

简略题目描述

有一个只包含0,1的字符串，要求出可以通过(类似异或)的方式能令序列变为1的子串个数。

数据范围

通过观察可知，判断一个子串为美丽字符串和 1 的数量是没有关系的。 因为所有的 1 都可以通过操作变成 1 个 1 ，而发现如果 0 的数量为偶数的话，可以通过一定数量的操作使得序列变成只有 1 的序列，但是如果 0 的数量为奇数的话，无论怎么合并，都会剩下一个单独的 0 无法合并。

于是问题转换为了求连续区间内 0 的个数为偶数的数量。而我们可以用前缀和来解决一个区间内的 0 的个数，再用区间长度减去当以 i 为左端点，且区间 0 的数量为奇数的区间个数即可。 于是就可以省去枚举 r 的循环了。

时间复杂度：O(n)

空间复杂度：O(n)

代码细节详见注释。

code（码风丑陋，请见谅（无坑，放心食用）） :

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int nn=2e5+5;
int n,s[nn],ji[nn][2],la[nn],v,e,ans;
string t;
//s[i]表示1-i的0的个数
//la[i]表示离i最近的0的位置(包括i)
//ji[i][0]=1表示当前有偶数个0
//ji[i][1]=1表示当前有奇数个0
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>t;
    t=" "+t;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1];
        if(t[i]=='0'){
            v++;
            e^=1;
            s[i]++,la[i]=i;
        }else{
            la[i]=la[i-1];
        }
        ji[i][e]=1;//差分
    }
    for(int i=1;i<=n;i++)ji[i][0]+=ji[i-1][0],ji[i][1]+=ji[i-1][1];//前缀和
    int v=s[n];
    for(int i=1;i<=n;i++){
        if(s[i-1]%2==1){//当前出现了奇数个0
            ans+=(n-i+1);
            ans-=(ji[n][0]-ji[i-1][0]);//前缀和
        }else {//当前出现了偶数个0
            ans+=(n-i+1);
            ans-=(ji[n][1]-ji[i-1][1]);//前缀和
        }
    }
    cout<<ans;
    return 0;
}

蒟蒻赛时调了30min，导致e题差 10 min写出(TAT)。