NOIP2025

· · 生活·游记

感觉之前写的东西只能算是考场记录，那就补充一点东西吧。

11.22

最后一个周末，心血来潮买了魔裁玩玩，果然少女乐队的受众终究难逃这游戏的魔爪。玩了 2h 后觉得挺和我口味的，考完 noip 后一定要爽玩。

没救了，怎么这么喜欢看姛互撕。

11.25

最后一场 dmy 模拟赛，果然又是依托，本来半小时过前两题还以为是信心场，一看 T3 瞬间倒闭了。什么叫让我做基环树森林计数，还限制度数？还限制是二分图并给定左右点数？做个鬼啊，跳了。T4 怎么是神秘数论，7 pts 的暴力分也太高了，还是滚回去做 T3 吧。绞劲脑汁想了个四维状态的 O(n^7) dp，我日怎么和暴力一个分？！那还是打暴力吧，欸等会这题暴力怎么打？？？

同学，noip 不是四个半小时吗？为什么你的文件创建时间都是9点前？

不出意外被 T4 的 7 分区分了，这鬼比赛打了干嘛？浪费人生。

T3 是双重容斥+生成函数，T4 是算复杂度要用积分的邪恶题，算出来是是 O(\frac{n^{\frac43}}{\log n}+\frac{n^{\frac32}}{\log^2 n})，真是优质比赛。

不过 T3 jly 的做法我居然听懂了，考场上我一定要像这样推生成函数帅气过题！

11.26

最后一次互讲，选了之前模拟赛被毙掉的 T4，但是讲的时候 mlk 好像能精准预判我接下来要干嘛，看来还是太简单了，幸亏毙掉了。

讲前给 yjc 选的题写了个 O(n^3)，然后漂亮地通过推生成函数优化掉一个 n，但仔细一想用组合意义是不是更简单？不管了生成函数就是爹。

嘻嘻，考场上我一定要推生成函数帅气过题呀！

现在回想起来 zlt 讲的题勉强算是支配对，买下伏笔了说是。

然后讲题过程中机房停电了，电脑重启完东西全没了，这下被迫考前不颓废了。

11.27

最后一场联测，感觉是某个中学为了整别人心态。这鬼 T1 题面写这么抽象是给谁看的？但好像除了我其他人都能看懂。。。然后这 T2 也太难了，确定难度不对标 noip T4？

甚至 2.5h 才做完前两题，还好 T3 对上电波直接想到第一步转化了，然后是对一个基环树哈希之类的，魔改一下树哈希随便做。但是过不了最后一个大样例，诡异的是我的基环树怎么有 >1 个返祖边？noip 前还不会基环树找环是不是没救了？

结果是比赛结束都没调出基环树找环，但问题远不止这些，我树的哈希值居然全是 0，但是交上去有 70 分，数据还是太用心了。

赛后换了一种找环方式就对了，何意味？

11.28

最后一天，sana 总算回机房了，怂恿她去打 dmy 比赛失败了，但是 yhy 成功忽悠 gen 去打了，gen 英勇地做出 T1 后杳无音讯，想必是对这场比赛好评如潮。

上午在随机做题，但主要是让自己不要乱想，果然考前还是会紧张，更何况之前考得都不好，压力更大了。

下午机房清洁，所有人被赶到操场上了，足球启动启动！球技果然比不过 sana，这人不应该好久不踢球了吗，完全没生疏啊。最后一球让她打了个超帅的进门，具体忘了，给这人爽飞了。

回机房后隔壁机房的小朋友们迁移到这边了，发现他们装备好强，都是我没见过的机械键盘，坐我后面那个人 vscode 背景透明度超低，完全看不清他的代码。

最后一晚了，干什么呢？好像写题也阻止不了我胡思乱想了，于是情况就变成了一边打板子一边幻想，真是的。

依旧默写 tarjan 三部曲，点双从来没一次写对过，不过自从我参赛以来就没在考场上写过这个。

开摆了，看看魔裁的切片，美滋滋。

11.29 正赛日

大概 7:30 起床，前一晚睡得不错，起来很精神，但是做了很奇怪的梦。梦里在下很大的雨，风很大，天上的云像漩涡一样在转。不知道有什么意味，希望不是，但大概率是我退役的前兆。

去食堂购买装备，上次没让我把巧克力和咖啡带进机房，这次打算再试一遍能不能带。到了机房发现没网，果然是打模拟赛前断网了。不过 maojun 的笔记有本地的 md，于是一群人围在他座位后面看，抽象。就剩半小时了还复习什么，正好我浏览器缓存的视频还能看，美美颓废了一会。

去考场了，唉还是不让我把巧克力带进去，生气了，出去外面吃还是太离谱了。

出师不利，压缩包密码输了三遍。T1 一眼鉴定为贪心，还好不是去年的 T1，难度和提高组 T1 一样吧。但是到 T2 就冲不动了，虽然一开始就意识到非法状态末尾是 121 这样的，但是当时比较脑抽，跑去数合法状态了。然后细节怎么也想不对，过了半个小时也不会做，由于当时对 T2 的判断是简单题，有点破防了。总之后来发现数非法状态就很简单了，然后就是推推组合式子对吧？然后推出来一个 n^3 的东西，太着急了没看出是范德蒙德卷积，又浪费了半小时时间。

一个半小时总算开到 T3 了，读完题面立刻会了 n^4，算了一下常数感觉能过 n=360。大概是设 f_{u,i,j} 为 u 子树内 mex 为 i，还有 j 个点没有确定。然后就不会做了，完全编不出来和深度相关的做法，遂决定跳题。开 T4 之前手搓了个 n=360 数据，本地 1s 不到，那就放心了。

T4 思考了一会，发现可以分治找支配对，然后就是要做 n\log n 次区间取 \max，把区间按权值排序然后并查集一下，用基排就能 qn\log n 了。但是写出来发现极限数据跑 10s+，气笑了，那岂不是仅比暴力多 eps？想半天不会 O(n) 找支配对，于是开始卡常，1h 后卡过了若干特殊性质，但拼起来分数还没上 300，无语+摆烂。

出考场查询环节。某人太超模了，我多训一年打不过他退役一年/ll

GF 没人 AK，但好像有三个人过了 T4，和 yhd 交流了一下，他会 O(n) 支配对，但是区间取 \max 写的是带 \log 做法，那我两做法拼起来不就对了？不过他本地极限数据 2s+，想必是能过的。

很多人被 T2 创飞了，看来我是幸运的。从去年 noip 到今年 csp-s 发挥的都不尽人意，这把算是发挥出全部水准了，没有遗憾了。

有个小插曲是，我回家复现了 T1，交洛谷上 90 分，还好是我复现时写挂了。最后能有个好心情回归 whk，真好。

没有遗憾个鬼，我草我基排个蛋啊，都分治了顺便把 ckmax 做了不就行了？qnlog n 都写不明白，超级无敌暴怒！

小 M 真心希望大家不要重蹈覆辙，以为支配对必须先找完再求答案。

最后是 100+100+48+45=293，省排 20~30。

11.30

事已至此，先玩会游戏吧。花了一个晚上加一天玩到二周目中期，说实话这游戏作案动机一个比一个离谱，推理部分勉强能接受，可能是我从来没玩过推理类游戏的原因。不过画得真好看，还有就是轻白。不太会写游戏评测，就这样吧，总之十分推荐。