2022年第十三届蓝桥杯大赛软件类国赛C/C++大学B组题解
发布网友
发布时间：2024-08-25 13:51
共1个回答
热心网友
时间：2024-08-25 14:05
A: 背包问题，将数视为体积为特定值的物品，最大体积设定为2022。状态表示为前n个物品中选取m个组成特定体积，状态转移方程为dp[i][j] = dp[i-1][j] || dp[i-1][j-weight[i]] + value[i]，其中weight[i]和value[i]为物品的重量和价值。优化通过滚动数组实现，遍历时逆序进行。
答案为379187662194355221，需注意使用long long类型。
B: 钟表题，采用模拟方法，注意精度与角度取舍，答案为4 48 0。
C: 卡牌问题，使用二分法寻找最优解。
D: 最大数字问题，通过回溯搜索枚举每一位的操作。
E: 出差问题，使用Dijkstra算法解决最短路径问题，考虑隔离时间，注意特判情况。
F: 费用报销问题，属于背包问题，处理日期统一为天数单位，定义状态为选取前i张票据占用体积的最大价值，状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + value[i])，其中cost[i]和value[i]为票据的费用和价值。
G: 故障问题，利用概率论计算，理解样例，进行模拟。
H: 机房问题，为lca裸题，加入点权即可。
I: 齿轮问题，使用二分查找，考虑排序条件与优化，时间复杂度为O(n log n)。
J: 搬砖问题，是01背包问题，通过贪心排序优化，状态转移方程为dp[j] = max(dp[j], dp[j-weight[i]] + value[i])，其中weight[i]和value[i]为砖块的重量和价值。
总结，比赛体验一般，部分题目的描述不严谨，如B题未考虑0 0 0的情况，G题缺乏样例解释，另外，C/C++题目中背包问题数量较多。
