CSP2024复赛

· · 生活·游记

比赛前

周五体育课跑了 1km，然后就开始咳嗽了。

复习了 Tarjan，KMP 和 Manacher，结果一个都没考。

目标分数：J 组尽量 AK，S 组至少 250。

CSP-J

T1

太水了，完全不用脑子。

开了一个字典记录每个字符代表的花色及数值。

T2

直接模拟即可。但是题面写的很详细，大概是来吓唬新手的。

T3

发现没有大样例，看了题面才知道，如果给大样例就暴露了规律。

看了一下题，发现是某场古老的模拟赛的原题。先尽量用 8，剩下的可以打表处理。但我记起来曾经手算的时候算错了，所以写了一个搜索。

前 3 题大概使用了 45 分钟。

T4

一开始想到图论，如果一个接龙序列以 i 开始，j 结尾，就连 i 到 j 的边。但边数是 n^2，也没法算答案，还无法处理两轮接龙是同一人的情况，卡了很久。

发现 k 不会变，而且轮数最大只有 100，所以可以拿一个 dp_{i_j} 记录第 i 轮以 j 结尾是否可行。转移的时候把每个人的词库扫一遍就行了。

开始写，可是必须用动态数组， vector 和 list 平时也没用过，就忘记怎么用，只好手写链表。10:15 写好了，但大样例过不了，手算了一下，发现是两轮接龙是同一人没有判断，再加一个数组记录即可。大样例跑了 1.2s，怀疑会TLE，于是写了fread快读，优化到了 0.9s。此时，离考试结束还有 1 小时。

估分

## CSP-S 听 `nodgd` 给我们加油。 赛时嗓子又痛又渴，水还喝完了。 ### T1 直接贪心，从小到大看每个怪物，让它尝试攻击没有被淘汰的最弱的怪物。赛后发现可以用桶，还要简单。 写完了之后去想了后面题目的思路，想到了 `T2` 和 `T3` 的思路，还怀疑 `T1` 没有这么简单，证明了一下这个贪心的思路。此时是 $4$ 点。 ### T2 首先算出每辆车能被哪段区间的检测器判断为超速，然后按左端点排序，贪心选择打开的检测器。但这个贪心策略改了 $3$ 次才说服了自己。 然后就是算出每辆车的超速区间，按照公式算即可，但测大样例时发现算出的超速的车的数量总是比标准答案多 $1$。检查发现是多测不清空。 在 $4:50$ 通过了大样例。我记错了时间，认为考试在 $6:00$ 结束，但实际结束在 $6:30$，这让我有点慌，认为 `T4` 的暴力写不完了。 ### T3 `dp`。设 $dp_{i_j}$ 表示确定前 $i$ 个的颜色，并且第 $i$ 个涂颜色 $j$ 的最大价值。朴素转移是 $O(n^2)$ 的，经过思考，发现可以优化到 $O(n)$，方法以后写。 写完了，测大样例发现差距巨大。输出 $dp$ 数组发现 $dp_{i_红}$ 一定等于 $dp_{i_蓝}$，但由于一些原因，$dp_{n_蓝}$ 算错了，但 $dp_{n_红}$ 没有错，原因现在还不知道。将 $dp$ 的第二维删掉，过了大样例。 此时是 $5:30$。 upd：此题 $70$ 分，因为程序会访问 $a_{i+1}$，是上一组数据输入之后未清空的，会导致 `WA`，但给的样例的 $n$ 都是递增的，所以无法触发这个 bug。希望 CCF 继续用脚造数据。 ### T4 写了一个 $O(Tn \sum c)$ 的暴力，应该有 $40$ 分。 在 $5:55$ 调试过了样例 $1 \sim 3$，后面的跑的太慢，测不了。觉得自己极限写完了，然后才发现是 $6:30$ 结束。。 ### 估分 $100 + 100 + [70,85] + [32,40] = [302,325]$。