问题 A: mine
时间限制: 1 Sec 内存限制: 256 MB
提交: 129 解决: 31
[提交][状态]
题目描述
有一个1 维的扫雷游戏，每个格子用*表示有雷，用0/1/2 表示无雷并且相邻格子中有0/1/2 个雷。
给定一个仅包含?、、0、1、2 的字符串s，问有多少种方法将所有的?改为/0/1/2 使其合法。
输入
一行一个字符串s
输出
一行一个整数表示答案，对10^9+7 取模
样例输入
?1?
样例输出
2
提示
对于30%的数据，|S|<=20。
对于60%的数据，|S|<=1000。
对于100%的数据，|S|<=10^6。
通过数据范围发现效率应该是O(N)的。
然后发现‘1’非常恶心。其实1可以分开考虑，即分成雷在前面和雷在后面两种。讨论起来就非常方便了。
#pragma GCC optimize("O3")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000005
#define ll long long
#define mod 1000000007
using namespace std;
int n;ll f[N][5];char s[N];
int main()
{ scanf("%s",s+1);n=strlen(s+1);if(s[1]=='0')f[1][0]=1;if(s[1]=='1')f[1][4]=1;if(s[1]=='*')f[1][3]=1;if(s[1]=='?'){f[1][0]=1;f[1][4]=1;f[1][3]=1;}for(int i=2;i<=n;i++){if(s[i]=='?'){f[i][3]=(f[i-1][4]+f[i-1][2]+f[i-1][3])%mod;f[i][0]=(f[i-1][0]+f[i-1][1])%mod;f[i][1]=f[i-1][3];if(i!=n)f[i][4]=(f[i-1][1]+f[i-1][0])%mod;if(i!=n)f[i][2]=f[i-1][3];}else{if(s[i]=='*')f[i][3]=(f[i-1][4]+f[i-1][2]+f[i-1][3])%mod;if(s[i]=='0')f[i][0]=(f[i-1][0]+f[i-1][1])%mod;if(s[i]=='1'){f[i][1]=f[i-1][3];f[i][4]=(f[i-1][1]+f[i-1][0])%mod;}if(s[i]=='2')f[i][2]=f[i-1][3];}}ll ans=0;for(int i=0;i<=3;i++)ans+=f[n][i];cout<<ans%mod;
}