第 191 场周赛

Posted on | In , | |
Words count in article: 569 | Reading time ≈ 3

1464. 数组中两元素的最大乘积

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<nums.size(); i++) {
            for(int j=i+1; j<nums.size(); j++) {
                res = max(res, (nums[i]-1) * (nums[j]-1));
            }
        }
        return res;
    }
};

1465. 切割后面积最大的蛋糕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        long long maxh = 0, maxw = 0;
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        long long  pre = 0;
        long long hh = h, ww = w;
        for(long long  h: horizontalCuts) {
            maxh = max(maxh, h-pre);
            pre = h;
        }
        maxh = max(hh-pre, maxh);
        pre = 0;
        for(long long  v: verticalCuts) {
            maxw = max(v-pre, maxw);
            pre = v;
        }
        maxw = max(ww-pre, maxw);
        return (int)(maxh*maxw %1000000007);
    }
};

1466. 重新规划路线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        set<int> st;
        st.insert(0);
        int res = 0;
        for(auto c: connections) {
            if(st.count(c[1])) {
                st.insert(c[0]);
            } else {
                res ++;
                st.insert(c[1]);
            }
        }
        return res;
    }
};

1467. 两个盒子中球的颜色数相同的概率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    vector<int> left, right, bas;
    int ln = 0, rn = 0;
    int alls = 0;
    double tot, ak;
    
    double fac(int a){   // 求阶乘
        double ans = 1;
        for(int i = 1; i <= a; i ++) ans *= i;
        return ans;
    }
    
    double get(vector<int>& bas){   // 求排列数
        int n = 0;
        for(auto x:bas) n += x;
        double ans = fac(n);
        for(auto x:bas) ans /= fac(x);
        return ans;
    }
    
    
    void dfs(int i){
        if(ln > alls / 2 || rn > alls / 2) return ;  // 剪枝
        if(i == left.size()){   // 叶子节点
            // for(auto x:left) cout << x << " ";
            // cout << endl;
            // for(auto x:right) cout << x <<" ";
            // cout << endl;
            int a = 0, b = 0;
            for(auto x:left){
                if(x) a ++;
            }
            for(auto x:right){
                if(x) b ++;
            }
            if(a == b)   // 两个箱子中的球的颜色种类相同
                ak += get(left) * get(right);
            return;
        }
        for(int j = 0; j <= bas[i]; j++){   // 枚举当前颜色球，左右箱子中的个数
            left[i] = j;    
            right[i] = bas[i] - j;
            ln += j;   // 记录两个箱子中球的总数，用于剪枝
            rn += bas[i] - j;
            dfs(i + 1);   // 递归调用
            ln -= j;   // 恢复现场
            rn -= bas[i] - j;
        }
    }
    
    double getProbability(vector<int>& balls) {
        
        bas = balls;
        left = vector<int>(balls.size(), 0);
        right = vector<int>(balls.size(), 0);
        tot = get(balls);   // 求分母
        for(auto x:balls) alls += x;   
        dfs(0);  // 求分子
        // cout << ak << " " << tot << endl;
        return ak / tot; 
    }
};
Donate? comment?