对话
老码农总是喜欢揪住细节不放，这道题也是两次才AC，所以本蒟蒻只能乖乖的把原因写清楚。
题目描述
给定 n 个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有 (n 1) 个字母的字符串使得每个字母对都在这个字符串中出现。
输入格式
第一行输入一个正整数 n。
第二行到第 (n 1) 行每行两个字母，表示这两个字母需要相邻。
输出格式
输出满足要求的字符串。
如果没有满足要求的字符串，请输出 No Solution。
如果有多种方案，请输出字典序最小的方案（即满足前面的字母的 ASCII 编码尽可能小）。
输入输出样例
输入 #1复制
代码语言：javascript复制4
aZ
tZ
Xt
aX
输出 #1复制
代码语言：javascript复制XaZtX
说明/提示
不同的无序字母对个数有限，n 的规模可以通过计算得到。
题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1341
- 参考题解：https://www.luogu.com.cn/problem/P1341
- 标签：
OI、图论、欧拉回路
正解
- 先放一个oi_wiki的链接 —>欧拉图相关基础知识
- 这道题是一个非常明显的欧拉路的题，直接套模版就行，字母为止可以交换，所以是无向图要双向建边
- 因为都是字符，所以存的时候要转换成int类型，我自己写了函数转的比较小，大家嫌麻烦可以干脆把数组开大一点，毕竟最大的‘z'才到122。小贴士：大写字母和小写字母的ascll码是不紧挨着的，如果要要把字符按照从1开始算的话要小心，当然你直接不管中间的七八个字符也行
- 最后提一句吧，千万记得欧拉回路的起点是谁都行，找最小就ok，但起点终点不相同的欧拉路的起点是2选1，这个点必须是奇数点
本蒟蒻因为这个原因第一次只拿了30分
30分
代码语言：javascript复制// Copyright (C) 2021-2028 coder-oldgeek.com All rights reserved.
// 题目: 无序字母对
// 链接: https://www.luogu.com.cn/problem/P1341
// 难度: 普及 /提高
// 提交:
// 题解：
// - https://www.luogu.com.cn/problem/solution/P1341
#include <bits/stdc .h>
using namespace std;
#define endl 'n';
int pan(char x) {
if (x <= 'z' && x >= 'a') {
return x - 'a' 27;
} else {
return x - 'A' 1;
}
}
char unpan(int x) {
if (x <= 52 && x >= 27) {
char y = x 'a' - 27;
return y;
} else {
char y = x 'A' - 1;
return y;
}
}
struct node {
int to, is;
};
int degree[55];
stack<int> st;
vector<vector<bool>> g(55, vector<bool>(55));
void dfs(int now) {
for (int i = 1; i < 55; i) {
if(!g[now][i]) {
continue;
}
g[now][i] = false;
g[i][now] = false;
dfs(i);
}
st.push(now);
}
void best_coder() {
int n;
cin >> n;
int k = 0x7f7f7f;
for (int i = 1; i <= n; i) {
string s;
cin >> s;
g[pan(s[0])][pan(s[1])] = true;
g[pan(s[1])][pan(s[0])] = true;
degree[pan(s[0])];
degree[pan(s[1])];
k = min(k, pan(s[1]));
k = min(k, pan(s[0]));
}
int cnt = 0;
for (int i = 1; i <= 55; i) {
if(degree[i] % 2 == 1) {
cnt;
}
}
if (cnt == 1 || cnt > 2) {
cout << "No Solution";
return;
}
dfs(k);
while (!st.empty()) {
cout << unpan(st.top());
st.pop();
}
}
void happy_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main() {
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
AC代码
代码语言：javascript复制// Copyright (C) 2021-2028 coder-oldgeek.com All rights reserved.
// 题目: 无序字母对
// 链接: https://www.luogu.com.cn/problem/P1341
// 难度: 普及 /提高
// 提交:
// 题解：
// - https://www.luogu.com.cn/problem/solution/P1341
#include <bits/stdc .h>
using namespace std;
#define endl 'n';
int pan(char x) {
if (x <= 'z' && x >= 'a') {
return x - 'a' 27;
} else {
return x - 'A' 1;
}
}
char unpan(int x) {
if (x <= 52 && x >= 27) {
char y = x 'a' - 27;
return y;
} else {
char y = x 'A' - 1;
return y;
}
}
struct node {
int to, is;
};
int degree[55];
stack<int> st;
vector<vector<bool>> g(55, vector<bool>(55));
void dfs(int now) {
for (int i = 1; i < 55; i) {
if (!g[now][i]) {
continue;
}
g[now][i] = false;
g[i][now] = false;
dfs(i);
}
st.push(now);
}
void best_coder() {
int n;
cin >> n;
int k = 0x7f7f7f;
for (int i = 1; i <= n; i) {
string s;
cin >> s;
g[pan(s[0])][pan(s[1])] = true;
g[pan(s[1])][pan(s[0])] = true;
degree[pan(s[0])];
degree[pan(s[1])];
k = min(k, pan(s[1]));
k = min(k, pan(s[0]));
}
int cnt = 0;
int t = 0x7f7f7f7f;
for (int i = 1; i <= 55 && cnt <= 2; i) {
if (degree[i] % 2 == 1) {
cnt;
t = min(t, i);
}
}
if (cnt == 1 || cnt > 2) {
cout << "No Solution";
return;
}
if (cnt == 0) {
dfs(k);
} else {
dfs(t);
}
while (!st.empty()) {
cout << unpan(st.top());
st.pop();
}
}
void happy_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main() {
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
