C++ 标准解答 (NOIP C++14)

/**
 * 题目: 翰林院的《韵书》编纂 (Sorted Word Frequency)
 * 知识点: std::map 的自动排序特性
 */

#include <iostream>
#include <string>
#include <map> // 包含有序映射头文件

using namespace std;

int main() {
    // 1. IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 2. 定义有序映射
    // Key: string (拼音)
    // Value: int (次数)
    // std::map 底层是红黑树，Key 会自动按字典序排列
    map<string, int> rhyme_book;

    // 3. 读取并统计
    for (int i = 0; i < n; i++) {
        string pinyin;
        cin >> pinyin;
        
        // 插入/更新操作 O(log M)，其中 M 是不同拼音的数量
        rhyme_book[pinyin]++;
    }

    // 4. 遍历输出
    // std::map 的迭代器会严格按照 Key 的顺序遍历
    // auto const& [key, val] 是 C++17 的结构化绑定写法
    // NOIP C++14 可以用 iterator 或 pair 写法，如下：
    
    for (auto const& pair : rhyme_book) {
        // pair.first 是 key (拼音)
        // pair.second 是 value (次数)
        cout << pair.first << " " << pair.second << endl;
    }

    return 0;
}

数据生成器 (Generator)

生成器会从拼音库中随机抽取，生成乱序的输入，用来验证 map 的排序能力。

请保存为 gen_map.cpp 并运行。

/**
 * Project: The Rhyme Book (Ordered Map Data Generator)
 * Author: Isaac Asimov (AI)
 */

#include <iostream>
#include <fstream>
#include <random>
#include <string>
#include <vector>
#include <map>

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int n;
        cin >> n;
        map<string, int> m;
        for(int i=0; i<n; i++) {
            string s; cin >> s;
            m[s]++;
        }
        
        // 输出必须是有序的
        for(auto const& p : m) {
            cout << p.first << " " << p.second << endl;
        }
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

// 常见文言文拼音
vector<string> pinyins = {
    "zhi", "hu", "zhe", "ye", "yi", "yan", "zai",
    "gong", "shang", "jue", "zhi", "yu", // 五音
    "tian", "di", "xuan", "huang",       // 天地玄黄
    "yu", "zhou", "hong", "huang",       // 宇宙洪荒
    "ri", "yue", "ying", "ze",           // 日月盈昃
    "chen", "xiu", "lie", "zhang",       // 辰宿列张
    "han", "lai", "shu", "wang"          // 寒来暑往
};

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    int n;

    if (case_id == 1) {
        // 样例复现
        n = 8;
        fout << n << endl;
        fout << "zhi\nhu\nzhe\nye\nzhi\nhu\nyi\nyan" << endl;
        fout.close();
        return;
    }
    else if (case_id <= 3) {
        n = 20;
    } 
    else if (case_id <= 7) {
        n = 1000;
    } 
    else {
        n = 100000; // 压力测试
    }

    fout << n << endl;

    for (int i = 0; i < n; i++) {
        string s;
        if (rand_int(1, 100) <= 80) {
            // 80% 从库里选，保证重复率
            s = pinyins[rand_int(0, pinyins.size() - 1)];
        } else {
            // 20% 生成随机拼音 (a-z 的随机组合)
            // 这样能测试排序逻辑对生僻字符串的处理
            int len = rand_int(2, 5);
            for(int k=0; k<len; k++) s += (char)('a' + rand_int(0, 25));
        }
        fout << s << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Rhyme Book Data ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

阿西莫夫的点评

1. 为什么要有序？ 在处理文言文或任何语言学资料时，索引（Index） 是必不可少的。一本没有按拼音或部首排序的字典，跟一堆废纸没有区别。std::map 完美模拟了建立索引的过程。
2. 代价是什么？ std::map 的插入和查询复杂度是 $O(\log N)$，而 unordered_map 是 $O(1)$。 为了获得“有序”这个属性，我们付出了一点点时间代价。但在需要输出排序结果的场景下，这比“先用 Hash 统计再把结果拷出来排序”要优雅和高效得多。

希望这道题能让学生体会到，数据结构不仅仅是存数据的地方，它们本身就蕴含着组织信息的哲学。