CF1870B-Friendly-Arrays-题解

title: CF1870B Friendly Arrays 题解
date: 2023-09-20 10:32:12
categories: 
 - 题解

翻译

给出长度为 \(n\) 的序列 \(a\) 和长度为 \(m\) 的序列 \(b\)，选出 \(b\) 中的任意个数（可以不选），让 \(a\) 的每个数都或上它们，求 \(a_1 \oplus a_2 \oplus \dots \oplus a_n\) 的最大值和最小值。

思路

令 \(x=a_1 \oplus a_2 \oplus \dots \oplus a_n\)。

当 \(m=1\) 时，如果选择 \(b_1\)，每个 \(a_i\) 在 \(b_1\) 每位为 \(1\) 的二进制位上也为 \(1\)，此时 \(x\) 在这些位上的值取决于 \(n\) 的奇偶性（\(n\) 个 \(1\) 异或）。取消 \(m\) 的限制，可以发现，每多取一个 \(b_i\)，\(x\) 只会不断变大或变小。

当 \(n\) 为偶数时，\(x\) 会不断变小，全部不选时值最大，全选时值最小；

当 \(n\) 为奇数时，\(x\) 会不断变大，全选时值最小，全部不选时值最大。

code：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10;
int t,n,m,a[N],b[N],suma,sumb;
signed main()
{
	scanf("%d",&t);
	while(t--)
	{
		suma=sumb=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),suma^=a[i];
		for(int i=1;i<=m;i++)scanf("%d",&b[i]),sumb|=b[i];
		if(n%2)printf("%d %d\n",suma,suma|sumb);
		else printf("%d %d\n",(suma|sumb)-sumb,suma);
	}
}