AT_zone2021_f题解

Fubaogege · 2024-03-18 19:09:28 · 题解

此题需要用到异或，没学过异或的人可以去百度上搜索。

进入正题，这题有很多的异或结果，我们除了 a_i，其它全部加入线性基，然后把它的结果存下来。

此题有 -1 的结果，我们可以看到，输出 -1 的条件是：没有存在线性基。

总结

将 1\sim n 除 a_i 以外全部加入线性基并存下他，如果没有，则输出 -1，否则输出他最大位数上的原数。

代码

两个自定义函数的代码（如上定义）：

void js1(int a){
    int t=a;
    for(int i=1;~i;i--){
        if((a&(1<<i))>0){
            if(!p[i]){
                p[i]=a;
                o[i]=t;
                return ;
            }
            else a=a^p[i];
        }
    }
}

int js2(int a){
    for(int i=19;~i;i--){
        if((a&(1<<i))>0){
            return a^o[i];
        }
    }
}

主函数代码（自定义函数用 jsx(xxx) 代替了）。

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int tt;
        cin>>tt;
        c[tt]++;
    }
    for(int i=1;i<n;i++){
        if(!c[i]){js1(i);}
    }
    int x;
    for(int i=19;~i;i--){
        if((1<<i)<=n){
            x=i;break;
        }
    }
    for(int i=0;i<x;i++){
        if(!p[i]){
            cout<<"-1";
            return 0;
        }
    }
    for(int i=1;i<n;i++){
        cout<<i<<" "<<js2(i)<<endl;
    }
    return 0;
}