腾讯 的数字分解题

#include #include #include #include #include using namespace std; int a[100][100]; int F(int n,int m) { if(a[n][m]>0){ return a[n][m];//记忆搜索 } if(n==1) return a[1][m]=1; if(m==1) return a[n][1]=1; if(nm) return a[n][m]=F(n,m-1)+F(n-m,m); } int GD(int x) { int i; int count=0; for(i=1;i<=x/2;i++) { if(x%i==0) count++; } return count; } int main() { int n; while (scanf("%d",&n)!= EOF) { memset(a,-1,sizeof(a)); printf("%d\n",F(n,n)-GD(n)-1); } return 0; }

没参加笔试，只能想到o(nnlgn)的解法。不知道最后会不会超时。想法就是先求出完整排列的次数，然后去掉不符合题意的排列次数。完整排列的想法就是把整个排列看成是一个多项式。比如 7 = a*1+b*2+c*3+d*4+e*5+f*6+g*7 求这几个未知数的所有可能情况就行了。用动态规划来求。还有很多不同的解法：比如这个博客讲得非常细致。blog link，还有知乎大佬用公式直接求的. zhihu link 去掉不符合题意的答案，只要做 int tmp = dp[i][i]-1,tmp2 = i/2; for (int t = 1; t <= tmp2;t++) if (i%t == 0) tmp--; 因为题意可以看出，分解出来各项都相等的都不能算。所以只要去掉这些项就行了。 #include <stdio.h> #include <algorithm> #include <iostream> #include <stdlib.h> #include <string> #include <unordered_map> #include <vector> #include <math.h> #include <set> using namespace std; int main() { int dp[101][101]; for (int i = 0; i < 100;i++) for (int j = 0; j < 100; j++) dp[i][j] = 0; for (int i = 0; i < 100; i++){ dp[0][i] = 1; dp[i][0] = 1; dp[1][i] = 1; } for (int i = 2; i < 100; i++){ for (int j = 1; j < 100; j++){ for (int k = 0; k <= j; k += i){ dp[i][j] += dp[i - 1][j - k]; } } int tmp = dp[i][i]-1,tmp2 = i/2; for (int t = 1; t <= tmp2;t++) if (i%t == 0) tmp--; cout <<i<< ":" << tmp << endl; } return 0; } 当然，我觉得最暴力的解法就是先跑一遍上面的程序，然后把得到的结果直接保存为数组。 比如这样： int main(){ int res[100] = { 0,0,0, 1, 2, 5, 7, 13, 18, 27, 38, 54, 71, 99, 131, 172, 226, 295, 379, 488, 621, 788, 998, 1253, 1567, 1955, 2432, 3006, 3712, 4563, 5596, 6840, 8343, 10139, 12306, 14879, 17968, 21635, 26011, 31181, 37330, 44581, 53166, 63259, 75169, 89128, 105554, 124752, 147263, 173522, 204220, 239939, 281583, 329929, 386147, 451272, 526815, 614150, 715216, 831818, 966455, 1121503, 1300152, 1505493, 1741623, 2012554, 2323512, 2679687, 3087729, 3554341, 4087960, 4697203, 5392771, 6185687, 7089496, 8118258, 9289085, 10619859, 12132156, 13848648, 15796466, 18004322, 20506251, 23338467, 26543648, 30167353, 34262958, 38887669, 44108101, 49995923, 56634161, 64112355, 72533801, 82010173, 92669716, 104651415, 118114292, 133230928, 150198130, 169229869, }; int n; cin >> n; cout << res[n] << endl; return 0; }

什么题意？

我递归溢出了