首页 > 代码库 > 【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...）
【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...）
The Revenge of the Princess’ Knight
Problem DescriptionThere is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can’t refuse any request from the devil. Also, this devil is looking like a very cute Loli.
The devil’s birthday is approaching, of course, she wants some beautiful gift from the king. The king search everywhere in this kingdom, and finds a beautiful ring for her.
For simplicity, we can see this ring as a ring(so it is a cycle!) of lowercase characters with length n.
The king’s cute daughter, WJMZBMR, gets nothing from her father in her birthday. She feels very sad. By the influence of the king and the devil, this kingdom is full of lolicon, some people think the king is unfair to his kawayi daughter, so they form a party called princess’s knight and plan to destroy king’s gift for the devil to make things fair.
The knight of the knight (or the lolicon of the lolicon), a man called z*p, has the chance to destroy the ring now. But due to his limitless of strength, he can only cut this ring into exactly k continuous parts. To please the princess, he want among those part, the maximum one respect to the lexicographical order is minimized. How can he do it?
InputThe first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains two integers n and k, which are the length of the ring and the parts z*p can cut.
The next line is a string represent the ring.
n <= 1000,1<=k<=n.
T <= 5.
OutputFor each case, output the maximum part in one line.
Sample Input120 3bbbaaaaabbabaabbbbaa
Sample Outputaaabbabaabbbbaabbb
AuthorWJMZBMR
【题意】
字符串环，割成k分，求最大字典序的那个部分最小
【分析】
果断是看题解的...
二分的答案就是这K个块字典序的上限。假设以i作为起点，由于字典序上限已知，所以我们可以立刻求出i点最远能选到哪个点。
现在问题变成了：已知每一个点最远能跳R的距离，求是否存在一条路径，使得跳K次回到起点。
首先我们假设，每个点的R≠0，意思就是每个点都能向后跳，这样我们只需要用贪心的思想，枚举任意点为起点，然后向后能跳多少跳多少，若跳回来所花的次数T<=K，则为true 【由于每个点都能向后跳，则我们一定能够通过改变几个跳跃，使得T==K 若当前的点数<K，也就是每次只跳1步都没法跳到，当然就是false了】
现在的问题就是，如果有某些点R==0怎么办，也就是它一步也不能向后跳，并且其它位置也不能跳到这个位置。所以我们想到，将这个点删除掉，并且，将所有受到影响的点全部减一，以前可以从 a向后跳3步,但现在 b (a<=b<=a+3)被删掉了，所以a只能挑2步了，这样最多迭代n次 处理之后，所有点的R都是不为0的了。
http://blog.csdn.net/t1019256391/article/details/38347293
对于删点那部分操作呢。我是从后往前扫，要是它要跳到一个为0的点，那么它的skip就变成离这个为0的点最接近的不为0的点。
for(int i=q;i<=q+n-1;i++) nr[i]=0;for(int i=q+n-1;i>=q;i--){ if(sk[i]>0&&sk[i]!=q+n) { if(sk[sk[i]]==0&&nr[sk[i]]==0) sk[i]=0,h--; else if(sk[sk[i]]==0) sk[i]=nr[sk[i]]; } if(sk[i]>0) { for(int j=i+1;j<=q+n-1;j++) { if(sk[j]>0) break; nr[j]=i; } }}所以删点是O（n）的，我二分完之后还每次枚举开始的位置（我自己感觉不枚举会丧失单调性啊。。好像）
然后还有一个二分咯，总时间复杂度是O（n^2 logn）
可以说我还没AC么。。拍了一个上午了。。
.
.
.
.
.
.
好吧现在我A了。。。对拍没用啊！！还是自己Y出的错。。
代码如下：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 #define Maxn 4010 9 #define INF 0xfffffff 10 11 char s[Maxn]; 12 int n,c[Maxn],cl,k; 13 14 void init() 15 { 16 scanf("%s",s+1); 17 cl=0; 18 for(int i=1;i<=n;i++) c[++cl]=s[i]-‘A‘+1; 19 for(int i=1;i<=n;i++) c[++cl]=s[i]-‘A‘+1; 20 } 21 22 int mymin(int x,int y) {return x<y?x:y;} 23 24 int rk[Maxn],sa[Maxn],Rs[Maxn],y[Maxn],wr[Maxn]; 25 void get_sa(int m) 26 { 27 memcpy(rk,c,sizeof(rk)); 28 for(int i=0;i<=m;i++) Rs[i]=0; 29 for(int i=1;i<=cl;i++) Rs[rk[i]]++; 30 for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1]; 31 for(int i=cl;i>=1;i--) sa[Rs[rk[i]]--]=i; 32 33 int p=0,ln=1; 34 while(p<cl) 35 { 36 int kk=0; 37 for(int i=cl-ln+1;i<=cl;i++) y[++kk]=i; 38 for(int i=1;i<=cl;i++) if(sa[i]>ln) y[++kk]=sa[i]-ln; 39 for(int i=1;i<=cl;i++) wr[i]=rk[y[i]]; 40 41 for(int i=0;i<=m;i++) Rs[i]=0; 42 for(int i=1;i<=cl;i++) Rs[wr[i]]++; 43 for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1]; 44 for(int i=cl;i>=1;i--) sa[Rs[wr[i]]--]=y[i]; 45 46 for(int i=1;i<=cl;i++) wr[i]=rk[i]; 47 for(int i=cl+1;i<=cl+ln;i++) wr[i]=0; 48 p=1,rk[sa[1]]=1; 49 for(int i=2;i<=cl;i++) 50 { 51 if(wr[sa[i]]!=wr[sa[i-1]]||wr[sa[i]+ln]!=wr[sa[i-1]+ln]) p++; 52 rk[sa[i]]=p; 53 } 54 m=p,ln*=2; 55 } 56 sa[0]=rk[0]=0; 57 } 58 59 int height[Maxn]; 60 void get_he() 61 { 62 int kk=0; 63 for(int i=1;i<=cl;i++) if(rk[i]!=1) 64 { 65 int j=sa[rk[i]-1]; 66 if(kk) kk--; 67 while(c[i+kk]==c[j+kk]&&i+kk<=cl&&j+kk<=cl) kk++; 68 height[rk[i]]=kk; 69 } 70 height[1]=0; 71 } 72 73 int lcp[2010][2010]; 74 75 void get_lcp() 76 { 77 for(int i=1;i<=cl;i++) 78 { 79 int minn=INF; 80 for(int j=i+1;j<=cl;j++) 81 { 82 minn=mymin(minn,height[j]); 83 lcp[sa[i]][sa[j]]=lcp[sa[j]][sa[i]]=minn; 84 } 85 } 86 for(int i=1;i<=cl;i++) lcp[i][i]=cl-i+1; 87 } 88 89 int sk[Maxn],nr[Maxn]; 90 bool check(int x,int l) 91 { 92 for(int q=1;q<=n;q++) 93 { 94 int h=n; 95 for(int i=q;i<=q+n-1;i++) 96 { 97 if(lcp[i][sa[x]]==0&&c[i]>c[sa[x]]) {h--;sk[i]=0;continue;} 98 99 if(lcp[i][sa[x]]>=l) sk[i]=i+l;100 else if(c[i+lcp[i][sa[x]]]>c[sa[x]+lcp[i][sa[x]]]) sk[i]=i+lcp[i][sa[x]];101 else sk[i]=q+n;102 103 if(sk[i]>q+n) sk[i]=q+n;104 }105 106 for(int i=q;i<=q+n-1;i++) nr[i]=0;107 for(int i=q+n-1;i>=q;i--)108 {109 if(sk[i]>0&&sk[i]!=q+n)110 {111 if(sk[sk[i]]==0&&nr[sk[i]]==0) sk[i]=0,h--;112 else if(sk[sk[i]]==0) sk[i]=nr[sk[i]];113 }114 if(sk[i]>0) 115 {116 for(int j=i+1;j<=q+n-1;j++)117 {118 if(sk[j]>0) break;119 nr[j]=i;120 }121 }122 }123 124 125 if(h<k||sk[q]==0) continue;126 127 int now=q;h=0;128 while(now<q+n)129 {130 now=sk[now];131 h++;132 }133 if(h<=k) return 1;134 }135 return 0;136 }137 138 int fffind(int x)139 {140 int l,r;bool ok=0;141 l=1;142 r=mymin(n,cl-sa[x]+1);143 while(l<r)144 {145 int mid=(l+r)>>1;146 if(check(x,mid)) r=mid,ok=1;147 else l=mid+1;148 }149 if(check(x,l)) ok=1;150 if(!ok) return -1;151 return l;152 }153 154 int eg[Maxn];155 156 void ffind()157 {158 int l,r,h=0;159 for(int i=1;i<=cl;i++) if(sa[i]<=n) eg[++h]=i;160 l=1;r=h;161 while(l<r)162 {163 int mid=(l+r)>>1;164 if(fffind(eg[mid])!=-1) r=mid;165 else l=mid+1;166 }167 int x=fffind(eg[l]);168 for(int i=sa[eg[l]];i<=sa[eg[l]]+x-1;i++) printf("%c",c[i]-1+‘A‘);169 printf("\n");170 }171 172 int main()173 {174 int T;175 scanf("%d",&T);176 while(T--)177 {178 scanf("%d%d",&n,&k);179 init();180 get_sa(200);181 get_he();182 get_lcp();183 ffind();184 }185 return 0;186 }
2016-08-26 14:30:59
【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。