[CF959E] Mahmoud and Ehab and the xor-MST – 贪心,最小生成树

\(n\) 个点的完全图标号 \((0-n-1)\)，\(i\) 和 \(j\) 连边权值为 \(i\ \textrm{XOR}\ j\)，求 MST 的值

Solution

设 \(f[n]\) 表示点数为 \(n+1\) 时的答案，那么贪心地考虑，显然 \(f[0]=0, f[n]=f[n-1]+lowbit(n)\)

根据观察易得 \(f[n]=2f[n-1]+2^n-2^{n-1}\)，同时由于 \(f[]\) 就是个 \(lowbit\) 的前缀和，满足可加性，所以直接对 \(n\) 二进制分解并统计答案即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;
int f[N],n,ans;

signed main() {
    cin>>n;
    --n;
    f[0]=1; f[1]=3; f[2]=8;
    for(int i=3;i<=40;i++)
        f[i]=f[i-1]*2-(1ll<<(i-1))+(1ll<<i);
    for(int i=0;i<=40;i++) if(n&(1ll<<i)) ans+=f[i];
    cout<<ans;
}