T3 eee考场上打的暴力但还是1=了

这道题最先想到的应该是暴力枚举 代码如下: 这样很明显是错的 举个例子: 8 3 2 3 0 3 1 0 7 4 上述代码仅会输出 2 （2 3 0 3 1 和 0 7 4） 这说明从左到右枚举是不合理的 那从右到左呢? 代码如下: 很好，程序已经能过15个测试点了，只有5个超时，那开始优化吧 很明显可以用动规 代码如下: 至此，题解 谢谢观看!

解析 思路1 令前缀异或和 Sx=a1⊕a2⊕…⊕axS_{x} = a_{1} ⊕ a_{2} ⊕ … ⊕ a_{x}Sx =a1 ⊕a2 ⊕…⊕ax ，则区间 [l,r][l,r][l,r] 异或和可以表示为 Sr⊕Sl−1S_{r} ⊕ S_{l -1}Sr ⊕Sl−1 。则在右端点固定为 RRR 时，找到任意满足 Sl−1=R⊕KS_{l - 1} = R ⊕ KSl−1 =R⊕K 的 lll 等同于为一合法区间，为使区间长度尽可能小，我们选择最大的合法 lll。可以维护 posxpos_{x}posx 表示前缀中满足 sy=xs_{y} = xsy =x 的最大的 yyy。在记动态规划状态 fxf_xfx 表示前 xxx 个数中的最大和发区间数，则有动态规划转移方程 fff 中的最大值即为答案。 思路2 前半部分推导同解法一，随后，我们考虑使用贪心法，我们要取出足够多的区间，假设我们最终取出了若干个不交区间作为答案集合，那么考虑这个答案里的最左边的集合，它的右端点一定是越靠左越好，将这个最左边的区间取出来之后，相当于我们无法再取任何左侧的点了，那么在剩下的部分中，我们依然是取一个越靠左越好的区间。因此，我们的做法就可以是，从左到右按顺序扫描，每次一旦发现一个合法的区间，就直接取出来，并让答案+1，之后再取区间只能取当前这个点右侧的区间，一直取到最后没有合法区间为止，就能得到答案。判断合法区间的方式就是判断 posxpos_{x}posx 是否在上一次取的区间右端点的右侧即可。 答案 思路1 思路2