Skip to content

第 313 场周赛

比赛链接

Date: 2022-10-02

A 公因子的数目

暴力判断即可，复杂度 \(O(min(a, b))\)。

如果 \(a, b\) 范围很大，可以先分解质因数，复杂度 \(O(\sqrt {a} + \sqrt {b})\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int commonFactors(int a, int b) {
        int res = 0;
        for (int i = 1; i <= min(a, b); i++) {
            if (a % i == 0 && b % i == 0) {
                res ++;
            }
        }
        return res;
    }
};

1
2
3
class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        return sum([1 if a % i == 0 and b % i == 0 else 0 for i in range(1, min(a, b) + 1)])

B 沙漏的最大总和

暴力遍历即可，这种题用 Python 更好写。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxSum(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        int res = 0;
        for (int i = 0; i + 2 < n; i++) {
            for (int j = 0; j + 2 < m; j++) {
                res = max(res, g[i][j] + g[i][j + 1] + g[i][j + 2] + g[i + 1][j + 1] + g[i + 2][j] + g[i + 2][j + 1] + g[i + 2][j + 2]);
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
class Solution:
    def maxSum(self, g: List[List[int]]) -> int:
        n, m = len(g), len(g[0])
        res = 0
        for i in range(n - 2):
            for j in range(m - 2):
                res = max(res, sum(g[i][j : j + 3]) + g[i + 1][j + 1] + sum(g[i + 2][j : j + 3]))
        return res

C 最小 XOR

记 \(x\) 为 num2 中 1 的个数，我们会把这些 1 优先放到 num1 中的高位 1 上去。

这样做的目的，是尽可能地让异或结果接近 0 。

如果放完了还有剩余，则从低位开始放多余的 1，这些 1 异或后仍会是 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
class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int x = 0;
        for (int i = 0; i < 31; i++) {
            if (num2 >> i & 1) {
                x++;
            }
        }
        int res = 0;
        for (int i = 30; i >= 0; i--) {
            if (num1 >> i & 1) {
                if (x > 0) {
                    res |= 1 << i;
                    x--;
                }
            }
        }
        for (int i = 0; i <= 30; i++) {
            if (!(num1 >> i & 1) && x){
                res |= 1 << i;
                x--;
            }
        }
        return res;
    }
};

D 对字母串可执行的最大删除数

设 \(d[i]\) 为把 \(s[i:n]\) 的内容都删除掉的最大操作次数。那么在求解 \(d[i]\) 时，遍历每个 \(j\)，从 \(i + 1\) 开始，直到 \(n - j > j - i\) 结束。

转移时，如果有 \(s[i:j] == s[j:j+j-i]\) 则考虑 \(d[i] = max(d[i], d[j] + 1)\)。

初始化时，所有 \(d[i] = 1\)。

时间复杂度：\(O(n^3)\)，字符串判断是否相同可以使用字符串hash来加快。但对于 Python 来说直接对比字符串切片也可以通过本题，在 C++ 中可以使用 string_view。

class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        vector<int> d(n, 1);
        string_view ss = s;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; (j - i) <= (n - j); j++) {
                int len = j - i;
                if (ss.substr(i, len) == ss.substr(j, len)) {
                    d[i] = max(d[i], d[j] + 1);
                }
            }
        }
        return d[0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def deleteString(self, s: str) -> int:
        n = len(s)
        d = [1] * n
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n, 1):
                leng = j - i
                if j + leng > n:
                    break
                if s[i:j] == s[j:j+leng]:
                    d[i] = max(d[i], d[j] + 1)
        return d[0]
本文访问 次