仅供参考

T4 化学式的原子数

solution

这是一道大模拟题，主要考察表达式和哈希。 步骤：

1. 读入字符串 $s$ , 定义哈希栈 $st$ 遍历字符串 $s$
2. $if$ 遇到 字符 $($ 定义一个空哈希表入栈
3. $if$ 遇到 字符 $)$ 出栈顶哈希表，将表后数字分别乘分子式中数字，读取括号后面数字 $num$，$e$ 表示哈希表中分子式数字，$atn$ 原子名字，$st.top()[atn] += e * num$
4. 否者，读取分子式，$st.top()[atn] += e;$
5. 最后，将栈顶哈希表输出，因为 $map$ 自动可以按字典序排

读入数字，分子式代码

int get_n(){
	int j = i , sum = 0;
	if(s[i] <= '9' && s[i] >= '0'){
		while(s[j] <= '9' && s[j] >= '0' && j < len){
			sum = sum * 10 + s[j] - '0';
			j ++;
		}
		i = j;
	}
	return max(sum , 1);
}

string get_s(){
	string d;
	if(s[i] <= 'Z' && s[i] >= 'A'){
		int j = i + 1;
		d += s[i];
		while(s[j] <= 'z' && s[j] >= 'a' && j < len){
		    d += s[j];
		    j ++;
		}
		i = j;
	}
	return d;
}

注意要更新 $i = j$ , tnnd 我在这里调了半小时

code

完整代码

#include<bits/stdc++.h>
using namespace std;

string s;
int len , i;
stack<map<string , int> > st;

int get_n(){
	int j = i , sum = 0;
	if(s[i] <= '9' && s[i] >= '0'){
		while(s[j] <= '9' && s[j] >= '0' && j < len){
			sum = sum * 10 + s[j] - '0';
			j ++;
		}
		i = j;
	}
	return max(sum , 1);
}

string get_s(){
	string d;
	if(s[i] <= 'Z' && s[i] >= 'A'){
		int j = i + 1;
		d += s[i];
		while(s[j] <= 'z' && s[j] >= 'a' && j < len){
		    d += s[j];
		    j ++;
		}
		i = j;
	}
	return d;
}

int main(){
	freopen("atom.in" , "r" , stdin);
	freopen("atom.out" , "w" , stdout);
	cin >> s;
	len = s.size();
	st.push({});
	
	while(i < len){
		if(s[i] == '('){
			st.push({});
			i ++;
		}
		else if(s[i] == ')'){
			auto w = st.top();
			i ++;
			int num = get_n();
			st.pop();
			
			for(auto &item : w){
				string atn = item.first;
				int e = item.second;
				st.top()[atn] += e * num;
			}
		}else{
			string atn = get_s();
			int e = get_n();
			st.top()[atn] += e;
		}
	}
	auto w = st.top();
	for(auto &item : w){
		string atn = item.first;
		int e = item.second;
		cout << atn << " " << e << endl;
	}
	return 0;
}

T5 小W挖宝藏

solution

读题，注意到 $n,m<100$，搜索肯定会爆，考虑 $dp$ 的低配版 记忆化搜索，设 $dp(i , j)$表示以第 $(i,j)$ 结尾的最长上升子数组的最大值，$i$为横坐标，$j$ 为纵坐标

可以得到状态转移方程为 $dp[i][j] = max_{\rm a[i + dx[k]][j + dy[k]] > a[i][j]} (dfs(i + dx[k])(j + dy[k]) + 1 , dp[i][j])$ 其中 $dx,dy$ 为方向数组

注意

1. 如果 $dp[i][j]$ 有值，跳出 $dfs$，$ans = dp[i][j] + 1$，因为子数组在一个元素时的长度没加
2. 注意边界条件

code

#include<bits/stdc++.h>
using namespace std;

const int N = 105;

int dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};

int n , m;
int a[N][N] , dp[N][N];

int dfs(int x , int y){
	if(dp[x][y]) return dp[x][y];
	
	for(int i = 0 ; i < 4 ; i ++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
		if(a[nx][ny] < a[x][y])  dp[x][y] = max(dp[x][y] , dfs(nx , ny) + 1);
	}
	return dp[x][y];
}

int main(){
	freopen("treasure.in" , "r" , stdin);
    freopen("treasure.out" , "w" , stdout);
	
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin >> a[i][j];
			//dp[i][j] = 1;
		}
	}
	int ans = 0, x , y;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			if(ans < dfs(i , j) + 1){
				ans = dfs(i , j) + 1;
				x = i;
				y = j;
			}
		}
	}
	cout << x << " " << y << endl << ans;
	return 0;
}

T6 小z的等待时间

solution

设 $dp[i]$ 为第 $i$ 朵花为 $0$ 时的时间，$dp[i] = dp[i + 1] + 1$

最后输出 $dp[1]$

code

#include<bits/stdc++.h>
using namespace std;

const int N = 2 * 1e5 + 5;

long long n , dp[N];

int main(){
	freopen("flowers.in" , "r" , stdin);
    freopen("flowers.out" , "w" , stdout);
	
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> dp[i];
	}
	for(int i = n ; i >= 1 ; i --){
		if(dp[i] <= dp[i + 1]) dp[i] = dp[i + 1] + 1;
	}
	cout << dp[1];
	return 0;
}