竞赛讨论区 > 2021牛客OI赛前集训营-普及组(第二场)题解
头像
Zhou_JK
编辑于 2021-10-07 20:55
+ 关注

2021牛客OI赛前集训营-普及组(第二场)题解

恰饭

算法一

时,每一种菜和甜品的组合的花费都是相同的,输出 即可。

时间复杂度 ,期望得分 分。

算法二

时,每一种菜的价格是相同的,枚举选哪个甜品,取个最小值即可。

时间复杂度 ,期望得分 分。

算法三

最优解肯定是价格最少的菜和价格最少的甜品,答案即为

时间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916665

卡片

算法一

时,答案即为卡片上不同数字个数。

时间复杂度 ,期望得分 分。

算法二

时,答案为

时间复杂度 ,期望得分 分。

算法三

暴力搜索选出了哪些卡片,将卡片上的数字拼起来,存到一个数组中,最后寻找数组中总共有多少元素即可。

时间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916669

数数

算法一

暴力枚举每个点是否在 中,再暴力判断是否合法,

时间复杂度 ,期望得分 分。

算法二

按照所有点 降序排序,令 表示到第 个点,选出的集合最后两个元素为 的方案数,可以枚举上一个 转移。

时间复杂度 ,空间复杂度 ,期望得分 分。

算法三

发现算法二可以滚动数组优化。

时间复杂度 ,空间复杂度 ,期望得分 分。

算法四

发现算法三还可以前缀和优化。

时间复杂度 ,空间复杂度 ,期望得分 分。

算法五

更换思路,按照所有点 升序排序。

考虑将 作为横坐标, 作为纵坐标,从后往前选点,选出的点 一定是单调递增的,且一定是 坐标向左/向右交替进行选点。

将所有点按照 排序,令 表示填完的最后一位是 ,接下来向左/向右填的方案数。

考虑转移:

对于 ,只需要枚举下一个填的位置 满足 ,令

对于 ,我们可以每次填入两个位置,我们需要找到下一个向左的位置 满足 转移即可。

具体的说对于一个 ,我们可以倒序枚举

  • 如果
  • 如果

时间复杂度 ,空间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916675

划分

算法一

暴力枚举每个节点和它的哪个儿子在一条直链上(或者和它的任意一个儿子都不在一条直链上),判断每条直链是否合法。

时间复杂度 ,期望得分 分。

算法二

对于 互不相同, 互不相同的情况,每个权值最终到达的节点都是唯一的,源点和到达点一定是在同一条直链上,否则不合法。如果某两条链之间有交且一个不包含另一个也不合法,反之一定合法。

时间复杂度 ,期望得分 分。

算法三

考虑一种构造方法,我们每次选择一个叶子 。考虑从 开始不断向父亲跳,直到当前的直链满足条件。若跳到根还是不合法或者该过程中存在一个点已经被划分到了另一条直链上,那么一定无解(因为其他划分方案都是在这种方案的基础上将某些链合并而成的)。否则将该直链加入划分方案。

时间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48923373

全部评论

(5) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐