2024年GPLT团体程序设计竞赛题解(无L3-3)

本文主要是介绍2024年GPLT团体程序设计竞赛题解(无L3-3)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

L1-1 编程解决一切

略~~~

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
const int N = 1e4+10;void solve(){cout<<"Problem? The Solution: Programming.";}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L1-2 再进去几个人

观察样例，再结合一下题意，看以得出答案为出去的人数减去进去的人数

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long longvoid solve(){int a,b;cin>>a>>b;cout<<b-a;
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L1-3 帮助色盲

按照题意模拟即可，赛时第一个点死活过不去，现在发现打错字母了〒▽〒

把"biii"写成了"bill"，痛失3分！没想到色盲竟是我自己？

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
//当前交通灯为红灯或绿灯时，检测其前方两米内是否有同向行走的人 —— 如果有
///如果没有，则根据灯的颜色给出不同的提示音。黄灯也不需要给出提示。void solve(){int a,b; cin>>a>>b;if(a==0){if(b==0){cout<<"biii"<<endl; //???cout<<"stop";}else{cout<<"-"<<endl;cout<<"stop";}}else if(a==1){if(b==0){cout<<"dudu"<<endl;cout<<"move";}else{cout<<"-"<<endl;cout<<"move";}}else{cout<<"-"<<endl;cout<<"stop";}}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L1-4 四项全能

刚开始理解错题了，其实只需要算出总数，减去会m-1项的人数，剩下的即为至少会m项的人数。

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long longvoid solve(){int n,m; cin>>n>>m;vector<int> a(m+1);int sum=0;for(int i=1;i<=m;i++){cin>>a[i]; sum+=a[i];}sum-=(m-1)*n;cout<<max(0*1LL,sum);
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L1-5 别再来这么多猫娘了！

有两个测试点含有替换词的字串，这点没想到。。。

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
const int N = 1e5+10;
int n;
string s[N],tar="<censored>";void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>s[i];int k; cin>>k; getchar();string str; getline(cin,str);int cnt=0;for(int i=1;i<=n;i++){while(str.find(s[i])!=str.npos){ int pos=str.find(s[i]); //找到违禁词 cnt++;str.erase(pos,s[i].size());str.insert(pos,"***"); //替换 }}if(cnt>=k){cout<<cnt<<endl<<"He Xie Ni Quan Jia!";}else{while(str.find("***")!=-1){int pos=str.find("***");str.erase(pos,3);str.insert(pos,"<censored>");}cout<<str;}
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L1-6 兰州牛肉面

用一个数组记录每种牛肉面卖出多少碗

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long longvoid solve(){int n; cin>>n;vector<double> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];double sum=0;vector<int> cnt(n+1);int x,y;while(cin>>x>>y,x){cnt[x]+=y;sum+=a[x]*y;}for(int i=1;i<=n;i++) cout<<cnt[i]<<endl;printf("%.2f",sum);
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L1-7 整数的持续性

按照题意写就行，判断每个数的持续性

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
const int N = 1e5+10;
unordered_map<int,bool> vis;
vector<int> ans;
int maxn=0;void solve(){int a,b; cin>>a>>b;for(int i=a;i<=b;i++){if(vis[i]) continue;vis[i]=1;int cnt=0;vector<int> tmp;int k=i;while(k>=10){int x=k,sum=1;while(x){sum*=x%10;x/=10;}k=sum; cnt++;vis[k]=1;}if(cnt>maxn){ //更新答案 ans.clear();maxn=cnt;ans.push_back(i);}else if(cnt==maxn){ans.push_back(i);}}cout<<maxn<<endl;int flag=0;for(auto i:ans){if(flag) cout<<' ';cout<<i;flag++;}
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L1-8 九宫格

题目有句话是这道题的关键点**“要求 1 到 9 这九个数字中的每个数字在每一行、每一列、每个宫位中都只能出现一次”**

也就是说需要判断三个条件：

在本行中该数字出现一次
在本列中该数字出现一次
在这个宫位该数字出现一次

当然这些数字的的范围在1—9.

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
const int N = 1e4+10;
int a[10][10];
bool flag=true;void solve(){flag=true;for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)cin>>a[i][j];for(int t=1;t<=9;t+=3){ //我们需要把这个9x9的矩阵分割成9个正方形宫位for(int p=1;p<=9;p+=3){set<int> s; //看是不是9个不同的数字//判断该宫位for(int i=t;i<=t+3-1;i++){for(int j=p;j<=p+3-1;j++){if(a[i][j]<=0||a[i][j]>9) flag=false;//数字越界了for(int k=1;k<=9;k++){if(a[i][j]==a[i][k]&&j!=k) flag=false;if(a[i][j]==a[k][j]&&i!=k) flag=false;}s.insert(a[i][j]);} }if(s.size()!=9) flag=false; }}if(flag) cout<<1<<endl;else cout<<0<<endl;}signed main(){int T=1;cin>>T;
//	IOS;while(T--){solve();} return 0;
}

至此L1结束！时间大约用了1小时10几分钟。比自己规定的1小时，多了10来分钟。。。

感觉L2应该简单些，事实正是如此！

L2-1 鱼与熊掌

题意很好理解，但是一看范围n,m都是1e5，暴力应该会超时的

所以我先把回答存起来，离线处理！

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
const int N = 1e5+10;
set<int> s[N];
int n,m;
vector<pair<int,int>> q;
int ans[N];void solve(){cin>>n>>m;for(int i=1;i<=n;i++){int k; cin>>k;for(int j=1;j<=k;j++){int x; cin>>x;s[i].insert(x);}}int k; cin>>k;for(int i=1;i<=k;i++){int l,r; cin>>l>>r;q.push_back({l,r});}for(int i=1;i<=n;i++){for(int j=0;j<k;j++){int l=q[j].fi,r=q[j].se;if(s[i].count(l)&&s[i].count(r)) ans[j+1]++;}}for(int i=1;i<=k;i++) cout<<ans[i]<<endl;
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L2-2 懂蛇语

一个简单的STL应用,题意很清楚

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
const int N = 1e4+10;
int n,m;
map<string,vector<string>> mp;void solve(){cin>>n; getchar();for(int i=1;i<=n;i++){string s,s1,str=""; getline(cin,s);s1=s; s=" "+s;for(int j=1;j<s.size();j++){//分离出单词首字母 if(s[j-1]==' '&&s[j]!=' ') str.push_back(s[j]);}mp[str].push_back(s1);}cin>>m; getchar();for(int i=1;i<=m;i++){string s,s1,str=""; getline(cin,s);s1=s; s=" "+s;for(int j=1;j<s.size();j++){//分离出单词首字母 if(s[j-1]==' '&&s[j]!=' ') str.push_back(s[j]);}if(!mp.count(str)) cout<<s1<<endl;else{int flag=0;vector<string> tmp;for(auto i:mp[str]){tmp.push_back(i);}sort(tmp.begin(),tmp.end());for(auto i:tmp){if(flag) cout<<'|';cout<<i; flag++;}cout<<endl;}}}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L2-3 满树的遍历

树的存储的题，非常基础

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
const int N = 1e5+10;
vector<int> tr[N];
int n,root;
int vis[N],flag=1,maxn; 
int f=0;
void dfs(int u){if(f) cout<<' ';cout<<u; f++;for(auto v:tr[u]){dfs(v);}
}void solve(){cin>>n;for(int i=1;i<=n;i++){int fa; cin>>fa;if(!fa){root=i;continue;}tr[fa].push_back(i);}for(int i=1;i<=n;i++){maxn=max(maxn,(int)tr[i].size());sort(tr[i].begin(),tr[i].end());}for(int i=1;i<=n;i++){if(tr[i].size()&&tr[i].size()!=maxn) flag=false;}cout<<maxn<<' ';if(flag) cout<<"yes"<<endl;else cout<<"no"<<endl;dfs(root);
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L2-4 吉利矩阵

想了10来分钟，是一道dfs的题加上剪枝应该能过，但是写道一半发现没什么思路，然后开L3了

https://www.cnblogs.com/cuijunjie18/p/18149439

这位大佬写的不错，思路非常清晰！

至此L2结束，此时总分166，此时时间剩余1小时不足10分钟，以为175稳了，甚至有机会拿个银…

开L3，第一题一看是个bfs的板题，以为能守铜摄银？但是写了半个多小时发现写不下去了，应该是思路错了，最后赶紧输出特殊样例，骗了3分，此时分数169，离175还差6分，时间还有半个多小时！

现在真正的慌了，赶紧回到L1看了那几道丢分的题，发现加起来足够6分了，看看第一道丢分的题红绿灯那个，发现找不到哪错了…能找到才怪 (￣▽￣)“赛后发现打错字了。。。把"biii” 写成了"bill" 犯了这种低级错误，痛失3分。然后发现剩下的两道丢分的题也找不到错误…

然后写了L3的第二道，此时只有20分钟左右，抱着不拿奖的心态做了，最后贪心加双指针骗了21分，最终分数190！

L3-1 夺宝大赛

从大本营出发找到所有点的最短路，也就是本题的最短时间
然后看看每个队伍与其它队伍到达时间是否相同，相同就会发生火并。都不同就更新答案。
然后…就没然后了，思路就是这么简单，痛失30分〒▽〒

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
const int N = 1e3+10, INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
//最先到达大本营并能活着夺宝的队伍获得胜利
int m,n,k;
int dist[N][N]; //大本营到参赛队的最短距离 
int g[N][N],sx,sy;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
vector<PII> arr; 
struct node{int x,y,step;
};
bool vis[N][N];void bfs(){memset(dist,INF,sizeof(dist));dist[sx][sy]=0;queue<node> q;q.push({sx,sy,0});vis[sx][sy]=1;while(q.size()){auto t=q.front(); q.pop();for(int i=0;i<4;i++){int tx=t.x+dx[i];int ty=t.y+dy[i];if(tx<1||ty<1||tx>m||ty>n) continue;if(vis[tx][ty]||g[tx][ty]==0) continue;vis[tx][ty]=1;q.push({tx,ty,t.step+1});dist[tx][ty]=t.step+1;}}
}void solve(){cin>>m>>n;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>g[i][j];if(g[i][j]==2) sx=i,sy=j; //大本营 }} bfs();cin>>k;for(int i=0;i<k;i++){int x,y; cin>>y>>x;arr.push_back({x,y});} int id=-1,res=INF;for(int i=0;i<k;i++){int flag=1,now=dist[arr[i].fi][arr[i].se];for(int j=0;j<k;j++){if(i==j) continue;if(dist[arr[i].fi][arr[i].se]==dist[arr[j].fi][arr[j].se]) flag=0;}if(flag&&dist[arr[i].fi][arr[i].se]<res){res=dist[arr[i].fi][arr[i].se];id=i+1;}}if(id!=-1) cout<<id<<' '<<res;else cout<<"No winner.";
}signed main(){int T=1;
//	cin>>T;
//	IOS;while(T--){solve();} return 0;
}

L3-2 工业园区建设

贪心加双指针骗分，有两个点超时，21分

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
const int N = 1e4+10;void solve(){int n,m,k;cin>>n>>m>>k;string s; cin>>s;s=" "+s;vector<int> a(n+1);int flag=0;for(int i=1;i<=n;i++){int l=i-1,r=i+1,cnt=0,sum=0,t=m;if(s[i]=='1') cnt++;else if(t>0){t--; cnt++;}while(l>0||r<=n){if(cnt==k) break;if(l>0&&s[l]=='1') cnt++,sum+=(i-l);else if(t>0&&l>0){t--; cnt++; sum+=(i-l);}if(cnt==k) break;if(r<=n&&s[r]=='1') cnt++,sum+=(r-i); else if(t>0&&r<=n){t--; cnt++; sum+=(r-i);}if(cnt==k) break;l--,r++;}if(flag) cout<<' ';cout<<sum; flag++;}cout<<endl;
}signed main(){int T=1;cin>>T;
//	IOS;while(T--){solve();} return 0;
}