是只调整锦标赛树上从这个人到根的路径上,所有原本胜出者不是这个人的场次。
题解
以这张图为例,蓝色线=晋级,黑色线=淘汰

显然2号早在第一场比赛的时候就被淘汰了,也就是说从根节点到2叶子结点的路上一直是1号在赢。但是实际上赞助商只需要让2号打败1号,因为在设定中 1和2比赛的胜者是最终胜出的。
而如何避这个叙述坑,且听下回分解
当然因为我本人是脑残+智障,所以如果我题解哪里写错了欢迎爆杀qaq
剩下的三篇里面
第一篇
显然,我们可以看出,编号为 j 的节点要想成为胜利者,需要改变 popcount(j) 次结果,
第二篇
首先注意到我们同一层不可能会修改多次比赛结果,因为 Sponsors 一定会定准一个目标然后修改结果
因此某个叶子如果被选为冠军,那么根节点到叶子节点这条路上的边一定都被选中了,而如果某个叶子节点到根的路径上有小于等于 k 条边没有被选中,那么这个点可能会被 Sponsors 选为冠军,因此我们要让这些点编号都小,设答案为 ans 那么这些点的编号应为 [1,ans]。
我有一些小疑问:
- 虽然会这道题的和部分不会的都知道同一层比赛最多修改一场就能达到最劣情况,但是“不可能”“一定”等字眼个人认为太过绝对,而且可能需要稍微补充一下这样的说明。
- 被选中是否应该修改为“胜出”?因为如果本来就是胜场便无需更改结果。