肉丝哥哥钦定好题 话说我的blog现在为什么到处都是肉丝哥哥

先来想一个弱化版，假如能够n整除K怎么做？

把每个数字看成一个字符串，按字典序排名，这个可以后缀数组解决，然后暴力枚举每种情况，O(1)判两个长度为n/K的数字大小即可

然后不能整除一定是有n-n/K*K个长度为n/K+1的数字

先二分答案排名，枚举起始位置，考虑一个贪心的做法，假如当前能够放一个长度为n/K+1的就立刻放，这样能够保证最优

why？放n/K+1和n/K的区别相当于多往前走了1步，但是多用了一组n/K+1，假如走n/K在未来某一决策能够走n/K+1，那么当前走n/K+1只需付出少用一组就可以拉回同一起跑线。其实也就是具有决策包容性

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int _=1e2;const int maxn=2*2e5+_;int n,K,U;char ss[maxn];int sa[maxn],Rank[maxn];namespace SA{ int Rsort[maxn],tt[maxn]; void getsa(int n,int m) { for(int i=1;i<=n;i++)Rank[i]=ss[i]-'0'; memset(Rsort,0,sizeof(Rsort)); for(int i=1;i<=n;i++)Rsort[Rank[i]]++; for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1]; for(int i=n;i>=1;i--)sa[Rsort[Rank[i]]--]=i; int ln=1,p=0; while(p
           
            0)tt[++k]=sa[i]-ln; memset(Rsort,0,sizeof(Rsort)); for(int i=1;i<=n;i++)Rsort[Rank[tt[i]]]++; for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1]; for(int i=n;i>=1;i--)sa[Rsort[Rank[tt[i]]]--]=tt[i]; for(int i=1;i<=n;i++)tt[i]=Rank[i]; p=1;Rank[sa[1]]=1; for(int i=2;i<=n;i++) { if(tt[sa[i]]!=tt[sa[i-1]]||tt[sa[i]+ln]!=tt[sa[i-1]+ln])p++; Rank[sa[i]]=p; } m=p;ln*=2; } } void GetTrueRank(int n) { int p=0; for(int i=1;i<=2*n-1;i++) if(sa[i]<=n)Rank[sa[i]]=Rank[sa[i]+n]=++p; for(int i=1;i<=n;i++)sa[Rank[i]]=i; } void main(int n){getsa(2*n-1,15);GetTrueRank(n);}}namespace PRINT{ void main(int ans,int len) { int st=sa[ans]; for(int i=1;i<=len;i++)putchar(ss[i+st-1]); puts(""); }}namespace SOL1{ void main() { int ans=(1<<30); for(int i=1;i<=U;i++) { int num=0,tt=0; for(int j=1;j<=K;j++) num=max(num,Rank[i+tt]),tt+=U; ans=min(ans,num); } PRINT::main(ans,U); }}namespace SOL2{ int calc(int em) { int mmax=0; for(int i=1;i<=U+1;i++) { int p=i,num=0; for(int j=1;j<=K;j++) { if(Rank[p]<=em)p+=U+1,num++; else p+=U; if(p>=i+n-1)break; } mmax=max(mmax,num); } return mmax; } void main() { int res=n-U*K; int el=1,er=n,em,ans; while(el<=er) { em=(el+er)/2; if(calc(em)>=res) { er=em-1; ans=em; } else el=em+1; } PRINT::main(ans,U+1); }}int main(){ scanf("%d%d%s",&n,&K,ss+1); U=n/K; for(int i=1;i