CSP-S 2022 游寄
cyffff
·
·
生活·游记
2022.9.18
初赛。由于去年 AK 了普及所以只报了提高。宇宙射线轰爆 CCF。
赛时磕填空 1，举了好多例子感觉没有一组是程序跑得出的。
赛后看了看，和大家选得差不多，但是好像第一题就我选 \text C。
根据代码，只有 \text C 跑得出来。
2022.9.21
CCF 官答/cf。
$O(\lfloor\log_k n\rfloor+1)$ 是日志函数的一个简单运用，但是由于 $+1$ 了是错的。
填空 $1$ 就算跑不出来也应该 $+1$。
估分 $78-6=72$。又是垫底。
### $2022.9.27
麻了，果然 GD 不到 ddl 是不会出线的。
查分查了一天，确实是 72，CCF/lh。
能不能过啊。过了。
2022.10.17\sim10.28
第一次停课，还是挺特殊的感觉的。
中午会去抄一些笔记，感觉勉强跟得上。
这几天就打打模拟赛，顺带复习了一些板子（事实上我也知道 \text{CSP} 复习板子用处不大）。
大概就是考前的晚上就开摆，打了一晚上音游。
大概 \text{Concvssion} 比 \text{Aleph-0} 好听一些，就用它替换了 \text{JRKSJ R5 F} 的题目名字。
有点紧张，但又不那么紧张。
2022.10.29
上午开摆。\text{Orzmic} 判定真神奇。
14:00
进场。
14:27
下发密码，\text{belief2022}。
看了题，第一眼 \text A 是个简单题，\text B 一眼没看出来，但是感觉很简单。
$\text D$ 不会。
#### $14:35\sim15:00
先想 \text A，发现 O(nm) 可以接受，然后第一反应是 dp_{i,j}，第 i 个景点为 j。突然看到不能重复，想加一维，发现有点难度，跳了。
15:00\sim 15:45
看 \text B，开始分类讨论，讨论区间内有没有 a_x<0,a_x=0,a_x>0,b_y<0,b_y=0,b_y>0，然后每种情况只和最小最大情况有关，写 \text{ST} 表就好了。期望得分 100。
15:45\sim16:30
再看 \text A，想了一会，还是不会，打算写个乱搞。考虑对 dp_{i,j} 维护第 i 个景点为 j 的前 k 优的解和路径。再这些解中找到不包含 j 的进行转移（归并）即可。
先令 k=500 跑了跑，发现 n\le300 的部分可以快速出解，但是 n\le2500 非常慢。数据分治，当 n\le 300 时取 k=500，否则取 k=5，期望得分 [70,100]。
我猜这玩意比较难卡？
16:30\sim17:30
战术厕所，看 \text C，理清了题意，发现是问是否是内向基环树森林，只需维护每个点出度是不是 1。对每个点维护两个 \text{set}，表示连向 i 的，没有被删除的/已经被删除的点集。发现没有 4 操作时均摊复杂度正确，跑了大样例 4 还挺快，可能能多草点分，期望得分 [60,?]。
看 \text D，完全没有思路。写了个 k=1 的分和 O(qn^2\log n) 的 \text{dij}。期望得分 36。
17:30\sim18:00
拍了 \text B，造了其它三个题的极限数据测了测没问题。
18:00\sim18:28
开摆，反复检查文件，战术厕所。
18:29
结束，出考场。期望得分 [70,100]+100+[60,?]+36=[266,336]。
发现 \text{Ntokisq} 也不会 \text A 的正解，他写了个随机化。
感觉今年 7 级可能要上 300，有点害怕。
问了 \text{iorit}，他全程刚 \text D，没打 \text C 的暴力。看起来不是很好。
后面发现大家全都会做 \text D，有点慌。可是我连矩乘题没看出来，难过。
原来 \text A 是简单题，折半即可。考场思路真奇怪。
晚上拿到代码测了测，INFOJ 是 100+100+60+52=312 分。真奇怪，\text D 的 52 我在考场上随便卡掉了，怎么跑得过？
今年的进步就在于考场决策，懂得跳 \text A 做 \text B，稳住心态。
对了一下，希望能有 7 级。
2022.10.31
有人在 INFOJ（?）上面测了 GD 所有人的分数。
我 100+100+60+52=312 排到了 \text{rk}30，震撼。
等个官方成绩。看起来 $7$ 级没问题？
写了 [$\text A$ 的题解](https://www.luogu.com.cn/blog/cyffff/solution-csp2022-a-p8817)。
### $2022.11.2
看了眼小图灵成绩。
还是 100+100+60+52=312，省排 36/1483，国排 255/8969。
2022.11.7
全 NO 45 是什么。。。。
CCF 你有一点良知吗？
年度难绷，不会造数据就别出题。
我草，怎么官方还卡我 5 分。
明天看看数据，要是是评测问题到时候考虑要不要申诉。不过问题不大。真是抽象。
### $2022.11.8
官方数据。
我草，CCF 数据有一点水平，把我卡了！
WA95.
怎么是 k=0 的点，还大了/yun。
小问题，调好了。
好文推荐。
2022.11.17
拿到了 7 级，三年了终于蓝√了。