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 了吗？（笑）

这次省选对我来说的一个意义就是认清了自己的弱项：