GPLT团体程序设计天梯赛模拟：2024年校赛

GPLT团体程序设计天梯赛模拟：2024年校赛

摘要

题目 分值 知识点
涂色难题 25 图论
幸运数字2 25 哈希优化
保守秘密 25 并查集
博弈大王 30 博弈论
双向奔赴 30 Dijkstra最短路

涂色难题

题目描述

在迷雾山脉的一处洞穴旁发现了一个扭曲的身影。这个生物，名为古鲁姆，拥有着滑腻的灰色皮肤和一对大而凸出的眼睛，这双眼睛在黑暗中闪烁着疯狂和渴望的光芒。他的身体瘦弱，几乎如同骨架包裹在湿冷的皮肤下，每一个动作都透露出狡猾和绝望。古鲁姆看见你们，说：“我守住魔戒数百年了，但是一直得不到它的认可，如果你们能解开魔戒给我出的涂色难题，也许它会跟你们走吧。” 魔戒说它会考验你们t次，每次会给出一颗由n个点（不保证每次n的值相同）组成的树，初始情况所有点都是没有颜色的，随后你们任意选择一个点作为树的根节点，随后给所有的点依次涂上颜色，并遵循以下规则：

  • 任意两个相同颜色的点，在只经过同颜色点的情况下，相互可达

  • 不可以存在：两个同颜色的点具有相同的深度（深度：当前点距离根节点的距离）

    魔戒希望最后树中的颜色种类最少，请回答每个树在满足涂色规则的前提下需要的最少颜色种类数。

    输入格式

    第一行 输入1 个整数：t，表示有t次考验（t组数据） 每个考验的第一行是 1 个整数：n，表示树的顶点数目。 接下来一行会给出n-1个整数，第i个数表示点i+1和这个数字存在一条边，保证给出的信息可以构建联通所有点的树结构。 数据范围：1≤t≤104，1≤n≤106，保证测试数据中的所有n之和不超过106。

    输出格式

    输出t行，每行一个整数，表示要最少使用的颜色种类数目。

输入样例#1

1
2
3
4
5
2
5
1 1 3 1
4
1 2 3

输出样例#1

1
2
2
1

样例解释

样例 1 构造出的树结构如上，我们可以选择 2 作为根节点，然后给[2 1 5]涂一个颜色、给[3 4]涂另一个颜色即可。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;

int t;
int ind[maxn];

void solve(){
	int n;cin>>n;
	if(n == 1){
		cout<<1<<"\n";
		return;
	}
	memset(ind,0,sizeof(ind));
	for(int i = 1 ; i <= n-1 ; i ++){
		int x;cin>>x;
		ind[x]++;
		ind[i+1]++;
	}
	int ans = 0;
	for(int i = 1 ; i <= n ; i ++){
		if(ind[i] == 1){
			ans++;
		}
	}
	cout<<ans-1<<"\n";
} 

int main(void){
	cin>>t;
	while(t--){
		solve();
	}
	return 0; 
}

幸运数字2

题目描述

“大部分人的幸运数字是7，而我的幸运数字是2！”一个小男孩摆弄着他手中的数字。 接下来男孩会给你们n个整数，如果某 2 个整数相加的和是 2 的幂，则称其为幸运对。请输出这n个整数中的幸运对数目。

输入格式

第一行 输入 1 个整数：n，表示有n个整数。 第二行会给出n个整数。 数据范围：1≤n≤106，1≤整数大小≤109

输出格式

输出一个整数，表示输出这n个整数中的幸运对数目。

输入样例#1

1
2
4 
7 3 2 1

输出样例#1

1
2

输入样例#2

1
2
3 
1 1 1

输出样例#2

1
3

样例解释

样例 1 可以选择下标(1, 4)和(2, 4)。 样例 2 可以选择下标(1, 2)、(1, 3)、(2, 3)

代码

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll n,ans;
unordered_map<ll, ll > mp; 

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		ll x;cin>>x;
		mp[x]++;
	}
	for(ll i = 2 ; i <= 2e9 ; i*=2){
		for(auto it: mp){
			ll k = it.first;
			ll v = it.second; 
			if(mp.count(i-k)){
				if(k < i/2){
					ans += v*mp[i-k];
				}else if(k == i/2){
					ans += v*(v-1)/2;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

保守秘密

题目描述

在遥远的西西里岛上，这里住着n个岛民。你们得知不久后西西里岛将会被毁灭，善良你和Blice 希望将这个消息赶紧告诉全部岛民，且越早越好。 由于你们通知岛民需要时间，通知第i个岛民的时间需要*t**i*​​分钟。原本你们需要挨个通知所有岛民，不过幸好，部分岛民之间可以通过电话进行联系。假设岛民之间的相互通知时间可以忽略不计。 输出所有岛民都得到消息的最少花费时间（分钟数）。

注意：如果你和 Blice 希望通知多个岛民，你们需要挨个通知，这意味花费的时间是相加的，而非同时通知取大值。

输入格式

第一行输入 2 个整数：n m，表示有n个岛民，其中m对岛民之间可以直接相互通知。 第二行输入n个整数，第i个整数表示你们通知第i个岛民的时间需要ti​分钟。 接下来m行每行会给出两个整数，表示这两个村民之间可以进行通知。（保证无重边、自环） 数据范围：1≤n≤106，0≤m≤106，1≤ti​≤109

输出格式

输出一个整数，表示最少花费时间。

输入样例#1

1
2
3
4
5 2
2 5 3 4 8
1 4
4 5

输出样例#1

1
10

输入样例#2

1
2
10 0
1 2 3 4 5 6 7 8 9 10

输出样例#2

1
55

样例解释

样例 1 ：仅需通知岛民[1, 2, 3]，他们就会将消息传给所有人，且这样花费时间是最少的。 样例 2 ：你们不得不自己通知所有岛民。

代码

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
const int maxn = 1e6 + 10;

ll n,m;
ll pre[maxn],tim[maxn],ans;

ll find(ll x){
	if(pre[x] == x) return x;
	return pre[x] = find(pre[x]);
}

void join(ll x, ll y){
	ll fx = find(x);
	ll fy = find(y);
	if(fx != fy){
		if(tim[fx] < tim[fy]) pre[fy] = fx;
		else pre[fx] = fy;
	}
}

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		pre[i] = i;
		cin>>tim[i];
	} 
	for(int i = 1 ; i <= m ; i ++){
		ll a,b; cin>>a>>b;
		join(a,b);
	}
	for(int i = 1 ; i <= n ; i ++){
		if(pre[i] == i){
			ans += tim[i];
		}
	}
	cout<<ans;
	return 0;
}

博弈大王

题目描述

Wow！运气真不错，你和 Blice 成功从千年一遇的大门进入了异世界，祝贺你们！但是异世界并非什么善良和平之地，在这里有更厉害的情景等待你们去挑战，挑战成功后也许会得到一些奇怪的东西。 当心，你们可能会失败！ 穿过大门，在那有个脑袋是显示器的人形机器人。它自称是“博弈大王”，它要和你们进行博弈游戏。 在机器人的脑袋上，显示出了n个顺序排列的格子，每个格子里都有一个数字。规则是这样的，首先会完全随机选择一个格子放置旗帜，然后由你们先手，博弈大王后手，双方轮流行动，规则如下：

  • 必须移动旗帜，如果无法移动旗帜就意味输掉比赛
  • 若希望旗帜从第j个格子移动到第i个格子，则必须保证i<j并且第i个格子的数字 < 第j个格子的数字

注意：在这个游戏里，你和 Blice 看作一个玩家，共同对抗博弈大王； 已知博弈大王和你都十分聪明不会失误，在你看到n个格子中的数字后，请给出你们的获胜概率乘以n。 当然，为了防止聪明的参赛者挨个输入值获取分数，这样的游戏会玩t轮。

输入格式

第一个 1 个整数：t，表示一共t轮游戏。 每轮游戏包含两行输入： 第一行 输入1 个整数：n，表示游戏里一共有n个格子。 第二行输入n个整数，其中第i个数字表示第i个格子里的数字。 数据范围：1≤∑i=1t​n≤106，1≤具体数字≤109

输出格式

输出获胜概率乘以n，显然是一个整数。

输入样例#1

1
2
3
4
5
2
3
2 1 3
2
2 1

输出样例#1

1
2
1
0

样例解释

样例 1 的第一轮游戏，如果旗帜初始被放置在下标 3 的位置，你们可以将其移动至下标 1 位置，这样博弈大王就无法移动，输掉了比赛。其他两种情况都无法获胜，所以胜率是31，乘以n=3得到 1 。 样例 1 的第二轮游戏，没有一种情况可以胜利，自然胜率是 0 。

代码

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;

int t;

void solve(){
	int n;cin>>n;
	int min_ = INT_MAX;
	int ans = n;
	for(int i = 1 ; i <= n ; i ++){
		int x;cin>>x;
		if(x < min_){
			min_ = x;
			ans --;
		}
	}
	cout<<ans<<endl;
}

int main(void){
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

双向奔赴

题目描述

很不幸，当前挑战地图是一个由n个点组成的无向连通图，你初始在 1 点，Blice 初始在n点。情况紧急，你们需要在一起才能更好地发挥实力。 现实情况总是要复杂一些，你和 Blice 都是正常的人类，自然会有体力上限。你至多可以移动a距离、Blice 至多可以移动b距离。你们决定选择某个点作为见面点，若双方可达，使得两人走过的距离之和最小，并输出这个最小的距离和的值。如果图中没有双方均可达的点，请直接输出(T_T)。

注：不可以在边上见面！

输入格式

第一行 4 个整数：n m a b，分别表示：图有n个顶点、图有m条边（不会出现重边自环）、你能行走的最远距离、Blice 能行走的最远距离。 接下来的m行，每行输入3 个整数u v w，表示u点和v的距离值为w。 数据范围：2≤n≤106、0≤m≤106、1≤a,b,w≤109

输出格式

若存在双方均可达的见面点，输入最小距离和，否则输出(T-T)。

输入样例#1

1
2
3
4
5
6
4 5 3 5
1 2 2
2 3 10
2 4 5
1 3 5
3 4 1

输出样例#1

1
7

输入样例#1

1
2
2 1 1 1
1 2 2

输出样例#1

1
(T_T)

样例解释

样例 1 ：其图结构如上，你只可能抵达1或2点，Blice 只可能抵达4、3、2点，所以你们仅可以在2点相见。两人路程和为 7。 样例 2 ：显然不可行（不可以在边上见面)。

代码

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
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6 + 10;
const int maxm = 2e6 + 10;

ll n,m,a,b;
ll idx;
ll head[maxn],d1[maxn],d2[maxn];
bool vis1[maxn],vis2[maxn];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >, greater<pair<ll,ll> > > pq1,pq2; 


struct edge{
	ll to,nex,w;
}e[maxm];

void add_edge(ll from, ll to, ll w){
	e[idx].to = to;
	e[idx].w = w;
	e[idx].nex = head[from];
	head[from] = idx++;
}

void dijkstra(){
	// 1
	for(int i = 1 ; i <= n ; i ++){
		d1[i] = inf;
	} 
	d1[1] = 0;
	pq1.push({d1[1],1});
	while(!pq1.empty()){
		int f = pq1.top().second;
		pq1.pop();
		if(vis1[f]) continue;		
		vis1[f] = true;
		for(int j = head[f] ; j != -1 ; j = e[j].nex){
			int to = e[j].to;
			if(!vis1[to] && d1[to] > d1[f] + e[j].w){
				d1[to] = d1[f] + e[j].w;
				pq1.push({d1[to], to});
			}
		}
	}
	// 2
	for(int i = 1 ; i <= n ; i ++){
		d2[i] = inf;
	} 
	d2[n] = 0;
	pq2.push({d2[n],n});
	while(!pq2.empty()){
		int f = pq2.top().second;
		pq2.pop();	
		if(vis2[f]) continue;	
		vis2[f] = true;
		for(int j = head[f] ; j != -1 ; j = e[j].nex){
			int to = e[j].to;
			if(!vis2[to] && d2[to] > d2[f] + e[j].w){
				d2[to] = d2[f] + e[j].w; 
				pq2.push({d2[to], to});
			}
		}
	}
}

int main(void){
	cin>>n>>m>>a>>b;
	memset(head,-1,sizeof(head));
	for(int i = 1 ; i <= m ; i ++){
		int x,y,w;
		cin>>x>>y>>w;
		add_edge(x,y,w);
		add_edge(y,x,w);
	}
	dijkstra();
	ll ans = inf; 
	for(int i = 1 ; i <= n ; i ++){
		if(d1[i] <= a && d2[i] <= b){
			ans = min(ans, d1[i] + d2[i]);
		}
	}
	if(ans == inf){
		cout<<"(T_T)";
	}else{
		cout<<ans;
	}
	return 0;
}
题解 > GPLT > 校内模拟
#GPLT
GPLT团体程序设计天梯赛模拟：2024年校赛
https://czwcugb.github.io/题解/GPLT/2024-school/
作者
ChenZhiwei
发布于
2025年4月18日
许可协议