题解 AT3950 【[AGC022E] Median Replace】

· · 题解

AGC 022E

首先考虑如何判断一个数列是否合法。

考虑维护一个栈，满足从栈顶到栈底是由一段连续的0和一段连续的1组成。从左到右将每一个数加入栈中，考虑加入的数是什么

  1. 若加入的数为0：
    • 若栈顶为0，如果栈内有2个0，那么可以替换成一个0，否则入栈。
    • 若栈顶为1，直接入栈即可。
  2. 若加入的数为1：
    • 若栈顶为0，则新加入的1可以和栈顶的0抵消，因为再加入一个数，这三个数的中位数之和新加入的数有关。
    • 若栈顶为1，如果栈内只有一个1则入栈，否则忽略它。

最后只需要判断栈内1的个数是否大于等于0的个数即可。

不难发现栈中0和1的个数只有可能是0\sim 2，于是便可以dp了，设f_{i,a,b}表示看到了第i位，栈内有a个1和b个0的方案数。接下来考虑转移：

\begin{aligned} f_{i,a,2}&\to f_{i + 1,a,1}\\ f_{i,a,1}&\to f_{i + 1,a,2}\\ f_{i,a,0}&\to f_{i + 1,a,1}\\ \end{aligned}
\begin{aligned} f_{i,a,b}&\to f_{i + 1,a,b - 1}\\ f_{i,0,0}&\to f_{i + 1,1,0}\\ f_{i,1,0}&\to f_{i + 1,2,0}\\ f_{i,2,0}&\to f_{i + 1,2,0} \end{aligned}
  1. 若这一位为?，则将上面两种转都做一遍即可。

时间复杂度为\mathcal O(n)

Code

int n;
int f[MAXN][3][3];
char s[MAXN];

int main(){
    scanf("%s",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++){
                addmod(f[i + 1][a][1],f[i][a][2]);
                addmod(f[i + 1][a][2],f[i][a][1]);
                addmod(f[i + 1][a][1],f[i][a][0]);
            }
        }
        if(s[i + 1] != '0'){
            for(int a = 0;a <= 2;a++){
                addmod(f[i + 1][a][0],f[i][a][1]);
                addmod(f[i + 1][a][1],f[i][a][2]);
            }
            addmod(f[i + 1][1][0],f[i][0][0]);
            addmod(f[i + 1][2][0],f[i][1][0]);
            addmod(f[i + 1][2][0],f[i][2][0]);
        }
    }
    int ans = 0;
    for(int a = 0;a <= 2;a++){
        for(int b = 0;b <= a;b++)
            addmod(ans,f[n][a][b]);
    }
    printf("%d\n",ans);
    return 0;
}