S2OJ - 441. 记分牌

#题面

#题目描述

比赛中记分牌上的得分数，由标有数字 $0$ ~ $9$ 的 $10$ 类卡片组合而成，例如得分 $225$ 由两张标有 $2$ 的卡片和一张标有 $5$ 的卡片组合而成。

然而，在一场比赛前，粗心的记分员只拿了包含 $0$ 在内的 $m$ 类卡片（假定每类卡片数目无限）。为了不延误比赛，记分员决定用这 $m$ 类卡片表示比赛分数，表示规则为：按从小到大的顺序，用第 $i$ 个能以这 $m$ 类卡片表示的十进制数代表得分 i，其中 $i \geq 0$。例如，若所带卡片只有 $\{0, 2, 4, 5\}$ 四类，则可组合成的十进制数从小到大分别为 $\{0, 2, 4, 5, 20, 22, 24, 25, 40, 42, 44, \ldots\}$ ，依次分别对应于得分 $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \ldots\}$ 。

当这 $m$ 类卡片所组合成数字的位数很多时，记分员自己也不知道到底现在分数是多少，请你编写程序帮助他/她计算准确的得分。其次，比赛还有一个关键得分 $s$ ，记分员还想知道得分为 $s$ 时记分牌上的数字会是多少。

#输入格式

第一行为正整数 $m$ ，表示目前可用数字卡片的种类数。

第二行为 $m$ 个各不相同的一位阿拉伯数字，以空格分隔，且其中肯定包含 $0$ 。表示 $m$ 种可用的卡片。

第三行为记分牌上的一个非负整数 $x$ ，其所有数位均取自第二行给定的 $m$ 个数字，且最高位非 $0$ 。

第四行为一个非负整数 $s$ ，你需要输出对应记分牌上的数字。

#输出格式

两行，第一行为十进制非负整数，对应于 $x$ 所表示的十进制得分。

第二行为一个非负整数，表示了分数为 $s$ 时对应的记分牌上的数字，保证此项输出不超过 $2147483647$ 。

#输入输出样例

输入样例 #1

4
0 4 2 7
27
7

输出样例 # 1

7 27

样例说明 #1

所给卡片从小到大排列为 $\{0, 2, 4, 7, 20, 22, 24, 27, \ldots\}$ ，对应得分为 $\{0, 1, 2, 3, 4, 5, 6, 7, \ldots\}$ 。

所以记分牌数字 $27$ 对应得分为 $7$ ，得分 $7$ 对应记分牌数字为 $27$ 。

#数据规模与约定

对于 $20\%$ 的数据，$m \leq 3$ ；
对于 $40\%$ 的数据，$x \leq 32767$ ， $s \leq 32767$ ；
对于 $100\%$ 的数据，$2 \leq m \leq 10$ ， $x \leq 2147483647$ 。

#思路

观察样例可知，卡片的排列可以看作是 $m$ 进制与 $10$ 进制间的转换。

$$\begin{aligned} \text{记分牌进制数} & \longleftrightarrow & \text{m 进制数} & \longleftrightarrow & \text{10 进制数} \\ 0 & \longleftrightarrow & 0 & \longleftrightarrow & 0 \\ 2 & \longleftrightarrow & 1 & \longleftrightarrow & 1 \\ 4 & \longleftrightarrow & 2 & \longleftrightarrow & 2 \\ 7 & \longleftrightarrow & 3 & \longleftrightarrow & 3 \\ 20 & \longleftrightarrow & 10 & \longleftrightarrow & 4 \\ 22 & \longleftrightarrow & 11 & \longleftrightarrow & 5 \\ 24 & \longleftrightarrow & 12 & \longleftrightarrow & 6 \\ 27 & \longleftrightarrow & 13 & \longleftrightarrow & 7 \\ & \ldots & \end{aligned}$$

故可以使用 std::map 来实现从记分牌与 $m$ 进制数之间的转换。

将读入的卡片先排序，然后建立映射：

1
2
3
4
5

sort(a, a + m);
for (int i = 0; i < m; i++) {
    m1[i] = a[i];
    m2[a[i]] = i;
}

此处 m1 是从 $m$ 进制到 「记分牌进制」 的转换， m2 是从 「记分牌进制」 到 $m$ 进制的转换。

先将读入的 $x$ 转为 $m$ 进制数：

1
2
3
4

reverse(x.begin(), x.end());
for (int i = 0; i < x.size(); i++) {
    mx.push_back(m2[x[i] - '0'] + '0');
}

再将这个 $m$ 进制数转为 $10$ 进制数：

1
2
3
4

reverse(mx.begin(), mx.end());
for (int i = 0; i < mx.size(); i++) {
    ans1 += (mx[i] - '0') * pow(m, i);
}

综合起来，就是下面这样：

1
2
3
4

reverse(x.begin(), x.end());
for (int i = 0; i < x.size(); i++) {
    ans1 += m2[x[i] - '0'] * pow(m, i);
}

之后输出 ans1 即可。

同样地，对 $s$ 的处理就是一个逆向过程。

先将读入的 $s$ 转换为 $m$ 进制数，再将这个 $m$ 进制数转换为 「记分牌进制」 数，合并以后就是这样：

1
2
3
4

while (s) {
    ans2.push_back(m1[s % m] + '0');
    s /= m;
}

之后输出 ans2 即可。

#代码

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

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, s, a[15], ans1 = 0;
    string x, ans2;
    map<int, int> m1, m2;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    sort(a, a + m);
    for (int i = 0; i < m; i++) {
        m1[i] = a[i];
        m2[a[i]] = i;
    }
    cin >> x >> s;
    reverse(x.begin(), x.end());
    for (int i = 0; i < x.size(); i++) {
        ans1 += m2[x[i] - '0'] * pow(m, i);
    }
    while (s) {
        ans2.push_back(m1[s % m] + '0');
        s /= m;
    }
    reverse(ans2.begin(), ans2.end());
    cout << ans1 << endl
         << ans2 << endl;
    return 0;
}

提交记录 #12569 - S2OJ