又来打 NOI 了。

Day -1

今天上午来报的道，感觉送的编织袋子不如去年的帆布包，没有很好的办法把换到的徽章送出去。

之前 WC 看过寝室了，感觉环境还好。

中午吃的学校食堂，感觉伙食很好，比 WC 的时候好很多。但是提供的饮料只有可乐雪碧和酸奶，但是我一喝碳酸饮料就会打嗝，而且打得很难受，所以希望有一些别的饮料。感觉去年 NOI 那种冰红茶或者果粒橙就挺好的。

由于宿舍没有插电的地方，导致我不能够蜗居在宿舍了，于是下午找了个自习室自习。

今天下午主要是翻了翻 OI wiki，看看有没有什么遗漏的地方，结果发现自己不会写 KDT 了（虽然但是，我感觉 NOI 不大会考 KDT）。（upd on Day1:貌似 D1T3 可以用 KDT 做到 O(n\sqrt{n})）

晚饭和午饭一个档次的，挺好。

和 MLE 打了一会儿乒乓球，然后就回到自习室了，先把今天的游记写了。

Day 0

上午开幕式，今天是第 41 届，所以是 40 周年，什么植树问题。

感觉开场的那个 NOI 满屏幕乱飞比较抽象，但是比较牛。

民乐表演比较牛，唱歌比较牛，街舞比较牛，音乐剧比较抽象。

顺序，结构，程序，循环

dzd 发表了比较厉害的演讲，讲了 NOI 40 年怎么办下来的。全文体现了 dzd 的刚正不阿，不为权钱所动，被全国人名吊起来打的光辉事迹。

下午是试机+笔试。

试机题目居然换成 NOIP2023 的了，比较牛。

笔试的时候，最开始不知道是不是工作人员唐了，直接把答案都填上了，后来紧急撤回了，延迟了 15 分钟考试。

还好没有挂分，目前得分 100+5。

下午复习了一些板子，晚上看了看以前写的总结，比较早就睡了，因为明天是 Day 1。

Day 1

省流：考的一般。

开考前坐我右边的右边的人貌似动了试卷袋，被叫走了，然后又回来了。

最开始看 T1 没有什么思路，感觉很神秘；T2 是一道交互题，感觉不是很难；T3 读懂了题，感觉是一个贪心+数据结构题。

回来想了想 T1，发现可以用双指针对每一个 l 求出最大的可能的 r，然后直接 O(1) 回答。考虑维护上面的在这个过程，可以用双指针。现在的问题变成如何 chk 一个区间是否满足条件。

发现乘上一个排列就不关注具体的每一个元素了，相当于是要对每一个元素出现的集合进行匹配（或者说所有元素出现的集合构成的集合要相同）。里面每一个集合用类似字符串哈希维护，外层套一个 map，时间复杂度 O(n\log n+q)，感觉很对。用 selfEval 测试，发现 selfEval 上有 20 个测试点，感觉比较牛。结果测出来是 80 分，结果发现是 n\le 2\times 10^5 的挂了，感觉 O(n\log n) 的部分常数比较大，决定到时候改一改。

感觉 T2 的题目描述方式很 JOISC 的风格，就是数据范围写一个很松的限制，然后再在计分方式里面写到底怎么得到最高分。

subtask 1 是简单的，直接问出两两点对的最大值即可；subtask 2，容易得到一个 t=20，s=n-1 的分治做大，就是使用淘汰赛的结构两两匹配。

但是 t 太大了。考虑 subtask 1 的 t=1，感觉很牛，启发我们不一定要两两匹配，可能是用一个更大的长度 k。考虑使用 DP 求出比较优的决策序列，发现是 2 2 2 2 3 6 19 183。比最优解多了 16 步，会扣 18 分。

然后又搜了搜，发现可以再优化一些，之比最优解多了 3 步，但是要扣 9 分。换了其他方式搜了搜，发现只能做到这个大小，就先暂时放弃了。打了 91 分。

回头优化 T1，把 map 换成了哈希表，复杂度是 O(n+q) 的，跑得很快，感觉很牛。

时间大概到了 10:20 的样子。感觉今天状态还行。

感觉 T3 比较抽象，于是开始考虑部分分，发现 A 性质可以用类似二分图的方式处理。于是开始考虑逐位贪心然后 chk 是否合法。

发现 B 性质可能可以用 2-SAT，但是只会做 O(nm) 的。

发现 A 性质告诉我们只要所有还没有满足要求的路径没有确定的边数都 \ge 2，就一定有解，于是发现了一个 O(nm) chk 的方式，成功获得 O(n^2m) 做法。

感觉里面的 O(nm) 可以优化到 O(m\operatorname{poly}(\log n)) 的，感觉没有多少前途，所以就没有写。

最后赶了一个 B 性质的平方，然后就只剩下十几分钟了，T1 没有对拍，不知道会不会 fst。

期望得分 100+91+40=231，感觉可能还行。

出来之后听说金牌线是 250，还有什么好多人都 AK 了。这些复刻 NOI2021 了，感觉自己寄掉了。

遇到 MLE 结果他 238，和他讨论了一下题目，发现我 T3 实现的那个 chk 可以直接做到 O(nm)，这下我不成小丑了。

最后查分的时候也没有挂分，100+91+40=231。后来据说这个成绩还可以，但是在队线下面，难过。感觉 Day2 冲一冲可以拿金，这下要加油了。

下午讲课，结果 T3 貌似有各种奇怪做法拿高分的。这下我成唐氏了。

晚上 xqz 找我们开了个小会，总结了一些今天考试时的失误，为后天的考试做准备。

Day 1.5

居然恢复了社会活动，感动。

去三峡博物馆转了一圈，但是我对这种东西不是很感兴趣，所以也没有太认真去看。就当是放松放松了。

下午和晚上准备再复习一轮，希望明天能够翻盘。

生死有命，富贵在天！

Day 2

省流：中规中矩，但是似乎还可以。

开考之后通读题面。发现 T1 可以使用辗转相除的方式做到 O(\log n) chk，通过观察发现 ans 不是很大，所以考虑将 chk 的过程倒序过来，相当于直接 dfs 出答案。

时间复杂度是 O(ans) 的，代码就 300 多 B，跑起来很快，直接拿下了 90 分，感觉很好，就扔到一边不管了。

看 T2，发现这个统计的方式很奇怪，记 f_i 表示 i 到根的路径数，发现 f_i=\sum\limits_{j 是 i 的祖先}c_{i,j}f_j，但是 c_{i,j} 的值是从叶子到根的了，但是 f 的转移是从根到叶子的。发现很奇怪。

我想到了联考之间的题目，对于每一个途径分配一个对应起点系数，求所有可行路径的系数和，发现就是要求 \sum\limits_{i=2}^nf_i\times val_i，发现可以用线段树合并 O(n\log n) 处理，然后将这个过程撤销回来即可。时间复杂度仍然是 O(n\log n) 的。

但是要写线段树合并和后缀推平以及他们的撤销，感觉不是很好写，写到大概 10:00 的时候写破防了，于是去看 T3。

发现 T3 是神秘图论题。众所周知，我图论一点不会，而且这道题非部分分有 55 分，所以直接去看暴力。发现特殊性质 A 可以直接 O(n) 缩点，特殊性质 B 可以 O(n^2) chk 每一个点是不是一类点。打了 25 分。

然后回去调 T2，11:30 的时候终于调出来了。目前得分 215。

最后的一个半小时，检查了所有代码之后开始尝试在 T1 和 T3 中拿到更高的分数，但是没有成功。

最终得分 90+100+25=215。

出来之后感觉自己又是大众分，但是我总有一种感觉，我可能金了？

下午查分之后大概知道了结果，231+215+100+5=551，多半是金牌，但是被乐零和火大等诸多大神薄纱，呜呜呜，鉴定为 D1T3 唐了。

讲题的时候听过 zak 300+300，非常恐怖。

晚上有嘉年华，五个徽章可以兑换一只唐龙，在速通了诸多活动之后也是喜提唐龙一只。于是速通了五个活动获得唐龙一只。

颁奖日

上午是《我与NOI》系列活动，没有我们学校的。

下午颁奖，其实知道上台领奖之前，我的心情有一直很平静。但是真正的站到台上的时候，心情还是无比的激动。

平静可能是因为这段时间我一直认为自己是能够拿到金牌的，激动时因为我真的拿到了金牌。也是完成了一个目标，圆了自己的 OI 梦。

（认识我的人都应该知道我是谁，就不打码了）

下午教练和班主任都来了，教练希望我后面的国家队选拔也认真考，希望能冲国家队（虽然但是，我感觉比较困难）。

但是，说不定呢？