2022 CSP-S
前言
-
这键盘上不好用的键又多了一个,现在是...右 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 表,可并堆,......
-
师傅别念了,我收拾旧山河就是了。
-
...难言也!