CF1186C(思维+位运算)
中文题意
给出两个字符串a,b,将字符串a中所有长度为|b| 的子串都与b相比较,如果它们对应位不同的个数为偶数,则计数器加一.求计数器最后的值.
输入
第一行是字符串a,长度不大于1e6
| 第二行是字符串b,长度不大于 | a |
输出
输出答案.
样例
input
input
1
2
01100010
00110
output
1
3
input
1
2
1010111110
0110
output
1
4
Note
The first example : let a=01100010 and b=00110. a has four substrings of the length b : 0110001100, 1100011000, 1000110001, 0001000010. f(00110,01100)=f(00110,01100)=2;
f(00110,11000)=f(00110,11000)=4;
f(00110,10001)=f(00110,10001)=4;
f(00110,00010)=f(00110,00010)=1.
Since in three substrings, f(b,c) is even, the answer is 3.
In the second example, there are five substrings that satisfy us: 10101010, 01010101, 11111111, 11111111.
思路
显然O(n^2)的暴力一定超时.但是应该是想办法把一次子串比较的时间缩短到O(1)或者O(logn)
我们分析一下子串比较.对于两个字符串只有01两种元素,然后要求的是对应位不相等的个数(的奇偶性).我们就可以从奇偶性这个方面下手.
首先我们假设两个串都有奇数个1.那么,如果没有任何一对1匹配,也就是两个子串的1都错开,那么一定有偶数个匹配(奇数加奇数等于偶数).
同理,如果两个串都有偶数个1,而且也没有任何一对1匹配,也会有偶数个1.
如果两个串中有1互相匹配了,只要把这些1全部去掉,就能向上面两种情况转换.上面的情况是只要子串的奇偶性(若无特殊说明,奇偶性就指含1的个数的奇偶性)相同,就一定有偶数个匹配,而在此处先匹配的’1-1’对,去掉后并不影响子串奇偶性是否相同.
综上所述,只要两个字符串奇偶性相同,就一定有偶数个匹配.我们只需要预处理出每个子串内部含1的个数即可(此处可以用前缀和实现).
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1000000+100];
char t[1000000+100];
int sum1[1000000+100];
int f=0;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin>>s+1>>t+1;
int len1 = strlen(s+1);
int len2 = strlen(t+1);
sum1[0]=0;
for(int i=1; i<=len1; ++i) { // 前缀和
sum1[i]=sum1[i-1]+s[i]-'0';
}
f=0;
for(int i=1; i<=len2; ++i) { // b串不需要区间,之间全部数出来就好了
f=(f+t[i]-'0')%2;
}
int ans=0;
for(int i=len2; i<=len1; ++i) {
if((sum1[i]-sum1[i-len2])%2 == f) { // 奇偶性相同
++ans;
}
}
cout<<ans<<endl;
return 0;
}
