Znzryb's Blog
0%

START200——Minimum Set

Posted on Edited on

思路讲解

image

不难发现，可以把原来的问题转化为图论问题，就是要联通嘛，然后搞一个mst。

不难发现，num⊕(num−lowbit(num))num\oplus (num-lowbit(num)) 是最小的，因为这个数是比你小的数里面，和你重叠程度最大的。

通过打表等手段，我们可以得到如下程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll ans=0;
ll wei=__lg(N);
ll cnt=0;
FOR(i,2,wei){
    ans+=1ll<<i;
    ++cnt;
}
for(ll i=2;i<=N;i<<=1){
    ll num=min(N,2*i-1)-i+1;
    for(ll j=2;(1ll<<j)<num;++j){
        ll val=(1ll<<(j));
        ans+=(num-1)/val*(val/2);
    }
    // ans+=num/2*2;
}
ans+=N/2;
ans+=(N/2-cnt)*2;
if(N%2==0 && N!=(1ll<<__lg(N))){
    ans--;
}
cout<<ans<<"\n";

唯一就是这一部分不是很优雅。我不太喜欢。至少我们要搞搞清楚为什么要-1吧？

其实要回答这个问题也简单，就是一开始我们写程序的时候假设都是奇数，使用的都是奇数的方法进行计数的，但是不是2的幂次的偶数比较特殊，不能和奇数直接互相转化，需要-1（比如说6，7-6代价是1，但是没有7的时候，就没有这个代价，所以要-1），而2的幂次因为和1相连代价+1（原来1-4，代价为5，但是改为5-1，代价为4，4-5，代价为1，正好抵消）。

AC代码

https://www.codechef.com/viewsolution/1183885336

心路历程（WA，TLE，MLE……）