Xor Transformation
Xor Transformation
https://ac.nowcoder.com/acm/contest/10662/G
题目:
给定一个X和Y,对于X每次可以选择一个A(0<=A<X),使得X = X xor A,现在要求在5步内将X变为Y,请输出操作数目,以及每步的A
题解:
我一开始被题目给的样例个迷惑了,以为将Y分解开,然后再加一步X就可以了,但发现想复杂了
对于W = (X ^ Y),也就是W,X,Y任意两个xor等于第三
如果W 等于 X,说明Y是0,但因为Y>=1,所以该情况不存在
如果W小于X,那么我们第一步直接选W不就完事了,X ^ W = Y
如果W大于X,那就不能直接选W了,为了得到Y,我们可以先xorY,再xorX,因为第一步得到W,W大于X,所以可以选X,再选X相当于把一开始的X抵消了,只剩下Y
代码:
#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48); return s*w; } int main() { ll x,y; cin>>x>>y; ll w=(x^y); if(w<x) { cout<<1<<endl; cout<<w<<endl; } else { cout<<2<<endl; cout<<y<<" "<<x<<endl; } }
XCPC 文章被收录于专栏
主要记录ICPC的真题