二进制分类

题目描述

给定正整数范围 $1\sim 1000$ 。将每个数写成无前导零的二进制，若 $1$ 的个数多于 $0$ 的个数则为 A 类数，否则为 B 类数。无输入，输出两个整数：A 类数个数、B 类数个数。

思路

枚举 $x\in[1,1000]$ ，分别统计其二进制总位数 $L$ 与 $1$ 的个数 $c_1$ ，则 $0$ 的个数为 $L-c_1$ 。按 $c_1>L-c_1$ 分类计数即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47


def is_type_a(x: int) -> bool:
    """判断正整数 x 化为二进制后 1 的个数是否严格多于 0 的个数。"""
    c1 = x.bit_count()
    c0 = x.bit_length() - c1
    return c1 > c0


def solve() -> None:
    # 统计 1~1000 中 A 类数数量，其余为 B 类数
    total = 1000
    cnt_a = sum(1 for i in range(1, total + 1) if is_type_a(i))
    print(f"{cnt_a} {total - cnt_a}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:15
 * update_at: 2026-10-05 23:15
 */
#include <cstdio>

typedef long long ll;

int cntA, cntB; // A 类数、B 类数的个数

int main() {
    for (int x = 1; x <= 1000; ++x) {
        int len = 0, t = x;
        while (t) { // 统计 x 的二进制位数
            ++len;
            t >>= 1;
        }
        int ones = 0;
        t = x;
        while (t) { // 统计二进制中 1 的个数
            if (t & 1) ++ones;
            t >>= 1;
        }
        int zeros = len - ones; // 0 的个数 = 总位数 - 1 的个数
        if (ones > zeros) ++cntA;
        else ++cntB;
    }
    printf("%d %d\n", cntA, cntB);
    return 0;
}

目录

题目描述

思路

参考代码