BZOJ2795: [Poi2012]A Horrible Poem

2019-11-06 06:44:11

字体：大中小

来源：转载

供稿：网友

一个字符串若被分成k个循环节，每个循环节里每种字母出现次数肯定都是一样的，那么循环节的个数k一定是这段字符串里每种字母出现次数的gcd的约数，然后枚举k，hash判一下

#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}void down(int &x,int y){if(x>y)x=y;}const int maxn = 510000;int gcd(int a,int b){return a==0?b:gcd(b%a,a);}ll hk=233,hk2=1e9+7;char s[maxn];ll sum[maxn],pw[maxn];int num[maxn][26];int n,q;bool judge(int l1,int r1,int l2,int r2){ ll s1=sum[r1]-sum[l1-1]*pw[r1-l1+1]; ll s2=sum[r2]-sum[l2-1]*pw[r1-l1+1]; return s1==s2;}int main(){ read(n); scanf("%s",s+1); for(int i=1;i<=n;i++) { for(int j=0;j<26;j++) num[i][j]=num[i-1][j]+(s[i]-j=='a'); } for(int i=1;i<=n;i++) sum[i]=sum[i-1]*hk+(ll)s[i]; pw[0]=1ll; for(int i=1;i<=n;i++) pw[i]=pw[i-1]*hk; read(q); while(q--) { int l,r; read(l); read(r); int lr=(r-l+1); int D=lr; for(int i=0;i<26;i++) D=gcd(D,num[r][i]-num[l-1][i]); int ans=lr; int k=sqrt(D); for(int i=1;i<=k;i++) if(D%i==0) { int tk; tk=lr/i; if(judge(l,r-tk,l+tk,r)) down(ans,tk); if(i*i==D) break; tk=lr/(D/i); if(judge(l,r-tk,l+tk,r)) down(ans,tk); } PRintf("%d/n",ans); } return 0;}

上一篇：【tensorflow1.0学习笔记】（12）实现经典的CNN卷积神经网络之二--VGGNet

下一篇：PyQt5学习笔记01----第一个窗口