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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

C/C++中int128的那点事

最近群友对int128这个东西讨论的热火朝天的。讲道理的话,编译器的gcc是不支持__int128这种数据类型的,比如在codeblocks 16.01/Dev...

3761
来自专栏学习力

《Java从入门到放弃》框架入门篇:Struts2的常用验证方式(二)

1789
来自专栏魂祭心

原 What Every Dev need

2908
来自专栏Java 源码分析

Bootstrap 源码分析

Netty 源码分析: Bootstrap 1. 结构 先看一个这个类的类层次结构, ? 好,这个结构还是比较明晰的,然后看他的主要字段,因为这些字段比较重...

2885
来自专栏java一日一条

50个常见的 Java 错误及避免方法(第二部分)

System.out.println("Whatdo you want to do?");

1193
来自专栏野路子程序员

Thinkphp修改一句代码,使得foreach标签支持对象,增加变量[数组对象]混合解析法!

3268
来自专栏数据结构与算法

洛谷P1481 魔族密码(LIS)

1622
来自专栏数据结构与算法

ZR#331. 【18 提高 3】括号序列(栈)

那么若区间$(l, r)$是可行的,那么$s_{l - } = s_r$,证明自己yy一下吧。。

981
来自专栏抠抠空间

模板语言

常用语法 只需要记两种特殊符号: {{  }}和 {% %} 变量相关的用{{}},逻辑相关的用{%%}。 变量 {{ 变量名 }} 变量名由字母数字和下划线组...

3548
来自专栏安恒网络空间安全讲武堂

​CTF逆向——常规逆向篇(下)

CTF逆向——常规逆向篇(下) 题目: CrackMe.exe(NSCTF reverse第一题) WHCTF2017 reverse HCTF reverse...

5265

扫码关注云+社区

领取腾讯云代金券