題目鏈接：點擊查看
題目大意：給出一個長度為 n 的字串，由 ' a ' , ' b ' , ' c ' 和 ' ? ' 組成，每一個 ' ? ' 都可以變成三個字母之一，這樣的話假設有 k 個 ' ? ' ，則整個字串就有 3^k 中不同的表示，現在問這 3^k 個字串中，一共有多少個 abc 的子序列（不需要連續）
題目分析：考慮 dp，如果沒有 ' ? ' 的話還是比較經典的一道 dp 題目，dp[ i ][ 0 ] 代表的是到了第 i 個位置時， ' a ' 子序列的個數，dp[ i ][ 1 ] 代表的是到了第 i 個位置時，' ab ' 子序列的個數，dp[ i ][ 2 ] 代表的是到了第 i 個位置時，' abc ' 子序列的個數，答案顯然就是 dp[ n ][ 2 ] 了
考慮 ' ? ' 會對 dp 的轉移產生什么影響，因為 ' ? ' 可以將三種字母全部都表示一遍，所以到了第 i 個位置時，如果前面有 x 個 ' ? ' 的話，那么到達此位置的字串就會有 3^x 種，如果不考慮 ' ? ' 的話，碰到一個 ' a ' ，dp[ i ][ 0 ] 就需要加一，但現在如果考慮到 ' ? ' 的影響，dp[ i ][ 0 ] 就需要加上 3^x 才行
再考慮用 ' ? ' 去分別表示三種字母：
- ' ? ' 表示 ' a ' ：前面仍然有 dp[ i - 1 ][ 0 ] 個 ' a '，仍然有 dp[ i - 1 ][ 1 ] 個 ' ab '，仍然有 dp[ i - 1 ][ 2 ] 個 ' abc '，多了 3^x 個 a
- ' ? ' 表示 ' b ' ：前面仍然有 dp[ i - 1 ][ 0 ] 個 ' a '，仍然有 dp[ i - 1 ][ 1 ] 個 ' ab '，仍然有 dp[ i - 1 ][ 2 ] 個 ' abc '，多了 dp[ i - 1 ][ 0 ] 個 b
- ' ? ' 表示 ' c ' ：前面仍然有 dp[ i - 1 ][ 0 ] 個 ' a '，仍然有 dp[ i - 1 ][ 1 ] 個 ' ab '，仍然有 dp[ i - 1 ][ 2 ] 個 ' abc '，多了 dp[ i - 1 ][ 1 ] 個 c
直接轉移就好了
代碼：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e5+100;
const int mod=1e9+7;
LL dp[N][3];
char s[N];
int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);
int n;
scanf("%d%s",&n,s+1);
LL base=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='a')
{
dp[i][0]=(dp[i-1][0]+base)%mod;
dp[i][1]=dp[i-1][1];
dp[i][2]=dp[i-1][2];
}
else if(s[i]=='b')
{
dp[i][0]=dp[i-1][0];
dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod;
dp[i][2]=dp[i-1][2];
}
else if(s[i]=='c')
{
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1];
dp[i][2]=(dp[i-1][1]+dp[i-1][2])%mod;
}
else if(s[i]=='?')
{
dp[i][0]=(dp[i-1][0]*3+base)%mod;
dp[i][1]=(dp[i-1][1]*3+dp[i-1][0])%mod;
dp[i][2]=(dp[i-1][2]*3+dp[i-1][1])%mod;
base=base*3%mod;
}
}
printf("%lld\n",dp[n][2]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/142792.html
標籤：其他
上一篇：Android-簡易計算器