传送阵：http://acm.hdu.edu.cn/showproblem.php?pid=4898
题目大意：一个首尾相连的字符串，将其分为k个子串，使得最大的字串最小
将所有子串排序，输出第k小即可
对于有循环节的串，用抽屉原理解决即可
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; struct node{ int l; char ch[2010]; }s[2010]; char ch[4010]; int vis[4010]; int n,k; bool operator < (node a,node b){ for(int i=1;i<=n;++i) if(a.ch[i]!=b.ch[i])return a.ch[i]<b.ch[i]; return a.ch[1]<b.ch[1]; } void work2(){ for(int i=1;i<=n;++i)ch[i+n]=ch[i]; for(int i=1;i<=n;++i){ int k=i+n;s[i].l=i; for(int j=i,l=1;j<k;++j,++l){ s[i].ch[l]=ch[j]; } } sort(s+1,s+n+1); memset(vis,0,sizeof(vis)); for(int i=1;i<k;++i){ int l=s[i].l; vis[l]=1;vis[l+n]=1; } for(int i=s[k].l;!vis[i];++i) putchar(ch[i]); return; } int Next[4010]; void get_pre(){ char s[4010]; for(int i=1;i<=n;++i)s[i]=ch[i],s[i+n]=s[i]; int i=1,j=2,k=0; for(;i<=n&&j<=n&&k<=n;){ if(s[i+k]==s[j+k])k++; else if(s[i+k]>s[j+k])i=i+k+1,k=0; else if(s[i+k]<s[j+k])j=j+k+1,k=0; if(i==j)j++; } if(i>j)i=j; for(k=1;k<=n;++k) ch[k]=s[i+k-1]; } bool check(){ Next[0]=Next[1]=0; for(int i=2;i<=n;++i){ int j=Next[i-1]; while(j&&ch[j+1]!=ch[i])j=Next[j]; Next[i]=ch[j+1]==ch[i]?j+1:0; } int l=n-Next[n]; if(n%l==0)return 1; return 0; } void work1(){ int l=n-Next[n]; int a=n/l; if(a<k)work2(); else{ if(a%k==0){ int p=a/k; int len=l*p; for(int i=1;i<=len;++i)putchar(ch[i]); return; }else{ int p=a/k+1; int len=l*p; for(int i=1;i<=len;++i)putchar(ch[i]); return; } } } void init(){ scanf("%d%d",&n,&k); scanf("%s",ch+1); get_pre(); } void work(){ if(check())work1(); else work2(); } int T; int main(){ scanf("%d",&T); while(T--){ init(); work(); puts(""); } return 0; }