CSP-J2925T3题解

解析

思路1

令前缀异或和 $S_{x} = a_{1} ⊕ a_{2} ⊕ … ⊕ a_{x}$，则区间 $[l,r]$ 异或和可以表示为 $S_{r} ⊕ S_{l -1}$。则在右端点固定为 $R$ 时，找到任意满足 $S_{l - 1} = R ⊕ K$ 的 $l$ 等同于为一合法区间，为使区间长度尽可能小，我们选择最大的合法 $l$。可以维护 $pos_{x}$ 表示前缀中满足 $s_{y} = x$ 的最大的 $y$。在记动态规划状态 $f_x$ 表示前 $x$ 个数中的最大和发区间数，则有动态规划转移方程

$f$ 中的最大值即为答案。

思路2

前半部分推导同解法一，随后，我们考虑使用贪心法，我们要取出足够多的区间，假设我们最终取出了若干个不交区间作为答案集合，那么考虑这个答案里的最左边的集合，它的右端点一定是越靠左越好，将这个最左边的区间取出来之后，相当于我们无法再取任何左侧的点了，那么在剩下的部分中，我们依然是取一个越靠左越好的区间。因此，我们的做法就可以是，从左到右按顺序扫描，每次一旦发现一个合法的区间，就直接取出来，并让答案+1，之后再取区间只能取当前这个点右侧的区间，一直取到最后没有合法区间为止，就能得到答案。判断合法区间的方式就是判断 $pos_{x}$ 是否在上一次取的区间右端点的右侧即可。

答案

思路1

#include <bits/stdc++.h>
#define ll long long
#define N 1050000
using namespace std;

ll n, K, num[N], dp[N], pos[N];

int main()
{
	memset(pos, -1, sizeof(pos));
	cin >> n >> K;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
		num[i] ^= num[i - 1]; // 维护异或前缀和
	}

	pos[0] = 0;
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = dp[i - 1];
		if (pos[num[i] ^ K] != -1)
			dp[i] = max(dp[i], dp[pos[num[i] ^ K]] + 1); // 状态转移
		ans = max(ans, dp[i]);							 // 求最大值
		pos[num[i]] = i;								 // 记录各个异或前缀和的位置
	}
	cout << ans;
}

思路2

#include <bits/stdc++.h>
#define ll long long
#define N 1050000
using namespace std;

ll n, K, num[N], dp[N], pos[N];

int main()
{
	memset(pos, -1, sizeof(pos));
	cin >> n >> K;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
		num[i] ^= num[i - 1]; // 维护异或前缀和
	}

	pos[0] = 0;
	ll ans = 0;
	int last_r = 0;
	for (int i = 1; i <= n; i++)
	{
		if (pos[num[i] ^ K] >= last_r)
		{
			last_r = i;
			ans++;
		}
		pos[num[i]] = i; // 记录各个异或前缀和的位置
	}
	cout << ans;
}