题解：AT_zone2021_f 出会いと別れ

X_Acheron_X · 2024-05-31 18:05:17 · 题解

思路：线性基

考虑枚举所有点的异或是不可行的，但是题目只需要判断和给出一组答案，显然考虑用线性基。

如果线性基无法满足从最高位到最低为都有可以异或的数，显然输出 -1。

考虑构造答案。

只需要记录所找的数的最大位上异或的数的原数，并将其异或即可。

代码

#include<bits/stdc++.h>
using namespace std;
//线性基

#define N 19
const int maxn=1<<19;

int p[N];
int frm[maxn];
int a[maxn];
int cnt=0;

void add(int x){
    int orn=x;
    for(int i=N;~i;i--){
        if(x&(1<<i)){
            if(!p[i]){
                cnt++;
                p[i]=x;
                frm[i]=orn;
                return;
            }
            else x^=p[i];
        }
    }
}

int query(int x){
    for(int i=N;~i;i--){
        if(x&(1<<i)){
            return x^frm[i];
        }
    }
}

inline int read(){
    int r(0),w(1);char ch;
    while(ch=getchar(),ch>=58 || ch<=47)w=(ch=='-'?-1:1);r=(r<<3)+(r<<1)+ch-48;
    while(ch=getchar(),ch<=57 && ch>=48)r=(r<<3)+(r<<1)+ch-48;
    return r*w;
}

int main(){
    int n=read(),m=read();
    for(int i=1;i<=m;i++){int in=read();a[in]=1;}
    for(int i=0;i<n;i++)if(!a[i])add(i);
    if(cnt!=__lg(n)){cout<<"-1";return 0;}
    for(int i=1;i<n;i++)cout<<i<<" "<<query(i)<<'\n';
    return 0;
}