hdu 5661異或

2つの区間、(a,b)と(c,d)、データ範囲はlong longであり、この2つの区間の中でそれぞれ1つの数字を選択して異を求めるか、最大の異または値を求める.
公式の問題解:
高位から低位への貪欲さを考えると、一人一人に対して、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がこの1位で0,1でも取れるわけではない場合、答えの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
",ans) ;
	}
	return 0;
}