题解：AT_agc022_e [AGC022E] Median Replace
kevinZ99
·
·
题解
Solution
首先我们要考虑在没有问号的情况下如何快速判断一个字符串是否可以。
明显的我们能发现但凡在消除过程中能在开头出现 11 的情况是必定可行的，因为我们只需要将后方的部分消除到只剩下一个数字，又因为任何数字和 11 的中位数都是 1。
其次我们考虑 00 的情况，若后方添加一个 0 则直接消除，若后方添加一个 1 我们发现，若这两个 0 要与后方的数字进行消除那么就必定要将这个 1 消除掉，所以我们贪心的直接将这三个数字合并成 0。
对于 01 的情况我们发现，操作完后的数字与这两个数字无关，直接与第三个数字相关，第三个数字是什么，合并完后的数字就是什么。
对于 10 我们发现若后方形成了 1000 的情况我们可以先消除 000 在进行之后的消除所以我们需要保留 10。
我们来总结一下现在剩下的状态。
分别有
一共有六种。
所以我们可以直接开始动态规划。
令 $f_{i,j}$ 表示填完了前 $i$ 个的问号，出现这六种情况的方案数。
特别的考虑到 $11$ 这种情况一但出现则必定可行，所以我们转移的时候需要注意一下。
# code
```cpp
//Author:Kevin Z K Y
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);(a)++)
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);(a)--)
#define fst first
#define sed second
using namespace std;
using us = unsigned short ;using ldb = long double ;
using ull = unsigned long long ;using ui = unsigned int ;
using ll = long long ;using hint = __int128 ;
using pii = pair<int,int> ;using pll = pair<ll,ll> ;
using pil = pair<int,ll> ;using vpil = vector<pil> ;
using vi = vector<int> ;using vl = vector<ll> ;
using vpi = vector<pii> ;using vpl = vector<pll> ;
using db = double ;namespace mystl{
#define gc() getchar()
#define Max(x,y) (((x)>(y))?(x):(y))
#define Min(x,y) (((x)<(y))?(x):(y))
#define Abs(x) (((x)<0)?(-(x)):(x))
#define putline() cout<<"------------------------------\n"
ll qpow(ll a , ll b , ll p) { if (a==0ll) return 0ll; ll c=1ll;
while(b) { if(b & 1) c=a*c%p; a=a*a%p; b>>=1; } return c; }
void exgcd(ll a,ll b,ll &cx,ll &cy){if(a % b ==0)cx = 0,cy = 1;
else { exgcd( b , a % b , cy , cx) ; cy -= a / b * cx ; } }
ll lcm ( ll x , ll y ){return x / std :: __gcd( x , y ) * y ; }
template<typename T>void read(T&x) {x=0; bool f=false; char ch;
ch = gc(); while(ch<'0'||ch>'9') f |= ( ch=='-') , ch=gc();
while(ch>='0'&&ch<='9') x=x*10+ch-'0' , ch=gc(); x=f?-x:x;}
template<typename T>void write(T x){char s[40];short d=0;T y=x;
if(x<0) putchar('-'),y=-y;if(x==0){ putchar('0'); return; }
while(y){s[++d]=y%10+'0';y/=10;}while(d>0)putchar(s[d--]);}
template<typename T>void wris(T x,char c){write(x);putchar(c);}
}using namespace mystl;
const db eps=1e-6,PI=acos(-1);
namespace my{
const int N=(int)(300005);
const ll inf=(ll)(1e9);
const ll p=inf+7;
ll f[N][7];
ll add(ll x,ll y){
return (x%p+y%p)%p;
// return (x+y>=p)?(x+y-p):(x+y);
}
char s[N];int n;
void solve(){
cin>>(s+1);n=strlen(s+1);
if(n==1){
cout<<(s[1]=='1'||s[1]=='?')<<'\n';
return ;
}
// reverse(s+1,s+1+n);
/*
0:{0}
1:{0 0}
2:{1}
3:{1 0}
4:{1 0 0}
5:{}
6:{1 1}
*/
if(s[1]=='0'||s[1]=='?')f[1][0]=1;
if(s[1]=='1'||s[1]=='?')f[1][2]=1;
up(i,2,n){
if(s[i]=='0'||s[i]=='?'){
f[i][0]=add(f[i][0],add(f[i-1][1],f[i-1][5]));
f[i][1]=add(f[i][1],f[i-1][0]);
f[i][3]=add(f[i][3],add(f[i-1][2],f[i-1][4]));
f[i][4]=add(f[i][4],f[i-1][3]);
}if(s[i]=='1'||s[i]=='?'){
f[i][0]=add(f[i][0],f[i-1][1]);
f[i][2]=add(f[i][2],add(f[i-1][3],f[i-1][5]));
f[i][3]=add(f[i][3],f[i-1][4]);
f[i][5]=add(f[i][5],f[i-1][0]);
f[i][6]=add(f[i][6],f[i-1][2]);
}f[i][6]=add(f[i][6],f[i-1][6]);
if(s[i]=='?')f[i][6]=add(f[i][6],f[i-1][6]);
}cout<<add(f[n][2],f[n][6])<<'\n';
}
}
int main(){
// freopen("","r",stdin);
// freopen("","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int _=1;while(_--)my::solve();return 0;
}
```