1396:病毒(virus)
- 白书最后一道题!加油!
- 链接
分析
- 由 题目所处的位置可判断要应用拓扑排序
(废话) - 难度主要在于如何比较字典序,注意比较相邻两单词第一个不相同的字母即可
- 输出0的情况:
1 存在环
2 字典不完整(找不到对应字母)
#include <bits/stdc .h>
using namespace std;
int n,tot;
int f[30],G[30][30],v[30],res[30],h[30];
//f记录入度,G记录前后,v记录是否入队,res中转,h记录对应顺序
string s[50010];
stack<int> r;
int main()
{
memset(f,0x3f,sizeof(f));
cin>>n;
for(int i=1;i<=n;i ) cin>>s[i];
for(int i=1;i<n;i ){
if(s[i]==s[i 1]) //完全相同,下一个
continue;
if(s[i 1].find(s[i])==0) //后一个包含前一个,没有比较的意义
continue;
if(s[i].find(s[i 1])==0){//前一个包含后一个,字典错误(与上一个相反)
puts("0");
return 0;
}
int x=0;
while(s[i][x]==s[i 1][x]) //寻找不同字母
x ;
int a=s[i][x]-'a' 1,b=s[i 1][x]-'a' 1;
if(G[b][a]){ //这里a在b前,而之前b在a前,前后矛盾,字典错误,结束
puts("0");
return 0;
}
G[a][b]=1;//存储
if(!v[a]) v[a]=1,f[a]=0;
if(!v[b]) v[b]=1,f[b]=1;
else f[b] ;//入度加一
}
memset(v,0,sizeof(v));
for(int i=1;i<30;i )
if(!f[i])
r.push(i),v[i]=1;
while(r.size()) {//拓扑排序
int x=r.top(); r.pop();
res[ tot]=x;//记录当前
for(int i=1;i<30;i ) {
if(G[x][i]) f[i]--;//入度减一
if(!f[i]&&!v[i])
r.push(i),v[i]=1;
}
}
for(int i=1;i<=tot;i )
h[res[i]]=i;
string que,ans; //que是被感染的字符串,ans是答案
cin>>que;
for(int i=0;i<que.length();i ) {
if(!h[que[i]-'a' 1]){//字典不完整,找不到对应字符
puts("0");
return 0;
}
ans =(char)(h[que[i]-'a' 1] 'a'-1);//记录答案
}
cout<<ans<<endl;
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhigjijg
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
excel下划线不显示怎么办
PHP中文网 06-23 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22