题解 | #位域之中#

位域之中

https://ac.nowcoder.com/acm/contest/66846/J

存在长度为 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;
    }
}