专栏文章

CSP-S 2025 总结

WWmd_125
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mineokwc
此快照首次捕获于
2025/12/02 01:11
3 个月前
此快照最后确认于
2025/12/02 01:11
3 个月前
查看原文

CSP-S 2025 总结

省流：原地爆炸，拿下 jz 倒数的“好成绩”。

赛前的那个上午

各个学长给我们分享了各种各样的小 trick。我们也是有认真的听，我知道，每一个小 trick 都可能是大巨们通过各种奇怪的方式总结出来的，或是因为这个 trick 场切难题，或是因为这个 trick 赛季报销（应该没有这么恐怖）。
我们也是有认真总结的。

赛时

提前大概 15 分钟进入考场，熟悉一下机位后就静静等待考试开始。
比赛开始，根据我们赛前的打算，在半个小时的时间内熟悉题意并大概思考出前两题的思路。本着这个策略，我们开始速通前两题。
T1 看到一个 n2\frac{n}{2} 的限制，很明显的贪心，直接拿下。
T2 跟我们赛前的一道模拟赛的题很像，应该也是最小生成树，思考了一下，感觉想到了一个复杂度差不多的做法，也算拿下，下一题！
T3 字符串题。看懂题意后稍微想了一下。无从下手，跳了。
T4 计数题，看懂题意后感觉有点思路，我觉得应该比 T3 简单，好的，等会就冲它了，回去打前面两题。
此时时间只过去了大概 40 分钟。还好不算很超出预期。
T1 的贪心挺好写的，就是考虑调整法，先将每个人放到自己最想去的部门，这样极有可能会导致一个部门人数超出 n2\frac{n}{2}。我们考虑把这个部门的人往另外两个部门放，对于这个部门的每个人算出一个 Δ\Delta，表示把这个人放到别的部门去的最小减量，根据这个贪心即可。此时距离比赛结束还有 3 个多小时。
T2 我的想法刚开始比较猎奇。刚开始是以为这 kk 乡镇是原 nn 座城市里选出来的，后来发现了，立刻观察出一个性质就是只保留原来 mm 条边里的最小生成树的那 n−1n-1 条边即可。然后我们知道要是每次都排序的话时间复杂度肯定会起飞的，所以我们想到假如说新加入一个乡镇，它一定会连最小的那条边，这样在这个树上跑树形 dpdp 应该就行了。
我们猜这个做法是对的，实现出来后第 3 个大样例死活过不去。我们有点红温，打个暴力排序求最小生成树的程序对拍一下。意外发现暴力比我们这个 dpdp 还快，答案还是对的。我们果断弃掉 dpdp，开始优化暴力。
暴力时间复杂度算一下发现是 O(2k×n×k×log⁡nk×α(n+k))\mathcal O(2^k\times n\times k\times \log nk\times\alpha(n+k))。拿计算器敲一下，大概过不去。我们想到可以提前排序，每次把最小的丢进一个堆存起来，这样时间复杂度来到 O(2k×n×k×log⁡k×α(n+k))\mathcal O(2^k\times n\times k\times \log k\times \alpha(n+k))。测一下极限数据只需要 1.22s1.22s。加一个如果目前答案已经劣于以前答案就结束操作的剪枝，就把时间缩进 1s1s 以内了。
此时距离比赛结束还有 2 个半小时。
后面我们的操作就很迷惑了。
T3 字符串题，我们一概不会字符串，直接跳了，我们考虑打完 T4 回来打 T3 的暴力。
T4 我们想到 ss 是固定的，然后我们转化一下题意：
对于每个位置求一个 did_i，如果在这个位置放的 cc 大于 did_i，就会产生 11 的贡献，统计贡献 ≥m\ge m 的方案。
我们认为 did_i 是固定的，是好求的。我们现在开始考虑计数方案，然后我们发现 did_i 是单调不增的，意思对于任意一个 cc。它能造成贡献是是一段前缀，我们发现这个可以做 dpdp。
想到这里我们兴致冲冲的就要开打了，我们天真的以为我们切了这道题。其实现在回来看一下，你会很容易发现 did_i 不是固定的，你这样算的话就相当于没考虑那些自己放弃的人。所以我们的算法从一开始就错了。
中途我们还因没有理清思路和状态就开打导致打了删，删了打，浪费了很多时间。最后也只是打出来个 O(n4)\mathcal O(n^4) 的。然后我们调了半天调过了小样例，发现第二个样例根本算不出来。当时脑子开始发热，我红温啦！
出去上了个厕所，也没找到转移哪里有问题（当然找不到啦，一开始就错了）。
发现还剩 40 分钟，不是，怎么打了这么久，回去打 T3 的暴力。
打 T3 暴力也是心不在焉，脑子里还想着 T4，再加上人有点红温，发现自己根本不会暴力，只想到一个最暴力的 O(nL3)\mathcal O(n L^3)，一分都没有。当时人就更红温了。最后只想到 10 分的暴力，打出来，测过最小的样例就没管了，连第二个大样例都没测。
回去继续冲 T4，越冲越红温。最后 20 分钟，想着不能爆 0 吧，打了个指数级暴力，但是是根据我们之前那个想法打的，发现也过不去大样例。我真的——！！！
红温到极致的我终于意识到想法的不对劲，可没时间补救了。检查一下 freopen，遗憾离场。

赛后

C
估分： 100 + [80,100] + 0  + 0 = 200
实际： 100 + 100      + 35 + 0 = 235
不是，T3 还能送我 3535 分？
总结一下这场比赛。
优点：
  • 水题还是能把握住的。
  • 有自信
缺点：
  • 感觉复杂度不对后的第一件事居然是卡常而不是优化。
  • 先去冲后面的题才去写暴力。这样会导致该拿的分没拿到。比如 T3 有 50 分的暴力档，因为红温加人比较急，就没有想到。
  • 不要红温，不要红温，不要红温！
  • 打一道题就一心一意的打，不要做这道题想那道题。
  • 太想当然了，导致 T4 思路整个假掉了。
感觉没有发挥出自己应有的实力，但好在一等奖还算是勉强保住了。
看看能不能去 NOIP 吧，能去的话争取把 NOIP 2025 稳住。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...