引言
** ACGO 他妈不要命了,敢拿 CSP/S 作为比赛名,侵犯 CCF 知识产权了,等着被罚款 1010010^{100}10100 元吧。
T1
最难的一题。最正常的一题。
首先有个直觉,按照任务结束时间进行 DP,定义 fif_ifi 为考虑时间 [0,i][0,i][0,i] 的最大收益,此时 fif_ifi 可以从 fi−1f_{i-1}fi−1 转移而来,或从所有任务在时间 rrr 结束的 fl+vf_l+vfl +v 得来。
然后发现数据范围 r≤109r\le 10^9r≤109,直接这样 DP 会炸。思考题目,发现我们不需要每个任务时间的具体值,只需要他们之间的相对数值,大概就是某个任务会不会和另一个任务时间有冲突。
所以我们可以把时间离散化一下,然后按上面的式子 DP 即可。在 l,rl,rl,r 中最多有 2n2n2n 中不同的取值,因此时间复杂度 O(mlogm)\mathcal{O}(m\log m)O(mlogm),mmm 与 2n2n2n 同阶,瓶颈在于排序。
TIPS
* 当数据满足特殊性质时有 O(nlogn)\mathcal{O}(n\log n)O(nlogn) 的贪心算法,瓶颈在于排序,这里不做讲解。
* 离散化:举个例子,当我们只想要元素之间的相对大小关系时,序列 [1,2,1000][1,2,1000][1,2,1000] 和 序列 [1,2,3][1,2,3][1,2,3] 便没有区别,所以就可以把很大的值域压到序列的长度,从而进行若干操作。本题解正是利用了这一点。
T2
私募出题人不给数据范围,还要老子自己猜。
AI做法:由于只有 111 条免费边,从 111 和 nnn 出发分别跑最短路 {ds},{dt}\{ds\},\{dt\}{ds},{dt},枚举每条边 (u,v)(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) (u,v)∈Gmin min(dsu +dtv ,dsv +dtu )
若 nnn 不可达,则输出 −1-1−1。时间复杂度为 O((n+m)logn)\mathcal{O}((n+m)\log n)O((n+m)logn)。
。
我的做法:分层图最短路。具体地说,将 u,vu,vu,v 连权值为 www 的双向边,u+n,v+nu+n,v+nu+n,v+n 连权值为 www 的双向边,u,v+nu,v+nu,v+n 和 v,u+nv,u+nv,u+n 连权值为 000 的单向边,跑出 1→2n1\rightarrow 2n1→2n 的最短路即可。自行理解。
T3
私募出题人不给数据范围,你家里人是批发的?
线段树板题,全场最**的题。
T4
私募出题人不给数据范围,家里少人了?
换根 DP 板题,fif_ifi 表示点 iii 的答案。先假设一个根 111,跑出 szusz_uszu 表示 uuu 的子树大小和 f1f_1f1 。
自上而下,转移为 fv=fu+(sz1−2×szv)×wf_v=f_u+(sz_1-2\times sz_v)\times wfv =fu +(sz1 −2×szv )×w。然后输出答案即可。线性复杂度。
结语
出这么**的题,还他妈没数据范围,出题人怕不是少了。