计算区间 [s, e] 内的 Round Number（RN数）个数

Round Number（RN数）是指二进制表示中 0 的个数大于 1 的个数的正整数。为了计算区间 [s, e] 内的 RN 数个数，我们可以通过以下步骤来解决这个问题：

问题分析

RN 数定义：RN 数是指二进制表示中 0 的个数多于 1 的个数的正整数。例如，二进制为 1010 的数有 3 个 0 和 2 个 1，因此它是 RN 数。

区间计算：我们需要计算在区间 [s, e] 内满足上述条件的 RN 数的个数。为了高效计算，可以通过预处理和组合数学来快速查询区间内的 RN 数数量。

预处理组合数：为了计算 RN 数的个数，我们需要预处理组合数表 C(n, m)，其中 C(n, m) 表示从 n 个物体中选 m 个的组合数。这个预处理可以通过动态规划来完成。

计算函数 f(x)：定义函数 f(x) 表示区间 [0, x) 内的 RN 数的个数。通过 f(e+1) - f(s) 可以得到区间 [s, e] 内的 RN 数的个数。

细节解释

1. 预处理组合数

我们使用一个数组 C 来存储组合数，其中 C[i][j] 表示从 i 个物体中选 j 个的组合数。我们通过以下步骤预处理组合数：

初始化 C[0][0] = 1，因为从 0 个物体中选 0 个的组合数是 1。

对于 i >= 1，C[i][0] = 1 和 C[i][i] = 1，这是因为只能选择 0 个或全部 i 个物体。

对于 i >= 2，C[i][j] = C[i-1][j-1] + C[i-1][j]，这是 Pascal 定理。

2. 计算区间 [0, x) 的 RN 数个数

定义函数 getn(x) 来计算区间 [0, x) 内的 RN 数个数。函数实现如下：

边界处理：如果 x <= 1，返回 0，因为没有满足条件的正整数。

二进制位处理：将 x 转换为二进制表示，存储在数组 bit 中。

长度小于 len 的情况：遍历所有长度小于 len 的二进制数，累加这些数的个数。

长度等于 len 的情况：逐位检查二进制位，如果当前位是 1，则计算在这一位之后可以选择 0 的组合数；如果当前位是 0，则继续处理下一位。

累加结果：将所有满足条件的组合数累加，得到区间 [0, x) 内的 RN 数个数。

3. 主函数实现

在 main 函数中，我们初始化组合数表，并读取输入的 s 和 e。然后计算 getn(e+1) - getn(s)，得到区间 [s, e] 内的 RN 数个数。

代码实现

#include 
   
    using namespace std;int s, e;int C[35][35], sum[35];void init() {    C[0][0] = 1;    for (int i = 1; i <= 32; ++i) {        C[i][0] = C[i][i] = 1;        for (int j = 1; j < i; ++j) {            C[i][j] = C[i-1][j-1] + C[i-1][j];        }    }    for (int i = 2; i <= 32; ++i) {        for (int j = i + 1; j < i; ++j) {            sum[i] += C[i-1][j];        }    }}int getn(int x) {    if (x <= 1) return 0;    int ans = 0, len = 0, num0 = 0, num1 = 1;    int bit[35];    while (x) {        bit[len++] = x % 2;        x /= 2;    }    for (int i = 2; i <= len; ++i) {        ans += sum[i];    }    for (int i = len - 1; i >= 0; --i) {        if (bit[i]) {            for (int j = i; j >= 0 && j + num0 + 1 > num1 + i - j; --j) {                ans += C[i][j];            }            num1++;        } else {            num0++;        }    }    return ans;}int main() {    init();    scanf("%d%d", &s, &e);    printf("%d\n", getn(e + 1) - getn(s));    return 0;}

解释

预处理组合数：函数 init() 预处理组合数表 C 和 sum，其中 sum[i] 表示长度为 i 的数中 RN 数的个数。

计算 RN 数个数：函数 getn(x) 计算区间 [0, x) 内的 RN 数个数。通过转换 x 为二进制表示，逐位分析每一位的贡献。

主函数：读取输入的 s 和 e，计算区间 [s, e] 内的 RN 数个数，并输出结果。

这个方法通过预处理组合数和逐位分析二进制位，高效地计算了区间内的 RN 数个数，保证了算法的时间复杂度为 O(n)。

转载地址：http://zcxfk.baihongyu.com/

你可能感兴趣的文章