题解 AT3950 【[AGC022E] Median Replace】
starseven
2020-06-12 21:02:13
[AtCoder](https://atcoder.jp/contests/agc022/tasks/agc022_e)
[luogu](https://www.luogu.com.cn/problem/AT3950)
[我的博文](https://www.cnblogs.com/starseven/p/13110345.html)
-----------------------------------------------
# 题意
给你一行字符串，里面有$1,0,?$,？表示既可以填$1$,又可以填$0$,而对于连续的三个数，可以合并，合并的结果是他们的中位数，求有多少个合法的序列满足合并的最后结果可能为1.
# 输入
$$ 101010?11?101??010101\dots 101???01$$
$$ 反正就是一行字符串 $$
# 分析
我拿到这题时没有办法，所以纯粹是听了老师讲了之后才懂的。老师说这类题（相邻的数合并）大多数都是用的一个栈模型来解决，为什么可以用栈模型，因为可以**贪心**。
### 注意：我们这里的栈是0一边，1一边
所以我们可以看这三个例子：
1. $\dots 000 \dots $
对于这连续的三个零，我们应不应该合并，因为我们要求的最后是一，而在这里是三个零互相抵消，然后变为一个零，我们肯定是稳赚不赔的！
2. $\dots 01\dots $
这里我们可以看到，我们之后的数加入为1，那合并就为1，反之亦然。所以这个可以直接在栈中“抵消”
3. $1111\dots$(这是在栈中)
我们通过前两个规则都可以知道，栈中的0最多有两个，那两个0用几个1就可以使中位数为一了呢，当然是三个就可以了，所以这个时候放入一也可以直接抵消
------
# 代码
通过我们前三个规则就可以打出代码了：
```cpp
#include<cstdio>
#include<iostream>
#define re register int
#define Starseven main
#define ll long long
using namespace std;
const int N=3e5+20;
const ll mod=1e9+7;
int num[N],len;
ll dp[N][4][4];
int Starseven(void){
while(1){
len++;
char ch=getchar();
if(ch=='\n') break;
while(ch!='0'&&ch!='1'&&ch!='?'){
ch=getchar();
}
if(ch=='1') num[len]=1;
else if(ch=='0') num[len]=2;
else num[len]==0;
}
len--;
dp[0][0][0]=1;
for(re i=1;i<=len;i++){
if(num[i]){
if(num[i]==1){
dp[i][1][0]=(dp[i][1][0]+dp[i-1][0][0]+dp[i-1][1][1])%mod;
dp[i][2][0]=(dp[i][2][0]+dp[i-1][1][0]+dp[i-1][2][1])%mod;
dp[i][3][0]=(dp[i][3][0]+dp[i-1][2][0]+dp[i-1][3][1]+dp[i-1][3][0])%mod;
dp[i][0][0]=(dp[i][0][0]+dp[i-1][0][1])%mod;
for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][2])%mod;
}
else{
for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0]+dp[i-1][j][2])%mod;
for(re j=0;j<=3;j++) dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][1])%mod;
}
}
else{
dp[i][1][0]=(dp[i][1][0]+dp[i-1][0][0]+dp[i-1][1][1])%mod;
dp[i][2][0]=(dp[i][2][0]+dp[i-1][1][0]+dp[i-1][2][1])%mod;
dp[i][3][0]=(dp[i][3][0]+dp[i-1][2][0]+dp[i-1][3][1]+dp[i-1][3][0])%mod;
dp[i][0][0]=(dp[i][0][0]+dp[i-1][0][1])%mod;
for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][2])%mod;
for(re j=0;j<=3;j++) dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0]+dp[i-1][j][2])%mod;
for(re j=0;j<=3;j++) dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][1])%mod;
}
}
ll ans=0;
for(re i=0;i<=3;i++) ans=(ans+dp[len][i][0])%mod;
ans=(ans+dp[len][2][1]+dp[len][3][1]+dp[len][3][2])%mod;
cout<<ans<<endl;
return 0;
}
```