NOIP2023词典问题：从字符频率统计到字典序比较的完整解析

19339201706 · 发表于 4 天前

一、问题理解与算法思路

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

关键算法步骤：

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

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

#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;
}

复制代码

三、算法核心解析

字符频率统计：使用两个26长度的数组记录每个字母出现次数
字典序边界生成：
- 最小字典序：字母升序排列(a-z)
- 最大字典序：字母降序排列(z-a)
并行比较优化：通过边界比较避免枚举所有排列组合

四、复杂度分析与优化

时间复杂度：O(n^2 * m)，其中n是单词数，m是单词长度
空间优化：使用short类型存储字符频率
IO优化：使用ios::sync_with_stdio加速输入输出

五、常见问题解答

Q：为什么要生成最小和最大字典序？ A：这样可以通过边界比较确定是否存在满足条件的排列，避免检查所有可能排列。

Q：如何处理特殊字符或大写字母？ A：题目限定小写字母，实际应用中可扩展ASCII码范围。

Q：算法是否可以进一步优化？ A：可以尝试使用字典树(Trie)或更高效的数据结构优化比较过程。

来源：NOIP2023词典