bzoj4310

题解：

后缀数组求出本质不同的串

然后二分答案

贪心判断是否可行

代码：

#include<bits/stdc++.h>

const int N=;

using namespace std;

typedef long long ll;

char s[N];

ll L,R,mid;

int K,n,rk[N],sa[N],height[N],tmp[N],cnt[N],Log[N];

int f[][N],g[N],len,nowl,nowr,ansl,ansr;

void SA(int n,int m)

{

      n++;

      for (int i=;i<n;i++)cnt[rk[i]=s[i]]++;

      for (int i=;i<m;i++)cnt[i]+=cnt[i-];

      for (int i=;i<n;i++)sa[--cnt[rk[i]]]=i;

      for (int k=;k<=n;k<<=)

       {

        for (int i=;i<n;i++)

         {

              int j=sa[i]-k;

              if (j<)j+=n;

              tmp[cnt[rk[j]]++]=j;

           }

          int j=;

        sa[tmp[cnt[]=]]=j=;

        for (int i=;i<n;i++)

         {

              if (rk[tmp[i]]!=rk[tmp[i-]]||rk[tmp[i]+k]!=rk[tmp[i-]+k])cnt[++j]=i;

             sa[tmp[i]]=j;

         }

        memcpy(rk,sa,n*sizeof(int));

        memcpy(sa,tmp,n*sizeof(int));

        if (j>=n-)break;

       }

      for (int i,k,j=rk[height[i=k=]=];i<n-;i++,k++)

     while (~k&&s[i]!=s[sa[j-]+k])height[j]=k--,j=rk[sa[j]+];

}

int lcp(int x,int y)

{

      if (x==y)return n-x;

      x=rk[x],y=rk[y];

      if (x>y)swap(x,y);

      int k=Log[y-x];

      return min(f[k][x+],f[k][y-(<<k)+]);

}

void kth(ll k)

{

      ll s=;

      for (int i=;i<=n;s+=n-sa[i]-height[i],i++)

     if (s+n-sa[i]-height[i]>=k)

      {

        nowl=sa[i],nowr=nowl+height[i]+k-s-;

        len=nowr-nowl+;

        return;

        }

}

int ask(int l,int r)

{

      int t=min(lcp(l,nowl),min(r-l+,len));

      if (t==r-l+&&t<=len)return ;

      if (t==len)return ;

      return s[l+t]<=s[nowl+t];

}

int check()

{

    int j,k=;

      for (int i=n-;~i;i=j,k++)

     {

        for (j=i;~j;j--)

         if (!ask(j,i))break;

        if (j==i)return ;

        }

  return k<=K;

}

int main()

{

      scanf("%d%s",&K,s);

      n=strlen(s);

     SA(n,);

      for (int i=;i<=n;i++)Log[i]=Log[i>>]+;

      for (int i=;i<=n;i++)f[][i]=height[i];

      for (int j=;j<;j++)

     for (int i=;i+(<<j-)<=n;i++)f[j][i]=min(f[j-][i],f[j-][i+(<<j-)]);

      for (int i=;i<=n;i++)R+=n-sa[i]-height[i];

     while (L<=R)

     {

        kth(mid=(L+R)>>);

        if (check())ansl=nowl,ansr=nowr,R=mid-;

        else L=mid+;

       }

      for (int i=ansl;i<=ansr;i++)putchar(s[i]);

      return ;

}