周赛 343 温习一下 Dijstra

plus2047 于 2023-04-30 发布

本周周赛难度不高，第三题温习一下 Dijstra, 第四题是一道比较奇葩的推理和构造题目。

weekly contest

1.

class Solution:
    def isWinner(self, player1: List[int], player2: List[int]) -> int:
        n = len(player1)
        s1 = s2 = 0
        for i in range(n):
            s1 += player1[i] * (2 if i > 0 and player1[i - 1] == 10 or i > 1 and player1[i - 2] == 10 else 1)
            s2 += player2[i] * (2 if i > 0 and player2[i - 1] == 10 or i > 1 and player2[i - 2] == 10 else 1)
        return 1 if s1 > s2 else 2 if s2 > s1 else 0

2.

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size(), s = arr.size();
        vector<int> row(s + 1), col(s + 1), cr(m), cc(n);
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                row[mat[i][j]] = i;
                col[mat[i][j]] = j;
            }
        }
        for(int i = 0; i < s; i++) {
            int r = row[arr[i]], c = col[arr[i]];
            if(++cr[r] == n or ++cc[c] == m) {
                return i;
            }
        }
        return -1;
    }
};

3.

不难想到，本题可以使用最短路算法求解。题目中一同提及了 start, target, 以及每条特殊路径的起止，这些节点。然后节点之间的距离就是两者之间的 L1 距离或者特殊路径长度。本题数据规模节点数量只有 400, 即使两两之间连接给出 N^2 条边也是可以求解的。

但是稍加推理不难发现，只有有限的几类边是有意义的，

void dijstra(vector<vector<pair<int, int>>>& g, vector<int>& dist, int start) {
    
    typedef pair<int, int> p;
    priority_queue<p, vector<p>, greater<p>> q;
    q.push({0, start});
    
    while(q.size()) {
        auto curr = q.top();
        q.pop();
        int d = curr.first, x = curr.second;
    
        if(dist[x] <= d) continue;
        dist[x] = d;
        
        for(auto child: g[curr.second]) {
            int dc = child.first, xc = child.second;
            if(dist[xc] > dc + d) {
                q.push({dc + d, xc});
            }
        }
    }
}

class Solution {
public:
    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& roads) {
        int n = 2 + roads.size() * 2;
        
        vector<vector<pair<int, int>>> g(n);
        g[0].push_back({cost(start[0], start[1], target[0], target[1]), n - 1});
        
        int m = roads.size();
        for(int i = 0; i < m; i++) {
            auto& r = roads[i];
            
            g[0].push_back({cost(start[0], start[1], r[0], r[1]), i * 2 + 1});
            g[i * 2 + 1].push_back({r[4], i * 2 + 2});
            g[i * 2 + 2].push_back({cost(r[2], r[3], target[0], target[1]), n - 1});
            
            for(int j = 0; j < m; j++) {
                if(i == j) continue;
                auto& rr = roads[j];
                g[i * 2 + 2].push_back({cost(r[2], r[3], rr[0], rr[1]), j * 2 + 1});
            }
        }
        
        vector<int> dist(n, INT_MAX);
        dijstra(g, dist, 0);
        return dist[n - 1];
    }
    int cost(int x1, int y1, int x2, int y2) {
        return abs(x1 - x2) + abs(y1 - y2);
    }
};

4.

本题其实不难，但比较容易疏漏出错。

不难发现以下几点，

因此，一个比较自然的思路是，从字符串末尾开始找，找到第一个能变动的字母，将其改成一个更大的字母，然后后续重复类似于 abcabcabc 的序列。

最终的解法如下。基本思路是，从后向前遍历，每个字母在不构成子串的前提下尝试替换为一个较大的字母，一旦替换成功，就在后续附加 abc 三个字母构成的某个周期序列，并注意不要引入新的回文串。

class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        int n = s.size();
        for(int i = n - 1; i >= 0; i--) {
            
            char b1 = i > 0 ? s[i - 1] : 0, b2 = i > 1 ? s[i - 2] : 0;
            int t = s[i] + 1;
            while(t == b1 or t == b2) t++;
            
            if(t - 'a' < k) {
                s[i] = t;
                
                string seq = "abc";                
                if(b1 == 'a' and t == 'b') seq = "cab";
                if(b1 == 'a' and t == 'c') seq = "bac";
                if(b1 == 'b' and t == 'a') seq = "cba";
                if(b1 == 'b' and t == 'c') seq = "abc";
                if(b1 == 'c' and t == 'a') seq = "bca";
                if(b1 == 'c' and t == 'b') seq = "acb";
                if(t == 'a') seq = "bca";
                if(t == 'b') seq = "acb";                
                if(b1 == 'a') seq = "bac";
                
                for(int j = i + 1; j < n; j++) {
                    s[j] = seq[(j - i - 1) % 3];
                }
                return s;
            }
        }
        return "";
    }
};