題目鏈接: http://poj.org/problem?id=2402
題目大意就是讓你找到第n個回文數是什么.
第一個思路當然是一個一個地構造回文數直到找到第n個回文數為止(也許大部分人一開始都是這樣的思路). 很明顯找到第n個之前的所有操作都是浪費, 這也是這個方法的最大弱點. 抱著僥幸心理(誰知道數據弱不弱啊)用這種方法提交了下, TLE (在另一個OJ上提交是9個測試點過了6個).
第二個思路也很容易想到, 但是比第一個思路要麻煩: 第n個回文數的每位數字都與n有一定的關聯. 也就是說由n的值可以推測出回文數. 那么如何推算呢? 首先當然要來找規律. 我們可以發現:
位數為1和2的回文數有9個 (1-9, 11-99)
位數為3和4的回文數有90個 ({101-191, 202-292, ...}, {1001-1991, 2002-2991, ...})
位數為5和6的回文數有900個 (不再列舉)
......
所以:
第1-9個回文數的位數為1
第10-18個回文數的位數為2
......
然后確定了位數之后(從某種意義上說)n已經沒有用了, 此時有用的應該是n在這個區間的位置.
比如第11個回文數是2位數, 11在10-18這個區間中是第2個. 2位數的回文數是從11-99, 而11在10-18中是第2個, 所以是11-99中的第2個, 也就是22.
然后把n的區間拉到19-98, 也就是說回文數是3位數的時候. 從19-28, 也就是這個區間當中的第1-10個, 它們的第1位和第3位都是1(1-10是這個區間中的第1組10個數); 從29-38(區間中的第11-20個), 它們的第1位和第3位都是2(11-20是這個區間中的第2組10個數); 以此類推.
繼續看19-28(區間中的第1-10個), 它們在區間中的序號就是回文數的第二位.
......
所以, 就可以發現區間決定一切. 回文數的每一位, 都由n所處的區間所決定.
到這里大概就可以寫出程序了. 有些細節可能需要處理. 下面上代碼.
1 #include <iostream> 2 using namespace std; 3 4 char toch(int n) { 5 return n+'0'; 6 } 7 8 long long power(int e) { 9 int sum = 1, i = 0; 10 for (; i<e; i++) 11 sum *= 10; 12 return sum; 13 } 14 15 void gen(long long n, char* s) { 16 long long i, lvl = 0, w, t, div; 17 for (i=0; ; i++) { 18 t = 9 * power(i/2); 19 if (n <= lvl+t) { 20 w = i+1; 21 n -= lvl; 22 break; 23 } 24 lvl += t; 25 } 26 n--; 27 div = power((w-1)/2); 28 for (i=0; i<(w+1)/2; i++) { 29 s[i] = s[w-i-1] = toch(w<3 ? n/div+1 : (i?n/div:n/div+1)); 30 n %= div; 31 div /= 10; 32 } 33 } 34 35 int main() { 36 long long t; 37 while (1) { 38 cin >> t; 39 if (!t) 40 break; 41 char s[1000] = {0}; 42 gen(t, s); 43 cout << s << endl; 44 } 45 return 0; 46 }
//其實沒必要long long, 這里只是為了保險起見.
和sizeof(指針))
