欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforces 959E Mahmoud and Ehab and the xor-MST(找规律)

程序员文章站 2022-03-25 20:25:37
...

链接

E. Mahmoud and Ehab and the xor-MST
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight (where 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 ≤ n ≤ 1012), 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
Copy

4

Output
Copy

4
解析:每个二进制位会贡献当前总数/2这么多的贡献 然后也相当于合并了这么些连通块 然后用总数减去合并的这些连通块再重复以上步骤

codeforces 959E Mahmoud and Ehab and the xor-MST(找规律)

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep1(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
const int N=1e5+100;
ll arr[N];
int main()
{
    ll n,ans=0,base=1;
    cin>>n;
    while(n>1)
    {
        ans+=base*(n>>1);
        base<<=1;
        n-=n>>1;
    }
    cout<<ans<<endl;
    return 0;
}