2024HNCPC G - Utakotoba

直接贴码了，注释可能有误，欢迎指出

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


/*
注意掉操作过程其实是可逆的
swap有一种方法就是x=x^y y = x^y x = x^y,灵感来源?
所以说其实a,b数组是由基向量生成出来的,如果a数组可以变成b数组,那么他们的基向量得是等价的,既然是等价的必然可以相互转化
所以有了构造思路就是把数组变成同一组0000+基向量的形式
那么答案就是a变成基的正向过程+b变成基的逆向过程

details: 
(1)对两个不同位置的数操作其实就是把一个数swap到另一个数旁边异或一下，再swap回去
*/
int n;
inline void solve(){
    cin>>n;
    vector<int>c(n+1),b(n+1);
    for(int i = 1;i<=n;++i) cin>>b[i];
    for(int i = 1;i<=n;++i) cin>>c[i];
    auto get=[&](vector<int> &a)->vector<pair<int,int>>{
        vector<int> base(20),pos(20,-1),ff(n+1,-1);//基,基的位置,位置的基(逆映射)
        vector<pair<int,int>> op;
        auto swp=[&](int x,int y)->void{
            op.push_back({x,y});
            op.push_back({y,x});
            op.push_back({x,y});
        };
        auto insert=[&](int x,int po)->void{
            for(int i = 15;i>=0;--i){
                if(!((x>>i)&1)) continue;
                if(!base[i]){
                    base[i] = x;
                    pos[i]=po;
                    ff[po]=i;
                    break;
                }else x^=base[i];
            }
        };

        auto XOR=[&](int l,int r)->void{
            if(l<=r){
                for(int i = l+1;i<=r-1;++i) swp(i,i-1);
                op.push_back({r-1,r});
                for(int i = r-2;i>=l;--i) swp(i,i+1);
            }else{
                for(int i = r;i<=l-2;++i) swp(i,i+1);
                op.push_back({l,l-1});
                for(int i = l-1;i>r;--i) swp(i,i-1);
            }
        };

        //插入线性基
        for(int i = 1;i<=n;++i) insert(a[i],i);

        //将线性基从高位到低位提前
        int l = 0;//目前基的个数
        for(int i = 14;i>=0;--i){
            if(!base[i]) continue;
            ++l;
            for(int j = pos[i];j>l;--j){
                if(ff[j]!=-1) pos[ff[j]]=j-1;
                if(ff[j-1]!=-1) pos[ff[j-1]]=j;
                swap(ff[j],ff[j-1]);
                swap(a[j],a[j-1]);
                swp(j,j-1);
            }
        }

        //构造线性基,类似于高等代数里面的化成阶梯型
        /*
        1 1 0 0 1    (1)
        1 0 1 0 0    (2)
        0 1 1 1 0    (3)
        1 0 0 1 0    (4)
        0 0 0 1 1    (5)
        
        先把第一列第一行下面的1全消掉
        先把第二列第二行下面的1全消掉
        ...
        */
        //整个过程是看i这个可以变成基向量元素前面不应该是1的位置把它处理掉
        for(int i = 1;i<=l;++i){//从高位到低位处理
            for(int j = 14;j>=0;--j){//从高位到低位处理
                if(pos[j]==i) break;
                if(base[j]&&((a[i]>>j)&1)){
                    a[i]^=base[j];
                    XOR(i,pos[j]);
                }
            }
        }
        //化成最简形式,类似于把阶梯型矩阵化成行最简形式
        //把第i行第j列上下的1全部消掉，因为已经是阶梯型，所以只有那些基里的1要消了
        for(int i = 14;i>=0;--i){
            for(int j = i-1;j>=0;--j){
                if(base[j]&&(base[i]>>j)&1){
                    a[pos[i]]^=base[j];
                    base[i]^=base[j];
                    XOR(pos[i],pos[j]);
                }
            }
        }
        //把最前面的L个线性基换到最后面,将后面经过的全部位置变成0
        for(int i = l,r=0;i>=1;--i,++r){
            for(int j = i;j<n-r;++j){
                swp(j,j+1);
                swap(a[j],a[j+1]);
                int now = a[j];
                for(int k = 14;k>=0;--k){
                    if(base[k]&&(now>>k&1)){
                        now^=base[k];
                        if(pos[k]==i){//刚好用的是当前这个异或操作且需要异或
                            a[j]^=base[k];
                            op.push_back({j,j+1});
                        }
                    }
                }
            }
        }
        return op;
    };
    vector<pair<int,int>>op1 = get(b);
    vector<pair<int,int>>op2 = get(c);
    reverse(op2.begin(),op2.end());
    cout<<op1.size()+op2.size()<<"\n";
    for(auto i:op1) cout<<i.first<<" "<<i.second<<"\n";
    for(auto i:op2) cout<<i.first<<" "<<i.second<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/theskyinblue/article/details/143695628

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！