Codeforces #571 C Vus the Cossack and Strings

题目链接


Solution 1


手动操作具体可以参照下面的代码
AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char a[maxn],b[maxn];
int main(){
	scanf("%s%s",a,b);
	int nb=strlen(b),na=strlen(a),bnum=0,ans=0;
	int p1=0,p2=nb-1,temp=0;
	for(int i=1;i<nb;i++)
		if(b[i-1]!=b[i]) bnum++;
///手动更新开头与结尾
	for(int i=0;i<nb;i++)
		if(a[i]!=b[i]) temp++;
	if(temp%2==0) ans++;
	for(int i=nb;i<na;i++){
		if(b[p1]!=a[i-nb]) temp++;
		if(b[p2]!=a[i]) temp++;
		temp=(temp+bnum)%50;
		if(temp%2==0) ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Solution 2

因此，当我们维护ans的时候只需要关心当前a串与b串的1的个数之和的奇偶性
AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char a[maxn],b[maxn];
int main(){
	scanf("%s%s",a,b);
	int nb=strlen(b),na=strlen(a);
	int num=0,temp=0,ans=0;
	for(int i=0;i<nb;i++){
		if(b[i]=='1') num++;
		if(a[i]=='1') temp++;
	}
	if((num+temp)%2==0) ans++;
	for(int i=nb;i<na;i++){
		if(a[i-nb]=='1') temp--;
		if(a[i]=='1')  temp++;
		if((num+temp)%2==0) ans++;
	}
	printf("%d\n",ans);
	return 0;
}