题目大意：求恰好出现n次的字典序最小的串。
题目思路：后缀数组加单调栈，n为1的时候要特判，不过数据有点水，不判都能过。
[cpp] #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define M 100010 int max(int a,int b) { return a>b a:b; } int min(int a,int b) { return a } int height[M],rank[M],r[M],sa[M]; int ts[M],ta[M],tb[M],tv[M],pos,st,ed; struct node { int h,st,w; }q[M]; bool cmp(int *y,int a,int b,int l) { return y[a]==y[b]&&y[a+l]==y[b+l]; } void da(int n,int m) { int i,j,*x=ta,*y=tb,p; for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--) sa[--ts[x[i]]]=i; for(j=1,p=1;p { p=0; for(i=n-j;i for(i=0;i=j) y[p++]=sa[i]-j; for(i=0;i for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--) sa[--ts[tv[i]]]=y[i]; swap(x,y); x[sa[0]]=0; p=1; for(i=1;i { if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1; else x[sa[i]]=p++; } } } void calh(int n) { int i,k,tmp; for(i=1;i<=n;i++) rank[sa[i]]=i; k=0; for(i=0;i { tmp=sa[rank[i]-1]; for(;r[i+k]==r[tmp+k];k++) ; height[rank[i]]=k; k --k:0; } } char s[M]; int solve(int len,int k) { int i; node tmp; int top=0,tail=0; height[len+1]=0; if(k==1) { st=0,ed=len; return 1; } for(i=1;i<=len+1;i++) { tmp.h=0; tmp.st=i; while(top=height[i]) { tmp.h+=q[tail-1].h; tmp.st=q[tail-1].st; tmp.w=q[tail-1].w; if(tmp.h==k-1&&tmp.w>height[i]) { st=sa[tmp.st]; if(top ed=st+max(height[i]+1,q[tail-2].w+1); else ed=st+height[i]+1; return 1; } tail--; } if(height[i]==0) continue; tmp.w=height[i]; tmp.h+=1; q[tail++]=tmp; } return 0; } int main() { int i,k,len; while(scanf("%d",&k)!=EOF) { scanf("%s",s); len=strlen(s); for(i=0;i r[i]=s[i]+1; r[len]=0; da(len+1,200); calh(len); if( solve(len,k)==0) { puts("impossible"); continue; } for(i=st;i printf("%c",s[i]); puts(""); } }