bzoj 4310 跳蚤

bzoj 4310 跳蚤

​​ Description

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

Input

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

Output

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

Sample Input

2 ababa Sample Output

ba //解释： 分成aba和ba两个串，其中字典序最大的子串为ba 题意：分成最多k段 取出每段里字典序最大的子串 再把这取出的所有子串中选一个字典序最大的 求整个串字典序最大的最小 首先二分 二分我答案是字典序第几小的串 （不重复中第k小 然后找到这个第k小的在哪里 贪心的针对全局构造 使得不存在构造之后出现比我大的子串 如果满足说明二分的正确缩小范围 因为显然字典序越靠后的 越容易满足答案 如何找第k小的 需要在排好序的后缀从前往后扫 即可 如何贪心 如果发现我当前这个长度区间比我第k小要大 那么就想办法把我的首字母切掉，如果首字母比较大说明第k小 不符合答案

#include#include#include#define ll long longusing namespace std;const int N=1e5+10;ll sum;int K,mn[N][17],Log[N],rk[N<<1],rk1[N<<1],ansl,ansr;int cnt[N],height[N],tmp[N],sa[N],n;char s[N];inline int lcp(int x,int y){ if (x==y) return n-x+1; x=rk[x];y=rk[y];if (x>y) swap(x,y);x+=1;//printf("%d %d\n",x,y); int t=Log[y-x+1];//printf("%d\n",t); return min(mn[x][t],mn[y-(1<>1]+1; for (int i=1;i<=n;++i) mn[i][0]=height[i]; for (int j=1;j<=Log[n];++j) for (int i=1;i+(1<1 static int len1,len2,lp;len1=r1-l1+1;len2=r2-l2+1;lp=lcp(l1,l2); if (lp>=len2&&len1>len2) return 0; if (lp>=len1&&len2>=len1) return 1; if (lp>=len1&&lp>=len2) return len1<=len2; return s[l1+lp]<=s[l2+lp];}inline bool check(){static int lst,tim;lst=n;tim=1; for (int i=n;i;--i){ if (s[i]>s[ansl]) return 0; if (!cmp(i,lst,ansl,ansr)) lst=i,++tim; if (tim>K) return 0; }return 1;}int main(){ freopen("bzoj4310.in","r",stdin); scanf("%d",&K);scanf("%s",s+1);n=strlen(s+1); for (int i=1;i<=n;++i) cnt[s[i]]=1;int m=300; for (int i=1;i<=m;++i) cnt[i]+=cnt[i-1]; for (int i=1;i<=n;++i) rk[i]=cnt[s[i]];int k=0; for (int p=1;k!=n;p<<=1,m=k){ for (int i=1;i<=m;++i) cnt[i]=0; for (int i=1;i<=n;++i) ++cnt[rk[i+p]]; for (int i=1;i<=m;++i) cnt[i]+=cnt[i-1]; for (int i=n;i;--i) tmp[cnt[rk[i+p]]--]=i; for (int i=1;i<=m;++i) cnt[i]=0; for (int i=1;i<=n;++i) ++cnt[rk[i]]; for (int i=1;i<=m;++i) cnt[i]+=cnt[i-1]; for (int i=n;i;--i) sa[cnt[rk[tmp[i]]]--]=tmp[i]; memcpy(rk1,rk,sizeof(rk)>>1);k=rk[sa[1]]=1; for (int i=2;i<=n;++i){ if (rk1[sa[i]]!=rk1[sa[i-1]]||rk1[sa[i-1]+p]!=rk1[sa[i]+p]) ++k; rk[sa[i]]=k; } }k=0; for (int i=1;i<=n;++i){ if (rk[i]==1) continue;k=k==0?0:k-1; while(s[i+k]==s[sa[rk[i]-1]+k]) ++k; height[rk[i]]=k; }init();for (int i=1;i<=n;++i) sum+=i,sum-=height[i];/* for (int i=1;i<=n;++i){ for (int j=sa[i];j<=n;++j) putchar(s[j]);puts(""); }*/// for (int i=1;i<=n;++i) printf("%d\n",height[i]); ll l=1,r=sum,mid;int L,R; while(l<=r){ get_k(mid=l+r>>1); if (check()) L=ansl,R=ansr,r=mid-1;else l=mid+1; }for (int i=L;i<=R;++i) putchar(s[i]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。