【NOIP 2023】词典题（洛谷P9868）解题思路与代码实现详解

一、题目解读

2023年NOIP中的词典题（洛谷P9868）要求判断给定n个单词是否存在一种字典序排列，使得每个单词在排序后都不包含另一个单词。题目核心在于理解字典序与字符包含关系的约束，需通过高效算法确定是否存在合法排列。

二、解题思路

采用“预处理字符频率+边界构建+并行比较”的策略：

1. 利用vector存储单词及字符频率，使用short优化空间；

2. 构建每个单词的最小字典序（按字符频率升序排列）和最大字典序（降序）；

3. 通过并行比较各单词的边界：若单词i的最小字典序≥单词j的最大字典序，则i与j可共存，最终输出二进制结果串。

三、解题步骤详解

1. 输入处理：读取n和m（实际为n个单词），存储单词并初始化频率矩阵；

2. 字符频率预处理：遍历单词，统计各字母出现次数，同时更新min_chars和max_chars；

3. 构建字典序边界：生成每个单词的最小/最大字典序字符串（min_words/max_words）；

4. 并行比较优化：对每个单词i，遍历其他单词j，判断min_words[i]≥max_words[j]是否成立，标记合法性；

5. 输出结果：将二进制合法性串输出。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 优化输入输出速度

    int n, m;
    cin >> n >> m;
    vector<string> words(n);
    vector<vector<short>> min_chars(n, vector<short>(26, 0)); // 存储每个单词的最小字符频率
    vector<vector<short>> max_chars(n, vector<short>(26, 0)); // 存储每个单词的最大字符频率

    // 预处理字符频率（使用short节省空间）
    for (int i = 0; i < n; ++i) {
        cin >> words[i];
        for (char c : words[i]) { // 遍历单词字符
            min_chars[i][c - 'a']++; // 统计最小频率
            max_chars[i][c - 'a']++; // 统计最大频率
        }
    }

    // 预处理所有单词的字典序边界
    vector<string> min_words(n), max_words(n);
    for (int i = 0; i < n; ++i) {
        // 构建最小字典序
        for (int c = 0; c < 26; ++c) {
            min_words[i] += string(min_chars[i][c], 'a' + c); // 按频率升序拼接
        }
        // 构建最大字典序
        for (int c = 25; c >= 0; --c) {
            max_words[i] += string(max_chars[i][c], 'a' + c); // 按频率降序拼接
        }
    }

    string result(n, '0');
    if (n == 1) {
        cout << "1\n";
        return 0; // 特判n=1直接输出合法
    }

    // 并行比较优化
    for (int i = 0; i < n; ++i) {
        bool valid = true;
        for (int j = 0; j < n; ++j) {
            if (i == j) continue; // 跳过自身比较
            if (min_words[i] >= max_words[j]) { // 若i的最小字典序≥j的最大字典序
                valid = false;
                break; // 标记不合法并跳出
            }
        }
        result[i] = valid? '1' : '0'; // 更新结果串
    }

    cout << result << '\n';
    return 0;
}

五、总结

该解法巧妙利用字符频率边界与字典序比较，通过并行优化降低时间复杂度至O(n^2)，配合short类型节省空间。对于NOIP竞赛中的中等难度题目，此代码兼顾效率与可读性，是解决词典题的经典思路。进一步优化可考虑更高效的比较算法（如二分查找），但现有方案已满足题目要求。