hdu 5661 异或

﹏ヽ暗。殇╰゛Y 2022-08-21 08:52 149阅读 0赞

两个区间，(a,b)和(c,d)，数据范围为long long ，在这俩个区间里面各选取一个数字求异或，求最大的异或值。

官方题解：

考虑从高位到低位贪心，对于每一位，如果x，y只有唯一的取法，那么只能这么取；否则贪心地必须使答案的这一位等于1。如果x，y都是0，1都能取，则设这是从右向左数第len位，因为x，y能取的值一定都是连续的一段，因此x，y的后len位都能取0111...1（len-1个1）和1000...0（len-1个0）（否则做不到从右向左数第len位都能取0,1）。也就是说，后len位的贡献一定能达到可能的上界111...1（len个1）。此时不必继续考虑后面的位。

如果x，y在这一位并不是0,1都能取，那么由于要使得答案的这一位等于1，也只有唯一的取法。

至此，这一位考虑完毕，然后根据选取的方案，修正一下x和y的范围，然后对后一位做即可。

#include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <queue>
    
    using namespace std ; 
    
    //若x第i位只能取1，则y第i位贪心取0，同时y的后i-1位上限变为11...11
    //若x第i位只能取0，则y第i位贪心取1，同时y的后i-1位下限变为00...00
    //这是肯定的，因为x，y的取值是连续的。
    
    int main() 
    {
    	int t;
    	long long a , b , c , d  ;
    	long long aa , bb , cc , dd ; 
    	scanf("%d",&t);
    	while(t--) 
    	{
    		scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&d);
    		long long ans = 0 ;
    		for(long long cur = 1LL << 61 ; cur > 0 ; cur >>= 1) 
    		{
    			aa=a&cur; bb=b&cur;
    			cc=c&cur; dd=d&cur;
    			if(aa==bb) 
    			{            //如果x这一位只能取0或1
    				if(cc==dd) 
    				{        //如果y这一位只能取0或1
    					ans|=aa^cc;
    				}
    				else 
    				{         //如果y这一位0和1都能取
    					ans|=cur;//ans这一位贪心取1
    					if(aa==0) 
    					{      //如果x这一位只能取0，则y必定取1
    						c&=cur;//y该位以后的位的下限是00...00
    					}
    					else 
    					{      //如果x这一位只能取1，则y必定取0
    						d|=cur-1;//y该位以后的位的上限是11...11
    					}
    				}
    			}
    			else 
    			{             //如果x这一位0和1都能取
    				ans|=cur; //ans这一位贪心取1
    				if(cc==dd) 
    				{         //如果y这一位只能取0或1
    					if(cc==0) 
    					{     //如果y这一位只能取0，则x必定取1
    						a&=cur;
    					}
    					else 
    					{     //如果y这一位只能取1，则x必定取0
    						b|=cur-1;
    					}
    				}
    				else 
    				{        //如果y这一位0和1都能取，任取一个即可，且ans后面所有的位都能取1
    					ans|=cur-1;
    					break;
    				}
    			}
    		}
    		printf("%I64d\n",ans) ;
    	}
    	return 0;
    }