省选游记（退役记）

· · 个人记录

Day 0

起床战争！和小学生玩，很有意思。

有个叫 sexyfish 的说自己是孤儿，感觉很可怜，希望他能尽快和父母团聚。

看了一些板子，发现自己不会写线段树。

我要进江苏省队 /fendou

晚上看了看ツンデレ主题的睡前小故事。我草，ツンデレ天下第一。

Day 1

开局读 T1。彳亍，高难度模拟。不会做。

看了下 T2 T3，感觉 T2 > T3。

仔细想了下 T1，发现读错题了，原来只需要从 x 往左往右扫一下就好了，区间扔到端点上，时间复杂度 O(n)。

回头看 T2，转化题意后就是选出 t 个点，然后删掉它们之间的边，要求形成 t 个大小相差 \le k 的连通块。

不是很会做，感觉只会 2^n。推推性质发现这 t 个点要形成连通块，但是还是不会做。

想先糊一下部分分，感觉 m = n - 1 的时候只需要从叶子往上拓扑排序就好了，45 分感觉很稳。

还想推性质，但是感觉总推不出来，回去打 25pts 的暴力。还是很轻松的过了样例。然后写了个 generator，发现随机图答案几乎都是 1？但是有锤子用。

感觉这题很逆天，写树的部分分的时候发现自己根本不会推，寄。

剩下两个半小时。只好看 T3，然后发现是神仙贪心题，推了好久都不知道有什么好做法。然后发现看错题了。用个 multiset，树上启发式合并一下还是有个单次 O(n\log^2 k) 的做法的。看了一下居然送了 48pts，感谢。感觉后面的分不用做了。

写完之后直接 WA 了几个大样例，感觉可能贪心寄了，想了想好像真有个反例，寄了，我操。

回去看 T2，过了二十分钟后还是忍不住想 T3，感觉贪心好像没啥问题啊！发现我怎么也想不起来刚才想出来的反例了！？

回去认真一看，我去，原来是比 answer 小了！原来是启发式合并少合并了个东西！改了改样例全过了，我去，贪心真的是真的。

剩一个半小时回去看 T2，又感觉 t 个关键点一定要是割点，但是不是很会证，想了十分钟感觉没啥问题。推出来这个，总共有差不多三个条件，但是我还是想不出来要怎么做。

  2. 删点后要形成 t 个大小相差 \le k 的连通块。

并且合法的 t 在 k = 0 的时候是 \max d(n)\approx\sqrt[3]{42n} 的，在 k = 1 的时候差不多是 600 的。

说了这么多还是不知道怎么处理。

然后梦游了半个小时，回去看眼 T3，其实还是有个特殊性质 C 可以拿的。本质上就是个树形 dp，f_u = \min( \sum f_v + {\rm tag}_u, {\rm size}_u)，但是才 6 分，还得敲个动态 dp。检查一下剩下 10 分钟打算写一下，写完线段树和矩阵之后，树剖写到一半就考试结束了，血亏 6pts。

之后云斗学院把三题都测了，没挂分。

但是估分 100 + 25 + 48 = 173 也挺低的，寄。

寄！怎么办？寄！怎么办？寄！怎么办？我他妈直接起床战争，欺负小学生！结果被小学生欺负了。

晚上吃完饭玩了会你画我猜。洛谷的同学们个个都是人才，说话又好听，luanmenglei 又不穿裤子。

明天我必翻盘，操！

Day 2

开题，T1, T2 怎么都是博弈游戏，有病？

T3 看起来不是很可写，先不管。

看了半天觉得 T1 可以拓扑，但是发现我拓扑不会消环。虽然感觉正反传递两边就好了，但是不是很会证正确性，也可能就是假的。

甚至发现原来有向图拓扑排序如果有环最后是根本拓扑不掉的！甚至会留下很多尾巴，而不是只会被拓扑到剩下一堆环。看来一直以来都理解错拓扑排序了。

感觉消消可以做，打算先开 T2。

T2 指数级算法算是送的，但是多项式算法还是很难想。转头去看特殊性质。

A 就是给 Bob 找个合法方案，于是发现把限制条件建图之后就相当于给每条边分配一个点，不难发现一个连通块合法的充要条件是点数 \ge 边数。仔细分讨一下：

  1. 如果连通块有自环，那么 Bob 的选择显然是唯一的。
  2. 如果连通块是一棵树，方案数量是可以 O(n) 枚举出来的。
  3. 如果连通块有一个二元环（有重边），方案数量是 2。

有了这个发现好像就可以做 C 了。而且不同连通块之间是独立的，所以 Bob 的方案数量就是 O(n) 的。

感觉分讨一下也能做 B 和 D，感觉有 20 + 8 + 12 + 12 + 12 = 62。

直接开始写，结果写到一半发现 B 和 D 假了。因为这两种的 Alice 决策都有 2^n 种，根本算不了。痛失 24pts，炸裂。

好在 D 对 Alice 的限定比较严格，仔细分讨一下好像还能做。上面分类的三种，1, 3 都是比较好讨论的，可是 2 我直到考试结束都没想出来。

B 感觉 Bob 有 O(n) 种决策，但是难点还是我们要对 Alice 取 \max，这个东西没啥意义。结果回厦门的动车上 Tony2 跟我讨论的时候才发现只有 2 种，看错题了我去，血亏。

打完之后 40pts 后还剩两小时，只好回去打 T1，发现 100pts 还是相当困难的，而且节点数差不多至少有 10^6，边数差不多就是 10^7，感觉直接爆炸，写鸡儿。看了半天部分分，发现还是打爆搜比较靠谱。打了快半小时终于通过部分样例。发现爆搜还能通过 m = 1，彳亍，谢谢出题人。差不多有 55pts。

回去看 T3，感觉这个 10 分都很难打，想了几个 dp 都不太对劲，焯。

剩下一个小时感觉很慌，目前还只有 95pts，于是考虑去做 T2 的性质 D，结果就是没过样例，因为树的情况想了好几个最优构造都不对，甚至有的比答案大有的比答案小，逆天。

还想做一下 T1 的一红棋子一黑棋子，发现分讨还是很麻烦的，黑棋子可以选择原地反复横跳，也可以选择穿过红棋子所在列反复横跳。想了半天，感觉我还是原地爆炸比较好。

最后五分钟放弃挣扎，看看文件洗洗睡了。

估分 55 + 40 + 0 = 95，出来发现 Tony2 爆切 T1，这么神！今一您扬向！

动车上在那个什么学院测了一下 T1，没挂分，但是我又不会正解，焯。感觉打的比较保守，只选择打了暴力，冲一冲 T1 正解应该比较好，不过这都是后话了。

感觉 T2 要挂分，操。

4 月 4 日（Day 4）

前几天发现自己打的性质 C 出现了问题，其实看上面的分析就能看出问题。我假定了出现环一定是二元环，但显然不是。应该会形成一棵基环树，需要对这个环正反旋转进行分讨，可能这也是为什么大样例一直过不去的原因。

比较惨的是，我先判断一组测试数据是否满足某个特殊性质，然后进行求解。拜此所赐，我的指数级暴力在测试数据满足特殊性质 C 的时候会出错，将会挂分 [12, 32]，操蛋。

这告诉我们过大样例就和过编译一样没有意义。

但是我已经退役了，都已经和我没关系了。