老码农总是喜欢揪住细节不放,这道题也是两次才AC,所以本蒟蒻只能乖乖的把原因写清楚。
给定 n 个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有 (n+1) 个字母的字符串使得每个字母对都在这个字符串中出现。
第一行输入一个正整数 n。
第二行到第 (n+1) 行每行两个字母,表示这两个字母需要相邻。
输出满足要求的字符串。
如果没有满足要求的字符串,请输出 No Solution
。
如果有多种方案,请输出字典序最小的方案(即满足前面的字母的 ASCII 编码尽可能小)。
输入 #1复制
4
aZ
tZ
Xt
aX
输出 #1复制
XaZtX
不同的无序字母对个数有限,n 的规模可以通过计算得到。
题目原文请移步下面的链接
OI
、图论
、欧拉回路
// 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;
}
// 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;
}