NOIP 游记 & 考前回忆录

DyingEncoder · 2025-11-13 17:12:45 · 生活·游记

NOIP 考前回忆录

注：高二老 OIer AFO 前的追忆。

可能也和同机房大佬们的复健笔记差不多吧。但是既然我一直都在“健”，也就无所谓 “ 复健 ” 了。

Day -15 11.13

听说其他学校的优秀战绩和往届的优秀战绩，看本届 OI 伙伴一轮一轮被刷下，感觉自己也希望渺茫，不禁悲从中来，不可断绝。突然有点伤感自己为什么不早点学 OI，感叹自己学 OI 那难以言说的意义。

训练计划：练习题库 “ 动态规划 DP ” 中第一页所有 \textcolor{#52c41a}{“普及+/提高”} 的题目。目前进度大概 \frac{3}{5}。

同机房大佬让我去分享导弹拦截的一种做法。不知道题解能不能过。

Day -14 11.14

给自己的目标是 NOIP 250+，但是发讨论区别人也说不可能。其实我也觉得希望渺茫。但谁知道呢。CSP前的集训让我从做不出几道蓝题到拥有切小部分蓝题的实力，说不定 NOIP 前的集训我也能再次进阶呢？

我，能够实现 \textcolor{#52c41a}{绿}\rightarrow \textcolor{#3498db}{蓝} 的进阶吗？

这真是一次渡劫。

今天没写 DP，看了 NOI2025 冬令营讲的贪心专题（然而讲的题难度大都不超过 \textcolor{#fadb14}{普及/提高-}，对我还算比较友好）

练了一天的 贪心+数学，由于不想让别人说我写水题写太多（虽然我的能力只允许我能做出贪心和数学的水题）我没写自己号上，第一轮遗憾退役的巨佬 HAPPINESS23333 把他的号传给了我，我在他的号上写了 9 道题。

Day -13 11.15

【LGR-250】洛谷 NOIP 模拟赛赛时记录

爆 0 祭。 /kl

【LGR-250】洛谷 NOIP 模拟赛赛后总结

不错。很棒。四道思维题我一点也不会。题解也看不懂。

本来打算放弃补题，遭到 MPLN 大佬的严厉批评。沉下心来看了 1.5\text{h} 题解后终于看懂了。在凌晨 1 点通过了该题。

今天由于比赛情况不佳，全天都没有心情练题。好不容易补出题，已经是第二天了。明天要逼自己多写题了。

Day -12 11.16

今天是我的生日！

阅读四道题题面。

T1

一看 T1 怎么是个背包。一看数据范围，背包体积怎么 10^{18} 了？？？不对，但是每个物品价值为 1，可能可以贪心做。但是怎么贪呢？

• 每次选价格最低的买？不对。1 100 和 60 60 两个物品，你不炸了？
• 因为两个物品一个便宜一个贵，所以要一起考虑。每次先把便宜的买了，然后再不断买两个的平均价格最小的？不对。100 1 和 50 100 两个物品，体积 101，你不炸了？
• 先不断买平均价格最小的，然后不够了再买最便宜的？不对。40 100,50 110 和 50 120 三个物品，体积 140，你不炸了？

算了，先不管了，先去看 T2。

T2

诶，好像是DP。维护最值和取到最值的方案数，一看数据范围还是个 O(n^2) DP。应该不难吧？试试设个状态：

• 设 f_{i,j} 表示考虑了前面 i 个糖果，当前花了价格为 j 的原价最大值。转移分两种情况，一种买当前糖果，一种不买。不对啊，买不买是有条件的，仅记录 j 没办法确定是不是可以买或不买？
• 设 f_{i,c_1,c_2} 表示考虑了前 i 个糖果，买了 c_1 个 1 元糖果和 c_2 个 2 元糖果的原价最大值。不对啊还是不能确定买不买当前的？
• 设 f_{i,c_1,c_2} 表示考虑了前 i 个糖果，买了 c_1 个 1 元糖果和 c_2 个 2 元糖果的原价最大值，但是从 f_j 转移，钦定 [i,j] 这一段都要买？不对，先不说这个行不行，枚举一下轻松 O(n^5)，我还不如直接打暴力。

算了我到时候应该想得到的。先看 T3 吧。

T3

诶一看就是个树形DP。怎么tmd是 mex？我考前还说这种数学里的概念肯定不会出到题目里。

诶？还是 O(n^2) DP？应该不会很难吧？试试设计状态。

状态设计一定要包含当前位于哪个节点。然后要包含当前点的决策，即填哪个数。所以设 f_{i,j} 表示考虑到第 i 个点，当前选的数字为 j 的最大的树的价值。但是这玩意怎么转移啊？？？如果说钦定当前的 j 是这个子树的 \text{mex}，那倒还可能转移一下。

考虑是否有这样的性质：当前的 j 一定是子树的 \text{mex} 才最优？不对，显然不是。因为给的样例里，叶节点就不符合该性质，其他节点好像也有反例。

那是否，当前的 j 一定是子树中选择数字的最大值？好像有点道理。考虑是否有这样一个性质：整个子树所占的数字一定是一个连续的数字段？似乎这样子钦定不会变劣。但是这样的话我要处理每个子树选择数字段的并？枚举每个点，再枚举每个点数字段的左右端点，再枚举每个点的儿子的左右端点，O(n^5) 好像还可以。但真有这个性质吗？我不会证。

先看看 T4 吧。

T4

诶，序列类型题目。我要对于每次询问，确定所有长度在 [L_i,R_i] 范围内的区间中，区间和的最大值。然后还要对于 1\sim n 的每个点，统计包含它的区间的区间和的最大值。

嗯。这题好像比较常规。朴素做法先枚举 q，再枚举每个点 i，再枚举左端点 l，然后右端点在 [\max(l+L-1,i),\min(l+R-1,i)] 范围内。区间和嘛，前缀和一下即可。右端点在 [\max(l+L-1,i),\min(l+R-1,i)] 范围内的区间和最大值可以用 st 表维护。时间复杂度 O(qn^2)。

再看数据范围：补耗，出题人看不得 n^2，所有带 n^2 的算法最多只能做前三个测试点。但是 q 很小，不禁让人想到是不是真的要对于每个询问单独处理一次。q 如果这么小的话，离线也没什么效果了，瓶颈就是怎么突破这个 n^2。

初读题目结束，感觉应该不会很难吧。

T1 大概可以拿将近满分，T2 和 T3 貌似部分分很少。T4 应该部分分蛮多的。

那我这次得控分控到 200 pts 左右吧？要不拿不到省一，我就得十年 OI 一场空了。

然后我从第一题开始想做法。

约 45+35 min (9:15\sim 10:35)

想 T1。

突然发现出题人给只会背包的小朋友准备了 65 pts 的高分。心里还算是有点底了。

观察样例解释，怎么感觉就是一直买平均价格最便宜的？但是我自己都造了 hack 了，大样例应该也跑不过几分。算了不写那个错误做法了。

想了半天，只想到一个肉眼可见的性质：小 R 的最终购买方案，对于每种糖果，一定是若干个 x_i+y_i，然后 1 个或 0 个 x_i。

这不是 P 话吗。

不过这貌似直接指向了 DP 的做法：物品体积为 x_i+y_i，价值为 2 的完全背包，和物品体积为 x_i，价值为 1 的 01 背包组成的混合背包。

啊啊啊啊啊为什么不会这题贪心啊？明明背包用贪心是错解，这里为什么就可以做？究竟本题有什么特殊的地方？

算了。真的想不到。把 DP 先打了。现在含泪得到了 60 pts。

考虑特殊性质：

• 当 x_i=y_i 时，贪心选最小价格的糖果一直买应该就行了。

• 当 x_i\ge y_i 时，这时永远也占不了便宜。所以应该是不断买 x_i+y_i 最小的，然后贪心选 x_i 最小的买吧。

  而且貌似贪心选 x_i 最小的，只会选一个。因为 x_i+y_i\le x_a+y_a \le 2x_a，同理 x_i+y_i\le 2x_b，所以 2(x_i+y_i)\le 2x_a+2x_b，x_i+y_i\le x_a+x_b。如果已经买不起 x_i+y_i 了，那肯定买不起 x_a+x_b 了。

  :::info[为什么这样是对的？]

  • 为什么一定是买了 x_i+y_i 最小的？

    假设买得起 x_j 又买了 y_j，那把它们换成 x_i+y_i 一定不劣嘛。假设买得起 x_j 但是不买 y_j，那买 x_j 的策略也应该从小到大。

  • 买完 x_i 最小的，会不会能买得起对应的 y_i？

    不可能。设买完 k(k\ge 0) 个 x_i+y_i 后，买了 x_j 是最小的，则 x_i+y_i\le x_j+y_j。买不起。 :::

这时候我的左边那桌已经开始大声抓头发+骂人了（我如果向 CCF-NOI 科学委员会举报他考试讲话，而且还是骂 CCF，他准得禁赛三年）。

约 20+35 min (10:35\sim11:30)

想了一些别的做法。除了基于原来的状态设计略作改变（但还是尝试失败），我还想到是否可以尝试让每个物品的清仓价格都为 1，然后选择一些商品，让它的原价翻倍。但是很快我发现这不能说是等价转化，只能说是和题意一点关系都没有。

现在总共想了 20 min，压力倒还好。我感觉应该就是本题状态设计比较巧妙吧，可能比较吃思维，我可能不擅长。

但是现在已经过去了快两个半小时了，按照我模考的经验，我还是得赶紧打掉暴力，后面两题的暴力 + 性质分，每道题大概要预留一个小时。

然后我开始想暴力。woc 这个暴力出题人只给前 5 个点呐。凉心出题人呐。

打完样例发现没过小样例。？怎么回事？wok 看错题意了，它的题目的正确意思是，小 R 用了贪心策略来买糖果使得他买的糖果原价总和最大，但是这个贪心是错的，你有设定清仓价格的很多方案，问你有多少方案使得他的贪心策略是对的。

我还以为问的是，我有很多设定清仓价格的方案，按照这种贪心策略，小 R 能买到原价总和最大是多少，取到最大值的时候方案有多少。但是要是真的写成题意，也是 使小 R 购买糖果原价总和最大的方案数。这里感觉可能不是我的问题，是题目真的写得模棱两可。但也怪我不手玩样例。

我 怎 么 又 读 错 题 了。

:::info[考前读错的题]

• [NOIP 2024] 树的遍历
• [CSP-S 2025] 谐音替换 :::

md早知道点个“读题专家”了。

算了，现在已经没时间想正解了。而且卡贪心这种题，怎么像个构造题一样，这么恐怖肯定和 Ad-hoc 一样难做。还是老老实实打暴力吧。

大概打到 11:30，仅仅收获 20 pts。

这时候边上的大哥还在 O(1) 询问 CCF 的浮木。我没带水，只带了饮料，喝得喉咙有点齁。问监考员，说附近没有接水的。好吧。

当前得分 100 pts。

约 40 min (11:30\sim 12:10)

稍微想了一下这个 \text{mex} 到底咋搞，想了很久还是赶紧这个结论不太对。可能要先确定枚举子树的某个顺序，再那样是对的。那个做法正确性还是没法保证，而且现在也没有时间让我把那个做法打了，跑样例看正确性了。保险起见还是打个暴力吧。

一个肉眼可见的性质是，每个结点上填的数字应该不会超过它的子树大小。并且 i 号结点处产生的贡献应该最多就只能为 sz_i（都是感性理解出来的）。第二个结论显然；第一个结论因为如果你在某点填 >sz_i 的数，让它的某个祖先来填上 sz_i 这个数，那么你把这两个点交换位置，贡献至少增加 1 对吧。

所以我暴力枚举每个点的填数，然后再计算此时树的价值。考场代码时间复杂度可能是 O(n!\cdot n) 吧。但是跑样例没跑过。我输出了过程但是感觉都没问题，不知道为啥就跑不过样例。我想这下完了，难道我要把 T4 AC 了吗。

当前得分 100 pts。

约 40 min (12:10\sim 12:57)

完了现在没有退路了。T4 必须多拿点分。

想了一段时间突然顿悟：原来是枚举 q,i,l，来更新 i 处的答案，但 [l,l+区间长度] 里明明有很多个 i，这就是重复计算。我们为何不枚举 q,l，一次性对 [l,l+区间长度] 里的每个 i 都更新答案呢？

初步想法是，枚举 q,l，取 [l+L-1,l+R-1] 区间里的最值，设取到最值在位置 p，则最大区间和为 s_p-s_{l-1}（s 是前缀和数组）。然后用 s_p-s_{l-1} 更新 i\in[l,l+p] 的所有答案 k_i 即可。用线段树 O(\log n) 更新 i\in[l,l+p] 的每个位置（区间取 max）即可。 时间复杂度 O(qn\log n)，卡卡常甚至可以通过！

wok 天才啊！ 我赶紧开始打，然后发现不对啊，那 p\sim l+R-1 的位置咋办？它们不也能被更新吗？只是不被 s_p-s_{l-1} 更新罢了。

我灵机一动发现可以继续递归到 [p,l+R-1] 区间，继续寻找最值位置，更新最值左边的答案。如果数据过水，最值全在中间位置，时间复杂度 O(qn\log ^2 n)，但是很容易被卡成 O(qn^2\log n)。

然后我又发现不对啊，线段树什么时候可以对区间取 max 了？？？（至少我考场上写着写着发现不对劲，最坏情况下也能被卡成暴力取 max）我考场上觉得线段树也许不能区间取 max 了。只能写一个暴力取 max。如果线段树真的可以区间取 max，请在评论区告诉我，谢谢。。。

注：我在考后发现这样写的时间复杂度是 O(qn^3)，比暴力还烂。但貌似考场上我没意识到这点，着急忙慌地写了 O(qn^3) 。。。

考场上测样例时，跑测试点 1\sim3 的时候都很快，所以没意识到自己写了个 O(qn^3) 大劣解。希望 CCF 的数据也和样例一样水。

预估得分 5\sim 15 pts。

最后 3 min (12:57\sim 13:00)

仔细地检查了自己的文件操作，确认没有任何问题。

得分

呜呜呜肯定没省一了qwq。

注：成绩出了，省二。

NOIP 考后

Day 1 11.29

走出考场门，听到一些人在讨论：

“T3 好像对重儿子考虑即可，轻儿子全部赋 0 就是最优了。”

“T3 那题我写了个又臭又长的长链剖分。”

“你真敢写长链剖分啊？”

“唉，我 T1 的反悔贪心没调出来……”

“T4 可以莫队二次离线。”

打开 LA 群，发现大家都说这次好难：

“这场比赛比 NOI 2025 难。真的，我没开玩笑。”

“T2 不是写一个范特蒙德卷积就可以 n^2 以内了吗？”

我：“重儿子？长链剖分？反悔贪心？莫队二次离线？范特蒙德卷积？我考的不是 NOIP 提高组吗？”

看到大家都觉得难我就心里平衡了。到底多难啊？我打开洛谷，一看：

wok， 黄黑黑黑！（T2 后面降紫了）

我突然想起来自己考试的时候发现下发文件叫 "day1.pdf"。豁然开朗：一定是 dzd 不小心搞错了，把 NOI 的题目下发下来当 NOIP 的试题了。dzd 真好，知道我没有资格打 NOI，还把 NOI 的题搬来给我做。

已严肃完成今日“NOI/NOI+/CTSC”大学习。已严肃完成今日“National Olympiad in Informatics Plus”大学习。

冷知识：如果这次比赛太难，我们或许可以把 IOI 或者 NOI 的题搬来做一下。

Day 2 11.30

其实考完之后，也应该算是 AFO 了。但是还是希望不要那么痛苦地和 OI 分手，于是我和她吃了一顿分手饭，然后决定在最后一周把之前我们打算一起做的事情做掉。

Day 3 12.1

水了 2 道绿题。

Day 4 12.2

水了一道二维差分和二维前缀和。

求问：差分数组叫 cf，那二维差分的数组该叫……

Day 5 12.3

水了一道生成树。绿题 AC 200 祭。 :::align{center}

追忆

:::

Day 5、6

等等。我妈说我 whk 搞得好就让我再打一年？

Day 5 Day 6 各自 AC 一道蓝题。