前言

胸有丘壑，气吞山河。

正片

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\)。

根据题意直接列出转移方程：

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;
}

D 题：

一道大模拟，只要把题看懂了就可以了。

有很多的细节和赋值顺序。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
string s;
int n,m;
int value[N],len;
int sum[N],point[N],w,cnt;
bool check(char s){return s>='a'&&s<='z';}
struct Node{
	char opt;
	int idx;
	int rk;
}lr[N];
bool cmp(Node x,Node y){return x.opt<y.opt;}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>s;n=s.size();s=" "+s;
	for(int i=n;i;i--) if(check(s[i])) lr[++len].opt=s[i],lr[len].idx=i,lr[len].rk=len,point[i]=len;
	for(int i=1;i<=len;i++) cin>>value[i];
	cnt=len+1;
	for(int i=n;i;i--){
		sum[i]=sum[i+1];
		if(check(s[i])){
			cnt--;
			sum[i]+=value[cnt];
		}
		else sum[i]++;
	}
	sort(lr+1,lr+len+1,cmp);//按照字典序排列。
	for(int i=1;i<=len;i++){
		int rk=lr[i].rk,idx=lr[i].idx;//从后往前第rk个
		if(idx==n){
			cout<<lr[i].opt;
			if(i!=len) cout<<"+";
		}
		else{
			cout<<"1";
			for(int j=1;j<=sum[idx+1];j++) cout<<"0";
			cout<<lr[i].opt;
			if(i!=len) cout<<"+";
		}
	}
	if(len==n) return 0;
	cnt=0;
	bool flag=true;
	for(int i=1;i<=n;i++){
		if(!check(s[i])){
			if(flag){
				if(s[i]=='0') continue;
				if(len) cout<<"+";
				flag=false;
			}
			cout<<s[i];
		}
		else{
			if(flag) continue;
			cnt++;
			for(int j=1;j<=value[cnt];j++) cout<<"0";
		}
	}
	return 0;
}

E 题：

F 题：