题目https://www.luogu.org/problemnew/show/P1341

题意:给定n对字母对,要求构造一个个数为n+1的字符串,使得每一个字母对都在里面出现过。

思路:这种题目都卡了好久,代码能力真的不行了啊。

其实就是每个字母是节点,每个字母对就是这两个字母之间连一条边,每个字母对都要出现就是每条边都要经过一次且只经过一次。

所以就是一个欧拉路的问题。

欧拉路问题很简单,首先如果度数是奇数的点只能是0或2个。

之后就是遍历节点的每一条边,全部dfs结束了之后把这个节点加入栈中就行了。

 #include<cstdio>
#include<cstdlib>
#include<map>
#include<set>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<iostream> #define inf 0x7fffffff
using namespace std;
typedef long long LL;
typedef pair<int, int> pr; int n;
const int maxm = ;
const int maxn = ;
int g[maxn][maxn];
//int head[maxn], to[maxm * 2], nxt[maxm * 2], vis[maxm * 2];
int deg[maxn];
int tot = ; stack<int>ans; void dfs(int now){ for(int i = ; i <= ; i++){
if(g[now][i] <= )continue;
g[now][i]--;g[i][now]--;
dfs(i);
}
ans.push(now);
//printf("%c", now);
} int main()
{
scanf("%d", &n);
for(int i = ; i < n; i++){
string s;
cin>>s;
g[s[]][s[]]++;g[s[]][s[]]++;
//cout<<s[0]-'A'<<" "<<s[1]-'A'<<endl;
deg[s[]]++;
deg[s[]]++;
//add(s[0] - 'A', s[1] - 'A');
} //printf("%d\n", deg['I' - 'A']);
int cnt = , dian = ;
for(int i = ; i <= ; i++){
if(deg[i] % ){
cnt++;
if(!dian)dian = i;
}
}
if(!cnt){
for(int i = ; i <= ; i++){
if(deg[i]){
dian = i;
break;
}
}
} if(cnt && cnt != ){
printf("No Solution\n");
}
else{
dfs(dian);
//cout<<ans.size()<<endl;
if(ans.size() >= n+){
while(!ans.empty()){
printf("%c", ans.top());
ans.pop();
}
printf("\n");
}
else{
printf("No Solution\n");
}
} }

最新文章

  1. 判断IP地址是否合法类
  2. ANGULAR JS WATCH监听使用(详)
  3. Docker搭建便捷的开发者环境
  4. 解决Win10服务主机本地系统网络受限
  5. 百度web前端面试2015.10.18
  6. Roman to Integer
  7. 深入探讨Java类加载机制
  8. 使用Myeclipse完成Hibernate的逆向工程
  9. IOS中UISearchBar的使用
  10. JS中,如何查询一个对象的所有属性
  11. .net MVC 使用 JSON JavaScriptSerializer 进行序列化或反序列化时出错,字符串的长度超过了为 maxJsonLength 属性设置的值
  12. 数据库及SQL优化
  13. 160A
  14. 重建索引解决mssql表查询超时的问题
  15. A标签href属性详解--记录八
  16. (转)NGUI类关系图
  17. How do I create a List in Scala?
  18. Map 和 WeakMap 数据结构
  19. 为网站添加favicon.ico图标
  20. C#虚基类继承与接口的区别

热门文章

  1. [转帖]linux下的find文件查找命令与grep文件内容查找命令
  2. Servlet 响应及请求信息
  3. 【洛谷】P3980 [NOI2008]志愿者招募
  4. python第一个浏览器的自动执行程序
  5. Python基础 第6章 抽象
  6. 2.ASP.NET Core Docker学习-镜像容器与仓库
  7. 一个农民工自学java找到工作的励志故事
  8. CentOS7离线安装Nginx(详细安装过程)
  9. ORA-16401: archivelog rejected by RFS
  10. linux时间同步ntpdate