【题解】LuoGu6286：Cezar

原题传送门 一开始看错了题意，错以为是每个字符串里面加密后排序 后来才发现是字符串之间排序 那么对于两个字符串$s_{a_i},s_{a_{i+1}}$，加密后的$s_{a_i}$的字典序要小于$s_{a_{i+1}}$ 可以从最高位开始比较，第一位不同的字符，比如是$c1,c2$，说明加密后的$c1<c2$，就从$c1$往$c2$连一条有向边

最终做一遍拓扑构造答案 如果有点的入度不为0，说明有环，是无解的 否则就输出构造的方案

中间我还判断了一下如果相邻的两个字符串只有长度不一样无解的情况

这道题目非常暴力，复杂度$O(n)$

Code：

#include <bits/stdc++.h> #define maxn 1010 using namespace std; struct Edge{ int to, next; }edge[maxn * maxn]; int num, head[maxn], f[maxn], n, d[maxn], a[maxn], s[maxn][maxn], cnt[maxn]; char ans[maxn], S[maxn]; char st[maxn][maxn]; queue <int> q; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int get(){ char c = getchar(); for (; c < 'a' || c > 'z'; c = getchar()); return c - 'a' + 1; } bool check(int x, int y){ if (x == y) return 1; for (int i = head[x]; i; i = edge[i].next) return check(edge[i].to, y); } int getfa(int k){ return k == f[k] ? k : f[k] = getfa(f[k]); } void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; } int main(){ freopen("cezar.in", "r", stdin); freopen("cezar.out", "w", stdout); n = read(); for (int i = 1; i <= n; ++i){ scanf("%s", st[i] + 1); cnt[i] = strlen(st[i] + 1); for (int j = 1; j <= cnt[i]; ++j) s[i][j] = st[i][j] - 'a' + 1; } for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = 1; i <= 26 * 2; ++i) f[i] = i; for (int i = 1; i < n; ++i){ int idx = a[i], idy = a[i + 1]; int l1 = cnt[idx], l2 = cnt[idy]; int x = 0, y = 0; for (int j = 1; j <= min(l1, l2); ++j) if (s[idx][j] != s[idy][j]){ x = s[idx][j], y = s[idy][j]; break; } if (x == 0 && y == 0){ if (l1 > l2){ puts("NE"); return 0; } continue; } addedge(x, y), ++d[y]; } for (int i = 1; i <= 26; ++i) if (!d[i]) q.push(i); char c = 'a'; while (!q.empty()){ int u = q.front(); q.pop(); ans[u] = c, ++c; for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to; --d[v]; if (!d[v]) q.push(v); } } for (int i = 1; i <= 26; ++i) if (d[i]) return puts("NE"), 0; puts("DA"); for (int i = 1; i <= 26; ++i) printf("%c", ans[i]); return 0; }