题解：CF461E Appleman and a Game
Lu_xZ
·
·
题解
补充了部分细节问题。
如果 s 确定，如何求出其最小操作数？
注意到 $g_{i} \ge g_{i - 1}$，因为任意 $i$ 的方案都能砍掉 $s_i$ 后变成 $i - 1$ 的方案。
因此 $i$ 的转移点为最小的 $j$ 满足 $(j, i]$ 是 $t$ 的子串。
有如下贪心：对于每一段，能延伸就延伸（在 $t$ 的 sam 上跑，有转移边就走，否则回到根）。
在段数相同的情况下要最小化总长度，这样才能在总长度确定时最大化段数。
设 $f(k, i, j)$ 表示已经拼了 $k$ 段，以字符 $i$ 开头且不能再往后延伸一个字符 $j$ 的最小总长度。
倍增优化：$f(2^k, i, j) \gets f(2^{k - 1}, i, x) + f(2^{k - 1}, x, j)$。
问题转化为求 $f(1, i, j)$。
其代表的子串在将来一定是接一个 $j$ 开头的段，并产生 $2$ 的贡献。
把以 $i$ 开头的字符串 $s$ 分成三类：
1. 是 $t$ 的子串且后面不能加 $j$，在后面接一个 $j$ 开头的段，恰好产生两个段。
2. 是 $t$ 的子串且后面能加 $j$，不一定能产生两个段。
3. 不是 $t$ 的子串，已经产生至少两个段了，哪怕新接的段不产生贡献，贡献仍然至少为二。
因此在相同长度下，一三比二更优。
固定长度为 $k$，第二类有 $x = O(n)$ 种，一三加起来有 $4^{k - 1} - x$。
存在一三串当且仅当 $4^{k - 1} - x > 0$，取 $k = 11$ 足矣。
对所有后缀建出树高为 $11$ 的字典树即可求出所有有用的 $f(1, i, j)$（可能存在大于 $11$，但是没用）。
统计答案：从高到低枚举 $2^k$，$h_{i, j}$ 表示 $i$ 开头，后面接不了 $j$，在当前答案下的最小长度。
由于有“不能接”这一限制，贪心的让 $h_{i, j} < n$，并在最后补一个 $j$（体现在答案上就是加 $1$）。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
int m, t[N * 15][4], idx;
char s[N];
ll n, f[61][4][4], h[4][4], g[4][4];
void dfs(int u, int v, int d, ll& x) {
if(!u) return;
if(!t[u][v]) {
x = min(x, (ll)d);
return;
}
for(int i = 0; i < 4; ++ i) {
dfs(t[u][i], v, d + 1, x);
}
}
main() {
scanf("%lld%s", &n, s);
m = strlen(s);
for(int i = 0; i < m; ++ i) s[i] -= 'A';
for(int i = 0; i < m; ++ i) {
for(int j = i, p = 0; j < m; ++ j) {
if(j - i >= 11) break;
if(!t[p][s[j]]) t[p][s[j]] = ++ idx;
p = t[p][s[j]];
}
}
memset(f, 0x3f, sizeof f);
for(int i = 0; i < 4; ++ i) {
for(int j = 0; j < 4; ++ j) {
dfs(t[0][i], j, 1, f[0][i][j]);
}
}
for(int k = 1; k <= 60; ++ k) {
for(int i = 0; i < 4; ++ i) {
for(int j = 0; j < 4; ++ j) {
for(int x = 0; x < 4; ++ x) {
f[k][i][j] = min(f[k][i][j], f[k - 1][i][x] + f[k - 1][x][j]);
}
}
}
}
ll ans = 0;
for(int k = 60; k >= 0; -- k) {
ll mi = 1e18;
for(int i = 0; i < 4; ++ i) {
for(int j = 0; j < 4; ++ j) {
h[i][j] = 1e18;
for(int x = 0; x < 4; ++ x) {
h[i][j] = min(h[i][j], g[i][x] + f[k][x][j]);
}
mi = min(mi, h[i][j]);
}
}
if(mi < n) {
ans |= 1ll << k;
swap(g, h);
}
}
printf("%lld", ans + 1);
}
```