首页 > > 程序设计 > C/C++ >

04:病毒

2018-06-17 22:48:15来源：未知阅读 ()

04:病毒

查看
提交
统计
提问

总时间限制:: 1000ms
内存限制:: 65535kB

描述

有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。

　　现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其它文档。

　　现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。

输入

virus.in
第一行为整数K（≤50000），表示字典中的单词个数。
以下K行，是被病毒感染了的字典，每行一个单词。
最后一行是需要你恢复的一串字母。
所有字母均为小写。

输出

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

样例输入

6
cebdbac
cac
ecd
dca
aba
bac
cedab

样例输出

abcde
思路自己看代码吧，
注意特判

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<stack>
  5 #include<cstdlib> 
  6 #include<cmath>
  7 const int MAXN=50000;
  8 using namespace std;
  9 string a[MAXN];
 10 int maxnlength;
 11 struct node
 12 {
 13     int u;
 14     int v;
 15     int w;
 16     int next;
 17 }edge[MAXN];
 18 int rudu[MAXN];
 19 int head[MAXN];
 20 int num=1;
 21 int ans[10001];//保存拓扑排序的结果 
 22 int now=1;
 23 int n;
 24 int maxnchar=0;
 25 int map[101][101];
 26 void topsort()
 27 {
 28     stack<int>s;
 29     for(int i=1;i<=maxnchar;i++)
 30     {
 31         if(rudu[i]==0)
 32         {
 33             s.push(i);
 34             ans[now]=i;
 35             now++;
 36         }
 37     }
 38     int flag=0;
 39     while(s.size()==1)
 40     {
 41         if(s.size()>1)
 42         {
 43             flag=1;
 44             break;
 45         }
 46         int p=s.top();
 47         s.pop();
 48         for(int i=head[p];i!=-1;i=edge[i].next)
 49         {
 50             rudu[edge[i].v]--;
 51             if(rudu[edge[i].v]==0)
 52             {
 53                 s.push(edge[i].v);
 54                 ans[now]=edge[i].v;
 55                 now++;
 56             }
 57         }
 58     }
 59     if(flag==1)
 60     {
 61         printf("0\n");
 62         exit(0);
 63     }
 64 }
 65 int main()
 66 {
 67     
 68     scanf("%d",&n);
 69     for(int i=1;i<=n;i++)head[i]=-1;
 70     for(int i=1;i<=n;i++)
 71     {
 72         cin>>a[i];
 73         if(a[i].length()>maxnlength)
 74         maxnlength=a[i].length();
 75         for(int j=1;j<=a[i].length();j++)
 76         {
 77             if(a[i][j]-96>maxnchar)
 78             maxnchar=a[i][j]-96;
 79         }
 80     }
 81     int flag2=0;
 82     for(int i=2;i<=n;i++)
 83     {
 84         int j=i-1;
 85             for(int k=0;k<=min(a[i].length()-1,a[j].length()-1);k++)
 86             {
 87                 if(a[j][k]!=a[i][k])
 88                 {
 89                     if(map[a[j][k]-96][a[i][k]-96]==1||map[a[i][k]-96][a[j][k]-96]==1)
 90                     {
 91                         printf("0\n");
 92                         return 0;
 93                     }
 94                     edge[num].u=a[j][k]-96;
 95                     edge[num].v=a[i][k]-96;
 96                     edge[num].next=head[edge[num].u];
 97                     head[edge[num].u]=num++;
 98                     rudu[a[i][k]-96]++;
 99                     flag2=1;
100                     map[a[j][k]-96][a[i][k]-96]=1;
101                     break;
102                 }
103             }
104             //if(flag2==1)break;
105     }
106     topsort();
107     char sr[101];
108     char huiche[1];
109     gets(huiche);
110     gets(sr);
111     int l=strlen(sr);
112     //int srl=sr.length();
113     for(int i=0;i<=l;i++)
114     {
115         if(sr[i]-96>maxnchar)
116         {
117             printf("0\n");
118             return 0;
119         }
120     }
121     for(int i=0;i<=l;i++)
122     {
123         for(int j=1;j<=now-1;j++)
124         {
125             if(ans[j]==sr[i]-96)
126             {
127                 printf("%c",char(j+96));
128             }
129         }
130     }
131     return 0;
132 }