[AGC022E] Median Replace 题解

题意：

有个长度为 $N$（$N$ 为奇数）的 $\texttt{01}$ 串 $s$，其中有若干位置是 $\texttt{?}$。

一次操作可将 $3$ 个连续的字符替换成这三个数的中位数。

求有多少将 $\texttt ?$ 替换成 $\texttt0$ 或 $\texttt1$ 的方案使得进行 $\frac{N-1}{2}$ 次操作后的字符串可以是 $\texttt1$。

输入格式：

一行，给定 $s$ 。

输出格式：

一行，答案

数据范围：

$1\leq N\leq300000$ 且 $N$ 为奇数。

做多替换三个的题了，还以为是把每个位置都换成中位数……（~~我就说大早上写题会弱智吧~~）

容易发现，如果一个字符串由 $a$ 个连续的 $\mathtt{1}$ 和 $b$ 个连续的 $\mathtt{0}$ 拼接而成，则当 $a > b$ 时一定合法。

考虑维护一个从栈顶到栈底由一段连续的 $\mathtt{0}$ 和一段连续的 $\mathtt{1}$ 组成的栈，然后依次加入每个 $s_i$ ，则

若 $s_i = \mathtt{0}$ ，
- 若栈顶为 $\mathtt 0$ ，当栈顶有 $2$ 个 $\mathtt 0$ 时可以替换成一个 $\mathtt 0$ ，否则入栈。
- 若栈顶为 $\mathtt 1$ ，直接入栈。
若 $s_i = \mathtt{1}$ ，
- 若栈顶为 $\mathtt 0$ ，新加入的 $\mathtt 1$ 可以和栈顶的 $\mathtt 0$ 抵消。
- 若栈顶为 $\mathtt 1$ ，仅在 $\mathtt 1$ 只有一个时加入。

那么这个栈就用很小的状态数就维护了一个串是否合法。

于是可以考虑 dp 了。设 $f(i,a,b)$ 为考虑到第 $i$ 位，栈内有 $a$ 个 $\mathtt 1$ 和 $b$ 个 $\mathtt 0$ 的方案数，考虑转移：

若 $s_{i+1}=\mathtt 0$ ，则
$\begin{aligned} &f(i + 1,\,a,\,1) \uparrow f(i,\,a,\,2) + f(i,\,a,\,0) \\[6pt] &f(i + 1,\,a,\,2) \uparrow f(i,\,a,\,1) \end{aligned}$
若 $s_{i+1} = \mathtt 1$ ，则
$\begin{aligned} &f(i + 1,\,a,\,b-1) \uparrow f(i,\,a,\,b) &(b\ne 0) \\[8pt] & \begin{cases} f(i + 1,\,1,\,0)\uparrow f(i,\,0,\,0) \\[6pt] f(i + 1,\,2,\,0)\uparrow f(i,\,1,\,0) \\[6pt] f(i + 1,\,2,\,0)\uparrow f(i,\,2,\,0) \end{cases} & (b = 0) \end{aligned}$
若 $s_{i + 1} = \mathtt{?}$ ，则把上面两种转移都做一遍即可。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(3e5 + 15))

char s[N];
int n, f[N][3][3];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); n = strlen(s + 1); f[0][0][0] = 1;
    for(int i = 0; i < n; i++)
    {
        if(s[i + 1] != '1') {
            for(int a = 0; a <= 2; a++)
            {
                add(f[i + 1][a][1], f[i][a][2]);
                add(f[i + 1][a][2], f[i][a][1]);
                add(f[i + 1][a][1], f[i][a][0]);
            }
        }
        if(s[i + 1] != '0') {
            for(int a = 0; a <= 2; a++)
            {
                add(f[i + 1][a][0], f[i][a][1]);
                add(f[i + 1][a][1], f[i][a][2]);
            }
            add(f[i + 1][1][0], f[i][0][0]);
            add(f[i + 1][2][0], f[i][1][0]);
            add(f[i + 1][2][0], f[i][2][0]);
        }
    }
    int res = 0;
    for(int a = 0; a <= 2; a++)
        for(int b = 0; b <= a; b++) add(res, f[n][a][b]);
    cout << res << '\n';
    return 0;
}