拼多多算法笔试

第四题可以二分优化一下，否则会超时

ac100%思路： 面为 1 ~ i - 1 的所有组合 ， 即 (i-1) ^ n种 ，相应的 1 ~ i的所有组合 有 （i）^n种，所以最大面出现的组合数为i^n - (1-i)^n, n = int(input()) Xi_lst = list(map(int, input().split())) pre = 0 ans = 0 max_num = max(Xi_lst) for i in range(1,max_num+1): now = 1 for j in Xi_lst: if j > i: now *= (i/j) ans += (now-pre) *i pre = now print('%.2f'%ans) 参考： http://codeforces.com/problemset/problem/453/A https://www.cnblogs.com/chaiwenjun000/p/5321135.html

三四都不会，GG

第三题 看半天看不懂题目

1×1/4＋2×3/4

第三题 组合数 #include <iostream> #include <vector> using namespace std; long long C[51][51] = {0}; void GetC(int maxn) {     C[0][0] = 1;     for(int i = 1; i <= maxn; ++i) {         C[i][0] = 1;         for(int j = 1; j <= i; ++j){             C[i][j] = C[i-1][j]+C[i-1][j-1];         }     } } double getNum(const int *arr, const int n, const int maxNum) {     int gE = 0;     double less = 1.0;     double ret = 0.0;     for(int i = 0; i < n; ++i) {         if(arr[i] >= maxNum) gE++;         else less *= arr[i];     }     for(int k = 1; k <= gE; ++k) {         double cn = C[gE][k];         double tP = 1.0;         for(int i = 0; i < gE - k; ++i) {             tP = tP * (maxNum - 1);         }         ret = ret + cn * tP * less;     }     return ret; } int main(){     int n = 0;     int maxNum = 0;     double fengmu = 1.0;     double fengzhi = 1.0;     double ans = 1.0;     int arr[55] = {0};     cin >> n;     GetC(n);     for(int i = 0; i < n; ++i) {         cin >> arr[i];         fengmu *= arr[i];         if(arr[i] > maxNum) maxNum = arr[i];     }     for(int i = 2; i <= maxNum; ++i) {         fengzhi = fengzhi + i * getNum(arr, n, i);     }     ans = fengzhi/fengmu;     printf("%.2lf\n", ans);     return 0; } 第四题思路应该是对于i , j 坐标求 大于该数的个数，没时间写了

骰子可以用动态规划吧，先将Xi数组从小到大排列，当前状态等于当前取值比上一个的概率乘以对应值，然后加上1-该概率乘以上一个状态的期望。。

我第一题只0.4不知道为啥。。第二题没看，第三题放弃，第四题应该是两数组相乘，求乘积的第k大值，但我还是复杂度过高，0.9

楼主扑克牌做出来了？

第四题的优化我只能想到行n和列m相等的情况，可以算从1开始求和到大于k的时候，得到的一个值s，然后就是拿行号i和列号j的和等于m+n-s的数取出来sort，然后取s-k的数。行列不等的时候看不出来规律

第四题可以对(1,n*m)二分，每次O(n+m)的判断mid是第几大与K比较就可以啦