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的真题

全部评论

相关推荐

12-10 19:11
重庆大学 Java
香梨想要offer:一样啊朋友,我也是被驳回了,真的挺让人无语的,为什么不一开始就挂了算了,内耗我这么多天。如果华为给每个人造成的内耗能汇聚起来,该是多大一股能量
点赞 评论 收藏
分享
球球别再泡了:坏,我单9要了14
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务