ACGO CSP/S 比赛题解

userId_undefined
Zzzzzzsr（单身十年换S1
出道萌新出题人代码纠察员

2026-10-19 20:52:41

发布于：广东

21阅读
0回复
0点赞

引言

** ACGO 他妈不要命了，敢拿 CSP/S 作为比赛名，侵犯 CCF 知识产权了，等着被罚款 1010010^{100} 元吧。

T1

最难的一题。最正常的一题。

首先有个直觉，按照任务结束时间进行 DP，定义 fif_i 为考虑时间 [0,i][0,i] 的最大收益，此时 fif_i 可以从 fi−1f_{i-1} 转移而来，或从所有任务在时间 rr 结束的 fl+vf_l+v 得来。

然后发现数据范围 r≤109r\le 10^9，直接这样 DP 会炸。思考题目，发现我们不需要每个任务时间的具体值，只需要他们之间的相对数值，大概就是某个任务会不会和另一个任务时间有冲突。

所以我们可以把时间离散化一下，然后按上面的式子 DP 即可。在 l,rl,r 中最多有 2n2n 中不同的取值，因此时间复杂度 O(mlog⁡m)\mathcal{O}(m\log m)，mm 与 2n2n 同阶，瓶颈在于排序。

tips

  • 当数据满足特殊性质时有 O(nlog⁡n)\mathcal{O}(n\log n) 的贪心算法，瓶颈在于排序，这里不做讲解。
  • 离散化：举个例子，当我们只想要元素之间的相对大小关系时，序列 [1,2,1000][1,2,1000] 和 序列 [1,2,3][1,2,3] 便没有区别，所以就可以把很大的值域压到序列的长度，从而进行若干操作。本题解正是利用了这一点。

T2

私募出题人不给数据范围，还要老子自己猜。

AI做法：由于只有 11 条免费边，从 11 和 nn 出发分别跑最短路 {ds},{dt}\{ds\},\{dt\}，枚举每条边 (u,v)(u,v) 作为免费边，答案为

min⁡(u,v)∈Gmin⁡(dsu+dtv,dsv+dtu)\min_{(u,v)\in G} \min(ds_u+dt_v,ds_v+dt_u)

若 nn 不可达，则输出 −1-1。时间复杂度为 O((n+m)log⁡n)\mathcal{O}((n+m)\log n)。
。
我的做法：分层图最短路。具体地说，将 u,vu,v 连权值为 ww 的双向边，u+n,v+nu+n,v+n 连权值为 ww 的双向边，u,v+nu,v+n 和 v,u+nv,u+n 连权值为 00 的单向边，跑出 1→2n1\rightarrow 2n 的最短路即可。自行理解。

T3

私募出题人不给数据范围，你家里人是批发的？

线段树板题，全场最**的题。

T4

私募出题人不给数据范围，家里少人了？

换根 DP 板题，fif_i 表示点 ii 的答案。先假设一个根 11，跑出 szusz_u 表示 uu 的子树大小和 f1f_1。

自上而下，转移为 fv=fu+(sz1−2×szv)×wf_v=f_u+(sz_1-2\times sz_v)\times w。然后输出答案即可。线性复杂度。

结语

出这么**的题，还他妈没数据范围，出题人怕不是少了。

userId_undefined
去预览
0/2000

全部评论 8

热门讨论