2024年睿抗机器人开发者大赛CAIP-编程技能赛（省赛）
·
一、RC-u1 热҈热҈热҈
输入样例：
15 3
33 35 34 36 37 40 32 31 30 29 28 29 33 38 40
输出样例：
5 1
1.1 解题思路：
循环依次遍历当前天的温度是否大于等于35（再判断是否为星期四），同时更新星期几
1.2代码示例：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,day;
cin>>n>>day;
int a=0,b=0;
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
if(temp>=35){
if(day==4)b++;
else a++;
}
day++;
if(day==8)day=1;
}
cout<<a<<" "<<b;
}
二、RC-u2 谁进线下了？
输入样例：
3
6 2
7 3
11 5
10 1
2 9
5 8
14 3
4 3
1 6
18 1
12 1
20 0
13 0
3 2
16 4
8 1
19 0
9 4
17 1
15 0
8 2
19 1
12 2
1 9
10 1
7 5
18 0
14 0
5 2
4 4
2 5
6 2
16 3
13 1
20 0
3 7
9 3
15 0
17 5
11 3
18 0
5 2
2 9
9 4
4 7
10 3
16 0
1 6
20 0
15 1
6 0
3 6
14 3
7 4
19 0
17 0
8 9
11 0
13 5
12 0
输出样例：
1 9
2 13
3 27
4 30
5 33
6 25
7 4
8 27
9 24
10 12
11 19
12 18
13 8
14 18
15 4
16 17
17 16
18 8
19 12
20 6
2.1 解题思路：
模拟，依次循环20场比赛，根据相应队伍的名次给出分数
d2.2代码示例：
#include<bits/stdc++.h>
using namespace std;
int a[21];
int main()
{
int n;
cin>>n;
while(n--)
{
for(int i=1;i<=20;i++)
{
int p,k;
cin>>p>>k;
if(p==1){
a[i]+=12;
}
else if(p==2){
a[i]+=9;
}
else if(p==3){
a[i]+=7;
}
else if(p==4){
a[i]+=5;
}
else if(p==5){
a[i]+=4;
}
else if(p<=7){
a[i]+=3;
}
else if(p<=10){
a[i]+=2;
}
else if(p<=15){
a[i]+=1;
}
a[i]+=k;
}
}
for(int i=1;i<=20;i++)cout<<i<<" "<<a[i]<<endl;
}
三、RC-u3 点格棋
输入样例：
6 8
wm....mw
.w..ww..
..wm.wwm
w.w....w
.m.c.m..
w.....w.
输出样例：
2 7
3 5
4 6
4 7
3.1 解题思路：
首先，我们要明确一点，可能的火炉一点出现在“.”（空格）上。
1.我们首先要把身边有火炉的暖海豚去掉，留下那些身边没有火炉，但自己是暖海豚的海豚，这些海豚附近的空格上肯定会有“隐藏”的火炉。
2.然后我们把冷海豚找到，因为他的身边一定没有火炉，把他身边的空格位置给去掉。
3.最后遍历每一个空格位置，判断他的身边是否有暖海豚，如果有的话，则该地方为火炉。（也可以去遍历每一个剩余的暖海豚（步骤一中去除了身边有火炉的暖海豚），遍历它的八个方向，是否有空格，如果有，则为火炉）
3.2代码示例：
#include<bits/stdc++.h>
using namespace std;
//八个方向
int x[8]={-1,-1,0,1,1,1,0,-1};
int y[8]={0,1,1,1,0,-1,-1,-1};
int main()
{
int n,m;
cin>>n>>m;
char a[n+1][m+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)cin>>a[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//有火炉身边的暖海豚全部变成空格，剩下来的暖海豚周围有我们找的火炉
if(a[i][j]=='m')
{
for(int k=0;k<8;k++)
{
int newx=i+x[k];
int newy=j+y[k];
if(!(newx>=1&&newx<=n&&newy>=1&&newy<=m))continue;
if(a[newx][newy]=='w')a[newx][newy]=' ';
}
a[i][j]=' ';
}
//冷海豚周围没有火炉
if(a[i][j]=='c')
{
for(int k=0;k<8;k++)
{
int newx=i+x[k];
int newy=j+y[k];
if(!(newx>=1&&newx<=n&&newy>=1&&newy<=m))continue;
if(a[newx][newy]=='.')a[newx][newy]=' ';
}
}
}
}
int sign=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//火炉只可能出现在.上
//如果该.附近八个方向还有暖海豚，说明可能有火炉
if(a[i][j]=='.')
{
for(int k=0;k<8;k++)
{
int newx=i+x[k];
int newy=j+y[k];
if(!(newx>=1&&newx<=n&&newy>=1&&newy<=m))continue;
if(a[newx][newy]=='w'){
cout<<i<<" "<<j<<endl;
sign=1;
break;
}
}
}
}
}
if(sign==0)cout<<"Too cold!";
}
四、RC-u4 章鱼图的判断
输入样例：
3
10 10
1 3
3 5
5 7
7 9
1 2
2 4
2 6
3 8
9 10
1 9
10 10
1 3
3 5
5 7
7 9
9 1
1 2
2 4
4 8
8 10
10 1
10 10
1 3
3 5
5 7
7 9
9 1
2 4
4 8
8 10
10 2
10 6
输出样例：
Yes 5
No 0
No 2
4.1 解题思路：
考察图、并查集的知识点
根据题目意思得，章鱼图指的是在一个图中有且仅有一个环，且环中顶点数大于2。
我们可以用并查集存储各个顶点的祖先，如果当连接a、b边的时候，他们的祖先相同，说明他们已经是连同的，此时加上a、b边，必然连接成环，只不过我们要考虑到一点，一个图里面不能有超过两个的环，所以我们还要用一个数组进行记录环的个数，存储在祖先节点即可。
如果是只有一个章鱼子图，则利用bfs去求环的长度即可（因为我们知道这个还的祖先节点，这个节点必在环内）
4.2代码示例：
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N=1e5+5;
vector<int> g[N];
int f[N],d[N],s[N],r[N];//s表示每一个联通子图中的环的个数
int t,n,m;
int find(int x)//求祖宗节点
{
if(x!=f[x])return f[x]=find(f[x]);
return f[x];
}
int bfs(int now,int end,int sum)//求两个端点的最短距离
{
d[now]=1;
for(auto num:g[now])
{
if(num==end&&sum>2)return sum;
if(d[num]==1)continue;
int temp=bfs(num,end,sum+1);
if(temp)return temp;
}
return 0;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
//初始化
for(int i=1;i<=n;i++)
f[i]=i,s[i]=0,d[i]=0,r[i]=i,g[i].clear();
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
//用二维vector建边
g[a].push_back(b);
g[b].push_back(a);
//保存两个点的祖先
int fa=find(a);
int fb=find(b);
//如果两个点的祖先相等他们一定能围成一个环
if(fa==fb){
s[fb]++;
r[a]=r[b]=r[fa]=r[fb]=a;
}
else//连接两个点并把两个子图中的环的个数连接一下
{
if(s[fa]==1&&s[fb]==0)r[fb]=r[fa];
f[fa]=fb,s[fb]+=s[fa];
}
}
int ans=0;//章鱼子图的个数
int pre=0;
for(int i=1;i<=n;i++)
{
if(find(i)==i&&s[i]==1)//如果该点就是祖宗节点并且该子图中的子图的个数是1那么该子图就是章鱼子图
{
ans++;
pre=r[i];
}
}
if(ans!=1)//如果章鱼子图的个数不是1直接输出即可
cout<<"No "<<ans<<endl;
else
{
cout<<"Yes "<<bfs(pre,pre,1)<<endl;
}
}
return 0;
}
五、RC-u5 工作安排
输入样例：
3
5
1 2 50
3 3 100
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 20
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 100
1 5 1
3 2 5000
5 5 800
输出样例：
101
80
800
5.1 解题思路：
背包问题，读入数据后，需要按一定顺序排序（优先做结束时间造的工作，其次是花费时间少，最后是工资最高），排完序后，找出状态转移方程即可
5.2代码示例：
#include<bits/stdc++.h>
using namespace std;
struct node{
int t,d,p;
};
bool cmp(node a,node b){
if(a.d!=b.d)
{
return a.d<b.d;
}
if(a.t!=b.t)
{
return a.t<b.t;
}
return a.p>b.p;
}
void solve()
{
int n;
cin>>n;
vector<node>v;
int maxd=0;
for(int i=0;i<n;i++)
{
node temp;
cin>>temp.t>>temp.d>>temp.p;
maxd=max(maxd,temp.d);
if(temp.d>=temp.t)
{
v.push_back(temp);
}
}
n=v.size();
sort(v.begin(),v.end(),cmp);
int dp[maxd+1];//dp[i]代表在i时间内所获得的最大工资
memset(dp,0,sizeof(dp));
int maxmoney=0;
for(int i=0;i<n;i++)
{
for(int j=v[i].d;j>=v[i].t;j--)
{
dp[j]=max(dp[j],dp[j-v[i].t]+v[i].p);
maxmoney=max(maxmoney,dp[j]);
}
}
cout<<maxmoney<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
4
0- 0
已为社区贡献2条内容
所有评论(0)