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

?模拟赛(3) 赛后总结

今天打得还好吧!起码没有犯很唐的错误乐。

题目


A 维护集合

只打了暴力。

因为数最大只有 \(10^5\) ,所以可以提前预处理出所有的答案。枚举约束 \(i\) 再枚举其作为 \(w\) 重约数的约数 \(i^w\) ,然后枚举其倍数 \(j\) ,那么 \(i\) 就可以作为 \(j\)\(w\) 重约数。把每个数的所有 \(x\) 重约数保存起来,按几重从大到小排序,查询时找到最靠前的集合中存在的约数,答案即为其重数 \(k\)


B 星星点灯

灯与灯之间可以相互引燃,可以想到最小生成树。

但如果有灯通过其他灯引燃的代价还不如它自己直接花 \(m\) 的代价点燃,那会产生不止一个的起始点,需要建好几棵树。所以将边权与 \(m\) 取一个最小值,就可以将所有灯连接起来了。答案就是最小生成树边权之和再加上 \(m\) ,因为还有一个起点需要先点燃。


C 发工资

\(n\) 个大臣视作 \(n\) 个任务,其奖金上下限就是任务出现的时间和截至时间。那么 \(m\) 个金条就是 \(m\) 个完成任务的机会,金条的价值就是可以完成一个任务的时间。

那么贪心策略很明显了,将任务按照右端点排序,优先完成截至时间早的任务,二分找到最早的可以完成它的机会,匹配不到就说明这个任务要放弃。我记得初赛好像选择有考这个。


D 翘课

经典把 DP 当成贪心做。

发现每一天一定是翘最早和最晚的课才有意义,中间的课即使不上也要留在学校。那么可以保存每一天的课程,对每一天枚举要上的最早的课和最晚的课,就可以暴力计算出 \(c_{i,j}\) 表示第 \(i\) 天翘 \(j\) 节课最少要在学校留多长时间。设一天一共有 \(t\) 节课,那么 \(c_{i,t}=0\) .因为把一天的课都翘了,可以直接不去学校。

有了 \(c\) 数组之后就可以进行分组 DP 了。\(n\) 天就是 \(n\) 个组,每天能选择翘课的数量也只能选择一种方案。最后答案就是从 \(0\)\(k\) 枚举一共要翘几次课,取 \(dp_{n,i}\) 的最小值。


其实 A 也不难,我应该再多看一看的,当时写完暴力就不管了。

今天感觉困困的,困得难受,难受得睡不着。我服了。

http://www.hskmm.com/?act=detail&tid=18340

相关文章:

  • 用鼠标滚轮缩放原理图界面的小工具
  • 实验任务1
  • OI界的梗(继 @CCCsuper 2.0 版本)
  • 9/26
  • Python 私有属性深度解析
  • 菜鸟记录:c语言实现洛谷P1219 ———八皇后
  • 当危机爆发时,所有网络安全都是本地的
  • crc校验原理是什么?
  • CF1385D a-Good String
  • 9月23日(日记里有)
  • 9月25日(日记里有)
  • Git 提交代码前,一定要做的两件事
  • 本地调试接口时遇到的跨域问题,十分钟解决
  • 用 Excel 快速处理接口返回的 JSON 数据
  • 调度的基本概念
  • Overleaf项目文件同步工具: olsync
  • CF1995D Cases
  • 日志| 编辑距离 | 最长有效括号 |
  • day5
  • 《etcd库——键值存储系统》 - 教程
  • 有一个函数只会返回0和1,且返回0和返回1的概率不等。要求只能通过这个函数生成一个等概率返回0和1的函数
  • AI智能体开发实战:17种核心架构模式详解与Python代码实现
  • 代码随想录算法训练营第十天 | 232. 用栈实现队列、225. 用队列实现栈、20. 有效的括号、删除字符串中的所有相邻重复项
  • 2025.9.26总结 - A
  • MySQL性能优化
  • 关于“悬荡悟空”决策机制的简要技术说明
  • 最小二乘问题详解1:线性最小二乘
  • 9月26日
  • 工程监理行业多模态视觉​​​​​​​大模型系统,打造工地行业全场景的监理智能生态
  • 完整教程:【鸿蒙心迹】摸蓝图,打地基