题解 CF1979D Fixing a Binary String

· · 题解

观察不出来性质，我选择了最朴素的方法。

题意

定义一个字符串是 k\text{-proper}，需要满足下列两个条件。

定义一次操作为选择一个 p \in [1,n] \cap \mathbb{N^*}，将字符串 s_1s_2\ldots s_n 变为 s_{p+1}s_{p+2}\ldots s_ns_ps_{p-1}\ldots s_1。

你需要找到一个整数 p 使得将字符串 s 恰好一次操作后是 k \text{-proper}。

分析

根据定义可以得到 k\text{-proper} 字符串一定是 k 个 0 和 k 个 1 交替出现的，所以即存在两种：0 开头的和 1 开头的。

于是对应两种字符串，直接枚举 p 判断进行操作后两字符串是否相等即可。

枚举 p 的时间复杂度 O(n)，使用哈希判断两字符串相等的时间复杂度为 O(1)，总体时间复杂度为 O(n)。

注意事项

本题是 CodeForces 上的一道题，由于 Hack 机制的存在，强烈不建议大家写固定模数哈希（双哈希也不建议），所以我选择了随机双底数自然溢出前后缀哈希。

代码

//the code is from chenjh
#include<cstdio>
#include<cstdlib>
#include<random>
#define MAXN 100005
using namespace std;
typedef unsigned int UI;
typedef unsigned long long ULL;
int n,k;
mt19937 mtrd(random_device{}());
const UI P[]={61,3881,6907,19260817,29050993,998244353};//底数列表。
UI p1,p2;
ULL pn1[MAXN],pn2[MAXN],hsl[2][MAXN],hsr[2][MAXN],htl[2][MAXN],htr[2][MAXN];
char s[MAXN],t[MAXN];
void init(ULL hsl[][MAXN],ULL hsr[][MAXN],char *s,const int n){//初始化前后缀哈希。
    hsl[0][0]=hsl[1][0]=0;
    for(int i=1;i<=n;i++)
        hsl[0][i]=hsl[0][i-1]*p1+s[i]-'0'+1,hsl[1][i]=hsl[1][i-1]*p2+s[i]-'0'+1;//前缀哈希。
    hsr[0][n+1]=hsr[1][n+1]=0;
    for(int i=n;i>0;--i)
        hsr[0][i]=hsr[0][i+1]*p1+s[i]-'0'+1,hsr[1][i]=hsr[1][i+1]*p2+s[i]-'0'+1;//后缀哈希。
}
ULL qryl(ULL *hs,ULL *pn,const int l,const int r){//查询前缀。
    return hs[r]-hs[l-1]*pn[r-l+1];
}
ULL qryr(ULL *hs,ULL *pn,const int l,const int r){//查询后缀。
    return hs[l]-hs[r+1]*pn[r-l+1];
}
void solve(){
    scanf("%d %d %s",&n,&k,s+1);
    init(hsl,hsr,s,n);//初始化 s 的哈希值。
    bool f=0;
    for(int i=1;i<=n;f^=!(i++%k)) t[i]=f|'0';//0 开头的 k-proper 序列。
    init(htl,htr,t,n);
    for(int p=1;p<=n;p++)
        if(qryl(hsl[0],pn1,p+1,n)==qryl(htl[0],pn1,1,n-p)&&qryl(hsl[1],pn2,p+1,n)==qryl(htl[1],pn2,1,n-p)
        &&qryr(hsr[0],pn1,1,p)==qryl(htl[0],pn1,n-p+1,n)&&qryr(hsr[1],pn2,1,p)==qryl(htl[1],pn2,n-p+1,n)){
            printf("%d\n",p);return;
        }//判断 s[p+1:n]=t[1:n-p] 和 s[p:1]=t[n-p+1:n]。
    f=1;
    for(int i=1;i<=n;f^=!(i++%k)) t[i]=f|'0';//1 开头的 k-proper 序列。
    init(htl,htr,t,n);
    for(int p=1;p<=n;p++)
        if(qryl(hsl[0],pn1,p+1,n)==qryl(htl[0],pn1,1,n-p)&&qryl(hsl[1],pn2,p+1,n)==qryl(htl[1],pn2,1,n-p)
        &&qryr(hsr[0],pn1,1,p)==qryl(htl[0],pn1,n-p+1,n)&&qryr(hsr[1],pn2,1,p)==qryl(htl[1],pn2,n-p+1,n)){
            printf("%d\n",p);return;
        }//判断条件同上。
    puts("-1");
}
int main(){
    p1=P[mtrd()%6];
    do p2=P[mtrd()%6];while(p1==p2);//随机选择双底数。
    *pn1=*pn2=1;
    for(int i=1;i<MAXN;i++) pn1[i]=pn1[i-1]*p1,pn2[i]=pn2[i-1]*p2;//预处理幂次。
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}