病毒
2018-06-17 22:48:22来源:未知 阅读 ()
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:UVa/数组与字符串习题集
下一篇:2596 售货员的难题
- P1358 扑克牌 2020-05-06
- 表达式·表达式树·表达式求值 2020-04-29
- C++ 函数模板 2020-04-24
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash