codeforces-Ed81-B

codeforces-Ed81-B

七月 08, 2020

B - Infinite Prefixes

题意
给出一个长度为n 的01串 s 和一个空串t
你可以在t后接任意个s
问 t中可以出现几个位置
他的前缀 0的数量cnt0 和前缀1的数量cnt1
满足 cnt0-cnt1=x
如果有无限个输出-1

一个s中它的cnt0-cnt1=de是固定的
t无论接多少s 它总的cnt0-cnt1=kde
所以题意转化成 kde+vis[i]=x 求符合要求的k有几个
vis[i]=一个s中出现的所有 前缀cnt0-cnt1的值
比如 s=00111
vis[]={1,2,0,-1} 0比1多一个 0比1多两个 ，，，
枚举vis[i]求(x-vis[i])%de==0

注意de=0 时特判 如果有vis[i]==x那一定有无限个
如果没有那么输出0

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define IO std::ios::sync_with_stdio(false);

# define endl '\n'

string s,t;
//int de[(int)1e5+5];
int main() {
    int T;cin>>T;
    while(T--){
        int n,x;cin>>n>>x;
        string s;cin>>s;
        int len=s.size();
        vector<int>vis;
        //for(int i=0;i<len;i++)de[i]=0;
        int cnt1=0,cnt0=0;
        for(int i=0;i<len;i++){
            if(s[i]=='1')cnt1++;
            else cnt0++;
            //de[i]=cnt0-cnt1;
            vis.push_back(cnt0-cnt1);
        }
        int de=cnt0-cnt1;
        //cout<<de<<endl;
        if(de==0){
            bool flag=0;
            for(auto i:vis){
                if(i==x){
                    flag=1;
                    break;
                }
            }
            if(flag)cout<<-1<<endl;
            else cout<<0<<endl;
        }
        //else if((de>0&&x<0)||(de<0&&x>0))cout<<0<<endl;//这一步多余且会造成错误两者不同号也有可能出现有限个解
        else{
            int ans=0;//bool flag=0;
            if(x==0)ans++;
            for(auto i:vis){
                int val=x-i;
                if(val<0&&de>0)continue;
                if(val>0&&de<0)continue;
                else if(de!=0&&abs(val)%abs(de)==0)ans++;
            }
            ///if(flag)cout<<-1<<endl;
            cout<<ans<<endl;
        }
    }
}