题解 CF959E 【Mahmoud and Ehab and the xor-MST】

使用 Kruskal 暴力打表，作差发现为 ``` 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 ... ``` 观察到第 $i$ 项 $a_i$ 的值为 $$\max_{2^x|\ i}\{x\}$$ 后面就不知道怎么做了。 不过观察原始数据可以简单地找出递推式。 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 3 4 8 9 11 12 20 21 23 24 28 29 31 32 48 49 51 52 56 ... ``` 分奇偶观察，发现有如下式子 $$a_{i\times 2}=a_i\times 2+i$$ $$a_{i\times 2+1}=a_i\times 2+i+1$$ 随便递归一下就出来了。 ```cpp #include<bits/stdc++.h> #define reg register #define inl inline #define int long long using namespace std; int n; map <int,int> m; int Solve(reg int x) { if(x==1) return 1; if(x==2) return 3; if(m[x]) return m[x]; reg int res=(!(x&1)?(2*Solve(x>>1)+(x>>1)):(2*Solve(x>>1)+(x>>1)+1)); return m[x]=res; } signed main() { scanf("%lld",&n); n--; printf("%lld\n",Solve(n)); return 0; } ```