首页 > 代码库 > BestCoder13 1001.Beautiful Palindrome Number(hdu 5062) 解题报告
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", n == 1 ? 9 : ans[n]);60 }61 }62 return 0;63 }
（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", n == 0 ? 1 : ans[n]); // 10^0 也要考虑，即143 }44 }45 return 0;46 47 }
听说还可以用组合数学做，一个一个数当然也行
BestCoder13 1001.Beautiful Palindrome Number(hdu 5062) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。