why put shushu on B????? || NOIP 2025 游记

littlebug · 2025-11-12 10:11:42 · 生活·游记

推荐在 cnblog 阅读。同样地，洛谷不会实时更新qaq

退役喵~（真的qwq

没什么好说的，早就放下了…

祈祷失败……不过也没有完全失败，虽然数数放了 B，但是这是个紫题，大部分人还是做不出来的。

Day -17

祈祷 NOIP 不会把数数放在 AB（1/18）

Day -16

祈祷 NOIP 不会把数数放在 AB（2/18）

Day -15

祈祷 NOIP 不会把数数放在 AB（3/18）

Day -14

祈祷 NOIP 不会把数数放在 AB（4/18）

Day -13

祈祷 NOIP 不会把数数放在 AB（5/18）

Day -12

祈祷 NOIP 不会把数数放在 AB（6/18）

Day -11

祈祷 NOIP 不会把数数放在 AB（7/18）

Day -10

祈祷 NOIP 不会把数数放在 AB（8/18）

Day -9

祈祷 NOIP 不会把数数放在 AB（9/18）

Day -8

祈祷 NOIP 不会把数数放在 AB（10/18）

Day -7

祈祷 NOIP 不会把数数放在 AB（11/18）

Day -6

祈祷 NOIP 不会把数数放在 AB（12/18）

Day -5

祈祷 NOIP 不会把数数放在 AB（13/18）

Day -4

祈祷 NOIP 不会把数数放在 AB（14/18）

Day -3

祈祷 NOIP 不会把数数放在 AB（15/18）

Day -2

祈祷 NOIP 不会把数数放在 AB（16/18）

Day -1

祈祷 NOIP 不会把数数放在 AB（17/18）

上午打点板子，11:58 准时出发喵。

车上睡睡睡。

下午继续打板子，感觉图论和数学的板子都忘完了啊。然后桌子离插座太远导致没法充电，何意味。

约了几个人面积。

去试机，原来 5 考场在 4 号机房吗。喵了一眼发现左边是和我姓名同首字母的 Au✌🏻，看来位置是按照姓名首字母字典序排的。

注意到电脑上啥编译器都有，不过没有 CLion，vs 又不怎么会用，所以还是老老实实地用 devc++ 吧。不过倒是可以拿 vs 写代码的。

唉我去的时候已经开始试机了，所以面积失败…只能等明天赛后了。

Day 0

起床。祈祷。

祈祷 NOIP 不会把数数放在 AB（18/18）

去考场了。

考场外碰到了 @_ImposterX_ 并领到了徽章 /崇拜

正式赛

没在没让动键盘的时候动键盘，几个监考老师一直在那转来着。

密码是什么什么 dream。（!noip@Nov29,2025:dream

读题。

我【】你【】的出题人在 B 放数数。白祈祷了呜呜（

开 A，思考 eps 秒，发现同时选 x_i,y_i 一定是选那个 x_i+y_i 最小的，剩下的就选最小的 x_i 就好了，于是直接这么做。没过 candy3，哦需要考虑选若干个 x_i 的情况，那从小到大枚举选几个 x_i，剩下的全选最小 x_i+y_i，取个 min 就做完了。

于 30min 过掉了所有大样例，感觉不大会有 corner case，直接看 B 了。

在代码开头写下了：

// why put shushu on B?????
// why put shushu on B?????
// why put shushu on B?????
// why put shushu on B?????
// why put shushu on B?????

B 大概就是一个，统计「贪心的答案 \ne 01 背包的答案」的方案数，思考 20min，真的好无头猪，一点想法都没有 /yun。去看部分分。

先是会一个 O(2^n m) 的暴力，能过掉 n \le 10 的点。然后按照分值去思考部分分。发现 m = 2n-1 只需要判一下 w_i 全为 2 是否合法就可以了；m = 2n-2 是还需要判一个「只存在一个 w_i = 1」，复杂度是 O(nm) 的。然后是性质 A，发现这种情况是全部合法的，直接输出 2^n 即可。

然后去研究 m=2，发现需要分讨两种情况：

• 按照贪心策略，先是考虑只选一个 w_i = 2 的情况，容易注意到这个 i 只能是 n，而为了让贪心选到 a_n，需要把一个后缀都强制 w_i = 2，具体地需要找一个最大的 p 满足 a_p \le a_n/2，然后 i>p 的部分必须 w_i = 2，i \le p 的随便选，于是有 2^p 种方案。
• 然后是选两个 w_i = 1 的情况，容易发现必须有一个 w_i = 1 满足 i>p（不然贪心就选不到两个 1），剩下一个随便放。于是枚举 i \in (p,n) , j \in [1,i) 作为最后一个 1 和倒数第二个 1，方案数即为 2^{j-1}。然后要特判掉 i=n，直接给答案加上一个 2^{n-1} 即可。

凑一凑发现有 52pts 了！剩下的也不会了，开写。

第一件事肯定是写暴力，然后发现 01 背包是 O(nm) 的而不是 O(m) 的！那上面那一坨部分分是不是得假一堆 /jk

回去看了看，哦大部分还是不依赖这个的，那还好。

写写写，发现只有 m = 2n-2 的部分分影响了，观察大样例发现输出都差不多，进而发现都是 2^n 或 2^n-1，于是直接判了下 w_1 = 1 和 w_n = 1 两个情况，过大样例了。

看时间，发现 B 已经花了 2h 了，不过还剩下 2h 写 CD 的部分分，时间还是比较充分的。

开 C，是 mex 问题，想起来前几天刚和 @Synthesize 讨论了一个 mex 问题来着（但是并没有任何作用），于是在代码开头的注释中写下了 // tie tie @Synthsize /qq。

思考，但是发现只会一个 O(4^n n) 的暴力状压做法，甚至完全想不到 m 有什么作用，加点剪枝可以过掉 n \le 13 共 16pts，或许还能拿退火骗点分。打算先看看 D。

花几分钟重新理解了下题意，便有了一个 O(n^2 \log n) - O(n^2 q) 的暴力 + 预处理做法，直接预处理选择每个长度对每个位置产生的贡献，用线段树维护区间 min 即可，有 15pts。然后看特殊性质，发现 R_j \le 32 可以直接上面的做法，不过仅考虑长度 \le 32 的情况，复杂度是 O(32n \log n) - O(n \sum (R_j-L_j)) 的，也有 15pts。

其它部分分都不会了。

虽然注意到这个东西真的很像莫队，但是发现莫队的复杂度完全比暴力更劣啊（

于是先写 D，成功过掉两个部分分的大样例。

还剩 1h 写 C，根本不急，不过中间因为错误地考虑了 f_{u,S} 不可达的情况，浪费了点时间，暴力写完就只剩 30min 了。快速去写退火，本来以为计算整棵树的 mex 复杂度是 O(n) 的，然后发现并不是，似乎可以用 dsu on tree 做到 O(n \log n) 不过没时间了，于是直接写了 O(n^2) 的，毕竟退火也不是很依赖这个东西的复杂度。

经过一番调参，发现根本过不掉 n \le 40 的大样例，最大只能做到比答案小 [5,20]，还剩 5min 调不动了，查了查文件就摆了。

估分：100 + 52 + 16 + 30 = 198

出考场，准备面积，几个熟悉的来找了我，但是约好的两个没面过的怎么没来 /kel，我的位置和衣服都和描述的一样啊喵 /wq

最后人快走光了，实在等不到我也走了 w

教练说难度黄紫黑黑，？真 NOI Plus 啊（

高二的年级主任请吃了饭。笑点解析：我高一并且这次来打 NOIP 的高二有 5 个，高一有 15 个。

然后返程，因为电脑昨天在酒店的时候用没电了，所以没法玩小岛时光了，只好睡睡睡。

回机房，开始复现考场代码。A 过了，B 怎么 m=2 挂没了 /jk，问了问发现是没判 a_i = a_n，要寄喵 /ll

这下只剩 178 了，幸好测了测 CD 都没有挂分。

以下为在各 OJ 民间数据的测试结果：

洛谷：100 + 32 + 16 + 30 = 178 核桃：100 + 52 + 16 + 30 = 198 云斗：100 + 52 + 16 + 30 = 198

怎么说呢，虽然只有洛谷挂了，但是确实是挂了，数据稍微强一点就能把我卡掉了。。

不过 178pts 在 SD，应该还是有 1= 的吧？

和群 u 聊了会儿天，感觉好像比较弱的打的比较好，反而比较强的打的没那么好了，果然 B 正解是冲不得的。

Day 1

会放不到两天的假期（明天晚上开学）。

所以今天要玩一天喵。

然后游记一直在咕咕咕……

uno 好玩 qwq

Day 2

终于来写游记了 w

回忆录会补的，不过可能需要等一段时间啦qwq，补 whk 的时候会抽空写喵！

Day 3

开始 whk 了喵（其实昨天晚上就开始了），感觉 whk 并没有那么枯燥无聊，反而是很好玩的。

可能是因为，高中 whk 对我来说会比较困难，但并非完全不能做，经过一番思考还是可以做对题的，所以会感觉到好玩 /fendou

Day 4

出成绩了，教练告诉我说拿了 198pts，并且 SD rk39！

这个分数是实在没想到的，感谢 CCF 数据和大样例一样水。名次就更是没想到的了，看来暴力打满优势巨大啊！

Day 13

回归 whk 后的第一个周末，发现现在无聊的时候，对于 OI 知识，可以随便想做啥做啥了，不用关心有没有用，是否浪费时间，退役了就是好（？

回来发现不会打字了 ww，这就是坏处吗 /kel

断断续续地，用两周部分自习课的时间，把回忆录基本上写完了——

不仅仅是 OI || 我的 OI 生涯回忆录

（洛谷 ver.

。