练83.3 特殊的集合

解题思路

将1～n按奇数基底划成互不相交的链q,2q,4q…。链上不能同时取相邻元素，最优交替选。可等价从(n/2,n]全部选入，排除它们的一半，再递归到1～floor(n/4)。所以答案累加n-floor(n/2)，然后n/=4。

正确性说明

每条倍增链是一条路径，最大独立集可由链顶向下隔一个取一个。全体链顶正是(n/2,n]，隔过下一层后剩余链与1～floor(n/4)同构，故递推准确。

易错点

n到十亿，不能逐个开数组或枚举。

复杂度

时间O(log n)，空间O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    long long ans = 0;
    while (n > 0) {
        ans += n - n / 2;
        n /= 4;
    }
    cout << ans << "\n";
    return 0;
}