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

CF2115 总结

CF2115 总结

感受

做过前两道 ,但是第一道一直卡,想不出怎么维护最小次数使一个数变为 \(gcd\),过了半小时,开始看 \(B\) ,直接会了。看 \(C\) 在想最优策略,被值全部相同但刷出了普通攻击的情况卡了,连 dp 都没列。看 \(D\) 想从高到低位贪心,也发现了最后一个人可以调整,但是因为感觉会对下一位有影响,不好做。剩下的题没看,回去把 A 做了,遗憾离场。

题解

A

首先不难发现结尾状态一定是全变成 gcd 。然后思考最优策略,如果恰好有 \(gcd\) 直接用它与不是 gcd 的做一遍一定是最优的。然后思考没有是 gcd 的情况,先搞出一个 gcd 一定是优的,如果过程在搞出一个 \(gcd\) 之前做了别的事,这个操作的位置没有操作到 gcd 后面还是需要一次操作,同时不可能操作一下别的数会让搞出 \(gcd\) 次数变少,所以问题变为最小的操作次数凑出 \(gcd\) 。因为值域小于 \(5000\) ,所以 \(dp_{i,j}\) 表示用前 \(i\) 个数搞出 \(j\) 的最小操作次数。

数据范围增大有基于反演和卷积的 \(O(V\log V)\)(CF2115A - Gellyfish and Flaming Peony - 洛谷专栏)

B

首先知道结尾状态而不知道初始状态,考虑倒推。不难发现可以对其图论建模 \(z=\min(x,y)\) 反向后有 \(x\ge z,y\ge z\) 对于一个值可能有多个这样的限制,一定要满足最大的那个,那么最优的选择就是压着合法的下界,对于最后推出来的数组做一遍操作判断能否做出 \(b\) 即可。不压下界,一定对任意点都没有贡献,压下界就有可能有贡献。

C

对于值全部相同但刷出了普通攻击,我们有两种选择在 dp 转移时取 \(\max\) 即可。

如果最小值不为 \(1\) 闪耀一定会用,如果有超过最小值的数,不闪耀也一定会用,所以最优决策与最小值和可以操作超过最小值的个数。

\(f_{i,j,s}\) 表示还剩 \(i\) 轮,最小值为 \(j\) ,序列总和为 \(nj+s\) 的最大概率,转移比较简单。 不难发现时间复杂度有问题,直接做最后一维是 \(V^2\) 的,但是观察特点,一但 \(s\)\(0\) 消了一次接下来的 \(s\) 最大是 \(n-1\) 。最后一维是 \(n\) 的时间复杂度是可以接受的,所以枚举第一次消 \(0\) 的时候,如果是 \(t\) , 概率显然为 \((1-p)^sp^{t-s}\binom{i-1}{s-1}\) ,这样我们就可以统计答案,且时间复杂度正确。(此题有一点卡精度,所以组合数和概率一起递推,还卡时间,注意常数)。

D

从高到低贪心以及最后一个人控制是正确。

我们先让问题变简单一点,我们钦定全选 \(b_i\) ,同时将 \(a_i=a_i\oplus b_i\) ,问题变为选或不选 \(a_i\) (与原问题等价)。找到最后一个当前位为 \(1\) 就能知道当前位的最优解,但是别的数这一位也有一,就会导致有影响,前面选了奇数个你就必须选 \(1\) 前面选了偶数个就必须不选,为了消除前面的影响,我们对前面为 \(1\) 的位置异或上最后一个,将这一位所有 \(1\) 消掉,同时分情况将答案异或上最后一个的值,这样前面的选择就不影响了,每一位独立,直接暴力做,不难发现这样选择与原问题最优选择等价。

E

完全背包问题,我们有最直接的暴力 \(O((n+m)r)\) 的,但是由于 \(c\le 10^9\) 所以直接做显然不行。

因为值域巨大,我们发现会先填一些性价比很高 \((c_u,w_u)\) 的物品,对于剩下的体积再用其他物品来做,不难证明其他物品最多选 \(c_u\) 个(鸽巢原理),占用的体积最大时 \(c_{max}^2\) 。我们可以先全选性价比最高的,直到选不了,再考虑替换。最后剩下的体积小于 \(c_u\) ,用这个取跑背包,不难发现剩下的体积可能装不满,取出一两个性价比最优的会使答案更大(设答案为 \(C+{V-used\over c_u}*w_u\)),所以我们维护 \(f_i\) 表示最大的 \(i+k\times c_u-{used\over c_u}*w_u\) (相当于取出一些性价比最优的给其他物品选)即可,转移形如同余最短路,转圈算法即可。

将两个做法拼起来 \(r<c^2\) 时,跑完全背包的暴力,否则同余最短路。不能直接同余最短路的原因是取模后没有考虑背包容量,如果小于 \(c^2\) 同余最短路会搞出超过体积的最优解。

F1

首先因为前缀,每次操作会多增加一个连续段(区间是多增加两个)所以考虑序列分块。

对于插入删除操作都可以直接暴力做,时间复杂度是 \(O(n\sqrt n)\) 的。对于删除操作,不好直接做,但是全局删除,所以考虑延迟删除,打个标记,遍历到了再删,每个点只会删一次所以总时间复杂度与插入一样。查询操作,先考虑简单的,在块内,可以暴力遍历一遍每个连续段维护的值,再考虑段间,最大的问题是位置,不知道每个点在上一个集合对应的位置,所以可以记每个块记位置的变化(每个块以上一个块为基础重新1-n 编号,所以要能还回去)。找 \(\sqrt n\) 块中的所有所有位置遍历一遍即可。

总结: 操作分块,每个块内维护连续段(位置连续经历的操作相同),每个连续段维护加入的数(vector),删除的数的个数,还要维护操作完第 \(k\) 个位置是上一块的那个位置。插入操作,就先增加连续段,然后 \(i\) 暴力插入每个连续段的 vector 。反转也是增加连续段然后暴力反转,删除操作打标记。查询操作,找 \(\sqrt n\) 块中的所有所有位置所在的连续段遍历一遍 vector 即可。

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

相关文章:

  • luogu P8816 [CSP-J 2022] 上升点列 题解
  • CF558C Amr and Chemistry BFS解
  • Atbash密码和摩斯密码
  • Redis 中如何保证缓存与数据库的内容一致性?
  • Payload CMS:开发者优先的Next.js原生开源解决优秀的方案,重新定义无头内容管理
  • 第一次写博客
  • 07. 自定义组件
  • python语法记录
  • 2025 年储罐厂家推荐最新公司权威排行榜榜单发布,深度解析衬四氟储罐 / 硫酸储罐 / 盐酸储罐工厂选购指南
  • UnicodeEncodeError: locale codec cant encode character \u5e74 in position 2: encoding error
  • 2025 年生物除臭设备厂家最新推荐排行榜:覆盖污水处理厂 / 垃圾中转站等多场景,助力企业精准挑选优质设备
  • 2025 年球墨铸铁管公司:重庆南恩物资全品类管材供应与市政工程适配解决方案解析
  • 2025生物除臭设备厂家最新品牌企业推荐排行榜揭晓:印染厂污水,食品厂污水,污水处理厂,污水泵站,污水站,餐厨垃圾,屠宰场,厨余垃圾生物除臭设备公司推荐
  • 2025 工业加热器选型必看:六大加热器实力厂家深度推荐,覆盖多场景加热设备解决方案
  • YOLO模型部署
  • 从理念到沙盘:用悟空博弈模拟器点亮人机共治的曙光
  • 深入解析:Redis事务详解:原理、使用与注意事项
  • phone num
  • Perplexity发布搜索API,驱动下一代AI应用开发
  • PWN手的成长之路-09-SWPUCTF 2023 秋季新生赛Shellcode
  • 20251005 总结
  • OKR1
  • 2025 年装盒机制造厂 TOP 企业品牌推荐排行榜,自动化 / 喷胶 / 牙膏 / 手机壳 / 3C 数码 / 内外盒 / 面膜 / 电子产品 / 玩具 / 日用品装盒机推荐这十家公司!
  • 英语_阅读_Chinas Spring Festival_待读
  • 2025 年自动包装生产线 TOP 企业品牌推荐排行榜!食品行业 / 日化产品 / 智能化 / 小型 / 多功能集成 / 柔性 / 后道 / 高速自动包装生产线推荐!
  • 题解:AT_arc181_e [ARC181E] Min and Max at the edge
  • 酵母单杂交实验:解密 “转录因子 - DNA 互作” 的核心工具
  • api调用钉钉群机器人发信息 - 规格严格
  • 2025 年氢氧化铝生产厂家 TOP 品牌榜单来袭,阻燃,高白,酸融,导热,超细,微粉级,低粘度,灌封胶用,覆铜板用氢氧化铝公司推荐!
  • 飞算 JavaAI 赋能老工程重构:破旧立新的高效利器