第3章 进位制

1010. Radix

笔记

• 全部化成十进制再比较
• 可用秦九韶算法计算十进制数（递推计算）
• 最大值是zzzzzzzzzz<$10^{16}$，可用long long保存，但要注意尽可能都用long long
• long long作乘法会溢出，需要先转成double类型
• (double)(a * b)和(double) a * b不等价，前者先计算乘法，可能会溢出
• 最低开始查找的进制数可从数本身确定，但要注意+1
• 最高开始查找的进制数可能是目标本身，但至少是36起

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 1e18;

int get(char c) {
    if (c <= '9') return c - '0';
    else return c - 'a' + 10;
}

LL convert(string s, LL base) {
    LL res = 0LL;
    for (auto c : s) {
        if ((double) res * base + get(c) > 1e16) 
            return INF;     // 超过题目假定的最大上界，修枝
        res = res * base + get(c);
    }
    return res;
}

int main() {
    string s1, s2;
    LL tag, base;
    cin >> s1 >> s2 >> tag >> base;

    if (tag == 2LL) swap(s1, s2);
    LL target = convert(s1, base);

    LL l = 0LL, r = max(target, 36LL);
    for (auto c : s2)
        l = max(l, (LL)get(c) + 1LL);     // 确定表示s2所需的最低进制数

    // 二分
    LL i = l - 1, j = r + 1;
    while(i + 1 != j) {
        LL m = i + j >> 1;
        if (convert(s2, m) < target) i = m;
        else j = m;
    }

    if (convert(s2, j) == target) cout << j << endl;    // 取红色区域的端点
    else puts("Impossible");

    return 0;
}

1015. Reversible Primes

笔记

• 题目不仅要求转换后的是质数，还要求原本就是质数
• 可把d进制转换和倒置融合在一起实现，不必分开实现

#include <iostream>
using namespace std;

bool check(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++) 
        if (n % i == 0) return false;
    return true;
}

int convert(int n, int d) {
    int r = 0;
    while(n) {
        r = r * d + n % d;
        n /= d;
    }
    return r;
}

int main() {
    int n, d;
    while(scanf("%d", &n), n >= 0) {
        scanf("%d", &d);
        int tmp = convert(n, d);
        if (check(n) && check(tmp)) puts("Yes");
        else puts("No");
    }

    return 0;
}

1027. Colors in Mars

#include <iostream>
using namespace std;
int a[3];

char get(int n) {
    if (n < 10) return (char)('0' + n);
    else return (char)('A' + n - 10);
}

int main() {
    for (int i = 0; i < 3; i++)
        cin >> a[i];

    cout << "#";
    for (int i = 0; i < 3; i++)
        cout << get(a[i] / 13) << get(a[i] % 13);

    return 0;
}

1100. Mars Numbers

笔记

• 可用sstream中的stringstream类把字符串转换成流，方便处理
• 可通过文本编辑器把,替换成", "，再在首尾填上"，则可实现用双引号包裹所有单词。也可用正则表达式匹配([\w]{3})，然后替换成"$1"

#include <iostream>
#include <sstream>
using namespace std;

string names_low[] = {"tret", 
                  "jan", "feb", "mar", "apr", "may", "jun", 
                  "jly", "aug", "sep", "oct", "nov", "dec"};

string names_high[] = {                  
                  "tam", "hel", "maa", "huh", "tou", "kes", 
                  "hei", "elo", "syy", "lok", "mer", "jou"};

int get(string word) {
    // 假设是低位
    for (int i = 0; i <= 12; i++)
        if (names_low[i] == word)
            return i;
    // 假设是高位
    for (int i = 0; i < 12; i++)
        if (names_high[i] == word)
            return (i + 1) * 13;
    return -1;
}

int main() {
    int n;
    cin >> n;
    getchar();      // 去掉末尾空行

    while(n--) {
        string line;
        getline(cin, line);

        stringstream ssin(line);
        if (line[0] <= '9') {
            int x;
            ssin >> x;

            int d_low = x % 13, d_high = x / 13;
            if (x < 13) cout << names_low[d_low];
            else {
                cout << names_high[d_high - 1];
                if (x % 13 != 0) cout << " " << names_low[d_low];
            }
            cout << endl;
        } else {
            string word;
            int res = 0;
            while(ssin >> word) res += get(word);
            cout << res << endl;
        }
    }

    return 0;
}

1019. General Palindromic Number

笔记

• 转换成b进制后再用第二类双指针算法判断是否是回文数
• 注意特判是否为$0$

#include <iostream>
#include <vector>
using namespace std;

bool check(vector<int>& num) {
    for (int i = 0, j = num.size() - 1; i < j; i++, j--)
        if (num[i] != num[j]) 
            return false;
    return true;
}

int main() {
    int n, b;
    cin >> n >> b;

    vector<int> num;
    if (!n) num.push_back(0);
    while(n) {
        num.push_back(n % b);
        n /= b;
    }

    if (check(num)) puts("Yes");
    else puts("No");

    for (int i = num.size() - 1; i >= 0; i--) {
        cout << num[i];
        if (i > 0) cout << ' ';
    }

    return 0;
}