NOIP 2025 游记

P2441M · 2025-12-01 08:33:39 · 生活·游记

Day -1

狂暴刷模板。

Day 0

狂暴刷模板。

临时抱佛脚这一块。

下午就去酒店住了，点了杯奶茶，没干正事。

Day 1

6:50 起床吃了个早餐。

去考场。

进校门的时候还是有点紧张，走到信息楼的时候就已经缓解得差不多了。

进考场，提前了 5 分钟开考。

看了一遍题，发现 T4 依旧是 DS，比较震撼。

用了 CP Editor。敲了一遍缺省源。

想 T1。一开始认为 x+y 最小的一直取就行了，假完了。思考了一下，发现如果 x+y 不是最小的糖果取了 >1 个一定可以交换取到更优，所以最优方案一定是形如把所有糖果按 x 从小到大排序后取一段前缀，剩下的全部用最小的 x+y 补。15\text{min} 搞定。

想 T2。一开始以为是所有定价方案里原价总和的最大值，然后被样例解释爆了才理解对。感觉有点歧义啊！直观感受就是不太可做。摸了一会儿性质，发现贪心不优当且仅当存在一个 2 被某个 1 卡住了，并且可以通过将最小的两个 1 换成 2 取到更优解。用性质来写 \mathcal{O}(2^n) 做法的 check，调了一些细节之后过了。有点激动。

开始想如何计数。思考枚举两个最小的 1 怎么做，思考不出来。这般大概一个小时过去了，还是没有什么头猪，有点慌了。感觉事情不太对劲，开始写 T3、T4 的暴力了。

感觉 T4 更好写。写了个 \mathcal{O}(qn^2) 拼上 L=R 或者 R\leq 32 的单调队列，预期 40\text{pts}。没看懂其他特殊性质在干什么，跳了。

看 T3。显然值域是 [0,n-1]，所以有 \mathcal{O}(n^n) 做法。这也太蠢了！改成状压。直接合并是 \mathcal{O}(4^nn)，还是太蠢了。用树形背包状物限制一下 sz 就是 \mathcal{O}(2^nn) 了。预期 24\text{pts}。

回去继续搞 T2 的部分分。全部相等时输出 2^n。尝试写 m=2，大样例过不了！那咋办那咋办那咋办那咋办那咋办那咋办那咋办那咋办。对拍，小的拍不出来，大的拍出来没用。pofangle。不管了，去 check 了。

这就结束了。死透了。

出考场，好像挺多人 T2 都没做出来。大神 @oyoham 估分 300^{+}\text{pts}，这诗人？？这诗人？？这诗人？？这诗人？？这诗人？？这诗人？？

学习了 T2 做法。回家仔细思考，发现想不明白是因为没注意到 a_i+a_k<a_j\Rightarrow a_i<a_j。这诗人？？这诗人？？这诗人？？这诗人？？这诗人？？这诗人？？

T4 怎么是倍增值域分块。没见过，题的问题。

T4 我怎么做过 q=1 的 \mathcal{O}(n\log{n}) 做法的题？！！那咋办，场上没想起来。我的问题。

T3 怎么是巨大难题。题的问题。