跳蚤

Description

很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。现在他想找一个最优的分法让“魔力串”字典序最小。

Input

第一行一个整数 k,K<=15 接下来一个长度不超过 10^5 的字符串 S。

Output

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

Sample Input

2 ababa

Sample Output

ba

//解释： 分成aba和ba两个串，其中字典序最大的子串为ba

---

颓废十多天后的第一篇博客-_- 另外这题题面写错了，是最小化“魔力串”的字典序~

---

思路:

使最大值最小，可以考虑二分答案，即“魔力串”的字典序编号。

根据后缀数组的特性，字符串本质不同的子串数量为 sum=∑n−sa[i]−height[i]+1 。 (式子中的”+1”与个人的后缀数组实现有关) 这个式子的含义是，排名相邻的两个后缀中，不同的前缀的方案数。

于是，二分的区间即为 1−sum 之间。 同时，根据这个式子，可以快速找出某个确定字典序排名对应的子串。

考虑二分一个答案后如何检验。 显然，方法为贪心地分段，若分段段数不超过 k ，则当前答案合法。 由于后缀数组考虑的是后缀的排名，那么从后往前考虑，每次在最前端添加一个字符时，判断当前段与二分的答案之间的排名先后顺序，若大于当前二分排名则需要在上一个位置处分一段，否则不进行分段。 查询串的字典序大小可以使用height数组做成 rmq 来快速实现。

于是这就完成了~

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef pair<int,int> pr; typedef long long ll; const int N=1e6+9; const int K=23; int n,k; int wa[N],wb[N],wc[N]; int sa[N],rk[N],hi[N]; int st[N][K],logs[N]; char s[N]; inline int minn(int a,int b){return a>b?b:a;} inline void calc(char *r,int n,int m) { int *x=wa,*y=wb; for(int i=1;i<=m;i++) wc[i]=0; for(int i=1;i<=n;i++) wc[x[i]=r[i]-'a'+1]++; for(int i=1;i<=m;i++) wc[i]+=wc[i-1]; for(int i=n;i>=1;i--) sa[wc[x[i]]--]=i; for(int j=1,p=0;j<=n && p<n;j<<=1,m=p,p=0) { for(int i=n-j+1;i<=n;i++) y[++p]=i; for(int i=1;i<=n;i++) if(sa[i]>j) y[++p]=sa[i]-j; for(int i=1;i<=m;i++) wc[i]=0; for(int i=1;i<=n;i++) wc[x[i]]++; for(int i=1;i<=m;i++) wc[i]+=wc[i-1]; for(int i=n;i>=1;i--) sa[wc[x[y[i]]]--]=y[i]; swap(x,y); x[sa[1]]=p=1; for(int i=2;i<=n;i++) if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j]) x[sa[i]]=p; else x[sa[i]]=++p; } for(int i=1;i<=n;i++) rk[sa[i]]=i; for(int i=1,p=1;i<=n;i++) { if(p)p--; if(rk[i]==n)continue; int j=sa[rk[i]+1]; while(r[i+p]==r[j+p])p++; hi[rk[i]]=p; } } inline void build() { logs[0]=-1; for(int i=2;i<=n;i++) logs[i]=logs[i>>1]+1; for(int i=1;i<=n;i++) st[i][0]=hi[i]; for(int i=1;i<=logs[n];i++) for(int j=1;j+(1<<i)-1<=n;j++) st[j][i]=minn(st[j][i-1],st[j+(1<<i-1)][i-1]); } inline int lcp(int l,int r) { if(l==r)return n-l+1; l=rk[l];r=rk[r]; if(l>r)swap(l,r);r--; int dt=logs[r-l+1]; return minn(st[l][dt],st[r-(1<<dt)+1][dt]); } inline pr find(ll kth) { static int p; for(p=1;p<=n && kth>n-sa[p]-hi[p-1]+1;p++) kth-=n-sa[p]-hi[p-1]+1; return pr(sa[p],sa[p]+hi[p-1]+kth-1); } inline int cmp(pr a,pr b) { int la=a.second-a.first+1; int lb=b.second-b.first+1; int dt=lcp(a.first,b.first); if(la<=dt || lb<=dt)return la<=lb; return s[a.first+dt]<s[b.first+dt]; } inline bool check(ll mid) { pr kth=find(mid); for(int i=n,lst=n,cnt=1;i>=1;i--) { if(s[i]>s[kth.first])return 0; if(!cmp(pr(i,lst),kth))cnt++,lst=i; if(cnt>k)return 0; } return 1; } int main() { scanf("%d%s",&k,s+1); n=strlen(s+1); calc(s,n,26); build(); ll sum=0; for(int i=1;i<=n;i++) sum+=n-sa[i]-hi[i-1]+1; ll l=1,r=sum,ans=sum,mid; while(l<=r) { mid=l+r>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } pr ret=find(ans); for(int i=ret.first;i<=ret.second;i++) putchar(s[i]); return 0; }