题解 P5994 【[PA2014]Kuglarz】

逃离地球 · 2020-08-18 16:37:57 · 题解

题目大意

• 桌子上有 n 个杯子排成一行，其中某些杯子下藏有一个小球。你可以花费 c(l,r) 元，询问区间 [l, r] 内球总数的奇偶性。求猜出每个杯子是否有球的的最小花费。

题解

• 猜出每个杯子里是否有小球相当于我们知道每个杯子里小球个数的奇偶性。

• 当我们知道区间 [l,r_1] 和区间 [l,r_2] 的奇偶性后，我们就能知道区间 [r_1+1,r_2] 的奇偶性。

• 考虑把 n 个杯子看作 n 个点，把知道 [l,r] 的奇偶性看作从 l 点到 r 点连边。那么图中有边 (l,r_1) 和边 (l,r_2) 就相当于图中有边 (r_1+1,r_2)。

• 但是感觉这条性质不是很好用，因为不能推导出连通性。如果能把 r_1+1 里的 +1 去了，就能推到出一条很强的性质：两点之间联通相当于两点之间有一条边。

• 于是考虑改变边的定义，知道 [l,r] 的奇偶性相当于从 l-1 到 r 连边。那么有边 (l,r_1) 和边 (l,r_2) 就相当于有边 (r_1,r_2)。也就是说，两点之间联通相当于两点之间有一条边。

• 再看我们的目的：知道每个杯子里小球个数的奇偶性。放在那张图中，就是要让所有的点 i-1 和点 i 都联通。也就是说，这张图是一张连通图。

• 于是，我们先把图建出来，在点 l-1 和 点 r 之间连一条边权为 c(l,r) 的边。然后再选出其中的一些边，使得这张图是一张连通图。

• 同时我们还要最小化花的钱，即最小化选出的边权的和。

• 求出这张图的最小生成树即可，时间复杂度 O(n^2 \log n)。