NOIP2025 游记

· · 生活·游记

NOIP2025 游记

Day 1

学校外只遇到了 xjh，在理塘找到了 dxh3434。

考场外发现 Skeleton_Huo 竟然是座位号 1，离谱。

密码我记得是 !noip@Nov,2025:dream，输错了一次。

A

一开始想直接贪心，但是很快发现不对，仔细想想如果选了一对糖果的话，只会选代价最少的那一对，所以直接枚举只选一个选了多少个，剩下的用代价最少的那一对填就行了。

B

这个时候只花了 10min。

一开始看错题了，以为问的是到达所有方案中最大值的方案数，写完发现我怎么是线性的，然后样例爆了，这才发现原来题目问的是当前方案小 R 决策是最优的方案数，感觉浪费了 20min 左右。

先考察什么情况下会有最优方案，感性理解一下应该是用两个 1 换一个 2 会更优的话就不是最优方案了。

也就是说如果最大的未选择的 2 大于最小的两个被选择的 1 就不是最优方案了，然后开始对这个东西做 DP，感觉怎么做都很难搞，因为要保证按照题目中的顺序来，可能的方法是按 dp_{i, j, k} 表示 2 最后一个被选的是 i，1 最后一个被选的是 j，一共花了 k 块，但是算答案也不是很好算。

那就换一种角度，对着原价顺序看，这个 2 很特殊，先用 i 枚举它，那么比它原价还高的肯定要被选，比它原价低的有两类，A 类是现价是 1 会在 i 前面，否则在 i 后面，B 类是怎么样都在 i 后面，设这个分界点是 j。

然后又有两种情况，如果最后剩下了一块钱不买糖果的话，就要求 [i + 1, j] 中有一个 1 比 2 严格小，并且它被选择，且比它原价小的全是 2，枚举这个 1 的位置即可。

另一种情况是最后钱全部花完了，就要求 i 后面有两个 1 被选择且加起来比它小：

  1. 如果两个都在 A 类，这是不可能的，因为 A 类中的糖果满足 2a_k > a_i。
  2. 如果一个在 A，另一个在 B，枚举这两个 k, p，那么 [i + 1, k - 1] 可被选可不选，[k + 1, p - 1] 全是 2，[p + 1, n] 全部无所谓。
  3. 两个都在 B，枚举这两个 k, p，那么 [i + 1, j] 全部是可选可不选，(j, k) 全部是 2，(k, p) 全部是 2，(p, n] 无所谓。

可选可不选的部分可以和 [1, i - 1] 这些选 1 选 2 无所谓的糖果坐一桌，用小球盒子的组合数算出来方案，后来发现也可以用范德蒙德卷积，本质是一个 two counting。

完了变成 O(n ^ 3) 咋办，先写吧。

写完了发现这个 p 很没用，它和组合数没关系，所以直接把它提出来，用双指针维护 k 和所有可能的 p。

这样就变成 O(n^2) 的了，没怎么调试就过了 11 个大样例，感觉 11 个大样例很稳啊，所以没有写对拍。

这个时候只剩下 2h 了，感觉复刻 CSPS2025 了。

C

不会啊爆，感觉出来好像一个子树里面有一些会变成 X 也就是说给上面的 mex 叠层用的，对当前子树不做贡献的，另一些会给当前子树做贡献，于是编了个假的背包 DP，后来发现忘记考虑用来叠层的节点也会计算子树内贡献，因为要保留子树内的最大 mex，一下变成了 O(n^3)，但是这个时候只有 20min 了，调不出来。

假的 DP 过了 1 2 4 大样例，很奇妙，看数据范围的话是 24 分。

D

没时间想了，对着单调队列猛猛冲，写了个 O(q(R - L)n) 的东西，看数据范围好像可以拿 40 分（？）。

最后检查了文件名和 freopen 就结束了。

出来估分是 100 + 100 + [0,24] + 40 = [240, 264]。 很多人都是 280 多，很多人没切出来 T2，感觉这个 T2 确实很搞啊。

在 LA 一看天都塌了，T1 没判 pre < m 啊，可能要挂。

似乎是要退役了，260 应该上不了你 GD 省二倍对线，为啥 GD 变成超级强省了啊。

晚上品鉴了疯狂动物城 2，感觉剧情每一步都能猜出来啊，变成了温馨的友情第一电影，好像没有 1 那种悬疑感觉了。

想买马萨诸塞但是没有米。

Day 2

看了 lca 老师的题解之后，怎么我的假做法改成 O(n^3) 之后是真的啊，据说可以拿 [50,70] 分啊，受不了了！！！！可能我 T2 某些地方少花一点时间就可以拿下了。

真就是 NOI 模拟赛啊，还少了半小时，是为了避免食堂关门提早下去吃饭吗？

我错了贼猴，我错了 ZR，我错了后面忘了。

Day \infty

95+100+0+40=235。

寄。

T3 48 很人均啊，这个分感觉没有三倍队线了。

T3 MLE 了，我考场甚至写了 cerr << abs(&Mst - &Med)/1048576. << "Mb\n"; 还没有检查出来，改小数组就 24 了。破防了。