さてD。点数の割には意外と簡単？
http://codeforces.com/contest/276/problem/D
問題
２つの整数値L,Rが与えられる。
LとRの間の数値A,Bを選択したとき、A xor Bの最大値を答える。
解法
LとRの最上位ビットの位置が同じ場合、A,Bは常にそのビットを持つので、A ^ Bにもそのビットは立たない。
よってLとR両方そのビットを落とす。
上記処理を加えると、(L==Rの時)LとRが両方0になるか、もしくはLとRの最上位ビットの位置が異なるようになる。
前者はA=B=0しか取れないので最大値は0。
後者は、L=0XXXXX、R=1YYYYYのようなビット構成の場合、A=011111、B=100000を取れば最大値111111が取れる。
ll L,R; void solve() { int f,r,i,j,k,l,x,y; ll re = 0; cin >> L >> R; while(L>0 && R>0) { ll lt=1; ll rt=1; while(lt*2<=L) lt<<=1; while(rt*2<=R) rt<<=1; if(lt!=rt) break; L ^= lt; R ^= rt; } if(R==0) _P("0\n"); else { ll rt=1; while(rt*2<=R) rt<<=1; cout << (rt*2-1) << endl; } return; }
まとめ
ビット処理がちょっとまどろっこしくなってしまった。
もっときれいに書けないかな。
以前のSRMでもxorしてく問題があったので、おかげで割と簡単に気づけた。
TopCoder SRM 564 Div1 Hard DefectiveAddition - kmjp's blog
