2023 CSP-J/S 游寄

赛前

停课了两个星期，打了好几场模拟赛。

（吐槽一下，说是 CSP-S 模拟赛，但难度和知识点早就超了提高了）。

模拟赛的质量很高，学到了很多算法和小技巧。

当然，每天都被爆踩。

上午：CSP-J

开题仍然延续老传统：顺序开题。

apple

很快找到了性质：逢三取一，打了一会就切了。

road

一开始考虑了 dp。

后来发现没必要，就一个贪心。

维护一个下降子序列，然后暴力跑就好了。

uqe

模拟，就跟着题目打。

bus

一开始想到拆点，但又没有继续想（真遗憾啊~）。

后面又想强连通分量缩点化成 DAG，结果强连通分量内还要考虑一大堆，没做法。

最后搞得没时间了，打了个总司令就结束了。

下午：CSP-S

上午搞得有点没信心了，一开始还想打保守点。

看了看题：T1 一眼暴力，T2 没啥思路，T3 题面好长，T4 什么东西。

最后还是顺序开题了。

lock

一眼暴力。

结果看题看漏了，没看到 “这 \(n\) 个状态都不是正确密码” 这句话。

搞得我调来调去大半天，最后重新审题才调对。

game

一开始没啥思路，只有个 \(O(n^3)\) 的暴力。

想了想应该是 DP，遂设 \(f_i\) 表示以 \(i\) 为左端点的合法区间个数。

然后……没想出来。

感觉自己思路是不是有点问题，然后开始发散思维，还真让我想到了个算法。

处理区间问题，试下 CDQ 分治（他甚至在初赛时出了一遍）。

然后按照题意，构造出了跨中点的区间贡献形式（消掉所有可以直接消去的字母后不就是回文串嘛，打了颗 Trie 树维护了一下）

然后就过了所有大样例。

自己造了 \(2 \times 10^6\) 的大样例，发现跑了 \(2\) 秒超时了。

最后发现忘开 \(O2\)，开了就过了。

struct

还剩一个半小时。

看题，然后上手。

拉扯了一个小时，挂了，咋调调不对，只好重构。

半个小时重构还不对，遂寄。

tree

瞟了两眼，笑死，打都没打。

赛后

爆炸爆炸爆炸爆炸。

民间数据评测（luogu、小图灵、云斗）结果：

CSP-J：300（+T4的分数，T4打了总司令，看天了）、rk191。

CSP-S：200、rk190。