病毒 (virus)
题目描述
题目描述
有一天，小y 突然发现自己的计算机感染了一种病毒！ 还好，小y 发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。
现在怎么恢复原来的文档呢？小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照 字母顺序 排列的。他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的 有序性(之前的字母顺序)，找到病毒替换字母的规律，再用来恢复其它文档。
现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。
输入格式
第一行为整数
K(K≤50000)，表示字典中的单词个数。
以下K 行，是被病毒感染了的字典，每行一个单词。
最后一行是需要你恢复的一串字母。
数据保证 所有字母均为小写。
输出格式
输出仅一行，为恢复后的一串字母。
当然也有可能出现字典不完整、甚至字典是错的情况，这个时候只输出一个0。
样例
样例输入6
cebdbac
cac
ecd
dca
aba
bac
cedab样例输出
abcde
分析
题目的大概意思
每个字母都被其他字母所代替，根据已经排序好的单词确定字母变化的规律，恢复被感染的字母串。
思路
这道题是道 拓扑排序。
既然题目给出的单词是排序好的，我们可以把 字典序小的字母 看成是 字典序大的字母 的入度。
根据拓扑排序求出每个字母对应字母。
由于题目没有保证字母一定是
a,b,c,⋅⋅⋅⋅⋅⋅，z 这样的顺序，所以我们需要把计算过的字母保存起来，判断是否出现过即可(可以只判断计算了入度和出度的字母)。
如果某个字母出现过，那么就将字母的个数 (假设记作
cnt)
cnt+1。
接着使用拓扑排序，用
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];bool toposort()
{
int cnt = 0;
for (int i = 1; i <= 26; i++)
if (vis[i]) ++cnt;
for (int i = 1; i <= cnt; i++) // 循环的是字母表第i个字母
{
int k = 1;
while (k <= 26 && (in[k] || !vis[k])) ++k; // 如果这个字母不是当前最小的或者没有被算过则跳过
if (k > 26) return 0;
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");
else
for (int i = 0; i < lenw; i++) // 输出
cout << ans[i];
return 0;
}关注博主即可阅读全文
原创：https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说
免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。
您必须遵守我们的协议，如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源www.panoramacn.com资源全部来自互联网收集，仅供用于学习和交流，请勿用于商业用途。如有侵权、不妥之处，请联系站长并出示版权证明以便删除。 敬请谅解！ 侵权删帖/违法举报/投稿等事物联系邮箱：2640602276@qq.com未经允许不得转载：书荒源码源码网每日更新网站源码模板！ » 兔兔 的 题解 —— 病毒 (virus)
关注我们小说电影免费看关注我们，获取更多的全网素材资源，有趣有料！120000+人已关注
评论抢沙发