2022“杭电杯”中国大学生算法设计超级联赛（3）

本文主要是介绍2022“杭电杯”中国大学生算法设计超级联赛（3），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

比赛链接：

https://vjudge.net/contest/507736

B - Boss Rush

题意：

有 \(n\) 个技能，第 \(i\) 个技能使用完后的 \(t_i\) 时间内不能使用其他技能，该技能会在 \(len_i\) 的时间中，每秒造成 \(d[i][j]\) 点伤害 \((1 <= j <= len_i)\)，boss 有 \(H\) 滴血，问最短多少时间能杀死 boss。

思路：

先二分时间，然后通过记忆化搜索 + 状态压缩判断指定时间内是否能造成相对应的伤害。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 20, M = 1e5 + 10, K = 3e5 + 10;
LL n, H, t[N], len[N], d[N][M], pre[N][M], dp[K];
bool check(LL x){
	for (int i = 0; i < (1 << n); i ++ ){
		dp[i] = -1;
	}
	function<LL(LL)> dfs = [&](LL state){
		if ( ~ dp[state]) return dp[state];
		LL ans = 0, sumt = 0;
		for (int i = 0; i < n; i ++ ){
			if (state >> i & 1){
				sumt += t[i + 1];  //已经使用的技能的冷却时间
			}
		}
		if (sumt > x) return dp[state] = 0;
		for (int i = 0; i < n; i ++ ){
			if ( ! (state >> i & 1)){  //使用新的技能
				ans = max(ans, pre[i + 1][min(len[i + 1], x - sumt)] + dfs(state | (1 << i)));
			}
		}
		return dp[state] = ans;
	};
	return dfs(0) >= H;
}
void solve(){
	cin >> n >> H;
	LL mx = 0;
	for (int i = 1; i <= n; i ++ ){
		cin >> t[i] >> len[i];
		mx += t[i] + len[i];
		for (int j = 1; j <= len[i]; j ++ )
			cin >> d[i][j];
		for (int j = 1; j <= len[i]; j ++ )
			pre[i][j] = pre[i][j - 1] + d[i][j];
	}
	LL L = 0, R = mx + 1;
	while(L < R){
		LL mid = (L + R) >> 1;
		if (check(mid)){
			R = mid;
		}
		else{
			L = mid + 1;
		}
	}
	if (L > mx) cout << "-1\n";
	else cout << L - 1 << "\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL T = 1;
	cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}

C - Cyber Language

题意：

给定一行句子，输出每个单词的首字母的大写。

思路：

签到，按题意操作。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
char s[100];
void solve(){
	gets(s);
	for (int i = 0; i < strlen(s); i ++ )
		if (i == 0 || s[i - 1] == ' ')
			cout << (char)(s[i] - 'a' + 'A');
	cout << "\n";
}
int main(){
	LL T = 1;
	cin >> T;
	getchar();  //把换行读取了
	while(T -- ){
		solve();
	}
	return 0;
}

I - Package Delivery

题意：

快递站有 \(n\) 个包裹，每个包裹从第 \(l\) 天存放到第 \(r\) 天，每次去快递站可以拿 \(k\) 个包裹，问最少去快递站几次能拿到所有包裹。

思路：

对于第 \(i\) 个快递，它的时间为 \(l_i\) 到 \(r_i\)。
按照贪心的策略，肯定拿 \(r_i\) 最小的那个快递，再从所有 \(l_j <= r_i <= r_j\) 的快递中选 \(r_j\) 最小的 \(k\) 个拿走。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
	LL n, k;
	cin >> n >> k;
	vector < pair<LL, pair<LL, LL> > > st(n);
	vector < pair<LL, LL> > ed(n);
	for (int i = 0; i < n; i ++ ){
		cin >> st[i].first >> ed[i].first;
		st[i].second = {ed[i].first, i};
		ed[i].second = i;
	}
	sort(st.begin(), st.end());
	sort(ed.begin(), ed.end());
	priority_queue < pair<LL, LL>, vector< pair<LL, LL> >, greater< pair<LL, LL> > > q;
	vector <bool> used(n, false);
	LL ans = 0;
	for (int i = 0, j = 0; i < n; i ++ ){
		if (used[ed[i].second]) continue;
		while(j < n && st[j].first <= ed[i].first){
			q.push(st[j].second);
			j ++ ;
		}
		ans ++ ;
		for (int t = 0; t < k; t ++ ){
			if (q.empty()) break;
			used[q.top().second] = true;
			q.pop();
		}
	}
	cout << ans << "\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL T = 1;
	cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}

K - Taxi

题意：

有 \(n\) 个小镇，第 \(i\) 个小镇的位置为 \(（x_i，y_i）\)，费用为 \(w_i\)，对于一个点 \(（x^{'}, y^{'}）\)，它到第 \(i\) 个小镇的费用为 \(min(w_i, \lvert x^{'} - x_i \rvert + \lvert y^{'} - y_i \rvert)\)，现有 q 次询问，每次告诉一个点 \(（x^{'}, y^{'}）\)，问小镇到这个点的费用最大为多少？。

思路：

\(max(\lvert x^{'} - x_i \rvert, \lvert y^{'} - y_i \rvert)\)
= \(max(max(x^{'} - x_i, - x^{'} + x_i), max(y^{'} - y_i, - y^{'} + y_i))\)
= max{\((x^{'} + y^{'}) + (- x_i - y_i), (x^{'} - y^{'}) + (- x_i + y_i), (- x^{'} + y^{'}) + (x_i - y_i), (- x^{'} - y^{'}) + (x_i + y_i)\)}
所以只需要预处理出所有城镇坐标的四个属性，就可以通过 O(1) 的方法计算曼哈顿距离的答案。
而 \(w\) 则没办法，所以对 \(w\) 进行排序，使其单调，那么就可以通过二分取选择 \(w\)。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL N = 1e5 + 10, INF = 1e18;
struct node{
	LL x, y, w;
	bool operator < (const node & x) const{
		return w < x.w;
	}
}point[N];
LL a[N], b[N], c[N], d[N], ans;
void solve(){
	LL n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i ++ )
		cin >> point[i].x >> point[i].y >> point[i].w;
	sort(point + 1, point + n + 1);
	a[n + 1] = b[n + 1] = c[n + 1] = d[n + 1] = -INF;
	for (int i = n; i >= 1; i -- ){
		a[i] = max(a[i + 1], point[i].x + point[i].y);
		b[i] = max(b[i + 1], point[i].x - point[i].y);
		c[i] = max(c[i + 1], - point[i].x + point[i].y);
		d[i] = max(d[i + 1], - point[i].x - point[i].y);
	}
	while(q -- ){
		LL x, y;
		cin >> x >> y;
		ans = 0;
		LL L = 1, R = n;
		function <bool(LL)> check = [&](LL k){
			LL mx = a[k] - x - y;
			mx = max(mx, b[k] - x + y);
			mx = max(mx, c[k] + x - y);
			mx = max(mx,  d[k] + x + y);
			ans = max(ans, min(point[k].w, mx));
			return point[k].w < mx;
		};
		while(L < R){
			LL mid = (L + R) >> 1;
			if (check(mid)){
				L = mid + 1;
			}
			else{
				R = mid;
			}
		}
		check(L);
		cout << ans << "\n";
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL T = 1;
	cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}

L - Two Permutations

题意：

给定两个序列 \(p\) 和 \(q\)，每次重构从其中一个序列中取出首位元素，然后加入序列 \(r\) 的后面，直到两个序列所有元素被取完结束，现在给定序列 \(s\)，问有多少种取法可以让 \(r = s\)。

思路：

因为每次只从 \(p\) 或者 \(q\) 中取出元素，所以可以定义 \(dp[i][0]\) 表示 \(r\) 序列的第 \(i\) 位是从 \(p\) 序列中取出来的方案数，\(dp[i][1]\) 表示 \(r\) 序列的第 \(i\) 位是从 \(q\) 序列中取出来的方案数。
如果该元素本来就是从本序列中取出，即 \(s[i - 1]\) 和 \(s[i]\) 是从同一个序列中取出的，那么它们位置的坐标差为 1。
如果是从不同序列中取出的，因为之前总共取了 \(i\) 个元素，那么两个序列中的位置之和一定等于 \(i\)。
所以在动态规划之前，先记录两个序列中每个元素的位置即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 998244353;
void solve(){
	LL n;
	cin >> n;
	vector <LL> p(n + 1), q(n + 1), id1(n + 1), id2(n + 1), s(2 * n + 1);
	for (int i = 1; i <= n; i ++ ){
		cin >> p[i];
		id1[p[i]] = i;
	}
	for (int i = 1; i <= n; i ++ ){
		cin >> q[i];
		id2[q[i]] = i;
	}
	for (int i = 1; i <= 2 * n; i ++ )
		cin >> s[i];
	vector < vector<LL> > dp(2 * n + 1, vector<LL>(2));
	dp[0][0] = 1;
	LL ans = 0;
	for (int i = 1; i <= 2 * n; i ++ ){
		LL pre = s[i - 1], now = s[i];
		if (id1[now] == id1[pre] + 1) dp[i][0] = (dp[i][0] + dp[i - 1][0]) % mod;
		if (id1[now] + id2[pre] == i) dp[i][0] = (dp[i][0] + dp[i - 1][1]) % mod;
		if (id2[now] == id2[pre] + 1) dp[i][1] = (dp[i][1] + dp[i - 1][1]) % mod;
		if (id2[now] + id1[pre] == i) dp[i][1] = (dp[i][1] + dp[i - 1][0]) % mod;
	}
	cout << (dp[2 * n][0] + dp[2 * n][1]) % mod << "\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL T = 1;
	cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}

这篇关于2022“杭电杯”中国大学生算法设计超级联赛（3）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

2022“杭电杯”中国大学生算法设计超级联赛（3）

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯