题意
有一个长度为 n 的字符串，仅由 0∼9 的数字组成。给了你 m,k，定义一种把原字符串划分成 m 段的划分方式的权值为划分后每一段表示成十进制后第 k 大的数字。求权值最小的划分方式的权值。
1≤k≤m≤n≤106。
分析
首先会注意到，当 k>1 的时候，我们一定会把一个一位数划分出来作为权值，因为这样子可以使权值尽量的小。于是我们可以从小到大枚举答案，判断是否合法。
假设我们枚举到 i，如果至少有 k−1 个数字大于 i，那么 i 一定是合法的。当然，我们也可以把多个数字接在一起，使得这个数字比 i 大。这样子我们就不好直接判。可以反向考虑找到所有比 i 小的去构造。直接拿出相邻两个比 i 大的位置中间的所有数字，排序取前 cnt−k+1 个即可。这样就是 O(n) 的。
for (int i = 0; i < 10; i++){
int cnt = 0;
for (int j = 1; j <= n; j++) if (a[j] > i) ax[++cnt] = j;
if (cnt < k) return printf ("%d\n", i), 0;
for (int j = 1; j < cnt; j++) ay[j] = ax[j + 1] - ax[j] - 1;
sort (ay + 1, ay + cnt);
int res = n - cnt;
for (int j = 0; j <= cnt - k + 1; j++) res -= ay[j];
if (res >= m - k + 1) return printf ("%d\n", i), 0;
}
然后就是 k=1 的。因为我们要让最大值最小，考虑二分。首先一个显然的就是，设 B=nm，那么划分一定就是若干个长度为 B 和若干个长度为 B+1 的。当 m|n 的时候，长度都是 B。我们可以直接 SA 取出 rk 最大的作为开头输出。
剩下的直接二分 rk。我们按照每一个块一次跳。如果当前位置的 rk 比 mid 小，我们就可以让这个块长度是 B+1，否则就是 B。当有了 nmod 个长度为 B + 1 的块的时候，我们直接输出第 n \bmod m 这个块。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 2000005
il int rd(){
int s = 0, w = 1;
char ch = getchar();
for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
return s * w;
}
int n, m, k, B, a[N], id[N], vis[N], ax[N], ay[N];
int sa[N], oldsa[N], rk[N], oldrk[N], t[N];
char s[N];
il void ms(int *a, int v, int n){for (int i = 0; i <= n + 4; i++) a[i] = v;}
il void mc(int *a, int *b, int n){for (int i = 0; i <= n + 4; i++) a[i] = b[i];}
int Main_easy(){
for (int i = 0; i < 10; i++){
int cnt = 0;
for (int j = 1; j <= n; j++) if (a[j] > i) ax[++cnt] = j;
if (cnt < k) return printf ("%d\n", i), 0;
for (int j = 1; j < cnt; j++) ay[j] = ax[j + 1] - ax[j] - 1;
sort (ay + 1, ay + cnt);
int res = n - cnt;
for (int j = 0; j <= cnt - k + 1; j++) res -= ay[j];
if (res >= m - k + 1) return printf ("%d\n", i), 0;
}
}
il void SA(){
int M = 10;
ms(t, 0, M), ms(sa, 0, n + n), ms(rk, 0, n + n);
for (int i = 1; i <= n; i++) t[rk[i] = a[i] + 1]++;
for (int i = 1; i <= M; i++) t[i] += t[i - 1];
for (int i = n; i >= 1; i--) sa[t[rk[i]]--] = i;
for (int w = 1; w < n; w <<= 1, M = n){
mc(oldsa, sa, n), ms(t, 0, M);
for (int i = 1; i <= n; i++) t[rk[oldsa[i] + w]]++;
for (int i = 1; i <= M; i++) t[i] += t[i - 1];
for (int i = n; i >= 1; i--) sa[t[rk[oldsa[i] + w]]--] = oldsa[i];
mc(oldsa, sa, n), ms(t, 0, M);
for (int i = 1; i <= n; i++) t[rk[oldsa[i]]]++;
for (int i = 1; i <= M; i++) t[i] += t[i - 1];
for (int i = n; i >= 1; i--) sa[t[rk[oldsa[i]]]--] = oldsa[i];
mc(oldrk, rk, n);
for (int p = 0, i = 1; i <= n; i++)
if (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) rk[sa[i]] = p;
else rk[sa[i]] = ++p;
}
}
il bool cmp(int a, int b){return rk[a] < rk[b];}
il bool check(int x){
for (int i = 1; i <= n; i++) vis[i] = 0;
for (int i = 1; i <= x; i++) vis[id[i]] = 1;
for (int i = 1, cnt = 0; i <= n;){
if (vis[i]) i += B + 1, cnt++;
else i += B;
if (cnt == n % m) return 1;
}
return 0;
}
int Main(int T){
n = rd(), m = rd(), k = rd(), scanf ("%s", s + 1);
for (int i = 1; i <= n; i++) a[i] = s[i] - 48;
if (k ^ 1) return Main_easy(), 0;
SA(), B = n / m;
if (n % m == 0){
for (int i = 1; i <= m; i++) id[i] = (i - 1) * B + 1;
sort (id + 1, id + m + 1, cmp);
for (int i = 1; i <= B; i++) printf ("%d", a[id[m] + i - 1]);
return puts(""), 0;
}
for (int i = 1; i <= n - B; i++) id[i] = i;
sort (id + 1, id + n - B + 1, cmp);
int l = 1, r = n - B, ans = -1;
while (l <= r){
int mid = (l + r) >> 1;
if (check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
for (int i = 1; i <= B + 1; i++) printf ("%d", a[id[ans] + i - 1]);
return puts(""), 0;
}
int main(){
int T = rd();
for (int i = 1; i <= T; i++) Main(i);
return 0;
}
