嗯欧爱劈 2025 游记

· · 生活·游记

坐标 ZJ。

赛前策略是打稳一点，先签到，后暴力，最后对着 T2 难度的题冲正解。

结果没有 T2 难度的题。

进场。发现正后方是 @wangyizhi。

先简单浏览了一遍，第一印象是 T1 一眼贪心，T2 找性质 dp + 组合数学，T3 树形 dp 或者数据结构维护，T4 纯度数据结构题。整体感觉应该跟去年那套差不多。

开 T1，很快就发现了只有一种糖果一直选，其它最多只选 1 次的性质。然后先后尝试了先选 x_i+y_i 最小的糖果，后面再补别的的策略，以及先取所有比较小的 x_i，再一股脑选 x_i+y_i 最小的糖果的策略。但是尝试了很多都假了，最后画了个图重新理了一下思路，发现唐了，直接按 x_i 排序，枚举前缀取到哪里就做完了。用时 45min。

T2 似乎不太好做，先看后面。

这个 T4 看起来很好骗分，一开始把所有好区间价值的最大值看成所有好区间的价值和了。然后拆贡献做，写到一半发现很多地方都读错了。那好像不太好做，先放一放。

盯了半天 T3 只会 n^n 爆搜，还要剪一下状态才能稳过 n=7 的极限数据拿到 8pts。如果真的跟去年难度差不多，那看这个形式如果不过 T2 很难省一啊。

时间还剩很多，eat 补充能量，认真思考一下 T2。感觉需要转化出原价总和取到最大的充要条件，也就是找性质。

想了半天发现不会，那不管了先写一个 2^n 枚举。然后 go to WC，回来准备先做 m=2 然后以此推广来想正解。

考虑计不合法的，想了很久感觉 m=2 会了。简单写了一下，发现漏了只选一个 1 的情况，补上就能过第一个样例了，这个样例正好满足 m=2。特殊性质对应的大样例是 sale4 和 sale7，这两个也过了，当时觉得自己是对的。然后发现特殊性质 A 是送的，感觉自己有 44pts。

然后想正解，终于发现不合法当且仅当贪心策略选了一个 1 而漏了一个价值高的 2。那么可以 n^2 枚举这个错选的 1 和价值很高的 2，然后推了若干组条件，考虑剩下的哪些可以是 1，哪些可以是 2，哪些都可以是。

写到一半发现怎么漏了一个最重要的：对于所有 \frac{a_k}{w_k} > \frac{a_i}{2}，要满足 \sum w_k = m-1。这个是最紧的限制。那我是不是只能 dp 了，但是 dp 状态如果要记当前的 \sum w_k 就是二维起手，再套上那个 n^2 的枚举就是 n^4 打底，还只能多 4pts，还很容易假。

那做你妈呢，怎么只有 40min 了，赶紧去拼 T4。

我怎么只会 qn^3 啊，哦区间 checkmax 可以线段树维护优化到 O(qn^2logn)。查看数据范围，他妈的怎么只能极限拿 5pts。不管了写了再说。

还有 20min，迷茫，知道自己现在想出什么都没用了。

最后测一遍大样例，我草为什么把爆搜和 m=2 拼一起我 T2 大样例就过不去了。为什么 sale2 后面 m=2 部分输出不对。那不是完蛋了吗。妈的没时间了，赶紧根据输入的 c 调一下数据点分治优先级就能过了。

怎么 4h30min 过这么快。

出来发现大家都不会 T2，感到平和了一些，但是还是担心 m=2 的部分分。

因为太急了没写 T1 对拍，应该不会挂。

估分：100 + [24,44] + 8 + 5 - eps = [137,157] - eps。

感谢 CCF 让我体验了一把省选/NOI难度。

I demand a reroll.

upd：100 + 44 + 0 + 5 = 149。

大概能卡线省一吧。

实际上 T2 数据再强一点就能卡掉一点分。另外赛时没有发现有 m=2n-1 和 m=2n-2 这两个送的性质，另外没有看出 B 性质意味着什么。这几个点是比较遗憾的。

T3 挂了是因为发现直接 n^n 本地评测机太慢，所以把值域上界缩到了 n-1 还是 n-2，然后算 mex 的时候没算 W_{max}+1 的贡献。如果因为这 8pts 没有省一我将红温。下次应该相信 CCF 评测机，别人 T4 的 O(qn^3) 都有 10pts。

复盘了一下 T2 思考过程，发现离正解差一个枚举 i 左边 2 的个数，还差一步范德蒙德卷积。但是我打了 abc433 并且场切了运用范德蒙德卷积的 F 题，所以只要想到枚举 2 的个数大概率就能切了。不过推出最终的式子和思考一些 corner 大概也需要一定时间，确实是由于这道题较长的思维链没有时间继续做下去了。没有想到枚举的原因大概源于我对 dp 的过度信仰，导致最后忽略了只有 1 和 2，才使这道题直接推柿子可做。

滚回去 whk 了。