题解 CF959E 【Mahmoud and Ehab and the xor-MST】
VenusM1nT
2020-11-24 20:21:51
使用 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;
}
```