2 条题解

  • 3
    @ 2022-10-1 23:19:36

    阶乘之和 题解

    题目大意

    求正整数 nn 是否能分解为若干个阶乘之和

    思路分析

    直接暴力枚举。枚举10种状态,每种为选或不选。

    代码

    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #include <string>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #define IL inline
    using namespace std;
    const int N = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    
    int a[12] = {0,1,1,2,6,24,120,720,5040,40320,362880};
    bool used[11];
    
    bool f(int q)
    {
    	if(q == 0 || q > 409114) // 特判为0或超出范围
    		return false;
        //枚举10种状态,每种为选或不选。
    	for(int a1 = 0;a1 <= 1;a1++)
    		for(int a2 = 0;a2 <= 1;a2++)
    			for(int a3 = 0;a3 <= 1;a3++)
    				for(int a4 = 0;a4 <= 1;a4++)
    					for(int a5 = 0;a5 <= 1;a5++)
    						for(int a6 = 0;a6 <= 1;a6++)
    							for(int a7 = 0;a7 <= 1;a7++)
    								for(int a8 = 0;a8 <= 1;a8++)
    									for(int a9 = 0;a9 <= 1;a9++)
    										for(int a10 = 0;a10 <= 1;a10++)
    												if(q == (a1*a[1] +a2*a[2] +a3*a[3] +a4*a[4] +a5*a[5] +a6*a[6] +a7*a[7] +a8*a[8] +a9*a[9] +a10*a[10]))
    													return true;
    	return false;
    }
    
    
    int main()
    {
    	int x;
    	while(cin >> x && x >= 0)
    	{
    		f(x)?puts("YES"):puts("NO");
    	}
        return 0;
    }
    
    • 2
      @ 2022-10-1 11:21:31
      /***************************************
      Note:
      ***************************************/
      #include <iostream>
      #include <algorithm>
      #include <cstdio>
      #include <cstring>
      #include <string>
      #include <iomanip>
      #include <cmath>
      #include <queue>
      #include <map>
      #include <stack>
      #include <vector>
      #include <fstream>
      using namespace std;
      #define LL long long
      #define ULL unsigned long long
      #define ULLI unsigned long long int
      const int N = 1e6+6;
      int n;
      bool flag = 0;
      int a[10] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
      void dfs(int sum,int step){
      	if (sum > n) return;
      	if (sum == n) flag = 1;
      	if (step > 10) return;
      	dfs(sum+a[step],step+1);
      	dfs(sum,step+1);
      }
      int main(){
      	while (cin >> n and n >= 0){
              if (n == 0){
                  cout << "NO" << endl;
                  continue;
              }
      		dfs(0,0);
      		if (flag) cout << "YES";
      		else cout << "NO";
      		cout << endl;
      		flag = 0;
      	}
          return 0;
      }
      
      • 1

      信息

      ID
      2827
      时间
      1000ms
      内存
      256MiB
      难度
      7
      标签
      递交数
      57
      已通过
      13
      上传者