Codeforces Round #554 Div.2 E - Neko and Flashback

逃离我推掉我的手 2021-11-08 17:20 378阅读 0赞

# 欧拉路径 #

神题啊神题！这道题的突破口就是后两个数组每个元素是一一对应的。

也就是说，对于一个p的排列，b'和c'取得每一个元素的下标在p中都是一样的。

根据b和c数组的性质可以得出，b\[i\] <= c\[i\]。

这也是我们输出-1的一个判断方法。

再来看b和c两个数组，他们是由原数组相邻两个数分别取min和max构造出来的，很容易看出b'和c'同一个位置的两个数一定在原数组中相邻。

我们可以根据这个相邻关系建图，a若与b在原数组中相邻，就连一条无向边，那么最后我们要构造的合法数组即为该无向图的一条欧拉路径。

因为数据比较大，所以我们要先离散化，再考虑有重边，我们可以用multiset来存图，跑过的边直接删除就行了。

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define full(a, b) memset(a, b, sizeof a)
    using namespace std;
    typedef long long ll;
    inline int lowbit(int x){ return x & (-x); }
    inline int read(){
        int X = 0, w = 0; char ch = 0;
        while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
        while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
        return w ? -X : X;
    }
    inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
    inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
    template<typename T>
    inline T max(T x, T y, T z){ return max(max(x, y), z); }
    template<typename T>
    inline T min(T x, T y, T z){ return min(min(x, y), z); }
    template<typename A, typename B, typename C>
    inline A fpow(A x, B p, C lyd){
        A ans = 1;
        for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
        return ans;
    }
    const int N = 200005;
    int n, k, b[N], c[N], p[N], d[N];
    vector<int> rd;
    multiset<int> g[N];
    
    void dfs(int s){
        for(auto it = g[s].begin(); it != g[s].end(); it = g[s].begin()){
            int u = *it;
            g[s].erase(it), g[u].erase(g[u].lower_bound(s));
            dfs(u);
        }
        rd.push_back(s);
    }
    
    int main(){
        
        ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        n = read();
        for(int i = 1; i < n; i ++) b[i] = read(), p[++k] = b[i];
        for(int i = 1; i < n; i ++) c[i] = read(), p[++k] = c[i];
        for(int i = 1; i < n; i ++){
            if(b[i] > c[i]){
                printf("-1\n");
                return 0;
            }
        }
        sort(p + 1, p + k + 1);
        k = (int)(unique(p + 1, p + k + 1) - p - 1);
        for(int i = 1; i < n; i ++){
            b[i] = (int)(lower_bound(p + 1, p + k + 1, b[i]) - p);
            c[i] = (int)(lower_bound(p + 1, p + k + 1, c[i]) - p);
        }
        for(int i = 1; i < n; i ++){
            g[b[i]].insert(c[i]), g[c[i]].insert(b[i]);
            d[b[i]] ++, d[c[i]] ++;
        }
        int t = 0;
        for(int i = 1; i <= k; i ++){
            if(d[i] & 1) t ++;
        }
        if(t != 0 && t != 2){
            cout << "-1" << endl;
            return 0;
        }
        bool odd = false;
        for(int i = 1; i <= k; i ++){
            if(d[i] & 1){
                odd = true, dfs(i);
                break;
            }
        }
        if(!odd) dfs(1);
        if(rd.size() != n) cout << "-1" << endl;
        else{
            for(int i = rd.size() - 1; i >= 0; i --){
                cout << p[rd[i]];
                if(i != 0) cout << " ";
            }
            puts("");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/onionQAQ/p/10820877.html