加强文明网站内容建设,做网站的登陆功能,WordPress富媒体说说,wordpress必装的插件题目链接: http://poj.org/problem?id2402 题目大意就是让你找到第n个回文数是什么. 第一个思路当然是一个一个地构造回文数直到找到第n个回文数为止(也许大部分人一开始都是这样的思路). 很明显找到第n个之前的所有操作都是浪费, 这也是这个方法的最大弱点. 抱着侥幸心理(谁知…题目链接: http://poj.org/problem?id2402 题目大意就是让你找到第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 iostream2 using namespace std;3 4 char toch(int n) {5 return n0;6 }7 8 long long power(int e) {9 int sum 1, i 0;
10 for (; ie; 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 (i0; ; i) {
18 t 9 * power(i/2);
19 if (n lvlt) {
20 w i1;
21 n - lvl;
22 break;
23 }
24 lvl t;
25 }
26 n--;
27 div power((w-1)/2);
28 for (i0; i(w1)/2; i) {
29 s[i] s[w-i-1] toch(w3 ? n/div1 : (i?n/div:n/div1));
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, 这里只是为了保险起见.转载于:https://www.cnblogs.com/lsdsjy/p/poj2402.html
