codeforces 1186C Vus the Cossack and Strings

题目链接：https://codeforc.es/contest/1186/problem/C

题目大意：xxxxx(自认为讲不清。for instance)

　　例如：a="01100010" b="00110"。

　　我们把a截到b的长度就有4个字串。

　　a1=01100 a2=11000 a3=10001 a4=00010

　　f(s1,s2)表示是s1与s2异或后1的个数

　　题目要求每个a子串与b的f(ai,b)的值为偶数的个数。

ps：暑假第一天，签到写个稍微简单一点的题

思路：

　　如果在例子中b串是"00000"。那么题目变为求ai的1的个数为偶数的个数

　　这里我们用前缀和来求就非常好了。

　　a1= 01100 符合题意

　　a2= 11000 符合题意

　　a3= 10001 符合题意

　　a4= 00010 不符合题意

　　前缀和应该会吧。O(1)就可以知道和。然后判断一下奇偶就好了

　　但是b串不一定是"00000"

　　这时我们看一下如果b="00100"会怎么样？

　　a1= 01000 不符合题意

　　a2= 11100 不符合题意

　　a3= 10101 不符合题意

　　a4= 00110 符合题意

　　所以，我们可以得出当b串的1的个数为奇数是我们求a子串的1的个数为奇数的个数

　　反之，求偶数的个数

　　愉快的贴代码^-^

#include <bits/stdc++.h>
using  namespace std;
#define N 1000100
 
int x[N];
int ser=0;
signed main()
{
    ios::sync_with_stdio(false);
    string s,ss;
    cin>>s>>ss;
 
    for(auto&c:s){
        int a=(c==‘1‘);
        x[++ser]=a;
        x[ser]+=x[ser-1];
    }
 
    int b=0;
    for(auto&c:ss){
        b^=(c==‘1‘);
    }
    int Ans=0;
    for(int i=ss.size();i<=ser;i++){
        //cout<<x[i]<<" "<<x[i-ss.size()]<<endl;
        Ans+=!((x[i]-x[i-ss.size()])&1)^b;
    }
    cout<<Ans;
    return 0;
}

codeforces 1186C Vus the Cossack and Strings

原文：https://www.cnblogs.com/opooopooo/p/11112253.html