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

作者: wjyyy 分类: 二进制,图论,生成树,解题报告,贪心 发布时间: 2018-10-25 21:48

点击量:37

 

    这个题真是太有意思了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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */