题面大意是：
给一个长度为N的串
\( N \leq 100000 \)
最多分割k次
问若干分割方法中
字典序最大的子串最小是什么
问了一下ZJT大佬……
原来是建出SA之后
先二分后缀
后二分长度
有一些细节要注意，除此之外就很simple了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 100010 char s[N]; int a[N],set[N],n; int SA[N],rk[N],h[N]; int buc[N],fir[N],sec[N],tmp[N]; void make_SA() { copy(s+1,s+1+n,set+1); sort(set+1,set+1+n); For(i,1,n) a[i]=lower_bound(set+1,set+1+n,s[i])-set; fill(buc,buc+1+n,0); For(i,1,n) buc[a[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) rk[i]=buc[a[i]-1]+1; bool unique; for(int p=1;p<=n;p<<=1) { For(i,1,n) fir[i]=rk[i],sec[i]=i+p>n?0:rk[i+p]; fill(buc,buc+1+n,0); For(i,1,n) buc[sec[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) tmp[n- --buc[sec[i]]]=i; fill(buc,buc+1+n,0); For(i,1,n) buc[fir[i]]++; For(i,1,n) buc[i]+=buc[i-1]; for(int j=1,i;j<=n;++j) { i=tmp[j]; SA[buc[fir[i]]--]=i; } unique=true; for(int j=1,i,last=0;j<=n;++j) { i=SA[j]; if(!last) rk[i]=1; else if(fir[i]==fir[last]&&sec[i]==sec[last]) rk[i]=rk[last],unique=false; else rk[i]=rk[last]+1; last=i; } if(unique) break; } for(int j=1,i,k=0;j<=n;j++) { if(rk[j]==1) k=0; else { k>0?--k:k; i=SA[rk[j]-1]; while(i+k<=n&&j+k<=n&&a[j+k]==a[i+k])++k; } h[rk[j]]=k; } } int k; int solve1() { int L[N],Len; int l=1,r=n,mid,cnt,last; for(;r!=l;) { mid=(l+r)>>1; cnt=0; last=n; fill(L,L+1+n,INF); Len=n; For(i,mid+1,n) { Len=min(Len,h[i]); L[SA[i]]=Len; } if(Len==0) cnt=INF; else For(i,1,n) { last=min(last,i+L[i]-1); if(i==last) { cnt++; last=n; } } if(cnt>k) l=mid+1; else r=mid; } return l; } int solve2(int x) { int L[N],Len; int l=h[x]+1,r=n-SA[x]+1,last,cnt,mid; for(;r!=l;) { mid=(l+r)>>1; cnt=0; last=n; fill(L,L+1+n,INF); Len=mid; For(i,x+1,n) { Len=min(Len,h[i]); L[SA[i]]=Len; } L[SA[x]]=mid; For(i,1,n) { last=min(last,i+L[i]-1); if(i==last) { cnt++; last=n; } } if(cnt>k) l=mid+1; else r=mid; } return l; } int main() { read(k); scanf("%s",s+1); n=strlen(s+1); make_SA(); // For(i,1,n) printf("%d ",SA[i]); puts(""); // For(i,1,n) printf("%d ",rk[i]); puts(""); int x=solve1(),ans=solve2(x); // printf("%d",x); For(i,0,ans-1) putchar(s[SA[x]+i]); puts(""); return 0; } |