[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;
}