题目描述
给定一个长度为 的环状字符串。
将这个字符串划分成 段,每段长度为
,这个划分的代价为字典序最大的划分子段。
求所有划分方案下,字典序最小的划分代价。
题目太难描述了自己看题吧。
正解
环状字符串按照套路先倍长,然后枚举起始位置就能枚举到所有的划分了。
现在问题就是如何快速求出一个划分的代价。
考虑后缀排序,求出每一个后缀的排名。
然后一个划分的代价其实就是区间(并不连续,类似于区间 )的排名取 max。
这个可以用线段树或者单调队列做,时间复杂度 /
。
总复杂度 。
吐槽
这题后缀排序怎么卡二分 + 哈希啊,让我这种不会 SA 的人怎么活啊。(我的 SA 是直接蒯 Luogu 题解的
upd : 好像后面重测我的二分 + 哈希又活过来了。
#include <bits/stdc++.h> #define N 1000005 using namespace std; int n, m, k, rlim; int mac[N]; int S, rak[N], sa[N], tax[N], tp[N]; char s[N]; void Qsort() { for (int i = 0; i <= S; i++) tax[i] = 0; for (int i = 1; i <= n; i++) tax[rak[i]]++; for (int i = 1; i <= S; i++) tax[i] += tax[i - 1]; for (int i = n; i >= 1; i--) sa[ tax[rak[tp[i]]]-- ] = tp[i]; } void SuffixSort() { S = 75; for (int i = 1; i <= n; i++) rak[i] = s[i] - '0' + 1, tp[i] = i; Qsort(); for (int w = 1, p = 0; p < n; S = p, w <<= 1) { p = 0; for (int i = 1; i <= w; i++) tp[++p] = n - w + i; for (int i = 1; i <= n; i++) if (sa[i] > w) tp[++p] = sa[i] - w; Qsort(); swap(tp, rak); rak[sa[1]] = p = 1; for (int i = 2; i <= n; i++) rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p; } } int que[N]; int main() { scanf("%d %d %s", &n, &m, s + 1), k = n / m; for(int i = 1; i <= n; ++i) s[i + n] = s[i]; n <<= 1, rlim = n - m + 1; SuffixSort(); n >>= 1; for(int i = 1; i <= m; ++i) { int hd = 1, tl = 0; for(int j = i; j <= rlim; j += m) { while(hd <= tl && j - que[hd] >= n) ++hd; while(hd <= tl && rak[j] > rak[que[tl]]) --tl; que[++tl] = j; if(j - m * (k - 1) > 0) mac[j - m * (k - 1)] = rak[que[hd]]; } } mac[0] = N; int mpos = 0; for(int i = 1; i <= n; ++i) if(mac[i] < mac[mpos]) mpos = i; int str = sa[mac[mpos]]; for(int i = 0; i < m; ++i) putchar(s[str + i]); putchar('\n'); return 0; }