Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：把一个长度为 n 的只由数字构成的串分成 k 个不为空的子串，使得最大的串最小（大小是指串所对应的十进制数的大小）。
思路：由于长度为 x 的串肯定大于长度为 x-1 的串，因此很容易想到，我们要尽可能使得 k 组串的长度平均（避免出现某一个串的长度非常大的情况）。
我们可以知道，最大值的串的长度一定为 LEN=(n+k-1)/k。
而每一组的长度，只可能是 LEN 或者 LEN-1。
然后 build_sa。
注意循环串的几个地方记得 %n。
接下来二分 sa 数组的下标。
二分 check 的时候，先枚举断点，断环为链。
由于每部分最长的长度为 LEN，所以 0..LEN-1 中一定存在一个断点。
然后贪心，尽可能取 LEN。
根据 rk 值来决定某一段的长度是 LEN 还是 LEN-1（如果 rk 值比当前的大，那么就只能取 LEN-1，否则取 LEN）。
如果此时 k 段的长度之和超过了 n，说明此时的最大值还可能更小。
于是继续二分区间的前一半。
代码实现
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
21using namespace std;
22const double eps = 1E-8;
23const int dx4[4]={1,0,0,-1};
24const int dy4[4]={0,-1,1,0};
25const int inf = 0x3f3f3f3f;
26const int N=1E5+7;
27char s[N];
28int sa[N],t[N],t2[N],c[N];
29int rk[N],height[N];
30int L;
31int n,k;
32int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[(a+l)%n]==r[(b+l)%n];}
33void build_sa(int n,int m)
34{
35 int *x = t;
36 int *y = t2;
37 //ms(cnt,0);
38 ms(c,0);
39 for ( int i = 0 ; i < n ; i++) c[x[i]=s[i]]++;
40 for ( int i = 1 ; i < m ; i++) c[i]+=c[i-1];
41 for ( int i = n-1 ; i >= 0 ; i--) sa[--c[x[i]]] = i;
42 for ( int k = 1 ; k <= n ; k <<=1)
43 {
44 int p = 0;
45 for ( int i = 0 ; i < n ; i++) if (sa[i]>=k) y[p++] = sa[i]-k;
46 else y[p++] = n+(sa[i]-k)%n;
47 ms(c,0);
48 for ( int i = 0 ; i < n ; i++) c[x[y[i]]]++;
49 for ( int i = 0 ; i < m ; i++) c[i]+=c[i-1];
50 for ( int i = n-1 ; i >=0 ; i--) sa[--c[x[y[i]]]] = y[i];
51 swap(x,y);
52 p = 1;
53 x[sa[0]] = 0 ;
54 for ( int i = 1 ; i < n ; i++)
55 x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
56 if (p>=n) break;
57 m = p;
58 }
59}
60void getHeight(int n)
61{
62 int k = 0;
63 for ( int i = 0 ; i < n ; i++) rk[sa[i]] = i ;
64 height[0] = 0 ;
65 for ( int i = 0 ; i < n ; i++)
66 {
67 if (rk[i]==0) continue;
68 if (k) k--;
69 int j = sa[rk[i]-1];
70 while (s[i+k]==s[j+k]) k++;
71 height[rk[i]] = k;
72 }
73 }
74 int getSuffix(char s[])
75 {
76 int len = strlen(s);
77 int up = 0;
78 for ( int i = 0 ; i < len ; i++)
79 {
80 int val = s[i];
81 up = max(up,val);
82 }
83 build_sa(len,up+1);
84 getHeight(len);
85 return len;
86 }
87bool check( int p)
88{
89 cout<<"p:"<<p<<endl;
90 p = sa[p];
91 for ( int i = 0 ; i < L ; i++)
92 {
93 int st = i ;
94 int ed = st+n-1;
95 for ( int j = 0 ; j < k ; j++)
96 {
97 int tmp = st%n;
98 if (rk[tmp]>rk[p])
99 st+=L-1;
100 else st+=L;
101// cout<<"tmp:"<<tmp<<" rk[tmp]:"<<rk[tmp]<<" st:"<<st<<endl;
102 if (st>ed) return true;
103 }
104 }
105 return false;
106}
107void bin()
108{
109 int l = 0 ;
110 int r = n-1;
111 while (l<r)
112 {
113 int mid = (l+r)/2;
114 if (check(mid)) r= mid;
115 else l = mid+1;
116 }
117 int ans = sa[l];
118 // cout<<"L:"<<L<<endl;
119 for ( int i = 0 ; i < L ; i++)
120 {
121 int v = (ans+i)%n;
122 printf("%c",s[v]);
123 }
124 printf("\n");
125}
126int main()
127{
128 freopen("code/in.txt","r",stdin);
129 while (scanf("%d%d",&n,&k)!=EOF)
130 {
131 L = (n+k-1)/k;
132 // cout<<"L:"<<L<<endl;
133 scanf("%s",s);
134 getSuffix(s);
135 bin();
136 // for ( int i = 0 ; i < n ; i++) cout<<"sa[i]:"<<sa[i]<<" rk[i]:"<<rk[i]<<endl;
137 }
138return 0;
139}