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 using namespace std;
 3 
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <cmath>
 7 
 8 int qm[27],sd[27],dy[27];// qm记录入度 
 9 string s[50001];
10 int next[1000],back[1000],last[1000];//邻接表元素 
11 bool yt[27][27];// 判断字母应该出现的顺序 
12 int tot,cmax;
13 bool cx[27];
14 
15 void add_edge(int a,int b)
16 {
17     tot++;
18     next[tot]=b;// b 必须要在 a 之后才能出现 
19     back[tot]=last[a];// 指针指向下一条边 
20     last[a]=tot;// 相当于head指针 
21 }
22 
23 void dfs(int x,int t)// t表示字母个数 
24 {
25     if (t>sd[x]) sd[x]=t; //sd表示与x相关的字母数量 
26     int i=last[x];
27     while (i!=0)// 枚举与x+96相关的所有字母 
28     {
29         int v=next[i];
30         if (sd[v]<=t) dfs(v,t+1); 
31         i=back[i];
32     }
33 }
34 
35 void error()
36 {
37     cout<<"0";
38     exit (0);// 退出程序 相当于return 0； 
39 }
40 
41 int main()
42 {
43     int k;
44     cin>>k;
45     for (int i=0; i<=k; i++)
46         getline(cin,s[i]);
47     for (int i=2; i<=k; i++)// 因为判断是把当前字符串与上一个字符串进行比较 
48     {
49         int l1=s[i-1].size(); 
50         int l2=s[i].size(); 
51         for (int j=0; j<=min(l1,l2)-1; j++) //比较到较短的长度 
52         {
53             int t1=s[i-1][j]-96;
54             int t2=s[i][j]-96;
55             cmax=max(t1,max(t2,cmax));// 找到所有输入的最大值 
56             if (t1==t2) continue;  
57             if (yt[t2][t1]) error();//t1必须在t2之前  
58             qm[t2]++;// 入度   拓扑排序 
59             yt[t1][t2]=true;
60             add_edge(t1,t2);
61             break;
62             // 如果找到t1<t2的元素直接退出 因为字典序只比较第一个不相同的元素 
63         }
64     }
65     for (int i=1; i<=cmax; i++)
66     {
67         if (qm[i]==0)  //如果他的入度为0 
68         dfs(i,1);
69     }//统计与所有字母相关的字母的数量 
70     string que,ans="";
71     getline(cin,que);// 输入待处理的字符串 
72      for (int i=0; i<=que.size()-1; i++) 
73     {
74         if (cx[sd[que[i]-96]]) error();
75         cx[sd[que[i]-96]]=true; //进行判重
76           if (sd[que[i]-96]==0) error();//如果没有找到可以匹配的元素 
77         ans=ans+(char (sd[que[i]-96]+96));
78     }
79     cout<<ans;
80     return 0; 
81 }

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