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 被选择且加起来比它小：

如果两个都在 $A$ 类，这是不可能的，因为 $A$ 类中的糖果满足 $2a_k > a_i$ 。
如果一个在 $A$ ，另一个在 $B$ ，枚举这两个 $k, p$ ，那么 $[i + 1, k - 1]$ 可被选可不选， $[k + 1, p - 1]$ 全是 2， $[p + 1, n]$ 全部无所谓。
两个都在 $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，我错了后面忘了。

NOIP2025 游记

文章操作

NOIP2025 游记

Day 1

A

B

C

D

Day 2

相关推荐

评论

NOIP2025 游记