洛谷 P9868 [NOIP2023] 词典

原文链接：NOIP真题第四讲：词典

题目来源：2023 年 NOIP T1

本题考察点：【贪心、枚举、模拟】

前置知识

字典序：指按照a、b、c、...、z的顺序，即a<b<c<...<z；

一、题目及链接

题目链接：

https://www.luogu.com.cn/problem/P9868

题意：题意很简单，但是描述很复杂，这也是真题的一大特点吧！题目意思是给n个单词，用每个单词去和其他的n-1个单词比较，比较的时候可以随意排序，如果当前单词排序后字典序小于其余n-1个单词，那么输出1，否则输出0；

二、题目分析

此题需要用到【贪心】思想，即当前单词与其他n-1个单词比较的时候，当前单词从小到大排序，其他单词从大到小排序即可，这样对于当前单词即为最优情况。

思考一下，如果需要比较两个字符串的字典序大小，不需要比较整个字符串，比如当前用单词word1和其他n-1个单词比较的时候，只需要使用word1的最小的字母和其他单词的最大的字母比较，如果word1的最小字母大于等于其他某个单词wordx的最大字母，那么word1的最优字典序一定大于wordx的最优字典序，直接输出0，结束比较，否则word1的最小字母小于wordx的最大字母，那么可以让word1的最小字母排最前面，wordx的最大字母排最前面，即可满足题目所说的性质。

栗子1：word1="hddx"，wordx="abd"，word1的最小字母为d，wordx的最大字母为d，不管如何对word1和wordx排序，都无法得到word1的字典序小于wordx；

栗子2：word1="dxa"，wordx="bdx"，word1的最小字母为a，wordx的最大字母为x，因为可以让word1排序为"adx"，wordx排序为"xdb"，那么此时word1的字典序小于wordx的字典序；

三、AC Code


#include "iostream"
#include "cstdio"
using namespace std;
const int N = 3010;
struct word{char minChar = 'z', maxChar = 'a';  // 初始值
}dict[N];
int n, m;
char c;
// check函数：如果第x个单词排序后无法小于第y个单词的排序，那么返回true，否则返回false
bool check(int x, int y) {return dict[x].minChar >= dict[y].maxChar;  // 只需要比较第x个单词的最小字母和第y个单词的最大字母即可
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> c;if(dict[i].minChar > c) dict[i].minChar = c;if(dict[i].maxChar < c) dict[i].maxChar = c;}}for (int i = 1; i <= n; i++) {bool f = true;for (int j = 1; j <= n; j++) {if (i == j) continue;  // 单词本身不和自己比if (check(i, j)) {   // 如果第i个单词和第j个单词不满足题目性质f = false;  // 置为false，直接breakbreak;}}cout << f;  // f为当前第i个单词和其他单词比较完的结果}return 0;
}