Kyooma's Blog

2022年“图森未来杯”全国程序设计邀请赛

  • ~3.93K 字

题目来自: 2022年“图森未来杯”全国程序设计邀请赛

题集密码

ecnusei20

A - ECNU知多少

华东师范大学大学软件工程学院创建于XXXX年1月，是国家首批35所示范性软件学院之一，也是全国师范院校中唯一获准成立的示范性软件学院。

你能帮忙恢复这句话中缺失的信息吗？

CODE
1
2
3
4
5
6
7
8
#include <bits/stdc++.h>

using namespace std;

int main(){
	cout << "2002\n";
	return 0;
}

B - 你的数太多了

给定一个大小为 $n$ 的有序可重数列，要求把其中出现了超过 1 次的数字都去掉，求操作之后的数列。

对于所有数据满足：$1≤n≤10^5,1≤a_i≤10^9$。

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void solve(){
	int n;
	scanf("%d", &n);
	map<int, int> mp;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		mp[a[i]]++;
	}
	for(int i = 0; i < n; i++){
		if(mp[a[i]] > 1) continue;
		printf("%d ", a[i]);
	}
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

C - 五折券

现在你走进一个大商场，打算买 $n$ 个商品，其中第 $i$ 个商品的价格为 $a_i$ 元，同时你有 $m$ 张五折券。

若你买第 $i$ 个商品使用了 $Y$ 张打折券，则他购买这个商品只需要花费 $\lfloor \frac{a_i}{2^Y} \rfloor$ 元。

现在请你计算一下你购买这些商品至少要花费多少元？

对于所有数据满足：$1≤n≤10^5，1≤m≤2×10^5，1≤a_i≤10^9$。

SOLUTION

贪心, 每次取最大的数除以2即可

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;

void solve(){
	int n, m;
	scanf("%d%d", &n, &m);
	priority_queue<int> q;
	for(int i = 0, x; i < n; i++){
		scanf("%d", &x);
		q.push(x);
	}
	while(!q.empty()){
		int x = q.top();
		q.pop();
		x /= 2;
		q.push(x);
		m--;
		if(!m) break;
	}
	ll ans = 0;
	while(!q.empty()){
		ans += q.top();
		q.pop();
	}
	printf("%lld\n", ans);
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

D - 正多边形

给定二维格点上的n的点$(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$，是否存在$m$个点能构成正$m$边形？

SOLUTION

赛中在纸上画了半天, 发现好像画不出端点都在整数点上的正三角形, 然后就猜了一下只有正四边形是可能的, 于是就AC了

只需要暴力判断四个点能不能构成正四边形

对于所有数据满足：$3≤m<n≤10^2,−10^3≤x_i,y_i≤10^3$。

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e4 + 10, inf = 0x3f3f3f3f;

pii a[N];

int dis(pii x, pii y){
	return (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second);
}

void solve(){
	int n, m;
	scanf("%d%d", &n, &m);
	if(m != 4){
		printf("No\n");
		return;
	}
	for(int i = 0, x, y; i < n; i++){
		scanf("%d%d", &x, &y);
		a[i] = {x, y};
	}
	int ok = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			for(int p = 0; p < n; p++){
				if(p == i || p == j) continue;
				for(int q = 0; q < n; q++){
					if(q == i || q == j || q == p) continue;
					int dis1 = dis(a[i], a[j]), dis2 = dis(a[j], a[p]), dis3 = dis(a[p], a[q]), dis4 = dis(a[q], a[i]);
					if(dis1 != dis2 || dis1 != dis3 || dis1 != dis4) continue;
					int t1 = a[i].first - a[j].first, d1 = a[i].second - a[j].second;
					int t2 = a[p].first - a[j].first, d2 = a[p].second - a[j].second;
					if(t1 * t2 + d1 * d2 == 0) ok = 1;
				}
			}
		}
	}
	if(ok){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

E - 无独有偶（Easy）

对于 $n$ 名同学，每个人都有一个对应的实力值 $a_i$（实力值可能相同），组成序列 $a_1,⋯,a_n$。本质不同的实力值子序列是指长度不同或长度相同但对应位置上数不同的实力值子序列。

现在你需要回答有多少至少出现 两次 的本质不同实力值子序列。

对于所有数据满足：$1\le n\le 20$，$1\le a_i\le 10^9$。

SOLUTION

注意到$n$只有20, 暴力跑子序列即可, 对于判断我用了hash, (其他的判断方式比如map, int>可能也可以过.)

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 10;
const pii mod = {1e9 + 7, 1e9 + 9}, base = {131, 251};

pll operator*(const pll &p1, const pll &p2){
	return {p1.first * p2.first % mod.first, p1.second * p2.second % mod.second};
}

pll operator+(const pll &p1, const pll &p2){
	return {(p1.first + p2.first) % mod.first, (p1.second + p2.second) % mod.second};
}

int a[N];

void solve(){
	int n;
	scanf("%d", &n);
	map<pll, int> mp;
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	for(int i = 1; i < (1 << n); i++){
		pll res = {0, 0};
		for(int j = 0; j < n; j++){
			if(i >> j & 1){
				res = res * base + pll{a[j], a[j]};
			}
		}
		mp[res]++;
	}
	int ans = 0;
	for(auto i : mp){
		if(i.second > 1){
			ans++;
		}
	}
	printf("%d\n", ans);
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

F - 木桶效应

假设 有 $n$ 块木板，这 $n$ 块木板排成一排，每块木板长度为 $a_i$。当使用连续的一段木板作木桶时，木桶的容量为这些木板长度的最小值。

对于任意一个 $x(1\le x\le n)$，你需要回答如果使用 $n$ 块木板中的连续 $x$ 块木板做木桶，木桶的最大容量分别为多少？

对于所有数据满足：$1\le n\le 10^6$，$1\le a_i\le 10^9$。

SOLUTION

第一眼看过去感觉一眼线段树, 然后去试了试, 然后就TLE了. 果然1e6不大可能是线段树.

仔细想了想用个set就行了.

从小到大考虑, 以当前$i$为最小值的时候, 其实就是对数组中大于等于$i$的值求最长连续段(若长度为$m$), 则$i$这个值就能作为$x(1\le x\le m)$的答案, 然后标记每段的末尾的值, 最后更新即可

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e6 + 10;

int ans[N];

struct node{
	int a, p;
	bool operator<(const node &k){
		return a < k.a;
	}
}a[N];

void solve(){
	set<int> st;
	int n;
	scanf("%d", &n);
	for(int i = 0, x; i < n; i++){
		scanf("%d", &x);
		a[i] = {x, i + 1};	
	}
	sort(a, a + n);
	st.insert(0);
	st.insert(n + 1);
	for(int l = 0; l < n; l++){
		int r = l;
		while(r < n && a[r].a == a[l].a) r++;r--;
		int len = 1;
		for(int j = l; j <= r; j++){
			auto p = st.lower_bound(a[j].p);
			int r = *p;
			p--;
			len = max(r - 1 - *p, len);
		}
		for(int j = l; j <= r; j++){
			st.insert(a[j].p);
		}
		ans[len] = max(ans[len], a[l].a);
		l = r;
	}
	for(int i = n; i >= 1; i--){
		ans[i] = max(ans[i], ans[i + 1]);
	}
	for(int i = 1; i <= n; i++){
		printf("%d ", ans[i]);
	}
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

G - 数列

一个数列$A={a_1,a_2,…a_n}$（以下简写为$A={a_n}$）是$a,b-$数列当且仅当该数列满足以下条件：

  • $a_1=a,a_n=b$
  • $∀i∈[1,n),a_i<a_i+1≤a_i+2$

给定$k,a,b$，输出字典序最小的$k$个$a,b-$数列，同时统计有多少个满足条件的数列。

对于所有数据满足：$0≤a≤b≤10^6,1≤k≤10^5$。

SOLUTION

题意实际上就是初始值为$a$, 你每次可以让$a$变为$a+1$或者$a+2$, 问最后变成$b$有多少种不同的操作序列.

那么我们假设操作次数为$n$, $+1$的操作次数为$x$, $+2$的操作次数为$y$, 那么就有这么两个方程

  • $a + x + 2y = b$
  • $x + y = n$

那么我们就可以解出$x, y$了, 而对于这样一组$x, y$, 它的方案数就是一个简单的组合问题了, 可以推出柿子是$\frac{A_n^n}{A_x^xA_y^y}$, 而又注意到$n$最多只有$10^6$, 所以可以枚举这个$n$, 来计算总方案数.

至于要输出的字典序最小的$k$个, 直接dfs搜就行, 不过要注意它的输出格式(需要简单模拟一下)

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7;

ll qpow(ll a, ll b){
	ll res = 1;
	while(b){
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

ll f[N], inv[N];
int k, tot, ap[N], a, b, pre = inf;
vector<int> res;

void dfs(int now, int tar){
	if(now > tar) return;
	if(tot == k) return;
	if(now == tar){
		tot++;
		if(tot == 1){
			for(int i = 0; i < res.size(); i++){
				ap[i + 1] = res[i];
				printf("%d ", res[i]);
			}
			printf("%d\n", tar);
			ap[res.size() + 1] = tar;
		}else{
			printf("< %d >", ap[pre]);
			for(int i = pre; i < res.size(); i++){
				printf(" %d", res[i]);
			}
			printf(" %d\n", tar);
		}
		return;
	}
	res.push_back(now);
	dfs(now + 1, tar);
    pre = min(pre, (int)res.size());
	dfs(now + 2, tar);
	res.pop_back();
}

void solve(){
	scanf("%d%d%d", &a, &b, &k);
	ll ans = 0;
	for(int i = b - a; i >= 0; i--){
		int y = b - a - i, x = i - y;
		if(x < 0 || y < 0) break;
		ans += f[i] * inv[x] % mod * inv[y] % mod;
		if(ans >= mod) ans -= mod;
	}
	printf("%lld\n", ans);
	dfs(a, b);
}

int main(){
	int T = 1;
	f[0] = 1;
	for(int i = 1; i <= 1e6; i++){
		f[i] = f[i - 1] * i % mod;
	}
	inv[1000000] = qpow(f[1000000], mod - 2);
	for(int i = 1e6 - 1; i >= 0; i--){
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
	while(T--) solve();
	return 0;
}

H - 一起去旅行

现在你有一辆电驴最多只能存储 $t$ 的电量，想不想一起去旅行呢？

给出一张 $n$ 个点 $m$ 条边的无向图，表示旅行地图，你需要从 1 号点去往 $n$ 号点。每条边有一个权值表示经过这条边所需要耗费的电量。

每个点上都有一个充电桩，如果你在此处充 1 单位的电量需要耗费 $w_i$ 元。当然，我们不允许你在途中抛锚，即你必须保证每到达一个点，其小电驴的电量均大于等于 0。

请问你到达 $n$ 号点至少需要充多少电费。初始时你的小电驴电量为 0。

SOLUTION

可以建一张分层图, 将每个点拆成$t + 1$个点, 表示到达这个点的电量, 于是充电的操作就变成了这$t + 1$个点之间的连边, 不过要注意得连一条链, 连的太多可能会TLE

然后跑dij就完了

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e4 + 10, inf = 0x3f3f3f3f;

struct Edge{
	int v, c;
};

struct node{
	int p, ci, d;
	bool operator < (const node &k) const {
		return d > k.d;
	}
};

int vis[N][100], dis[N][100], w[N];
vector<Edge> e[N];


void solve(){
	int n, m, t;
	scanf("%d%d%d", &n, &m, &t);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= t; j++){
			dis[i][j] = inf;
		}
	}
	for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
	for(int i = 0, u, v, c; i < m; i++){
		scanf("%d%d%d", &u, &v, &c);
		e[u].push_back({v, c});
		e[v].push_back({u, c});
	}
	priority_queue<node> q;
	dis[1][0] = 0;
	q.push({1, 0, 0});
	while(!q.empty()){
		node ti = q.top();
		q.pop();
		int p = ti.p, ci = ti.ci, di = ti.d;
		if(vis[p][ci]) continue;
		vis[p][ci] = 1;
		if(ci < t){
			if(di + w[p] < dis[p][ci + 1]){
				dis[p][ci + 1] = di + w[p];
				q.push({p, ci + 1, dis[p][ci + 1]});
			}
		}
		for(int i = 0; i < e[p].size(); i++){
			int v = e[p][i].v, wi = e[p][i].c;
			if(ci < wi) continue;
			if(vis[v][ci - wi]) continue;
			if(dis[v][ci - wi] > di){
				dis[v][ci - wi] = di;
				q.push({v, ci - wi, di});
			}
		}
	}
	int ans = inf;
	for(int i = 0; i <= t; i++){
		ans = min(ans, dis[n][i]);
	}
	printf("%d\n", ans);
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

J - 中庸之道

现在你希望能设计一个数据结构，来实现如下两种操作，

  • $1\ \ \ x$，表示加入在数组最后添加一个数 $x$。
  • $2$，表示这个数组的中位数。

注意，最开始的时候数组是空的。中位数的定义为将所有数从小到大排序后的序列 $A$ 中，下标为 $\lceil \frac{|A|}{2} \rceil$ 的数的值。

对于所有数据满足：$1≤q≤2×10^5$，$−10^9≤x≤10^9$。

保证输入的第一个操作不为 $2$。

SOLUTION

一眼字典树, 这题中字典树对于插入和查询操作的时间复杂度都是常数级别的(因为$x$的长度只有10), 但是需要加一个基值让所有值变成正数, 不过可能权值线段树也够了

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 5e6 + 10;

int trie[N][10], tot, sum[N][10], ssum = 0;
int color[N];

void insert(int x){
	int r = 1e9, p = 0;
	ssum++;
	for(int i = 0; i < 10; i++, r /= 10){
		int c = x / r;
		c %= 10;
		sum[p][c]++;
		if(!trie[p][c]) trie[p][c] = ++tot;
		p = trie[p][c];
	}
	color[p]++;
}

int find(int k){
	int res = 0, p = 0;
	while(k > 0){
		for(int i = 0; i < 10; i++){
			if(sum[p][i] < k) k -= sum[p][i];
			else{
				res = res * 10 + i;
				p = trie[p][i];
				k -= color[p];
				break;
			}
		}
	}
	return res;
}

void solve(){
	int q;
	scanf("%d", &q);
	while(q--){
		int op, x;
		scanf("%d", &op);
		if(op == 1){
			scanf("%d", &x);
			x += 1000000000;
			insert(x);
		}else{
			printf("%d\n", find((ssum + 1) / 2) - 1000000000);
		}
	}
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可