这次周赛做的很差很差，主要原因可能是因为我的双指针水平太差了，这个t3真的看了很久没有看出来怎么做，甚至连贪心都想了，自然也没时间做完t4了，Profile Here。另外，之后如果A/B题太简单就不发题解了，只提一下用到了什么知识点，可以节约一些时间。

Question D Minimum Time to Visit a Cell In a Grid

题意

给定一个n*m的方格，左上的格子为起点，坐标记作(0, 0)，右下的格子为终点，坐标记作(n-1, m-1)。只能移动到相邻（上下左右）的格子，均需要花费1s时间，而不能停留在某个格子保持位置不变。给定每个格子的最早到达时间，求从起点到达终点的最短时间。

题解

是一个经典的单源最短路问题，如果差分约束问题做得够多的话，应该会一开始想到用差分约束的方法建边，之后从起点跑一个dijkstra。但是这个思路稍微有一点问题，是因为每个格点有一个要求的最早到达时间，而每个时刻都要求在移动，不能停留，这就要求如果可以从起点出发的话，就一定存在一个阶段可以满足在两个格点之间来回走的方式使满足所有格点的最早到达时间，因此这个最短到达时间和格点的最短到达时间之差的奇偶性与每个格点距离起点的hamilton距离的奇偶性应该是相同的（因为来回走并不会改变hamilton距离的奇偶性）。

在满足奇偶性的前提下，这个问题就是一个完完全全的魔改版dijkstra了。考虑从u走到v，从起点到u和v的最早时间是$t_u$和$t_v$，应该满足：

• $t_v \ge t_u + 1$
• $t_v \ge grid[v.x][v.y]$

接下来实现魔改dijkstra就可以了。代码见下：

代码

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
class Solution {
public:
    int minimumTime(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
        int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
        priority_queue<piii> q;
        int dis[n][m];
        memset(dis, -1, sizeof(dis));
        q.push(piii(0, pii(0, 0)));
        while (!q.empty()) {
            auto p = q.top(); q.pop();
            int i = p.second.first, j = p.second.second;
            if (dis[i][j] >= 0) continue;
            dis[i][j] = -p.first;
            for (int k = 0; k < 4; k++) {
                int nx = i + dir[k][0], ny = j + dir[k][1];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || dis[nx][ny] >= 0) continue;
                int v = (dis[i][j] + 1 >= grid[nx][ny] ? dis[i][j] + 1 : grid[nx][ny] + (grid[nx][ny] % 2 != (nx + ny) % 2));
                q.push(piii(-v, pii(nx, ny)));
            }
        }
        return dis[n - 1][m - 1];
    }
};

Question C Find the Maximum Number of Marked Indices

题意

给定一个长为n的数组nums，在每个下标只能使用一次的前提下，找同时满足条件的(i, j)对($i \le j$)使得$2 * nums[i] \le nums[j]$的最多对数。

题解

首先暴力搜索是不行的，其次要注意每个下标只能使用一次，如果不是的话（即统计所有的i, j pair，且每个下标可以用无限次）可以遍历第一维，然后对第二维做二分，就可以在O(nlogn)的时间内实现。

但比赛时候我的思路就stuck在这里了，然后同时还想了个假的双指针做法，直接以为这题的正解不是双指针，但实际上就是个只需要五行就能写完的双指针…首先应该注意到答案最多不能超过n/2，因为每个数只能用一次。所以很自然的想法是把所有数按从小到大排序后，分成前半部和后半部两部分。nums[i]只在前半部分取，nums[j]只在后半部分取，而nums[i]我们希望从小到大选，因为这样可以让更多的后半部数可选，按照这种贪心方式可以用双指针来实现。

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int l = 0, r = (n + 1) / 2;
        while(r < n){
            if(nums[l] * 2 <= nums[r]) l += 1;
            r += 1;
        }
        return l * 2;
    }
};

但我一开始想双指针均左向右扫描，对于每个左指针指到的nums[i]，都让右指针每次找到一个最小的nums[j]使满足nums[i] * 2 <= nums[j]，但这个如果不分成前后两部是错的，因为这样选到的一部分nums[j]可能本身可以用于充当nums[i]。

Question B Find the Divisibility Array of a String

涉及知识点

模拟，简单数论（记得取模）

typedef long long ll;
class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        int n = word.length();
        vector<int> ret(n, 0);
        ll res = 0;
        for(int i = 0; i < n; i++){
            res *= 10;
            res += (word[i] - '0');
            ret[i] = (res % m == 0);
            res %= m;
        }
        return ret;
    }
};

Question A Left and Right Sum Differences

涉及知识点

前缀和，模拟

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> lsum(n + 1, 0), rsum(n + 1, 0);
        for(int i = 1; i <= n; i++){
            lsum[i] = lsum[i - 1] + nums[i - 1];
        }
        for(int i = n - 1; i >= 0; i--){
            rsum[i] = rsum[i + 1] + nums[i];
        }
        vector<int> ret(n, 0);
        for(int i = 0; i < n; i++){
            ret[i] = abs(lsum[i] - rsum[i + 1]);
        }
        return ret;
    }
};