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

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int N =  + ;

 int ans[N];

 int num[N];

 int l, ll;

 bool is_Palindrome(int tmp)

 {

     l = ;

     while (tmp > )

     {

         num[l++] = tmp % ;

         tmp /= ;

     }

     l--;

     for (int i = ; i <= l/; i++)

     {

         if (num[i] != num[l-i])

             return false;

         if (num[i] >= num[i+] && i != l/)

             return false;

     }

     return true;

 }

 int main()

 {

     int cnt;

     ans[] = ;

     ans[] = ;

     //ans[6] = 258;

     ll = , cnt = ;

     for (int i = ; i <= 1e6; i++)

     {

         if (is_Palindrome(i))

             cnt++;

         if (i == )

             ans[ll++] = cnt;

         if (i == )

             ans[ll++] = cnt;

         if (i == )

             ans[ll++] = cnt;

         if (i == )

             ans[ll++] = cnt;

         if (i == 1e6)

             ans[ll] = cnt;

     }

     int T, n;

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             scanf("%d", &n);

             printf("%d\n", n ==  ?  : ans[n]);

         }

     }

     return ;

 }

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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N =  + ;

 char str1[N], str2[N];

 int ans[N];

 int main()

 {

     for (int i = ; i <= 1e6; i++)

     {

         sprintf(str1, "%d", i);

         int len = strlen(str1);

         strcpy(str2, str1);

         reverse(str2, str2+len);

         if (strcmp(str1, str2))

             continue;

         bool flag = true;

         for (int j = ; j < (len+)/; j++)

         {

             if (str1[j-] >= str2[j])

             {

                 flag = false;

                 break;

             }

         }

         if (flag)

             ans[len]++;

     }

     for (int i = ; i <= ; i++)

         ans[i] += ans[i-];

     int t, n;

     while (scanf("%d", &t) != EOF)

     {

         while (t--)

         {

             scanf("%d", &n);

             printf("%d\n", n ==  ?  : ans[n]);  // 10^0 也要考虑，即1

         }

     }

     return ;

 }

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