Skip to content

第 357 场周赛

比赛链接

Date: 2023-08-06

A 故障键盘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    string finalString(string s) {
        string t = "";
        for (auto c : s) {
            if (c == 'i') {
                reverse(t.begin(), t.end());
            } else {
                t += c;
            }
        }
        return t;
    }
};

复杂度分析

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

B 判断是否能拆分数组

比赛时，使用了 DP，记 \(d[i][j]\) 表示区间 \((i, j)\) 能否拆分。

但其实只需要有任意一组连续两个数字之和大于等于 \(m\) 即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool canSplitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<int> sum(n + 1);
        vector<vector<int>> d(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
            d[i][i] = 1;
        }
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                for (int k = l; k < r; k++) {
                    d[l][r] = d[l][r] || (d[l][k] && d[k + 1][r] && (l == k || sum[k + 1] - sum[l] >= m) && (k + 1 == r || sum[r + 1] - sum[k + 1] >= m));
                }
            }
        }
        return d[0][n - 1];
    }
};

复杂度分析

  • 时间复杂度：\(O(n^3)\)
  • 空间复杂度：\(O(1)\)

C 找出最安全路径

很无脑的题，码量有点大。

 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
class Solution {
public:
    static constexpr int dir[4][2] = {
        {0, 1}, {0, -1}, {1, 0}, {-1, 0}
    };
    int maximumSafenessFactor(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> v(n, vector<int>(n, -1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 1) {
                    v[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        while (q.size()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (v[nx][ny] == -1) {
                    v[nx][ny] = v[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }

        auto check = [&](int mid) {
            queue<pair<int, int>> q;
            if (v[0][0] < mid) return false;
            q.push({0, 0});
            vector<vector<int>> vis(n, vector<int>(n, 0));
            while (q.size()) {
                auto [x, y] = q.front(); q.pop();
                if (x == n - 1 && y == n - 1) {
                    return true;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (v[nx][ny] >= mid && vis[nx][ny] == 0) {
                        q.push({nx, ny});
                        vis[nx][ny] = 1;
                    }
                }
            }
            return false;
        };

        int l = 0, r = n * m;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

复杂度分析

  • 时间复杂度：\(O(n^2\log n^2)\)。
  • 空间复杂度：\(O(n^2)\)。

D 子序列最大优雅度

我们先忽略种类数，只考虑 profit。那么我们会选择前 \(k\) 大的 item，种类数为 \(c\)。

我们会让种类数变得更少吗？并不，减少种类数必然会引入更低的 profit，并不能使答案更优。

那么如何让种类数变多？已选择的种类并不会被删除，只需要新增种类。新增种类的同时，需要去除旧种类中 profit 最低的（并且该种类个数必须大于 1）。

 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
class Solution {
public:
    using ll = long long;
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        int n = items.size();
        sort(items.begin(), items.end(), [&](vector<int>& lth, vector<int>& rth) {
            return lth[0] > rth[0];
        });
        vector<int> c(n);
        ll kind = 0;
        ll sum = 0;
        priority_queue<int, vector<int>, greater<int>> q;
        for (int i = 0; i < k; i++) {
            sum += items[i][0];
            c[items[i][1] - 1]++;
            if (c[items[i][1] - 1] == 1) {
                kind++;
            } else {
                q.push(items[i][0]);
            }
        }
        ll res = sum + kind * kind;
        for (int i = k; i < n; i++) {
            if (c[items[i][1] - 1] != 0 || q.size() == 0) {
                continue;
            }
            c[items[i][1] - 1]++;
            kind++;
            sum -= q.top(); q.pop();
            sum += items[i][0];
            res = max(res, sum + kind * kind);
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n\log n)\)。
  • 空间复杂度：\(O(n)\)。
本文访问 次