題目連結
題目大意
有一個串a和串b,都是01串,a串的長度大于等于b串,設a串中的長度為b的子串為c,問所有的f(b,c)的值是偶數的有多少個,f(x,y)的定義為串x和串y相同位置值不同的個數。
解題思路
想了大半天的異或,發現還是和個數有關。。。。。
當f(a,b)是偶數時,a串和b串的奇偶性是相同的,這個在紙上畫一下就明白了。
之後我們就可以用字首和線上性的時間求出答案
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1e6+5;
char s1[N],s2[N];
int a[N],b[N];
int main()
{
scanf("%s",s1+1);
scanf("%s",s2+1);
int len1=strlen(s1+1);
int len2=strlen(s2+1);
for(int i=1;i<=len1;i++)
{
if(s1[i]=='1')
a[i]=a[i-1]+1;
else
a[i]=a[i-1];
}
for(int i=1;i<=len2;i++)
{
if(s2[i]=='1')
b[i]=b[i-1]+1;
else
b[i]=b[i-1];
}
int flag=b[len2]%2;
int ans=0;
for(int i=1;i+len2-1<=len1;i++)
{
int k=a[i+len2-1]-a[i-1];
if(k%2==flag)
ans++;
}
printf("%d\n",ans);
return 0;
}