或与异或时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给出两个数a , b a,ba,b可以对其进行无限次操作每次操作可以选择a aa和b bb其中一个数作为操作对象然后将操作对象的值变成以下三种之一另一个不变1)a ∣ b a∣ba∣b。(按位或运算符“ ∣ ” “|”“∣”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1 11时结果位就为1 11。)2)a b a\bab。(按位与运算符“ ” “\”“”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位都为1 11时结果位才为1 11。)a ⊕ b a⊕ba⊕b。(按位异或运算符“ ˆ ” “ \^\ ”“ˆ”是双目运算符。其功能是参与运算的两数各对应的二进位相异或当两对应的二进位相异时结果为1 11。)对于每组给出的a aa和b bb给出一个t a r g e t targettarget判断是否可以通过操作使得a aa和b bb其中之一变成t a r g e t targettarget。输入描述第一行包含一个整数T ( 1 ≤ T ≤ 10 4 ) T (1≤T≤10^4)T(1≤T≤104)表示T TT组询问。接下来T TT行每行包含三个整数a b t a r g e t ( 0 ≤ a , b , t a r g e t ≤ 10 17 ) a \ b \ target (0≤a,b,target≤10^{17})abtarget(0≤a,b,target≤1017)。输出描述输出包含T TT行对于每个询问如果a aa和b bb能通过操作得到t a r g e t targettarget 输出YES否则输出NO。示例1输入3 1 2 3 3 2 4 3 5 3输出YES NO YES说明1 ⊕ 2 3 1⊕231⊕23输出Y E S YESYES。对于a 3 , b 2 a3,b2a3,b2不存在任意操作组合可以使得其中之一变成4 44输出N O NONO。无需操作初始时a t a r g e t atargetatarget输出Y E S YESYES。解题思路本题是位运算性质推导题核心是利用位运算的逐位独立性将二进制位分类并分析绑定关系最终将可达性判定转化为集合覆盖校验实现每组查询O(1)的高效求解。1. 位分类与绑定性质按位与、或、异或运算均不产生进位每一位的运算结果仅由两个数的对应位决定。我们将所有二进制位按a、b的取值分为三类双1位x a ba和b对应位均为1仅b为1位y (~a) ba对应位为0b对应位为1仅a为1位z a (~b)a对应位为1b对应位为0由于同一类的所有位在a、b中的取值完全一致每次位运算对同类别位的修改是同步的要么全部变为1要么全部变为0。因此每一类位是不可拆分的整体只能整体保留或整体去除无法单独选中某一类中的部分位。2. 可达性判定结论通过任意次操作能得到的数恰好是上述三类位的任意子集的并集每一类要么全选要么全不选。因此target可达的充要条件是target的所有1位可以被若干个完整的类别覆盖即对每一类target要么包含该类的全部位要么不包含该类的任何位。同时a、b均为0的位永远无法生成1若target在这类位上为1则直接不可达该逻辑已被上述校验条件自然覆盖。3. 校验方法依次校验三类位若某类的所有位在target中均为1说明该类被完整选中将该类的所有位从target中移除。若某类部分位在target中为1、部分为0说明无法拆分该类target不可达。最终若target被完全清空所有1位都被完整类覆盖则可达否则不可达。算法每组查询时间复杂度为O(1)可轻松应对1万组测试数据。总结核心逻辑将二进制位按初始取值分为三类利用位运算的同步性得出每类不可拆分的结论通过校验target是否为若干完整类的并集来判定可达性。关键操作三类位掩码计算、逐类完整覆盖校验、剩余位清零判定。效率保障单组查询仅需常数次位运算万级数据毫秒级完成。代码简要说明位分类计算通过位运算计算三类位的掩码x、y、z分别对应双1位、仅b为1位、仅a为1位。逐类校验移除依次检查每一类若该类的所有位都在target中x (~c) 0则将该类位从target中清除c ~x。结果判定最终若c为0说明target可由若干完整类组合得到输出YES否则输出NO。输入优化关闭流同步加速输入输出适配万级测试用例的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--){ll a,b,c;cinabc;ll x,y,z;xab;y(~a)b;za(~b);if(!(x(~c)))c~x;if(!(y(~c)))c~y;if(!(z(~c)))c~z;if(c)coutNOendl;elsecoutYESendl;}return0;}
