T1 谁拿了最多奖学金

模拟

solution

没什么好讲的，更据题意模拟即可。

求出每个人的奖学金，再求和和最大值

code

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

const int N = 105;

int n , sum , mx , p[N];
string s[N];

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		int e1 , e2 , w;
		char r1 , r2;
		
		cin >> s[i];
		cin >> e1 >> e2 >> r1 >> r2 >> w;
		
		if(e1 > 80 && w >= 1) p[i] += 8000;
		if(e1 > 85 && e2 > 80) p[i] += 4000;
		if(e1 > 90) p[i] += 2000;
		if(e1 > 85 && r2 == 'Y') p[i] += 1000;
		if(e2 > 80 && r1 == 'Y') p[i] += 850;
	}
	for(int i = 1 ; i <= n ; i ++){
		sum += p[i];
		
		if(p[mx] < p[i]) mx = i;
	}
	cout << s[mx] << endl << p[mx] << endl << sum;
	return 0;
}

T2 过河

dp + 数学

solution

首先朴素的思路很简单，设 $dp_{i}$ 为青蛙跳到第 $i$ 个位置最少需要踩到的石子数，有如下转移：

$$dp_{i} = \min_{s \leqslant k \leqslant t}(dp_{i - j} + \text{flag})$$

若 $i$ 位置有石头 $flag$ 为 $1$，否则为 $0$

但是这题的 $l$ 到了恐怖的 $10^9$，朴素肯定会 T。考虑优化，注意到 $m \leqslant 100$ 很小，考虑从 $m$ 入手

若两个石头间距离很大的话，则中间有很多状态是无用的，此时可以考虑缩点。我们可以缩小石头间距离达到缩小 $l$ 的目的

具体地，若两个石头距离大于 $100$ 的话，可以让石头距离为 $100$，否则距离不变（$100$ 这个数字可以为其他较大的数）

注意当 $s = t$ 时不能缩点，此时统计有多少个石头位置 为 $s$ 倍数即可

code

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

const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int l , s , t , m , ans = inf , cnt;
int a[N] , b[N] , to[N] , dp[N];

int main(){
	cin >> l >> s >> t >> m;
	
	if(l > N - 5) l = N - 5;
	
	for(int i = 1 ; i <= m ; i ++){
		cin >> a[i];
		cnt += (a[i] % s == 0);
	}
	if(s == t){
		cout << cnt;
		return 0;
	}
	
	sort(a + 1 , a + m + 1);
	
	for(int i = 1 ; i <= m ; i ++){
		if(a[i] - a[i - 1] > 100) b[i] = b[i - 1] + 100;
		else b[i] = b[i - 1] + a[i] - a[i - 1];
		
		to[b[i]] ++;
	}
	for(int i = 1 ; i <= l + t ; i ++){
		dp[i] = inf;
		for(int j = s ; j <= t ; j ++){
			if(i - j >= 0) dp[i] = min(dp[i] , dp[i - j] + to[i]);
		}
	}
	for(int i = l ; i <= l + t ; i ++){
		ans = min(ans , dp[i]);
	}
	cout << ans;
	return 0;
}

T3 篝火晚会

模拟 + 贪心

solution

可以先求每个同学的愿望是否都能够实现，即 $ans$ 是否为 $-1$

对于每个同学，如果他最希望相邻的两个同学的最希望相邻同学中都有他，则其愿望可以实现。

进行判定后则可以构造出一个目标的环，该环符合同学们的意愿，构造环的过程用 $dfs$ 选择一名同学遍历他希望相邻的同学即可

于是问题转化为从 $1$ 到 $n$ 的环变为目标环所需最小代价

考虑破环为链转化为链上问题，注意目标环有从左和从右两种拆链方式，对于从 $1$ 到 $n$ 的链变为目标链可以反转下，从目标链变为从 $1$ 到 $n$ 的链

根据所给命令形式，首先若目标链上与 $1$ 到 $n$ 的链上相同位置的元素不用换，对于不同位置上的：考虑建图，若当前元素为 $a_i$，连接链上 $a_i$ 位置的元素，链上 $a_i$ 位置的元素再链它的值所对应位置上的元素......依此类推，因为每个点都有一条出度和一条入度，所以最后图一定是一个或多个环构成的，加起来即代价为 $ans = n - cnt$。$cnt$ 为相同位置的元素个数

如何统计每条链上的相同位置的元素个数呢，可以令 $cnt_{i}$ 为目标环从 $i$ 到 $i + n - 1$ 的链上相同位置的元素个数

所以对于开二倍之后的每个元素 $a_i$，都会对 $cnt_{i - a_i + 1}$ 产生 $1$ 的贡献，枚举元素后统计最大 $cnt$ 即可

code

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

const int N = 1e5 + 5;

int n , flag = 1 , idx , cnt1[N] , cnt2[N] , ans;
int g[N][2] , vis[N] , q1[N] , q2[N];

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> g[i][0] >> g[i][1];
	}
	
	for(int i = 1 ; i <= n ; i ++){
		int p1 = g[i][0] , p2 = g[i][1];
		
		if(g[p1][0] != i && g[p1][1] != i) flag = 0;
		if(g[p2][0] != i && g[p2][1] != i) flag = 0;
	}
	if(!flag){
		cout << -1;
		return 0;
	}
	
	int t = 1;
	
	while(1){
		q1[++ idx] = t , vis[t] = 1;
		
		if(!vis[g[t][0]]) t = g[t][0];
		else if(!vis[g[t][1]]) t = g[t][1];
		else break;
	}
	q2[1] = 1;
	for(int i = 2 ; i <= n ; i ++){
		q2[i] = q1[n - i + 2];
	}
	for(int i = 1 ; i <= n ; i ++){
		q1[i + n] = q1[i];
		q2[i + n] = q2[i];
	}
	
	for(int i = 1 ; i <= 2 * n - 1 ; i ++){
		if(i - q1[i] + 1 >= 1) cnt1[i - q1[i] + 1] ++;
		if(i - q2[i] + 1 >= 1) cnt2[i - q2[i] + 1] ++;
	}
	for(int i = 1 ; i <= n ; i ++){
		ans = max(ans , max(cnt1[i] , cnt2[i]));
	}
	cout << n - ans;
	return 0;
}

T4 等价表达式

solution

直接去求等价的十分困难，可以带入一些数去求表达式的值，看有那些表达式和所给的表达式相等

直接随机化，随机十组数据就可以了

注意本题的括号有可能不匹配，要特判一下

code

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

int to[20] = {0 , 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 21 , 23};

const int N = 100;

int n , w[N];
string fs , ps[N];
stack<ll> num;
stack<char> op;

unordered_map<char , int> ma = {{'+' , 1} , {'-' , 1} , {'*' , 2} , {'^' , 3}};

bool isd(char a){
	return a >= '0' && a <= '9';
}

ll qpow(ll a , ll b){
	ll mul = 1;
	for(int i = 1 ; i <= b ; i ++) mul *= a;
	return mul;
}

void eval(){
	ll p2 = num.top(); num.pop();
	ll p1 = num.top(); num.pop();
	char r = op.top(); op.pop();
	
	if(r == '+') num.push(p1 + p2);
	if(r == '-') num.push(p1 - p2);
	if(r == '*') num.push(p1 * p2);
	if(r == '^') num.push(qpow(p1 , p2));
}

bool check(string s){
	int l = 0 , r = 0;
	for(int i = 0 ; i < s.size() ; i ++){
		if(s[i] == '(') l ++;
		if(s[i] == ')') r ++;
	}
	return l == r;
}

ll solve(string s , ll d){
	while(num.size()) num.pop();
	while(op.size()) op.pop();
	
	for(int i = 0 ; i < s.size() ; i ++){
		if(s[i] == ' ') continue;
		if(s[i] == 'a'){
			num.push(d);
		}
		else if(isd(s[i])){
			ll sum = 0 , j = i;
			
			while(isd(s[j])){
				sum = sum * 10 + s[j] - '0';
				j ++;
			}
			i = j - 1;
			num.push(sum);
		}
		else if(s[i] == '('){
			op.push(s[i]);
		}
		else if(s[i] == ')'){
			while(op.size() && op.top() != '(') eval();
			op.pop();
		}
		else{
			while(op.size() && op.top() != '(' && ma[s[i]] <= ma[op.top()]) eval();
			op.push(s[i]);
		}
	}
	while(op.size()) eval();
	return num.top();
}

int main(){
	char ch = getchar();
	while(ch != '\n' && ch != '\r'){
		fs += ch;
		ch = getchar();
	}
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		ch = getchar();
		while(ch == '\n' || ch == '\r'){
			ch = getchar();
		}
		while(ch != '\n' && ch != '\r'){
			ps[i] += ch;
			ch = getchar();
		}
	}
	
	for(int i = 1 ; i <= 10 ; i ++){
		ll res = solve(fs , to[i]);
		
		for(int j = 1 ; j <= n ; j ++){
			if(!check(ps[j])) continue;
			if(solve(ps[j] , to[i]) == res){
				w[j] ++;
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		if(w[i] == 10) cout << char(i + 'A' - 1);
	}
	return 0;
}

ps : 这份代码在洛谷上 AC 了，但在这个网站上不知道为什么会 WA（太玄学了）