本文共 3399 字，大约阅读时间需要 11 分钟。

文档恢复

题目链接：

题目大意

有一个规则，原来的字母会变成规定的另一种，不会有两个字母变成相同的字母。

思路

大概就是先通过给出的字典序进行判断，求出两个字符之间的字典序大小关系。

然后你就大概想拓扑一样，每次找比其他所有字符都大的点。

然后每次这个点只能有一个，否则就会有多组解。（其实就是一个找链的过程）

然后你每次找到就给他记录它是字典序第几大的，然后把这个点删掉。

最后你就读入要翻译的字符串，然后按你记录的转，再输出就可以了。

记得出现的字母不一定是从 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;}