CSP-S 2023 游寄
xiezheyuan · · 生活·游记
曾像夜那么黑 每个清晨
曾阻挡每个梦 每一道门
终于也可能 无限可能 自由发生
—— 张碧晨《开往早晨的午夜》
T1 题解 | T3 题解 | 第一轮游记 | 前情提要
Day -3
上午常规 5 机房板子大赛。把快速幂、并查集、MST、最短路等基本算法打了一遍。感觉良好。顺便学了一种 kmp 的非常规（但是很短+思路简单）的写法。
下午模考。T1 是一个简单的 MST 性质题，本来以为需要 Brovka 但实际上完全不需要，写了一个均摊
T2 貌似是一个和原根有关的性质题，推了很久的性质发现还是不会，拿 20 分跑路。
T3 看起来很像逆序对的变形，但是实际上并不简单，输出 -1 走人。
T4 看起来是一个非常复杂的线性代数找规律，朴素的高斯消元 + 暴力
挂分长rp，AK掉大分。 爆零就爆零，天天好心情。
Day -2
上午继续写了一些板子，然后就摆烂了。下载了一个无名杀供下午考试搞颓用。
下午又是模考。
第一题非常简单，前缀和搞一搞即可。
第二题可以看出来是一个 dp，但是总处理不了后缀前缀之类出现计算重复的问题。赛后知道是 KMP+dp。直接写了一个
第三题据说是一个分治，但是暴力有 60pts，果断暴力。
第四题不会，随便写了部分分，得 30 分。
Day -1
到 HNFMS 先查看成绩。发现 Day -2 的模测 T1 文件名 desert 写成了 dessert 怒挂 100 分。其他都还好。
上午摆烂。下午摆烂。
越接近 CSP 摆烂越严重。
晚上晚自习请假，将可持久化 sgt，可持久化 trie，重链剖分，ACAM 等复习了一下。
Day 0 2023.10.21
上午读了读《骗分导论》等经典书目，中午随便吃了点东西就出发去长沙理工大学（以下统一简称 CUST）考试了。
这一次 zip 压缩包有一个密码，pdf 也有一个密码。有意思。
开考前 10 分钟先解锁 zip 压缩包。题目名和大样例看了一遍。
开考！先瞅了瞅 T1。T1 读了几遍题没有看懂。最后终于看懂了，意识到这是一道水题，飞速切之。不过大样例过水，感觉万一挂了就不好了。
不得不说 CUST 的电脑性能是真的差。编译都要编译 10 秒钟。
看 T2，第一眼感觉是一个区间 dp。然后看了看数据范围
n \leq 2 \times 10^6
吓得我发抖。跳过 T2 看 T3。
T3 的题意是真的长。大致是在模拟结构体的内存分配。数据范围很小，感觉是大模拟。但补齐机制非常难懂。
写了三个小时，其中一度想过放弃，不过都被倔强的我坚持下来（反正其他题不会做，不成功，便成仁）。
终于在历史上的一刻，18:06，终于通过了大样例。我长吁了一口气。
顺手把 T2 的
把代码放到 NOI Linux 虚拟机测试。CCF 非常良心地配了 VMware Tools 好评。
最后检查了一下文件名就跑了。
下考之后感觉身边同学们都放弃了 T3，写了 T2。T2 怎么写啊！有的说是 map+hash，有的说是 KMP 形式 dp，还有人说是 SAM。6
各大平台都是 100+35+100+0=235（小图灵 T4 奇妙多 5 分），HN rk 50 左右。感觉被 lg 众多巨佬吊打了。
NOIP 2023 加油。
Update on 2023.10.29 出分了：