B4088 [CSP-X2020 山东] 最大回文数

chen_zhe · 2025-03-05 10:14:18 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

这道题目需要我们从输入的一批正整数中筛选出最大的回文数。所谓回文数，就是正读和倒读都完全一致的数字，比如经典的 1221 或对称结构的 1234321。

特别要注意的是，题目中给出的数字可能极其庞大（最大可达 10^{32}），这意味着常规的整型变量无法存储，必须采用字符串形式来处理这些数字。

在解决问题的过程中，两个关键点需要特别注意：如何高效判断回文数，以及如何比较超大数字的大小。

对于回文判断，我们可以将数字视为字符串，通过左右双指针同时向中间移动的方式快速验证。具体来说，设置起始指针和末尾指针，每次比较两端的字符是否相同，直到指针相遇或发现不匹配的字符。这里给出该函数的示例。

bool isPal(string s) {
    int left = 0, right = s.size()-1;
    while(left < right) {
        if(s[left] != s[right]) return false;
        left++; right--;
    }
    return true;
}

当处理大数比较时，直接转为数值类型显然不可行。这里可以采用两步比较策略：首先比较字符串长度，长度较长的自然数值更大；若长度相同，则按照字典序逐位比较字符。这种比较方式完全符合数值大小的本质规律，例如 4567 和 4558 这两个四位数，通过字典序比较到第三位时即可判断前者更大。

整个算法的执行流程可以概括为：遍历所有输入的数字，通过回文判断筛选出候选对象，同时动态维护当前最大值的记录。具体实现时需要注意初始化最大值为空字符串，并在遇到符合条件的更大回文数时及时更新。这里提供主函数的代码：

int main(){
    int n;
    cin >> n;
    string ans = "";  // 用于保存当前最大的回文数（以字符串形式存储）
    while(n--){
        string s;
        cin >> s;
        if(isPal(s)){
            // 如果 ans 为空，或者 s 长度更长（位数更多），或者长度相同但字典序更大
            if(ans == "" || s.size() > ans.size() || (s.size() == ans.size() && s > ans)){
                ans = s;
            }
        }
    }
    cout << ans << endl;
    return 0;
}