NOIP2023模拟7联测28 异或-Toy模板网

这篇具有很好参考价值的文章主要介绍了NOIP2023模拟7联测28 异或。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目大意

给定一个长度为 $n$ 的由非负整数组成的序列 $a$ ，你们需要进行一系列操作，每次操作选择一个区间 $[l, r]$ ，对于所有 $l\leq i\leq r$ ，将 $a_i$ 异或上 $w$ 。你需要将所有 $a_i$ 都变为 $0$ ，求最小的操作次数。

$1\leq n\leq 17,0\leq a_i\leq 10^{18}$

题解

首先我们设序列 $d$ 为序列 $a$ 的差分序列（即 $d_i=a_i\oplus a_{i-1}$ ），于是我们就可以将区间修改变成单点修改（后缀区间修改）或双点修改（非后缀区间修改）。

求出差分序列后，我们在差分序列上操作，题意变为要将所有 $d_i$ 变为 $0$ 。

我们先不考虑 $w$ 的取值，而考虑如何取区间 $[l, r]$ 。将 $n$ 个数看成 $n$ 个点，将修改操作看成连接两个修改点的无向边（或自环）。那么，一组合法的方案由若干个连通块组成。

考虑每个连通块的最小边数，设这个连通块的大小为 $x$ ，则最小边数的下界为 $x - 1$ （即一棵树），上界为 $x$ （将其中一个点连向其他所有点，再在这个点上连一个自环即合法）。我们考虑如何取到下界。

我们发现，可以取到这个下界当且仅当连通块内的数异或和为 $0$ 。

必要性： 每次操作都是双点修改，那么整个连通块内的数的异或和不变，如果最终的异或和为 $0$ ，则开始时异或和必须为 $0$ 。

充分性： 考虑用一条链串起这个连通块中的所有数，每次将链头通过异或自己的方式删掉，下一个数受到影响后成为新的链头。那么，经历 $x - 1$ 次操作后，最后一个数肯定为 $0$ ，不需要再对其操作了。

也就是说，我们要将差分序列 $d$ 分成若干个子序列，对于每个子序列：

当其异或和为 $0$ 时，其权值为 $x - 1$
否则，其权值为 $x$

我们要求一种划分方式，使得权值和最小。

可以发现，答案就是 $n$ 减去划分出的子序列中异或和为 $0$ 的子序列的数量，那我们要使划分出的子序列中异或和为 $0$ 的子序列的数量最大，可以用状压 $D P$ ，设 $f_s$ 表示 $d$ 的子序列 $s$ 可以划分成多少个异或和为 $0$ 的子序列，那么枚举子集的子集来转移即可。

可以先预处理出每个子序列的异或和。

时间复杂度为 $O(3^n)$ 。文章来源地址https://www.toymoban.com/news/detail-735194.html

code

#include<bits/stdc++.h>
using namespace std;
int n,f[1<<20];
long long a[25],d[25],v[1<<20];
int main()
{
//	freopen("xor.in","r",stdin);
//	freopen("xor.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);d[i]=a[i]^a[i-1];
	}
	for(int s=1;s<1<<n;s++){
		for(int i=1;i<=n;i++){
			if((s>>i-1)&1) v[s]^=d[i];
		}
	}
	for(int s=1;s<1<<n;s++){
		for(int t=(s-1)&s;t;t=(t-1)&s){
			f[s]=max(f[s],f[t]+f[s^t]);
		}
		if(v[s]==0) f[s]=max(f[s],1);
	}
	printf("%d",n-f[(1<<n)-1]);
	return 0;
}