出题人题解

A

若 $a_{1}a\_1$ 为奇数，输出 0。

若 $a_{1}a\_1$ 为偶数且 $a_2\to a_{n}a\_2\backslash to\; a\_n$ 存在小于 $a_{1}a\_1$ 的奇数，输出 1。

否则输出 -1。

B

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

若 $A>BA\; >\; B$，则交换从高到低 $AA$ 和 $BB$ 不同的那一位。

C

可以发现，最优解必然在 $\{s=0,t=1\}\backslash \{s=0,t=1\backslash \}$、$\{s=10^9-1,t=10^9\}\backslash \{s=10^9-1,t=10^9\backslash \}$、$\{s=0,t=10^9\}\backslash \{s=0,t=10^9\backslash \}$ 三组解中的一组，逐一验证取最优即可。

D

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

还可以发现，当 $x>\sqrt{n}x>\backslash sqrt\; n$ 时，$L-x^2<0L-x^2\; \backslash lt\; 0$，因此仅需要考虑 $x\le \sqrt{n}x\backslash le\; \backslash sqrt\; n$。

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

第二层再枚举它前面的第 $x+1x+1$ 个障碍物 $jj$，然后删除它们之间的 $xx$ 个障碍物，并用 $a_i-a_j-x^{2}a\_i-a\_j-x^2$ 更新答案 。

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

E

考虑先构造一条 $1\to n1\backslash to\; n$ 的链，边权分别以 $1\to n-11\backslash to\; n-1$ 分配。

那么对于 $nn$ 个点的完全图的情况，接下来一次考虑边 $1\to 3,2\to 4,3\to \mathrm{5...}1\backslash to\; 3,2\backslash to\; 4,\; 3\; \backslash to\; 5...$，对于边 $u\to vu\backslash to\; v$，所分配给它的边权必须满足它大于等于链 $u\to vu\; \backslash to\; v$ 的边权和。

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

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

F

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

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

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