首页 > 代码库 > BZOJ2795: [Poi2012]A Horrible Poem
BZOJ2795: [Poi2012]A Horrible Poem
题解：
首先判断长度len是否是l-r的循环节可以做到O（1）
只需判断 l-l+len-1 和 r-len+1-r 是否相同即可，这一步可以用hash
然后循环节一定是总长度的约数。
这样可以做到n√n，但是会T。
一个鬼畜的优化是 枚举在每块内每个字母的个数，这个个数必须是总个数的约数，然后我们取一下gcd，再枚举约数。
实测可过。
另一种做法可以戳这里：http://blog.csdn.net/zeyu_king/article/details/41989279
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 60000014 #define maxm 500+10015 #define eps 1e-1016 #define ull unsigned long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,m,a[maxn],c[maxn],s[maxn][30];32 ull b[maxn],power[maxn];33 const ull base=13131;34 inline ull get(int x,int y){return b[x]-b[x+y]*power[y];}35 inline int gcd(int x,int y){return y?gcd(y,x%y):x;}36 inline int solve()37 {38 int x=read(),y=read(),z=y-x+1,len=y-x+1,t=0;39 for1(i,26)z=gcd(z,s[y][i]-s[x-1][i]);40 if(z==1)return len;41 for(int i=1;i*i<=z;i++)if(z%i==0)42 {43 int tmp=len/z*i;44 if(get(x,len-tmp)==get(y-(len-tmp)+1,len-tmp))return tmp;45 c[++t]=len/i;46 }47 for3(i,t,1)if(get(x,len-c[i])==get(y-(len-c[i])+1,len-c[i]))return c[i];48 return len;49 }50 int main()51 {52 freopen("input.txt","r",stdin);53 freopen("output.txt","w",stdout);54 n=read();n=0;55 char ch=getchar();56 while(ch<‘a‘||ch>‘z‘)ch=getchar();57 for(;ch>=‘a‘&&ch<=‘z‘;ch=getchar())a[++n]=ch-‘a‘+1;58 for3(i,n,1)b[i]=b[i+1]*base+a[i];59 for1(i,n)for1(j,26)s[i][j]=s[i-1][j]+(a[i]==j);60 power[0]=1;61 for1(i,n)power[i]=power[i-1]*base;62 m=read();63 while(m--)printf("%d\n",solve());64 return 0;65 }
2795: [Poi2012]A Horrible Poem
Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 121 Solved: 72
[Submit][Status]
Description
给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。
Input
第一行一个正整数n (n<=500,000)，表示S的长度。
第二行n个小写英文字母，表示字符串S。
第三行一个正整数q (q<=2,000,000)，表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n)，表示询问字符串S[a..b]的最短循环节长度。
Output
依次输出q行正整数，第i行的正整数对应第i个询问的答案。
Sample Input
8
aaabcabc
3
1 3
3 8
4 8
aaabcabc
3
1 3
3 8
4 8
Sample Output
1
3
5
3
5
HINT
Source
鸣谢 jiangzoi&oimaster
BZOJ2795: [Poi2012]A Horrible Poem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。