第 364 场 LeetCode 周赛题解

A 最大二进制奇数

降序排序字符串，然后将最后一个 1 与最后一位交换

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        sort(s.begin(), s.end(), greater<>());
        for (int i = s.size() - 1;; i--)
            if (s[i] == '1') {
                swap(s[i], s.back());
                break;
            }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

---

B 美丽塔 I

枚举： 枚举山状数组的最大值的下标 $i$，然后遍历两端 $[0,i)$ 和 $(i,n-1]$ ，求各位置能达到的最大高度

class Solution {
public:
    using ll = long long;

    long long maximumSumOfHeights(vector<int> &maxHeights) {
        int n = maxHeights.size();
        ll res = 0;
        for (int i = 0; i < n; i++) {
            ll cur = maxHeights[i];
            for (int j = i - 1, last = maxHeights[i]; j >= 0; j--) {
                last = min(last, maxHeights[j]);
                cur += last;
            }
            for (int j = i + 1, last = maxHeights[i]; j < n; j++) {
                last = min(last, maxHeights[j]);
                cur += last;
            }
            res = max(res, cur);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

C 美丽塔 II

单调栈+枚举：设 $l[i]$ 为当 $heights[i]=maxHeights[i]$ 时 ${\sum }_{k=0}^{i}heights[k]$ 的最大值，类似地设 $r[i]$ 为当 $heights[i]=maxHeights[i]$ 时 ${\sum }_{k=i}^{heights.size()-1}heights[k]$ 的最大值，用单调栈预先求出 $l$ 和 $r$ 数组，答案即为： m a x { l [ i ] + r [ i ] − m a x H e i g h t s [ i ]    ∣    0 ≤ i < n } max\{ l[i]+r[i]-maxHeights[i] \; | \; 0\le i< n \} max{l[i]+r[i]−maxHeights[i]∣0≤i<n}

class Solution {
public:
    using ll = long long;

    long long maximumSumOfHeights(vector<int> &maxHeights) {
        int n = maxHeights.size();
        vector<ll> l(n), r(n);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && maxHeights[st.top()] > maxHeights[i])//栈顶位置最大高度大于当前位置最大高度则需要出栈
                st.pop();
            l[i] = st.empty() ? 1LL * (i + 1) * maxHeights[i] : l[st.top()] + 1LL * (i - st.top()) * maxHeights[i];
            st.push(i);
        }
        st = stack<int>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && maxHeights[st.top()] > maxHeights[i])//栈顶位置最大高度大于当前位置最大高度则需要出栈
                st.pop();
            r[i] = st.empty() ? 1LL * (n - i) * maxHeights[i] : r[st.top()] + 1LL * (st.top() - i) * maxHeights[i];
            st.push(i);
        }
        ll res = 0;
        for (int i = 0; i < n; i++)
            res = max(res, l[i] + r[i] - maxHeights[i]);
        return res;
    }
};
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

---

D 统计树中的合法路径数目

计数+ $dfs$：设一个质数点 $root$ 的 $v$ 集合为： { 从 u 出发只通过非质数点能到达的非质数点的数目 ∣ u 是 r o o t 的邻接点 } \{ 从u出发只通过非质数点能到达的非质数点的数目 | u是root的邻接点 \} {从u出发只通过非质数点能到达的非质数点的数目∣u是root的邻接点}，例如下图中 $root$ 的 $v$ 集合为 { 1 , 2 , 3 } \{1,2,3 \} {1,2,3}。

知道 $root$ 的 $v$ 集合后，则树中含 $root$ 的合法路径可分为两类：

1. 一个端点为 $root$ 的路径，这类路径数为：${\sum }_{v_i\in v}{v}_i$
2. 两个端点都不为 $root$ 的路径，这类路径数为： $\frac{1}{2}{\sum }_{v_i\in v}{\sum }_{j\ne i}{v}_i{v}_j=\frac{1}{2}\left(({\sum }_{v_i\in v}{v}_i{)}^2-{\sum }_{v_i\in v}{v}_i^2\right)$

不妨以 $1$ 为树根，首先通过 $dfs$ 计算 $cnt\_np$ 数组：$cnt\_np[i]$ 为以 $i$ 为根的子树中从 $i$ 出发只通过非质数点能到达的非质数点的数目。然后再次 $dfs$ ，并在遍历过程中记录“从当前节点的父节点出发(且不经过当前节点)只通过非质数点能到达的非质数点的数目”，这样每到达一个质数点，就能求出它的 $v$ 集合，从而计算含该点的合法路径数。

class Solution {
public:
    using ll = long long;

    long long countPaths(int n, vector<vector<int>> &edges) {
        vector<int> isp(n + 1, 1);//isp[i]:i是否是质数
        isp[1] = 0;
        for (int i = 2; i <= n; i++) {//预处理判断数是否是质数
            for (int j = 2; j * j <= i; j++)
                if (i % j == 0) {
                    isp[i] = 0;
                    break;
                }
        }
        vector<vector<int>> e(n + 1);
        for (auto &ei: edges) {//建图
            e[ei[0]].push_back(ei[1]);
            e[ei[1]].push_back(ei[0]);
        }
        vector<ll> cnt_np(n + 1);//以i为根的子树中从i出发只通过非质数点到达的非质数点的数目
        function<int(int, int)> comp_path = [&](int root, int p) {//当前点为root,父节点为p
            if (isp[root]) {//当前点为质数点
                cnt_np[root] = 0;
                for (auto j: e[root])
                    if (j != p)
                        comp_path(j, root);
            } else {//当前点非质数点
                cnt_np[root] = 1;
                for (auto j: e[root])
                    if (j != p)
                        cnt_np[root] += comp_path(j, root);
            }
            return cnt_np[root];
        };
        comp_path(1, 0);
        ll res = 0;
        function<void(int, int, int)> dfs = [&](int root, int p, int up) {//当前点为root,父节点为p,up:从p出发(且不经过当前节点)只通过非质数点能到达的非质数点的数目
            if (isp[root]) {//当前点为质数点
                vector<ll> v;// v集合
                if (up != 0)
                    v.push_back(up);
                for (auto j: e[root])
                    if (j != p) {
                        dfs(j, root, 0);
                        if (cnt_np[j])
                            v.push_back(cnt_np[j]);
                    }
                ll s = 0, s2 = 0;
                for (auto it: v) {
                    s += it;
                    s2 += it * it;
                }
                res += s + (s * s - s2) / 2;//+=含当前质数点的合法路径数目

            } else {//当前点非质数点
                ll s = up + 1;
                for (auto j: e[root])
                    if (j != p && cnt_np[j])
                        s += cnt_np[j];
                for (auto j: e[root])
                    if (j != p)
                        dfs(j, root, s - cnt_np[j]);
            }
        };
        dfs(1, 0, 0);
        return res;
    }
};
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
64
65
66
67
68