欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CodeForces 526D Om Nom and Necklace

程序员文章站 2022-05-18 21:19:52
呵呵,先贴一张图:(这就是我CodeForces的头像(至少现在是)) "洛谷题目页面传送门" & "CodeForces题目页面传送门" 给定字符串$a$,求它的每一个前缀,是否能被表示成$m+1$个字符串$A$和$m$个字符串$B$交错相连的形式,即求$\forall i\in[1,n],\le ......

呵呵,先贴一张图:(这就是我codeforces的头像(至少现在是))

CodeForces 526D Om Nom and Necklace

洛谷题目页面传送门 & codeforces题目页面传送门

给定字符串\(a\),求它的每一个前缀,是否能被表示成\(m+1\)个字符串\(a\)\(m\)个字符串\(b\)交错相连的形式,即求\(\forall i\in[1,n],\left[\exists a,\exists b,a_{1\sim i}=\underbrace{a+b+a+\cdots+a+b+a}_{m+1\text{个}a,m\text{个}b}\right]\)

\(|a|\in[1,10^6]\)

考虑把\(a+b\)看作一个整体,这样问题就转化为了求\(a\)的每一个前缀是否能被表示成\(m\)个字符串\(s\)相连再连上一个\(s\)的前缀(可以\(=\varnothing\),也可以\(=s\))。

我们先考虑怎么在短时间内知道一个\(a\)的前缀是否可以被表示为\(m\)\(s\)相连,如果可以就再往后扩展。这是一个非常经典的问题。设要求的是\(a\)的前缀\(a_{1\sim i}\)。首先,得满足\(m|i\),于是我们可以枚举\(\dfrac im\),即\(|s|\)。然后如果\(a_{1\sim i-\frac im}=a_{1+\frac im\sim i}\),那么\(a_{1\sim i}\)可以被表示为\(m\)\(s\)相连(这个很好证吧,错位相等)。我们可以拿\(a_{1+\frac im\sim i}\)去匹配\(a_{1\sim \frac im}\),这个显然可以哈希,而在枚举\(|s|\)\(a_{1\sim i-\frac im}\)永远是\(a\)的前缀,所以也可以z算法(如果聪明的读者还不知道z算法是什么,please点击这个)。

接下来要考虑如何往后拓展。这个比较简单,往后拓展的那段子串长度一定\(\in[0,|s|]\),并且要与\(a\)的前缀匹配。这不正是z算法的专长吗?\(\min(|s|,z_{m|s|+1})\)不就是能往后拓展的最长长度吗?这个最长长度也可以哈希+二分,但那复杂度就带\(\log\)了。对了,能往后拓展最长\(z_{m|s|+1}\)个,就意味着\(\forall i\in[m|s|,m|s|+z_{m|s|+1}]\)\(a_{1\sim i}\)都能被表示成\(m+1\)个字符串\(a\)\(m\)个字符串\(b\)交错相连的形式,这是个区间答案赋成\(1\)的操作,可以用线段树或树状数组维护,但更简单的有差分。最后被赋成\(1\)的次数若\(>0\),则答案为\(1\),否则为\(0\)

感觉说的不太清楚。。。具体看代码吧(也不一定能看懂啊)

#include<bits/stdc++.h>
using namespace std;
const int n=1000000;
int n/*|a|*/,m/*要被表示成m+1个a与m个b交错相连的形式*/;
char a[n+5];//字符串 
int z[n+1];//z数组 
void z_init(){//z算法 
    z[1]=n;
    int zl=0,zr=0; 
    for(int i=2;i<=n;i++)
        if(zr<i){
            while(i+z[i]<=n&&a[i+z[i]]==a[1+z[i]])z[i]++;
            if(z[i])zl=i,zr=i+z[i]-1;
        }
        else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
        else{
            z[i]=zr-i+1;
            while(i+z[i]<=n&&a[i+z[i]]==a[1+z[i]])z[i]++;
            zl=i;zr=i+z[i]-1;
        }
}
int d[n+1];//差分数组 
int main(){
    cin>>n>>m>>a+1;
    z_init();
    for(int i=1;i*m<=n;i++)//枚举|s| 
        if(z[i+1]>=i*(m-1)){//a[1~i*m]可以被表示为m个s相连 
//          cout<<i<<" "<<i*m+min(i,z[i*m+1])<<"\n";
            d[i*m]++;//往后拓展的左端点差分数组++ 
            if(i*m+min(i,z[i*m+1])+1<=n)d[i*m+min(i,z[i*m+1])+1]--;//往后拓展的右端点的下一个差分数组-- 
        }
    int now=0;
    for(int i=1;i<=n;i++){
        now+=d[i];//现在now为i的答案被赋成1的次数 
        cout<<!!now;//转为bool值 
    }
    return 0;
}
/*1
7 2
bcabcab
*/
/*2
21 2
ababaababaababaababaa
*/