04:病毒

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

新老客户大回馈,云服务器低至5折

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:1269 匈牙利游戏 2012年CCC加拿大高中生信息学奥赛

下一篇:2577 医院设置