给定 个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有 个字母的字符串使得每个字母对都在这个字符串中出现。
第一行输入一个正整数 。
第二行到第 行每行两个字母，表示这两个字母需要相邻。
输出满足要求的字符串。
如果没有满足要求的字符串，请输出 No Solution。
如果有多种方案，请输出字典序最小的方案（即满足前面的字母的 ASCII 编码尽可能小）。
4
aZ
tZ
Xt
aX
XaZtX
不同的无序字母对个数有限， 的规模可以通过计算得到。
登录并绑定洛谷账号后即可在此在线提交代码并实时评测。
前往登录Author: Yuyi
这道题可以说是之前做过的所有欧拉路径题目的“终极结合版”。 题目要求把一系列的无序字母对串联成一个完整的字符串，并且要求字典序最小。如果把每个字母看作“图中的顶点”，把每个字母对看作“连接这两个字母的无序边”，那么“串联成包含所有字母对的字符串”完美等价于：在无向图中寻找一条欧拉路径。
在这个背景下，本题融合了我们刚刚积累的所有经验：
No Solution。G[150][150] 的二维邻接矩阵来存图。在寻找起点时：
rep(v, 0, 127)，这天生就保证了我们每一次都会优先探索字典序较小的字母，连排序都省了！cnt 是否等于 即可。如果不等于，那就说明图断开了，有边根本没遍历到，直接输出 No Solution 即可。#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 1e5+5;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
X = 0;int w = 0; char ch = 0;
while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
if(w) X = -X;
}
int n;
// 字母的 ASCII 码最大到 122，开 150 的二维数组作为邻接矩阵绰绰有余
int G[150][150];
int deg[150];
char ans[maxn];
int cnt;
void dfs(int u)
{
// 从 0 遍历到 127，天生满足 ASCII 码（字典序）最小的贪心策略
rep(v,0,127)
{
if(G[u][v] > 0)
{
// 无向图删边
G[u][v]--;
G[v][u]--;
dfs(v);
}
}
// 无路可走，压入答案栈
ans[++cnt] = u;
}
void solve()
{
read(n);
int start_node = 150;
rep(i,1,n)
{
string s;
cin >> s;
int u = s[0];
int v = s[1];
G[u][v]++;
G[v][u]++;
deg[u]++;
deg[v]++;
// 随时维护出现过的、ASCII码最小的字符
start_node = min({start_node, u, v});
}
int odd_cnt = 0;
int S = 0;
// 寻找奇数度数的点
rep(i,0,127)
{
if(deg[i] % 2 == 1)
{
odd_cnt++;
// 找到的第一个奇数度数点，因为循环是从小到大的，必定是字典序较小的那个
if(S == 0) S = i;
}
}
// 如果奇数度数的点不是 0 个（欧拉回路）也不是 2 个（欧拉通路），则无解
if(odd_cnt != 0 && odd_cnt != 2)
{
cout << "No Solution\n";
return;
}
// 如果是欧拉回路，从拥有连边的最小字母开始
if(S == 0) S = start_node;
dfs(S);
// 极其优雅的连通性判定：如果压入栈的节点数不等于 边数+1，说明图不连通！
if(cnt != n + 1)
{
cout << "No Solution\n";
return;
}
// 逆序输出答案栈，注意不要加多余的空格
dep(i,cnt,1) cout << ans[i];
cout << "\n";
return;
}
int main()
{
int T_case=1;
// freopen("mul.in","r",stdin);
// freopen("mul.out","w",stdout);
// read(T_case);
while(T_case--) solve();
return 0;
}
Generated by Gemini 3.1 Pro
暂无讨论内容。