lessons/参考实现/01-欧拉路径/CodeForces-508D.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int code(char c) {
    if ('a' <= c && c <= 'z') return c - 'a';
    if ('A' <= c && c <= 'Z') return 26 + c - 'A';
    return 52 + c - '0';
}

char decode(int x) {
    if (x < 26) return static_cast<char>('a' + x);
    if (x < 52) return static_cast<char>('A' + x - 26);
    return static_cast<char>('0' + x - 52);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    constexpr int sigma = 62;
    constexpr int vertices = sigma * sigma;
    vector<vector<int>> adj(vertices);
    vector<int> in(vertices, 0), out(vertices, 0);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int u = code(s[0]) * sigma + code(s[1]);
        int v = code(s[1]) * sigma + code(s[2]);
        adj[u].push_back(v);
        ++out[u]; ++in[v];
    }

    int start = -1, plus = 0, minus = 0;
    bool ok = true;
    for (int v = 0; v < vertices; ++v) {
        int diff = out[v] - in[v];
        if (diff == 1) { ++plus; start = v; }
        else if (diff == -1) ++minus;
        else if (diff != 0) ok = false;
        if (start == -1 && out[v] > 0) start = v;
    }
    ok = ok && ((plus == 0 && minus == 0) || (plus == 1 && minus == 1));
    if (!ok || start == -1) {
        cout << "NO\n";
        return 0;
    }

    vector<size_t> cursor(vertices, 0);
    vector<int> st{start}, path;
    path.reserve(n + 1);
    while (!st.empty()) {
        int v = st.back();
        if (cursor[v] == adj[v].size()) {
            path.push_back(v);
            st.pop_back();
        } else {
            st.push_back(adj[v][cursor[v]++]);
        }
    }
    if (static_cast<int>(path.size()) != n + 1) {
        cout << "NO\n";
        return 0;
    }
    reverse(path.begin(), path.end());

    cout << "YES\n";
    cout << decode(path[0] / sigma) << decode(path[0] % sigma);
    for (int i = 1; i <= n; ++i) cout << decode(path[i] % sigma);
    cout << '\n';
}