2024CSP-J2/S2游记

· · 生活·游记

虽然也不是第一次打了，但是好久没打过正式赛还是很紧张。

毕竟是高中的老人了，不能出闪失。（不过不爆零进NOIP好爽）

2024CSP-J2

这次学聪明了，考前40min去试机，昨天写过对拍了，今天没写出问题。

把Geany编译参数调好，还有15min。

有个小操作，就是会发一个zip文件下来，虽然这个时候看不到里面的内容，但是名字是可以看的。这样等于提前知道四道题名字，把文件和输入输出都写好，节省时间。

开考看到第一题有点不可思议，这CSP真题啊？

把四道题目浏览了一下，T1T2一眼出，T3估计是找规律，T4一下没读懂。

T1事实上给set不停insert即可，但是觉得这样太侮辱题目了我还硬写了个哈希去搞，此时8:45。

T2神奇大模拟，直接秒，9:00。

T3像找规律，特别是只给了一组小样例，很可疑。不过一眼没找出规律，发现可以用string来dp，时间复杂度约是 \rm O(N^2) 的dp打了个 1000 的表，发现规律：以 7 个为一组成规律，N \ge 21 写了个找规律。写完9:40。

相当于留了2.5h给T4，我是信心满满的感觉能AK啊，看完接龙，感觉“跳串”这个操作很像图上跳点，造了一个以值为点的图，但是发现无论如何无法对“连续接龙的两人必须不同”做出约束。

推掉！直接以原来的点来建图。

发现一条字符串上 S_{i,j} \to S_{i,k} 相当于操作+1，边权为 1 ，两条字符串之间相同的字符直接跳不加操作次数，连权值为 0 的边。

跑了个SPFA，搞成死循环给我吓死了。对走的顺序做出约束，显然一个人接完龙换人，权值为 1 的边不能连走两次，权值为0的边走两次没意义，所以 0 也不走两次，这样必须交替走。也就是没两步路径权值和必定+1，r_j 到 100，SPFA时间复杂度 \rm O(2\times r_j\times \sum l_i)，建图时间复杂度 \rm O((\sum l_i) ^ 2)。能干掉 N\le 10^3 的点。

最后也没想过怎么优化，寄。（其实 0 边显然可以用虚拟点优化，但是太烦了而且也没什么用，所以到最后一秒也没写）

最后听讲评原来是dp啊，那没事了。

期望得分 100+100+100+60=360。

根据cjq第一定律，pj1=不能再打普及，所以这估计也就是人生中最后一场普及了。也许这一生也没法AK普及，但是这也不重要了。

中午和gzy&ycy去KFC了，中午没时间睡午觉，直接一瓶咖啡干下去，还好有新手保护。（咖啡越喝越没用，不过我之前几乎没喝过，所以特别有用）

2024CSP-S2

提前45min试机，右边是姚睿文大佬，我们搁那写对拍和线段树。只能说不枉我每个信息课都在拿python写C++的线段树，12分钟种树完成。（虽然也没用上）

不知道为什么我的电脑似乎有一点点小问题，pdf输密码打不开，不过到14：30就好了，我不知道为什么。

T1发现就是让大一点点的去干小的，写可重集，忘了怎么拼了！！！！！忘了！！！五个字符排列组合了一遍都没试出来，最后用了queue。样例反正都过了，感性理解一下对的。

T2匀变速直线运动？这么及时吗我刚刚学。不过还是一次函数和直线相交问题，很像种树啊，我刚写过（虽然写爆了）。直接大分讨，虽然叫我注意精度，但是我发现除了整除分母最高 2\times 10^3，精度应该不出问题。

有一组样例第二个答案一直少 1 ，然后最后发现 \rm M 写成 \rm N 了，那个点 \rm N = M - 1。当时过掉最后一个样例的时候太激动了！去年175pts历历在目，在vp的时候不止一次幻想过自己200+甚至300+，难道今天要实现了吗？

T3，50pts的dp还是好想的。本来想了 dp_{i,j,k} 表示第 i 个字符时最后一个红为 i 蓝为 j，发现这两个里面必有一个是 i，优化成 dp_{i,0/1,j}。时间复杂度 \rm O(N^2)。

想到状态 dp_{i,0/1,0/1} 可以 \rm O(N)。然后想转移。去上了个厕所，还有2h，然后就看了一个小时。没错，就是“看”了一个小时，啥都没干。

突然发现转移点就是 A_j=A_i 时，因为只有这样才能让 A_i 有贡献。否则直接拿无限制的最优解转移就行了！！！

永远记得，2024年10月26日18:04，我过掉了T3的大样例！

我只记得当时心跳的很快，手一直在抖，我人生中的所有提高模拟赛，没有任何一场过掉三题，难道就是今天吗？

还有25分钟，没有任何负担了，好好享受比赛就行了。和去年这时写着结构体一直不过快写哭了，今年可算是惬意。T4模拟写了特殊性质A，加一个记忆化把下面特殊性质A也拿了。最后发现前三个点直接爆搜啊，看什么 2^{31}-1，其实就是 [0,3]，搜！

18:21写完爆搜，检查了一下所有代码，18:29，等待那一刻到来。

比赛结束后，大声喊出“328”的那一刻，也许曾经付出的那么多努力都值得了。

预估 100+100+100+28=328。（一定要让我梦想成真啊）