CF959E Mahmoud and Ehab and the xor-MST 题解【二进制】【贪心】【生成树】

这个题真是太有意思了ovo

Description

Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of $$n$$ vertices numbered from $$0$$ to $$n-1$$. For all $$0\le u<v<n$$, vertex $$u$$ and vertex $$v$$ are connected with an undirected edge that has weight $$u\bigoplus v$$ (where $$\bigoplus$$ is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer $$n(2\le n\le 10^{12})$$, the number of vertices in the graph.

Output

The only line contains an integer $$x$$, the weight of the graph’s minimum spanning tree.

Example

input
4
output
4

Note

In the first sample:

The weight of the minimum spanning tree is 1+2+1=4.

题意：

给定一个编号为$$o\sim n-1$$的带权完全无向图。其中连接$$i$$和$$j$$点的边权值为$$i\bigoplus j$$。求这个图的最小生成树。

题解：

贪心。因为要生成树，所以每个点都要连一条边到一个比它编号更小的点（这是随机生成树的算法233333）。那么在$$\tt MST$$上，每个点$$i$$连接的边权就是$$\min_{j\in [0,i)}i\bigoplus j$$。

一个二进制数$$i$$异或一个比它小的二进制数$$j$$所得到的答案最小值是多少呢？应该是它的$$\text{lowbit}$$，因为需要构造出一个值使得$$i$$异或$$j$$$$(j<i)$$后的最高位的1最低，如果要求尽可能低又不等于$$i$$，那么最低就是1了，但是如果$$\text{lowbit}(i)$$不是1，那么$$j>i$$就不符合生成树的要求了，可以依此类推到高位直到$$\text{lowbit}$$。

最高位尽可能低的原理是$$\sum_{i=0}^{k-1}2^i<2^{k}$$，我们要贪心地使最高位的1所在位最低，而因为$$(i-\text{lowbit}(i))\bigoplus i=\text{lowbit}(i)$$，则保证了$$j<i$$情况下所得值最小，为$$\text{lowbit}(i)$$，也就是二进制下恰好只有唯一的1。

所以答案就是$$\sum\limits_{i=0}^{n-1}\text{lowbit}(i)$$。

然后介绍求法…因为所有的奇数的$$\text{lowbit}$$都是1，所以每两个数就会出现一次$$\text{lowbit}=1$$，同理，每四个数就会出现一次$$\text{lowbit}=2$$。我们现在来分析一个二进制数：

对于$$10101_{(2)}$$来说，我们现在想知道有多少个比它小的数$$\text{lowbit}=1$$。那么只要满足较高位（即一次右移）小于$$1010$$，并且第0位为1就可以了；要求$$\text{lowbit}=2$$，就要满足第2位及以上的位（两次右移）小于$$101$$，这时要注意如果右移前最后一位是$$1$$，那么它自己也要被算上，比如要求$$\text{lowbit}=4$$，则第3位及以上小于$$10$$，但是如果恰好等于$$10100_{(2)}$$也是合法的，所以每次右移前要判断当前位是否做出贡献。

Code：

#include<cstdio>
int main()
{
long long n;
scanf("%I64d",&n);
n-=1;
long long ans=0;
long long base=1;
while(n)
{
ans+=base*(n&1);
n>>=1;
ans+=base*n;
base<<=1;
}
printf("%I64d\n",ans);
return 0;
}

Subscribe

/* */