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

1. 题目背景与解题思路概述这组题目来自洛谷在线评测平台涵盖多种算法题型。作为算法竞赛选手我经常通过刷题来保持手感。最近集中解决了P14923、P11967等9道题目发现它们虽然编号分散但涉及的知识点很有代表性。下面我将按照题目难度和知识点分类分享我的解题思路和代码实现。2. 基础数据结构题解2.1 P10289 队列模拟这道题考察基本的队列操作。题目要求模拟一个队列支持入队、出队和查询队首元素三种操作。#include queue using namespace std; int main() { queueint 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) { stackchar 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; vectorint w(N1), v(N1); for(int i1; iN; i) cin w[i] v[i]; for(int i1; iN; i) { for(int j0; jW; j) { for(int k0; kK; 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(); vectorvectorint dp(m1, vectorint(n1)); for(int i1; im; i) { for(int j1; jn; 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 pairint, int pii; vectorint dijkstra(vectorvectorpii graph, int start) { int n graph.size(); vectorint dist(n, INT_MAX); dist[start] 0; priority_queuepii, vectorpii, greaterpii 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, vectorvectorint edges) { vectorvectorint graph(n); vectorint inDegree(n, 0); for(auto e : edges) { graph[e[0]].push_back(e[1]); inDegree[e[1]]; } queueint q; for(int i0; in; 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: vectorint 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*21] lazy[node] * (r - mid); lazy[node*21] 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*21, mid1, r, L, R, val); tree[node] tree[node*2] tree[node*21]; } 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*21, mid1, 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: vectorint parent, size; stackpairint, int history; public: DSU(int n) { parent.resize(n); size.resize(n, 1); for(int i0; in; 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. 解题技巧与优化策略在解决这组题目时我总结了一些通用技巧输入输出优化对于C在数据量较大时使用ios::sync_with_stdio(false); cin.tie(0);可以显著加快IO速度。调试技巧对于复杂的算法可以编写小数据生成器和对拍程序验证代码正确性。复杂度分析实现算法前先估算时间复杂度确保不会超时。例如n1e5时O(nlogn)算法通常可行O(n^2)则不行。空间优化动态规划问题中如果当前状态只依赖于前一个状态可以压缩空间到一维。边界处理特别注意数组越界、空容器访问等边界情况这是比赛中常见的失分点。7. 常见错误与调试方法在解决这些题目时我遇到了几个典型错误数组越界在P10725中最初没有检查物品数量k的下限导致数组访问越界。优先级队列使用错误在Dijkstra实现中忘记处理重复节点导致效率降低。浮点数精度问题虽然这组题目中没有涉及但在其他题目中需要注意比较浮点数时使用epsilon。递归爆栈深度优先搜索时对于大数据量需要使用非递归实现或手动设置栈大小。调试方法使用小样例手动模拟算法执行过程输出中间变量检查状态转移是否正确使用assert验证不变量对于WA的测试点构造边界案例测试8. 题目扩展与变种思考这些题目都可以进一步扩展P10289可以增加双端队列操作或者限制队列最大容量。P10725可以改为完全背包或多重背包问题。P13019可以扩展为求所有LCS而不仅是一个。P11967可以增加负权边改用SPFA算法。P14923可以支持更多的区间操作如区间最值、区间gcd等。对于想进一步提高的选手我建议尝试实现这些扩展版本并比较不同解法的效率差异。