USACO 1.2 Dual Palindromes：多進制回文檢測

USACO 1.2 Dual Palindromes：多進制回文檢測

找大於 S 的前 N 個整數，使其在 2~10 進制中至少有兩種為回文數。N≤15, S≤10000。

算法流程

1. 從 S+1 開始枚舉整數 i。
2. 對每個 i，檢查進制 2~10 的表示是否為回文。
3. 計數達 2 即合格，輸出並計入答案。
4. 直到找到 N 個合格數。

進制轉換與回文判斷

void toBase(int num, int base) {
    int idx = 0;
    while (num / base) {
        s[idx++] = "0123456789ABCDEF"[num % base];
        num /= base;
    }
    s[idx++] = "0123456789ABCDEF"[num % base];
    s[idx] = '\0';
}

bool isPalindrome() {
    int len = strlen(s);
    if (s[0] == '0' && s[len-1] == '0') return false; // 排除前導零情況
    for (int i = 0; i <= len/2; i++)
        if (s[i] != s[len-1-i]) return false;
    return true;
}

完整代碼（C++）

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

char s[100];
int N, S;

int main() {
    freopen("dualpal.in", "r", stdin);
    freopen("dualpal.out", "w", stdout);
    scanf("%d %d", &N, &S);
    int found = 0;
    for (int i = S+1; ; i++) {
        int palCount = 0;
        for (int b = 2; b <= 10; b++) {
            if (palCount >= 2) break;
            toBase(i, b);
            if (isPalindrome()) palCount++;
        }
        if (palCount >= 2) {
            printf("%d\n", i);
            if (++found == N) break;
        }
    }
    return 0;
}

關鍵點

• 進制轉換用字符串查表 "0123456789ABCDEF" 簡潔高效。
• 回文判斷排除前導零（如 1001 合法，010 非法）。
• USACO 題目要求文件 IO，freopen 處理。
• 數據範圍小，暴力枚舉完全足夠。

複雜度

• 檢查一個數：9 * log_base(i) 位操作。
• 總體極快，秒級通過。

此題是進制轉換、回文判斷、暴力枚舉的基礎綜合練習，USACO 入門經典題目。