题解：P11472 命运黄之瓜

NewInTown · 2024-12-24 12:07:38 · 题解

出题人来啦~

~大家要好好品鉴题目背景哦~

以下是正文：

不妨假设 a_1⊕a_2⊕\cdots⊕a_n 不大于 b_1⊕b_2⊕\cdots⊕b_n。所以我们需要最大化 a_1⊕a_2⊕\cdots⊕a_n。

令 c_i=a_i\cdot(2^{31})+b_i。对 c 做线性基得到线性基 C。

从高向低枚举答案的第 i 位，对于第 i 位，先假设其为 1：

• 由于 a 小于 b，所以可以确定 a 的 i 至 30 位的值，使用线性基 C 的 i+31 至 61 位构造 a。

• 将 C 的 0 至 i+30 位取出，将这 i+31 个数分别并上 (2^{31}-1) 后，再做一次线性基得到线性基 D。

• 不难发现可以使用 D 确定 b 的最大值 b_{\max}，若 \frac{b_{\max}}{2^{i}}<\frac{a}{2^{i}} 则与 a 不大于 b 矛盾。

不难发现若第一步构造成功并且第三步没有矛盾则表明答案的第 i 位可以为 1，否则一定为 0。

枚举结束即可得到 a 和 b，注意需要再次判断 a 与 b 的大小，即可得到答案。至此此题完结。

单次询问时间复杂度 O(n\log v+\log^3v)。

std：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
const int MAXN=2e5+5;
int a[MAXN],b[MAXN],n;
void add(ll *a,ll x) {
    for(int j=61; j>=0; j--)if(x>>j&1) {
            if(!a[j]) {
                a[j]=x;
                return;
            } else x^=a[j];
        }
}
int work(int* a,int* b) {
    ll c[62]= {0},d[62]= {0};
    for(int i=1; i<=n; i++)add(c,(ll)a[i]<<31|b[i]);
    int A=0,B=0;
    for(int i=30; i>=0; i--)if(c[i+31]) {
            if(~A>>i&1) {
                A^=c[i+31]>>31;
                B^=c[i+31]&0x7fffffff;
            }
            memcpy(d,c,sizeof(ll)*31);
            for(int j=31; j<i+31; j++)add(d,c[j]&0x7fffffff);
            int nb=B;
            for(int j=30; j>=0; j--)nb=max((ll)nb,nb^d[j]);
            if((nb>>i)<(A>>i)) {
                A^=c[i+31]>>31;
                B^=c[i+31]&0x7fffffff;
            }
        }
    for(int j=30; j>=0; j--)B=max((ll)B,B^c[j]);
    return min(A,B);
}
int main() {
    int t;
    cin>>t;
    while(t--) {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)scanf("%d",a+i);
        for(int i=1; i<=n; i++)scanf("%d",b+i);
        printf("%d\n",max(work(a,b),work(b,a)));
    }
    return 0;
}