4310: 跳蚤

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 180  Solved: 83

[][][]

Description

很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。

首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。

现在他想找一个最优的分法让“魔力串”字典序最小。

Input

第一行一个整数 k。

接下来一个长度不超过 105 的字符串

Output

输出一行，表示字典序最小的“魔力串”。

Sample Input

13

bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba

Sample Output

cbc

HINT

S的长度<=100000

Source

Solution

首先求出后缀数组和height数组，这样能得到本质不同的子串数目

这里利用：本质不同的子串$=\sum(Len-SA[i]-height[i])$利用SA[],height[]的定义很好想

然后要求最大值最小，显然二分，二分一个mid，求出第mid大的子串

然后贪心的检验，从后往前扫，当字典序超过二分的值时，划分一下，看划分个数与K的关系即可

中间涉及比较，用LCP实现即可，显然ST表非常方便

 

Code

#include
      
        #include
       
         #include
        
          using namespace std; #define maxn 1000100 char S[maxn]; int SA[maxn],len,K; int wa[maxn],wb[maxn],ws[maxn],wv[maxn]; long long tot; int L,R; inline int cmp(int *r,int a,int b,int l) {     return r[a]==r[b]&&r[a+l]==r[b+l]; } inline void DA(char *r,int *sa,int n,int m) {     int p,*x=wa,*y=wb,*t;     for (int i=0; i
         
          =0; i--) sa[--ws[x[i]]]=i;     p=1; for (int j=1; p
          
           =j) y[p++]=sa[i]-j;             for (int i=0; i
           
            =0; i--) sa[--ws[wv[i]]]=y[i]; t=x,x=y,y=t;p=1;x[sa[0]]=0; for (int i=1; i
            
             r) swap(l,r); l++; return RMQ(l,r); } void Get(long long k) { for (int i=1; i<=len; i++) if ((long long)(len-SA[i]-height[i])
             
              =len1) return 1; if (len1>len2 && lcp>=len2) return 0; if (lcp>=len1 && lcp>=len2) return len1>len2? 0:1; return S[l1+lcp]>S[l2+lcp]? 0:1; } int Check() { int cnt=1,last=len-1; for (int i=len-1; i>=0; i--) { if (S[i]>S[L]) return 0; if (!Compare(i,last,L,R)) ++cnt,last=i; if (cnt>K) return 0; } return 1; } int main() { scanf("%d",&K); scanf("%s",S); len=strlen(S); S[len]=0; DA(S,SA,len+1,200); calheight(S,SA,len); ST(len); for (int i=1; i<=len; i++) tot+=len-SA[i]-height[i]; // printf("%d\n",tot); long long l=1,r=tot; while (l<=r) { long long mid=(l+r)>>1; Get(mid); // printf("L=%d R=%d\n",L,R); if (Check()) r=mid-1; else l=mid+1; // printf("%I64d %I64d\n",l,r); } Get(r+1); for (int i=L; i<=R; i++) putchar(S[i]); return 0; }