首页 > 代码库 > hdu-5920 Ugly Problem(贪心)
hdu-5920 Ugly Problem(贪心)
题目链接：
Ugly Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 363 Accepted Submission(s): 134
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.
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).
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个回文数的和为这个数;
思路：
每次找前边取一半减一,然后再复制另一半,这样很快就好了，手写了了一个大数减法,写成了智障了都;
AC代码：
#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <bits/stdc++.h>#include <stack>#include <map>using namespace std;#define For(i,j,n) for(int i=j;i<=n;i++)#define mst(ss,b) memset(ss,b,sizeof(ss));typedef long long LL;typedef unsigned long long ULL;template<class T> void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<‘0‘||CH>‘9‘;F= CH==‘-‘,CH=getchar()); for(num=0;CH>=‘0‘&&CH<=‘9‘;num=num*10+CH-‘0‘,CH=getchar()); F && (num=-num);}int stk[70], tp;template<class T> inline void print(T p) { if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + ‘0‘); putchar(‘\n‘);}const LL mod=1e9+7;const double PI=acos(-1.0);const int inf=1e9;const int N=1e4+120;const int maxn=1e3+220;const double eps=1e-12;int n,k,cnt;char s[maxn];int a[maxn];struct Big{ int a[maxn],leng;}ans[maxn],temp;Big fun(Big A,Big B){ Big C; mst(C.a,0); for(int i=A.leng;i<maxn;i++)A.a[i]=0; for(int i=B.leng;i<maxn;i++)B.a[i]=0; int hi=max(A.leng,B.leng),lc=0; for(int i=0;i<hi;i++) { if(A.a[i]<B.a[i]) { A.a[i+1]--; A.a[i]+=10; C.a[i]=A.a[i]-B.a[i]; } else C.a[i]=A.a[i]-B.a[i]; } for(int i=0;i<=hi;i++) { if(C.a[i]<0) { C.a[i+1]--; C.a[i]+=10; } } int flag=1; for(int i=hi+1;i>=0;i--) { if(C.a[i]>0){lc=i;flag=1;break;} } if(flag)C.leng=lc+1; else C.leng=0; return C;}Big newBig(Big A){ int lenth=A.leng; Big B,C,D,E; mst(B.a,0);B.leng=0; mst(C.a,0);C.leng=0; mst(D.a,0);D.leng=0; mst(E.a,0);E.leng=0; B.leng=lenth; if(lenth%2==1) { int mid=lenth/2; for(int i=lenth-1;i>=mid;i--)B.a[i]=A.a[i]; for(int i=mid-1;i>=0;i--)B.a[i]=D.a[i]=0; D.a[mid]=1; D.leng=mid+1; E=fun(B,D); if(E.leng==A.leng-1) { C.leng=E.leng; for(int i=0;i<C.leng;i++)C.a[i]=9; } else { C.leng=A.leng; for(int i=C.leng-1;i>=mid;i--)C.a[i]=E.a[i]; for(int i=mid-1;i>=0;i--)C.a[i]=E.a[2*mid-i]; } } else { int mid=lenth/2; for(int i=lenth-1;i>=mid;i--)B.a[i]=A.a[i]; for(int i=mid-1;i>=0;i--)B.a[i]=D.a[i]=0; D.a[mid]=1;D.leng=mid+1; E=fun(B,D); if(E.leng!=lenth) { C.leng=E.leng; for(int i=C.leng-1;i>=0;i--)C.a[i]=9; } else { C.leng=lenth; for(int i=C.leng-1;i>=mid;i--)C.a[i]=E.a[i]; for(int i=mid-1;i>=0;i--)C.a[i]=E.a[2*mid-i-1]; } } return C;}void solve(){ int lenth=temp.leng; Big A; while(lenth) { if(lenth==2&&temp.a[1]==1) { A.leng=1; A.a[0]=9; } else if(lenth==1) { if(temp.a[0]==0)break; A.leng=1; A.a[0]=temp.a[0]; ans[++cnt]=A; break; } else A=newBig(temp); ans[++cnt]=A; temp=fun(temp,A); lenth=temp.leng; }}int main(){ int t,Case=0; read(t); while(t--) { printf("Case #%d:\n",++Case); scanf("%s",s); int len=strlen(s),num=0; cnt=0; for(int i=len-1;i>=0;i--)temp.a[num++]=s[i]-‘0‘; temp.leng=len; solve(); printf("%d\n",cnt); for(int i=1;i<=cnt;i++) { for(int j=ans[i].leng-1;j>=0;j--)printf("%d",ans[i].a[j]); printf("\n"); } } return 0;}
hdu-5920 Ugly Problem(贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。