首页 > 代码库 > 病毒 (拓扑)
病毒 (拓扑)
病毒
【问题描述】
有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。
现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其它文档。
现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。
【输入格式】virus.in
第一行为整数K（≤50000），表示字典中的单词个数。
以下K行，是被病毒感染了的字典，每行一个单词。
最后一行是需要你恢复的一串字母。
所有字母均为小写。
【输出格式】virus.out
输出仅一行，为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况，这时请输出一个0。
【输入样例】
6
cebdbac
cac
ecd
dca
aba
bac
cedab
【输出样例】
abcde
1 #include<iostream> 2 using namespace std; 3 #include<cstring> 4 #include<string> 5 #define N 50010 6 int tmp[N][100],map[27][27],rudu[27],ans[27]; 7 bool word[27]; 8 int n,js,m,d,p; 9 string s;10 void juge(int a,int b) //这一步可以优化 11 { 12 if(tmp[a][b]==0||tmp[a+1][b]==0)return ;13 if(tmp[a][b]!=tmp[a+1][b])14 {15 map[tmp[a][b]][tmp[a+1][b]]=1;16 rudu[tmp[a+1][b]]++;17 }18 else juge(a,b+1); 19 }20 bool topo() //拓扑 21 {22 for(int i=1;i<=27;++i) //统计出现的字母个数 23 if(word[i])m++;24 for(int i=1;i<n;++i)25 juge(i,1);26 while(p!=m)27 {28 js=0;29 for(int i=1;i<=m;++i)30 {31 if(rudu[i]==0)32 {33 d=i;34 rudu[i]=-1;35 js++;36 }37 }38 if(js!=1)return false;//包括两种情况：1.没有入度是0的；2.入度是0的有多个点； 39 ans[++p]=d;40 for(int i=1;i<=m;++i)41 {42 if(map[d][i])43 {44 map[d][i]=0;45 rudu[i]--;46 }47 } 48 }49 return true; 50 }51 void out_() //输出 52 {53 for(int i=1;i<=tmp[n+1][0];++i)54 {55 for(int j=1;j<=m;++j)56 {57 if(tmp[n+1][i]==ans[j])58 {59 cout<<char(j+96);60 break;61 }62 }63 }64 }65 int main()66 {67 memset(tmp,0,sizeof(0));68 cin>>n;69 for(int i=1;i<=(n+1);++i)70 {71 cin>>s;72 for(int j=0;j<s.size();++j)73 {74 tmp[i][++tmp[i][0]]=int(s[j]-96);75 word[s[j]-96]=1;76 }77 }78 if(topo()==0)cout<<0;79 else out_();80 return 0;81 }
病毒 (拓扑)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。