兔兔 的 题解 ——病毒 (virus)

病毒 (virus)

题目描述

题目描述
有一天，小y 突然发现自己的计算机感染了一种病毒！ 还好，小y 发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。
现在怎么恢复原来的文档呢？小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照 字母顺序 排列的。他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的 有序性(之前的字母顺序)，找到病毒替换字母的规律，再用来恢复其它文档。
现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。

输入格式

第一行为整数 $K(K \leq 50000)$，表示字典中的单词个数。
以下 $K$ 行，是被病毒感染了的字典，每行一个单词。
最后一行是需要你恢复的一串字母。
数据保证 所有字母均为小写。

输出格式

输出仅一行，为恢复后的一串字母。
当然也有可能出现字典不完整、甚至字典是错的情况，这个时候只输出一个 $0$。

样例

样例输入

6
cebdbac
cac
ecd
dca
aba
bac
cedab

样例输出

abcde

分析

题目的大概意思

每个字母都被其他字母所代替，根据已经排序好的单词确定字母变化的规律，恢复被感染的字母串。

思路

这道题是道 拓扑排序。
既然题目给出的单词是排序好的，我们可以把 字典序小的字母 看成是 字典序大的字母 的入度。
根据拓扑排序求出字母每个对应字母。
由于题目没有保证字母一定是 $a, b, c, ······， z$，所以我们需要把计算过的字母保存起来，判断是否出现过(可以只判断计算了入度和出度的字母)。
如果某个字母出现过，那么就将字母的个数 $+1$(假设记作 $cnt$)。
接着使用拓扑排序，用 $i$ 循环 $cnt$ 次，每次找出没有入度的字母，也就是当前没有计算过的字母中最小的那个，这个字母对应的答案为 $i + 96$ $(i + 'a' - 1)$。
最后再判断一下需要还原的字符串中的每个字母是否都有对应的答案：

• 如果不是，就输出 $0$。
• 否则，就输出每个字母对应的答案。

正解代码如下：

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;const int MAXK = 5e4 + 5;
int K;
string S[MAXK], Word;
string ans[MAXK];
vector<int> W[MAXK];
map<char, char> mp;
int in[MAXK], lenw;
bool vis[MAXK], check[MAXK];bool toposort()
{int cnt = 0;for (int i = 1; i <= 26; i++)if (vis[i]) ++cnt;for (int i = 1; i <= cnt; i++){int k = 1;while (k <= 26 && (in[k] || !vis[k])) ++k;if (k > 26) return 0; // 如果 k > 26, 说明没有字母符合条件, 即不成立mp[k + 'a' - 1] = i + 'a' - 1;vis[k] = 0;int siz = W[k].size();for (int j = 0; j < siz; j++)--in[W[k][j]];}for (int i = 0; i < lenw; i++){if (!mp[Word[i]]) return 0;ans[i] = mp[Word[i]];}return 1;
}int main()
{scanf("%d", &K);for (int i = 1; i <= K; i++){cin >> S[i];int len = min(S[i - 1].length(), S[i].length());for (int j = 0; j < len; j++){if (S[i - 1][j] != S[i][j]){int w1 = S[i - 1][j] - 'a' + 1;int w2 = S[i][j] - 'a' + 1;W[w1].push_back(w2), ++in[w2];vis[w1] = vis[w2] = 1;break;}}}cin >> Word;lenw = Word.length();if (!toposort()) printf("0");elsefor (int i = 0; i < lenw; i++)cout << ans[i];return 0;
}