题解：P13437 [GCJ 2009 #1C] All Your Base

· · 题解

题目传送门

题目大意：

‌题目理解与分析‌ ‌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。 ‌

#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;//本人磕瑾天（虽然很小众）
}