【1】做题心得 - 2025 NOIP #65 - T1【构造】【神人】

ExFish · 2025-11-19 14:33:46 · 题解

构造不太容易但是思路是不困难的。你发现显然是需要一次异或对齐 a,b 才好修改 a 最高位为 c。然后不停右移异或使得 a=c 让 b 为 0 一次异或既可以解决，最劣情况 64 次操作计算完成呢。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,c;
vector<int>op;
int ls(int x){
    for(int i=30;~i;i--)if((x>>i)&1) return i+1;
    return 0;
}
int main(){
    freopen("kks.in","r",stdin);
    freopen("kks.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>a>>b>>c;
        if(a==b&&b==c){ cout<<"0\n\n";continue; }
        if(a==b&&b==0){ cout<<"-1\n";continue;  }
        op.clear();
        if(ls(a)<ls(b)) a^=b, op.push_back(3);
        if(ls(b)<ls(a)) b^=a, op.push_back(4);
        if(ls(c)<ls(a)){
            while(ls(b)>ls(c)){
                if(ls(b)==ls(a)) a^=b, op.push_back(3);
                op.push_back(2), b>>=1;
            }
        }
        if(ls(a)<ls(b)) a^=b, op.push_back(3);
        while(ls(c)>ls(a)){
            if(((c>>(ls(b)+ls(c)-ls(a)-1))&1)!=((a>>(ls(b)-1))&1))
                op.push_back(3), a^=b;
            op.push_back(1), a<<=1;
        }
        while(ls(b)){
            if(((c>>(ls(b)-1))&1)!=((a>>(ls(b)-1))&1))
                op.push_back(3), a^=b;
            op.push_back(2), b>>=1;
        }
        if(b!=c) b^=a,  op.push_back(4);
        cout<<op.size()<<"\n";
        for(auto i:op) cout<<i<<" ";
        cout<<"\n";
    }
    return 0;
}