【HDU 4898】 The Revenge of the Princess’ Knight （后缀数组+二分+贪心+...）

The Revenge of the Princess’ Knight

Problem Description

There 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?

Input

The 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.

Output

For each case, output the maximum part in one line.

Sample Input

1

20 3

bbbaaaaabbabaabbbbaa

Sample Output

aaabbabaabbbbaabbb

Author

WJMZBMR

【题意】

　　字符串环，割成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("
");
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 }

[HDU4898]

2016-08-26 14:30:59