$200$ $pits$

T1 小田的宝石镇

solution

读题，容易得出一共有两条可能的最短路径 分别是：$a + 5b$ 和 $11a$ 所以答案取最大 $max(a + 5b , 11a)$

code

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

long long a , b;

int main(){
	freopen("gem.in" , "r" , stdin);
	freopen("gem.out" , "w" , stdout);
	
	cin >> a >> b;
	cout << min(a + 5 * b , 11 * a);
	return 0;
}

注意到 $a$ $b$ 达到了 $10^{12}$ 不开 long long 见祖宗

T2 小田的好数组

solution

读题，容易知道答案只有 $0$ 或 $n$ 两种可能，因为如果某个子序列是好数组，那么这个数组都是好数组。 否者就是 $0$ ，排序后比较即可

code

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

const int N = 2 * 1e5 + 5;

int n , a[N] , b[N];

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

T3 小田的数字合并

solution

读题，可以知道如果想极差最大，那么极小值只能为一个数，枚举极小值，用前缀和处理左右两边相加的和，比较即可 $ans = max(s[n] - s[i] - a[i],s[i - 1] - a[i])$ , 注意开 $long$ $long$

code

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

const int N = 2 * 1e5 + 5;

long long n , a[N] , b[N];

int main(){
	freopen("num.in" , "r" , stdin);
    freopen("num.out" , "w" , stdout);
	
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		b[i] = b[i - 1] + a[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		int mx = max(b[i - 1] , b[n] - b[i]);
		ans = max(ans , mx - b[i]);
	}
	cout << ans;
	return 0;
}

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 + dx[k]][j + dy[k]] = max_{\rm a[i + dx[k]][j + dy[k]] > a[i][j]} (dp[i + dx[k]][j + dy[k]] , dp[i][j] + 1)$ 其中 $dx,dy$ 为方向数组

注意

1. $dp[i][j] = 1$ 要初始化，因为一个元素的子序列长为 $1$
2. 要先转移 $dp[i + dx[k]][j + dy[k]]$，用已知去推未知

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 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;
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			for(int k = 0 ; k < 4 ; k ++){
				if(a[i + dx[k]][j + dy[k]] > a[i][j]) dp[i + dx[k]][j + dy[k]] = max(dp[i + dx[k]][j + dy[k]] , 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 < dp[i][j]){
				ans = dp[i][j];
				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("flower.in" , "r" , stdin);
    freopen("flower.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;
}