CF959E Solution

题目链接

题解

为避免构造时出现环，令父结点编号小于子节点。可以发现，对于整数\(x\)，满足\(y<x\)且\(y^\wedge x\)最小的\(y\)为\(x-lowbit(x)\)，此时边\((y,x)\)的权值为\(lowbit(x)\)。如此构造，\(ans=\sum\limits_{i=1}^{n-1}lowbit(i)\)（\(lowbit(1)=1\)而\(lowbit(n)\ge 1\)，因此\(sum\)区间为\([1,n-1]\)而非\([2,n]\)）。如果暴力求和时间复杂度为\(O(n)\)，而我们需要使时间复杂度在\(logn\)以内，仍需进一步推导。

设整数\(x,y\)满足\(?x=lowbit(y),1?≤?y?≤?n?\)。因为\(lowbit\)一定为\(2\)的整数次幂，所以当且仅当\(x\)为\(2\)的整数次幂时\(y\)的个数\(?>?0\)。可以发现，当\(y=y+2x\)时，\(lowbit(y)\)是不变的（因为进行运算的为\(lowbit\)左侧的数位）。因此对于每个\(x\)，\(y\)的值为一个等差数列：首项为\(x\)，公差为\(2x\)。例如\(x?=?4\)时\(y\)组成的数列为\(\{4,12,20,?28,...\}\)。所以每一个二进制位对答案的贡献便是对应序列\(\le n\)的元素个数\(\times i\)，也就是\((\lfloor \frac{n-i}{2i}\rfloor+1)\cdot i\)（首项为\(i\)所以元素个数为\(\frac{n-i}{2i}\)向下取整\(+\)首项）。这样我们只需枚举\(\le n\)的\(2\)的整数次幂，时间复杂度\(O(logn)\)。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n,ans=0;
    scanf("%lld",&n); n--;
    for(int i=1;i<=n;i<<=1) ans+=((n-i)/(i*2)+1)*i;
    printf("%lld",ans);
}

CF959E Solution

原文：https://www.cnblogs.com/violetholmes/p/14363972.html