本文共 3399 字，大约阅读时间需要 11 分钟。
有一个规则，原来的字母会变成规定的另一种，不会有两个字母变成相同的字母。
然后按顺序给出按原来的字典序排好的字符串，然后再给你一个字符串，要你还原出边之前的。 如果无解或者有多组解就输出 0。大概就是先通过给出的字典序进行判断，求出两个字符之间的字典序大小关系。
（记得如果矛盾就直接是 0）然后你就大概想拓扑一样，每次找比其他所有字符都大的点。
（具体就是在你求出的大小关系中，它一定会至少大于一个点，且一定不会小于任何点）然后每次这个点只能有一个，否则就会有多组解。（其实就是一个找链的过程）
然后你每次找到就给他记录它是字典序第几大的，然后把这个点删掉。
最后你就读入要翻译的字符串，然后按你记录的转，再输出就可以了。
记得出现的字母不一定是从 a 开始顺着下来的，所以你还要记录一下字典序第 i 大变化前是哪个字符。
#include#include using namespace std;int a, k, root = -1, ans[500001];int gx[31][31], dy[31], sn, mb[31];char c[500001][101], ac[500001];bool noans, cx[31];void work(int deg, int l, int r) { //得出关系 if (l == r || l > r) return ; if (noans) return ; if (!c[l][deg - 1]) return ; int last = l; for (int i = l + 1; i <= r; i++) if (c[i][deg] != c[last][deg]) { if (!c[last][deg]) { last = i; continue; } cx[c[last][deg] - 'a'] = 1; work(deg + 1, last, i - 1); if (!c[i][deg]) { last = i; continue; } cx[c[i][deg] - 'a'] = 1; if (gx[c[i][deg] - 'a'][c[last][deg] - 'a'] == 1) { //关系与之前矛盾 noans = 1; return ; } gx[c[i][deg] - 'a'][c[last][deg] - 'a'] = -1;//确立关系 gx[c[last][deg] - 'a'][c[i][deg] - 'a'] = 1; last = i; } work(deg + 1, last, r);//记得最后那一段}int main() { // freopen("resume.in", "r", stdin);// freopen("resume.out", "w", stdout); memset(dy, -1, sizeof(dy)); scanf("%d %d", &a, &k); for (int i = 1; i <= k; i++) scanf("%s", &c[i]); int last = 1;//同上，只是一开始处理大序列的 for (int i = 2; i <= k; i++) { if (c[i][0] != c[last][0]) { cx[c[i][0] - 'a'] = 1; cx[c[last][0] - 'a'] = 1; work(1, last, i - 1); if (noans) break; if (gx[c[i][0] - 'a'][c[last][0] - 'a'] == 1) { noans = 1; break; } gx[c[i][0] - 'a'][c[last][0] - 'a'] = -1; gx[c[last][0] - 'a'][c[i][0] - 'a'] = 1; last = i; } } work(1, last, k);//记得最后那一段 if (noans) { //产生了矛盾 printf("0"); return 0; } for (int i = 0; i < 26; i++)//记录按字典序排下来是那些字母 if (cx[i]) mb[++mb[0]] = i; for (int I = 1; I <= mb[0]; I++) { int i = mb[I]; bool yes = 1, have = 0; for (int j = 0; j < 26; j++) if (gx[i][j] == -1) { yes = 0; break; } else if (gx[i][j] == 1) { have = 1; } if (yes && have) { if (root != -1) { //有多组解（建图的话就是多个连通块） printf("0"); return 0; } root = i; } else if (yes && !have) { //多组解 printf("0"); return 0; } } if (root == -1) { //矛盾（图就是成了环） printf("0"); return 0; } dy[root] = 1; for (int i = 0; i < 26; i++)//取消掉这个点 gx[i][root] = gx[root][i] = 0; for (int I = 2; I < a; I++) { //刚刚的是确立字典序最小的，接着就是确立后面的 root = -1; for (int II = 1; II <= mb[0]; II++) { int i = mb[II]; if (dy[i] != -1) continue; bool yes = 1, have = 0; for (int j = 0; j < 26; j++) if (gx[i][j] == -1) { yes = 0; break; } else if (gx[i][j] == 1) { have = 1; } if (yes && have) { if (root != -1) { printf("0"); return 0; } root = i; } else if (yes && !have) { printf("0"); return 0; } } if (root == -1) { printf("0"); return 0; } dy[root] = I; for (int i = 0; i < 26; i++) gx[i][root] = gx[root][i] = 0; } for (int I = 1; I <= mb[0]; I++) { int i = mb[I]; if (dy[i] == -1) { dy[i] = a; break; } } scanf("%s", &ac);//读入，复原 sn = strlen(ac); for (int i = 0; i < sn; i++) ans[i] = dy[ac[i] - 'a']; for (int i = 0; i < sn; i++) putchar(mb[ans[i]] + 'a'); fclose(stdin); fclose(stdout); return 0;}
转载地址：http://mgvh.baihongyu.com/