C. Vus the Cossack and Strings(异或判断二进制位匹配数奇偶)
Problem - C - Codeforces
题目描述
Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings aa and bb . It is known that |b| \\leq |a|∣b∣≤∣a∣ , that is, the length of bb is at most the length of aa .
The Cossack considers every substring of length |b|∣b∣ in string aa . Let's call this substring cc . He matches the corresponding characters in bb and cc , after which he counts the number of positions where the two strings are different. We call this function f(b, c)f(b,c) .
For example, let b = 00110b=00110 , and c = 11000c=11000 . In these strings, the first, second, third and fourth positions are different.
Vus the Cossack counts the number of such substrings cc such that f(b, c)f(b,c) is even.
For example, let a = 01100010a=01100010 and b = 00110b=00110 . aa has four substrings of the length |b|∣b∣ : 0110001100 , 1100011000 , 1000110001 , 0001000010 .
f(00110, 01100) = 2f(00110,01100)=2 ;
f(00110, 11000) = 4f(00110,11000)=4 ;
f(00110, 10001) = 4f(00110,10001)=4 ;
f(00110, 00010) = 1f(00110,00010)=1 .
Since in three substrings, f(b, c)f(b,c) is even, the answer is 33 .
Vus can not find the answer for big strings. That is why he is asking you to help him.
输入格式
The first line contains a binary string aa ( 1 \\leq |a| \\leq 10^61≤∣a∣≤106 ) — the first string.
The second line contains a binary string bb ( 1 \\leq |b| \\leq |a|1≤∣b∣≤∣a∣ ) — the second string.
输出格式
Print one number — the answer.
题意翻译
给定两个由0,10,1构成的字符串aa和bb，其中|b|\\leq |a|.∣b∣≤∣a∣.
对于aa的某个长度为|b|∣b∣的字串cc，记对应位不同的字符数为f(b, c).f(b,c).
如：当b=00110,c=11000b=00110,c=11000时，f(b, c) = 4,f(b,c)=4,其中第1,2,3,41,2,3,4位不同。
输入输出样例
输入 #1复制
01100010
00110
输出 #1复制
3
输入 #2复制
1010111110
0110
输出 #2复制
4
题解:
考虑一次匹配的奇偶,
举个例子
1100
0011
不匹配个数是偶数
1100
1100
不匹配个数是偶数
1100
1010
不匹配个数依旧是偶数
所以位置是不用考虑的,因为涉及到变化,如果为2,相当于奇偶不变,奇数就更不用考虑了,相当于数目不变
所以可以利用异或来看一段不匹配的是不是偶数,
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
const int N = 1e6 + 10;
void solve()
{string a;string b;cin >> a >> b;int n = a.size();int m = b.size();a = " " + a;b = " " + b;int ans = 0;int s = 0;for(int i = 1;i <= m;i++){s = s ^(a[i] - '0')^(b[i] - '0');}if(s%2 == 0){ans++;}for(int i = m + 1;i <= n;i++){s = s^(a[i - m] - '0')^(a[i] - '0');if(s%2 == 0)ans++;}cout << ans;
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;
// cin >> t;while(t--){solve(); }
}当然前缀和也可以
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e6+1000;
typedef long long LL;
char a[maxn],b[maxn];
LL sum[maxn];
void solve()
{LL alen=strlen(a+1);LL blen=strlen(b+1);for(LL i=1;i<=alen;i++){sum[i]=sum[i-1]+(a[i]=='1');}LL cnt1=0;for(LL i=1;i<=blen;i++){if(b[i]=='1') cnt1++;} LL ans=0;for(LL i=1;i<=alen-blen+1;i++){if ( ( (sum[i+blen-1]-sum[i-1])+cnt1)%2==0){ans++;}}cout<<ans<<endl;
}
int main(void)
{cin>>a+1;cin>>b+1;solve();
return 0;
}
