B.Circle of digits Input
给出一串数环(只包含数字‘1’~‘9’),把数环分成k部分,每个部分可以表达一个十进制数。令某种分割方法中,最大的数为该方法的特征值,求这个数环所能得到的最小特征值。
TLE,数据范围达到10^5。
令特征值最后可能得长度为len,那么len = (n + k - 1) % k;
能想的的做法是,扩展数环为两倍的数串,做一遍后缀数组,这样可以得到每个后缀的排名。利用height数组,得到每个位置往后扩展len长度之后的排名。之后令每个位置为最大值,贪心扫一遍(尽量使分块长度为len,否则为len-1,并检查剩下部分是否合法)。
但是还是会t。
据说做法是:
"先处理所有串,i 可能 的下一个串的起始位置i+len 和 i+len-1,i作为父亲,后面小于i的串两个做为儿子然后构造一个森林,然后用LCT维护,然后可以用枚举答案,答案做根,末串只有两种,access判断这两种末串根到根的节点总数是不是k,这样可以在O(logn)的时间内判断一个答案是否可行,n次O(nlogn),然后建树是也是(nlogn)。"
---- [hut]-Keam
不会。
暂且贴个t的。。
#include <algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> using namespace std; #define MAXN 200010 #define INF 123456789 int sa[MAXN], sb[MAXN], r[MAXN]; int wa[MAXN], wb[MAXN], wc[MAXN], wd[MAXN]; int cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a + l] == r[b + l]; } void da(int *r, int *sa, int n, int m) { int *x = wa, *y = wb; for(int i = 0; i < m; i++) wd[i] = 0; for(int i = 0; i < n; i++) wd[x[i] = r[i]]++; for(int i = 1; i < m; i++) wd[i] += wd[i - 1]; for(int i = n - 1; i >= 0; i--) sa[--wd[x[i]]] = i; for(int j = 1, p = 0; p < n; j *= 2, m = p) { p = 0; for(int i = n - j; i < n; i++) y[p++] = i; for(int i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j; for(int i = 0; i < n; i++) wc[i] = x[y[i]]; for(int i = 0; i < m; i++) wd[i] = 0; for(int i = 0; i < n; i++) wd[wc[i]]++; for(int i = 1; i < m; i++) wd[i] += wd[i - 1]; for(int i = n - 1; i >= 0; i--) sa[--wd[wc[i]]] = y[i]; swap(x, y), p = 1, x[sa[0]] = 0; for(int i = 1; i < n; i++) x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; } return ; } int rank[MAXN], height[MAXN]; void calheight(int n) { for(int i = 1; i <= n; i++) rank[sa[i]] = i; for(int i = 0, k = 0, j; i < n; i++) { if(k) k--; j = sa[rank[i] - 1]; while(r[i + k] == r[j + k]) k++; height[rank[i]] = k; } } bool flag; int n, k, h; int id[MAXN], rk[MAXN]; inline bool cmp(int a, int b) { return rk[a] >= rk[b]; } bool cmp(int a[], int b[]) { for(int i = 0; i < h; i++) { if(a[i] > b[i]) return true; if(a[i] < b[i]) return false; } return true; } bool ok1(int p) { for(int i = h; i <= n - h; i += h) if(!cmp(p, i + p)) return false; return true; } bool ok2(int p) { int re = n % k - 1; for(int i = h; re && (i <= n - h); i += h) { if(cmp(p, i + p)) re--; else i--; } if(re) return false; return true; } bool ok(int p) { if(flag) return ok2(p); else return ok1(p); } char str[MAXN]; int main() { // freopen("B.in", "r", stdin); while(~scanf("%d%d%s", &n, &k, str)) { for(int i = 0; i < n; i++) r[i] = str[i] - '0'; for(int i = 0; i < n; i++) r[i + n] = r[i]; h = n / k + (n % k ? 1 : 0); flag = n % k ? true : false; int len = n + h; int tmp = r[len]; r[len] = 0; len++; da(r, sa, len, 12); calheight(len - 1); len--; r[len] = tmp; int cnt = 0; for(int i = 1; i <= len; i++) if(sa[i] <= len - h && height[i] < h) id[cnt++] = sa[i]; len = 2 * n; r[len] = 0; len++; da(r, sa, len, 12); calheight(len - 1); len--; int x = 0; for(int i = 1; i <= len; i++) { if(sa[i] <= len - h) { if(height[i] >= h) rk[sa[i]] = x; else rk[sa[i]] = ++x; } else rk[sa[i]] = INF; } int ans = id[cnt - 1]; for(int i = 0; i < cnt; i++) { //for(int j = 0; j < h; j++) printf("%d", r[j + id[i]]); cout << ' ' << rk[id[i]]; puts(""); if(ok(id[i])) { ans = id[i]; break; } } for(int j = 0; j < h; j++) printf("%d", r[j + ans]); puts(""); } return 0; }