【GPLT】2025年第十届团队程序设计天梯赛赛后题解

题目集选自官网 : 团体程序设计天梯赛-练习集

评价

整体难度较去年(除去猫娘) 基本持平 ，依旧是同样题型， L2-3的超时优化 和 字符串(依旧) 较其他题目更为卡时间
但今年服务器问题多多少少影响心态和发挥

L1

L1-105 珍惜生命

经典Hello world题目

#include <iostream>
using namespace std;int main(){cout << "Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.";
}

L1-106 偷感好重

三个数字相加输出即可

#include <iostream>
using namespace std;int main(){int a,b,c;cin >> a >> b >> c;cout << a+b+c;
}

L1-107 高温补贴

简单的分支语句题目。
个人感觉：今年阅读理解比去年少很多了(也短很多)

#include <iostream>
using namespace std;int main(){int t,s,t1;cin >> t >> s >> t1;if(s && (t >= 35 && t1 >= 33))cout << "Bu Tie\n" << t;else if(!s && (t >= 35 && t1 >= 33))cout << "Shi Nei\n" << t;else if(s)cout << "Bu Re\n" << t1;else cout << "Shu Shi\n"<< t1;
}

L1-108 零头就抹了吧

数学题
思路 ： 找到二进制最高位的1即可

用 log2(n) 找到最高位 1 ， 然后 pow(2,位数) 还原数字

#include <iostream>
#include <cmath>
#define int long long
using namespace std;
int n;
void solve(){cin >> n;printf("%lld" , (int)pow(2,(int)log2(n)));
}signed main(){int _=1;//cin >>_;while(_--)solve();
}

L1-109 这是字符串题

循环结构题目
数组/map 保存 每个字符的权重

然后统计字符出现个数并且答案加上该字符权重即可

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <tuple>
#include <stack>
#include <cmath>
#include <algorithm>
#include <map>#define int long long
#define For(a,b) for(int i=(a) ; i<= (b) ; ++i)
#define endx(x) {cout << (x) << '\n' ; return;}
#define debug(x) {cout << #x << ' ' << (x) << '\n';}
using namespace std;
const int N = 1e5+10;
const int M = 1e3+10;
int n,m,k,q;void solve_5(){map<char,int>ma; // 字符->权重string s;cin >> s;For('a','z'){cin >> q;ma[i] = q;}map<int,int>mp; // 字符->出现个数int sum = 0;for(const auto x : s){++mp[x];sum += ma[x];}For('a','z'){cout << mp[i];if(i != 'z')cout << ' ';}cout << '\n' << sum;
}signed main(){int _=1;//cin >>_;while(_--)solve_5();
}

L1-110 这不是字符串题

转换为字符串模拟题

字符串操作:

//字符串尾部插入
s.push_back(字符);
//字符串替换
s.replace(被替换子串 首位置的下标, 被替换子串长度 , 替换字符串);
//字符串(子串)翻转
reverse(起始位置下标，结束位置下标-1);//tips:左闭右开区间

对于第二个操作，可以新建一个字符串简化操作

#include <iostream>
#include <cstring>
#include <algorithm>
#define For(a,b) for(int i = (a) ; i <= (b) ; ++i)
using namespace std;
int x;
string s;
int main(){int n,m;cin >> n >> m;while(n --){cin >> x;s.push_back((char)x + 'a' -1); // 转为字符串}int op , l1 ,l2;while(m --){cin >> op;if(op == 1){cin >> l1;string t = "";For(1,l1){cin >> x;t.push_back((char)x + 'a' - 1);}string tt = "";cin >> l2;For(1,l2){cin >> x;tt.push_back((char)x + 'a' - 1);}if(string::npos != s.find(t)){ // 如果找到可替换序列s.replace(s.find(t) , l1 , tt); // 替换该序列}}else if(op == 2){string t = "";For(0,(int)s.size()-2){ // s.size() -> String::size_type / unsignedif((s[i] + s[i+1] - 2*'a' + 2)&1){t.push_back(s[i]); // 如果是奇数 保留原字符}else{t.push_back(s[i]); // 如果是偶数 保留原字符t.push_back((char)(s[i] + s[i+1] - 2*'a' + 2)/2 + 'a' - 1); // 插入新平均数(字符)}}t.push_back(s[s.size()-1]);// 带上最后一个字符s = t;}else{cin >> l1 >> l2;reverse(s.begin() + l1 - 1, s.begin() + l2); // 字符串翻转}}For(0,s.size()-1){cout << (s[i] - 'a' + 1) << " \n"[i == s.size()-1];}return 0;
}

L1-111 大幂数

---

思路 : 从大到小迭代幂次 ; (固定幂次)从 1 开始的连续自然数依次 减去 给出的正整数 $n$ ， 如果最后 $n$ 恰好等于 0 就符合题意 ， 否则该幂次无解(需要继续迭代)

---

注意到 $n\le 2^{31}$

所以 幂次 不会超过 31

因为需要输出幂次最大，所以从31 往 1 迭代

每个幂次判断是否符合条件
这里使用的是dfs判断,当然也可以换成循环

bool dfs(int n , int x , int q){int i = 1;while(n){if( n < pow(i,q))return false;n -= pow(i,q);ansx = i;i++;}return true;
}

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <tuple>
#include <stack>
#include <cmath>
#include <algorithm>
#include <map>#define int long long
#define For(a,b) for(int i=(a) ; i<= (b) ; ++i)
#define endx(x) {cout << (x) << '\n' ; return;}
#define debug(x) {cout << #x << ' ' << (x) << '\n';}
using namespace std;
const int N = 1e5+10;
const int M = 1e3+10;
int n,m,k;int ansx = 0;
bool dfs(int n , int x , int q){ // dfs(剩余数 ， 连续自然数 ， 幂次)if( n == 0){ // 如果剩余数 == 0 表示 符合题意ansx = x - 1;return true;}if( n < pow(x,q))return false; return dfs(n - pow(x,q) , x+1 , q); 
}void solve(){cin >> n;for(int i=31;i>=1;--i){ // 幂次迭代if(dfs(n , 1 , i)){cout << "1^" << i;for(int j=2;j<=ansx;++j){cout << "+" << j << "^" << i;}return ;}}cout << "Impossible for " << n << "."; // 无解
}signed main(){int _=1;//cin >>_;while(_--)solve();
}

L1-112 现代战争

模拟题 ， 类似于 L1-087 机工士姆斯塔迪奥

---

思路：保存坐标和该坐标的值，按照值排序
从大到小遍历值 ， 如果该坐标消失 则不消耗轰炸步数$k$，否则标记该坐标的行和列消失，并且消耗依次轰炸步数

(tip: 行和列 用 数组标记即可)

---

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <tuple>
#include <stack>
#include <cmath>
#include <algorithm>
#include <map>#define int long long
#define For(a,b) for(int i=(a) ; i<= (b) ; ++i)
#define endx(x) {cout << (x) << '\n' ; return;}
#define debug(x) {cout << #x << ' ' << (x) << '\n';}
using namespace std;
const int N = 1e5+10;
const int M = 1e3+10;
int n,m,k,q;
int r,w,z;
int a[M][M];
int line[M]; // 行 / 列标记数组
int row[M]; // 行 / 列标记数组void solve_8(){cin >> n >> m >> k;vector<tuple<int,int,int>>v;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin >> a[i][j];v.push_back({i,j,a[i][j]});}}sort(v.begin(),v.end(),[&](tuple<int,int,int> a,tuple<int,int,int> b){return get<2>(a) > get<2>(b);});for(const auto & x : v){tie(r,w,z) = x;if(row[r])continue;if(line[w])continue;row[r] = true;line[w] = true;k -- ;if(!k)break; // 如果轰炸步数归零则结束}bool ii = false;for(int i=1;i<=n;i++){if(row[i])continue;if(ii)cout << '\n';ii = true;bool jj = true;for(int j=1;j<=m;j++){if(line[j])continue;if(jj)cout << a[i][j];else cout << ' ' << a[i][j];jj = false;}}
}
signed main(){int _=1;//cin >>_;while(_--)solve_8();
}

L2

栈的模拟题

---

如果碰到 ${}^{\prime }{)}^{\prime }$ 就 持续出栈 直到栈顶是 ${}^{\prime }{(}^{\prime }$ ，然后再出栈一次并且输出一行答案即可
否则入栈

---

L2-053 算式拆解

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <tuple>
#include <stack>
#include <cmath>
#include <algorithm>
#include <map>#define int long long
#define For(a,b) for(int i=(a) ; i<= (b) ; ++i)
#define endx(x) {cout << (x) << '\n' ; return;}
#define debug(x) {cout << #x << ' ' << (x) << '\n';}
using namespace std;
const int N = 2e5+10;
const int M = 1e3+10;
int n,m,k;
stack<char>st;
stack<char>ans;
void solve(){string s;cin >> s;for(const auto & x : s){if(!st.empty() && (x == ')')){ // 如果碰到了 ')'while(!st.empty()){if(st.top() == '('){ //持续出栈 直到栈顶是'('st.pop();// 将'(' 出栈break;}ans.push(st.top()); // 先入后出 翻转 答案方便输出st.pop(); }swhile(!ans.empty()){ // 输出答案printf("%c",ans.top());ans.pop();}printf("\n");continue; // ')' 不入栈}st.push(x); // 次序入栈}
}signed main(){int _=1;//cin >>_;while(_--)solve();
}

L2-054 三点共线

---

思路：将同一个$y$坐标的点放入同一个set里面

因为答案是要按照 $y=1$ 的 $x$ 坐标升序 ; 还有相同则按照 $y=0$ 的 $x$ 坐标升序输出。
所以外层循环遍历$y=1$的点，内层循环遍历$y=0$的点，两点确立一条直线，带入$y=2$判断对应$x$坐标是否存在

因为又要去重又要排序，建议使用set ， 但因为$x$ 坐标是绝对值不超过 $10^6$的整数,判断是否存在可以用标志数组防止超时

最后一个点超时思路：当 $y=2$的点过少，需要更换遍历策略，这里是内层循环遍历$y=2$的点，答案经过特殊处理

---

(1). 3 个set 分别存储 $y=0/1/2$ 的 $x$ 坐标, 标记数组mp 分别标记 $y=0/2$ 对应 $x$ 坐标是否存在

(2-1). 如果 $y=2$ 的坐标不存在直接输出 -1 ， 结束

(2-2). 如果 $y=2$ 的坐标过少，外层循环遍历$y=1$的点，内层循环遍历$y=2$的点 , 由于set 从小到大排序 ，两点对应直线是在 $y=0$ 上的 $x$ 坐标从大到小 ， 答案需要逆序处理(这里选择栈) , 数学推导 $\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$,其中$y=0,y_2=2,y_1=1$ ， 所以 $x=2\ast x_1-x_2$ ， 判断该 $x$坐标是否在 $y=0$的标记数组mp0 中存在即可。

(2-3). 否则 外层循环遍历$y=1$的点，内层循环遍历$y=0$的点 , 数学推导 $\frac{x-x_0}{x_1-x_0}=\frac{y-y_0}{y_1-y_0}$,其中$y=2,y_0=0,y_1=1$ ， 所以 $x=2\ast x_1-x_0$ ， 判断该 $x$坐标是否在 $y=2$的标记数组mp 中存在即可。

#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
//#define int long long
using namespace std;
const int N = 2e6+10;
const int NN = 1e6;
set<int>se[4];
bool mp[N];// y = 2 点标识数组
bool mp0[N];// y = 0 点标识数组
bool win ;
signed main(){int n;scanf("%d",&n);int x,y;int min2 = 1e6;int max2 = -1e6;while(n --){scanf("%d %d",&x,&y);if(y == 2){mp[x+NN] |= true;// 标记存在min2 = min(min2 , x);max2 = max(max2 , x);}else if(y == 0)mp0[x + NN] |= true; // 标记存在se[y].insert(x);}if(min2 == 1e6 && max2 == -1e6){ // 如果没有 y = 2 的点 直接输出 -1cout << -1;return 0;}if(se[2].size() < 1e3){int xx0 , xx1 , xx2 ;stack<tuple<int,int,int>>st;for(const int &x1 : se[1]){for(const int &x2 : se[2]){if(x2 == x1 && mp0[x1 + NN]){ // 平行于 y 轴 (垂直的直线)st.push({x1 , x1 , x2});}else if(abs(2*x1 - x2) <= NN  && mp0[2*x1 - x2 + NN]){ // 数学推导st.push({2*x1 - x2 , x1 , x2});}}while(!st.empty()){ // 逆序输出答案win = true;tie(xx0 , xx1 , xx2) = st.top();st.pop();printf("[%d, 0] [%d, 1] [%d, 2]\n", xx0 , xx1 , xx2);}}if(!win)cout << -1;return 0;}for(const int &x1 : se[1]){if(2*x1 - *se[0].begin() < min2 || 2*x1 - *se[0].rbegin() > max2)continue; // 如果遍历的区间都不存在 y = 2的点就跳过for(const int &x0 : se[0]){if(x1 == x0 && mp[x1+NN]){// 平行于 y 轴 (垂直的直线)win = true;printf("[%d, 0] [%d, 1] [%d, 2]\n", x0 , x1 , x1);}else if( abs(2*x1 - x0) <= NN  && mp[2*x1 - x0 + NN]){// 数学推导win = true;printf("[%d, 0] [%d, 1] [%d, 2]\n", x0 , x1 , 2*x1 - x0);}//else if(2*x1 - x0 < min2)break;}}if(!win)cout << -1;return 0;
}

L2-055 胖达的山头

差分题

---

思路：将时间点都统一记录 ， 活跃的起始时间点附加信息op=1 , 终止时间点附加信息op = -1
按照时间点从小到大遍历，sum累加对应op，取最高的sum作为答案即可

类似于坐公交车，上车+1人，下车-1人，时间点排序，记录车内人数最多作为答案即可。

---

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <tuple>
#include <stack>
#include <cmath>
#include <algorithm>
#include <map>#define int long long
#define For(a,b) for(int i=(a) ; i<= (b) ; ++i)
#define endx(x) {cout << (x) << '\n' ; return;}
#define debug(x) {cout << #x << ' ' << (x) << '\n';}
using namespace std;
const int N = 2e5+10;
const int M = 1e3+10;
int n,m,k;
struct st{string s;int op;
}s[N];
void solve(){cin >> n;For(1,n){cin >> s[i].s;s[i].op = 1;cin >> s[n+i].s;s[n+i].op = -1;}sort(s+1,s+2*n+1,[&](struct st a , struct st b){return a.s < b.s;});int ans = 1;int sum = 0;for(const auto & x : s){sum += x.op;ans = max(ans,sum);}cout << ans;
}signed main(){int _=1;//cin >>_;while(_--)solve();
}

L2-056 被n整除的n位数

（数位）dfs题

---

思路：从最高位填写数字，如果填写到目前为止不满足题意退出递归，否则直到填写到对应的 $n$位，判断是否在给定的区间$[a,b]$里面，是则记录答案

---

#include <iostream>
#include <set>
#define int long long
using namespace std;
int a,b,n;
set<int>se;
void dfs(int x , int len){//数字 ， 位数if(x % len != 0)return ; // 题意前 i 位数能被 i 整除if(len == n){ // 位数为 n 位数了if(x <= b && x>= a){ // 在区间内se.insert(x); // 记录答案}return ;}for(int i=0;i<10;++i){ // 0-9 数字依次填写dfs(x*10 + i , len + 1); }
}
signed main(){cin >> n >> a >> b;for(int i=1;i<=9;i++) // 第一位 1 - 9 (单独拿出来去掉 0开头)dfs( i , 1);for(const auto & x : se){cout << x << '\n';}if(se.empty())cout << "No Solution";
}