B4262 [GESP202503 三级] 词频统计

chen_zhe · 2025-05-09 22:12:28 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

:::align{center} :::

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

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

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

for (int i = 0; i < n; ++i) {
    cin >> s[i]; // 读入第 i 个单词
    for (int j = 0; j < s[i].length(); ++j) {
        if (s[i][j] >= 'A' && s[i][j] <= 'Z')
            s[i][j] = s[i][j] - 'A' + 'a';
            //将 s[i] 转为小写。也可以使用 cctype 库的 tolower() 函数，例如 s[i] = tolower(s[i]);
    }
}

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

for (int i = 0; i < n; ++i) {
    int cur_c = 0; // 当前单词 s[i] 的出现次数
    for (int j = 0; j < n; ++j) {
        if (s[i] == s[j])
            cur_c++;
    }
    if (cur_c > max_c) {
        max_c = cur_c; // 最大出现次数
        ans_s = s[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;
    }
}

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