AT_abc418_d [ABC418D] XNOR Operation题解

简略题目描述

有一个只包含

0,1

的字符串，要求出可以通过(类似异或)的方式能令序列变为

1

的子串个数。

数据范围

$1 \leq N \leq 2 \times 10^5$
$N$ 是整数。
$T$ 是长度为 $N$ 的、仅由 0 和 1 组成的字符串。

通过观察可知，判断一个子串为美丽字符串和 $1$ 的数量是没有关系的。 因为所有的

1

都可以通过操作变成

1

个

1

，而发现如果

0

的数量为偶数的话，可以通过一定数量的操作使得序列变成只有 $1$ 的序列，但是如果

0

的数量为奇数的话，无论怎么合并，都会剩下一个单独的

0

无法合并。

于是问题转换为了求连续区间内

0

的个数为偶数的数量。而我们可以用前缀和来解决一个区间内的

0

的个数，再用区间长度减去当以

i

为左端点，且区间

0

的数量为奇数的区间个数即可。于是就可以省去枚举

r

的循环了。

时间复杂度：

O(n)

空间复杂度：

O(n)

代码细节详见注释。

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

CPP

#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)。

题解：AT_abc418_d [ABC418D] XNOR Operation

文章操作

AT_abc418_d [ABC418D] XNOR Operation题解

简略题目描述

数据范围

相关推荐

评论

题解：AT_abc418_d [ABC418D] XNOR Operation