洛谷 P9868 [NOIP2023] 词典

好久不写博客了，今天来水一篇

原题链接

初看此题在洛谷上的定位是黄题，实际上也并不是很简单。

其实主要就用到了贪心的思想，先说一下我在做题的时候是怎么想的吧。

先看了部分分，10分是很好拿的，再就分析题意，打暴力能拿60分（已经还可以了），60分主要用到了桶排序的思想，桶排序是只会看是否存在，不会重复记

60pts：（缺少了判断i！=j的情况）

#include<bits/stdc++.h>
using namespace std;
int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}while (ch <= '9' && ch >= '0') {x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
const int N = 3010;
string s[N];
int cnt[26];
int n, m;
int main() {n = read(), m = read();string mins = "";for (int i = 0; i < 3000; i++) {mins += "z";}for (int i = 1; i <= n; i++) {cin >> s[i];if (mins > s[i]) {mins = s[i];}}for (int i = 1; i <= n; i++) {int len = s[i].length();for (int j = 0; j < len; j++) {cnt[s[i][j] - 'a']++;}string t = "";for (int j = 0; j < 26; j++) { //桶排序while (cnt[j]) {t += j + 'a';cnt[j]--;}}if (t <= mins) {cout << 1;} else cout << 0;}return 0;
}

接下来就是正解：直接把每个字符串wi都从小到大或者从大到小排一下，记作ai，bi。如果bi小于除了i之外的所有ai，说明可以，否则不可以。求一个前后缀最大值即可。复杂度为O（26n+nm）

100pts：

#include<bits/stdc++.h>
using namespace std;
inline int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();return x * f;
}
const int N=3005;
char s[N];
char mx[N][N], mn[N][N];
char  pr[N][N], sf[N][N];
int c[35];
int  main() {int n = read(), m = read();for (int i = 1; i <= n; i++) {scanf("%s", s);int pmx = 0, pmn = 0;for (int j = 0; j < m; j++)c[s[j] - 'a']++;for (int j = 25; j >= 0; j--) {while (c[j])mx[i][pmx++] = j + 'a', c[j]--;}for (int j = 0; j < m; j++)c[s[j] - 'a']++;for (int j = 0; j <= 25; j++) {while (c[j])mn[i][pmn++] = j + 'a', c[j]--;}}for (int j = 0; j < m; j++)pr[1][j] = mx[1][j];for (int i = 2; i <= n; i++) {int flag = 0;for (int j = 0; j < m; j++) {if (pr[i - 1][j] < mx[i][j]) {flag = 0;break;} else if (pr[i - 1][j] > mx[i][j]) {flag = 1;break;}}if (!flag) {for (int j = 0; j < m; j++)pr[i][j] = pr[i - 1][j];} else {for (int j = 0; j < m; j++)pr[i][j] = mx[i][j];}}for (int j = 0; j < m; j++)sf[n][j] = mx[n][j];for (int i = n - 1; i >= 1; i--) {int flag = 0;for (int j = 0; j < m; j++) {if (sf[i + 1][j] < mx[i][j]) {flag = 0;break;} else if (sf[i + 1][j] > mx[i][j]) {flag = 1;break;}}if (!flag) {for (int j = 0; j < m; j++)sf[i][j] = sf[i + 1][j];} else {for (int j = 0; j < m; j++)sf[i][j] = mx[i][j];}}for (int i = 1; i <= n; i++) {int flag = 1;if (i > 1) {int tag = 0;for (int j = 0; j < m; j++) {if (mn[i][j] > pr[i - 1][j]) {tag = 0;break;} else if (mn[i][j] < pr[i - 1][j]) {tag = 1;break;}}flag &= tag;}if (i < n) {int tag = 0;for (int j = 0; j < m; j++) {if (mn[i][j] > sf[i + 1][j]) {tag = 0;break;} else if (mn[i][j] < sf[i + 1][j]) {tag = 1;break;}}flag &= tag;}if (flag)cout<<1;else cout<<0;}return 0;
}