Codeforces 1325 D. Ehab the Xorcist (思维/构造) /详解

Florence ·

更新时间:2024-09-20

· 556 次阅读

D. Ehab the Xorcist
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Given 2 integers u and v, find the shortest array such that bitwise-xor of its elements is u, and the sum of its elements is v.

Input
The only line contains 2 integers u and v (0≤u,v≤1018).

Output
If there’s no array that satisfies the condition, print “-1”. Otherwise:

The first line should contain one integer, n, representing the length of the desired array. The next line should contain n positive integers, the array itself. If there are multiple possible answers, print any.

Examples
inputCopy
2 4
outputCopy
2
3 1
inputCopy
1 3
outputCopy
3
1 1 1
inputCopy
8 5
outputCopy
-1
inputCopy
0 0
outputCopy
0

题意：
给出u,v，让你给出一个长度最短的数组使得各元素的异或和等于u，和等于v。

思路:

很明显，分类讨论：如果u>v这时候u的高位为1而小于v的任何数在这一位都不是1，因此无解；如果u==v && v ==0，那么答案为一个空数组；如果u==v && v !=0 ，那么答案为本身uv选任一，即1 u 。剩下的情况就需要思考一下，首先特殊情况上面都考虑了，接下来就是我们构造特殊数组，很明显两个相同数的异或和等于0，那么我们就肯定可以构造出u^0=u，这个0由两个（v-u)/2组成，就同时满足了u+(v-u)=v的条件。注意这个时候可以发现如果（v-u) 是一个奇数，那么答案也是无解的；因为题目求的是最短的数组，那么什么时候存在长度为2的数组呢？就是我们上面所说的u^0=u，扩展开来就是 u xor x xor x = u, x=(v-u)/2 ；我们可以尝试把u和一个x合并，那么就变成了（v-u)/2 和（v+u)/2 ，判断是否符合条件，如果不符合条件就输出长度为3的情况就ok了。简单来说，如果有解肯定有一组答案为u+x+x 其中x=(v-u)/2 ，那么如果有两个数的答案我们设为a ，b 则 a xor b=(u xor x) xor x , a+b=(u+x)+x 那么判断是否存在a即判断(u^x)是否等于u+x 。如果有什么讲的不清楚的欢迎留言私信交流~

代码1:

#include
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define ins insert
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#pragma GCC optimize(2)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch>= 1;}return ans%p;}ll Inv(ll x,ll p){return qp(x,p-2,p);}
ll Cal(ll n,ll m,ll p){if (m>n) return 0;ll ans = 1;for(int i = 1; i v || ( (v-u)&1 )) {
        put3();
        return 0;
    }
    else if(u==v){
        if(!u) cout<<0;
        else cout<<1<<" "<<u;
        return 0;
    }
    ll x=(v-u)/2,y=(v+u)/2;
    if(((x^y)==u) && x+y==v) cout<<2<<endl<<x<<" "<<y<<endl;
    else{
        cout<<3<<endl;
        cout<<u<<" "<<x<<" "<<x<<endl;
    }
    return 0;
}

作者：别对自己失望

CodeForces

1024 个赞