BestCoder13 1001.Beautiful Palindrome Number(hdu 5062) 解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5062

题目意思：给出 N，找出 1 ～ 10^N 中满足 Beautiful Palindrome Numbers （BPN）的数量有多少。满足 BPN 的条件有两个：（1）回文串（2）对称的部分从左到右递增排放。

（1）版本 1 （比较麻烦，建议看版本2） 46ms

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int N = 6 + 5;
 8 int ans[N];
 9 int num[N];
10 int l, ll;
11 
12 bool is_Palindrome(int tmp)
13 {
14     l = 0;
15     while (tmp > 0)
16     {
17         num[l++] = tmp % 10;
18         tmp /= 10;
19     }
20     l--;
21     for (int i = 0; i <= l/2; i++)
22     {
23         if (num[i] != num[l-i])
24             return false;
25         if (num[i] >= num[i+1] && i != l/2)
26             return false;
27     }
28     return true;
29 }
30 
31 int main()
32 {
33     int cnt;
34     ans[0] = 1;
35     ans[1] = 9;
36     //ans[6] = 258;
37     ll = 2, cnt = 9;
38     for (int i = 11; i <= 1e6; i++)
39     {
40         if (is_Palindrome(i))
41             cnt++;
42         if (i == 100)
43             ans[ll++] = cnt;
44         if (i == 1000)
45             ans[ll++] = cnt;
46         if (i == 10000)
47             ans[ll++] = cnt;
48         if (i == 100000)
49             ans[ll++] = cnt;
50         if (i == 1e6)
51             ans[ll] = cnt;
52     }
53     int T, n;
54     while (scanf("%d", &T) != EOF)
55     {
56         while (T--)
57         {
58             scanf("%d", &n);
59             printf("%d
", n == 1 ? 9 : ans[n]);
60         }
61     }
62     return 0;
63 }

View Code

（2）版本 2 （主要利用各种字符串处理函数） 250ms

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int N = 7 + 5;
 8 char str1[N], str2[N];
 9 int ans[N];
10 
11 int main()
12 {
13     for (int i = 1; i <= 1e6; i++)
14     {
15         sprintf(str1, "%d", i);
16         int len = strlen(str1);
17         strcpy(str2, str1);
18         reverse(str2, str2+len);
19         if (strcmp(str1, str2))
20             continue;
21         bool flag = true;
22         for (int j = 1; j < (len+1)/2; j++)
23         {
24             if (str1[j-1] >= str2[j])
25             {
26                 flag = false;
27                 break;
28             }
29         }
30         if (flag)
31             ans[len]++;
32     }
33     for (int i = 1; i <= 6; i++)
34         ans[i] += ans[i-1];
35 
36     int t, n;
37     while (scanf("%d", &t) != EOF)
38     {
39         while (t--)
40         {
41             scanf("%d", &n);
42             printf("%d
", n == 0 ? 1 : ans[n]);  // 10^0 也要考虑，即1
43         }
44     }
45     return 0;
46 
47 }

听说还可以用组合数学做，一个一个数当然也行