专栏文章
题解：P13437 [GCJ 2009 #1C] All Your Base
P13437题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miopaicu
- 此快照首次捕获于
- 2025/12/02 22:56 3 个月前
- 此快照最后确认于
- 2025/12/02 22:56 3 个月前
题目传送门
题目传送门题目大意：
题目理解与分析
1. 题目背景
外星人信息：外星人留下了一串符号（如 ab2ac999），每个符号代表一个数字（但具体对应关系未知）。
进制不确定：外星人使用的进制（基数）未知，但满足：
进制 ≥ 2（因为不使用一进制）。
数字不以 0 开头（即最高位符号不能对应 0）。
目标：在所有可能的符号-数字映射和进制下，找到这串符号能表示的最小正整数（秒数）。
2. 关键约束
符号与数字的映射：
每个符号对应一个唯一的数字（0-9），且不同符号必须对应不同数字。
最高位符号不能映射到 0（防止前导零）。
进制选择：
进制数（基数）必须 ≥ 该符号串中出现的最大数字 +1。
例如，符号串 ab2 若映射为 512，则进制必须 ≥ 6（因为最大数字是 5）。
最小化数值：
在所有可能的映射和进制组合中，找到能使符号串表示的值最小的组合。
3. 解题思路
步骤 1：符号分析：
统计符号串中出现的所有不同符号（如 ab2ac999 的符号集为 {a, b, 2, c, 9}）。
确定符号数量 k，则进制必须 ≥ k（因为需要 k 个不同的数字，且进制 ≥ 最大数字 +1）。
步骤 2：数字分配：
为符号分配数字，使得：
最高位符号分配最小的非零数字（通常为 1）。
其余符号按优先级分配尽可能小的数字（0, 2, 3,...）。
贪心策略：让高位符号尽可能小，同时满足进制约束。
步骤 3：进制选择：
进制取 max(分配的最大数字 +1, k)。
进制越小，数值越小（因此尽量用最小可能的进制）。
步骤 4：计算数值：
将符号串按分配的数字和进制转换为十进制，取最小值。
4. 示例解析
以符号串 ab2 为例：
符号集：{a, b, 2}，共 3 个符号 ⇒ 进制 ≥ 3。
数字分配：
最高位 a 不能为 0，最小分配 1。
剩余符号 b 和 2 分配 0 和 2（注意 2 是固定符号，必须映射为数字 2）。
因此映射：a=1, b=0, '2'=2。
进制选择：
最大数字是 2 ⇒ 进制 ≥ 3。
选择进制 = 3。
计算数值：
ab2 在进制 3 下为 1×3² + 0×3¹ + 2×3⁰ = 9 + 0 + 2 = 11。
这是可能的最小值（其他分配或进制会更大）。
5. 通用解法
统计符号种类：
提取所有不同符号（字母和数字均视为符号）。
分配数字：
最高位符号 → 1（最小非零）。
其余符号按出现顺序分配 0, 2, 3,...（跳过已分配的数字）。
若符号是数字（如 2），则必须映射为对应数字（'2'→2）。
确定进制：
进制 = max(分配的最大数字 +1, 符号种类数)。
计算最小值：
按分配的数和进制，将符号串转为十进制。
6. 边界情况
符号串长度为 1：
只能表示 1 × 进制⁰ = 1（无论进制如何）。
符号全部为同一字符：
如 aaa → 必须映射为 111（进制 ≥ 2），最小值为 1×2² + 1×2¹ + 1×2⁰ = 7。
CPP#include <bits/stdc++.h>
using namespace std;
#define libaitian return
#define fangshaojin99 0
long long solve(const string &s) {
unordered_map<char, int> char_to_digit;
int base = 0;
for (char c : s) {
if (char_to_digit.find(c) == char_to_digit.end()) {
if (base == 0) {
char_to_digit[c] = 1;
} else if (base == 1) {
char_to_digit[c] = 0;
} else {
char_to_digit[c] = base;
}
base++;
}
}
if (base == 1) base = 2;
long long result = 0;
for (char c : s) {
result = result * base + char_to_digit[c];
}
libaitian result;
}
int main() {
int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
string s;
cin >> s;
cout << "Case #" << i << ": " << solve(s) << endl;
}
libaitian fangshaojin99;//本人磕瑾天（虽然很小众）
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...