企业官网建设流程全解析

1. 题目解析与解题思路

这道题目来自第33次CSP认证考试的第一题，主要考察对基础数据结构和简单算法的掌握程度。题目要求统计一组文本数据中每个单词的出现频率以及包含该单词的篇章数量。

1.1 题目需求拆解

题目输入格式为：

• 第一行两个整数n和m，分别表示篇章数量和单词总数
• 接下来n行，每行第一个数字len表示该篇章的单词数量，后面跟着len个单词编号

需要输出m行，每行两个数字：

• 第一个数字表示包含该单词的篇章数量
• 第二个数字表示该单词在所有篇章中出现的总次数

1.2 解题思路分析

这道题的核心在于高效统计两个维度的数据：

1. 每个单词在所有篇章中的总出现次数（词频统计）
2. 每个单词出现在多少个不同的篇章中（篇章覆盖统计）

考虑到单词编号范围已知（1到m），我们可以使用两个数组来记录这些信息：

• WC数组记录每个单词的总出现次数
• PC数组记录包含每个单词的篇章数量

2. 代码实现详解

2.1 数据结构选择

const int MAXM=101; vector<int> WC(MAXM); // 单词总出现次数 vector<int> PC(MAXM); // 包含单词的篇章数

这里使用vector而不是原生数组有几个考虑：

1. 可以方便地初始化为全0
2. 边界检查更安全（虽然本题不需要）
3. 代码风格更现代

2.2 核心算法流程

for(int i=0;i<n;i++){ // 遍历每篇文本 int len; cin>>len; vector<int> temp(MAXM,0); // 临时记录当前篇章单词 for(int j=0;j<len;j++){ // 遍历当前篇章的每个单词 int word; cin>>word; WC[word]++; // 全局词频统计 temp[word]++; // 当前篇章词频统计 } for(int k=1;k<=m;k++){ // 更新篇章覆盖统计 if(temp[k]>0) PC[k]++; } }

这个双重循环的设计非常巧妙：

1. 外层循环处理每篇文本
2. 内层第一个循环处理文本中的每个单词，同时更新全局词频
3. 内层第二个循环检查哪些单词出现在当前篇章中，更新篇章覆盖统计

2.3 输出处理

for(int i=1;i<=m;i++){ cout<<PC[i]<<" "<<WC[i]<<endl; }

输出时需要注意：

1. 单词编号从1开始
2. 先输出篇章覆盖数，再输出总词频
3. 每个单词一行，按编号顺序输出

3. 算法优化与边界情况

3.1 时间复杂度分析

算法的时间复杂度为O(n*m)，其中：

• n是篇章数量
• m是单词总数

对于CSP第一题的规模（通常n,m≤100），这个复杂度完全足够。

3.2 空间复杂度优化

当前实现使用了三个数组：

1. WC：大小m
2. PC：大小m
3. temp：大小m（每次篇章处理时创建）

可以进一步优化空间：

• 去掉temp数组，改为在读取每个单词时直接判断是否是第一次出现在当前篇章
• 但这样会增加代码复杂度，在本题中得不偿失

3.3 边界情况处理

需要注意的特殊情况：

1. 空输入（n=0）
2. 空篇章（len=0）
3. 单词编号超出范围（题目保证不会出现）
4. 大量重复单词的篇章

当前代码已经正确处理了这些边界情况。

4. 常见错误与调试技巧

4.1 初学者常见错误

1. 数组越界：忘记单词编号从1开始，使用0-based索引
2. 初始化问题：忘记清零统计数组
3. 输出顺序错误：先输出了词频再输出篇章数
4. 重复计数：在更新PC数组时没有使用临时数组标记

4.2 调试建议

1. 使用小规模测试数据手工计算验证
2. 添加中间输出调试：

// 调试输出 cout << "Processing document " << i << endl; for(int k=1;k<=m;k++){ if(temp[k]>0) cout << "Word " << k << " appears " << temp[k] << " times" << endl; }

3. 使用assert检查不变量：

assert(word >=1 && word <=m);

4.3 测试用例设计

好的测试用例应该包含：

1. 常规情况：多篇章、多单词
2. 极端情况：单篇章、单单词
3. 边界情况：空篇章、最大数量篇章
4. 特殊分布：某些单词高频出现，某些单词只出现一次

示例测试用例：

3 5 4 1 2 3 4 2 1 1 3 5 5 5

预期输出：

2 3 // 单词1出现在2个篇章，共3次 1 1 // 单词2 1 1 // 单词3 1 1 // 单词4 1 3 // 单词5

5. 代码风格与工程实践

5.1 现代C++实践

可以进一步改进的编码风格：

1. 使用更明确的变量名：

vector<int> wordCount(MAXM); vector<int> documentCount(MAXM);

2. 使用范围for循环：

for(auto word : documentWords){ wordCount[word]++; }

3. 添加输入校验：

if(len <0 || len >100){ cerr << "Invalid document length" << endl; return 1; }

5.2 可扩展性考虑

如果问题规模扩大：

1. 可以使用unordered_map代替数组，支持更大的单词ID范围
2. 可以并行处理不同篇章，最后合并结果
3. 对于超大规模数据，可以考虑外排序和MapReduce

5.3 实际应用场景

类似的词频统计算法常用于：

1. 搜索引擎的倒排索引构建
2. 文本分类的特征提取
3. 关键词提取和文本摘要
4. 抄袭检测和文本相似度计算

在实际工程中，还需要考虑：

1. 单词归一化（大小写、词形等）
2. 停用词过滤
3. 分布式处理框架
4. 持久化存储和增量更新

6. 解题心得与经验分享

在解决这类统计问题时，我的经验是：

1. 明确统计维度：在本题中需要同时统计两个不同维度的数据（总次数和篇章数），需要设计合适的数据结构同时记录这些信息。

2. 选择合适的数据结构：根据数据规模和访问模式选择数组、哈希表等。本题因为单词ID范围已知且较小，使用数组是最佳选择。

3. 注意更新时机：篇章数的统计需要在处理完整个篇章后才能确定，因此需要临时存储当前篇章的单词出现情况。

4. 测试要充分：特别是边界情况，如空输入、最大规模输入、重复单词等。

5. 代码可读性很重要：虽然竞赛中常常使用短变量名，但适当添加注释和合理的命名习惯能减少错误。

这类基础算法题在面试和竞赛中很常见，掌握好这类问题的解决模式，可以举一反三应用到更复杂的问题中。建议初学者多练习类似的统计问题，培养对数据流动的敏感度。