当前位置: 首页 > news >正文

2024 睿抗编程技能赛——省赛真题解析(含C++源码)

2024 睿抗机器人开发者大赛CAIP-编程技能赛-本科组(省赛)

    • 前言
  • 热热热
    • 满分代码及解析
  • 谁进线下了?
    • 满分代码及解析
  • 暖炉与水豚(需要思考蛮久)
    • 满分代码及解析
  • 工作安排(dp)
    • 满分代码及解析
  • 章鱼图的判断
    • 满分代码及解析

前言

只要有注释都是自己写的 所以有些题目就直接以注释的方式把我的思路呈现出来 仅供参考 而且我写到时候比较仓促 只要AC就行 应该是有优化空间的
但是我敢保证我的代码和思路 都是大家看的懂 能学会的

热热热

在这里插入图片描述

题目链接

满分代码及解析

#include <bits/stdc++.h>
using namespace std;
const int N=50+10;
int tmp[N];//存一下温度
//基本思路: 首先我们要对于这给出的N天的气温数据进行判断 只要是满足条件就++
//同时对于不满足条件的天数我们进行计数 最后输出即可 
//表示明明可以喝到的但是碰到了疯狂星期四int n,w;//分别表示一共多少天 从星期几开始计数
int ans1,ans2;//表示最后能喝多少杯 多少杯是碰上星期四没喝上
int main()
{cin>>n>>w;for(int i=0;i<n;i++){cin>>tmp[i];if(tmp[i]>=35 && w%7!=4)//满足条件{ans1++;}else if(tmp[i]>=35 && w%7==4){ans2++;}if(w!=7){w++;}else{w=1;//一周只有七天啊}//给的是连续的天数这里直接++更新就好了}cout<<ans1<<' '<<ans2<<endl;return 0;
}

谁进线下了?

在这里插入图片描述

题目链接

满分代码及解析

#include <bits/stdc++.h>
using namespace std;
int n;
int a,b;//表示排名和杀人数量
int score[9]={0,12,9,7,5,4,3,2,1};
int get(int x)//对于每个排名直接返回得分
{if(x==6 || x==7){return 3;}else if(x>=8 && x<=10){return 2;}else if(x>=11 && x<=15){return 1;}else if(x>15){return 0;}else{return score[x];}
}
int ans[21];//存储每个队伍的得分情况
int main()
{cin>>n;//一共n场比赛while(n--)//每一场都是20条信息 输出的是全部比赛结束之后这二十只队伍各自的总得分{//处理信息for(int i=1;i<=20;i++){cin>>a>>b;int res=get(a)+b;ans[i]+=res;}}//按序号输出每个队伍的得分情况for(int i=1;i<=20;i++){cout<<i<<' '<<ans[i]<<endl;}return 0;
}

暖炉与水豚(需要思考蛮久)

在这里插入图片描述

题目链接

满分代码及解析

基本思路

我们需要做的是先找到地图上的不合法点(不对劲水豚) 从图上来说也就是一个处于warm状态的水豚 不可能在以他为中心的九宫格内 没有火炉也就是如果发现一个w时我们就去检查他的九宫格 如果发现没有m就是非法的 此时我们就需要在他的九空格的空闲位置(因为还有别的水豚会占位置)放置炉子
而且题目说了 这个不对劲状态是唯一的(我觉得这非常重要 不然就很复杂了)所以这题的思路是不是就渐渐浮出水面了呢
好了我们再次观察样例 把他想象成一个地图(6行8列  从1开始编号 )wm....mw.w..ww....wm.wwmw.w....w.m.c.m..w.....w.
很明显 不正常的水豚是位于(3,6)
所以我们可能会摆放的点只有(2,7)(3,5)(4,5)(4,6)(4,7)这五个点那么为什么最后答案把(4,5)这个点舍去了呢?
这是因为样例中有一只处于cold的水豚 他跟我们warm相反 
在以它为中心的九宫格内
是不可能有火炉的 正好与(4,5)冲突了 所以这个点就舍去了最后总结一下: 
那么我们是不是只需要干三件事情:
1.找到不合法点 将它四周的点全部看作可以摆放炉子 做个标记 
2.对于这些看似可以摆放炉子的点检查他的四周有没有cold的水豚 
-如果有就回溯一下
-如果没有就不做操作
3.按照要求排序输出

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char s[N][N];
int st[N][N];//标记隐藏火炉可以存在的位置
//弄个偏移量数组枚举它的八个方向
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};void check(int x,int y)
{bool has_m = false;for(int i=0;i<8;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx < 1 || xx > n || yy < 1 || yy > m) continue; // 越界检查if(s[xx][yy]=='m')//有炉子{has_m = true;}}if(!has_m) { // 如果九宫格内没有炉子,标记四周可放置位置for(int i=0;i<8;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx < 1 || xx > n || yy < 1 || yy > m) continue; // 越界检查if(s[xx][yy]=='.'){st[xx][yy]=1;}}}
}bool has_cold(int x, int y) {for(int i=0;i<8;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx < 1 || xx > n || yy < 1 || yy > m) continue; // 越界检查if(s[xx][yy] == 'c') return true;}return false;
}int main()
{cin>>n>>m;//地图大小memset(st,0,sizeof(st));//初始化为0表示没有隐藏的火炉for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>s[i][j];if(s[i][j]=='c'){st[i][j]=2;//标记cold水豚}}}// 检查每个w水豚for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='w'){check(i,j);//检查每个w水豚 找到不正常的水豚}}}// 对于标记为1的点,检查其九宫格内是否有c水豚for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(st[i][j]==1 && has_cold(i, j)){st[i][j]=0; // 与cold水豚冲突,取消标记}}}// 收集可能的暖炉位置vector<pair<int, int>> positions;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(st[i][j]==1){positions.push_back({i, j});}}}// 按要求排序sort(positions.begin(), positions.end());// 输出结果if(positions.empty()) {cout << "Too cold!" << endl;} else {for(auto &p : positions) {cout << p.first << ' ' << p.second << endl;}}return 0;
}

工作安排(dp)

在这里插入图片描述
题目链接

满分代码及解析

先贴一个 解析
看了几个 这是我认为最好懂的解析 明天我再把我的思路和代码更新上去
顺便把2023还有两个题目弄完

#include <bits/stdc++.h> // 引入所有标准库using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (虽然本题报酬用 int 足够)// 定义工作结构体,包含时间 t, 截止时间 d, 报酬 p
struct node {int t, d, p;// 重载小于运算符,用于按截止时间 d 升序排序bool operator<(const node &other) const {return d < other.d;}
};// 解决单组测试数据的函数
void solve() {int n; // 工作数量cin >> n;vector<node> e(n + 1); // 存储工作信息 (使用 1-based 索引方便一点)for (int i = 1; i <= n; i ++ ) {int t, d, p;cin >> t >> d >> p;e[i] = {t, d, p};}// 按截止时间 d 升序排序sort(e.begin() + 1, e.end());// dp[j] 表示考虑了前 i 个任务后,所有选定任务的总完成时间不超过 j 时,能获得的最大报酬// 时间上限取 5000 即可,因为截止时间最大为 5000// 注意:dp 数组大小设为 5010 避免可能的边界问题vector<int> dp(5010, 0); // 遍历按截止时间排序后的每个工作for (int i = 1; i <= n; i ++ ) {// 获取当前工作的信息: t=x, d=y, p=zauto [x, y, z] = e[i];// 剪枝:如果工作所需时间大于其截止时间,则不可能完成,跳过if (x > y) {continue;}// 逆序遍历时间 j,从最大可能的完成时间 (5000) 到当前工作所需时间 x// 这是 0/1 背包优化的关键,确保 dp[j-x] 使用的是考虑前 i-1 个工作时的状态for (int j = 5000; j >= x; j -- ) {// 尝试将工作 i 加入调度// 如果选择工作 i,它最晚可以在 min(j, y) 完成//   (必须 <= j 因为我们在计算 dp[j];必须 <= y 因为 y 是工作 i 的截止时间)// 如果工作 i 在 min(j, y) 完成,那么它之前的工作必须在 min(j, y) - x 之前完成// 这些之前工作的最大报酬是 dp[min(j, y) - x]// 所以,选择工作 i 得到的总报酬是 dp[min(j, y) - x] + z// dp[j] 取 "不选工作 i" (原来的 dp[j]) 和 "选工作 i" 两种情况的最大值dp[j] = max(dp[j], dp[min(j, y) - x] + z);}}// 所有工作处理完毕后,dp[5000] 存储了在时间 5000 或之前完成工作的最大报酬// 由于 dp[j] 是单调不减的,dp[5000] 就是所有可能完成时间中的最大报酬cout << dp[5000] << "\n";
}int main() {// 加速 IOios::sync_with_stdio(false);cin.tie(nullptr);int t; // 数据组数cin >> t;// 处理每组数据while (t -- ) {solve();}    return 0; // 程序正常结束
}

章鱼图的判断

在这里插入图片描述
题目链接

满分代码及解析

没具体学过图论 所以先参考别人的吧哈哈 后面如果会了会自己写一遍
对应解析

#include<bits/stdc++.h>using namespace std;
#define pb push_back
#define int long long
#define inf 0x3f3f3f3f
const int N = 1e3 + 10;
#define pII pair<int,int>void solve() 
{int n, m; cin >> n >> m;vector<int> in(n + 10, 0), va[n + 10], st(n + 10, 0);while(m --){int a, b; cin >> a >> b;in[a] ++, in[b] ++;va[a].pb(b), va[b].pb(a);}int huan = 0, cot = 0;for(int i = 1;i <= n; i ++){if(in[i] == 1){st[i] = 1;queue<int> heap;heap.push(i);while(heap.size()){int t = heap.front(); heap.pop();for(int k = 0;k < va[t].size();k ++){int j = va[t][k];if(!st[j]){if(in[j] == 2){st[j] = 1;heap.push(j);}else if(in[j] > 2){in[j] --;}}}}}else if(in[i] == 0){st[i] = 1;}}for(int i = 1;i <= n;i ++){if(!st[i]){st[i] = 1;int flag = 1;queue<int> heap;heap.push(i);int last = cot;while(heap.size()){int t = heap.front(); heap.pop();if(in[t] > 2) flag = 0;cot ++;for(int k = 0;k < va[t].size();k ++){int j = va[t][k];if(!st[j]){st[j] = 1;heap.push(j);}}}if(!flag) cot = last;huan += flag;}}if(huan == 1){cout << "Yes "<< cot << '\n';}else{cout << "No "<< huan << '\n'; }
}signed main(){int T = 1; cin >> T;while(T --){solve();}return 0;
}
http://www.lryc.cn/news/583353.html

相关文章:

  • 【Python】遇到 “non-integer arg 1 for randrange() ” 问题的解决方法
  • 技术开发栈中 URL地址末尾加不加 “/“ 有什么区别?
  • 闲庭信步使用图像验证平台加速FPGA的开发:第六课——测试图案的FPGA实现
  • 解决IDEA缺少Add Framework Support选项的可行性方案
  • java中list.remove(item); // 直接移除会导致ConcurrentModificationException
  • 图像自动化处理初探:从拖拽上传到参数设置
  • 基于Java+Maven+Testng+Selenium+Log4j+Allure+Jenkins搭建一个WebUI自动化框架(5)失败用例截图与重试
  • 制作MikTex本地包可用于离线安装包
  • Synology Cloud Sync构建的企业级跨域数据中台
  • 前端性能优化:从之理论到实践的破局道
  • 【PTA数据结构 | C语言版】一元多项式求导
  • 使用 Docker 搭建 Rust Web 应用开发环境——AI教你学Docker
  • 图像处理中的凸包检测:原理与实现
  • 前端开发自动化设计详解
  • 两种方式清除已经保存的git账号密码
  • AI在垂直领域的深度应用:医疗、金融与自动驾驶的革新之路
  • 分治算法---快排
  • 深度帖:浏览器的事件循环与JS异步
  • Foundry智能合约测试设计流程
  • 【25软考网工】第十章 (3)网络冗余设计、广域网接入技术
  • 【一起来学AI大模型】PyTorch DataLoader 实战指南
  • 前端交互自定义封装类:“双回调自定义信息弹窗”
  • ClickHouse 时间范围查询:精准筛选「本月数据」
  • pytorch 自动微分
  • Git 详解:从概念,常用命令,版本回退到工作流
  • sqlplus表结构查询
  • 3.常⽤控件
  • 跨平台ROS2视觉数据流:服务器运行IsaacSim+Foxglove本地可视化全攻略
  • 【动手学深度学习】4.9. 环境和分布偏移
  • MyBatis之数据操作增删改查基础全解