NOIP2023词典问题终极指南：从字符频率统计到字典序比较的完整解析 | 算法竞赛必备技能

4天前比赛题解55

一、问题理解与算法思路

词典问题要求判断每个单词是否存在一种排列方式，使其字典序严格小于其他所有单词的所有可能排列。核心思路是通过预处理每个单词的最小和最大字典序排列，然后进行高效比较。

关键算法步骤：

预处理每个单词的字符频率
生成最小和最大字典序排列
并行比较所有单词的边界情况

二、完整代码实现（带详细注释）

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

int main() {
    ios::sync_with_stdio(false);  // 关闭同步提升IO速度
    cin.tie(nullptr);             // 解除cin和cout的绑定
    
    int n, m;  // n:单词数量 m:单词长度(题目未实际使用)
    cin >> n >> m;
    vector<string> words(n);  // 存储所有单词
    // 使用short类型节省空间，存储每个单词的字符频率
    vector<vector<short>> min_chars(n, vector<short>(26, 0));
    vector<vector<short>> max_chars(n, vector<short>(26, 0));
    
    // 预处理字符频率统计
    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;
    }
    
    // 并行比较优化：检查每个单词的最小字典序是否小于其他所有单词的最大字典序
    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]) {  // 字典序比较
                valid = false;
                break;
            }
        }
        result[i] = valid ? '1' : '0';  // 设置结果位
    }
    
    cout << result << '\n';  // 输出结果
    return 0;
}