第 91 场双周赛

Date: 2022-11-13

A 不同的平均值数目

将其转换为 set 会更好写

C++

class Solution {
public:
    int distinctAverages(vector<int>& nums) {
        unordered_map<double, int> mp;
        multiset<int> st(nums.begin(), nums.end());
        while (st.size() > 0) {
            int sum = *st.begin() + *st.rbegin();
            st.erase(st.begin());
            st.erase(prev(st.end()));
            mp[1.0 * sum / 2]++;
        }
        return mp.size();
    }
};

复杂度分析

时间复杂度：\(O(n\log n)\)
空间复杂度：\(O(n)\)

B 统计构造好字符串的方案数

DP，设 \(d[i]\) 为构造长度为 \(i\) 的字符串的方案数，转移：

\[d[i] = d[i - zero] + d[i - one]\]

C++

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        const int MOD = 1E9 + 7;
        vector<int> d(high + 1);
        d[0] = 1;
        int res = 0;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) {
                d[i] += d[i - zero];
            }
            if (i >= one) {
                d[i] += d[i - one];
            }
            d[i] %= MOD;
            if (i >= low) {
                res = (res + d[i]) % MOD;
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

C 树上最大得分和路径

首先通过 DFS，计算出 Bob 到达每个点的时间 \(t\)，然后从 \(0\) 开始，模拟 Alice 的决策。

每次 Alice 到达一个点 \(x\)，如果 \(x\) 不会被 Bob 经过，或者 Alice 经过的时间要比 Bob 早，那么 Alice 获得这个点的全部权值。但如果两个人到达的时间相同，那么 Alice 获得一半收益。

之后，还要考虑 \(x\) 的每个子节点 \(y\)，尝试 DFS 求出每个 \(y\) 的最大收益，从中选择一个最大的即可。

C++

class Solution {
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        int n = edges.size() + 1;
        vector<vector<int>> g(n);
        for (auto &v : edges) {
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }
        vector<int> fa(n), t(n, -1);

        function<void(int, int)> dfs = [&](int x, int f) {
            fa[x] = f;
            for (auto &y : g[x]) {
                if (y == f) continue;
                dfs(y, x);
            }
        };
        dfs(0, -1);

        int p = bob;
        for (int i = 0; p != -1; i++, p = fa[p]) {
            t[p] = i;
        }

        function<int(int, int, int)> get = [&](int x, int f, int time) {
            int res = 0;
            if (t[x] == -1 || t[x] > time) {
                res += amount[x];
            } else {
                if (t[x] == time) {
                    res += amount[x] / 2;
                }
            }

            // 如果没有孩子，那么需要直接返回答案
            if (g[x].size() == 1 && g[x][0] == f) {
                return res;
            }
            // 这里由于收益可能是负数，所以 buf 初始化为负无穷
            int buf = INT_MIN; 
            for (auto &y : g[x]) {
                if (y == f) continue;
                buf = max(buf, get(y, x, time + 1));
            }
            return res + buf;
        };
        return get(0, -1, 0);
    }
};

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

D 根据限制分割消息

这题是一个大模拟，如果遍历每种分段个数 \(cnt\)，那么可以在 \(O(1)\) 的时间内知道 \(cnt\) 段最多可以容纳几个字符。

对于最终包含 \(cnt\) 段的情况，因为要以 \(<i/cnt>\) 的格式加一个后缀，而 \(i\) 的长度随着位数变化而变化。由于 \(cnt\) 最多到 10000，我们可以直接枚举 \(i\) 的长度，来计算 \(cnt\) 最多容纳的字符数。

C++

class Solution {
public:
    vector<string> splitMessage(string s, int limit) {
        int n = s.size();
        auto check = [&](int cnt) {
            int suf_len = to_string(cnt).size() + 3;
            int sum = 0, base = 10;
            for (int i = 1; i <= 4; i++, base *= 10) {
                int num = min(base - 1, cnt) - (base / 10 - 1);
                if (num < 0) break;
                int partial_len = max(0, limit - suf_len - i);
                sum += partial_len * num;
            }
            return sum >= s.size();
        };

        auto get = [&](int cnt) {
            vector<string> res;
            for (int i = 1, j = 0; i <= cnt; i++) {
                char suf[20];
                sprintf(suf, "<%d/%d>", i, cnt);
                string suf_s(suf);
                int rlen = min(limit - suf_s.size(), s.size() - j);

                res.push_back(s.substr(j, rlen) + suf_s);
                j += rlen;
            }
            return res;
        };
        for (int i = 1; i <= n; i++) {
            if (check(i)) {
                return get(i);
            }
        }
        return {};
    }
};

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

本文访问次