题目链接:https://syzoj.com/problem/490
内存限制：512 MiB 时间限制：1000 ms

题目描述

若将一个正整数转换为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A类数，否则就称其为B类数。

例如

    (1)10=(1)2

   其中1的个数为1,0的个数为0,则称此数为A类数；

    (13)10=(1101)2

   其中1的个数为3,0的个数为1,则称此数为A类数；

    (10)10=(1010)2

   其中1的个数为2,0的个数也为2,称此数为B类数；

    (24)10=(11000)2

   其中1的个数为2,0的个数为3，则称此数为B类数；

编程输出1～n之中(包括1和n),A、B两类数的个数。

输入格式

输入文件一行，为一个正整数n(1≤n≤20,000,000)

输出格式

输出文件一行，为空格隔开的两个整数a和b，其中a表示A类数的个数，b表示B类数的个数；

样例输入

3

样例输出

2 1

数据范围与提示

对于50%的数据，满足n≤1000
对于100%的数据，满足n≤20,000,000

解题思路

用f[i]来记录i中1的个数，因为i&(i-1)可以消去i最右边的1,故i中1的个数正好比i&(i-1)多1个。用w来记录i的位数，因为只有到2的整数幂的时候i的位数才会发生改变，所以判断一下i是否为2的整数幂，是的话位数加1。

#include <stdio.h>
int f[20000005];
int main() {
    int n, w = 0, ans1 = 0, ans2 = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        f[i] = f[i & (i - 1)] + 1;//i&(i-1)可以消去i最右边的1,故i中1的个数正好比i&(i-1)多一个 
        if (!(i & (i - 1)))       //判断是否为2的整数幂 
            w++;                  //位数加1
        if ((f[i] << 1) > w)      //i的1的个数大于位数w的一半
            ans1++;
        else ans2++;
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}