企业官网建设流程全解析

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, vector<int>& 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基础上增加一维记录物品数量：

vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(C+1, vector<int>(m+1, 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 空间优化技巧

实际可以优化为二维数组，逆序更新：

vector<vector<int>> dp(C+1, vector<int>(m+1, 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]); } } }

实测：当n=1000，C=1000，m=100时，优化后耗时从380ms降至50ms

4. 题目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(vector<vector<Edge>>& graph) { vector<bool> visited(graph.size(), false); priority_queue<Edge> 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 时间优化技巧

1. 对于字符串匹配题，关闭cin同步可以提速：

ios::sync_with_stdio(false); cin.tie(nullptr);

2. 图论题目使用邻接表而非邻接矩阵存储

3. DP问题先估算空间复杂度，必要时使用滚动数组

5.3 内存管理

当处理1e6规模数据时：

• 避免使用vector （特化容器效率低）
• 全局数组比动态分配更快
• 多case题目记得清空数据结构

这三道题覆盖了字符串、动态规划和图论三大经典题型，建议每个算法实现3-5个不同版本，对比运行效率。我在本地测试时发现，同样的KMP算法，用数组实现比vector快15%左右，但在OJ上可能因评测机差异而有不同表现。