2023‐08‐06 第 357 场周赛

故障键盘

• 日常模拟

class Solution {
public:
    string finalString(string s) {
        string res = "";
        
        for (auto c : s) {
            if (s.size() != 0 && c == 'i') reverse(res.begin(), res.end());
            
            else res.push_back(c);
        }
        
        return res;
    }
};

判断是否能拆分数组

• 这道题本来想用贪心的思路做的 但是没做出来 不知道是不是自己思路问题

class Solution {
public:
    bool canSplitArray(vector<int>& nums, int m) {
        // 无法排序
        int sum = accumulate(nums.begin(), nums.end(), 0);
        
        int l = 0, r = nums.size() - 1;
        
        while (l < r - 1) { // 只要最后剩两位
            
            if (sum - nums[l] >= m && sum - nums[r] >= m) { // 如果两者都行
                // 弹出最小的
                if (nums[l] > nums[r]) l ++, sum -= nums[l];
                
                else r --, sum -= nums[r];
                
            } else if (sum - nums[l] >= m) { // 左边满足
                // 弹出左边的
                l ++, sum -= nums[l];
                
            } else if (sum - nums[r] >= m) { // 右边满足
                
                r --, sum -= nums[r];
                
            } else return false;
             
        }
        
        
        return true;
    }
};

• 传送门
• ?????
• 脑筋急转弯？这么简单
• 思路确实恐怖如斯

class Solution {
public:
    bool canSplitArray(vector<int> &nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; i++)
            if (nums[i - 1] + nums[i] >= m)
                return true;
        return false;
    }
};

找出最安全的路径

• 这个题说实话 题目没看懂
• 这描述让人一脸懵逼
• 没发下手
• 但是看题解好像不是那么好做的

class Solution {
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int maximumSafenessFactor(vector<vector<int>> &grid) {
        int n = grid.size();
        vector<pair<int, int>> q;
        vector<vector<int>> dis(n, vector<int>(n, -1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    q.emplace_back(i, j);
                    dis[i][j] = 0;
                }
            }
        }

        vector<vector<pair<int, int>>> groups = {q};
        while (!q.empty()) { // 多源 BFS
            vector<pair<int, int>> nq;
            for (auto &[i, j]: q) {
                for (auto &d: dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (0 <= x && x < n && 0 <= y && y < n && dis[x][y] < 0) {
                        nq.emplace_back(x, y);
                        dis[x][y] = groups.size();
                    }
                }
            }
            groups.push_back(nq); // 相同 dis 分组记录
            q = move(nq);
        }

        // 并查集模板
        vector<int> fa(n * n);
        iota(fa.begin(), fa.end(), 0);
        function<int(int)> find = [&](int x) -> int { return fa[x] == x ? x : fa[x] = find(fa[x]); };

        for (int ans = (int) groups.size() - 2; ans > 0; ans--) {
            for (auto &[i, j]: groups[ans]) {
                for (auto &d: dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (0 <= x && x < n && 0 <= y && y < n && dis[x][y] >= dis[i][j])
                        fa[find(x * n + y)] = find(i * n + j);
                }
            }
            if (find(0) == find(n * n - 1)) // 写这里判断更快些
                return ans;
        }
        return 0;
    }
};