CSP-S2024 游记

strcmp · 2024-10-26 22:51:45 · 生活·游记

先是一段时间的模拟赛。

心有对模拟赛：T1 发现是等差数列，然后会了。T2 发现是简单题，会了。T3 找规律许久发现是多项式，尝试插出来无果滚去打了阶乘暴力。T4 不会一点 puts("0")。

也是心有对：T1 使用 unsigned short 套 bitset 压空间的做法，爆完了测样例测不出来获得了 20。T2 发现是简单构造。T3 想到了爆搜出所有点跑二维数点，然后没时间写了。喜提 200-。

剩下的模拟赛基本重复会正解调出来一题，然后剩下题全是暴力，或者干脆会正解调不出来爆零。

Day0

找本子/cy

Day1

按照小粉兔作息起床。

然后🐟🐟枕发作一直到十二点。

发现 Q 群里 J 组有题目了，看了 T1T2T3 半分钟基本都会了，看 T4 发现只会一个线段树优化建图的状物，不会其它做法，润。为什么都说 T4 简单呢，果然还是群友太牛了。

下午进考场，先打了一遍缺省源，发现还有半个小时开考的时候就下发 pdf 密码了，心里一惊感觉很不对啊！打开 pdf 一下子把电脑卡死机了，鼠标键盘都动不了，周围人都开始看题了我还只能对着一动不动的电脑发呆。还好监考人员说能换电脑，换了电脑一看发现原来那台电脑时间有问题，已经开考五六分钟了我压缩包都没解压，顿时有点小崩（顺带吐槽一下，考点的桌子面积真的太小了，一张纸都放不下）。

点开题一看，T1，这是什么东西。贪心，这不是大弱项？完了今天是不是要一题切不了了。

再仔细考虑，哎，这不是简单题吗。你考虑从低到高枚举，高的贪心踢掉低的不就行了。不想排序讨论一遍所以直接 map 启动，写完了一测发现过不了样例二，打个补丁再测发现过不了样例四，再打个补丁就能过全部样例了，10min 直接丢掉看 T2。

发现 T2 题面很长，T3 也没什么思路。

那不妨先读懂 T2 在干什么，读完题后发现好像正解不难的样子。第一问看完题就会了，a_i \ge 0 的我们就关心一下 p_m 会不会超速。a_i < 0 的就 lower_bound 一下找到 p_k 看会不会超速，拿那个式子抄上去就好了，平方一下就能避免浮点数。

顿时不会做第二问，再一想发现它就类似于 01 序列给定很多个区间，然后要求这些区间内至少有一个 1，问最多 0 的数量。

这东西刚开始觉得不可做，仔细一想直接贪不就行了，左端点挂 vector 上每次贪心往前放 1，拿个树状数组啥的维护区间内是不是有 1 就好了。

摸鱼导致想了不少时间，但写起来很顺，1h20min 的时候过了所有样例。

天胡开局，我什么时候能 1h20min 切两题了，那是不是后面就很有希望了。

开 T3，写了一个 1D1D dp 式子发现完全处理不了一个类似两个红色中间夹一个蓝色，蓝色对之前的贡献。

是不是只能 n^3 暴力 dp 了啊。

发现 n^3 纯不好评价啊，n^2 用个 2D 的状态代替就行了，写个 2D/0D 的 dp 每次转移端点。设个 f_{i,\,j,\,0/1} 代表 i 末尾有 j 个红色或者蓝色，同时 i - j 强制钦定是蓝色或者红色的最大和。

发现 0/1 的转移完全一致，直接压掉，发现能滚动数组，也直接滚掉。

然后每次相当于全局加 0 或者 a_i，开头插一个 0 或者 a_i，然后对 1 位置做一些取 \max 啥的。

不想动脑子于是直接丢了个线段树上去，发现同色点好像不太好处理的样子，于是直接取 i 的前四个同色点转移，大样例 0.8s，很难绷啊。

写到这里差不多 2h20min 了，发现还有 1h40min 写 T4。

于是先检查了 123 确认没有锅了。

我什么时候也能 2h20min 有 300 分了。T4 题面又很长于是完全不想看，而且看了好像也没啥思路。

摸鱼鱼，点开了那个 edge 的 surf 小游戏，到结束。

出场了才想到 T3 能简单线性，就把线段树删了就好了，顿时难绷起来，是不是要被卡常卡正确性了。还发现 n \le 2000 的数据点分治我写了 n 次 memset 二十万级别的数组，因为我 f 第二维跟线段树用的一个 maxn，寄了寄了。是不是要被卡了。

一出场，怎么一万个 AK，惊了，全世界就我 T4 0 分，哭哭了，以后不在场上还能拿分的时候摸鱼鱼了。