算法竞赛模板整理

整理了竞赛中常用的算法模板，方便快速查阅。

排序算法

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
void quickSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int pivot = arr[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i < j) swap(arr[i], arr[j]);
    }
    quickSort(arr, l, j);
    quickSort(arr, j + 1, r);
}

图论

最短路（Dijkstra）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> dijkstra(int src, vector<vector<pair<int,int>>>& adj, int n) {
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

动态规划

最长公共子序列（LCS）

1
2
3
4
5
6
7
8
9
int lcs(string& a, string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1
                                            : max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

持续更新中… 🔄