Ugly Problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 812    Accepted Submission(s): 286 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 Hint 9 + 9 = 18 999999999999 + 1 = 1000000000000   题意：将一个数s (1<=s<=10^1000) 拆成不超过50个回文数， 这些回文数相加等于s。 要求输出这样的数的个数，并从小到大输出这些数。 题解：每次都构造当前<=s的近似最大的回文数build ，然后 s=s-build 。  用字符串表示的时候注意写法就行了。 代码如下： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 1010 struct Node { char num[maxn]; int len; }ans[102];//ans数组开在main函数厉害爆栈了 Node detail(Node str)//构造一个较大的回文数 { int temp=str.len/2+1; str.num[temp]--; for(int i=temp;i<=str.len;++i) if(str.num[i]<'0') { str.num[i+1]--; str.num[i]+=10; } if(str.num[str.len]=='0') str.len--; for(int i=1;i<=str.len/2;++i) str.num[i]=str.num[str.len-i+1]; return str; } Node sub(Node res,Node subtor)//大数相减 { for(int i=1;i<=subtor.len;++i) { if(res.num[i]>=subtor.num[i]) res.num[i]=res.num[i]-subtor.num[i]+'0'; else { res.num[i+1]--; res.num[i]+=10; res.num[i]=res.num[i]-subtor.num[i]+'0'; } } for(int i=res.len;i>0;--i) { if(res.num[i]=='0') res.len--; else break; } return res; } int main() { int t,k=1; scanf("%d",&t); while(t--) { Node str; memset(ans,0,sizeof(ans)); scanf("%s",str.num+1); str.len=strlen(str.num+1); for(int i=1;i<=str.len/2;++i)//反转字符串，让高位表示高数位 swap(str.num[i],str.num[str.len-i+1]); int cnt=0; while(str.len>1) { if(str.len==2&&((str.num[1]-'0'+(str.num[2]-'0')*10)<20)) { ans[cnt].num[1]='9'; ans[cnt++].len++; str=sub(str,ans[cnt-1]); continue; } Node build=detail(str); ans[cnt++]=build; str=sub(str,ans[cnt-1]); } ans[cnt++]=str; printf("Case #%d:\n%d\n",k++,cnt); for(int i=0;i<cnt;++i) { for(int j=ans[i].len;j>=1;--j) putchar(ans[i].num[j]); printf("\n"); } } return 0; }