题解 | #小红背单词#

1. 问题分析

本问题的核心在于动态阈值的状态演变。传统的单词计数问题通常是静态频率统计，而本题引入了基于当前状态（已掌握单词数量 ）的递增记忆成本（需背诵新单词 次）。

核心约束：

• 输入规模（）： 线性或接近线性的复杂度即可满足需求。
• 字符串长度（）： 字符串哈希计算与比较的开销极低，可视为常数项。
• 状态依赖（）： 判定一个单词是否“被记住”的阈值是随时间动态增加的。这意味着处理顺序不可置换，必须采用在线处理（Streaming/Online Processing）策略。

2. 算法：状态化贪心模拟

由于背诵过程具有严格的时间顺序依赖，且当前动作的影响仅取决于过去累计的结果（已记住的单词总数），问题的本质是一个带状态转移的模拟模型。

混合哈希映射

我们选择使用一个哈希集合（HashSet）记录“已完全记住的单词”，并使用一个哈希映射（HashMap）记录“正在记忆中的新单词及其出现频次”。

1. 去重高效性： 已经记住的单词不再参与后续逻辑，通过 HashSet 实现 级别的快速过滤。
2. 计数动态化： 只有未进入已掌握库的单词才会进行计数累加，并与当前的动态阈值进行匹配。
3. 确定性： 模拟策略能完美复现题目描述的背诵逻辑，且无须任何回溯或复杂的数据结构。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int learned = 0;
    unordered_set<string> learned_words;
    unordered_map<string, int> staged_cnt;

    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        if (learned_words.count(word) > 0)
            continue;
        staged_cnt[word]++;
        if (staged_cnt[word] == learned + 1) {
            learned++;
            learned_words.insert(word);
            staged_cnt.erase(word);
        }
    }

    cout << learned << endl;
}

4. 复杂度分析

时间复杂度：

• 单次处理： 每次处理单词涉及哈希表的查找（Containment Check）、更新（Update Count）或插入（Set Insert），在平均情况下耗时 ，其中 为字符串长度。
• 全量处理： 针对 个单词，总复杂度为 。

空间复杂度：

• 存储开销： 其中 为输入中唯一单词的数量。
• 构成：
  • learned_words 最多存储 个单词。
  • staged_counts 在最坏情况下（没有单词达到阈值）存储 个单词的计数。