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

杂题选做

杂题选做

#1 CF1566F

题目传送门

我们先去掉初始就被访问的区间;然后套路地,如果一个区间包含了其他区间,那么该区间可以去掉。

然后我们考虑一个点的移动范围:就是它左边的点到它右边的点构成的区间。否则我们完全可以让左边或右边的点去移动。

然后一个点至多换一次方向,不然一定可以转化为只换一次方向且次数更少的方案。特别地,我们将不换方向的运动看成反方向不移动后换一次方向的运动。

于是我们对于相邻的两个点进行 dp,枚举它们之间的两个相邻区间,然后枚举两个点的初始运动方向。转移即可。

#2 P8179

题目传送门

首先,我们注意到:一个轮胎的使用时间是一段连续区间。不然可以把所有区间合并,然后节省换胎时间。

其次,我们考虑 \(t = 0\) 怎么做。此时使用费用是单调递增的,于是我们可以使用栈来维护当前最小代价。

那么 \(t \neq 0\) 呢?我们考虑把 \(t\) 加到第一次使用的代价,然后就发现此时费用并不单调。

但是我们发现取到第 \(\sqrt t+1\) 个时,因为加 \(t\) 导致影响就没了。(因为此时代价不小于第一个,所以能取到说明即使第一个加了 \(t\),这个物品取这么多个还是优的)

因此我们对前 \(\sqrt t\) 次此时做分组背包,对之后的使用用堆来维护。

可以明确的是:我们的选取一定是合法的,因为如果前面背包部分取不到 \(\sqrt t\) 个,那么说明取 \(\sqrt t\) 个不优,取 \(\sqrt t+1\) 个更不优。

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

相关文章:

  • kettle插件-国产数据库瀚高插件,助力国产数据库腾飞
  • 利用旋钮控制小灯亮度
  • 37 ACwing 298 Fence 题解
  • 35 ACwing 297 The Battle Chibi 题解
  • 一款由网易出品的免费、低延迟、专业的远程控制软件,支持手机、平板、Mac 、PC、TV 与掌机等多设备远控电脑!
  • 计划管理
  • 苍穹外卖第二天(Nginx如何配置、MD5加密)
  • aardio跨窗口传递变量
  • AI在简单视觉推理谜题中的挑战
  • 自动引入的element-plus覆盖tailwindcss样式冲突解决方法
  • 已严肃完成今日96种状态的超级神仙DP大学习
  • P3388 【模板】割点(割顶) tarjan
  • new day
  • 10.9每日总结
  • vLLM 吞吐量优化实战:10个KV-Cache调优方法让tokens/sec翻倍
  • Linux之周期性定时任务实践
  • MyBatis-Plus 的 QueryWrapper 应用以及在内存中处理JSON数组字符串匹配
  • P9461 「EZEC-14」众数 II
  • 提升
  • 详细介绍:win11 安装 WSL2 Ubuntu 并支持远程 SSH 登录
  • Ai元人文:论智能的“全息定帧”与“渐进式显影”机制
  • 24 LCA模拟赛2T4 colorful 题解
  • 23 LCA模拟赛2T2 异或排列 题解
  • Bugkuctf的哥哥的秘密
  • 国庆做题记录(基础算法)
  • fp16训练神经网络时出现nan问题
  • 第十篇
  • 504 品酒大会!!!!!!
  • 整体理解pai0-具身智能-01 - jack
  • 【数据结构】可撤销并查集 - Slayer