Codeforces 1295B - Infinite Prefixes

题目大意：

给定一个长度为n的字符串s，由字符0和1组成

你可以让这个字符串s无限延长

就令字符串t=sssssss......

求字符串t有多少个前缀字符串中，0的个数减去1的个数等于x

解题思路：

本文可能讲的很复杂……不知道多套了几个例子进去会不会好点……

对于一个周期，可以先记录前缀和到某个位置k时答案的大小

这里用一个数组cha记录这个差

最后cha[i]记录的是一个周期内出现i这个差的次数

就例如样例1的010010

可以得到不同前缀的差分别为1 0 1 2 1 2

那么cha[0]=1 cha[1]=3 cha[2]=2

又因为可能差会出现负数的情况，直接用cha数组可能会下标越界

取极限情况，得到差的范围是-1e5~1e5

所以cha开至少20w个单位，并定义一个基本常量v=100000

之后引用cha时数组内需要恒加上v

再用mx和mn两个变量记录一个周期内出现的差的最大最小值

处理完后，先进行特判

如果最后的差值d=0

说明t字符串的前缀中“0个数-1个数”的值总是在0上下浮动

此时，如果x这个数在一个周期内可能的差中出现过，可以说明不论在这个前缀之前加多少个周期（对答案贡献为0），都能满足“0个数-1个数”的值不变（x+0=x）

即 x==0||x<0&&x>=mn||x>0&&x<=mx

此时直接输出-1，表示有无穷个解

例：s=0101 x=1

对于0 010 01010 0101010 ......

都能满足x=1

否则，x永远不可能达到

例：s=1010 x=1

对于1 10 101 1010 10101 ......

差值总是在-1 0 -1 0 -1 0之间变动

永远不可能达到x=1

然后，如果d不等于0

先考虑d>0的情况

说明每过一个周期差值会正增长

如果x为负数

只需要考虑第一个周期能否达到x的值即可

所以此时，如果x比差值中最小的还要小，即d>0&&x<mn

直接输出0，无解

例：s=010 x=-1

第一个周期中出现的差值为1 0 1

-1没有出现过

所以之后不论取怎样的前缀 010 0100 01001 010010

都不可能出现-1（因为d>0）

相同的，如果d<0&&x>mx

同样永远达不到x的值，输出0，无解

例：s=101 x=1

第一个周期中出现的差值为-1 0 -1

1没有出现过

所以之后不论取怎样的前缀 101 1011 10110 101101

都不可能出现1（因为d<0）

然后就可以处理有解的情况了

特殊点：前缀可以为空

为空前缀时差值为0

又因为上面的周期没有考虑这点

所以在x=0时，让答案+1

这点在样例3中有出现

然后d>0和d<0仍然分开讨论

因为在x很大或者很小时

有很大一部分可以跳过（直接模拟这里会成为超时点）

例：s=010010 x=10000

此时这个s周期的d=2 mx=2 mn=0

在累积前缀差值小于9998的所有周期中，都不可能在他的周期内变化达到x

而在前面有了4999个s字符串后，添加第5000个s过程中，才有可能让0和1的差值达到x

所以这4999个s的情况可以直接用公式计算跳过

d>0时，因为一个周期浮动最大到mx过，所以可以让i变成x-mx（这也是前面9998的由来）

但也要注意s趋近于0时，x-mx小于0的情况，因为d>0，所以这个不可取

综上，让i=max(x-mx,0)

然后考虑i是不是一些周期拼接后会得到的值（保证i是多个整周期拼接后的差值），也就是看i是不是d的倍数

如果不是，让i增大到大于i的第一个d的倍数

转换可以用i=(i/d+1)*d

例：s=010010 x=9 d=2，计算得到dd=7，但是7不是2的倍数，所以要把dd变成8

然后，循环把可能的差值加到答案里去

这里用到的原理是这样的

假设k个周期后0和1的差值为dd

然后考虑第k+1个周期加入前缀的变化情况

又因为前面求过一个周期中差值变化情况 cha[i]表示i这个差值出现了这么多次

所以，x-dd，也就是第k+1这个周期只要能达到这个差值，就能让整个前缀中0和1差值等于x，为答案做出贡献

换言之 cha[x-dd+v] 也就是加入第k+1个周期的过程中，前缀内0和1的差值等于x的情况总数

所以可以把 cha[x-dd+v] 直接加到答案内

拿上面的例子：

例：s=010010 x=10000

此时d=2 mx=2 mn=0

公式计算得到dd=9998

在s的一个周期中，差值出现的6种情况分别为1 0 1 2 1 2

cha[0]=1 cha[1]=3 cha[2]=2

在这一个周期中，只有差值为2是才能和前面的9998构成x=10000，对答案做出贡献

总共有2种情况在，ans=2

然后dd再加上一个周期，dd=dd+d=10000

此时对于下一个周期，考虑是否存在差值为0，能让dd+0=x继续成立

发现cha[0]=1，所以差值为0在下一个周期中还能出现一次，ans=1+2=3

同理，d<0时只是递增方向相反了而已

i=min(x-mn,0)

其后处理同上

例：s=101101 x=-10000

此时d=-2 mx=0 mn=-2

公式得到dd=-9998

cha[0]=1 cha[-1]=3 cha[-2]=2

因为-9998-2=-10000=x

ans=cha[-2]=2

然后dd+=d 即-9998-2=-10000

因为-10000-0=-10000=x

ans=2+cha[0]=3

#include<bits/stdc++.h>

using namespace std;

int cha[];

string s;

const int v=;

void solve(){

    int n,x,i,n0=,n1=,d,ans=,mx=,mn=;

    memset(cha,,sizeof cha);

    cin>>n>>x>>s;

    for(i=;i<n;i++){

        if(s[i]=='')

            n0++;

        else

            n1++;

        d=n0-n1;

        cha[d+v]++;

        mx=max(mx,d);

        mn=min(mn,d);

    }

    //此时和接下来的d为一整个周期的0的个数-1的个数的值

    if(d==){//如果最终0和1的个数相同

        if(x==||x<&&x>=mn||x>&&x<=mx)//如果x曾在差值中出现过

            cout<<"-1\n";

        else

            cout<<"0\n";

        return;

    }

    if(d>&&x<mn||d<&&x>mx){//永远不可能达到x

        cout<<"0\n";

        return;

    }

    if(x==)

        ans++;//空前缀

    if(d>){

        i=max(x-mx,);

        if(i%d)

            i=(i/d+)*d;

        for(;abs(x-i)<=v&&cha[x-i+v];i+=d)

            ans+=cha[x-i+v];

    }

    else{

        i=min(x-mn,);

        if(i%d)

            i=(i/d+)*d;

        for(;abs(x-i)<=v&&cha[x-i+v];i+=d)

            ans+=cha[x-i+v];

    }

    cout<<ans<<'\n';

}

int main(){

    ios::sync_with_stdio();

    cin.tie();cout.tie();

    int T;cin>>T;while(T--)

        solve();

    return ;

}

巴特西

Codeforces 1295B - Infinite Prefixes

最新文章

热门文章