【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6565字，纯文字阅读大概需要10分钟。
内容图文
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个块字典序的上限。假设以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>
7usingnamespace std;
8#define Maxn 4010
9#define INF 0xfffffff
10 11char s[Maxn];
12int n,c[Maxn],cl,k;
13 14void init()
15{
16 scanf("%s",s+1);
17 cl=0;
18for(int i=1;i<=n;i++) c[++cl]=s[i]-‘A‘+1;
19for(int i=1;i<=n;i++) c[++cl]=s[i]-‘A‘+1;
20}
21 22int mymin(int x,int y) {return x<y?x:y;}
23 24int rk[Maxn],sa[Maxn],Rs[Maxn],y[Maxn],wr[Maxn];
25void get_sa(int m)
26{
27 memcpy(rk,c,sizeof(rk));
28for(int i=0;i<=m;i++) Rs[i]=0;
29for(int i=1;i<=cl;i++) Rs[rk[i]]++;
30for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1];
31for(int i=cl;i>=1;i--) sa[Rs[rk[i]]--]=i;
32 33int p=0,ln=1;
34while(p<cl)
35 {
36int kk=0;
37for(int i=cl-ln+1;i<=cl;i++) y[++kk]=i;
38for(int i=1;i<=cl;i++) if(sa[i]>ln) y[++kk]=sa[i]-ln;
39for(int i=1;i<=cl;i++) wr[i]=rk[y[i]];
40 41for(int i=0;i<=m;i++) Rs[i]=0;
42for(int i=1;i<=cl;i++) Rs[wr[i]]++;
43for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1];
44for(int i=cl;i>=1;i--) sa[Rs[wr[i]]--]=y[i];
45 46for(int i=1;i<=cl;i++) wr[i]=rk[i];
47for(int i=cl+1;i<=cl+ln;i++) wr[i]=0;
48 p=1,rk[sa[1]]=1;
49for(int i=2;i<=cl;i++)
50 {
51if(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 59int height[Maxn];
60void get_he()
61{
62int kk=0;
63for(int i=1;i<=cl;i++) if(rk[i]!=1)
64 {
65int j=sa[rk[i]-1];
66if(kk) kk--;
67while(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 73int lcp[2010][2010];
74 75void get_lcp()
76{
77for(int i=1;i<=cl;i++)
78 {
79int minn=INF;
80for(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 }
86for(int i=1;i<=cl;i++) lcp[i][i]=cl-i+1;
87}
88 89int sk[Maxn],nr[Maxn];
90bool check(int x,int l)
91{
92for(int q=1;q<=n;q++)
93 {
94int h=n;
95for(int i=q;i<=q+n-1;i++)
96 {
97if(lcp[i][sa[x]]==0&&c[i]>c[sa[x]]) {h--;sk[i]=0;continue;}
98 99if(lcp[i][sa[x]]>=l) sk[i]=i+l;
100elseif(c[i+lcp[i][sa[x]]]>c[sa[x]+lcp[i][sa[x]]]) sk[i]=i+lcp[i][sa[x]];
101else sk[i]=q+n;
102103if(sk[i]>q+n) sk[i]=q+n;
104 }
105106for(int i=q;i<=q+n-1;i++) nr[i]=0;
107for(int i=q+n-1;i>=q;i--)
108 {
109if(sk[i]>0&&sk[i]!=q+n)
110 {
111if(sk[sk[i]]==0&&nr[sk[i]]==0) sk[i]=0,h--;
112elseif(sk[sk[i]]==0) sk[i]=nr[sk[i]];
113 }
114if(sk[i]>0)
115 {
116for(int j=i+1;j<=q+n-1;j++)
117 {
118if(sk[j]>0) break;
119 nr[j]=i;
120 }
121 }
122 }
123124125if(h<k||sk[q]==0) continue;
126127int now=q;h=0;
128while(now<q+n)
129 {
130 now=sk[now];
131 h++;
132 }
133if(h<=k) return1;
134 }
135return0;
136}
137138int fffind(int x)
139{
140int l,r;bool ok=0;
141 l=1;
142 r=mymin(n,cl-sa[x]+1);
143while(l<r)
144 {
145int mid=(l+r)>>1;
146if(check(x,mid)) r=mid,ok=1;
147else l=mid+1;
148 }
149if(check(x,l)) ok=1;
150if(!ok) return -1;
151return l;
152}
153154int eg[Maxn];
155156void ffind()
157{
158int l,r,h=0;
159for(int i=1;i<=cl;i++) if(sa[i]<=n) eg[++h]=i;
160 l=1;r=h;
161while(l<r)
162 {
163int mid=(l+r)>>1;
164if(fffind(eg[mid])!=-1) r=mid;
165else l=mid+1;
166 }
167int x=fffind(eg[l]);
168for(int i=sa[eg[l]];i<=sa[eg[l]]+x-1;i++) printf("%c",c[i]-1+‘A‘);
169 printf("\n");
170}
171172int main()
173{
174int T;
175 scanf("%d",&T);
176while(T--)
177 {
178 scanf("%d%d",&n,&k);
179 init();
180 get_sa(200);
181 get_he();
182 get_lcp();
183 ffind();
184 }
185return0;
186 }
原文：http://www.cnblogs.com/Konjakmoyu/p/5810227.html
内容总结
以上是互联网集市为您收集整理的【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...）全部内容，希望文章能够帮你解决【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。