「DLESS-3」XOR and Split 题解
紊莫
·
·
题解
出题人题解。
Subtask 1
可以暴力枚举划分，然后按照题意判断，复杂度是 \mathcal O(n2^n) 的。
Subtask 2
可以采用 DP 的方式求解所有可能异或出的权值。
设 f_{i,j,k} 表示前 i 个位置，分出了 j 段，当前异或和为 k 是否可行。
转移枚举一下上一个位置即可。
时间复杂度是 \mathcal O(n^4) 的。
Subtask 3
此处提出一个观察，一个段的长度至多为 2，可以通过调整的方法来说明，若有一个段的长度 >2，将其中两个位置放到最后形成一个贡献为 0 的段，答案不变。
所以上文的转移是 \mathcal O(1) 的，时间复杂度是 \mathcal O(n^3) 的。
Subtask 4
## Subtask 5
我们说明，当 $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$。