现代汽车前瞻杯-2025牛客暑期多校训练营3——Bitwise Puzzle 位运算谜题（MSB的作用）

思路讲解

思路就是用异或操作可以对齐位数，然后使用最高位，不断左移异或。

总的来说我就是看题解的。

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78402363

源代码

// https://ac.nowcoder.com/acm/contest/108300/B
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*
a*=2 b/=2 a=a^b b=a^b

*/
inline void __(){
	ll A,B,C;
	cin>>A>>B>>C;
	if(A==0 && B==0 && C!=0){
		cout<<-1<<"\n";
		return;
	}
	if(A==B && B==C){
		cout<<"0\n\n";
		return;
	}
	vll ans;
	// 如果A B 位数不同，通过异或使得两者位数相同
	if(__lg(A)!=__lg(B)){
		if(__lg(A)>__lg(B)){
			B^=A;
			ans.pb(4);
		}else{
			A^=B;
			ans.pb(3);
		}
	}
	if(__lg(A)<__lg(C)){
		ll diff=__lg(C)-__lg(A);
		FOR(i,1,64){
			if(__lg(A)== __lg(C)) break;
			bitset<40> bia(A),bic(C);
			if(bia[__lg(B)]!=bic[__lg(B)+diff]){
				A^=B;
				ans.pb(3);
			}
			ans.pb(1);
			A<<=1;
			--diff;
		}
		ll siz=__lg(B);
		ROF(i,siz,0){
			bitset<40> bia(A),bic(C);
			if(bia[i]==bic[i]){
				B>>=1;
				ans.pb(2);
			}else{
				A^=B;
				ans.pb(3);
				B>>=1;
				ans.pb(2);
			}
		}
		B>>=1;
		ans.pb(2);
		B^=A;
		ans.pb(4);
	}else{
		// 先对齐位数
		// if(__lg(A)!=__lg(B)){
			// B^=A;
			// ans.pb(4);
		// }
		ll siz=__lg(A);
		ROF(i,siz,0){	// 最多操作64次
			bitset<40> bia(A),bic(C);
			if(bia[i]==bic[i]){
				B>>=1;
				ans.pb(2);
			}else{		
				A^=B;
				ans.pb(3);
				B>>=1;
				ans.pb(2);
			}
		}
		// B>>=1;
		// ans.pb(2);
		B^=A;
		ans.pb(4);
	}
	cout<<SZ(ans)<<"\n";
	for(auto &e:ans){
		cout<<e<<" ";
	}
	cout<<"\n";
// #ifdef LOCAL
    // debug(A);debug(B);debug(C);
// #endif
}
/*
WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78400950
1
1 1 2147483647

ans: 在保证A，B，C正确的情况下，使得操作数量小于64
AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78402363
*/

心路历程（WA，TLE，MLE……）

这边多进行了一次操作导致WA了。

}else{
	// 先对齐位数
	// if(__lg(A)!=__lg(B)){
		// B^=A;
		// ans.pb(4);
	// }
	ll siz=__lg(A);
	ROF(i,siz,0){	// 最多操作64次
		bitset<40> bia(A),bic(C);
		if(bia[i]==bic[i]){
			B>>=1;
			ans.pb(2);
		}else{		
			A^=B;
			ans.pb(3);
			B>>=1;
			ans.pb(2);
		}
	}
	// B>>=1;
	// ans.pb(2);
	B^=A;
	ans.pb(4);
}