小码匠的信息学江湖【第84式】：欧拉回路之无序字母对

小码匠

发布于 2023-09-06 14:22:44

1910

发布于 2023-09-06 14:22:44

文章被收录于专栏：小码匠和老码农

对话

老码农总是喜欢揪住细节不放，这道题也是两次才AC，所以本蒟蒻只能乖乖的把原因写清楚。

题目描述

给定 n 个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有 (n+1) 个字母的字符串使得每个字母对都在这个字符串中出现。

输入格式

第一行输入一个正整数 n。

第二行到第 (n+1) 行每行两个字母，表示这两个字母需要相邻。

输出格式

输出满足要求的字符串。

如果没有满足要求的字符串，请输出 No Solution。

如果有多种方案，请输出字典序最小的方案（即满足前面的字母的 ASCII 编码尽可能小）。

输入输出样例

输入 #1复制

4
aZ
tZ
Xt
aX

输出 #1复制

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分

// 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代码

// 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;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-09-06，如有侵权请联系 cloudcommunity@tencent.com 删除

int