「DLESS-3」XOR and Split 题解

出题人题解。

可以暴力枚举划分，然后按照题意判断，复杂度是 $\mathcal O(n2^n)$ 的。

可以采用 DP 的方式求解所有可能异或出的权值。

设 $f_{i,j,k}$ 表示前 $i$ 个位置，分出了 $j$ 段，当前异或和为 $k$ 是否可行。

转移枚举一下上一个位置即可。

时间复杂度是 $\mathcal O(n^4)$ 的。

此处提出一个观察，一个段的长度至多为 $2$，可以通过调整的方法来说明，若有一个段的长度 $>2$，将其中两个位置放到最后形成一个贡献为 $0$ 的段，答案不变。

所以上文的转移是 $\mathcal O(1)$ 的，时间复杂度是 $\mathcal O(n^3)$ 的。

$n=2^k$ 的时候，直接分出 $n$ 段，$n>2$ 答案就是 $1\oplus 2\oplus ...\oplus n = n$，$n=2$ 答案是 $3$。

我们说明，当 $n\ge 4$ 时，$n$ 是 $2^k$ 的时候，答案是 $n$，否则是第一个满足 $2^i>n$ 的 $2^i-1$。

$n=2^k$ 的时候已经在 Subtask4 说明，现在我将证明 $n$ 不是二的幂次时的答案。

首先答案上界一定不超过 $2^i-1$，因为可能的最高位也是小于 $2^i$ 的。

下面给出一种可能的方法达到这个上界：

先看 $n=2^k+1$ 的情况，我们知道 $1\oplus 2\oplus ...\oplus (2^k-1)$ 是 $0$，所以可以这样构造：前 $2^k-2$ 段，每段长度是 $1$，然后一段长度是 $2$，最后一段长度是 $1$。

比如 $n=17$ 的时候，方案就是 1 2 3... 14 15 15 16。

这样就得到了 $2^k\oplus (2^k-1) = 2^{k+1}-1$。

然后和 $2^k+1$ 奇偶性相同的 $n$ 也是容易的，可以在后面加入两个元素构成的无用段。

再看 $2^k+2$ 的情况，我们把多一个的 $2^k-1$ 换成 $2^{k-1}$ 和 $2^{k-1}-1$，效果相同。

该做法在 $n$ 较小的时候没有足够的元素用来调整，所以特判 $n\le 4$ 即可。

时间复杂度 $\mathcal O(1)$，期望得分 $100$。