前言
胸有丘壑，气吞山河。
正片
A 题：
考虑使用 DP，由于题目给了 2 个 a 不能在一起的限制，所以每次接上一个 a 都要考虑一下前面的一个状态是否也是 a。
于是就可以使用 \(f,g\) 数组，\(f_i\) 表示第 \(i\) 个字母是 a 的合法情况有多少，\(g_i\) 表示第 \(i\) 个字母是 b 或 c 的合法情况有多少。
预处理出 \(i=1\) 的情况，即 \(f_1=1,g_1=2\)。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2000;
int n,f[N],g[N];//f[i]a,g[i]b,c
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
f[1]=1,g[1]=2;
for(int i=2;i<=n;i++){
f[i]=g[i-1];
g[i]=f[i-1]*2+g[i-1]*2;
}
cout<<g[n]+f[n]<<"\n";
return 0;
}
/*
*/
B 题：
证明可以用数学归纳法或者一些分讨做，这里就不过多阐述。
可以发现规律：\(n\) 是奇数的时候，一定是 tao 赢；否则是 chang 赢。
AC code
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int T;
int n;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>T;
while(T--){
cin>>n;
if(n&1) cout<<"tao\n";
else cout<<"chuan\n";
}
return 0;
}
C 题：
依旧考虑使用 DP。
\(f_{i,0}\) 表示 \(i\) 颗蓝宝石可以转换成多少枚 1 级的蓝宝石；\(f_{i,1}\) 表示 \(i\) 颗红宝石可以转换为多少枚 1 级的蓝宝石。
初始化：\(f_{i,0}=1\)。
根据题意直接列出转移方程：
\[f_{i,0}=f_{i-1,1}+y\times f_{i-1,0} \]\[f_{i,1}=f_{i-1,1}+x\times f_{i,0} \]AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef array<int,2> AR2;
typedef pair<int,int> PII;
typedef unsigned long long ULL;
#define fi first
#define se second
const int dx[]={},dy[]={};
const int N=200010;
int n,x,y;
int f[N][2];//f[i][1]红宝石
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>x>>y;
f[1][0]=1;
for(int i=2;i<=n;i++){
f[i][0]=f[i-1][1]+y*f[i-1][0];
f[i][1]=f[i-1][1]+x*f[i][0];
}
cout<<f[n][1]<<"\n";
return 0;
}