2022 Robocom世界机器人开发者大赛 CAIP编程赛道 本科组-决赛 挨打记录+题解_2022睿抗机器人开发者大赛caip-编程技能赛初赛题目
赞
踩
2022 Robocom CAIP编程赛道 决赛挨打记录+题解
打完决赛本菜鸡可以退役辣！并不是很开心因为上学期的考试还没复习完，哭了TAT
由于PTA还没有上架题目，只能描述个大概，各位姥爷见谅
u1
给定一串时间序列，表示在什么时刻按了开关。在按下之后的15秒后会变绿灯，持续30秒，如果在持续期间有再次被按下则延长15秒，只能被延长一次，请输出所有的绿灯时间段
这第一题是真的恶心，我写它就写了快半个小时，蚌埠住了
大致思路就是模拟，如果灯没被按就变一下flag，然后维护一下st和ed两个时间段，如果这中间又被按了一下就ed+15这样子
#include<bits/stdc++.h> using namespace std; const int N=1010; int n; int a[N]; int main() { cin>>n; for (int i=1;i<=n;i++) cin>>a[i]; a[n+1]=0x3f3f3f3f; //让最后一个一定大于ed 防止特判 bool flag=false,add=false; //false代表没被按 true代表被按了 int st=0,ed=0; for (int i=1;i<=n+1;i++) { if (!flag) //没被按 { flag=true; st=a[i]+15;ed=a[i]+15+30-1; } else { if (a[i]<st) continue; if (a[i]>ed) { flag=false;add=false; cout<<st<<" "<<ed<<endl; i--;continue; } if (!add) { add=true; ed+=15; } } } return 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
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
u2
给定一个5*5的棋盘，给定一个终点，有四只小怪，分别在棋盘的上下左右四个边界处，处于r1、r2、c1、c2四个行/列，还给定这四只小怪移动的距离，你要做的操作如下：
- 找到一个起始点
- 东西方向的小怪移动他们的距离，然后四只小怪一起攻击，攻击方式为小怪所在的本行/本列
- 你从起始点移动d1距离到第二个点
- 南北方向的小怪移动他们的距离，然后四只小怪一起攻击
- 你从第二个点移动d2距离到终点
要求每次移动到的点都不能被攻击，求合法的位置选择的具体方案
这题也是离了大谱，我看错题看错了两次，第一次以为移动的距离是只能往一个方向移动d1、d2的距离，第二次以为是小怪第一次不动，第二次东西南北一起动…他喵的
这个题可以反着推，从终点开始找，看看哪些点可以从终点走d2步到达，然后判断是否合法，再找哪些点可以从这个点走d1步到达且合法即可
不过问题是像俺这种解法是有可能重复的，由于unique函数不能用在结构体上（可能重载一下运算符可以，但我不会），所以写了个比较笨的去重，我感觉pair嵌套大礼包也是可以写的
#include<bits/stdc++.h> using namespace std; const int N=5; int c1,c2,r1,r2; int a[N]; int edx,edy,d1,d2; struct Node{ int a,b,c,d; friend bool operator<(Node x,Node y) { if (x.a!=y.a) return x.a<y.a; if (x.b!=y.b) return x.b<y.b; if (x.c!=y.c) return x.c<y.c; if (x.d!=y.d) return x.d<y.d; } }; int dx[]={1,1,-1,-1},dy[]={1,-1,1,-1}; bool equal(Node x,Node y) { if (x.a==y.a && x.b==y.b && x.c==y.c && x.d==y.d) return true; return false; } int main() { cin>>c1>>c2>>r1>>r2; for (int i=1;i<=4;i++) cin>>a[i]; cin>>edx>>edy>>d1>>d2; vector<Node> ans; for (int i=0;i<=d2;i++) { int dx1=i,dy1=d2-i; for (int k=0;k<4;k++) { int nx1=edx+dx1*dx[k],ny1=edy+dy1*dy[k]; if (nx1<1 || nx1>5 || ny1<1 || ny1>5) continue; if (nx1==r1-a[3] || nx1==r2+a[4] || ny1==c1+a[1] || ny1==c2-a[2]) continue; for (int j=0;j<=d1;j++) { int dx2=j,dy2=d1-j; for (int l=0;l<4;l++) { int nx2=nx1+dx2*dx[l],ny2=ny1+dy2*dy[l]; if (nx2<1 || nx2>5 || ny2<1 || ny2>5) continue; if (nx2==r1-a[3] || nx2==r2+a[4] || ny2==c1 || ny2==c2) continue; ans.push_back({nx2,ny2,nx1,ny1}); } } } } sort(ans.begin(),ans.end()); for (int i=0;i<ans.size();i++) if (!i || (i && !equal(ans[i],ans[i-1]))) cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<" "<<ans[i].d<<endl; return 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
- 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
u3
给定一个图有n个点，m条边，每条边的长度都为1，然后给定你起点S和终点T，同时给定你是在K个人中的第p个。给定所有点的权值，规定路径上的第1个点分给第1个人，第p个点分给第p个人，第p+1个点分给第1个人…问在保证路径最短的前提下，你最后能获得的最大权值和是多少？
这题乍一看像最短路，结果仔细想了一下重点在边长全为1上，那也就是说对于给定的起点和终点，中间如果存在两条路线可走，那么这两条路线上对应的点到起点的距离一定是相等的，那么这个问题其实就等价成了对于给定的起点和终点，途中第p+n*k(n>=0)中的点的权值之和最大是多少
那我们可以先bfs一遍求出来所有点的距离，然后再bfs一遍求出来价值之和即可
#include<bits/stdc++.h> using namespace std; const int N=100010,M=2*N; int n,m,k,p; int a[N]; int h[N],e[M],ne[M],idx; int S,T; int dist[N],val[N]; bool st[N]; void add(int a,int b) { e[idx]=b;ne[idx]=h[a];h[a]=idx++; } int main() { cin>>n>>m>>k>>p; for (int i=1;i<=n;i++) cin>>a[i]; memset(h,-1,sizeof(h)); while(m--) { int a,b;cin>>a>>b; add(a,b);add(b,a); } cin>>S>>T; memset(dist,0x3f,sizeof(dist)); queue<int> q; q.push(S); st[S]=true;dist[S]=1; while(!q.empty()) { int t=q.front();q.pop(); for (int i=h[t];~i;i=ne[i]) { int j=e[i]; if (dist[j]>dist[t]+1) { dist[j]=dist[t]+1; q.push(j); } } } memset(val,-0x3f,sizeof(val)); memset(st,0,sizeof(st)); q.push(S); st[S]=true;val[S]=0; while(!q.empty()) { int t=q.front();q.pop(); if (dist[t]>=p && (dist[t]-p)%k==0) { val[t]+=a[t]; } if (t==T) break; if (dist[t]>=dist[T]) continue; for (int i=h[t];~i;i=ne[i]) { int j=e[i]; if (dist[j]>dist[t] && val[j]<val[t]) val[j]=val[t]; if (!st[j]) { st[j]=true; q.push(j); } } } cout<<val[T]; return 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
- 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
需要注意的是，第二遍bfs我们一定要用dist[t]小于dist[T]的点去更新，因为其实是有可能出现dist[t]==dist[T]，但是它先进入队列，并且和T有一条边，就把T的结果给更新了，然而这种是不合法的，因为这两个点距离相等，且和终点之间有一条边，那么从它走到T一定不是最短路径了
从下面的题开始我就开始瞎写了
u4
题目大意是给定两个数组，问你最少需要多少步操作可以把数组一变成数组二，并且要求给出对第一个数组的操作：
- 如果当前数字不变，输出2
- 如果当前数字被删除，输出0
- 如果当前数字前或后被添加了一个数字，输出3
- 如果当前数字被改变，输出1
没什么好说，照着编辑距离瞎写的，结束2分钟交了一发举然骗到了17分，绝了
这题听说只管操作1和2打暴力能拿20分，tm比我凹了半天的解得分还高，我是真的会谢
#include<bits/stdc++.h> using namespace std; const int N=1010; int a[N],b[N]; int lena,lenb; int f[N][N]; string ans[N][N]; int main() { int t=0; while(t!=-1) { cin>>t; a[++lena]=t; } t=0; while(t!=-1) { cin>>t; b[++lenb]=t; } memset(f,0x3f,sizeof(f)); for (int i=0;i<=lena;i++) { f[i][0]=i; if (!i) ans[i][0]=""; else ans[i][0]=ans[i-1][0]+"3"; } for (int i=0;i<=lenb;i++) { f[0][i]=i; if (!i) ans[0][i]=""; else ans[0][i]=ans[0][i-1]+"3"; } for (int i=1;i<=lena;i++) for (int j=1;j<=lenb;j++) { f[i][j]=min(f[i][j],f[i-1][j]+1); if (a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]); else f[i][j]=min(f[i][j],f[i-1][j-1]+1); if (f[i][j]==f[i-1][j]+1) { if (i>j) ans[i][j]=ans[i-1][j]+"0"; else ans[i][j]=ans[i-1][j]+"3"; } else if (f[i][j]==f[i-1][j-1]) { ans[i][j]=ans[i-1][j-1]+"2"; } else if (f[i][j]==f[i-1][j-1]+1) { ans[i][j]=ans[i-1][j-1]+"1"; } } cout<<f[lena][lenb]<<endl; cout<<ans[lena][lenb]; return 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
- 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
u5
给定一棵树，和所有点的种类，问你有多少个三元组，这三个点之间的最短距离两两相同，且这三个点的种类都不同
没什么好说，一点思路都没有，floyd嗯跑拿了17分，结束前20分钟的时候在想是不是可以floyd换bfs，后来一想后面枚举的部分不会优化，那总的时间复杂度还是O(n^3)，没区别啊
结果赛后有人告诉我floyd换bfs直接拿满了，我当场怀疑人生
#include<bits/stdc++.h> using namespace std; const int N=2010; typedef pair<int,pair<int,int>> PIII; int n; int g[N][N]; int t[N]; int main() { cin>>n; memset(g,0x3f,sizeof(g)); for (int i=1;i<=n-1;i++) { int a,b;cin>>a>>b; g[a][b]=g[b][a]=1; } for (int i=1;i<=n;i++) cin>>t[i]; for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); vector<PIII> ans; for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) for (int k=j+1;k<=n;k++) { if (g[i][j]==g[j][k] && g[i][j]==g[i][k]) { if (t[i]!=t[j] && t[i]!=t[k] && t[j]!=t[k]) { ans.push_back({i,{j,k}}); } } } cout<<ans.size(); return 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
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
总结
总的来说还算凑合，因为只需要有分就能拿奖，打得很放松，最后交的一发也送我拿了国一（应该吧？），94分摸了
