Skip to content

第 330 场周赛

比赛链接

Date: 2023-01-29

千载难遇两 hard ，红红火火过大年

A 统计桌面上的不同数字

如果桌面上有 \(x\)，那么下一次 \(x - 1\) 一定会出现，因为 \(x \mod (x-1) = 1\)

1
2
3
4
5
6
7
class Solution {
public:
    int distinctIntegers(int n) {
        if (n == 1) return 1;
        return n - 1;
    }
};

1
2
3
class Solution:
    def distinctIntegers(self, n: int) -> int:
        return n - 1 if n > 1 else n

复杂度分析

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

B 猴子碰撞的方法数

如果 \(n\) 个猴子都往一个方向转，就不会发生碰撞，其余情况都会。所以答案为 \(2^n - 2\)。使用快速幂计算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    static constexpr int mod = 1E9 + 7;
    int ksm(int a, int b) {
        int res = 1;
        for (;b; b >>= 1) {
            if (b & 1) {
                res = 1ll * res * a % mod;
            }
            a = 1ll * a * a % mod;
        }
        return res;
    }
    int monkeyMove(int n) {
        int res = ksm(2, n);
        res = ((res - 2) % mod + mod) % mod;
        return res;
    }
};

复杂度分析

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

C 将珠子放入背包中

假设 \(k = n\)，那么背包价格之和固定为 \(2\sum_i \textit{weights}[i]\)。如果 \(k\) 变为 \(n - 1\)，那么相当于从中选择一对 \(\textit{weights}[i] + \textit{weights}[i + 1]\) 删去。

依次类推，每次 \(k\) 减小 \(1\)，都等价于找到一组 \(\textit{weights}[i] + \textit{weights}[i + 1]\) 删去。所以我们提前将这 \(n - 1\) 个相邻价值对排好序，贪心求解即可。

 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:
    using ll = long long;
    long long putMarbles(vector<int>& weights, int k) {
        int n = weights.size();
        vector<int> a;
        ll res = 0;
        for (int i = 0; i < n; i++) {
            res += weights[i] + weights[i];
            if (i + 1 < n) {
                a.push_back(weights[i] + weights[i + 1]);
            }
        }
        sort(a.begin(), a.end());
        ll mi = res, mx = res;
        for (int i = 0; i < n - k; i++) {
            mx -= a[i];
            mi -= a[a.size() - i - 1];
        }
        return mx - mi;
    }
};

复杂度分析

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

D 统计上升四元组

四元组 \((i, j, k, l)\)，需满足条件 \(\textit{nums}[i] < \textit{nums}[k] < \textit{nums}[j] < \textit{nums}[l]\)。

对于每个 \(l\)，求解前面有多少个 \(j\) 满足 \(\textit{nums}[i] < \textit{nums}[k] < \textit{nums}[j]\) 即可。

从小到大遍历 \(k\)，然后在从小到大遍历 \(j\)，过程中记录前面有多少个小于 \(\textit{nums}[k]\) 的元素，这样即可对于每个 \(j\) 求出所组成的三元组 \((i, j, k)\) 的个数。

 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:
    using ll = long long;
    long long countQuadruplets(vector<int>& nums) {
        int n = nums.size();
        vector<ll> d2(n);
        ll res = 0;
        for (int i = 2; i < n; i++) {
            int les = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) {
                    d2[j] += les;
                }
                if (nums[j] < nums[i]) {
                    les++;
                    res += d2[j];
                }
            }
        }
        return res;
    }
};

复杂度分析

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