CSP 2024 游记
qW__Wp
·
·
生活·游记
2024/10/25。
不是哥们。
Day -1
17:55 出发。目的地：广东东莞。
20:16 到达。车上睡得真香，晚上不想睡了。
吃宵夜 + 复习模（mú）板（但是一个都没考到2333）。
23:59 睡觉。
CSP-J
6:45 起床。
8:00 进考场。
T1 T2 一眼。这 T2 题面怎么这么长，还以为是什么高深的题，你 CSP 特有的题面长。
T3 算了一下拼各个数字所需火柴棒，发现拼 8 要花 7 根，是最多的。由于要使答案长度尽量短，考虑尽量拼 8。再看特殊数据，也印证了猜想。
虽然拼 8 的长度必然是最短的，但是可能存在其他方案长度相同但字典序更小。发现这种情况只会在 n 较小时出现。先一直拼 8 直到 n<30，剩下的爆搜，并把爆搜出来的部分拼在前面即可。设置一下最大层数（最大长度肯定不会超过 8），这样速度快得飞起。
做完前三题发现还有 2h+，但是 T4 多少有点抽象，最后写了第一个测试点 r=1 的情况就摆大烂了（考场上脑抽了，完全可以写一个 O(\sum l \times n \times k) 的记忆化搜索）。
# CSP-S
T1 水。
T2 有点难懂啊，读题读了半天，先跳了。T3 很好理解，但是没什么思路，写了个 $O(2^n)$ 的暴力润了。这辈子没见过这么抽象的 T4，果断放弃。
回来想 T3 的 dp，写写写发现好像写不出来。-1h。
做 T2，重新缕了一遍，终于看懂了。根据样例分析不难发现对于每一辆车记录被判超速的检测器区间，但是这个第二问的贪心没想出来？？？？-2.5h，比赛结束。
$100+0+20+0=120$，遗憾离场。
---
这个 S T2 原来是经典 trick，哎，菜死了/kk。
**数形结合。** 把区间按右端点升序排序，记录上一个选的点 $j$，如果 $l_i \le j$，那么 $[l_i,r_i]$ 已经被覆盖，跳过。否则再多选一个点 $r_i$，并令 $j \leftarrow r_i$。
赛后秒切，草。
---
可惜没如果。
**来日方长。**