Codeforces Round #385 (Div. 1)

<br >

A.Hongcow Builds A Nation

贪心。

显然就是凑成一个最大的块即可

那么首先并查集处理已经确定的点

然后把剩下不确定的放到点数最多的一个块中

最后统计边数即可


B.Hongcow's Game

交互题

交互的方法比较特殊。

每次二分一部分区域,然后将可以补充的填上

也就是把矩阵不断的切成四块,然后依次补上

可以把一些子询问合并

因为可能有一半已经有结果了,不会有所影响

举个例子(官方题解):

First level:

[1,2,3,4]

[5,6,7,8]

Second level

[1,2],[5,6] (i.e. ask 1,2,5,6 all together, but this is actually two different subproblems, one for the top left, and one for the bottom right).

[3,4],[7,8]

Third level

[1],[3],[5],[7]

[2],[4],[6],[8]


C.Hongcow Buys a Deck of Cards

n那么小,一看就是状压dp

但是似乎不能直接转移,因为每单位时间获取的金币的话,获取的是1个red和1个blue

那么,我们考虑,再记录下,到当前状态所节省的red

用f[i][j]表示状态为i, 到当前状态所节省了red,最多能节省blue的值

暴力转移即可

最后的答案显然就是 \(max(sr-i,sb-f[(1<<n)-1][i])\) 中的最小值

其中sr、sb为red和blue的和