8129 16 9 7 12 0 0 0 2 1 0 2 3 6 0 2 0，17 9 6 6 9

· · 生活·游记

本来预计睡到十二点再起，但是发现自己九点钟就起来并且毫无困意了。爬起来写了点板子。

十一点半被拉去吃饭然后前往学校。这次做坐大巴的人似乎比之前少，大巴都比以前小很多。

大概是一点到达金盆岭，和弹出、Harmonic 和 mian_ku 在附近随机游走。遇到了一个不知道干什么的女的，弹出直接宣称我们是来旅游的，我直接走开了。经过比对准考证发现我和弹出和 Harmonic 都在一个机房，这么牛？

一点半进入了学校，发现了一个雷霆 hpy 大头：

和大家一起在操场边坐了一会。看到操场上一个大人踢足球逗小孩玩，一脚把足球踢老远然后让小孩去捡，太几把好笑了。

两点开始进场，发现教学楼前已经聚集了大量人类。进机房打了一个缺省源和快读，配了下 vscode，测了一下速，发现 1s 可以跑 3e8，这也太牛了。不知道 CCF 机子能不能更快。

开考看题。本来准备看完四个题再写代码，结果看到这个 T1 给我唐飞了。那还说啥了，先写了再说。

花费 <5min 写完代码测一发直接通过大样例了，不管了。下一题。

我操这啥几把题面，看不懂。那就把后面两个题也看了吧。T3 像是一个可能能做的题目，T4 看起来是大 ds，那就该拼拼 T4，然后看看能不能冲出来 T3 了。

不管怎样先解决一下 T2，反复认真研读了一下题面发现一些很变态的事情：

感觉题面神秘的点也太多了，先写个暴力看看读对题没有吧。我操我他妈 dij 怎么全是 inf？？调了几分钟没调出来，直接写正解算了。

写正解的时候发现我复杂度有一个 O(nm)，看了一眼 2.5e8 似乎还能接受？写完测一下大样例吧。花费 5min 写完了代码，好像直接通过所有大样例了，大样例都挺快的，直接扔掉了。这个时候是 15:00 左右。优势在我！

仔细研究 T3，发现可能是这个题？尝试使用路径编号和之差 =1 刻画了一下，写了一下立方通过了大样例。但是思考了十几分钟发现做不下去了。

在草稿纸上画了一下发现每个合法路径都只有一个 x \to y \to z 和 x \to w \to z 这种结构的状物，应该可以枚举这个东西。剩下需要解决的问题就是 dp 出每个点为开头和结尾的两点之间路径唯一的个数了。

推了几分钟发现有几个地方的转移没推明白，不管了先写了看看怎么样吧。写出来发现完全无法通过样例，那么我们直接开始枚举每种可能的转移，经过若干分钟的枚举，它居然通过样例了！！！！！

但是它似乎没有通过 migrate3.in，在第一组测试数据上输出了一个 8200 左右的数。赶紧写个拍子，还好之前写了暴力。

根据拍出来的数据调了一下总算是过拍了，我们现在已经得到了一个 O(n^2) 的做法，只需要将其优化就可以了！

对着代码一行一行改又蠕动了半个多小时才改完。migrate3.in 感觉神了，写错了一万个地方全都是这个样例调出来的。笑话是中途我以为自己需要写一个二维数点，写完发现是一维数点，然后愤怒地删除了树状数组板子。

看了一眼现在是 16:50 左右，还有一个半小时，优势仍然在我！

开始做 T4，初想法是直接二分，然后考虑怎么 check。我直接枚举两个连通块的根，然后我发现我需要计算使得子树内合法需要最少点数是多少。

这他妈咋算？？我的平方怎么变成立方了？？？？

几把的，不管了，先写了再说，30 分是不是也不算少了来着。写了一半发现我漏讨论了一个根再另一个根子树内的情况，怎么又爆了？

在草稿纸上紧急画了一下发现是好修的，只需要把下面的子树挖掉就行了。写了一万年终于通过了样例，然后测了一下 hub3.in：

17
9
6
6
11

？？？？？？

抱着侥幸心理把最后一组单独拉出来测了一下，发现输出还是 11。玩几把蛋了，这我咋调。这个时候已经 18:00 了。

纠结了 1s 决定赶紧写拍子。在我写暴力的时候监考过来宣读了 T2 样例解释的问题。我只想说你能不能别读了，我真要调不出题了 /ll /ll /ll

在 #67 拍出来了一组数据，手玩了一下发现怎么我构造不出解？让暴力输出一下方案发现我暴力写挂了，判两个联通块错了。

这个时候我的心态已经接近爆炸了。赶紧继续挂着拍子。好在拍出来的反例是对的，我发现我判两个根中间的点是否合法的时候出问题了。紧急修改了一版发现还是不对？？？直接怒了，改成遍历每个点终于对了。此时 18:20。

检查完文件直接在 T3 注释写了点小文字，然后在 T4 注释默写追忆。不过怎么默不完了，草。

估分 100+100+100+30=330。

出考场询问得知弹出 350，Harmonic 215，弹出还是太强了。水群发现好像大家都在喷 T2 题面和 T3。

出来之后面积了 雨ノ宮 あめ 并获得一张小卡片！然后去渔人码头食用了一些烧烤。

其实感觉 T2 O(nm) 有跑不过去的风险。询问了一下 gza，他说 CCF 机子很快，那就先相信一下。祈祷不要挂分。

我能去 WC 吗？我问我自己。