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 条评论
登录 后参与评论

相关文章

  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • P1983 车站分级

    题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一...

    attack
  • cf1056B. Divide Candies(数论 剩余系)

    求满足\(i^2 + j^2 \% M = 0\)的数对\((i, j)\)的个数,\(1 \leqslant i, j \leqslant 10^9, M \...

    attack
  • 395. Longest Substring with At Least K Repeating Characters

    这是一个经典的分治法解决的问题,关键在于我们如何将这个问题分解为更小的子问题。反过来想,这个子字符串一定不包含什么元素呢?当一个元素出现的总次数小于k,那么该元...

    眯眯眼的猫头鹰
  • cf1056B. Divide Candies(数论 剩余系)

    求满足\(i^2 + j^2 \% M = 0\)的数对\((i, j)\)的个数,\(1 \leqslant i, j \leqslant 10^9, M \...

    attack
  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • P1983 车站分级

    题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一...

    attack
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • cf547D. Mike and Fish(欧拉回路)

    attack
  • P2419 [USACO08JAN]牛大赛Cow Contest

    题目背景 [Usaco2008 Jan] 题目描述 N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are ...

    attack

扫码关注云+社区

领取腾讯云代金券