题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

~~本人作为 xxs 无法参加，但是看到如此简单的 T3 还是忍不住水一篇题解。~~

思路

先定义一些变量的含义。

对 $a$ 数组做一个前缀异或，记前 $i$ 个数的异或值为 $s_i$ 。
$cnt$ 数组记录每一个前缀异或出现的次数。
$pos$ 数组记录每一个前缀异或最后一次出现的位置
用 $l$ 记录 $1 \sim l$ 的数都无法作为区间的左端点。

然后从前往后扫一遍，需要更新答案的有两种情况：

$s_i=k$
$pos_{s_i} \ge l$ 且 $cnt_{s_i} > 0$

以上两种情况都要让

ans

加

1

，

l=i

。因为此时

i

已经被用过，若以

1 \sim i

中的任意一个数为左端点，则该区间一定包含

i

，这是不符合题意的。

注意：如果你是一边遍历一边做前缀异或，那请注意，遇到以上两种情况时，一定要让 $s$ 清零！

有人可能会问，数组到底要开多大呢？根据数据范围，

a_i \le 2^{20}

，异或一下顶多

2^{20}-1

（

20

位全是

1

），大概是

10^6

多，开到

2 \times 10^6

就足够了。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define mod 10007
#define for1(i, a, b) for (register int i = a; i <= b; i++)
#define for2(i, a, b) for (register int i = a; i >= b; i--)
#define pr(x) cout << "In line " << __LINE__ << ": " << #x << " = " << (x) << endl
const int N = 2e6 + 5;
int TT = 1, n, k;
int a[N], cnt[N], pos[N];

void solve()
{
	cin >> n >> k;
	for1(i, 1, n) cin >> a[i];
	int s = 0, ans = 0, l = 0;
	for1(i, 1, n){
		s ^= a[i];
        if (s == k || cnt[s ^ k] && pos[s ^ k] >= l){
			ans++; l = i; s = 0;
		}
		cnt[s]++; pos[s] = i;
	}
	cout << ans << endl;
}
	
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //cin >> TT;
    while (TT--) 
		solve();

    return 0;
}

题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

文章操作

思路

代码

相关推荐

评论

题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）