可能更好的阅读体验
发现有些洛谷折叠框不能在 ACGO 讨论区很好的渲染,所以将就着看吧,更好的阅读体验可以直接看原文。
本文章会持续更新。
引言
* 2026 csp-s 同年龄选手省排 30+。
不敢说目标是进队,但再怎么样我也不想让童年的梦就此草草落幕。
PART 1
> 短期的目标是以每周六到下周五(恰好是一周,为什么不是完整的一周有个人原因)为一个周期,就近年真题单独训练部分知识点。
WEEK 1(4.4-4.10)
> 图论 MST
P14362 [CSP-S 2025] 道路修复
* 难度:蓝
* 耗时:浏览题解 fv9j9qo5 思路后 30min 调出
水蓝。
本题部分分非常充裕,考虑直接暴力枚举每个乡村是否进行城市化改造,再暴力求 MST 最小代价更新答案,可以得到 48pts 的高分,考场上我是对其又进行了一部分随机化乱搞拿到了 60pts。
考场代码又臭又长,也没有参考价值就不放了。
::::error[48pts]
::::
注意到所有非原图 MST 的边无论是否加入城市化改造乡村的边,都是没有任何竞争力的,可以直接扔掉。
这步操作将一次 solve 的复杂度从 O(mlogm)O(m\log m)O(mlogm) 优化到了 (nklognk)(nk\log nk)(nklognk),可以得到 80pts,这里已经非常接近正解了。
::::warning[80pts]
::::
注意到 dfs 函数已经无法优化了(严谨地表述是很难优化),算法瓶颈在于 solve 函数中的 sort。考虑提前排序好,若该边不在所选边的集合中,直接跳过即可。
::::success[100pts]
::::
P1967 [NOIP 2013 提高组] 货车运输
* 难度:蓝
* 耗时:一眼瞪出正解,实现花了 30min+。
* 二刷
这纯拼好题吧,咋这么板。
显然走一条限重小的边当且仅当它能连通两个连通块,不得不走。所以考虑直接对原图按边权降序排序后做一个 Kruskal,所有非树边没有任何价值。求出重构树后问题等价于求树上两点之间路径边权最小值,LCA 实现。
::::success[100pts]
Link
::::
CF1245D SHICHIKUJI AND POWER GRID
* 难度:绿
* 耗时:12min
双倍经验:P1550。
板板板。
考虑建一个超级源点,用于记录一个点是否通上电,然后暴力建边跑 Kruskal。
::::success[100pts]
Link
::::