AGC022E Median Replace
给出一个长度为奇数 $n$ 的残缺 $01$ 串，问有多少种补全方法，每次将连续三个位替换为它们的中位数后，能有一种方案使它变为 $1$。
$n\leq 3\times 10^5$
解题思路：
考虑如何判断合法，题目操作本质是 $000$ 变为 $0$，$111$ 变为 $1$，删去 $10,01$
维护一个栈，从左往右加入每一个字符，如果栈顶为 $0$ 那么就将 $0$ 留下，直到有连续 3 个 0 的时候删掉两个。
若新加入了 1，删去栈顶的 0 和新加入的 1。如果栈顶为 1 ，那么不管加入什么都留下。通过这个可以得出新的 $j’,k’$
栈里必定是若干 $1$ 接上若干 $0$，当 $1$ 个 $1$ 的段数大于等于 $2$ 个 $0$ 的段数或者最后只有 1 的时候，串就是美丽的。
定义 $f_{i,j,k}$ 表示考虑前 $i$ 位，当前有 $j$ 个 $1$ 和 $k$ 个 $0$ 的方案数，枚举❓是 $0/1$ 转移。
那么转移需要分类讨论一下了：
若加入的是 $1$
- 若栈里已经有至少 $1$ 个 $0$，直接抵消，$f_{i-1,j,k} \to f_{i,j,k-1}$ （$01$ 无用）
- 否则，若栈里有 $2$ 个 $1$，加入后无影响不改变 $f_{i-1,2,k} \to f_{i,2,k}$
- 否则，栈里 $1$ 个数 $+1$ $f_{i-1,j,k} \to f_{i,j+1,k}$
若加入的是 $0$
- 若栈里已有 $2$ 个 $0$ 消成 $1$ 个，$f_{i-1,j,2} \to f_{i,j,1}$
- 否则栈里 $0$ 个数 $+1$ $f_{i-1,j,k} \to f_{i,j,k+1}$
若加入的是 $?$
分别当成 $0/1$ 转移即可。
不难发现我们的 $j,k \leq 2$ 代码并不难写。
时间复杂度 $O(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
| char s[N];
int f[N][3][3],n,ans;
signed main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif
f[0][0][0] = 1;
scanf("%s",s+1);
n = strlen(s+1);
for (int i = 1;i <= n;++i) {
for (int j = 0;j <= 2;++j) {
for (int k = 0;k <= 2;++k) {
if (s[i] == '0') {
if (k < 2) f[i][j][k+1] = (f[i][j][k+1] + f[i-1][j][k]) % mod;
else f[i][j][1] = (f[i][j][1] + f[i-1][j][k]) % mod;
}
if (s[i] == '1') {
if (k) {
f[i][j][k-1] = (f[i][j][k-1] + f[i-1][j][k]) % mod;
} else {
if (j < 2) f[i][j+1][k] = (f[i][j+1][k] + f[i-1][j][k]) % mod;
else f[i][2][k] = (f[i][2][k] + f[i-1][j][k]) % mod;
}
}
if (s[i] == '?') {
if (k < 2) f[i][j][k+1] = (f[i][j][k+1] + f[i-1][j][k]) % mod;
else f[i][j][1] = (f[i][j][1] + f[i-1][j][k]) % mod;
if (k) {
f[i][j][k-1] = (f[i][j][k-1] + f[i-1][j][k]) % mod;
} else {
if (j < 2) f[i][j+1][k] = (f[i][j+1][k] + f[i-1][j][k]) % mod;
else f[i][2][k] = (f[i][2][k] + f[i-1][j][k]) % mod;
}
}
}
}
}
for (int i = 0;i <= 2;++i) {
for (int j = 0;j <= i;++j) {
ans = (ans + f[n][i][j]) % mod;
}
}
printf("%lld\n",ans);
#ifndef ONLINE_JUDGE
fclose(stdin);fclose(stdout);
#endif
return 0;
}
|