【好题分享】Median Replace

水题分享 AtCoder 提交地址

【题目描述】

给定一个奇数长度的 $01$ 串 \(S\)，其中有若干个位置是 ? 字符。

每次可以将 $3$ 个连续的字符替换成这三个数的中位数。求有多少种方案将 ? 替换成 $0/1$ 使得进行 \(\dfrac{N-1}{2}\) 次操作后的字符串是 $1$。

【样例输入#1】

1??00

【样例输出#1】

2

【样例输入#2】

?0101???10???00?1???????????????0????????????1????0

【样例输出#2】

402589311

【数据规模与约定】

• $1\leq |S| \leq 300000$；
• 保证 \(|S|\) 为奇数；
• \(S\) 只由 0、1、? 构成。

首先，我们先不考虑 ? 的情况，对于一个字符串 \(S\) ，我们可以用栈来维护这个字符串是否合法。

对于 $01$，$10$ 这样的串，新的字符加入后，操作得到的字符肯定是新加的字符。

对于 $000$ 这样的串，直接操作肯定是最优的。

所以我们考虑 $000,01,10,111$ 这四个串；

很显然，我们要先删除 $000$，然后是 $01,10$，最后是 $111$。

具体来说，这个栈从栈底到栈顶由一段连续的 $1$ 和一段连续的 $0$ 组成。

对于每个新加入栈的字符 \(c\)，我们分情况考虑：

当 \(c\) 是字符 $0$ 时，如果堆顶有两个 $0$，我们将这三个 $0$ 合并后得到一个 $0$；当堆顶是 $1$ 时，因为 $000$ 的优先级在 $01$ 之前，这个新加入的 $0$ 可能会与后面的字符组成 $000$ 的串，所以我们直接将它加入栈。

当 \(c\) 是字符 $1$ 时，如果堆顶是 $0$，我们直接将这两个字符抵消；否则，将 $1$ 入栈。

然后因为要求最后得到的字符是 $1$，所以最后栈中的 \(cnt_0\leq cnt_1\)，因为 \(cnt_0 \leq 2\)，所以，我们把 \(cnt_1>2\) 的情况存在 \(cnt_1=2\) 的情况里就可以了。

因此我们设 \(f_{i,j,k}\) 表示枚举到第 \(i\) 个字符，且当前的堆中有 \(j\) 个 $1$，\(k\) 个 $0$ 的情况。

然后直接转移就好了

最后记录答案的时候，答案也就为 \(f_{n,j,k}(j\geq k)\) 的和。

代码如下：

#include<bits/stdc++.h>
#define rint register int
using namespace std;
inline int read(){
    int s=0,f=1; char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=0;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘) s=(s<<1)+(s<<3)+(c^48),c=getchar();
    return f?s:-s;
}
const int Mod=1e9+7;
char s[300010];
int n,f[300010][3][3],ans;
int main(){
    scanf("%s",s+1); n=strlen(s+1);
    f[0][0][0]=1;
    for(rint i=0;i<n;++i)
        for(rint j=0;j<=2;++j)
            for(rint k=0;k<=2;++k){
                if(s[i+1]!=‘0‘){
                    if(k) f[i+1][j][k-1]=1ll*(f[i+1][j][k-1]+f[i][j][k])%Mod;
                    else f[i+1][min(j+1,2)][k]=1ll*(f[i+1][min(j+1,2)][k]+f[i][j][k])%Mod;
                }
                if(s[i+1]!=‘1‘){
                    if(k==2) f[i+1][j][1]=1ll*(f[i+1][j][1]+f[i][j][k])%Mod;
                    else f[i+1][j][k+1]=1ll*(f[i+1][j][k+1]+f[i][j][k])%Mod;
                }
            }
    for(rint i=0;i<=2;++i)
        for(rint j=0;j<=i;++j) ans=1ll*(ans+f[n][i][j])%Mod;
    printf("%d",ans);
    return 0;
}

【好题分享】Median Replace

原文：https://www.cnblogs.com/LCGUO/p/13540811.html