精英培训。

在所有选手中 NOI 排倒数第五，只要不垫底就赢了。

早上来了北京，感觉非常冷，而且很干燥，然后因为早上起的比较早，所以中午睡了一会。

下午就是试机和开营仪式，发现电脑上面字体很小，但是调整分辨率以后会比较难受，就是会很模糊，所以干脆不管了，反正把 vscode 和浏览器开到 $200\%$ 是差不多的。

然后就回去了，感觉酒店还行，但是问题就是非常热（然后开冷空调吹的是热风），那么怎么办呢，我和 @deepskycore 试图开窗，发现我们都不会开窗，后面 @ningago 来了之后用力一下就开了，于是就好多了。

晚上正常时间睡觉。

$0+100+0$，rk51。

感觉早饭还是不错的，能吃饱，然后坐车到清华，直接就开始考试了。

一看题，发现 T1 是期望，然后想了一下没有显然的部分分，然后直接跳了，去看 T2，想了一下发现 $m=0$ 的部分是非常简单的，直接先按照颜色贪心匹配，然后再统一匹配即可，写了大概 15min 拿了 45pts。

然后考虑优化，发现直接对每个颜色开一棵线段树维护括号匹配，然后再对没有被选的开一棵线段树就可以了，后面想了想加上了 $4$ 个 set，维护每个颜色每种类型的位置。

感觉是写麻烦了，写了 1.5h 5k，但是还好，没怎么调就过了。

然后想了一下 T1 和 T3，决定先开 T3（我也不知道为什么，可能是看到期望就不想开了）。

然后想了半天想出了一个用差为 $1$ 的线段去卡这个界的做法，没想过具体的询问次数，但是感觉不是很多，然后写了一下，细节想了挺久的，然后发现交上去过不了，然后我瞎试了几个，直接用 $k=\frac{2}{3},b=\frac{1}{6}$ 给卡掉了，发现算法是假的。

然后就有点急眼，时间也不多了，尝试搞了一下 sub1 也没有搞出来，出场感觉垫底了，发现还是有不少人也差不多是 $100$，看来没有搞 T1 是最大的败笔。

下午听了一下讲题，感觉 T1 看起来也不是很难，感觉搞一下应该可以会一些分？

讲题之前的“参观校园”感觉比较难受，感觉就是罚走，腿要废了，CCF 看来是比较喜欢让选手在休息时间走路的，NOI 的 day1.5 也是。

$97.33+11+100$，rk17。

虽然看起来分挺好看的，但是打的过程非常红温。

开局先看 T1，发现是个交互，然后想了 5min，把前面两个 sub 给写了，先拿了 20pts，然后开始思考正解，想了一会就发现了距离 $\leq 2$ 的性质，然后一直不知道怎么用，自己手搓了若干个伪算交上去都只有 20pts，然后时间已经过去 1h 了，然后自己手搓了一个拍子，用随机数据拍，发现我写的算法基本上都可以直接拍出来。

然后还是不会，从头开始想，又写了一些算法，还是错的，直到 3h 的时候总分还是 $20+0+0$，非常红温，感觉要倒闭了，中间看过一会 T2 和 T3，感觉都不是很好做的题，一眼没啥思路。

然后上个厕所冷静了一下，强迫自己不要管 T1 了，专心想 T3，看看能拿多少分，因为这个题和最优方案差的哪怕比较远也可以拿几乎一半的分，所以就当成交互想，试图只利用一些信息。

然后我就发现，我具体的拓扑序似乎不是很重要，根似乎是比较重要的。那么一条边如果我两边都选过了，那么这条边就绝对被 fix 了，那么就有一个很显然的 $O(叶子个数)$ 的做法，直接写了之后获得了 $50$ 多分，然后我开始想怎么优化。首先分析样例 $2$，因为这个样例我用了 $3$ 次操作，但是实际上只需要两次，那么我就发现，我只需要舍弃一些“到最近的度数 $\geq 3$ 的节点距离为 $1$”的叶子就可以了，然后我画了一下，发现如果舍弃了两个同一个父亲的叶子，就会无法分辨，所以我加上了这个判断。

然后这一下就获得了 $91$ 分，感觉只需要再优化 eps 次就是正解了，那么我想了一些类似菊花的东西，发现我本来会认为它需要 $n-1$ 次操作，但是实际上只需要 $2$ 次！因为我可以在第一次遍历到的时候顺序扫这些叶子，第二次倒序扫，那么就可以完全区分了，加上这个优化后就拿到了 100pts。

这个时候感觉 T3 很简单啊，然后继续搞 T1。

又写了若干伪算之后，我开始考虑能不能类似 sub2 做，因为直接用 sub2 的做法只能找到一个可以到达所有点的点，但是有一些是他不能一步到达的，那么我就想，是不是如果这个点是错的，那么答案只能出现在这些点里面。

于是我就写了一个，每次按照 sub2 的方法找出一个点，存起来，然后递归找所有能到达它的点，最后再对所有存起来的点 $num^2$ 求出它们的关系，找出出度最大的那个点。

写完之后发现直接过掉了 72 分，感觉非常震惊，因为我也不知道这个做法的道理是什么，然后我就试图压操作次数，先猜最后那个 $num^2$ 是不需要的，可以直接取最后一次取出的那个点，然后交了一发发现……没有变化？

然后我加上了一个记忆化，就获得了 80 分，然后由于感觉里面跑的太多了，差不多是 $4n$ 级别，然后这个时候只有一个小时了，就没有去思考有道理的优化方法。然后就加上了一些没有道理的优化方法，比如设定一个阈值 $C$，当感觉继续递归会爆这个限制了就不递归了，先尝试了 $C=1000$，发现直接错了，然后试 $C=1500$，获得了 $88$ 分，然后看时间不多了，就先去看看 T2。

看了一下，感觉菊花的情况符合条件的树不是很多，感受了一下要么是链，要么是只有根的度数 $>2$，那么对等价类计数，就只需要写一个背包就可以拿到 $4$ 分了，然后发现还有一个 $o=1$ 的链，这个显然直接输出 $n^{n-2}$ 就可以获得 $7$ 分，加起来就有 $11$ 分了。

然后回来只有 10min 了，去调了一下阈值，一个一个试，发现 $C=1050$ 的时候可以获得 $97.33$ 分，然后也没有时间试了，就结束了。

出场听说 T1 直接随机找一个点，然后做就是对的了，然后大家都很快都切了 qwq，感觉这场的 $1,3$ 都是随机区分啊，然后 $2$ 想要拿分又很困难，所以感觉整场的区分度非常不好。

然后又因为起的比较早，出场就开始头痛，然后考试又很消耗精力，所以好久才缓过来。

下午的讲座感觉实在很困，就直接睡着了/xk。

$20+30+71.57$，rk82，好笑的是，三场比赛 rk 加起来刚好是 $150$。

真爆完了。

上来先看 T1，做了一会发现只会一些复杂度很高的想法，然后也不算好写，那么就先扔了。T2 是抽象题，也扔了。

于是开了一下 T3，想了一下发现会了 $O(n^2)$ 的做法，然后由于没有很多分所以没写，然后继续想，看到数据范围大概是 $n\log n$ 级别的，就想了一下点分治，发现可以找出重心，并且可以找出最大的一棵子树。

然后就不知道怎么做了，一直不会菊花的情况，因为我这样做只能每次找出最大的子树，但是代价是所有的子树和，那么还是 $O(n^2)$ 的。

然后想了若干分钟都不会优化这个东西，所以就想了一下 $O(n\sqrt{n\log n})$ 的做法，感觉直接对这个东西阈值分治就可以了，如果度数很大就直接分治 $O(n\log n)$ 单次。

然后写了一下，获得了 $71.57$ 分，然后就没有更高了，后面想过直接找出一个独立集，那么用 $O(n\log n)$ 次就可以求出它们的所有临边，但是我没有意识到这个东西是可递归的，所以就放弃了，其实再加一步就做完了。

这个时候时间已经不是很多了，于是去看 T2，发现 T2 的数据范围很小，但是值域很大，然后就想了一下，感觉本质不同的值不会很多，那么写了一个爆搜，但是由于实现的不是很好，只能跑 $n\leq 5$，再大的就会炸，加了几个剪枝都没剪下去。

最后把 T1 的 20 分打了就结束了，其实这把每个题如果思考积极性再高一点的话都可以多一些分的。

总榜 rk58，精英培训 rk22，太菜了，还得加训。