1189 - Sum of Factorials PDF (English) Statistics ForumTime Limit: 0.5 second(s) Memory Limit: 32 MBGiven an integer n, you have to find whether it can be expressed as summation of factorials. For given n, you have to report a solution such that
n = x1! + x2! + ... + xn! (xi < xj for all i < j)
InputInput starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 1018).
OutputFor each case, print the case number and the solution in summation of factorial form. If there is no solution then print 'impossible'. There can be multiple solutions, any valid one will do. See the samples for exact formatting.
Sample InputOutput for Sample Input477911Case 1: 1!+3!Case 2: 0!+3!Case 3: 1!+2!+3!Case 4: impossible
解题思路:刚开始用dfs 跑，但是爆了，研究下发现，每次的答案出了0！和1！这两个相等的可以替换，其他都是唯一的， 因为阶乘相邻的差距太多，例如n前面的加起来都没有n!大，所以都是必须取的。 然后用这种贪心的策略跑一下就可以了
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; ll arr[20]; int save[20]; void init(){ arr[0] = arr[1] = 1; for(int i=2;i<=20;i++){ arr[i] = i*arr[i-1];//cout<<arr[i]<<endl; } return ; } int main(){ init(); int T; ll n; scanf("%d",&T); for(int t=1;t<=T;t++){ scanf("%lld",&n); printf("Case %d: ",t); for(int i=0;i<=20;i++){ if(n-arr[i]<0){ printf("impossible\n"); break; } int ans = 0; ll nn = n; for(int j=i;j>=0;j--){ if(nn-arr[j]>=0){ nn -= arr[j]; save[ans++] = j; //cout<<nn<<endl; if(nn==0){ printf("%d!",save[ans-1]); for(int k=ans-2;k>=0;k--) printf("+%d!",save[k]); printf("\n"); } } } if(nn==0) break; } } return 0; } //bool dfs(ll num,int t,int t1){ // if(num==0){ // printf("%d!",save[0]); // for(int i=1;i<t1;i++){ // printf("+%d!",save[i]); // } // printf("\n"); // return true; // } // if(num<0) return false; // for(int i=t;arr[i]<=num&&i<20;i++){ // save[t1] = i;//cout<<i<<endl;//cout<<(num-arr[i])<<" "<<arr[i]<<endl; // if(dfs(num-arr[i],i+1,t1+1)==true) return true; // // } // return false; //} View Code
转载于:https://www.cnblogs.com/yuanshixingdan/p/5561420.html
相关资源：JAVA上百实例源码以及开源项目