算法竞赛题解：队列、栈、动态规划与图论实战

发布时间：2026/11/4 20:32:24
算法竞赛题解：队列、栈、动态规划与图论实战

1. 题目背景与解题思路概述

这组题目来自洛谷在线评测平台，涵盖多种算法题型。作为算法竞赛选手，我经常通过刷题来保持手感。最近集中解决了P14923、P11967等9道题目，发现它们虽然编号分散，但涉及的知识点很有代表性。下面我将按照题目难度和知识点分类，分享我的解题思路和代码实现。

2. 基础数据结构题解

2.1 P10289 队列模拟

这道题考察基本的队列操作。题目要求模拟一个队列，支持入队、出队和查询队首元素三种操作。

#include <queue> using namespace std; int main() { queue<int> q; int n, op, x; cin >> n; while(n--) { cin >> op; if(op == 1) { cin >> x; q.push(x); } else if(op == 2) { if(!q.empty()) q.pop(); } else { if(q.empty()) cout << "Empty\n"; else cout << q.front() << "\n"; } } return 0; }

注意：题目没有说明操作是否合法，需要自行处理空队列时的出队和查询操作。

2.2 P10264 栈的应用

这是一道典型的栈应用题目，要求检查括号匹配。我的解法是用栈来跟踪未匹配的左括号。

#include <stack> #include <string> using namespace std; bool isValid(string s) { stack<char> st; for(char c : s) { if(c == '(' || c == '[' || c == '{') { st.push(c); } else { if(st.empty()) return false; char top = st.top(); if((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { return false; } st.pop(); } } return st.empty(); }

3. 动态规划专题

3.1 P10725 背包问题变种

这道题是01背包的变形，额外增加了物品数量的限制。我采用三维DP来解决：

int dp[101][101][101]; // dp[i][j][k]表示前i个物品，总重量j，总数量k的最大价值 int solve() { int N, W, K; cin >> N >> W >> K; vector<int> w(N+1), v(N+1); for(int i=1; i<=N; i++) cin >> w[i] >> v[i]; for(int i=1; i<=N; i++) { for(int j=0; j<=W; j++) { for(int k=0; k<=K; k++) { if(j >= w[i] && k >= 1) { dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-w[i]][k-1] + v[i]); } else { dp[i][j][k] = dp[i-1][j][k]; } } } } return dp[N][W][K]; }

3.2 P13019 最长公共子序列

经典LCS问题，我使用了带路径还原的解法：

string LCS(string &s1, string &s2) { int m = s1.size(), n = s2.size(); vector<vector<int>> dp(m+1, vector<int>(n+1)); for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { if(s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } // 路径还原 string res; int i = m, j = n; while(i > 0 && j > 0) { if(s1[i-1] == s2[j-1]) { res.push_back(s1[i-1]); i--; j--; } else if(dp[i-1][j] > dp[i][j-1]) { i--; } else { j--; } } reverse(res.begin(), res.end()); return res; }

4. 图论算法题解

4.1 P11967 最短路径问题

这道题是标准的最短路径问题，我使用了Dijkstra算法：

#include <vector> #include <queue> using namespace std; typedef pair<int, int> pii; vector<int> dijkstra(vector<vector<pii>> &graph, int start) { int n = graph.size(); vector<int> dist(n, INT_MAX); dist[start] = 0; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, start}); while(!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if(d > dist[u]) continue; for(auto &[v, w] : graph[u]) { if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }

提示：使用优先队列时要注意处理重复节点，当从队列中取出一个节点时，如果它的距离值已经比当前记录的大，可以直接跳过。

4.2 P13020 拓扑排序

这道题要求判断一个有向图是否有环，可以通过拓扑排序来实现：

bool hasCycle(int n, vector<vector<int>>& edges) { vector<vector<int>> graph(n); vector<int> inDegree(n, 0); for(auto &e : edges) { graph[e[0]].push_back(e[1]); inDegree[e[1]]++; } queue<int> q; for(int i=0; i<n; i++) { if(inDegree[i] == 0) q.push(i); } int cnt = 0; while(!q.empty()) { int u = q.front(); q.pop(); cnt++; for(int v : graph[u]) { if(--inDegree[v] == 0) { q.push(v); } } } return cnt != n; }

5. 高级数据结构应用

5.1 P14923 线段树应用

这道题需要区间查询和区间更新，我实现了带懒标记的线段树：

class SegmentTree { private: vector<int> tree, lazy; int n; void pushDown(int node, int l, int r) { if(lazy[node] != 0) { int mid = (l + r) / 2; tree[node*2] += lazy[node] * (mid - l + 1); lazy[node*2] += lazy[node]; tree[node*2+1] += lazy[node] * (r - mid); lazy[node*2+1] += lazy[node]; lazy[node] = 0; } } void updateRange(int node, int l, int r, int L, int R, int val) { if(R < l || L > r) return; if(L <= l && r <= R) { tree[node] += val * (r - l + 1); lazy[node] += val; return; } pushDown(node, l, r); int mid = (l + r) / 2; updateRange(node*2, l, mid, L, R, val); updateRange(node*2+1, mid+1, r, L, R, val); tree[node] = tree[node*2] + tree[node*2+1]; } int queryRange(int node, int l, int r, int L, int R) { if(R < l || L > r) return 0; if(L <= l && r <= R) return tree[node]; pushDown(node, l, r); int mid = (l + r) / 2; return queryRange(node*2, l, mid, L, R) + queryRange(node*2+1, mid+1, r, L, R); } public: SegmentTree(int size) : n(size) { tree.resize(4*n, 0); lazy.resize(4*n, 0); } void update(int L, int R, int val) { updateRange(1, 1, n, L, R, val); } int query(int L, int R) { return queryRange(1, 1, n, L, R); } };

5.2 P14924 并查集应用

这道题考察并查集的高级应用，需要支持撤销操作：

class DSU { private: vector<int> parent, size; stack<pair<int, int>> history; public: DSU(int n) { parent.resize(n); size.resize(n, 1); for(int i=0; i<n; i++) parent[i] = i; } int find(int u) { while(parent[u] != u) u = parent[u]; return u; } bool unite(int u, int v) { u = find(u); v = find(v); if(u == v) return false; if(size[u] < size[v]) swap(u, v); history.push({u, v}); parent[v] = u; size[u] += size[v]; return true; } void rollback() { if(history.empty()) return; auto [u, v] = history.top(); history.pop(); parent[v] = v; size[u] -= size[v]; } };

6. 解题技巧与优化策略

在解决这组题目时，我总结了一些通用技巧：

  1. 输入输出优化：对于C++，在数据量较大时使用ios::sync_with_stdio(false); cin.tie(0);可以显著加快IO速度。

  2. 调试技巧：对于复杂的算法，可以编写小数据生成器和对拍程序，验证代码正确性。

  3. 复杂度分析：实现算法前先估算时间复杂度，确保不会超时。例如，n=1e5时O(nlogn)算法通常可行，O(n^2)则不行。

  4. 空间优化：动态规划问题中，如果当前状态只依赖于前一个状态，可以压缩空间到一维。

  5. 边界处理：特别注意数组越界、空容器访问等边界情况，这是比赛中常见的失分点。

7. 常见错误与调试方法

在解决这些题目时，我遇到了几个典型错误：

  1. 数组越界：在P10725中，最初没有检查物品数量k的下限，导致数组访问越界。

  2. 优先级队列使用错误：在Dijkstra实现中，忘记处理重复节点，导致效率降低。

  3. 浮点数精度问题：虽然这组题目中没有涉及，但在其他题目中需要注意比较浮点数时使用epsilon。

  4. 递归爆栈：深度优先搜索时，对于大数据量需要使用非递归实现或手动设置栈大小。

调试方法：

  • 使用小样例手动模拟算法执行过程
  • 输出中间变量检查状态转移是否正确
  • 使用assert验证不变量
  • 对于WA的测试点，构造边界案例测试

8. 题目扩展与变种思考

这些题目都可以进一步扩展：

  1. P10289可以增加双端队列操作，或者限制队列最大容量。

  2. P10725可以改为完全背包或多重背包问题。

  3. P13019可以扩展为求所有LCS而不仅是一个。

  4. P11967可以增加负权边，改用SPFA算法。

  5. P14923可以支持更多的区间操作，如区间最值、区间gcd等。

对于想进一步提高的选手，我建议尝试实现这些扩展版本，并比较不同解法的效率差异。