CSP2024 游记

Day -INF

初赛。过了。

Day 0

下午到日照，在酒店把之前 Blog 上记的东西口胡了一遍。

晚上去考场试机，怎么还要模拟考试流程不让带包还要查身份证准考证。

屏幕太刺眼换了个显示器，试的时候发现没有 Linux 虚拟机测不了编译，不过倒是有 Excel 方便打草稿。

机子还可以一秒 $6\times 10^8$。

Day 1

上午继续复健。

下午到考场，发了压缩包密码先看样例，似乎没发现字符串和大模拟，看文件名也没看出来什么算法。

开题，先扫了一遍，t1 很可做，t2 好像可以数据结构？t3 一眼 DP，t4 题面过长神秘题。

t1 看小样例直接写了个判定当前数能否被下一个数干掉的东西，发现大样例过不去。手模一下发现还可以被更多的后面的数干掉，瞪了几分钟瞪出来了大概是求众数出现次数。感觉证明比较显然没仔细证，大样例过了。

t2 显然对于每一个车可以处理出区间，就变成了区间和点的问题。想的时候不知道为什么按照一开始的想法直接按数据结构想的，发现第一问可以线段树维护，第二问好像数据结构搞不了。直接上手搞区间和第一问，因为担心精度问题直接手写的整型取整，写完后发现测样例的区间不对，才注意到是开区间并且有不能整除的情况要分加速减速特判，写完后已经过了近 1hr。想到第二问似乎可以贪心的去搞，但是害怕后面打不完先开 t3。

t3 直接大力 DP 用 $f_{i,0/1}$ 表示前 $i$ 个数最后一个是 $0/1$ 的最大得分，实现了一下样例答案对了但过程和样例解释不一样，对着样例解释调了至少 10min，才注意到样例解释里 $1$ 和 $2$ 全写反了。测大样例发现过不去，推了一会以为式子写假了，赶紧写个 dfs 跑路回去看 t2。

t2 贪心实现了第二问，还是过不去大样例，瞪了一会发现多测没清空。改之后只能过匀速的特殊性质。此时剩的时间已经不是很充裕了，开始慌。后来改了一些东西，仍然过不去还剩半小时左右。

尝试打 t4 暴力，仔细读题并不是很好实现，特殊性质 A 是可做的。大概写了十几行看到剩的时间不多了，又听到监考一直在说要每个人检查文件，感觉写不完了。把文件整了一遍，听到说最后五分钟在关闭所有窗口并且手离开键盘鼠标的情况下打开 D 盘。文件没问题就照做了。

出考场越发感觉 t2 很典的东西没有写出来比较抽象，放掉 t3 的暴力 DP 也并不是一个很好的选择。时间主要就浪费在 t2 和 t3 互相调不出来的左右横跳上，这次比赛甚至是正式比赛中唯一一次没有去厕所缓一下的。越到后面心态越炸反而越写不出来。晚上连夜回济南，在车上看 u 群发现想的基本都是正解，就是实现太差。并且貌似人均 300。期望只有 $100+[10,20]+20+0=[130,140]$ 了。

Day 2

重写了一遍 t2 非常快的过掉了，并且发现死因是计算区间的时候开区间的向下取整，当正好可以整除时没有 $-1$。

另外好像 t2 考场代码时间复杂度比较炸。