CSP-S 2022 游记

更好的阅读体验戳此进入

Day - 2022.10.28

考试前懒得写游记了，摆。

Day - 2022.10.29

考试当天懒得写游记了，摆。

Day - 2022.10.30

考试之后又去考了个数学，所以又懒得写游记了，摆。

Day - 2022.10.31

开学了，整理一下这次的 CSP-S。

T1 开始半小时想了好多毫无头绪，麻了。

然后大概发现了应该要跑最短路，然后脑子里就没细想默认是 $O(n^3)$$O(n^3)$ 的，然后我又感觉很接近正解了，于是又想了半个多小时糊了一个巨恶心的（但是思想应该是正解假的，没维护次次优）的 $O(n^{2}k)$$O(n^2k)$ 嗯搞的，然后我考场上默认 $2.5\times 2.5=4$$2.5 \times 2.5 = 4$ 以为 $2s$$2s$ 能跑过去，然后赛后反应过来那玩意是 $6e8$$6e8$ 的，不过最难受的是最后发现这东西也需要最短路验证，然后写完最短路才反应过来最短路是 $O(nm)$$O(nm)$ 的，然后。。实际上这个时候已经可以写成 $O(nm)$$O(nm)$ 了已经是正解了，然后赛时脑子不太好使，没反应过来，没改前面的，最后就成 $O(n^{2}k)$$O(n^2k)$ 然后寄掉了，大概 $60\mathtt{\text{pts}}$$60\texttt{pts}$。

Upd：改题的时候发现好像主要 TLE 的原因是我的 $O(nm)$$O(nm)$ 宽搜求最短路退化成了 $O(n^3)$$O(n^3)$ 的，主要是我为了减少时间消耗把链式前向星变成 bitset 实现邻接矩阵了，然后考场上脑子又日常不太好使，最后效果就是用 $O(n^2)$$O(n^2)$ 替换了 $O(m)$$O(m)$。。。。。

后面的题都写的很迷，主要是 T1 一共消耗了将近三个小时，实在没时间想做法了，就 T2 写了个很水的线段树有 $60\mathtt{\text{pts}}$$60\texttt{pts}$，T4 本来写了个 $16\mathtt{\text{pts}}$$16\texttt{pts}$ 的 Tarjan 求 LCA，然后太久没写写挂了，剩下的也全寄了。。。

希望还能混个一等奖吧

然后大概是 sssmzy $300+\mathtt{\text{pts}}$$300+\texttt{pts}$，zpair 因为把 cin 搞成 icin 了所以挂了一堆分差一点上 $300\mathtt{\text{pts}}$$300\texttt{pts}$，cc0000 和 novax13 虽然不知道具体多少分不过也不少，我日常垫底。

UPD

update-2022_10_31 初稿