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的真题
三奇智元机器人科技有限公司公司福利 48人发布