Median Replace

xht · 2023-09-27 01:47:05 · 题解

Median Replace

题意

• 给定一个长度为 n 的 0/1 串 s，保证 n 为奇数，其中有些位置上的字符不确定。
• 请你求出有多少个 s 满足执行下列操作 \frac {n-1}2 次后能使 s 为 1：
  • 选择 s 的三个连续的字符，将它们替换为这三个数的中位数。

题解

考虑如何判断一个 0/1 串是否合法。

维护一个栈，这个栈从栈底到栈顶由一段连续的 1 和一段连续的 0 组成。

对于一个新加字符 c：

• 若 c=0：由于三个 0 抵消为一个 0 严格不劣，因此若原来栈顶有两个 0 则抵消为一个，否则加一个 0。
• 若 c=1：如果栈顶是 0，可以直接将这个 0 与新加的 1 抵消（因为无论和另外哪个数取中位数，答案都是另外那个数）；如果栈顶为 1，若已经有两个 1 了，那么这个串一定合法，因此直接忽略掉这个 1 就可以了，否则加一个 1。

根据这个过程可以知道栈 0/1 的个数只有 0 \sim 2 这三种，总共只有 9 种情况。

考虑根据这个判定方法进行 DP，时间复杂度 \mathcal O(n)。

代码

const int N = 3e5 + 7;
int n;
char s[N];
modint f[N][3][3], ans;

int main() {
    rds(s, n), f[0][0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                if (!!f[i][j][k]) {
                    if (s[i+1] != '0') {
                        if (k) f[i+1][j][k-1] += f[i][j][k];
                        else f[i+1][min(j+1,2)][k] += f[i][j][k];
                    }
                    if (s[i+1] != '1') {
                        if (k == 2) f[i+1][j][1] += f[i][j][k];
                        else f[i+1][j][k+1] += f[i][j][k];
                    }
                }
    for (int i = 0; i < 3; i++)
        for (int j = 0; j <= i; j++)
            ans += f[n][i][j];
    print(ans);
    return 0;
}