2021 联合省选游记

内容说明： 我所在的 SH 采用了 A+B 的方案选拔省队，因此 SH 并没有官方的省选赛，因此我们参与省选的方式是在得到题目后在学校机房进行断网模拟，由于考试环境和正式比赛没有差别，考试前也没有机会与任何正式选手进行交流，因此成绩具有可信度和参考价值。 --- 省选前没复习，因为联测都打不完。 第一天考试前 50 分钟还在打忏悔。 ### Day1 令 0:00 为考试开始时间，4:30 为考试结束时间。 #### 0:00 先看了 T1，感觉是一个和去年 T1 一样水的题。 然后看了 T2，不知道是什么东西。 最后看了 T3，感觉是个能做的题。 我选择了先推 T3 的一些基础结论，也顺带思考了一下 T2，于是半个小时就过去了。 #### 0:40 开始搞 T1，我首先思考了十分钟的不需要排序的算法，发现比较困难，就直接糊了个排序上去，几分钟写完了，思考了一下要不要改成基排变线性，最后懒得改。 #### 1:10 感觉 T3 似乎比 T2 要简单和有思路不少，就先去开了 T3。 根据我之前推出的结论，我们只需要对于每一对 $i<j$ 计算在 $\{i,...,n\}$ 导出子图中 $i,j$ 属于同一 SCC 的最早时间即可。 在将近半小时的思考后，我得到的最优算法仍然只是一个 $n$ 次 Dijkstra 的 $O(nm\log n)$ 算法，于是就选择写了这个算法，当时的期望是 $80$ 分。 #### 2:10 T2 还是不太会，所以先测了一下 T1 的大数据，发现很快，又想了想有没有什么比较卡的数据。 #### 2:20 开始推 T2，一开始我推出一个包含 $n+m$ 个变量又有加减法约束的系统，这个系统好像不太能解。 随后又乱搞了一下，将每一行视作 $m^2$ 个方程，这样变量的个数从每行每列的增量转变成了只有每列的增量，随后我意识到只需要对每列前加一个符号的修正，就可以使得所有不等式都是 $b_j-b_k\leq c$ 的形式，这样就可以采用差分约束系统解决了！ 于是写了一下。 #### 3:10 T2 没有大样例，极其生草，然后我自己造了组极端数据测了下。 要 3s... 然后就开始不懈卡常，由于我写的是 BellmanFord，先在判负环那里加了一个如果无法松弛就退出的优化，随后又优化了一下前面建边的部分，又写了个读优。 这时候要 1.5s 了... 发呆了好久，突然发现我没开 O2，开了之后跑起来非常快乐。 #### 3:30 最后一小时，所有样例和自己造的数据都测过了，没事干，就生成了一组 T3 的最大数据玩玩，看看要跑几十秒。 然后发现 0.9 秒就跑完了？ 我也懒得论证它的正确性了，就扔那不管了，最后半个小时的时候写了一下题解，出来之后好问群友。 --- Day1 期望得分：$100+100+[80,100]=[280,300]$ --- ### Day2 #### 0:00 进场看完题之后呆了，感觉一题也不会。 T1 是个之前隐隐约约觉得做过的题，看上去有个树剖+链的巨大难写做法，觉得实在写不出。 T3 由于我没学过支配树，感觉没戏。 想先找软柿子捏，就先开了 T2。 先口胡了二十分钟的假做法，发现啥都没优化，最后通过一种拆贡献的方法优化掉了一个 $m$。 #### 0:50 开始写 T2。 #### 1:00 写完 T2，发现 $n=13$ 跑得贼快。 然后开始想 T3（感觉 T1 比 T3 难不少），先理性分析了一波条件，然后开始自闭。 #### 1:30 这段时间里一会看看 T1，一会看看 T3，但感觉啥也没会，咋比 Day1 难这么多啊。 #### 2:00 这时候想到了一个 T3 大暴力，大概是 $O(\dfrac{(m+q)n^2}{\omega})$ 的，似乎能拿 $75$ 分（其实之前就想到了，只是因为要写 Tarjan 之后传连通性，懒得写），并开始写。 写起来很麻烦，大概写了半小时多，幸运的是没怎么调试就对了。 #### 2:50 T1 有了一个正解的雏形，大概是树链剖分上对于每条链维护一个主席树，但是稍微权衡一下感觉这个东西代码不短于 8k，写出来也不会调，就放弃了。 然后打了点小暴力，总共拿了大概 $45$ 分。 最后持续自闭。 --- Day2 期望得分：$45+100+75=220$ --- 后续： 测了一下洛谷和 NFLSOJ 的民间数据，都和预期一致（$300+220=520$）（其中 NFLSOJ 只有 Day1）。 不知道到没到 ZJ 队线呢。 --- 后记： 要是 D2T1 没有受之前做的题的干扰，然后又学过支配树的话，我不就 AK 了吗？（笑） 这次省选对我来说的一个意义就是认清了自己的弱项： - 数据结构：事实证明，不管多简单，只要是数据结构，我就做不出来。 - 奇怪科技：之前开玩笑说全 SH 省队竟无一人会支配树，事实证明，没人能做出来自己不会的科技题。