NOI 2023 游记

Day -7

坐了10h+高铁后到达成都！

Day -6~Day -2

赛前集训！还看了两场hdu多校的题，不过贡献几乎为 \(0\)。第二场的计算几何题写了一个小时，调了一个小时没过然后下播了。赛后改了一车东西才过。

成都的外卖怎么都这么辣！

Day -1

进校！感觉cdqz的环境和华二昆山的没法比，不过鉴于后者是国际学校也就不足为奇。

今年好像没有狼人杀环节。大概是因为没有一个举办狼人杀的中心？

交换徽章环节过后去吃饭，晚饭是自助餐，不辣的菜挺多的，好评。

睡觉时空调有滴水声。

Day 0

早饭比起预期略逊一筹。

开幕式节目中最引人注目的必然是成都七中杰出校友祝福NOI2023，其次个人认为是《变脸》。开幕式完查了学考的分，语文拿了C，符合预期。

中午回宿舍背了一下笔试并去在线题库中测了一下，没挂。

试机时打了个网络流，但是听说有自测工具后转而去研究自测工具，发现它大部分评测状态还是较为准确的（不像去年开了\(3\times 10^6\) 个deque后MLE报成WA），但是除以0好像会报WA而非RE。

15：00开始做笔试。做单选时有一道问丢失密码条扣几分的题，多选时看到了一道问选手考试前不能干什么的题。

"提示：NOI 笔试题目将完全出自本题库。"——《NOI 2023 基础知识题库》

不过由于对去年的笔试题还有一点印象，最后还是做对了。今年没有像去年一样不公布笔试成绩。

网络流打完后随便测了几组数据发现没写对，又调了一会才离场。

Day 1

开考后先翻了一遍题，看到了两个影响不会计数的我心态的 \(\bmod 10^9+7\)。

T1一眼容斥，花 \(40\) 分钟写完后调了一会过了所有大样例，然后用自测工具跑了一下，结果自测工具卡死了。

找工作人员重启自测工具后评测结果变成了No Score.，我认为这可能代表这是样例所以不得分，但是把代码改成会WA的版本后结果也没变。一段时间后工作人员说这是个bug，已经修了。

看T2后除了第一个条件等价于给定虚树别的啥也没看出来，没多久后决定开始拿部分分。先看 \(k=0\) 发现不会，于是看 \(n=1,k=0\)。发现可以按照编号从小到大加点设计dp，编号最大的点要么插在边上要么当成叶子，于是答案就是双阶乘。再一想发现 \(n\neq 1\) 也一样做。剩下的分主要是分类讨论，拼了点就 \(70\) 了，然后去开T3。

一开始 \(36\) 分直接容斥就行，但想特殊性质A时想了两个假做法后才会，拼到 \(52\) 后开始检查。

这T2怎么测试点 \(1,2\) 的数据范围不被后面几个测试点包含的。

花 \(30\) min 写了搜索，也没测极限数据。预估得分 \(100+70+52=222\)。

查分前一直在轮流辐辉王格林和前辈。三点准时差分，发现没挂。

晚上开了把随机。

Day 1.5

寝室里就一个人去嘉年华，于是我待在寝室里把随机打完了。

别的时间主要在聊天。下午去参加了一把狼人杀，抽到了不会玩的白狼王，被迫在狼队劣势时爆了，最后还是输了。

睡前有人声称明天考字符串就下播，但我认为明天不会考，于是和字符串相关的东西一点没看。

Day 2

string。弱势项目。

看到T1后开始想能不能点分治，然后发现点分治等价于dfs，于是就会了。

T2先看特殊性质B，发现满足该特殊性质就可以把比两个子串字典序大小转成比一个前缀和一个后缀的字典序大小，看上去把正反串拼一起建SA就能转二维数点。但问题是我不会SA。

回忆了下SA是倍增+基数排序。一开始先写了倍增+快速排序+主席树的代码，发现运行时间在时限外面，但我想不起来SA模板中的基数排序怎么写了，于是用了vector，还是挺慢，把询问离线后才跑进去。而特殊性质A只要处理 \(l\) 较小的情况就可以和特殊性质B一样做，就这样拿了 \(72\) 分。

T3写了个 \(\mathcal O(3^nn^2)\) 的dp，\(w_i=1\) 时观察到合并为二叉树结构而所有叶子等价，可以区间dp。

最后稍微改了改这个dp再加个随机交换，看看能不能多跑过一点分。

最后1小时对拍了T1，没发现问题。

查分前继续辐辉王格林和前辈。

差分发现T3随机交换多了10分，别的没挂。考字符串就下播的人过了字符串题。

经过交流发现从特殊性质B到正解要减掉的字符串都是回文串，用Manacher+二维数点就可以处理。但是直接枚举的人也过了。

查完分教练说够了，于是回寝室补票并开始打钢铁之魂100%完成度。

Day 3

除了竞技场3和神居以外的部分都打完了，花了差不多七个小时。闭幕式就图一乐。

总成绩全寝室垫底，或许因为计数和字符串都是我的弱势项目。

不过这是正式CNOI比赛第一次挂负分。

也会是最后一次。