Ugly Problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1159    Accepted Submission(s): 409 Special Judge Problem Description Everyone hates ugly problems. You are given a positive integer. You must represent that number by sum of palindromic numbers. A palindromic number is a positive integer such that if you write out that integer as a string in decimal without leading zeros, the string is an palindrome. For example, 1 is a palindromic number and 10 is not.   Input In the first line of input, there is an integer T denoting the number of test cases. For each test case, there is only one line describing the given integer s ( 1≤s≤101000 ).   Output For each test case, output “Case #x:” on the first line where x is the number of that test case starting from 1. Then output the number of palindromic numbers you used, n, on one line. n must be no more than 50. en output n lines, each containing one of your palindromic numbers. Their sum must be exactly s.   Sample Input 2 18 1000000000000   Sample Output Case #1: 2 9 9 Case #2: 2 999999999999 1

题意：给定一个数字，找出一个或几个回文数字，使得这几个回文数字之和刚好等于给出的数字。回文数字的数量不大于50！！！

字符串长度len无论奇偶，i与len-1-i都是左右对称的这点很受用

/* 思路：从中间开始向两边遍历并逐位赋值给b，找到不对称的地方时取较小的数， 每次找到的b都是小于a的较大回文数字，然后更新a，直到a的长度为1 */ #include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int N = 1010; char a[N],b[N],c[N],ans[N][N]; int len,num; int main() { int t; cin>>t; for(int k=1;k<=t;k++) { cin>>a; //条件数字输入 len=strlen(a); num=0; while(len>=1) { bool flag=0; b[len>>1]=a[len>>1]; //为奇数长度服务，因为在循环中奇数长度的中间字符没有包含 for(int i=len/2-1;i>=0;i--) //用这种方法可以很好的一起处理len为奇数或偶数的情况 { if(a[i]!=a[len-1-i]&&!flag) //找到首个两边不相等的字符，并取小的 { flag=1; b[i]=b[len-1-i]=a[i]<a[len-1-i]?a[i]:a[len-1-i]; } else //因为对输出回文数字的个数有要求所以要使得这些回文数字尽可能大但是又不能比给定数字a大 b[i]=b[len-1-i]=a[i]; } b[len]=0; if(!flag) //如果本身已经是个回文数字就退出while循环准备输出 { strcpy(ans[num++],a); break; } if(b[0]=='0') //特殊情况，b有前导0 { if(a[0]=='1') //把a拆分为1,9999…9，还有余下部分 { strcpy(ans[num++],"1\0"); for(int i=0;i<len-1;i++) ans[num][i]='9'; ans[num++][len-1]=0; } else //根据a[0]不同把a拆分为8,2999…92，余下部分 或7,3999…93，余下部分 或…… { int m=a[0]-'0'; ans[num][0]=(char)(11-m+'0'); ans[num++][1]=0; ans[num][0]=ans[num][len-1]=(char)(a[0]-1); for(int i=1;i<len-1;i++) ans[num][i]='9'; ans[num++][len]=0; } b[0]=a[0]; for(int i=1;i<len;i++)b[i]='0'; b[len]=0; } //没有前导0，直接把b放到结果串中 else { strcpy(ans[num++],b); } //获取c=a-b 并消除前导0存入a bool jw=false; int ta,tb,n; for(int i=len-1;i>=0;i--) { ta=a[i]-'0'; tb=b[i]-'0'; n=(10+a[i]-b[i]-jw); c[i]=n+'0'; jw=(a[i]-b[i]-jw)<0; } c[len]=0; int tc=0; while(c[tc]=='0')tc++; strcpy(a,c+tc); len=strlen(a); } printf("Case #%d:\n%d\n",k,num); for(int i=0;i<num;i++)cout<<ans[i]<<endl; } }