仰望半月的夜空 题解
可以的话，支持一下原作吧...
这道题数据很弱.....
因此各种乱搞估计都是能过的....
算法一
暴力长度然后判断判断，复杂度\(O(n^3)\)
期望得分15分
算法二
通过二分+\(hash\)或者等等来优化字典序比较，复杂度\(O(n^2 \log n)\)，可能要松一下
期望得分30分
ps:好吧有55分...
算法三
我们考虑字符集非常小的情况
我们猜想出题人很难卡掉玄学做法，因此我们就想一个玄学做法
我们考虑用\(SAM\)来处理这个问题
建出\(SAM\)后，我们用\(dp\)预处理出一个点向后走最长能走多远
然后在\(SAM\)上根据字典序找到每个长度分别对应哪个集合
取对应集合的\(right\)集合中的最小值即可
复杂度是个玄学，但是能通过字符集很小和数据随机的点
期望得分55~75分
不会在字符集很小的情况下造数据，求大佬
算法四
注意到实际上复杂度很高是因为我们在一个\(DAG\)上寻找答案
实际上我们建出后缀树，然后在树上寻找对应集合即可
复杂度可以做到\(O(n \log n)\)
字符集较小的时候可以直接\(O(n)\)
期望得分100分
算法五
考虑用\(SA\)来解决这个问题
不难发现，给后缀排好序之后，按照长度维护一个单调栈
不妨设单调栈中的后缀分别为\(i_1, i_2, ..., i_p\)
那么，长度\(L(i_1) + 1 \sim L(i_2)\)对应的字典序最小的串一定是以\(i_2\)为开头的
这样，我们就可以找到这\(n\)个串
然后再用二分找到这个串在后缀数组中对应的区间，用线段树或者\(st\)表(暴力也能过)来维护\(sa\)的最小值即可
复杂度\(O(n \log n)\)
期望得分100分
几乎是个模板字符串吧.....
Q：前半段和后半段相等的串有啥用啊？
A：我也不知道，所以才放在那里的....
#include#include #include #include using namespace std;#define ll long long#define ri register int#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)#define drep(io, ed, st) for(ri io = ed; io >= st; io --)#define gc getcharinline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w;} const int sid = 500050;const int ssd = 2000050;char t[sid];int n, S, top, s[sid], T[sid];int nc[sid], p1[sid], p2[sid], ip[sid];int sa[sid], rk[sid], lg[sid], bit[sid], st[sid][20];void init() { rep(i, 0, 25) bit[i] = 1 << i; rep(i, 2, 400000) lg[i] = lg[i >> 1] + 1;}void rsort(int n, int m) { rep(i, 1, n) nc[p2[i]] ++; rep(i, 1, m) nc[i] += nc[i - 1]; rep(i, 1, n) ip[nc[p2[i]] --] = i; rep(i, 0, m) nc[i] = 0; rep(i, 1, n) nc[p1[i]] ++; rep(i, 1, m) nc[i] += nc[i - 1]; drep(i, n, 1) sa[nc[p1[ip[i]]] --] = ip[i]; rep(i, 0, m) nc[i] = 0;}void ssort() { rep(i, 1, n) T[i] = s[i]; sort(T + 1, T + n + 1); int m = unique(T + 1, T + n + 1) - T - 1; rep(i, 1, n) rk[i] = lower_bound(T + 1, T + m + 1, s[i]) - T; for(ri k = 1; k <= n; k <<= 1) { rep(i, 1, n) { p1[i] = rk[i]; p2[i] = (i + k <= n) ? rk[i + k] : 0; } rsort(n, m); rk[sa[1]] = m = 1; rep(i, 2, n) { if(p1[sa[i]] == p1[sa[i - 1]] && p2[sa[i]] == p2[sa[i - 1]]) m --; rk[sa[i]] = ++ m; } if(m >= n) break; } for(ri i = 1, k = 0; i <= n; i ++) { if(k) k --; int j = sa[rk[i] - 1]; while(s[i + k] == s[j + k]) k ++; st[rk[i]][0] = k; } rep(j, 1, 19) for(ri i = 1; i + bit[j] - 1 <= n; i ++) st[i][j] = min(st[i][j - 1], st[i + bit[j - 1]][j - 1]);}inline int lcp(int l, int r) { if(l == r) return n - sa[l] + 1; if(l > r) swap(l, r); l ++; int L = lg[r - l + 1]; return min(st[l][L], st[r - bit[L] + 1][L]); }int stk[sid], mi[ssd];#define ls (o << 1)#define rs (o << 1 | 1)inline void build(int o, int l, int r) { if(l == r) { mi[o] = sa[l]; return; } int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); mi[o] = min(mi[ls], mi[rs]);}inline int qry(int o, int l, int r, int ml, int mr) { if(ml > r || mr < l) return 1e9; if(ml <= l && mr >= r) return mi[o]; int mid = (l + r) >> 1; return min(qry(ls, l, mid, ml, mr), qry(rs, mid + 1, r, ml, mr));}inline int get_pre(int l, int r, int pos, int L) { int ret = -1; while(l <= r) { int mid = (l + r) >> 1; if(lcp(mid, pos) >= L) r = mid - 1, ret = mid; else l = mid + 1; } return ret;}inline int get_suf(int l, int r, int pos, int L) { int ret = -1; while(l <= r) { int mid = (l + r) >> 1; if(lcp(mid, pos) >= L) l = mid + 1, ret = mid; else r = mid - 1; } return ret;}inline int solve(int l, int L) { int pre = get_pre(1, l, l, L); int suf = get_suf(l, n, l, L); return qry(1, 1, n, pre, suf); }inline int L(int x) { if(!x) return 0; return n - sa[x] + 1;}int main() { init(); S = read(); n = read(); if(S == 26) { scanf("%s", t + 1); rep(i, 1, n) s[i] = t[i]; } else rep(i, 1, n) s[i] = read(); s[0] = s[n + 1] = -1; ssort(); build(1, 1, n); rep(i, 1, n) if(L(i) > L(stk[top])) stk[++ top] = i; rep(i, 1, top) { int l = L(stk[i - 1]) + 1, r = L(stk[i]); rep(j, l, r) printf("%d ", solve(stk[i], j)); } printf("\n"); return 0;}