4201 01数（枚举）

4201 01数（枚举）

1. 问题描述：

如果一个正整数，其各个数位上的数字均满足要么是 0，要么是 1，则称该数字为 01 数。例如，1 和 10 都是 01 数。给定一个整数 n。请你计算，1~n 中有多少个 01 数。

输入格式

一行，一个整数 n。

输出格式

一个整数，表示 01 数的数量。

数据范围

前六个测试点满足 1 ≤ n ≤ 100。
所有测试点满足 1 ≤ n ≤ 10 ^ 9。

输入样例：

10

输出样例：

2
来源：https://www.acwing.com/problem/content/4204/

2. 思路分析：

一开始的时候感觉应该可以使用数位dp来解决，但是仔细一分析发现答案其实很少，总共有10位数字，每一位可以是0也可以是1所以最大答案数目为2 ^ 9 + 1 - 1 = 512种（除了最高位之外每一位可以是0也可以是1，并且最高位最大只能够为1属于一种情况，从1开始所以需要减去0），我们可以枚举所有0和1对应的二进制状态，如果是1那么将其转换为10进制的1，然后判断是否在n之内即可，所以有的时候多分析一下就可以简化一下代码。

3. 代码如下：

class Solution:
    def process(self):
        n = int(input())
        res = 0
        for i in range(1, 1 << 10):
            x = 0
            for j in range(10):
                x = x * 10 + (i >> j & 1)
            if x <= n:
                res += 1
        return res


if __name__ == "__main__":
    print(Solution().process())