【免费】第二届计算机学院“debug杯”程序设计竞赛题解1_debug杯资源-CSDN文库

需积分: 0 152 浏览量 2022-08-03 21:07:52 上传评论收藏 711KB PDF 举报

资源详情

资源评论

资源推荐

第二届计算机学院“Debug 杯”程序设计竞赛简易题解

01 A+B

本题是给出两个集合求它们的集合并的大小。这道题定位是一道签到题，主要考察 for

循环/使用数组标记的方法/排序/stl 集合 set 的使用。

Solution 1：对第一个数组里的所有的数，用一个标记数组 vis，标记所有出现的数

（vis[a[i]]=1），然后对于第二个数组里的所有数，如果没有出现过（!vis[a[i]），则计数 cnt++。

最后答案就是 n+cnt。（n 指第一个数组的数的个数）

Solution 2：对于两个数组的数，一起读入进同一个数组，并进行排序。对排序后的数去

重并计算个数即可。

Solution 3：使用 C++中的 stl 容器 set，将两个集合的元素都放入，最后输出该 set 的大

小 size 即可。

知识点：排序，stl 容器 set，循环遍历

By caozy623

02 采木头

本题是给出若干时间点（HH:MM:SS），这些时间点会增加若干数量木头。现在给出一些

询问，询问两个时间点之间增加的木头数量。

Solution ：因为询问数量较多，直接 for 循环回答询问的复杂度会很高。所以可以考虑

先把所有时间点转化成一个整数，然后设置数组 S[i] 进行前缀和维护数量。这样的话对

于时间点 L 到 R 之间的数量询问可以直接由 S[R]-S[L-1]给出。还有一个问题可以存在时

间点 00:00:00，这个时间的话导致可能出现 L=0，从而 L-1 是负数（下标为负数）。这时

候可以把所有时间点+1，然后查询的时候也相应地+1 进行回答即可。

知识点：前缀和，模拟

By caozy623

03 逛公园

本题是给出一张联通的无向图，并定义一个点对(u,v)之间的幸福度为,找出从 u 到 v 的一

条简单路径,使路径上所有点权中最小值最大，该最大值即为点对(u,v)之间的幸福度。然

后要求计算所有点对之间的幸福度之和。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

评论0

内容反馈

有只风车子

粉丝: 33
资源: 329

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip