DFS(dfs)

showproblem.php?pid=2212

DFS

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6322 Accepted Submission(s): 3898

Problem Description

A DFS(digital factorial sum) number is found by summing the factorial of every digit of a positive integer.

For example ,consider the positive integer 145 = 1!+4!+5!, so it's a DFS number.

Now you should find out all the DFS numbers in the range of int( [1, 2147483647] ).

There is no input for this problem. Output all the DFS numbers in increasing order. The first 2 lines of the output are shown below.

Input

no input

Output

Output all the DFS number in increasing order.

Sample Output

1
2
......

Author

zjt

题解:开始想到10位数,枚举每一位数字肯定会超时,O(10的10次方) 根据枚举的情况,1!+4!+5!和5!+4!+1!是一样的,所以可以从大到小按照顺序枚举出所有情况,即可,这样下一个位置枚举的时候就不可以出现比最后小的元素了,这里注意0的阶乘是1,而且为了避免第一位出现0 的情况,从最后一位向前枚举,最后的输出结果只有4个数,所以可以之间打表输出这4个数即可

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 //#define N 8776444321ll//要在后面加ll 这样不会超int
 5 #define ll long long
 6 const ll N = 8776444321;
 7 ll ans[500];
 8 int c ;
 9 int f[10],g[10];
10 int a[10];
11 int ck(ll sum)
12 {
13     for(int i = 0 ; i < 10 ; i++) f[i] = 0,g[i] = 0;
14     ll v = sum;
15     ll tm = 0 ;
16     while(v)
17     {
18         tm+=a[v%10];
19         f[v%10]++;
20         v/=10;
21     }
22     v = tm;
23     while(tm)
24     {
25         g[tm%10]++;
26         tm/=10;
27     }
28     for(int i = 0 ;i < 10 ; i++) if( f[i]!=g[i] ) return -1;
29     return v;
30 }
31 void dfs(int cur, ll sum)
32 {
33     ll res = ck(sum);
34     if(sum>N) return ;
35     if(res!=-1) ans[c++] = res; 
36     for(int i = cur ; i >= 0 ; i-- )
37     {
38         if(sum==0&&i==0) continue;
39         dfs(i,sum*10+i);
40     }
41 }
42 int main()
43 {
44     a[0] = a[1] = 1;
45     for(int i = 2 ; i < 10 ; i++)
46         a[i] = a[i-1]*i;
47     c = 0;
48     dfs(9,0);
49     sort(ans,ans+c);
50     for(int i = 1 ; i < c ; i++)
51         printf("%lld
",ans[i]);
52     return 0;
53 }

其实得到输出结果后可以直接打表:

 1 #include <cstdio>
 2 using namespace std;
 3 int main()
 4 {
 5     puts("1");
 6     puts("2");
 7     puts("145");
 8     puts("40585");
 9     return 0;
10 }