UVa12670 Counting Ones

原题链接:UVa12670

题目大意:多组测试数据,每组给定两个整数 $a,b\in [1,10^{16}]$,求区间 $[a,b]$ 中所有数的二进制中 $1$ 的个数。

数位 DP

解法

比较基础的数位 DP,求出 $0\text{~}n$ 中的所有数的二进制中 $1$ 的个数,那么 $[a,b]$ 区间内的 $1$ 的个数只需要作差求解。

首先将 $n$ 进行二进制分解,然后从高位往低位枚举。用res存答案,last表示在当前这一位的更高位已经选择了多少个 $1$。如果枚举到的当前位为 $1$,那么在这一位上有两种选择,如果选择该位为 $0$,那么剩下的低位任意选择 $0$ 或 $1$ 即可,枚举一下剩下的 $i$ 位中选择 $j$ 个 $1$,那么低位中对 $1$ 的个数的贡献就是j * c[i][j],同时需要求出此时低位的所有选择的方案数cnt,我们知道在前面已经选择了last个 $1$,因此还需要算上高位对 $1$ 的个数的贡献即last * cnt;如果选择该位为 $1$,那么只要令last++即可。最后记得res += last

代码

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 60;

LL c[N][N]; // c[i][j]表示共i位有j位为1的方案数

void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j) c[i][j] = 1;
            else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
}
LL solve(LL n) {
    if (!n) return 0;
    vector<int> num;
    while (n) num.push_back(n % 2), n /= 2;
    LL res = 0, last = 0; // last表示已经选择的1的个数
    for (int i = num.size() - 1; i >= 0; i--) {
        int x = num[i];
        if (x) {
            // 该位取0,那么剩下i位随便选
            LL cnt = 0; 
            for (int j = 0; j <= i; j++) {
                res += j * c[i][j]; // 低位对1的贡献
                cnt += c[i][j];
            }
            res += cnt * last; // 高位对1的贡献
            // 该位取1
            last++;
        }
        if (!i) res += last; // 加上右侧分支中1的个数
    }
    return res;
}

int main() {
    init();
    LL l, r;
    while (cin >> l >> r) {
        cout << solve(r) - solve(l - 1) << endl;
    }
    return 0;
}
updatedupdated2020-05-142020-05-14
加载评论
点击刷新