分析：我们可以看出这道题目的描述并不是很复杂，就是说对于一个给定的整数n，我们能否把他拆成k个powerful的数，也就是说这k个数要么是2的幂次，要么是某个数的阶乘，并且我们要让当前的k越小越好；然后如果不能被拆的话输出-1；
我们这样来看，先看会不会输出-1，我们如果把这个整数n用二进制的方法写出来，每个1都表明可以写成某个powerful的数，所以不可能输出-1；
那么我们就可以发现了k的个数就是这里二进制表示中1的个数，但是我们考虑到还有阶乘，我们令阶乘的和为s，个数为cnt，则k = cnt + F(n-s)，这里的F函数就是根据二进制找1；
既然这样我们就可以枚举每个阶乘的可能性，我们发现14！已经是最大的可能了，因为15！就已经超过了1^12的数据范围，并且我们可以发现1！和2！是不需要考虑的，因为他们和幂次是一换一的关系没有必要，所以最多只需要枚举2^12次，找到最小值即可！
那么这里的关键是在于我怎么把这么多种可能枚举出来呢，很显然不适合用dfs，所以我们这里枚举i为0~1<
代码：
-
include
-
define INF 1100000000
- using namespace std ;
- typedef long long LL ;
- typedef pair
PII ; - LL fa [20 ],n ;
- int k =INF ;
- int find (LL x ){
- int cnt =0 ;
- while (x ){
- cnt +=x &1 ;
- x >>=1 ;
- }
- return cnt ;
- }
- int main ()
- {
- int t ;
- cin >>t ;
- fa [1 ]=1 ;
- fa [2 ]=2 ;
- for (int i =3 ;i
- while (t –){
- k =1100000000 ;
- cin >>n ;
- for (int i =0 ;i
- int cnt =0 ;
- LL s =0 ;
- for (int j =0 ;j
- if (i &(1 <<j )){
- cnt ++;
- s +=fa [j +3 ];
- }
- }
- if (s >n )continue ;
- k =min (k ,cnt +find (n -s ));
- }
- cout <<k <<‘\n’;
- }
- return 0 ;
- }
Original: https://www.cnblogs.com/ZheyuHarry/p/16102176.html
Author: ZheyuHarry
Title: Factorials and Powers of Two
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583604/
转载文章受原作者版权保护。转载请注明原作者出处！