存在长度为 n 的a1,…,an
和长度为m 的b1....bm
| 运算 ： 1000|0110=1110 ，即: 保留所有的1
^ 运算：1110^1000=0110 , 即：一样为1的位变为0，其他位有1为1
由于位运算是针对数字的二进制下的每一位单独的运算，所以我们单独抽出数字b中某一位进行模拟，可以得出以下规律：
①当数字b的第 t 位为1时：
则进行对所有a1~an进行ai=ai∣b 的操作时
a1~an的每个数字的第 t 位都会变成1
则x的第t位只取决于 n的奇偶性
当n%2==1时：
x的第 t 位为1
当n%2==0时：
x的第t 位为 0
②当数字b的第 t 位为0 时：
则进行对所有a1~an进行ai=ai∣b 的操作时
a1~an的每个数字的第 t 位都不变
则对于x的第t位无影响
综上我们可以发现：只有b中的1可以影响x的值，同时 ③当n为偶数时，每次进行操作都会使x中的0增多或不变，即 ： 使x减小或不变
当n为奇数时，每次进行操作都会使x中的1增多或不变，即 ： 使x增大或不变
所以我们可以很快得出结论，当n为偶数时：x_max=a1^a2^a3,,,,^an
当n为奇数时：x_min=a1^a2^a3,,,,^an
要求 n为奇数时的最大值 和 n为偶数时的最小值 则 由结论③的出，要对a1..an进行最多次的操作 即要使b1,,,bm都进行ai=ai∣b 的操作
由于 | 是保留所有的1 的操作，所以 算得 b_max=b1|b2|...|bm 来获取最后能够通过操作得到的最多的 1
则 当n为奇数时：x_max=x|b_max ( x=a1^a2^a3,,,,^an)
当n为偶数时：由于b_max的操作使得b_max中为1的位 在x中为0，而b_max中为0的位，在x中不发生改变
所以可以得到 当n为偶数时：x_min=x&（~b_max）
python3
time=int(input()) for i in range(time): [n,m]=[int(i) for i in input().split()] a_list=[int(i) for i in input().split()] b_list=[int(i) for i in input().split()] x1=a_list[0] bm=b_list[0] for i in a_list[1:]: #得到x x1=x1^i for i in b_list[1:]:#得到b_max bm=bm|i if n%2==1: #奇偶类型分类 x_min=x1 x_max=x1|bm elif n%2==0: x_max=x1 x_min=x1 & (~bm) print(x_min,x_max)
这不是我写的但思想应该差不多吧
c++
#include<bits/stdc++.h>
using namespace std;
int a[200050],b[200050];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
int ans1=0;
for(int i=1;i<=n;i++){cin>>a[i];ans1^=a[i];}
for(int i=1;i<=m;i++)
{
cin>>b[i];
b[i]|=b[i-1];
}
for(int i=1;i<=n;i++){a[i]|=b[m];}
int ans2=0;
for(int i=1;i<=n;i++){ans2^=a[i];}
cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl;
}
}
京公网安备 11010502036488号