Weekly Contest 409

日期 2024/08/04
只有寫出第一與第二題。這次太晚起床去撰寫題目，來不及改完

• Design Neighbor Sum Service
• Shortest Distance After Road Addition Queries I
• Shortest Distance After Road Addition Queries II
• Alternating Groups III

第一題

vector<vector<int>> grid;
neighborSum(vector<vector<int>>& grid) {
    this->grid = grid;
}

int adjacentSum(int value) {
    const int m = grid.size();
    const int n = grid[0].size();
    int i = 0;
    int j = 0;
    for(i = 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            if(grid[i][j] == value)
                goto xx;
        }
    }
xx:
    int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    int ret = 0;
    for(int k = 0; k < 4; k++) {
        int x = dir[k][0] + i;
        int y = dir[k][1] + j;
        if(x < 0 || x >= m || y < 0 || y >= n)
            continue;
        ret += grid[x][y];
    }
    return ret;
}

int diagonalSum(int value) {
    const int m = grid.size();
    const int n = grid[0].size();
    int i = 0;
    int j = 0;
    for(i = 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            if(grid[i][j] == value)
                goto xx;
        }
    }
xx:
    int dir[4][2] = {{1, -1}, {1, 1}, {-1, 1}, {-1, -1}};
    int ret = 0;
    for(int k = 0; k < 4; k++) {
        int x = dir[k][0] + i;
        int y = dir[k][1] + j;
        if(x < 0 || x >= m || y < 0 || y >= n)
            continue;
        ret += grid[x][y];
    }
    return ret;
}

第二題

vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
    vector<int> ret;
    vector<vector<int>> indegree(n), outdegree(n);
    for(int i = 1; i < n; i++) {
        // indegree[n - i].push_back(n - i - 2);
        // cout << n - i - 1 << " " << n - i << endl;
        outdegree[n - i - 1].push_back(n - i);
    }

    for(vector<int> &q: queries) {
        vector<int> dp(n, -1);                
        outdegree[q[0]].push_back(q[1]);
        int x = dfs(0, outdegree, dp);
        ret.push_back(x);
    }
    return ret;
}

int dfs(int start, vector<vector<int>> &outdegree, vector<int> &dp) {
    const int n = outdegree.size();
    if(start == n - 1)
        return 0;

    if(dp[start] != -1)
        return dp[start];

    int ret = n - 1;
    for(int x: outdegree[start]) {
        ret = min(ret, dfs(x, outdegree, dp) + 1);
    }
    dp[start] = ret;
    return ret;
}

第三題

稍微修改程式碼也是依然超時

TLE

vector<int> shortestDistanceAfterQueries(int n,
                                         vector<vector<int>>& queries) {
    vector<int> ret;
    vector<vector<int>> indegree(n), outdegree(n);
    for (int i = 1; i < n; i++) {
        // indegree[n - i].push_back(n - i - 2);
        // cout << n - i - 1 << " " << n - i << endl;
        outdegree[n - i - 1].push_back(n - i);
    }

    vector<int> dp(n, -1);
    for (vector<int>& q : queries) {
        outdegree[q[0]].push_back(q[1]);
        fill(dp.begin(), dp.begin() + q[0] + 1, -1);
        int x = dfs(0, outdegree, dp);
        ret.push_back(x);
    }
    return ret;
}

int dfs(int start, vector<vector<int>>& outdegree, vector<int>& dp) {
    const int n = outdegree.size();
    if (start == n - 1)
        return 0;

    if (dp[start] != -1)
        return dp[start];

    int ret = n - 1;
    for (int x : outdegree[start]) {
        ret = min(ret, dfs(x, outdegree, dp) + 1);
    }
    dp[start] = ret;
    return ret;
}

討論區解答

vector<int> shortestDistanceAfterQueries(int n,
                                         vector<vector<int>>& queries) {
    vector<int> rr(n);
    iota(rr.begin(), rr.end(), 0);
    set<int> ss(rr.begin(), rr.end());

    vector<int> ret;
    for(vector<int> &q: queries) {
        auto x = ss.lower_bound(q[0] + 1);
        auto y = ss.upper_bound(q[1] - 1);

        ss.erase(x, y);
        ret.push_back(ss.size() - 1);
    }
    return ret;
}

第四題