#创作计划# CSP-S 游记
2025-11-02 12:09:57
发布于：广东
初赛
Day -1
对。
Day 0
不对。
Day 1
对。
感觉还行，由于休息够了感觉比既报 J 又报 S 的更有优势。
好了看题。
我去什么 KMP？什么线段树？什么 Trie？吓哭了。
然后是一道 DAG 拓扑排序的题，我觉得答案可能有很多，但选项的答案特别小，而且前面几题都选的 D，这题为了保险就选了 B 了。
然后单选题印象最深的就是两个“编程”题。
第一个是 01 背包。
不难发现当物品的重量越大，价值也越大。
我们还注意到全选不行，但是可以放弃一个选。放弃一个中，放弃第二个是最优的。那有没有其他情况呢？可以发现最小两个的价值加起来已经超过第二个了，所以不存在其他情况。
第二个是那个任务的。
第一眼看到感觉像可反悔贪心，然后正常按右端点排序，结果发现可以无惩罚解决，然后就结束了。
后面发现可反悔贪心做法假了。
然后是组合题。
第一题是一个简单全排列问题，当时时间还有一个半小时，我干脆直接把所有全排列都打了一遍。
第二题有点难绷。不过这是 CSP 第一次出交互题，还是挺震惊的。
题目意思就是给你两个相同的蛋，猛锤超过 次就会爆炸，求这个 。
solve1 很简单，就是暴力试。
我没看 solve2，先猜一下，应该是分块，尝试 次。结果果然如此，但是为什么他的分块这么奇怪，以递减数列来分呢？不管了，肯定有他的道理。
正常写写到最后一题时才发现原来他这么做是为了平衡次数，减小常数。比如说第一块最坏需要查询 次，第二块最坏要查询 次，以此类推。
第三题看着很唬人，其实也就是个折半搜索。
注意值域是 就行。
然后完善程序第一题是一道免费边的题，一眼分层图最短路，秒切。
第二题是个小交互，仔细读十几分钟题后就发现是枚举所有可能组合就行了，可以证明每种情况都有它对应的组合。
最小测试轮数我不会证，但题目也没要证。
最后注意的一点是，CCF 还是这么喜欢阴人，它的每一种情况是前 后 的，所以枚举全排列需要选上一个排列（prev_permutation）。
Day 1.5
去 ACGO 测了一下：我去？？？？？？93？？？？？？？
错了几个很糖的错误，比如那个 DAG 答案就是以上都不对，猜蛋那题 check2 次数可能比 check1 多。可以看出我不会造 hack 数据
Day
还真是 。群友现在还不知道他们被拉爆了。（我向他们报的是 ）
复赛
Day 0
做了一下超速检测， 才做完第一部分。我该在哪里停留？我问我自己。
Day 1
不想那么多了，相信自己。
666 监考老师把 J 组解压密码当 S 组放上去了，硬控我 1min。
666 放上去的解压密码漏了个 4，硬控我 2min。
先开 T1。
什么鬼。不超过 ？那就枚举最大的咯？
不管了，先拿暴力分再说。
令 分别为拿 个 ，拿 个 ，拿 个 的结果。
好的， 以内的数据都过了。
现在开始想正解。
首先蒙个结论：最多的一定拿 。然后枚举最大的贪心就行。
结果发现样例没过，结论假了。
现在还剩 ，没办法了，先开 T2。
第一眼，肯定是 MST。
诶 这么小？估一下时间复杂度吧。有分 的数据， 还只有 ，那时间复杂度不出意外就是 了。
注意到原来的有很多浪费，我们真正需要的只有 条边，就是原来的最小生成树。
然后枚举 二进制位，看看选哪些是最优的。此时我们只需要 个点和这几个点连通就行了。排序后 MST 即可。
时间复杂度 ，瓶颈在于排序。
赛时没想到怎么优化，赛后才想到：我预处理出 条边和所有点的连边排序，这样每次枚举 就不用排序了啊，时间复杂度可以降到 ，我啥比吧。
然后看 T3。
我去 T3 怎么是字符串啊。有点难度，先打暴力。
好了暴力打好了，样例过。
先写一个哈希板子再说。
不对正解好像是 Trie 之类的。
那算了，还是看看 T1 吧。
又想了 20min 还是没想出来，那就拼测试点吧。
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我为什么场切 题，这下得被群友打爆了 555555555555555555。
拼好了， 的可以拿前 个点，错误的结论可以拿性质 A,B，随机数据也可以顺便过了。
总共 分，但当时赛时以为是 的，所以阈值定为 ，估计又少 。
T3 后面还是想了想，弄了个 的暴力和性质 B。
然后随便写写，最后考完后发现写了了棍母，喜提 。
最终结果：，T2 还可能挂。
我是给 CCF 送钱的那一批吧。
有帮助，赞一个