CF1717D Madoka and The Corruption Scheme

· · 题解

题目所问是：指定一个局面，使得在最坏情况下，赞助商做完调整后，获得冠军的人编号尽可能小。

考虑在最坏情况下，则面对一个我们指定的局面时，赞助商一定会将一个编号尽可能大的人送上去成为冠军。

易见，为了送一个人上去成为冠军，赞助商花费最少调整次数的方法，是只调整锦标赛树上从这个人到根的路径上，所有原本胜出者不是这个人的场次。

对于每一个人，锦标赛树上从其到根的每一场次，胜出者为子树内包含其的这一方则记为 1，否则记为 0，将这样的每一场次的情况按顺序连成一个二进制数，作为这个人的属性值。

可以看出，这个属性值有如下性质：

从而，所有属性值二进制表示中 0 的个数小于等于 k 的人，都可以成为冠军。赞助商一定会从这些人中选出编号最大的送上去成为冠军，我们要让成为冠军的人编号尽可能小，即求最小可能的最大编号，即为属性值二进制表示中 0 的个数小于等于 k 的人数。

这个人数，即

\sum_{i=0}^{\min(n,k)}\binom{n}{i}

容易做到 O(\min(n,k)) 的时间复杂度。