洛谷 P1341 无序字母对 Label:欧拉路 一笔画
2024-10-16 09:30:49
题目描述
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
输入输出格式
输入格式：
第一行输入一个正整数n。
以下n行每行两个字母，表示这两个字母需要相邻。
输出格式：
输出满足要求的字符串。
如果没有满足要求的字符串，请输出“No Solution”。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案
输入输出样例
输入样例#1：
4
aZ
tZ
Xt
aX
输出样例#1：
XaZtX
说明
【数据规模与约定】
不同的无序字母对个数有限，n的规模可以通过计算得到。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int tot,p,N,x,y,k=INF;
int a[],c[],du[],b[][];
char str[]; void dfs(int u){
for(int i=;i<;i++){ //A到z之间还有一些字符，总共58个~
if(b[u][i]){
b[u][i]=b[i][u]=;
dfs(i);
// break;
}
}
c[++tot]=u;
} int main(){
// freopen("01.in","r",stdin);
scanf("%d",&N);
for(int i=;i<=N;i++){
scanf("%s",str);
x=str[]-'A',y=str[]-'A';//字符串从0开始读入
k=min(k,min(x,y));
b[x][y]=b[y][x]=;
++du[x],++du[y];
}
for(int i=;i<;i++){
if(du[i]&){
a[++p]=i;
}
} if(p==) dfs(k);
else if(p==) dfs(a[]);
else{
puts("No Solution");
return ;
} for(int i=tot;i>=;i--){
printf("%c",c[i]+'A');
} return ;
}照例转载题解:
把两个字母拆成两个顶点 然后构造一个无向图 ，这样根据欧拉回路 当一个图中每个点的度数都是偶数时 纯在欧拉环 而只有2个奇数度数时，存在欧拉路径 因此先验证一下然后dfs 这里为了储存答案我用了双端队列，当然也可以不用 偷点懒，至于最小字典序的话 拍一下序就好了 而如果你用 vector的话 直接从小到大排序（我就是这么做的），而如果你用链表的号 需要首字母从小到大 第二个字母从大到小
我再说两句:
按照欧拉路的性质,若有度奇数点,只能从奇数点走,
本题中若没有则按照题意以Line39的处理方式从ASCII最小序走
特别注意!!!
Line16不可写!!!
这样不写处理的话字符串会以一种神奇的方式连接起来!!!,想想看为什么~
最新文章
- jQuery基础的工厂函数以及定时器的经典案例
- SQL Server存储(6/8) ：理解DCM页
- Dell 服务器做Raid
- 《Linux内核设计与实现》读书笔记（二十）- 补丁, 开发和社区
- “耐撕”团队2016.04.12站立会议
- delphi TPopupMenu.Popup
- Java ZIP File Example---refernce
- Tomcat启动报错org.apache.coyote.AbstractProtocol.init Failed to initialize end point associated with ProtocolHandler ["http-apr-8080"]”
- 【HDU4552】 怪盗基德的挑战书（后缀数组）
- android Handler及消息处理机制的简单介绍
- 持续集成 之 apache-continuum
- Android中振动器(Vibrator)的使用
- PostgreSQL9.1 with PostGIS 2.1.4 for mapping coordinates on linux/ubuntu 已经打包成deb 可下载
- 008 pandas介绍
- tomcat运行时为什么不能删除war
- MVC应用程序请求密码的功能(一)
- 将nosetests的echo结果保存到本地文件
- python--条件判断和循环--3
- leetcode 27 Romove element
- SVN图标不显示的解决几种方式