GPLT-2025年第十届团体程序设计天梯赛总决赛题解(共计266分)

今天偶然发现天梯赛的代码还保存着，于是决定写下这篇题解，也算是复盘一下了

L1本来是打算写的稳妥点，最后在L1-6又想省时间，又忘记了insert，replace这些方法怎么用，也不想花时间写一个文件测试，最后用了两个vector<int>a,b每次操作来回传数组的元素，以为实现起来很方便，最后反而写了个170行的屎山代码，花了一个多小时的时间debug最后还只拿了5分，属于是左右脑互博了...

L2的话，L2-2写着写着把无解-1忘了？L2-4少了一些边界条件

L3 最后15分钟发现L3-3很多人拿了16分，于是火急火燎写了一个暴力，怒拿1分，赛后看代码才发现把同一种情况下的乘法写成加法了

欲速则不达，以后做事还是慢慢来，先把基础打扎实。接下来要准备考研了，就当这是个提醒吧。

L1-105 珍惜生命

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int n,m,k;
const int N=1e6+10;
void solve()
{cout<<"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.";
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L1-106 偷感好重

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int n,m,k;
const int N=1e6+10;
void solve()
{cin>>n>>m>>k;cout<<n+m+k<<'\n';
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L1-107 高温补贴

按照题意模拟

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int n,m,k;
const int N=1e6+10;
void solve()
{int t,s,t1;cin>>t>>s>>t1;if(t>=35&&s&&t1>=33)cout<<"Bu Tie\n"<<t;else if(t>=35&&!s&&t1>=33)cout<<"Shi Nei\n"<<t;else if(s)cout<<"Bu Re\n"<<t1;else cout<<"Shu Shi\n"<<t1;
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L1-108 零头就抹了吧

找到2^i中第一个大于付的钱的i，然后输出2^(i-1)

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
void solve()
{cin>>n;int i=0;while((1<<i)<=n){i++;}cout<<(1<<(i-1));
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L1-109 这是字符串题

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10;
int a[N],b[N];
void solve()
{string s;cin>>s;_rep(i,0,25){cin>>a[i];}int res=0;for(auto i:s){res+=a[i-'a'];b[i-'a']++;}_rep(i,0,25){cout<<b[i]<<" \n"[i==25];}cout<<res<<endl;
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L1-110 这不是字符串题

用一个自增的cnt和vector<int>a,b,cnt为奇数就把a的东西存到b去，反之

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10;
vector<int>a,b;
int cnt;
void solve()
{cin>>n>>m;_rep(i,1,n){int x;cin>>x;a.pb(x);}while(m--){cnt++;int op;cin>>op;if(op==1){int l1,l2;cin>>l1;vector<int>c;while(l1--){int x;cin>>x;c.pb(x);}cin>>l2;vector<int>d;while(l2--){int x;cin>>x;d.pb(x);}int idx=-1;if(cnt&1){for(int i=0;i<(int)a.size();i++){if(i+(int)c.size()>(int)a.size())break;bool bl=true;for(int j=0,k=i;j<(int)c.size();j++,k++){if(c[j]!=a[k]){bl=false;break;}}if(bl){idx=i;break;}}}else{for(int i=0;i<(int)b.size();i++){if(i+(int)c.size()>(int)b.size())break;bool bl=true;for(int j=0,k=i;j<(int)c.size();j++,k++){if(c[j]!=b[k]){bl=false;break;}}if(bl){idx=i;break;}}}if(idx!=-1){if(cnt&1){bool bl=false;for(int i=0;i<(int)a.size();i++){if(idx<=i&&i<=idx+((int)c.size())-1){if(!bl){for(auto k:d){b.pb(k);}bl=true;}}else b.pb(a[i]);}a.clear();}else {bool bl=false;for(int i=0;i<(int)b.size();i++){if(idx<=i&&i<=idx+((int)c.size())-1){if(!bl){for(auto k:d){a.pb(k);}bl=true;}}else a.pb(b[i]);}b.clear();}}else cnt++;}else if(op==2){if(cnt&1){for(int i=0;i<(int)a.size();i++){if(!i)b.pb(a[i]);else {if((a[i]+a[i-1])%2==0){b.pb((a[i]+a[i-1])/2);}b.pb(a[i]);}}a.clear();}else {for(int i=0;i<(int)b.size();i++){if(!i)a.pb(b[i]);else {if((b[i]+b[i-1])%2==0){a.pb((b[i]+b[i-1])/2);}a.pb(b[i]);}}b.clear();}}else {int l,r;cin>>l>>r;l--,r--;if(cnt&1){for(int i=0;i<(int)a.size();i++){if(l<=i&&i<=r){b.pb(a[l+r-i]);}else b.pb(a[i]);}a.clear();}else{for(int i=0;i<(int)b.size();i++){if(l<=i&&i<=r){a.pb(b[l+r-i]);}else a.pb(b[i]);}b.clear();}}}if(cnt%2==0){for(int i=0;i<(int)a.size();i++){cout<<a[i]<<" \n"[i==(int)a.size()-1];}}else {for(int i=0;i<(int)b.size();i++){cout<<b[i]<<" \n"[i==(int)b.size()-1];}}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L1-111 大幂数

可以发现指数k（我的代码中是m）最大从31开始向下递减，每次暴力判断的时间复杂度是根号级别的，所以直接枚举指数然后判断即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10;
int qmi(int a,int b){int res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;
}
vector<int>a,b;
int cnt;
int check(int k,int sum){int s=0;for(int i=1;;i++){s+=qmi(i,k);if(s==sum)return i;if(s>sum)return -1; }
}
void solve()
{cin>>n;int m=31;bool bl=false;while(m!=0){int t=check(m,n);if(t!=-1){_rep(i,1,t){cout<<i<<"^"<<m<<"+\n"[i==t];}bl=true;break;}m--;}if(!bl)cout<<"Impossible for "<<n<<".";
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L1-112 现代战争

用一个优先队列每次弹出最大值，然后弹出过后的话就把坐标的行列标记为使用过，于是每一轮弹出坐标，直到那个弹出的坐标的行列没有被使用过，那个坐标就是这一轮要被删除的坐标

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10;
int g[1010][1010];
bool st[1010][1010];
struct aa{int i,j,w;
};
struct cmp{bool operator()(aa a,aa b){return a.w<b.w;}
};
void solve()
{int n,m,k;cin>>n>>m>>k;priority_queue<aa,vector<aa>,cmp>p;_rep(i,1,n){_rep(j,1,m){int x;cin>>x;g[i][j]=x;p.push({i,j,x});}}while(k--){auto t=p.top();while(1){p.pop();if(!st[t.i][t.j])break;t=p.top();}for(int j=1;j<=n;j++){st[j][t.j]=true;}for(int j=1;j<=m;j++){st[t.i][j]=true;}}for(int i=1;i<=n;i++){bool bl=false;for(int j=1;j<=m;j++){if(st[i][j])continue;if(bl)cout<<" ";bl=true;cout<<g[i][j];}if(bl)cout<<'\n';}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L2-053 算式拆解

一个栈储存碰到的所有字母，遇到')'就一直弹出直到遇到‘(’,在这途中弹出的字符就是这一行的算式

#include<bits/stdc++.h>
using namespace std;
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10;
void solve()
{string s;cin>>s;vector<char>v;for(auto i:s){if(i==')'){vector<char>now;while(v.back()!='('){now.pb(v.back());v.pp;}v.pp;reverse(all(now));for(int i=0;i<(int)now.size();i++){cout<<now[i];}cout<<'\n';}else v.pb(i);}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L2-054 三点共线

枚举前两维(y=0,1)，判断第三维(y=2),把y=2时的x存到数组里，不过要注意存的时候防止出现负数，最坏情况下，第一维1e6,第二维-1e6,为了防止负数所以第三维要整体+3e6

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define double long double
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define laile	cout<<"laile"<<endl;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10,INF=4e18;
vector<int>q[4];
bool st[4][N];
struct aa{int a,b,c;
};
bool cmp(aa a,aa b){if(a.b!=b.b)return a.b<b.b;return a.a<b.a;
}
vector<aa>res;
int has[6000001];
void solve()
{cin>>n;_rep(i,1,n){int x,y;cin>>x>>y;y++;if(y==3)has[x+3000010]++;else q[y].pb(x);}if(q[1].size())sort(all(q[1]));if(q[2].size())sort(all(q[2]));for(int i=0;i<(int)q[1].size();i++){int pre=0;if(i&&q[1][i]==q[1][i-1])continue;for(int j=0;j<(int)q[2].size();j++){if(j&&q[2][j]==q[2][j-1])continue;int sub=q[2][j]-q[1][i];if(has[q[2][j]+sub+3000010])res.pb({q[1][i],q[1][i]+sub,q[1][i]+2*sub});}}aa pre={-INF,-INF,-INF};sort(all(res),cmp);if(!res.size())cout<<"-1\n";else{for(auto i:res){if(pre.a!=i.a||pre.b!=i.b||pre.c!=i.c){cout<<"["<<i.a<<", 0] ["<<i.b<<", 1] ["<<i.c<<", 2]\n";}pre=i;}}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L2-055 胖达的山头

最小区间覆盖问题​

先给区间排序,用multset存每个区间的右端点,每次找到multset中第一个大于当前区间左端点的点，然后把这个点替换成这个新的点，如果没找到就直接插入这个区间的右端点，最后multiset的元素个数就是最终答案

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define double long double
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define laile	cout<<"laile"<<endl;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10,INF=4e18;
struct aa{int i,j,w;
};
struct cmp{bool operator()(aa a,aa b){return a.w<b.w;}
};
vector<PII>v;
PII get(string &s){int a=0,b=0,now=0;for(auto i:s){if(isdigit(i)){now=now*10+i-'0';}else if(i==' '){a=now;now=0;}}return {a,now};
}
void solve()
{cin>>n;string s;getline(cin,s);while(n--){getline(cin,s);PII t=get(s);v.pb(t);}sort(all(v));multiset<int>now;for(auto i:v){if(!now.size()){now.insert(i.se);}else{int ma=0,maidx;bool bl=false;auto t=now.lower_bound(i.fi);if(t==now.begin()){now.insert(i.se);}else{t--;int tt=i.se;now.erase(t);now.insert(tt);}}}cout<<now.size()<<'\n';
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L2-056 被n整除的n位数

可以发现满足前i位被i整除的数字其实并不多，那么这题实际上就是直接暴力，这里我用的方法是逐位递增，用vector<int>v[16]存前i位满足在区间内部的所有数字，比如a=34567，b=66666，

首先v[1]显然可以存[3，4，5，6]，

然后v[2]利用v[1]的值，遍历0~9，相当于枚举了30,31,32,33....40,41,....,68,69这些数字

然后用被 i 整除这个条件可以筛掉大部分数字，然后合法的又存到v[2]里，以此类推

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long 
#define double long double
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define laile	cout<<"laile"<<endl;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10,INF=4e18;
int qmi(int a,int b){int res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;
}
struct aa{int i,j,w;
};
struct cmp{bool operator()(aa a,aa b){return a.w<b.w;}
};
int get(int x){if(x==0)return 1;int res=0;while(x){x/=10;res++;}return res;
}
bool check(int x){if(get(x)!=n)return false;vector<int>now;while(x){now.pb(x%10);x/=10;}reverse(all(now));int cnt=0,sum=0;for(auto i:now){sum=sum*10+i;cnt++;if(sum%cnt!=0)return false;}return true;
}
vector<int>v[20];
int la[20],lb[20];
int nine(int x){int res=9;_rep(i,1,x-1){res=res*10+9;}return res;
}
void solve()
{int a,b;cin>>n>>a>>b;bool bl=false;if(get(a)<n){int t=1;_rep(i,1,n-1){t*=10;}a=t;}else if(get(a)>n){cout<<"No Solution";return;}if(get(b)>n){int t=9;_rep(i,1,n-1){t=t*10+9;}b=t;}else if(get(b)<n){cout<<"No Solution";return;}vector<int>aa,bb;int c=a;while(c){aa.pb(c%10);c/=10;}reverse(all(aa));c=b;while(c){bb.pb(c%10);c/=10;}reverse(all(bb));for(int i=1;i<=n;i++){la[i]=la[i-1]*10+aa[i-1];lb[i]=lb[i-1]*10+bb[i-1];}_rep(i,0,9){v[1].pb(i);}_rep(i,2,n){_rep(k,0,9){for(auto j:v[i-1]){int t=((j*10)+k);if(t%i==0&&t>=la[i]&&t<=lb[i]){v[i].pb(t);}}}}vector<int>res;for(auto i:v[n]){if(check(i)){res.pb(i);bl=true;}}sort(all(res));if(!bl)cout<<"No Solution";else{res.erase(unique(all(res)),res.end());for(int i=0;i<(int)res.size();i++){cout<<res[i]<<'\n';}}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L3-040 人生就像一场旅行

类似最短路计数的思想

可以更新旅费（新路线旅费>原路线旅费）更新旅费和心情

否则如果新路线旅费=原路线旅费，更新心情更大的那条

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define laile	cout<<"laile"<<endl;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10,INF=4e18;
int qmi(int a,int b){int res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;
}
int sum;
int g[510][510];
int happy[510][510];
int dist[510][510];
void solve()
{cin>>sum>>n>>m>>k;memset(g,0x3f,sizeof(g));_rep(i,1,n){g[i][i]=0;}_rep(i,1,m){int a,b,w,h;cin>>a>>b>>w>>h;g[a][b]=g[b][a]=w;happy[a][b]=happy[b][a]=h;}_rep(k,1,n){_rep(i,1,n){_rep(j,1,n){if(g[i][k]+g[k][j]<g[i][j]){g[i][j]=g[i][k]+g[k][j];happy[i][j]=happy[i][k]+happy[k][j];}else if(g[i][k]+g[k][j]==g[i][j])happy[i][j]=max(happy[i][k]+happy[k][j],happy[i][j]);}}}_rep(i,1,k){int x;cin>>x;vector<int>a,b;int ma=0;_rep(j,1,n){if(x==j)continue;if(g[x][j]<=sum){a.pb(j);if(happy[x][j]>ma){ma=happy[x][j];b.clear();b.pb(j);}else if(happy[x][j]==ma){b.pb(j);}}}if(!a.size()){cout<<"T_T\n";}else {sort(all(a));sort(all(b));for(int i=0;i<(int)a.size();i++){cout<<a[i]<<" \n"[i==(int)a.size()-1];}for(int i=0;i<(int)b.size();i++){cout<<b[i]<<" \n"[i==(int)b.size()-1];}}}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L3-041 影响力

按题意暴力20分

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define laile	cout<<"laile"<<endl;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10,INF=4e18;
vector<vector<int>>v(N);
void solve()
{cin>>n>>m;_rep(i,1,n){v[i].pb(0);_rep(j,1,m){int x;cin>>x;v[i].pb(x);}}_rep(i,1,n){_rep(j,1,m){int res=0;_rep(k,1,n){_rep(l,1,m){res+=v[i][j]*max(abs(k-i),abs(l-j));}}cout<<res<<" \n"[j==m];}}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}

L3-042 污染大亨

暴力dfs16分

有一个细节，dfs的时候会遍历到不同的游戏情况，在回溯完之后为了确定某个小镇是否被污染，判断污染的st数组可以直接开int型，每一次被污染就st[u]++,回溯就st[u]--,这样可以保证st[u]=0时走到这个分支时小镇从未被污染

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long 
#define double long double
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10,INF=4e18,P=998244353;
vector<vector<int>>v(N);
int c[N];
int st[N];
int sum;
int qmi(int a,int b,int P){int res=1;while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}return res;
}
void infact(int u){sum++;st[u]++;for(auto i:v[u]){infact(i);}return;
}
void finfact(int u){st[u]--;for(auto i:v[u]){finfact(i);}return;
}
int res=0;
void dfs(int u,vector<int>&ve,int now){bool bl=false;_rep(i,1,n){if(st[i])continue;bl=true;sum=0;infact(i);dfs(u+1,ve,now*qmi(c[u],sum,P)%P);finfact(i);}if(!bl)res+=now,res%=P;
}
void solve()
{cin>>n;if(n==1){cout<<n<<'\n';}else {_rep(i,2,n){int x;cin>>x;v[x].pb(i);}_rep(i,1,n)cin>>c[i];vector<int>ve;dfs(1,ve,1);cout<<res;}
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}