2022 CSP游记

倒数第二场比赛。

又是不能带水进入考场。。。

先用半小时慢慢看题。

好消息：图论很多，貌似没有 dp。

坏消息：T1 不会做。

然后每题都想做法，发现只会做 T2。。。

最优解肯定是找到一行使得这一行里的最小数最大。

肯定是先想把矩阵构造出来然后上树套树开干，但是我整个 10 月都没写过代码，而且树套树又不是正解，就继续停下来想。

可以发现一行里的数都是用乘法确定的，这些行里的数的 b 值是确定的，然后就可以开始分讨了。

最开始是分 a 的最大最小和 b 的最大最小，结果打完代码发现样例不过。。。

然后怀疑人生。。。

后面发现 a 和 b 还要讨论正负数，然后讨论了半天，脑子不清醒了。

最后开了 1 棵线段树（把 a 和 b 都扔在同一棵树里），维护了 6 个东西，写了 6 个查询。

测样例发现 a 里有 0，用了个前缀和判断区间内是否有 0，又加了个特判。

测大样例结果发现数据是负数我输出了 0，尴尬。。。

又多加了判断 a 没有正数和 a 没有负数的情况，但是一个 OUT 文件长度比 ANS 文件长度多了 10000，另一个多了 100000。后面发现是换行符的问题。。。

开 T3，许久没有思路。发现其实就是问什么时候每个点都只有一个出度。

发现没有强制在线，就想搞离线分治。

发现每条边有存在时间，于是想到线段树分治。

打到一半发现想假了。。。立刻跑路。

看 T4，发现一股 dp 味（收回没有 dp 的话），但是这个链上转移让我想到了 ddp。。。（捂脸）反正不可能考 ddp，T1 还没做呢，跑路跑路。

开 T1，估计是 O(n^2+mk) 的算法。

k=0 是一个部分分，很尴尬的是我不会。。。

想了许久，发现可以以每个点为起点进行 bfs，找出与它距离小于等于 k 的点直接连边，O(mk)，符合猜测。

然后就转换为 k=0 的部分，寄。

抓耳挠腮半天，觉得肯定是枚举两个点（要求 O(n^2)）。然后就想枚举 A 和 D，想不出来，枚举 B 和 C，也想不出来。。。

剩下时间就听着键盘声吹着空调发抖了。。。

回来第二天发现 T1 RE，T2 100，但是忘记考虑 b=0 了。。。

做核酸想了想 T4，发现就是 ddp，差点当场去世。。。

回来再想了想 T1，发现好像做个预处理 1 和所有点的最大中转点再枚举 B 和 C 就行了。。。

听说 T3 是哈希，这真想不到。

下次（最后一次）记得把暴力打满/kk