GPLT团体程序设计天梯赛真题训练：2025年

GPLT团体程序设计天梯赛真题训练：2025年

摘要

题目 分值 知识点
L1-1 珍惜生命 5 HelloWorld
L1-2 偷感好重 5 简单运算
L1-3 高温补贴 10 分支
L1-4 零头就抹了吧 10 位运算
L1-5 这是字符串题 15 循环
L1-6 这不是字符串题 15 字符串
L1-7 大幂数 20 循环
L1-8 现代战争 20 优先队列
L2-1 算式拆解 25 栈
L2-2 三点共线 25 计算几何
L2-3 胖达的山头 25 差分
L2-4 被n整除的n位数 25 DFS
L3-1 人生就像一场旅行 30 Floyd
L3-2 影响力 30 数学，前缀和

L1-1 珍惜生命

1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;

int main(void){
	cout<<"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.";
	return 0;
}

L1-2 偷感好重

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;

int a,b,c;

int main(void){
	cin>>a>>b>>c;
	cout<<a+b+c;
	return 0;
}

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

int t1,s,t0;

int main(void){
	cin>>t1>>s>>t0;
	if(s == 1){
		if(t1 > 35 && t0 >= 33){
			cout<<"Bu Tie\n";
			cout<<t1;
		}else if(t1 <= 35 || t0 < 33){ 
			cout<<"Bu Re\n";
			cout<<t0;
		}
	}else if(s == 0){
		if(t1 > 35 && t0 >= 33){
			cout<<"Shi Nei\n";
			cout<<t1;
		}else{
			cout<<"Shu Shi\n";
			cout<<t0;
		}
	}
	return 0;
}

L1-4 零头就抹了吧

位运算，找到最高位的1，输出该位对应二进制数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

int n;

int main(void){
	cin>>n;
	if(n == 0) cout<<0;
	for(int i = 32 ; i >= 1 ; i --){
		if((n>>(i-1)) & 1){
			cout<<(1<<(i-1));
			break;
		}
	}
	return 0;
}

L1-5 这是字符串题

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

string s;
int cnt[26],w[26],ans;

int main(void){
	cin>>s;
	for(int i = 0 ; i < 26 ; i ++){
		cin>>w[i];
	}
	for(auto it : s){
		cnt[it - 'a']++;
	}
	for(int i = 0 ; i < 26 ; i ++){
		ans += cnt[i]*w[i];
	}
	for(int i = 0 ; i < 26 ; i ++){
		cout<<cnt[i]<<(i == 25 ? "\n":" ");
	}
	cout<<ans;
	return 0;
}

L1-6 这不是字符串题

因为输入数组的数值范围在0-26之间，转为包含a-z的字符串，再进行处理。

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

int n,m;
string s;

void solve(){
	int op; cin>>op;
	if(op == 1){
		int l1; cin>>l1;
		string s1 = "";
		for(int i = 1 ; i <= l1 ; i ++){
			int x; cin>>x;
			s1 += char('a' + x - 1);
		}
		int l2; cin>>l2;
		string s2 = "";
		for(int i = 1 ; i <= l2 ; i ++){
			int x; cin>>x;
			s2 += char('a' + x - 1);
		}
		int f = s.find(s1);
		if(f != -1) s.replace(f, l1, s2);
	}else if(op == 2){
		string res = "";
		for(int i = 0 ; i < s.length() ; i ++){
			res += s[i];
			if(i+1 < s.length()){
				int x1 = s[i] - 'a' + 1;
				int x2 = s[i+1] - 'a' + 1;
				if((x1 + x2) % 2 == 0){
					res += char('a' + (x1+x2)/2 - 1);
				}
			}
		}
		s = res;
	}else{
		int l, r; cin>>l>>r; l--; r--;
		string temp = "";
		string res = "";
		for(int i = 0 ; i < s.length() ; i ++){
			if(i >= l && i <= r){
				temp += s[i];
				if(i == r){
					reverse(temp.begin(), temp.end());
					res += temp;
				}
			}else{
				res += s[i];
			}
		}
		s = res;
	}
}

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		int x; cin>>x;
		s = s + char('a' + x - 1);
	}
	while(m--){
		solve();
	}
	for(int i = 0 ; i < s.length() ; i ++){
		cout<<int(s[i]-'a'+ 1)<<(i == s.length()-1 ? "\n":" ");
	}
	return 0;
}

L1-7 大幂数

从高到低，依次枚举k的值，并判断是否合法。

注意：需要开LL 和 写求幂函数（k <= 30, 快速幂不是必要的）

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;
using ll = long long;

ll n;
ll mypow(ll a, ll n){
	ll res = 1;
	while(n){
		if(n & 1) res *= a;
		a = a*a;
		n >>= 1;
	}
	return res;
}

//ll mypow(ll a, ll n){
//	ll res = 1;
//	for(int i = 1 ; i <= n ; i ++){
//		res *= a;
//	}
//	return res;
//}

bool judge(ll k){
	ll sum = 0;
	for(int i = 1 ; ; i ++){
		sum += mypow(i, k);
		if(sum == n){
			cout<<1<<"^"<<k;
			for(int j = 2 ; j <= i ; j ++){
				cout<<"+"<<j<<"^"<<k;
			}
			return true;
		}
		if(sum > n) break;
	}
	return false;
}

int main(void){
	cin>>n;
	for(int i = 30 ; i >= 1 ; i --){
		if(judge(i)){
			return 0;
		}
	}
	cout<<"Impossible for "<<n<<".";
	return 0;
}

L1-8 现代战争

使用row和col分别记录被消除的行和列。

使用优先队列存储对应数值和坐标，可以快速找到当前最大值及其坐标。

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

int n, m, k;
int a[maxn][maxn];
bool row[maxn], col[maxn];
priority_queue<pair<int, pair<int,int> > > pq;

void solve(void){
	while(!pq.empty()){
		int tx = pq.top().second.first;
		int ty = pq.top().second.second;
		pq.pop();
		if(!row[tx] && !col[ty]){
			row[tx] = col[ty] = true;
			break;
		}
	}
}

int main(void){
	cin>>n>>m>>k;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin>>a[i][j];
			pq.push({ a[i][j], {i, j} });
		}
	}
	while(k--){
		solve();
	}
	for(int i = 1 ; i <= n ; i ++){
		if(row[i]) continue;
		bool f = false;
		for(int j = 1 ; j <= m ; j ++){
			if(col[j]) continue;
			if(f) cout<<" ";
			cout<<a[i][j];
			f = true;
		}
		if(f) cout<<"\n";
	}
	return 0;
}

L2-1 算式拆解

栈模拟。

若 char == ‘）’，将之前的非空临时字符串存入栈，若栈不为空，则输出顶端；

若 char == '('，将之前的非空临时字符串存入栈；

若 char == else，将字符存入临时字符串。

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;

string s, res;
stack<string > st;

int main(void){
	cin>>s;
	for(auto it : s){
		if(it == ')'){
			if(!res.empty()){
				st.push(res);
				res = "";
			}
			if(!st.empty()){
				cout<<st.top()<<"\n";
				st.pop();
			}
		}else if(it == '('){
			if(!res.empty()){
				st.push(res);
				res = "";
			}
		}else{
			res += it;
		}
	}
	return 0;
}

L2-2 三点共线

注意：这里不能用set去重，需要存入vector，最后再去重。因为set的遍历比vector要慢，会超时。

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;
using ll = long long;
const ll N = 1e7;

ll n;
bool vis[10*N];
vector<ll> v[2];

int main(void){
	cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		ll x, y; cin>>x>>y;
		if(y == 2){
			vis[x + N] = true;
		}else{
			v[y].push_back(x);
		}
	}
	for(int i = 0 ; i <= 1 ; i ++){
		sort(v[i].begin(), v[i].end());
		v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
	}
	bool f = false;
	for(auto x1 : v[1]){
		for(auto x0 : v[0]){
			if(vis[x1*2 - x0 + N]){
				f = true;
				cout<<"["<<x0<<", 0] "<<"["<<x1<<", 1] "<<"["<<x1*2-x0<<", 2]\n";
			}
		}
	}
	if(!f) cout<<-1;
	return 0;
}

L2-3 胖达的山头

将ss:hh:tt转为数值，再转化为差分问题。

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
#include<bits/stdc++.h>
using namespace std;
const int day = 3600*24;

int n, ans, diff[day+1];

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		char c;
		int s1,h1,t1,s2,h2,t2;
		cin>>s1>>c>>h1>>c>>t1;
		cin>>s2>>c>>h2>>c>>t2;
		int l = s1*3600 + h1*60 + t1;
		int r = s2*3600 + h2*60 + t2;
		diff[l]++;
		diff[r+1]--;
	}
	for(int i = 1 ; i <= day ; i ++){
		diff[i] += diff[i-1];
		ans = max(diff[i], ans);
	}
	cout<<ans;
	return 0;
}

L2-4 被n整除的n位数

DFS从高位到低位生成 L - R的n位数，并剪枝。

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

ll n, l, r;
bool f;

void dfs(ll d, ll sum){
	if(sum > r) return;
	if(d == n){
		if(sum >= l && sum <= r && sum % d == 0){
			f = true;
			cout<<sum<<"\n";
		}
		return;
	}
	if(sum % d == 0){
		for(ll i = 0 ; i <= 9 ; i ++){
			dfs(d+1, sum*10 + i);
		}
	}
}

int main(void){
	cin>>n>>l>>r;
	for(ll i = 1 ; i <= 9 ; i ++){
		dfs(1, i);
	}
	if(!f) cout<<"No Solution\n";
	return 0;
}

L3-1 人生就像一场旅行

双权值Floyd。

注意：输出时，需要排除\(d[x][x]\)（自己走到自己）的情况。

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

int b, n, m, k;
int d[maxn][maxn],w[maxn][maxn];
vector<int> v1, v2;

void floyd(){
	for(int t = 1 ; t <= n ; t ++){
		for(int i = 1 ; i <= n ; i ++){
			if(d[i][t] == inf) continue;
			for(int j = 1 ; j <= n ; j ++){
				if(d[i][j] > d[i][t] + d[t][j]){
					d[i][j] = d[i][t] + d[t][j];
					w[i][j] = w[i][t] + w[t][j];
				}else if(d[i][j] == d[i][t] + d[t][j]){
					w[i][j] = max(w[i][j], w[i][t] + w[t][j]);
				}
			}
		}
	}
}

void solve(){
	v1.clear(); v2.clear();
	int max_ = -1;
	int x; cin>>x;
	for(int i = 1 ; i <= n ; i ++){
		if(i != x && d[x][i] <= b){
			v1.push_back(i);
			if(w[x][i] > max_){
				max_ = w[x][i];
				v2.clear();
				v2.push_back(i);
			}else if(w[x][i] == max_){
				v2.push_back(i);
			}
		}
	}
	if(v1.empty()){
		cout<<"T_T\n";
		return;
	}
	for(int i = 0 ; i < v1.size() ; i ++){
		cout<<v1[i]<<(i == v1.size()-1 ? '\n':' ');
	}
	for(int i = 0 ; i < v2.size() ; i ++){
		cout<<v2[i]<<(i == v2.size()-1 ? '\n':' ');
	}
}

int main(void){
	memset(d, inf, sizeof(d));
	cin>>b>>n>>m>>k;
	for(int i = 1 ; i <= m ; i ++){
		int x, y; cin>>x>>y>>d[x][y]>>w[x][y];
		d[y][x] = d[x][y]; w[y][x] = w[x][y];
	}
	floyd();
	while(k--){
		solve();
	}
	return 0;
}

L3-2 影响力

解法1：二维前缀和

设数组\(a[i,j]\)为$ max(i-1, j-1)$

求出a数组的二维前缀和，就求出了(0, 0) - (i, j)之间的所有点到（0， 0）的切比雪夫距离之和。

对于非原点，按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
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;

int main(void){
	cin>>n>>m;
	vector<vector<ll> > w(n+1, vector<ll>(m+1));
	vector<vector<ll> > a(n+1, vector<ll>(m+1));
	vector<vector<ll> > c(n+1, vector<ll>(m+1));
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin>>w[i][j];
			a[i][j] = max(i-1, j-1);
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
            // 加上四个象限
			c[i][j] += a[i][j];
			c[i][j] += a[n-i+1][j];
			c[i][j] += a[i][m-j+1];
			c[i][j] += a[n-i+1][m-j+1];
			// 减去4个重合边
            c[i][j] -= a[i][1] + a[1][j] + a[n-i+1][1] + a[1][m-j+1];
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cout<<c[i][j]*w[i][j]<<(j == m ? '\n':' ');
		}
	}
	return 0;
}

解法2：矩阵旋转 + 前缀和

切比雪夫距离： \[ d[p1][p2] = max\{|x1 - x2|, |y1 - y2|\} \] 曼哈顿距离： \[ d[p1][p2] = |x1 - x2| + |y1 - y2| \]

设 u = (x+y)/2， v = (x-y)/2，得到对应点（u, v),

旋转后数组（u, v）的曼哈顿距离 就是 原矩阵（x, y）的切比雪夫距离。

然后，我们可以推出： \[ D_A=\sum_B\frac{|u_A-u_B|+|v_A-v_B|}{2}\\ D_A=\frac{1}{2}\left(\sum_B|u_A-u_B|+\sum_B|v_A-v_B|\right) \\ \] 然后，对于一个点（u, v），它的曼哈顿距离之和（这里以u的部分为例，v类似）等于： \[ SumU_A=\sum_{B:u_B\leq u_A}(u_A-u_B)+\sum_{B:u_B>u_A}(u_B-u_A) \\ SumU_A=\left(u_A\sum_{B:u_B\leq u_A}1-\sum_{B:u_B\leq u_A}u_B\right)+\left(\sum_{B:u_B>u_A}u_B-u_A\sum_{B:u_B>u_A}1\right) \] 令\(count(u\leq u_A)\)表示满足\(u_B\leq u_A\)的点的数量，\(sum(u\leq u_A)\)表示这些点的\(u_B\)值之和。

令\(count(u>u_A)\)表示满足\(u_B>u_A\)的点的数量，\(sum(u>u_A)\)表示这些点的\(u_B\)值之和。 \[ SumU_A=[u_A\cdot count(u\leq u_A)-sum(u\leq u_A)]+[sum(u>u_A)-u_A\cdot count(u>u_A)] \] 我们只需要分别求出四个前缀和/ 后缀和数组即可。

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

int n,m;

int main(void){
	cin>>n>>m;
	vector<vector<int> > a(n+1, vector<int>(m+1));
	vector<vector<ll> > c(n+1, vector<ll>(m+1));
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin>>a[i][j];
		}
	}
	vector<int> pcu(2*N), pcv(2*N);
	vector<unsigned> psu(2*N), psv(2*N);
	// 写int有一个点会过不了
	// 换成unsigned过了
	// 求前缀和
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			int u = i+j;
			int v = i-j;
			pcu[u+N] ++;
			pcv[v+N] ++;
			psu[u+N] += u;
			psv[v+N] += v;
		}
	}
	for(int i = -N+5 ; i <= N-5 ; i ++){
		pcu[i+N] += pcu[i-1+N];
		pcv[i+N] += pcv[i-1+N];
		psu[i+N] += psu[i-1+N];
		psv[i+N] += psv[i-1+N];
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			int u = i+j;
			int v = i-j;
			c[i][j] += pcu[u+N]*u - psu[u+N];
			c[i][j] += pcv[v+N]*v - psv[v+N];
		}
	}
	// 求后缀和
	pcu.assign(2*N, 0);
	psu.assign(2*N, 0);
	pcv.assign(2*N, 0);
	psv.assign(2*N, 0);
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			int u = i+j;
			int v = i-j;
			pcu[u+N] ++;
			pcv[v+N] ++;
			psu[u+N] += u;
			psv[v+N] += v;
		}
	}
	for(int i = N-5 ; i >= -N+5 ; i --){
		pcu[i+N] += pcu[i+1+N];
		pcv[i+N] += pcv[i+1+N];
		psu[i+N] += psu[i+1+N];
		psv[i+N] += psv[i+1+N];
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			int u = i+j;
			int v = i-j;
			c[i][j] += psu[u+N] - pcu[u+N]*u;
			c[i][j] += psv[v+N] - pcv[v+N]*v;
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			c[i][j] /= 2;
			cout<<c[i][j]*a[i][j]<<(j == m ? '\n':' ');
		}
	}
	return 0;
}
题解 > GPLT > 真题模拟
#GPLT
GPLT团体程序设计天梯赛真题训练：2025年
https://czwcugb.github.io/题解/GPLT/2025/
作者
ChenZhiwei
发布于
2025年4月22日
许可协议