「CF959E」Mahmoud and Ehab and the xor-MST【OEIS】
E. Mahmoud and Ehab and the xor-MST
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 vertices numbered from 0 to . For all , vertex and vertex 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 , the number of vertices in the graph.
Output
The only line contains an integer , 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 .
-
题意:
给一个节点数为n的完全图,节点标号,边权定义为,为节点编号,求最小生成树 -
解法
-
上次西安邀请赛就让我学会了一个东西:不会的东西,难直接推的东西直接打表!先打再说
-
这题打表代码也贴一下吧
-
#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); } }
-
然后找规律,找不出来直接吧
-
-
附代码:
#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));
}