题解

A

若 为奇数，输出 0。

若 为偶数且 存在小于 的奇数，输出 1。

否则输出 -1。

B

若 ，则 1 1 和 n n 中必有一个是答案。

若 ，则交换从高到低 和 不同的那一位。

C

可以发现，最优解必然在 、、 三组解中的一组，逐一验证取最优即可。

D

首先发现，如果要删除障碍物，一定是删除一段连续的障碍物最优。

还可以发现，当 时，，因此仅需要考虑 。

至此，可以暴力枚举所有的删除情况并取最优，第一层循环枚举所有障碍物，称当前枚举至第 个障碍物。

第二层再枚举它前面的第 个障碍物 ，然后删除它们之间的 个障碍物，并用 更新答案 。

还需要考虑边界，为此添加两个分别位于 的障碍物即可规避对边界的讨论。

E

考虑先构造一条 的链，边权分别以 分配。

那么对于 个点的完全图的情况，接下来一次考虑边 ，对于边 ，所分配给它的边权必须满足它大于等于链 的边权和。

可以如下分配边权。（给出 的情况，邻接矩阵）

对于非完全图的情况，把大的边去掉即可。

F

可以发现，每次碰撞，都会使得胜利方的球的大小减小。因此，若玩家 想要获胜，最好的情况是让它参与最后一次碰撞即可。

问题转变为，对于每个 ，将除了 以外的球碰撞合并为一个球，然后和 比大小。有一个贪心的结论是，对于一堆球要碰撞，每次取最大的两个球碰撞，这样最终得到的球的大小一定是最小的。基于此有了一个 的做法。

再观察其他性质，如果一个较小的球最终能获胜，那么一个较大的球最终一定也能获胜。因此，在此基础上二分，得到了一个 的做法。