BZOJ 3714: [PA2014]Kuglarz Kruskal

题目能转化成最小生成树,挺神奇的。想了半天没想出来。

用sum[i]表示前i个杯子底球的总数,知道一个c[i][j],等于是知道了sum[j]和sum[i-1]的差的奇偶性。而sum[0]是知道的,所以只需要知道所有sum[i]与sum[0]的差的奇偶性,我们一位一位向前推,就可以推出每个杯子是否有球。这个奇偶性和sum都是可以满足两个相邻区间相加的。就类似从0走树上的边到一个点。

这样子,我们对于每个Cij建一条边,然后MST的答案就是所求。

发表评论