Codeforces #473 Div2 E. Mahmoud and Ehab and the xor-MST

どっかで出てそう。
http://codeforces.com/contest/959/problem/E

問題

0～(N-1)のラベルが降られたN個の頂点がある。
これらに辺を追加して連結にしたい。

ラベルu,vの頂点の間に辺を張ると、そのコストはu xor vである。
連結にする最小コストを求めよ。

解法

コスト1の辺を使うと0-1, 2-3, 4-5,....を結ぶことができる。
コスト2の辺を使うと0-2,4-6,8-10,...と結べるので、結局[0,4), [4,8), ...を連結にできる。

このように結局1～2^kの辺を小さい順に使うと[0,2^(k+1))の半開区間を連結にできる。
あとはそれぞれ2^kの辺が何本いるかを数えるだけ。

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	ll a=1;
	while(N>1) {
		ret+=N/2*a;
		N=(N+1)>>1;
		a<<=1;
	}
	cout<<ret<<endl;
	
}

まとめ

DとE逆でもよさそう。