CodeForces CF356E – Xenia and String Problem
这是一种不需要任何数据结构和处理字符串的工具，但细节繁多的做法。
设全串为 $s_{1\dots n}$。不难发现，Gray string 的串长必然是 $2^w-1\quad (w\geq 1)$ 的形式。若其长为 $2^w-1$，我们称其为 $w-1$ 阶 Gray string。
同时用归纳法可以证明，设一个 $w$ 阶 Gray string 的起始位置为 $x+1$（其终到位置为 $x+2^{w+1}$），那么必然有
$$
\forall k\in\{0,1,\cdots,w\},s_{x+2^k}=s_{x+2^k+2^{k+1}}=s_{x+2^k+2\times 2^{k+1}}=\cdots=s_{x+2^k+(2^{w-k}-1)2^{k+1}}\\
\forall i,j,0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j}
$$
成立。例如一个 $3$ 阶 Gray string 可以被描述为 $\mathtt{abacabadabacaba}$。
考虑在不更改字符的情况下，计算所有位置 $x\quad (0\leq x<n)$ 有多少 $w$ 满足 $s_{x+1\dots x+2^{w+1}}$ 是 Gray string。我们记 $g(y,w)$ 为最大的 $k$，满足 $s_y=s_{y+2^{w+1}}=s_{y+2\times 2^{w+1}}=\cdots=s_{y+(k-1)2^{w+1}}$，也即间隔为 $2^{w+1}$ 的极长邻项字符相等的链。这可以暴力 $\newcommand\bigO{\operatorname{O}}\bigO(n\log n)$ 求出。那么位置 $x$ 能够贡献一个 $w$ 阶 Gray string，当且仅当
$$
\forall 0\leq i\leq w,w\leq i+\lfloor\log_2 g(x+2^i,i)\rfloor\\
\forall 0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j}
$$
这依然可以 $\bigO(n\log n)$ 求出——我们从小到大遍历 $w$ 并更新上文式子的最小值，直到 $w$ 超过这个最小值或者出现重复字符。固定位置 $x$，记 $w_0$ 是满足上式的最大 $w$。
现在思考当某个位置的字符被替换后，$x$ 的贡献有何变化。我们分两个部分考虑：删除和新增。记在全串范围内，将 $s_u$ 变为字符 $c$ 会新增 $h(u,c)$ 的权值和。
被删除的串
易得对于所有 $u\quad (x<u<x+2^{w+1})$，$s_u$ 的改变将直接破坏 Gray string $s_{x+1\dots x+2^{w+1}-1}$；特别地，若 $u=x+2^w$（该 Gray string 的中央字符），且有 $\forall 0\leq i<w, {s_u}’\neq s_{x+2^i}$（不与更低阶的字符重复），则这个 $w$ 阶 Gray string 不会被破坏。
于是我们设立差分数组 $d(x)\quad(1\leq x\leq n)$，维护破坏造成的负权值。记 $b_w=(2^{w+1}-1)^2$。令
$$\begin{aligned}
{d(x+1)}’&\leftarrow d(x+1)-b_w\\
{d(x+2^{w+1})}’&\leftarrow d(x+2^{w+1})+b_w\\
{d(x+2^w)}’&\leftarrow d(x+2^w)+b_w\\
{d(x+2^w+1)}’&\leftarrow d(x+2^w+1)-b_w&\text{（中央字符可以改变）}\\
\forall i,0\leq i<w,{h(x+2^w,s_{x+2^i})}’&\leftarrow h(x+2^w,s_{x+2^i})-(2^{w+1}-1)^2&（但不能改为重复字符）
\end{aligned}$$
新增的串
我们称位置 $x$ 的扩展被阻拦，当且仅当有 $\forall 0\leq w\leq w_0,w_0<w+\lfloor\log_2 g(x+2^w,w)\rfloor$。这也就意味着 $w_o+1$ 阶位置出现了重复字符；反之，未被阻拦是说 $w_0$ 恰等于了限制式的上界。按照这个定义，同时出现 $w_0$ 卡到上界和 $w_0+1$ 阶位置有重复字符的话，会被归为“未阻拦”。
未被阻拦
我们令 $j$ 是所有 $w\quad (0\leq w\leq w_0)$ 中取到 $w_0=w+\lfloor\log_2 g(x+2^w,w)\rfloor$ 的值，也即上界的来源。若 $j$ 不唯一，由于替换单个字符最多更改一个 $g(x+2^w,w)$，故而 $w_0$ 不会改变，不可能在 $x$ 处有新的贡献。
若 $j$ 唯一，有两种可能使得 $g(x+2^j,j)$ 变大。记应用 ${g(x+2^j,j)}’$ 得到的新上界为 ${w_0}’$。
- $u=x+2^j+2^{j+1}g(x+2^j,j)$ 且 ${s_u}’=s_{x+2^j}$，也即 $u$ 为 $j$ 阶链尾的下一个位置。将 $s_u$ 设置为 $s_{x+2^j}$，就是将它合并到 $j$ 阶极长链上——这甚至还可能导致 $u$ 两侧两条 $j$ 阶链的合并；
- $j=w_0$ 且 $u_2=u=x+2^j$ 且 $\forall 0\leq w\leq w_0, {s_u}’\neq s_{x+2^w}$。由 $j=w_0$ 可以推出 $\lfloor\log_2 g(x+2^j,j)\rfloor=0\iff g(x+2^j,j)=1$，也即这条链长为 $1$。此时将该位置本身替换成 $s_{u+2^{j+1}}$（如果其与低阶的链不重复），可能会引发两条链的合并，较原串更优。
不难说明，其他任何位置替换任何字符，都只会使得 $x$ 的贡献削减（$g(x+2^w,w)$ 不增）；而负贡献已经在上文中计算完成了。如果上文两种情况有新的贡献，则我们分别累加 $h(u,{s_u}’)’\leftarrow h(u,{s_u}’)+\sum_{w=w_0+1}^{{w_0}’} b_w$。
被阻拦
可以验证，被阻拦时只有改变 $s_{u=x+2^{w_0+1}}$，也即 $w_0+1$ 阶链的首字符，才有可能在 $x$ 处有新贡献。若有 ${s_u}’\neq s_{x+2^{w_0+1}x+2^{w_0+2}}$（试图合并两条 $w_0+1$ 阶链），可能有 ${w_0}’>w_0+1$；否则必然有 ${g(u,w_0+1)}’=1,{w_0}’=w_0+1$。只有一种情况需要重新暴力计算。及时更新 $h(u,*)$ 即可。
最后我们从前到后累加差分，利用 $h$ 更新答案即可。
按照上述方法精细实现，可以做到 $\bigO(n\log n)$，常数小。是为目前本题最优解。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
#include <bits/stdc++.h> using namespace std; #define inl __attribute__((always_inline)) inline typedef long long ll; typedef pair <int, int> pint; #define fst first #define scd second #define all(p) begin (p), end (p) #define empb emplace_back constexpr int N = 1e5 + 10; constexpr ll b[] = { 1, 9, 49, 225, 961, 3969, 16129, 65025, 261121, 1046529, 4190209, 16769025, 67092481, 268402689, 1073676289, 4294836225, 17179607041 }; constexpr ll bpre[] = { 1, 10, 59, 284, 1245, 5214, 21343, 86368, 347489, 1394018, 5584227, 22353252, 89445733, 357848422, 1431524711, 5726360936, 22905967977 }; int n, g[17][N]; char s[N]; ll ans, dt[N], ata[N][26]; inl int cnxt (int x, int i) { return x + g[i][x+(1<<i)] * (1<<i+1) + (1<<i); } inl int ced (int x, int i) { return x + g[i][x+(1<<i)] * (1<<i+1) - (1<<i); } inl int cst (int x, int i) { return x + (1<<i); } inl int imple (int x) { static bool occ[26]; int w = 0, lmt = INT_MAX, y; memset (occ, 0, 26); while (w <= lmt && !occ[s[y = cst (x, w)]-'a']) lmt = min (lmt, __lg (g[w][y]) + w), occ[s[y] - 'a'] = 1, ++w; return --w; } int main () { /* */ scanf ("%s", s + 1); n = strlen (s + 1); for (int w = 0; (1<<w) <= n; ++w) for (int st = 1; st <= 1<<w+1; ++st) { int x = st, y = st, cnt = 0; while (x <= n) { while (y <= n && s[x] == s[y]) y += 1<<w+1, ++cnt; while (x < y) g[w][x] = cnt--, x += 1<<w+1; } } for (int x = 0; x < n; ++x) { static bool occ[26]; static int bd[17], lst[17]; memset (occ, 0, 26); int w = 0, lmt = INT_MAX, y, z, c, _g, alp; while (w <= lmt && !occ[s[y = cst (x, w)]-'a']) lmt = min (lmt, bd[w] = __lg (g[w][y]) + w), occ[lst[w++] = s[y] - 'a'] = 1; ans += bpre[--w], dt[x + 1] -= bpre[w]; for (int i = 0; i <= w; ++i) { dt[x+(1<<i+1)] += b[i], dt[y = cst (x, i)] += b[i], dt[y+1] -= b[i]; for (int k = 0; k < i; ++k) ata[y][lst[k]] -= b[i]; } if (w == lmt) { // ? 无阻拦/非严格阻拦。 int j = -1; for (int i = 0; i <= w; ++i) if (bd[i] == w) j = ~j ? INT_MAX : i; if (j == INT_MAX) continue; // ? 在j阶后面补足。 if ((z = cnxt (x, j)) > n) goto KAWA; c = s[z], s[z] = s[y = cst (x, j)]; _g = g[j][y], g[j][y] += 1 + ((alp = z + (1<<j+1)) <= n && s[alp] == s[y] ? g[j][alp] : 0); ata[z][s[y]-'a'] += bpre[imple (x)] - bpre[w]; g[j][y] = _g, s[z] = c; // ? 若有j = w，则自然有j阶连通块大小为1。尝试改换它自己的颜色。 KAWA: if (j != w || (z = cnxt (x, w)) > n || occ[s[z] - 'a']) continue; c = s[y = cst (x, w)], s[y] = s[z]; _g = g[w][y], g[w][y] += g[w][z]; ata[y][s[z]-'a'] += bpre[imple (x)] - bpre[w]; g[w][y] = _g, s[y] = c; } else { // ? 严格阻拦。 // ? 添置一个没有出现过的字符。 for (c = 0, y = cst (x, w+1); c < 26; ++c) ata[y][c] += !occ[c] * b[w+1]; if (g[w+1][y] > 1 || (z = y + (1<<w+2)) > n) continue; ata[y][s[z]-'a'] -= b[w+1]; c = s[y], s[y] = s[z], g[w+1][y] += g[w+1][z]; ata[y][s[z]-'a'] += bpre[imple (x)] - bpre[w]; s[y] = c, g[w+1][y] = 1; } } for (ll ima = ans, x = 1; x <= n; ++x) ans = max (ans, (ima += dt[x]) + *max_element (all (ata[x]))); printf ("%lld", ans); return 0; }
近期评论