#include<bits/stdc++.h>
using namespace std;
#define int long long
int qpow(int a, int b) {
if (b == 0)return 1;
int half = qpow(a, b / 2);
if (b % 2 == 0) {
return half * half;
}
return half * half * a;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, x, y;
cin >> n >> x >> y;
int biao = 1;
string s = bitset<32>(x).to_string();
string ss = bitset<32>(y).to_string();
for (int i = 0; i < s.size(); i++) {
if (s[i] == '0' && ss[i] == '1') {
biao = 0;
break;
}
}
if (!biao) {
cout << "NO" << '\n';
continue;
}
if (n == 1) {
if (x != y) {
cout << "NO" << '\n';
continue;
}else{
cout<<"YES"<<'\n';
cout<<x<<'\n';
continue;
}
}
int sum = 0;
int zong = 0;
if ((n - 2) % 2 == 0) {
reverse(s.begin(), s.end());
reverse(ss.begin(), ss.end());
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1' && ss[i] == '0') {
sum = sum + qpow(2, i);
}
if (s[i] == '1') {
zong ++;
}
}
if (sum == 0) {
if (zong == 1) {
cout << "NO" << '\n';
} else {
cout<<"YES"<<'\n';
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1' && sum1 == 0) {
sum1 += qpow(2, i);
} else if (s[i] == '1' && sum1 != 0) {
sum2 += qpow(2, i);
}
}
for (int i = 1; i <= n - 2; i++) {
cout << x << ' ';
}
cout << sum1 << ' ' << sum2 << '\n';
}
} else {
cout<<"YES"<<'\n';
for (int i = 1; i <= n - 2; i++) {
cout << x << ' ';
}
cout<<x<<' ';
cout << sum << '\n';
}
} else {
cout << "YES" << '\n';
for (int i = 1; i <= n - 2; i++) {
cout << x << ' '; //按位与的结果
}
cout<<x<<' ';
cout << y << '\n';
}
}
}
关于这个题,前面的大佬们,很多思路都说明白了,我这里总结一下首先:
第一个无解的情况是:是x和y的二进制中y的二进制必须x二进制的子集,也就是说不存在1在y里出现而不在x里出现的情况
然后我们先讨论长度为奇数,考虑这样的构造前n-1项全为x则异或之后的结果为0,又因为0异或任何数都等于对应的数,我们最后一个数就可以是y这样就满足了题意。
再考虑长度为偶数:长度为偶数的时候上述奇数构造并不成立,这时候 我们考虑这样的构造,我们前n-2项还是保持输出x,这样异或之后还是0,但是最后两项中第一项输出x,那么第二项的选择数想让数组异或之后是y的话,要满足这样的条件:即遍历x和y的二进制凡是x的二进制中为1且y也在这位为1,则对应的构造数在该位必须为0,而凡是x的进制中为0但y在这一位为0的,该构造数在这一位必须为1; 其他的x为0则构造数对应位为0即可;
但是这是会有一个这样的条件,如果x和y是相等的,那么则对应构造的数是0不满足题意。
重新考虑构造,对于这样的 比如 1100 这样的一个二进制数,我们可以取1000 和0100,对于 10011100,这样的数我们可以取10000000和00011100观察不难发现,用一个数来表示对应的x最高的一位,而第二个数表示剩下x-减去对应最高位的差值满足题意。
而这时候会有无解情况,即x在二进制中只有一位是1,那么在n>2的情况下无解。

京公网安备 11010502036488号