CF1870B

guozhe6241 · 2023-11-04 11:45:44 · 题解

模拟赛时过的一道题，看了大佬的题解，感觉不用那么麻烦。

题目传送门

CF1870B

题意

给你一个长度为 n 的数组 a，一个长度为 m 的数组 b。你可以进行若干次操作：选出 b 中的任意一个元素 b_j，然后令所有 a 中的元素 a_i 变为 a_i \operatorname{or} b_j（或运算）。请你求出若干次操作后，数组 a 所有元素的异或和的最小值与最大值。此处的“异或和”是指进行操作后，求 a_1 \operatorname{xor} a_2 \operatorname{xor} \dots \operatorname{xor} a_n 的最大值和最小值。

思路

思路很简单。最小值就是异或奇数的情况。最大值是不异或的情况。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
int t,n,m;
int a[maxn],b[maxn];
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        int ansmin=0,minnn=0,minx=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=m;i++){
            cin>>b[i];
            minx|=b[i];
        }
        for(int i=1;i<=n;i++){
            minnn^=a[i];
            ansmin^=(a[i]|minx);
        }
        cout<<min(ansmin,minnn)<<" "<<max(ansmin,minnn)<<endl;
    }
    return 0;
}

AC记录