题目大意
分成 \(x\) 堆，是的每堆的和的异或值最小
分析
这是一道非常简单的数位 \(DP\) 题
基于贪心思想，我们要尽量让最高位的 \(1\) 最小， 因此我们考虑从高位向低位进行枚举，看是否存在一种方案使得最高为不为 \(1\)，如果不存在，那就填 \(1\)
因此我们要解决如下问题：
- 保存之前的状态
- 考虑 \(A\), \(B\) 的限制
我们设已经考虑到 \(x\) 位，并且当前的值为 \(ans\)
显然如果该位可以不填，它必须满足存在一种状态使得之前已经决定的状态的异或和为 \(ans\)， 并且新增的一段不会使得 \(ans\) 改变
那这就是一个经典的区间DP问题 我们不妨设 \(f[i][j]\) 表示前 \(i\) 个数分成 \(j\) 段，是否存在这一种情况 如果满足上述条件，我们就能够从 \(f[k][j - 1]\) 转移到 \(f[i][j]\)对于每个一位，如果有一种给情况使得当前为为0，那就让 \(ans\) 的当前位为 \(0\)
复杂度：\(O(n^3logD)\)
对于最后一组数据：\(A =1, B \le n\)，段数只有上限
我们要想把 \(f\) 数组的第二个维度省掉的话，用 \(f[i]\) 记录将前 \(i\) 个数分段并得到可行解的最小段数，最后判断其是否小于 \(B\)，即可 复杂度：\(O(n^2logD)\)总结
想了半天发现 \(O(n^3logD)\) 没办法优化，结果发现最后一个点的 \(A = 1\)。
const int maxn = 2018;typedef long long LL;LL s[maxn];int f[maxn][maxn], g[maxn];LL ans = 0, t;int n, A, B, len = 0;bool valid(LL val, int dig) { return ((val >> (LL)dig | ans) == ans && (val & 1LL << (LL)dig-1LL) == 0);}void work1() { for(int x = len; x > 0; -- x) { forn(i, n) g[i] = INF; forn(i, n) Forn(j, i) if (g[j] < B) { t = s[i] - s[j]; if(valid(t, x)) if (g[j] + 1 < g[i]) g[i] = g[j] + 1; } ans <<= 1LL; if(g[n] > B) ans ++; }}void work2() { for(int x = len; x > 0; -- x) { memset(f, 0, sizeof(f)); f[0][0] = 1; forn(i, n) forn(j, i) for (int k = 0; k < i; ++ k) if(f[k][j-1]) { t = s[i] - s[k]; //printf("x = %d i = %d j = %d k = %d t = %d\n", x, i, j, k, t); if(valid(t, x)) f[i][j] = 1; } int i; for(i = A; i <= B; ++ i) { if(f[n][i]) break; } ans <<= 1LL; if(i > B) ans ++; }}int main() { read(n, A, B); forn(i, n) { read(s[i]); s[i] += s[i-1]; } len = (int)log2(s[n]) + 1; if (A == 1) work1(); else work2(); printf("%lld", ans); return 0;}