2022 CSP-S

Vision271 · 2022-10-31 08:05:15 · 个人记录

前言

• 这键盘上不好用的键又多了一个，现在是...右 shift，i，和 a 了。

• 你呢？你...呢？

• 好吧，也确实并无什么值得犹豫的。姑且这么认为吧。

赛时复原

• 阅前须知：这里的所有时间是我当时的电脑时间，我那个电脑慢 \text{15min}，也导致我以为提前下考了。

• 约 \text{13:40}\sim \text{14:15}：敲缺省源和板子。

  • 快写写挂了一次（没有 |48。）

  • 发现宏定义少了好多行，想不起来是啥。后来在使用中把用到的想起来了。

  • 敲了一个 dijkstra 的板子，然后又敲了一个 dinic 的板子（这个敲完 bfs 就扔了，因为发题了）。

  • 键盘的右上六键键帽乱了，思考之后决定凭记忆用那六个键。

• 约 \text{14:15}\sim \text{14:35}：审题，

  • 我没有意识到这是提早开赛了 \text{15min}。

  • 开始看题。

    • 先看了一眼 T1，觉得只会随机染色，算了一下复杂度，发现如果有 n^2 条边那么只能随一次。觉得正解可能不太好想到。

    • 看 T2，一眼秒了。事后证明秒假了。

    • 看了一眼 T3，稍微转化题意之后认为是所有点都必须属于 siz>1 的 SCC 上。事实上这个转化是错的，之后再谈。

    • 看了一眼 T4，觉得会前 5 个点的暴力+4 个点的树剖。

• 约 \text{14:35}\sim \text{15:30}：首先开了 T2。

  • 觉得没有必要创 T1 正解，至少没有必要这个时候创。

  • 开始时以为答案是 \max(\max\times \min,\min\times \max)。显然不对。开了两棵线段树。

  • 发现被第一个样例的 0 卡了，于是开始打补丁。

  • 测了第二个样例，发现完全假了。意识到需要对正负分类讨论。

  • 又开了一棵树，存 A 的区间 >0 的 \min 和 <0 的 \max。调了一会，过了。

• 约 \text{15:30}\sim \text{16:30}：重新整备了一下，开了 T4。

  • 开始思考下一题开哪个。仔细看了一下我会的分，认为是 85+100+40+36。

  • 觉得 T1 有希望冲正解，于是希望把 T1 留到后面做。觉得 T3 我可能还会更多的暴力，于是决定开 T4。

  • 原谅我忘了一开始想的暴力是什么，总之我刚把 hldecomp 的命名空间开了，就意识到我有更优的 44 分暴力。

  • 开始写，大概是一个 dp_{i,0/1/2}。没有意识到这个转移有环。

  • 测了样例挂了，发现有环。转为拆点跑 dijk，用了开头写的板子。

  • 觉得树剖只有 8 分，没必要现在写。有空再说。

• 约 \text{16:30}\sim \text{17:19}：开 T1。

  • 犹豫了一下开 T1 还是 T3。考虑之后认为应该先把 T1 拿到手。现在看来，也许应该 2134/2143，没有必要先开 4。

  • 约 \text{30min} 写了个随机染色。挂了。

  • 好像是 dfs 重构图的部分挂了。快速换了个 bfs，过了，但至今不知道 dfs 挂在哪里了。

  • 又挂了，发现是没有特判不许把 1 当景点。稍微修改重构图部分后过了。

  • 算了一下，发现 k=1 的那三个点可以搞到。开始希望最后三个点不是全是网格图。

• 约 \text{17:20}\sim \text{18:00}：开 T3。

  • 首先写了个奇怪的东西，发现完全不对。意识到题审错了。

  • 发现实质上是要求构成一个基环内向树森林。开始考虑用 outdeg 和 tarjan 来做。

  • 先写了 outdeg 部分，测了一下第一个样例，发现居然过了。开始考虑为什么。

  • 意识到根本不需要 tarjan。快速写完并复杂度分析，发现中间的没有 4 操作的 4 个点可以过。

  • 然而我没有意识到我的 check 是单次 O(n) 的。事实上那几个点需要线段树。

• 约 \text{18:00}\sim \text{18:15}：检查。

  • 本来以为还有半小时，犹豫了一下冲 T1 正解还是写 T4 树剖。

  • 突然广播告诉我还剩 \text{15min}。生气了一秒，然后没管，开始检查。

  • 把代码全部通读，没有发现逻辑错误。

  • 于是检查文件名和 freopen，然后把样例全部重新测了一遍。

赛后复盘

• 键盘和电脑时间这都属于不可抗力，不谈了。

• T1 我不会确实出人意料...折半，折半。

• T2 花的时间太久，一方面是没有想清楚，另一方面是...这个等下再谈。

• T3 这个自以为多过 \text{20pts} 确实是...总之挂在这里当一个地标罢，时不时就能看到。

• T4 来不及打树剖。其实该想到 k=2 的做法的，我赛时考虑过是否只能走路径上的点相关的结论。\text{24pts} 啊...

• 把刚才没谈的说一下：码力。码力非常之拉胯。速度 E，精密 E。这样可不行啊。

• 另外就是这次复习中暴露的问题。全盘铺开的结果就是啥都不会：线性基，虚树，同余最短路，平衡树，KDT，BSGS，扫描线，欧拉图，吉老师线段树，根号（全部根号相关），博弈论，z algorithm 开始的所有字符串，二分栈，拉格朗日插值法，势能分析与主定理，扩展欧拉定理（及光速幂），卡特兰数与斯特林数，复杂容斥，点分治，DP 套 DP，wqs，ST 表，可并堆，......

• 师傅别念了，我收拾旧山河就是了。

• ...难言也！