Post

2026 Hackathon复盘

Posted
By Yuanjian Liu
22 min read

复盘凭借印象构造题目大意后重新编写代码解题，使用的函数名和类名与比赛不同，主要提供算法和解题思路。

第一题

题目：给定一个$m \times n$的矩阵，矩阵里的数都是非负整数，构造由同心正方形堆叠而成的乘积靶，最中心的一个正方形的乘积数是$k$，第二个$3 \times 3$的正方形的乘积数是$k-1$，第三个$5 \times 5$的正方形乘积数是$k-2$，以此类推，最大的一个正方形的乘积数是1。把这个乘积靶放在矩阵中，矩阵对应位置的元素和乘积靶的乘积数相乘求和，得到一个结果result，问对每个给定的矩阵，这个结果result最大是多少？

解题思路:

这个result可以拆成$k$个同心全1的正方形相加，有

\[result(i,j) = \sum_{r=0}^{k-1} SquareSum(i-r, j-r, i+r, j+r)\]

用二维前缀和，每个正方形区域的和可以O(1)得到，因此每个位置需要O(k)。

二维前缀和的数组存储的元素定义如下：

\[prefix[i+1][j+1] = \sum_{0 \leq x \leq i, 0 \leq y \leq j} matrix[x][y]\]

矩形区域 $[x1, x2] \times [y_1, y_2]$的元素和为

\[prefix[x_2+1][y_2+1] - prefix[x_1][y_2+1] - prefix[x_2 +1][y1] + prefix[x1][y1]\]

乘积靶的边长为$2k-1$，需要满足$2k-1 \leq m$和$2k-1 \leq n$，所以最大值是

\[k_{max} = \lfloor \frac{min(m,n)+1}{2} \rfloor\]

C++实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <bits/stdc++.h>
using namespace std;

long long maxTargetResult(const vector<vector<int>> &matrix) {
    int m = matrix.size();
    if (m == 0) {
        return 0;
    }
    int n = matrix[0].size();
    int k = (min(m, n) + 1) / 2;
    int targetSize = 2 * k - 1;

    vector<vector<long long>> prefix(m + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            prefix[i + 1][j + 1] =
                matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
        }
    }
    auto rectangleSum = [&](int top, int left, int bottom, int right) -> long long {
        return prefix[bottom + 1][right + 1] - prefix[top][right + 1] - prefix[bottom + 1][left] +
               prefix[top][left];
    };
    long long answer = 0;
    // 枚举最大乘积靶的左上角
    // 靶覆盖:
    // [top, top + targetSize - 1]
    // [left, left + targetSize - 1]
    for (int top = 0; top + targetSize <= m; ++top) {
        for (int left = 0; left + targetSize <= n; ++left) {
            int centerRow = top + k - 1;
            int centerCol = left + k - 1;
            long long result = 0;
            for (int radius = 0; radius < k; ++radius) {
                result += rectangleSum(centerRow - radius, centerCol - radius, centerRow + radius,
                                       centerCol + radius);
            }
            answer = max(answer, result);
        }
    }
    return answer;
}

第二题

题目：给定一个数组array，长度为n，n一定是偶数，你和机器人比赛，每轮你先拿走数组中任意一个数，机器人总是会选择剩下的数组中间那个数，问你最高得分能到多少？

解题思路:

首先这题不是直接拿最大值，对一个数组[0,1,0,2]，如果拿了最大值2，机器人拿1，剩下只能拿0，总分2分，但如果先拿1，机器人会拿0，之后可以拿2，总得分为3分。

这题的思路是把数组分成两半，机器人在每一轮一定是拿中间的2个元素之一，每轮把中间两个元素放入优先队列，让机器人拿最小的那个，算出的分就是机器人最小得分，用总和减去机器人的最小得分就是我能获得的最高分。

C++实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>
using namespace std;

long long maxScore(const vector<int>& array) {
    int n = array.size();

    long long totalSum = std::accumulate(array.begin(), array.end(), 0LL);

    priority_queue<int, vector<int>, greater<int>> minHeap;

    long long robotScore = 0;
    int left = n / 2 - 1;
    int right = n / 2;
    while (left >= 0) {
        minHeap.push(array[left]);
        minHeap.push(array[right]);
        robotScore += minHeap.top();
        minHeap.pop();
        --left;
        ++right;
    }
    return totalSum - robotScore;
}

第三题

题目:给定一个$m \times n$的网格，在$(x1,y1)$, $(x2, y2)$放置两台监视器，第一台监视器可以覆盖 [x1, x1 + scope]的纵向无限长区间，第二台监视器可以覆盖[y2, y2 + scope]的横向无限长区间。现在给定一个pos数组，包含生物栖息地所在的坐标，问当选取最优的监视器放置策略时，最多能覆盖多少个栖息地？

解法一： 时间复杂度 $O(k^2)$，k为pos数组的长度。

该解法会超时，主要在于内层循环还需要遍历所有点，如果把找第二个监视器覆盖剩余点的问题优化成 $\log k$，就能得到最优解。

先固定一台监视器的竖直区间，对于没有被第一台覆盖的点，再选择一个长度为scope的y区间，让第二台覆盖尽可能多的点。

最优区间的左端点一定可以放在某个栖息地的x或y坐标上，对第一台只需要枚举pos[i].x，对第二台枚举pos[i].y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <bits/stdc++.h>
using namespace std;

int maxCoveredHabitats(
    const vector<pair<int, int>>& pos,
    int scope
) {
    int k = static_cast<int>(pos.size());
    int answer = 0;

    for(int j=0;j<k;j++) {
        int yStart = pos[j].second
        int covered = 0;

        for(const auto& [x, y]: pos) {
            if(yStart <= y && y <= yStart + scope) {
                ++covered;
            }
        }
        answer = max(answer, covered);
    }

    for(int i=0;i<k;++i) {
        int xStart = pos[i].first;
        int verticalCovered = 0;

        vector<int> remainingY;

        for(const auto&[x, y]: pos) {
            if (xStart <= x && x <= xStart + scope) {
                ++verticalCovered;
            } else {
                remainingY.push_back(y);
            }
        }

        sort(remainingY.begin(), remainingY.end());

        int left=0;
        for(int right=0; right < static_cast<int>(remainingY.size()); ++right) {
            while(remainingY[right] - remainingY[left] > scope) {
                ++left;
            }
            int horizontalCovered = right - left + 1;
            answer = max(answer, verticalCovered + horizontalCovered);
        }
        answer = max(answer, verticalCovered);
    }
    return answer;
    
}

解法二：扫描线+线段树，当k达到10^5时得用这种优化解法，时间复杂度为$O(k \log k)$。

思路如下：

  1. 按x排序，使用滑动窗口维护第一台监视器当前覆盖的点。
  2. 对于第一台没有覆盖的点，维护第二台监视器在不同$y_2$下能覆盖多少个点。
  3. 一个纵坐标为y的点，可以被所有满足 $y-scope \leq y_2 \leq y$ 的水平区间覆盖。
  4. 将所有可能的$y_2$离散化，用线段树维护区间加法和全局最大值。
  5. 一个点进入第一台监视器时，将它从第二台的统计中删除，离开时再加回来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
private:
    int n;
    vector<int> maximum;
    vector<int> lazy;

    void apply(int node, int value) {
        maximum[node] += value;
        lazy[node] += value;
    }

    void pushDown(int node) {
        if(lazy[node] == 0) {
            return;
        }

        apply(node*2, lazy[node]);
        apply(node*2 + 1, lazy[node]);
        lazy[node] = 0;
    }

    void rangeAdd(int node, int left, int right, int queryLeft, int queryRight, int value) {
        if(queryLeft <= left && right <= queryRight) {
            apply(node, value);
            return;
        }
        pushDown(node);
        int middle = left + (right - left) / 2;
        if (queryLeft <= middle) {
            rangeAdd(node * 2, left, middle, queryLeft, queryRight, value);
        }
        if (queryRight > middle) {
            rangeAdd(node * 2 + 1, middle + 1, right, queryLeft, queryRight, value);
        }
        maximum[node] = max(maximum[node*2], maximum[node*2 + 1]);
    }
public:
    explicit SegmentTree(int size): n(size), maximum(size*4, 0), lazy(size*4, 0) {}
    void rangeAdd(int left, int right, int value) {
        if (left > right || n == 0) {
            return;
        }
        rangeAdd(1, 0, n-1, left, right, value);
    }
    int getMaximum() const {
        return n==0 ? 0 : maximum[1];
    }
};

int maxCoveredHabitats(
    const vector<pair<int, int>>& points,
    int scope
) {
    int k = static_cast<int>(points.size());
    if(k==0) {
        return 0;
    }
    sort(points.begin(), points.end());
    // candidates维护第二台水平监视器所有值得考虑的起始纵坐标
    vector<long long> candidates;
    for(const auto&[x, y]: points) {
        candidates.push_back(y);
    }
    sort(candidates.begin(), candidates.end());
    candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
    // 线段树维护对于每一个候选水平区间起点 y_2，第二台监视器当前能够覆盖多少个“没有被第一台监视器覆盖”的栖息地。
    SegmentTree tree(static_cast<int>(candidates.size()));

    auto updatePoint = [&] (long long y, int delta) {
        int left = static_cast<int>(
            lower_bound(
                candidates.begin(),
                candidates.end(),
                y - scope
            ) - candidates.begin()
        );
        int right = static_cast<int>(
            upper_bound(
                candidates.begin(),
                candidates.end(),
                y
            ) - candidates.begin()
        ) - 1;
        tree.rangeAdd(left, right, delta);
    }

    // 初始状态：所有点都不在监视器1中，都放在第二台监视器里统计
    for(const auto&[x, y]: points) {
        updatePoint(y, 1);
    }

    int answer = tree.getMaximum();
    int right = 0;
    int verticalCovered = 0;

    // 按照相同 x 分组枚举第一台监视器的左端点。
    int left = 0;
    while(left < k) {
        long long xStart = points[left].first;
        // 每一轮循环是把监视器1放在xStart，用线段树把监视器2能覆盖的不包含监视器1覆盖的点的数量求出来
        // 被第一台监视器维护了的点，要从第二台里减掉
        while (right < k && points[right].first <= xStart + scope) {
            updatePoint(points[right].second, -1);
            ++verticalCovered;
            ++right;
        }
        // 此时已经有了监视器1放在xStart的时候的答案
        answer = max(answer, verticalCovered + tree.getMaximum());

        int nextLeft = left;
        //第一台监视器往前走，要在第二台里把nextLeft之前的加回来
        while(nextLeft < k && points[nextLeft].first == xStart) {
            updatePoint(points[nextLeft].second, 1);
            --verticalCovered;
            ++nextLeft;
        }
        left = nextLeft;
    }
    return answer;
}

第四题

题目: 总共有$n$个节点。有一个数组$s$，每个元素$s[i]$包含一个二元组$(u, v)$表示从节点$u$到节点$v$之间的边。再给定第二个整数数组$p$，长度和$s$一样，表示$s$中每条边所属的组号$g$。接下来有一个queries数组，每个query包含一个二元组$(g1, g2)$，表示query选取的两组边，针对query选择的两组边构建无向图，求每个query对应无向图的连通数（即形成了几个岛屿）。

基本解题思路：

  1. 按组把边分类存到一个unordered_map里，可以用组号获得所有该组的边。
  2. 每轮query创建新的并查集，初始连通数为n。
  3. 遍历query里要求的两组边，进行unite操作，完成后即获得最终连通数。

TLE警告：由于s和queries.size()达到1e5，这个方案会超时。这题主要就难在这个点，该方案也能有97%的用例通过，可惜没有部分分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <bits/stdc++.h>
using namespace std;
class DSU {
private:
    vector<int> parent;
    vector<int> size;
    int componentCount;

public:
    explicit DSU(int n)
        : parent(n), size(n, 1), componentCount(n) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false;
        }

        // 小树合并到大树
        if (size[rootX] < size[rootY]) {
            swap(rootX, rootY);
        }

        parent[rootY] = rootX;
        size[rootX] += size[rootY];
        --componentCount;

        return true;
    }

    int count() const {
        return componentCount;
    }
};

vector<int> countComponents(
    int n,
    const vector<pair<int, int>>& s,
    const vector<int>& p,
    const vector<pair<int, int>>& queries
) {
    unordered_map<int, vector<pair<int, int>>> groupEdges;
    
    for(size_t i=0;i<s.size();++i) {
        groupEdges[p[i]].push_back(s[i]);
    }
    vector<int> answer;
    answer.reserve(queries.size());

    for(const auto&[g1, g2]: queries) {
        DSU dsu(n);
        auto it1 = groupEdges.find(g1);
        if(it1 != groupEdges.end()) {
            for(const auto&[u, v]: it1->second) {
                dsu.unite(u, v);
            }
        }

        if(g2 != g1) {
            auto it2 = groupEdges.find(g2);
            if(it2 != groupEdges.end()) {
                for(const auto&[u, v]: it2->second) {
                    dsu.unite(u, v);
                }
            }
        }
        answer.push_back(dsu.count());
    }
    return answer;
}

这题赛场上没能过，应该需要根号分治+可回滚并查集解决。

分治的重点问题在于大组的边很多，不能在每个query中重复加入；小组虽然重复加入，但每组边数不超过阈值B，所以单次成本可控。取$ B=\sqrt{m} $，当$m=10^5$,重组数量最多只有316个，不同的重组+重组组合最多为$316 \times 315 / 2 \approx 50000$。通过分治的策略，让最坏复杂度大约为

\[O(\frac{m^2}{B} \log n) = O(m \sqrt{m} \log n)\]

可回滚并查集： 普通的并查集使用路径压缩后，很难撤销。可回滚并查集：(1)不使用路径压缩; (2)使用按大小合并，保证树高度为$O(\log n)$; (3)每次合并记录修改；(4)可以回到之前的快照。这样处理一对组时，可以记录快照，临时加入第二组边，得到连通分量数，回滚到快照。

C++实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

class RollbackDSU {
private:
    struct Change {
        int childRoot;
        int parentRoot;
        int oldParentSize;
    };

    vector<int> parent;
    vector<int> treeSize;
    vector<Change> history;
    int componentCount;

public:
    explicit RollbackDSU(int n) : parent(n), treeSize(n, 1), componentCount(n) {
        iota(parent.begin(), parent.end(), 0);
    }

    // 回滚并查集不能路径压缩
    int find(int x) const {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }

    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false;
        }
        if (treeSize[rootX] < treeSize[rootY]) {
            swap(rootX, rootY);
        }
        history.push_back({rootY, rootX, treeSize[rootX]});
        parent[rootY] = rootX;
        treeSize[rootX] += treeSize[rootY];
        --componentCount;

        return true;
    }

    int snapshot() const { return static_cast<int>(history.size()); }

    void rollback(int snapshotSize) {
        while (static_cast<int>(history.size()) > snapshotSize) {
            Change change = history.back();
            history.pop_back();

            parent[change.childRoot] = change.childRoot;
            treeSize[change.parentRoot] = change.oldParentSize;
            ++componentCount;
        }
    }

    int count() const { return componentCount; }
};

using Edge = pair<int, int>;

struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        uint64_t first = static_cast<uint32_t>(p.first);
        uint64_t second = static_cast<uint32_t>(p.second);
        return static_cast<size_t>((first << 32) ^ second);
    }
};

static pair<int, int> normalizePair(int g1, int g2) {
    if (g1 > g2) {
        swap(g1, g2);
    }
    return {g1, g2};
}

static void addEdges(RollbackDSU& dsu, const vector<Edge>& edges) {
    for (const auto& [u, v] : edges) {
        dsu.unite(u, v);
    }
}

vector<int> countComponents(int n, const vector<pair<int, int>>& s, const vector<int>& p,
                            const vector<pair<int, int>>& queries) {
    int m = static_cast<int>(s.size());
    int threshold = max(1, static_cast<int>(sqrt(max(1, m))) + 1);
    unordered_map<int, vector<Edge>> groupEdges;
    groupEdges.reserve(p.size() * 2);

    for (int i = 0; i < m; ++i) {
        groupEdges[p[i]].push_back(s[i]);
    }

    unordered_map<int, bool> isHeavy;
    isHeavy.reserve(groupEdges.size() * 2);

    for (const auto& [group, edges] : groupEdges) {
        isHeavy[group] = static_cast<int>(edges.size()) >= threshold;
    }

    vector<pair<int, int>> normalizedQueries;
    normalizedQueries.reserve(queries.size());
    unordered_map<pair<int, int>, int, PairHash> answer;
    answer.reserve(queries.size() * 2);

    for (const auto& [g1, g2] : queries) {
        auto key = normalizePair(g1, g2);
        normalizedQueries.push_back(key);
        answer.emplace(key, -1);
    }

    /*
     * 把待计算的查询分成两类：
     *
     * 1. 轻组 + 轻组
     * 2. 至少包含一个重组
     *
     * 第二类查询分配给其中一个重组。
     */
    vector<pair<int, int>> lightQueries;
    // heavyQueries[h] 表示以重组 h 作为基础的查询。
    unordered_map<int, vector<pair<int, int>>> heavyQueries;
    heavyQueries.reserve(groupEdges.size());

    for (const auto& [key, unused] : answer) {
        int g1 = key.first;
        int g2 = key.second;
        bool heavy1 = isHeavy.find(g1) != isHeavy.end() && isHeavy[g1];
        bool heavy2 = isHeavy.find(g2) != isHeavy.end() && isHeavy[g2];
        if (!heavy1 && !heavy2) {
            lightQueries.push_back(key);
        } else if (heavy1) {
            heavyQueries[g1].push_back(key)
        } else {
            heavyQueries[g2].push_back(key);
        }
    }

    RollbackDSU dsu(n);

    // 处理轻组+轻组
    for (const auto& key : lightQueries) {
        int snapshot = dsu.snapshot();
        int g1 = key.first;
        int g2 = key.second;
        auto it1 = groupEdges.find(g1);
        if (it1 != groupEdges.end()) {
            addEdges(dsu, it1->second);
        }
        if (g2 != g1) {
            auto it2 = groupEdges.find(g2);
            if (it2 != groupEdges.end()) {
                addEdges(dsu, it2->second);
            }
        }
        answer[key] = dsu.count();
        dsu.rollback(snapshot);
    }

    // 处理包含重组的查询
    for (const auto& [heavyGroup, queryList] : heavyQueries) {
        // 当前DSU应为空状态
        int emptySnapshot = dsu.snapshot();
        addEdges(dsu, groupEdges[heavyGroup]);
        int heavySnapshot = dsu.snapshot();

        for (const auto& key : queryList) {
            int otherGroup = key.first == heavyGroup ? key.second : key.first;

            if (otherGroup != heavyGroup) {
                auto it = groupEdges.find(otherGroup);
                if (it != groupEdges.end()) {
                    addEdges(dsu, it->second);
                }
            }

            answer[key] = dsu.count();
            dsu.rollback(heavySnapshot);
        }
        dsu.rollback(emptySnapshot);
    }
    // 按照原始查询顺序返回。
    vector<int> result;
    result.reserve(queries.size());

    for (const auto& key : normalizedQueries) {
        result.push_back(answer[key]);
    }

    return result;
}
Tutorial
algorithm C++ Python 算法
This post is licensed under CC BY 4.0 by the author.

© Yuanjian Liu. Some rights reserved.

Stay passionate about your life because it is awesome!