04:病毒
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录