小苯的数组构造【牛客tracker 每日一题】

小苯的数组构造时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述你对位运算很感兴趣你希望小苯帮你构造一个长度为n nn的全正数组a aa同时满足a 1 ∣ a 2 ∣ . . . ∣ a n x a_1 ∣ a_2 ∣ ... ∣ a_nxa1​∣a2​∣...∣an​x。 其中∣ ∣∣表示按位或运算。a 1 ⊕ a 2 ⊕ . . . ⊕ a n y a_1⊕a_2⊕...⊕a_nya1​⊕a2​⊕...⊕an​y。其中⊕ ⊕⊕表示按位异或运算。1 ≤ a i 2 31 , ( 1 ≤ i ≤ n ) 1≤a_i2^{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,y2^{31})n,x,y(1≤n≤2×105,1≤x,y231)意义如题所述。保证所有测试数据中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直接无解当n1时必须满足xy才有解。利用或运算特性所有元素均为 x 的子集总或恒为 x。构造时用 x 填充大部分元素利用偶数个相同数异或为 0的性质微调前两个元素使总异或等于 y保证所有元素为正。分情况处理奇偶长度、xy 等边界线性构造数组时间复杂度O ( n ) O(n)O(n)完美适配大数据范围。总结核心逻辑通过位运算规则快速判无解用 x 填充数组微调构造满足异或要求的合法解。关键操作二进制位合法性校验、分场景构造数组、保证所有元素为正整数。效率保障线性时间构造无冗余计算高效处理多组测试用例与大数据约束。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidSolve(){ll n,x,y;cinnxy;if(n1){if(xy){coutYES\nx\n;return;}coutNO\n;return;}if(y~x){coutNO\n;return;}if(!(n1)xy){ll lbx-x;if(lbx){coutNO\n;return;}coutYES\nlb (x^lb);for(ll i2;in;i)cout x;cout\n;return;}coutYES\n(n1?y:x^y);for(ll i1;in;i)cout x;cout\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--)Solve();return0;}