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

「CF959E」Mahmoud and Ehab and the xor-MST【OEIS】

程序员文章站 2023-12-26 22:55:57
...

E. Mahmoud and Ehab and the xor-MST

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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 nn vertices numbered from 0 to n1n - 1. For all 0u<v<n0 ≤ u < v < n, vertex uu and vertex vv 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(2n1012)n (2 ≤ n ≤ 10^{12}), the number of vertices in the graph.

Output

The only line contains an integer xx, 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=41+2+1=4.

  • 题意:

    给一个节点数为n的完全图,节点标号[0,n1][0,n-1],边权定义为u xor vu\ xor\ vu,vu,v为节点编号,求最小生成树
  • 解法

    • 上次西安邀请赛就让我学会了一个东西:不会的东西,难直接推的东西直接打表!先打再说233233

    • 这题打表代码也贴一下吧

    •   #include<bits/stdc++.h>
        using namespace std;
        const int maxn=1e5+10;
        
        struct node{
        	int a,b,c;
        	node(int d=0,int e=0,int f=0){
        		a=d;b=e;c=f;
        	}
        	friend bool operator<(const node &a,const node &b){
        		return a.c<b.c;
        	}
        	void print(){
        		printf("%d %d %d\n",a,b,c);
        	}
        }a[maxn];
        
        int n;
        
        struct dsu{
        	int fa[maxn],rank[maxn];
        	void init(int k){
        		for(int i=1;i<=k;i++) fa[i]=i,rank[i]=0;
        	}
        	int fin(int k){
        		return fa[k]==k?k:(fa[k]=fin(fa[k]));
        	}
        	
        	bool unite(int a,int b){
        		int x=fin(a),y=fin(b);
        		if(x==y) return false;
        		if(rank[x]<rank[y]) 
        		fa[x]=y;
        		else{
        			fa[y]=x;
        			if(rank[x]==rank[y]) rank[x]++;
        		}
        		return true;
        	}
        	
        	bool same(int a,int b){
        		return fin(a)==fin(b);
        	}
        }tree;
        
        
        int main()
        {
        	while(~scanf("%d",&n)){
        		int tot=0;tree.init(n);
        		for(int i=0;i<n;i++){
        			for(int j=i+1;j<n;j++){
        				a[++tot]=node(i,j,i^j);
        			}
        		}
        		sort(a+1,a+tot+1);
        		//for(int i=1;i<=tot;i++) a[i].print();
        		int ans=0,cnt=0;
        		for(int i=1;i<=tot&&cnt<n-1;i++){
        			if(tree.unite(a[i].a+1,a[i].b+1)){
        				cnt++;
        				ans+=a[i].c;
        			}
        		}
        		printf("%d\n",ans);
        	}
        }
      
    • 然后找规律,找不出来直接OEISOEIS233233

      • 「CF959E」Mahmoud and Ehab and the xor-MST【OEIS】
  • 附代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;

ll dfs(ll cur)
{
	if(cur==1) return 1;
	if(cur%2LL) return 2*dfs(cur/2)+cur/2+1;
	else return 2*dfs(cur/2)+cur/2;
}

int main()
{
	scanf("%lld",&n);
	printf("%lld\n",dfs(n-1));
}

上一篇:

下一篇: