A28836. 病毒(virus)
填空题
困难
知识点
题目描述
病毒(virus)
题目描述
有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。
现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其它文档。
现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。
输入
第一行为整数K（≤50000），表示字典中的单词个数。
以下K行，是被病毒感染了的字典，每行一个单词。
最后一行是需要你恢复的一串字母。
所有字母均为小写。
输出
输出仅一行，为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况，这时请输出一个0。
输入样例
6
cebdbac
cac
ecd
dca
aba
bac
cedab输出样例
abcde参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 30
int edge[N][N], deg[N];
set<int> st;//保存被感染后的所有字符
map<char, char> mp;//mp[i]：感染后的字符i原来是什么字符
bool topoSort()//如果返回值为false，则该有向图没有拓扑排序或没有唯一拓扑排序
{
int ct = 0;
char alph = 'a';
queue<int> que;
for(int v : st) if(deg[v] == 0)
{
que.push(v);
ct++;
}
if(ct > 1)//入度为0的应该只有1个
return false;
while(!que.empty())
{
int u = que.front();
que.pop();
mp[u+'a'] = alph++;//拓扑排序序列对应a,b,c...
ct = 0;
for(int v : st) if(edge[u][v] && --deg[v] == 0)
{
que.push(v);
ct++;
}
if(ct > 1)//删掉u后，入度为0的应该只有1个
return false;
}
return mp.size() == st.size();//st中每个字符都有对应的字符，图中才没有环，是完成了拓扑排序
}
int main()
{
string s, ls, t;//ls：上一个字符串
int k;
cin >> k;
for(int j = 1; j <= k; ++j)
{
cin >> s;
for(char c : s)//把所有感染后的字符串中的字符加入st
st.insert(c-'a');
if(j == 1)//第一次循环只记录ls
{
ls = s;
continue;
}
for(int i = 0; i < s.length(); ++i)
{
if(s[i] != ls[i])
{
if(ls[i] != '\0')
{
edge[ls[i]-'a'][s[i]-'a'] = 1;//ls[i]到s[i]有一条边
deg[s[i]-'a']++;
}
break;
}
}
ls = s;
}
cin >> t;//待转换字符串
bool hasAns = topoSort();
for(char c : t) if(st.count(c-'a') == 0)//如果出现不存在的字符
hasAns = false;
if(hasAns)
for(char c : t)
cout << mp[c];
else
cout << 0;
return 0;
}
上一题
下一题