[CF 1186C] Vus the Cossack and Strings

[CF 1186C] Vus the Cossack and Strings - 1800

문제 설명 : 

0과 1로만 이루어진 문자열 a,b가 주어진다. a의 길이는 b의 길이보다 크거나 같다. a문자열에서 b문자열의 길이와 같게끔 모든 substring들을 뽑아냈을 때, b문자열의 각 인덱스와 비교해서 값이 다른 인덱스의 숫자가 짝수개인 substring이 총 몇 개 존재 하는지 구하는 문제이다.

풀이 : 

결론부터 얘기하면 a문자열의 각 substring에 존재하는 1의 개수의 홀짝과 b에 존재하는 1의 개수의 홀짝이 같다면 정답이 된다.

'값이 다르다'는 얘기는 하나는 0이고 다른 하나는 1이라는 의미이다. 전체에서 이런 케이스가 총 몇 개인지를 세면 되는 것이다. 이걸 세는 방법은 비교할 두 문자열 c,d에서 1이 등장하는 횟수를 각각 cnt_c,cnt_d라 하고, c와 d에서 모두 값이 1인 인덱스의 개수를 k라고 하자. 그러면 값이 다른 인덱스의 개수는 (cnt_c + cnd_d - 2*k)개가 된다. 2*k는 항상 짝수일 것이므로 cnt_c+cnt_d의 값만 짝수면 되므로 둘 다 홀수거나 둘 다 짝수면 된다.

주의할 점 : 

-

배울 점 : 

값이 다른 인덱스의 개수는 곧 0과 1이 총 몇 번 등장하는지 묻는 것과 같다. 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
inline vector<int> int_seperation(int N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 1000009;
 
char a[SIZE],b[SIZE];
int psum[SIZE];
 
int main(){
    scanf("%s %s",a+1,b+1);
    int a_len=strlen(a+1),b_len=strlen(b+1);
 
    for(int i=1 ; i<=a_len ; i++){
        psum[i]=psum[i-1]+(a[i]=='1');    
    }
    int cnt=0;
    for(int i=1 ; i<=b_len ; i++){
        cnt+=(b[i]=='1');
    }
 
    int ans=0;
    for(int i=b_len ; i<=a_len ; i++){
        ans+=((psum[i]-psum[i-b_len])%2==cnt%2);
    }
 
    printf("%d\n",ans);
 
    return 0;
}
/*

*/