B4262 [GESP202503 三级] 词频统计

· · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

本题考察枚举法和字符串。

既然我们要找出哪个单词出现次数最多，一个最直接的想法就是：我们拿起第一个单词，然后把它和后面所有的单词都比一比，看看有多少个和它一样。数完之后，我们记下来这个单词和它的出现次数。接着，我们拿起第二个单词，也把它和后面所有的单词比一比，数数它出现了多少次，以此类推……

在本题中，忽略单词中字母的大小写，因此我们可以先把字符串全部转为小写字符后进行处理。

for (________) {
    cin >> s[i]; // 读入第 i 个单词
    for (________) { // 将 s[i] 转为小写字符串。
        if (________) 
            ________;

    }
}

接着，我们枚举每一个单词，将其与其他单词作比较，统计这个单词出现了多少次。这部分的参考代码：

for (int i = 0; i < n; ++i) {
    int ________; // 计数器 
    for (int j = 0; j < n; ++j) {
        ________
        ________ // 判断第 i 个单词出现了多少次
    }
    ________ 
    ________ // 判断最大出现次数，更新答案
}

这样，我们就完成了这个试题。

接下来介绍一个不在 GESP 考纲内的做法。

如果你学习过 C++ STL 的 map 的话，本题会更加轻松。我们创建一个 map，它的“键”是 string 类型（用来存小写单词），“值”是 int 类型（用来存次数），例如 map<string, int> cnt;。我们把它当作一个“桶”进行计数即可。

例如，读入字符串将其转为小写之后，可以使用 cnt[s]++;，记录单词 s 的出现次数。读入完毕之后，使用迭代器扫描整个 map，得到最大出现次数即可。参考代码（需要 C++11 语法标准）：

for (auto it = cnt.begin(); it != cnt.end(); ++it) {
    // it->first  就是单词
    // it->second 就是次数
    if (it->second > max_c) {
        max_c = it->second;
        ans_s = it->first;
    }
}

这样，我们就使用了两种方式，完成这一个试题。