Codeforces Round #628 (Div. 2) 一道比较中等的 二进制构造 题。
题目链接:Codeforces 1325D。
系列题解:
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd;
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy;
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs;
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist;
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem;
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。
题目
原题
题意简述
给出 $u,v$ 要求构造一个正整数数列 $a_i$,满足:
- $\sum_\oplus a_i=u$
- $\sum a_i=v$
即数列的异或和为 $u$,和为 $v$。
同时,数列的长度要尽量小,无解输出 $-1$。
数据范围
$$0\leq u,v\leq 10^{18}$$
时空限制
见原题 pdf
文件。
题解
思路
首先可以发现,如果数列的异或和为 $u$,那么数列的和将 $\geq u$。
所以如果 $u>v$,则无解。
另外,如果 $u=v$,那么有两种情况:
- $u=0$,直接输出 $0$;
- $u\ne 0$,那么输出 $1$ 和 $u$。
下面着重考虑 $u$ 小于 $v$ 的情况。
首先发现,如果 $u$ 是奇数,那么对数列和的贡献中必然存在奇数个 $1$,所以 $v$ 也得是奇数。
进一步推导,可以得出 $u,v$ 的奇偶性相同是有解的充分必要条件。
下面构造解法。
构造
思考得到了一种巧妙的方法。
设 $c=\frac{v-u}{2}$,那么数列 $a$ 可以为 $c,c,u$,满足题意。
但我们考虑有没有 $n=2$ 的构造方法,答案当然是有的。
如果 $c\operatorname{and}u=0$,即 $c,u$ 在二进制意义下没有重叠,那么将它们相加,并不会进位,也不会干扰异或和的结果,而和不变。
所以当 $c\operatorname{and}u=0$ 时有更优的解法为 $c,c+u$。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
reg bool f=false;
reg char ch=getchar();
reg ll res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
ll u,v;
int main(void){
u=read(),v=read();
if(u>v)
puts("-1");
else if(u==v){
if(v==0)
puts("0");
else
printf("1\n%lld\n",v);
}
else
if((u&1)!=(v&1))
puts("-1");
else{
reg ll x=(v-u)>>1;
if((x&u)==0)
printf("2\n%lld %lld\n",x,x+u);
else
printf("3\n%lld %lld %lld\n",x,x,u);
}
return 0;
}
近期评论