可能更好的阅读体验
发现有些洛谷折叠框不能在 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
::::
AT_ABC270_F [ABC270F] TRANSPORTATION
* 难度:绿
* 耗时:忘了,30min-。
板板板。
与上类似,建两个超级源点。
::::error[WA 1+15]
Link
::::
注意到当 1−n1-n1−n 的点已经联通后,两个超级源点没有连通的必要。
继续只跑一遍 Kruskal 特判一些东西也是可做的,但是就
* 机场港口都不用
* 只用机场
* 只用港口
* 机场港口都用
分四类取最优值更清晰。
::::success[AC]
Link
::::
CF1120D POWER TREE
* 难度:紫
* 耗时:思考近一天无果浏览 z692g8r0 题解后 1h 内调出
难难难。
妙妙题。
这里只介绍本题中我认为最精华的转换部分,细节可以参考原题解。
注意到任意节点的子树内时间戳都是连续的,所以我们可以将每一个点所能控制的叶节点抽象成一个区间(为了使相邻叶节点的时间戳连续,这里只对叶节点计算时间戳)。
所以问题变为给定一个序列和若干个区间,每个区间对应一个代价,每次可以将区间内的元素任意加减,求将序列元素全部清零的最小代价以及方案,
不妨考虑差分,对于 [l,r][l,r][l,r],每次可以将 dld_ldl 上的数全部移至 dr+1d_{r+1}dr+1 ,直到所有数都在 dn+1d_{n+1}dn+1 上(这里 ddd 为差分数组)。
再做一步转换:[l,r][l,r][l,r] 对应着连接 lll 和 r+1r+1r+1 的边,求使 n+1n+1n+1 与其它节点连通的最小代价。
MST 实现即可。
::::success[AC]
Link
::::