洛谷P1015 [NOIP 1999 普及組] 回文數 題解

題目描述

P1015 回文數 是NOIP 1999普及組的經典模擬題。題目要求如下：

給定一個數N（十進制）和進制K（2≤K≤16），將N轉換為K進制表示后，通過以下操作使其變為回文數：

1. 將當前數與其逆序數相加
2. 重復操作直到得到回文數或超過30次操作

輸入格式：

• 第一行輸入進制K（2≤K≤16）
• 第二行輸入十進制數N（1<N≤1e9）

輸出格式：

• 若30步內得到回文數，輸出STEP=步數
• 否則輸出Impossible!

解題思路

本題是典型的進制轉換+模擬操作問題，核心在于：

1. 正確實現大數的K進制轉換
2. 高效處理大數加法與進位
3. 準確判斷回文數

關鍵算法步驟

1. 進制轉換：將十進制數N轉換為K進制表示
2. 回文判斷：檢查當前數是否為回文
3. 加法模擬：實現大數與其逆序數的加法運算
4. 進位處理：處理不同進制下的進位邏輯

代碼解析（附用戶代碼講解）

以下是用戶提供的代碼的逐層解析：

#include<bits/stdc++.h>
#include<string>
using namespace std;int N;          // 目標進制
int step = 0;   // 操作步數
int len = 0;    // 當前數位長度
int ans[205] = {0};  // 存儲K進制數（低位在前）
int tem[205] = {0};  // 臨時反轉數組
int re[205] = {0};   // 未使用（可忽略）// 回文數檢查函數
int Check() {for(int i=0; i<len/2; ++i) {if(ans[i] != ans[len-i-1]) return -1;}return 1;
}// 加法操作函數
void play() {// 反轉數組到temfor(int i=0; i<len; ++i) tem[i] = ans[len-i-1];// 執行加法for(int i=0; i<len; ++i) ans[i] += tem[i];// 進位處理for(int i=0; i<len; ++i) {if(N != 16) {  // 非16進制通用處理if(ans[len-1] >= N) len++;ans[i+1] += ans[i] / N;ans[i] %= N;} else {        // 16進制特殊處理if(ans[len-1] >= 16) len++;ans[i+1] += ans[i] / 16;ans[i] %= 16;}}
}int main() {ios::sync_with_stdio(false);cin.tie(0);string s;cin >> N >> s;len = s.length();// 初始化K進制數（注意低位存儲方式）for(int i=0; i<len; ++i) {if(isdigit(s[len-i-1]))ans[i] = s[len-i-1] - '0';elseans[i] = s[len-i-1] - 'A' + 10;}if(Check() == 1) {  // 初始即為回文cout << "STEP=0";} else {while(step <= 30) {play();step++;if(Check() == 1) break;}if(step <= 30)cout << "STEP=" << step;elsecout << "Impossible!";}return 0;
}

代碼特點分析

1. 低位優先存儲：使用數組ans[]的低位在前方式存儲，簡化進位操作
2. 雙模式進位處理：通過N != 16判斷統一處理不同進制
3. 動態長度維護：通過len變量動態跟蹤當前數位長度

優化方案與注意事項

優化方向

1. 預分配數組空間：可預先分配200位空間，避免頻繁擴容
2. 提前終止判斷：在加法操作前即可判斷是否已產生回文
3. 進制處理統一化：將16進制特殊處理合并到通用邏輯中

關鍵細節說明

1. 輸入處理：

   • 使用len-i-1實現字符串反轉初始化
   • 正確處理字母A-F（10-15）的轉換

2. 進位邏輯：

   • 從低位到高位處理進位
   • 每次加法后檢查最高位是否需要擴容

3. 回文判斷：

   • 只需檢查前半部分與對應后半部分是否相等

測試樣例分析

示例1

輸入：

9
87

輸出：

STEP=4

過程：

87(10) = 106(9)
106 + 601 = 707（回文，4步）

示例2

輸入：

10
196

輸出：

Impossible!

（著名的回文數猜想反例）

復雜度分析

• 時間復雜度：O(30*L)，其中L為最大數位長度（≤200）
• 空間復雜度：O(L)，使用固定大小數組存儲

總結

1. 本題核心是掌握大數運算在模擬題中的應用
2. 關鍵點在于：
   • 正確實現進制轉換
   • 高效處理大數加法與進位
   • 準確判斷回文結構
3. 實際編程時需特別注意：
   • 數組越界問題（動態維護len變量）
   • 不同進制的字符處理（0-9和A-F）
   • 步驟計數器的初始值與終止條件

通過本題可以鞏固：

• 進制轉換的雙向實現
• 大數運算的基本技巧
• 模擬算法的優化策略