传送门

题目大意

给你n个字符串,问是否可以通过改变26个字母的排列顺序是这n个字符串的字典序是非降排列的。

分析

我们考虑设相邻两个字符串的第一个不相同字符的位置为j,以为要求字典序不降,所以有第i个字符串的第j位向第i+1个字符串的第j位连边,最后如果没有环则代表可以找到一种顺序,反之不能。

注:代码应用的是floyd判环。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define sp cout<<"---------------------------------------------------"<<endl
#define pb push_back
char s[][];
int g[][],ok;
int main(){
int n,m,i,j,k;
scanf("%d",&n);
while(n!=){
ok=;
for(i=;i<=n;i++)
scanf("%s",s[i]);
memset(g,,sizeof(g));
for(i=;i<n;i++){
int len=strlen(s[i]),len2=strlen(s[i+]);
j=;
while(j<len&&j<len2&&s[i][j]==s[i+][j])j++;
if(j<len&&j==len2){
ok=;
break;
}
if(j<len&&j<len2){
g[s[i][j]-'a'][s[i+][j]-'a']=;
}
}
for(k=;k<;k++)
for(i=;i<;i++)
for(j=;j<;j++)
g[i][j]|=(g[i][k]&g[k][j]);
for(i=;i<;i++)
if(g[i][i])
ok=;
if(ok)puts("yes");
else puts("no");
scanf("%d",&n);
}
return ;
}

最新文章

  1. C#利用微软库完成设备网络定位(经纬度-地址)
  2. Intellij IDEA使用总结
  3. RTP/RTCP的时间同步机制
  4. css问题 ie7兼容性问题
  5. 破解 “PEDIY CrackMe 2007” 之 KeygenMe_1_by_boonz
  6. 【转】Unity LayerMask 的位运算
  7. 模拟namenode崩溃,使用secondarynamenode恢复
  8. 《C++ Primer 4th》读书笔记 第10章-关联容器
  9. “互联网+”引发IT人才招工荒-新华网安徽频道
  10. Mac 终端命令运行java
  11. dos下的cd指令
  12. 使用Oracle Wrap工具加密你的代码
  13. MediaScanner与音乐信息扫描==
  14. bzoj3322 最大生成树+LCA
  15. 201521123072《java程序设计》第十三周学习总结
  16. (四) Keras Dropout和正则化的使用
  17. 斗地主 ai的一些资料
  18. Linker Scripts3--MEMORY Command
  19. [原][openstack-pike][controller node][issue-2][glance] Could not parse rfc1738 URL from string &#39;mysql+pymysql=http://glance:glance@controller/glance&#39;
  20. oh-my-zsh安装与使用

热门文章

  1. nyoj-1092-数字分隔(二)
  2. LeetCode Count Binary Substrings
  3. (转)C#正则表达式Regex类的用法
  4. Jmeter &amp; TICK
  5. Activiti:MalformedByteSequenceException: 3 字节的 UTF-8 序列的字节 3 无效。
  6. 反射ORM
  7. HDU5469(树的dfs)
  8. java代码swing编程JPaswordField类
  9. PostgreSQL 9.5 高可用、负载均衡和复制
  10. 想开发VR游戏?你需要注意这些东西