Skip to content

S2OJ - 1808. 数数

检测到 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\% 的数据,1LR1031 \leq L \leq R \leq 10^3
  • 对于 60%60\% 的数据,1LR1071 \leq L \leq R \leq 10^7
  • 对于 100%100\% 的数据,1LR1091 \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;
}