第 88 场双周赛

比赛链接

A 有效时间的数目

枚举每个 ?，计算总方案数。

C++

class Solution {
public:
    int countTime(string t) {
        int res = 1;
        if (t[0] == '?') {
            if (t[1] == '?') {
                res = 24;
            } else {
                if (t[1] <= '3') {
                    res = 3;
                } else {
                    res = 2;
                }
            }
        } else if (t[1] == '?') {
            if (t[0] == '2') {
                res = 4;
            } else {
                res = 10;
            }
        }
        if (t[3] == '?') res *= 6;
        if (t[4] == '?') res *= 10;
        return res;
    }
};

但这种方法不够优雅，可以直接枚举 24*60 个时间，判断每个时间是否与给定时间符合格式上的要求。

C++

class Solution {
public:
    int countTime(string time) {
        int res = 0;
        auto get = [&](int h, int m) {
            char t[10];
            sprintf(t, "%02d:%02d", h, m);
            string s(t);
            for (int k = 0; k < 5; k++) {
                if (time[k] != s[k] && time[k] != '?') {
                    return false;
                }
            }
            return true;
        };
        for (int h = 0; h < 24; h++) {
            for (int m = 0; m < 60; m++) {
                if (get(h, m)) {
                    res++;
                }
            }
        }
        return res;
    }
};

B 二的幂数组中查询范围内的乘积

将 n 进行二进制分解，然后暴力枚举即可。

C++Python

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> p;
        for (int i = 0; i <= 30; i++) {
            if (n >> i & 1) {
                p.push_back(1 << i);
            }
        }
        vector<int> ret;
        constexpr int MOD = 1E9 + 7;
        for (int i = 0; i < queries.size(); i++) {
            int l = queries[i][0], r = queries[i][1];
            int res = 1;
            for (int j = l; j <= r; j++) {
                res = 1ll * res * p[j] % MOD;
            }
            ret.push_back(res);
        }
        return ret;
    }
};

class Solution:
def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
    p = []
    for i in range(31):
        if n >> i & 1:
            p.append(1 << i)
    ret = []
    mod = 10**9 + 7
    for l, r in queries:
        res = 1
        for i in range(l, r + 1):
            res = res * p[i] % mod
        ret.append(res)
    return ret

C 最小化数组中的最大值

二分，单次判断时，累计前面可以 +1 的次数，去补齐当前的数字，如果补不齐，返回 false。

C++

class Solution {
public:
    using ll = long long;
    int minimizeArrayValue(vector<int>& nums) {
        ll l = 0, r = 1E9;
        auto check = [&](int m) {
            ll pre = 0;
            for (auto x : nums) {
                if (x <= m) {
                    pre += m - x;
                } else {
                    if (pre >= x - m) {
                        pre -= x - m;
                    } else {
                        return false;
                    }
                }
            }
            return true;
        };
        while (l < r) {
            int m = l + r >> 1;
            if (check(m)) r = m;
            else l = m + 1;
        }
        return l;
    }
};

D 创建价值相同的连通块

\(n\) 个点的权值和最大为 \(10^6\)，写个程序判断可得 \([1,10^6]\) 范围内拥有最多因数的最多有 100 个左右。因此我们枚举每一个因子 \(x\)，去判断是否有一种方案可以让树分割为若干个权值和为 \(x\) 的连通块。

树分块，随便一个根开始递归，遍历每个子树，返回每个子树分完若干个 \(x\) 之后剩下的权值和 \(remain\)，将所有的 \(remain\) 加起来，再算上根自己的权值，如果恰好可以分一个 \(x\) 就再分一个，如果小于 \(x\)，则返回递归，如果大于 \(x\)，则说明无解。

C++

class Solution {
public:
    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        vector<vector<int>> g(n);
        for (auto& v : edges) {
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }
        function<pair<int, int>(int, int, int)> dfs = [&](int x, int fa, int sum) {
            int par = nums[x], res = 0;
            for (auto &y : g[x]) {
                if (y == fa) continue;
                auto t = dfs(y, x, sum);
                res += t.first, par += t.second;
            }
            if (par == sum) {
                res++;
                par = 0;
            }
            return make_pair(res, par);
        };
        auto get = [&](int sum) {
            auto ret = dfs(0, -1, sum);
            if (ret.second == 0) {
                return ret.first;
            } else {
                return 0;
            }
        };
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int res = 0;
        for (int i = 1; i * i <= sum; i++) {
            if (sum % i == 0) {
                res = max(res, get(i));
                if (sum / i != i)
                    res = max(res, get(sum / i));
            }
        }
        return res - 1;
    }
};

本文访问 次