病毒

【问题描述】

  有一天,小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 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 int qm[27],sd[27],dy[27];// qm记录入度 
 7 string s[50001];
 8 int next[1000],back[1000],last[1000];//邻接表元素 
 9 bool yt[27][27];// 判断字母应该出现的顺序 
10 int tot,cmax;
11 bool cx[27];
12 void add_edge(int a,int b)
13 {
14     tot++;
15     next[tot]=b;// 记录能够到达的边 也就是说b 必须要在 a 之后才能出现 
16     back[tot]=last[a];// 指针指向下一条边 
17     last[a]=tot;// 相当于head指针 
18 }
19 void dfs(int x,int t)// t表示字母个数 
20 {
21     if (t>sd[x]) sd[x]=t; //sd表示与x相关的字母数量 
22     int i=last[x];
23     while (i!=0)// 枚举与x+96相关的所有字母 
24     {
25         int v=next[i];
26         if (sd[v]<=t) dfs(v,t+1); 
27         i=back[i];
28     }
29 }
30 void error()
31 {
32     cout<<"0";
33     exit (0);// 退出程序 相当于return 0; 
34 }
35 int main()
36 {
37     int k;
38     cin>>k;
39     for (int i=0; i<=k; i++)
40         getline(cin,s[i]);//读入数据 
41     for (int i=2; i<=k; i++)// 因为判断是把当前字符串与上一个字符串进行比较 故从2开始 
42     {
43         int l1=s[i-1].size(); 
44         int l2=s[i].size();     //保存两个字符串的长度,方便进行for循环 
45         for (int j=0; j<=min(l1,l2)-1; j++) //比较到较小长度即可 多了无意义 
46         {
47             int t1=s[i-1][j]-96;// -96是把字符转换成数字,方便yt数组的判断 97是a的码 减去96是为了让最小的元素为1 方便进行数组判断 
48             int t2=s[i][j]-96;//同理 
49             cmax=max(t1,max(t2,cmax));// 找到所有输入的最大值 
50             if (t1==t2) continue; // 如果是相同的话不需要进行判断 
51             if (yt[t2][t1]) error();// 因为根据题目要求的字典序输入 故t1必须在t2之前 否则出差 
52             qm[t2]++;// t2的入度++   拓扑排序 
53             yt[t1][t2]=true;//
54             add_edge(t1,t2);// 都懂 
55             break;// 如果找到t1<t2的元素直接退出 因为字典序只比较第一个不相同的元素 
56         }
57     }
58     for (int i=1; i<=cmax; i++)
59     {
60         if (qm[i]==0)  //入度为0 
61         dfs(i,1); // i+96表示进行搜索的字母 
62     }//统计与所有字母相关的字母的数量 
63     string que,ans="";
64     getline(cin,que);// 输入待处理的字符串 
65      for (int i=0; i<=que.size()-1; i++) 
66     {
67         if (cx[sd[que[i]-96]]) error();
68         cx[sd[que[i]-96]]=true; //判重??? 
69           if (sd[que[i]-96]==0) error();//没有找到可以匹配的元素 
70         ans=ans+(char (sd[que[i]-96]+96));
71     }
72     cout<<ans;
73     //个人感觉sd数组有一个妙用 
74     //就是因为题目的性质,
75     //所以每个与字母相连的字母的个数肯定不相同
76     //否则错误
77     //根据这一性质我们可以找出每一个字母对应的字母 
78 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏塔奇克马敲代码

第 16 章 模板与泛型编程

15120
来自专栏Linux驱动

27.C++- 智能指针

智能指针 在C++库中最重要的类模板之一 智能指针实际上是将指针封装在一个类里,通过对象来管理指针. STL中的智能指针auto_ptr 头文件: <memor...

362100
来自专栏Python绿色通道

Python入门三部曲(二)

如果不确定使用del语句还是pop()方法,有一个简单的标准:如果你要从列表中删除的一个元素,且不再以任何方式使用它,就使用del语句;如果你要在删除元素后还能...

13330
来自专栏Web 开发

JavaScript的对象引用

在一个函数体内,var变量声明的变量,其作用域只在该函数体内,对于函数体外而言,是不可见的(废话)。

9000
来自专栏Java3y

Object对象你真理解了吗?

28490
来自专栏Python攻城狮

正则表达式1.正则表达式概述2.re模块操作3.表示字符4.re模块的高级用法5.贪婪和非贪婪

在Python中需要通过正则表达式对字符串进行匹配的时候,可以使用一个模块,名字为re

23820
来自专栏ShaoYL

OC语言Block 续

337120
来自专栏Pythonista

封装与扩展性

封装在于明确区分内外,使得类实现者可以修改封装内的东西而不影响外部调用者的代码;而外部使用用者只知道一个接口(函数),只要接口(函数)名、参数不变,使用者的代码...

10030
来自专栏用户2442861的专栏

json格式

  1. “名称/值”对的集合(A collection of name/value pairs)。不同的语言中,它被理解为对象(object),记录(reco...

31720
来自专栏青玉伏案

窥探Swift之需要注意的基本运算符和高级运算符

  之前更新了一段时间有关Swift语言的博客,连续更新了有6、7篇的样子。期间间更新了一些iOS开发中SQLite、CollectionViewControl...

20450

扫码关注云+社区

领取腾讯云代金券