锐客网

  1. 首页 > it技术 > >

Factorials|Factorials and Powers of Two

Factorials|Factorials and Powers of Two
文章图片




分析：我们可以看出这道题目的描述并不是很复杂，就是说对于一个给定的整数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次，找到最小值即可！
【Factorials|Factorials and Powers of Two】那么这里的关键是在于我怎么把这么多种可能枚举出来呢，很显然不适合用dfs，所以我们这里枚举i为0~1<<12,然后再去枚举j从0~11，看i&1<
代码：

  1. #include
  2. #define INF 1100000000
  4. using namespace std;
  5. typedef long long LL;
  6. typedef pair PII;
  7. LL fa[20],n;
  8. int k = INF;
  10. int find(LL x){
  11. int cnt = 0;
  12. while(x){
  13. cnt += x&1;
  14. x >>= 1;
  15. }
  16. return cnt;
  17. }
  19. int main()
  20. {
  22. int t;
  23. cin >> t;
  24. fa[1] = 1;
  25. fa[2] = 2;
  26. for(int i = 3; i<=14; i++) fa[i] = fa[i-1]*i;
  27. while(t--){
  28. k = 1100000000;
  29. cin >> n;
  30. for(int i = 0; i<(1<<12); i++){
  31. int cnt = 0;
  32. LL s = 0;
  33. for(int j = 0; j<=11; j++){
  34. if(i&(1<
  35. cnt++;
  36. s+=fa[j+3];
  37. }
  38. }
  39. if(s>n) continue;
  40. k = min(k,cnt + find(n - s));
  41. }
  42. cout << k << '\n';
  43. }
  44. return 0;
  45. }

    推荐阅读


    上一篇：流概述

    下一篇：面试官（Zookeeper怎么解决读写、双写并发不一致问题，以及共享锁的实现原理（））