小苯的数组构造【牛客tracker 每日一题】
小苯的数组构造
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
你对位运算很感兴趣，你希望小苯帮你构造一个长度为n nn的全正数组a aa，同时满足：
a 1 ∣ a 2 ∣ . . . ∣ a n = x a_1 ∣ a_2 ∣ ... ∣ a_n=xa1∣a2∣...∣an=x。 （其中∣ ∣∣表示按位或运算。）
a 1 ⊕ a 2 ⊕ . . . ⊕ a n = y a_1⊕a_2⊕...⊕a_n=ya1⊕a2⊕...⊕an=y。（其中⊕ ⊕⊕表示按位异或运算。）
1 ≤ a i < 2 31 , ( 1 ≤ i ≤ n ) 1≤a_i<2^{31},(1≤i≤n)1≤ai<231,(1≤i≤n)。
小苯给了你x xx和y yy，希望你帮他解决这个问题。
如果您需要更多位运算相关的知识，可以参考OI-Wiki的相关章节。
输入描述：
每个测试文件内都包含多组测试数据。
第一行一个正整数T ( 1 ≤ T ≤ 1000 ) T (1≤T≤1000)T(1≤T≤1000)，表示测试数据的组数。
接下来对于每组测试数据，输入包含一行三个整数n , x , y ( 1 ≤ n ≤ 2 × 10 5 , 1 ≤ x , y < 2 31 ) n,x,y (1≤n≤2×10^5,1≤x,y<2^{31})n,x,y(1≤n≤2×105,1≤x,y<231)，意义如题所述。
（保证所有测试数据中，n nn的总和不超过3 × 10 5 3×10^53×105。）
输出描述：
对于每组测试数据，如果有解，先输出一行一个“ Y E S ” “YES”“YES”，再换行输出一行n nn个正整数，表示构造的数组a aa。（有多解输出任意即可。）
如果无解输出一行一个“ N O ” “NO”“NO”即可。（都不含双引号）
示例1
输入：
2 2 3 1 3 2 3输出：
YES 2 3 NO说明：
对于第一组测试数据，数组{ 2 , 3 } \{2,3\}{2,3}是符合条件的。
解题思路
本题核心是位运算性质推导 + 贪心构造法，快速判定解的存在性并构造合法数组。根据位运算规则，异或结果 y 的二进制位必须全部包含在或结果 x 中（y & ~x != 0直接无解）；当n=1时，必须满足x=y才有解。利用或运算特性：所有元素均为 x 的子集，总或恒为 x。构造时用 x 填充大部分元素，利用偶数个相同数异或为 0的性质，微调前两个元素使总异或等于 y，保证所有元素为正。分情况处理奇偶长度、x=y 等边界，线性构造数组，时间复杂度O ( n ) O(n)O(n)，完美适配大数据范围。
总结
核心逻辑：通过位运算规则快速判无解，用 x 填充数组+微调构造满足异或要求的合法解。
关键操作：二进制位合法性校验、分场景构造数组、保证所有元素为正整数。
效率保障：线性时间构造，无冗余计算，高效处理多组测试用例与大数据约束。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidSolve(){ll n,x,y;cin>>n>>x>>y;if(n==1){if(x==y){cout<<"YES\n"<<x<<'\n';return;}cout<<"NO\n";return;}if(y&~x){cout<<"NO\n";return;}if(!(n&1)&&x==y){ll lb=x&-x;if(lb==x){cout<<"NO\n";return;}cout<<"YES\n"<<lb<<' '<<(x^lb);for(ll i=2;i<n;i++)cout<<' '<<x;cout<<'\n';return;}cout<<"YES\n"<<(n&1?y:x^y);for(ll i=1;i<n;i++)cout<<' '<<x;cout<<'\n';}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cin>>T;while(T--)Solve();return0;}