Skip to content

S2OJ - 1808. 数数

题解716 字
# S2OJ # 2017 # bitset # 长乐集训 # 打表
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

给定 L,RL, R，请你回答 [L,R][L, R] 中有多少整数，满足它们的数位能被分成两个可重数集（每个数位都必须分配进某个数集），并且这两个数集里的数的和相等。

比如数字 123123 符合条件，因为其数位可以分成 {1,2}\{1, 2\} 与 {3}\{3\}，1+2=31 + 2 = 3。相应地，124124 不符合条件。

#输入格式

仅一行两个整数 L,RL, R。

#输出格式

仅一行一个整数表示答案。

#输入输出样例

样例输入 #1

9 28

样例输出 #1

2

#数据范围与约定

  • 对于 30%30\% 的数据，1≤L≤R≤1031 \leq L \leq R \leq 10^3；
  • 对于 60%60\% 的数据，1≤L≤R≤1071 \leq L \leq R \leq 10^7；
  • 对于 100%100\% 的数据，1≤L≤R≤1091 \leq L \leq R \leq 10^9。

#思路

先考虑如何确定某个特定的数是否可以被分为两个可重数集，使得这两个数集的和相等。

一个十位数所有数位相加之和最大为 10×9=9010 \times 9 = 90。那么可以开一个 std::bitset 来记录所有可能的和，最后判断 所有数位的和2\frac{\text{所有数位的和}}{2} 是否能被拼出来即可。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool check(int x) {
    int s = 0;
    std::bitset<128> f;

    f.set(0);

    while (x) {
        int k = x % 10;

        f |= f << k;
        s += k;
        x /= 10;
    }

    return s % 2 == 0 && f[s >> 1];
}

接下来分块打表即可，每块 10610^6 个数。

#代码

生成出的表将会输出至 stdout，并且会在 stderr 中输出当前的进度。

C++
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
#include <iostream>
#include <bitset>

using std::cin;
using std::cout;
const char endl = '\n';

const int SIZE = 1000000;

bool check(int x) {
    int s = 0;
    std::bitset<128> f;

    f.set(0);

    while (x) {
        int k = x % 10;

        f |= f << k;
        s += k;
        x /= 10;
    }

    return s % 2 == 0 && f[s >> 1];
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0, cnt = 0; i <= 1e9; i++) {
        if (check(i)) cnt++;

        if (i % SIZE == 0) {
            cout << cnt << ", ";
            std::cerr << i << endl;
        }
    }

    return 0;
}
C++
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
50
#include <iostream>
#include <bitset>

using std::cin;
using std::cout;
const char endl = '\n';

const int SIZE = 1000000;

const int f[]{/* 表 */};

bool check(int x) {
    int s = 0;
    std::bitset<128> f;

    f.set(0);

    while (x) {
        int k = x % 10;

        f |= f << k;
        s += k;
        x /= 10;
    }

    return s % 2 == 0 && f[s >> 1];
}

int solve(int x) {
    int res = f[x / SIZE];

    for (int i = x / SIZE * SIZE + 1; i <= x; i++) {
        if (check(i)) res++;
    }

    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int l, r;

    cin >> l >> r;

    cout << solve(r) - solve(l - 1) << endl;

    return 0;
}