# 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?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

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

/* */