OI集训 Day29

Content：杂题
Date：2025.8.14

CodeForces-1870E Another MEX Problem

题目大意

给你一个数组 \(a\)，你可以选择任意互不相交的子数组，先计算每一个子数组的 MEX 值，然后将这些 MEX 值的异或和作为这个方案的价值，求你可以获得的最大价值。

解题思路

首先我们肯定可以暴力 DP，定义 \(dp_{i,j}\) 表示前 \(i\) 个数能否凑出价值为 \(j\) 的方案，转移显然是 \(O(n^3)\) 的。

考虑如何优化。由于 MEX 的性质，可以发现从 \(i\) 往后的一段区间内 MEX 值是单调不降的，所以其中一定有大量相等的段。这些段本质是一样的，所以我们只需要考虑那些前后不同的位置即可，这些符合条件的转移区间至多有 \(2n\) 个，所以哦我们就得到了复杂度为 \(O(n^2)\) 得做法。

提交记录：Link