第 322 场周赛

Date: 2022-12-04

A 回环句

python 快乐题

C++ 没有 split 只能手写了。但是，由于题目输入比较规范，直接找空格判断两边也可以。

C++Python

class Solution {
public:
    bool isCircularSentence(string sentence) {
        if (sentence.back() != sentence.front()) {
            return false;
        }
        for (int i = 0; i < sentence.size(); i++) {
            if (sentence[i] == ' ' && sentence[i + 1] != sentence[i - 1]) {
                return false;
            } 
        }
        return true;
    }
};

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        s = sentence.split()
        for i in range(1, len(s)):
            if s[i][0] != s[i - 1][-1]:
                return False
        return s[-1][-1] == s[0][0]

复杂度分析

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

B 划分技能点相等的团队

排序后，一定是一一对应的。因为每个玩家都必须配对，并且和是一样的，那么必然头和尾一一对应。

比赛时傻了，还想着用 map。

C++Python

class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        int sum = accumulate(skill.begin(), skill.end(), 0);
        int n = skill.size(), m = n / 2;
        if (sum % m != 0) {
            return -1;
        }
        sort(skill.begin(), skill.end());
        int i = 0, j = n - 1, s = sum / m;
        long long res = 0;
        while (i < j) {
            if (skill[i] + skill[j] != s) return -1;
            res += skill[i] * skill[j];
            i++;
            j--;
        }
        return res;
    }
};

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        s = sum(skill)
        n = len(skill)
        m = n / 2
        if s % m:
            return -1
        skill.sort()
        i, j = 0, n - 1
        partial = s / m
        res = 0
        while i < j:
            if skill[i] + skill[j] != partial:
                return -1
            res += skill[i] * skill[j]
            i += 1
            j -= 1
        return res

复杂度分析

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

C 两个城市间路径的最小分数

注意到，这个路径中可以多次包含同一条道路，并不是我们常见的简单路径。所以，在 \(1\) 和 \(n\) 号点的联通分量中，那个最短的边一定可以被选到。

直接 BFS 或者 DFS，找到这个最短的边即可。

C++

class Solution {
public:
    using PII = pair<int, int>;
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<PII>> g(n + 1);
        for (auto &v : roads) {
            g[v[0]].push_back({v[1], v[2]});
            g[v[1]].push_back({v[0], v[2]});
        }
        vector<int> v(n + 1);
        int res = INT_MAX;
        function<void(int)> dfs = [&](int x) {
            if (v[x]) return;
            v[x] = 1;
            for (auto &t : g[x]) {
                res = min(res, t.second);
                dfs(t.first);
            }
        };
        dfs(1);
        return res;
    }
};

复杂度分析

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

D 将节点分成尽可能多的组

这个题稍有难度，但是细分下来每个点并不难。

首先点数 500 个，枚举每个点作为第一层，BFS 求解最多可以有多少层。过程中如果有拌脚的要返回 -1。

然后对于一个连通分量中的点，找到它们答案的最大值。当然也有可能所有点的答案都是 -1，那么整体就是 -1。说明无解。但是，只要有一个不是 -1，这一组连通分量就有答案。

然后对于所有的连通分量，单独求解，若有一个连通分量无解，则整体无解。否则将所有连通分量的答案加起来就是整体的答案。

C++

class Solution {
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        vector<int> v(n + 1);
        vector<vector<int>> g(n + 1);
        for (auto &v : edges) {
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }

        // 求解以 x 为出发点的最大层次
        auto gao = [&](int x) {
            vector<int> d(n + 1);
            d[x] = 1;
            queue<int> q;
            q.push(x);
            int res = 1;
            while (q.size()) {
                int x = q.front(); q.pop();
                res = max(res, d[x]);
                for (auto &y : g[x]) {
                    if (d[y] == 0) {
                        d[y] = d[x] + 1;
                        q.push(y);
                    } else {
                        if (abs(d[y] - d[x]) != 1) {
                            return -1;
                        }
                    }
                }
            }
            return res;
        };

        vector<int> ret(n + 1);
        for (int i = 1; i <= n; i++) {
            ret[i] = gao(i);
        }

        int res = 0, cur = -1;
        // 遍历每个连通分量
        function<void(int)> dfs = [&](int x) {
            if (v[x]) return;
            v[x] = 1;
            if (ret[x] != -1) {
                if (cur == -1 || cur < ret[x]) {
                    cur = ret[x];
                }
            }
            for (auto &y : g[x]) dfs(y);
        };
        for (int i = 1; i <= n; i++) {
            if (v[i]) continue;
            cur = -1;
            dfs(i);
            if (cur == -1) return -1;
            res += cur;
        }
        return res;
    }
};

复杂度分析

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

赛后小节，T1如果会 python 的话直接模拟会快一些，不需要动脑子。听说有人用其他语言写 wa 了，想不到 wa 在那里。T2 的话要及时想到一一对应的关系，会好写很多。T3 是脑筋急转弯，其实样例二给了提示。T4 需要大胆一些，再就是码力了。

这次发挥一般，由于一个多月快两个月周内没有刷过题了，所以速度直线下滑。

本文访问次