S2OJ - 441. 记分牌

题目链接:441. 记分牌 - S2OJ
难度:暂无评定

题面

题目描述

比赛中记分牌上的得分数,由标有数字 00 ~ 991010 类卡片组合而成,例如得分 225225 由两张标有 22 的卡片和一张标有 55 的卡片组合而成。

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

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

输入格式

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

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

第三行为记分牌上的一个非负整数 xx ,其所有数位均取自第二行给定的 mm 个数字,且最高位非 00

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

输出格式

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

第二行为一个非负整数,表示了分数为 ss 时对应的记分牌上的数字,保证此项输出不超过 21474836472147483647

输入输出样例

输入样例 #1

4
0 4 2 7
27
7

输出样例 # 1

7 27

样例说明 #1

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

所以记分牌数字 2727 对应得分为 77 ,得分 77 对应记分牌数字为 2727

数据规模与约定

对于 20%20\% 的数据,m3m \leq 3
对于 40%40\% 的数据,x32767x \leq 32767s32767s \leq 32767
对于 100%100\% 的数据,2m102 \leq m \leq 10x2147483647x \leq 2147483647

思路

观察样例可知,卡片的排列可以看作是 mm 进制与 1010 进制间的转换。

记分牌进制数m 进制数10 进制数00021142273320104221152412627137\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 来实现从记分牌与 mm 进制数之间的转换。

将读入的卡片先排序,然后建立映射:

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

此处 m1 是从 mm 进制到 「记分牌进制」 的转换, m2 是从 「记分牌进制」 到 mm 进制的转换。


先将读入的 xx 转为 mm 进制数:

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

再将这个 mm 进制数转为 1010 进制数:

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

综合起来,就是下面这样:

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

之后输出 ans1 即可。


同样地,对 ss 的处理就是一个逆向过程。

先将读入的 ss 转换为 mm 进制数,再将这个 mm 进制数转换为 「记分牌进制」 数,合并以后就是这样:

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

之后输出 ans2 即可。

代码

#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

S2OJ - 441. 记分牌
本文作者
宝硕
发布于
2021-07-02
许可协议
喜欢这篇文章?为什么不考虑打赏一下作者呢?
爱发电
文章目录
  1. 题面
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 输入输出样例
    5. 数据规模与约定
  2. 思路
  3. 代码