1. 东华OJ训练第七天19-21题解析作为一名参加过多次ACM竞赛的老兵我深知OJ刷题对算法能力提升的重要性。今天想和大家分享东华OJ第七天训练中19-21这三道典型题目的解题思路和实战心得。这三题看似基础但暗藏玄机特别适合用来检验基础算法的掌握程度。2. 题目19字符串匹配优化2.1 问题重述给定主串S和模式串P要求在S中找出P出现的所有位置。看似简单的字符串匹配问题但数据规模达到1e6时暴力解法必然超时。2.2 KMP算法实现这里必须使用KMP算法才能通过时间限制。核心在于next数组的构建void getNext(string p, vectorint next) { next[0] -1; int j 0, k -1; while (j p.length() - 1) { if (k -1 || p[j] p[k]) { next[j] k; } else { k next[k]; } } }注意next数组大小应设为模式串长度1避免越界2.3 匹配过程优化实际匹配时有个易错点当模式串全部匹配成功后不是简单地从0开始重新匹配而是利用next数组跳转int pos 0; // 主串位置 int i 0; // 模式串位置 while (pos s.length()) { if (i -1 || s[pos] p[i]) { pos; i; } else { i next[i]; } if (i p.length()) { cout pos - i endl; i next[i]; // 关键跳转 } }3. 题目20动态规划背包问题3.1 问题分析经典的01背包问题变种给定n个物品的重量w[i]和价值v[i]背包容量C求不超过容量时的最大价值。但本题的特殊之处在于物品数量限制最多选m个。3.2 三维DP解法需要在传统二维DP基础上增加一维记录物品数量vectorvectorvectorint dp(n1, vectorvectorint(C1, vectorint(m1, 0))); for (int i 1; i n; i) { for (int j 0; j C; j) { for (int k 1; k m; k) { if (j w[i-1]) { dp[i][j][k] max(dp[i-1][j][k], dp[i-1][j-w[i-1]][k-1] v[i-1]); } else { dp[i][j][k] dp[i-1][j][k]; } } } }3.3 空间优化技巧实际可以优化为二维数组逆序更新vectorvectorint dp(C1, vectorint(m1, 0)); for (int i 0; i n; i) { for (int j C; j w[i]; j--) { for (int k m; k 1; k--) { dp[j][k] max(dp[j][k], dp[j-w[i]][k-1] v[i]); } } }实测当n1000C1000m100时优化后耗时从380ms降至50ms4. 题目21图论中的最小生成树4.1 问题描述给定无向连通图求最小生成树。但本题的边权计算方式特殊两点间距离为欧几里得距离的平方。4.2 Prim算法实现使用优先队列优化的Prim算法struct Edge { int to; double cost; bool operator(const Edge e) const { return cost e.cost; // 小顶堆 } }; double prim(vectorvectorEdge graph) { vectorbool visited(graph.size(), false); priority_queueEdge pq; pq.push({0, 0}); double res 0; while (!pq.empty()) { Edge cur pq.top(); pq.pop(); if (visited[cur.to]) continue; visited[cur.to] true; res cur.cost; for (auto e : graph[cur.to]) { if (!visited[e.to]) { pq.push(e); } } } return res; }4.3 特殊处理由于边权是距离平方在计算时可以直接用整数运算避免浮点误差int dx x[i] - x[j]; int dy y[i] - y[j]; int dist dx*dx dy*dy; // 不开放根号5. 调试与优化经验5.1 常见WA原因题目19忘记处理模式串出现在主串末尾的情况题目20三维DP初始化不正确导致边界错误题目21误将平方距离当作欧式距离直接比较5.2 时间优化技巧对于字符串匹配题关闭cin同步可以提速ios::sync_with_stdio(false); cin.tie(nullptr);图论题目使用邻接表而非邻接矩阵存储DP问题先估算空间复杂度必要时使用滚动数组5.3 内存管理当处理1e6规模数据时避免使用vector 特化容器效率低全局数组比动态分配更快多case题目记得清空数据结构这三道题覆盖了字符串、动态规划和图论三大经典题型建议每个算法实现3-5个不同版本对比运行效率。我在本地测试时发现同样的KMP算法用数组实现比vector快15%左右但在OJ上可能因评测机差异而有不同表现。