CF1770H

zhoukangyang · 2023-01-10 17:42:05 · 题解

cnblogs

题意

给定排列 p 和 q。有一张 n \times n 的网格图，(i_1,j_1) 和 (i_2,j_2) 有边当且仅当 |i_1 - i_2| + |j_1 - j_2| = 1 (1 \le i_1, i_2, j_1, j_2 \le n)。你需要构造 2n 条路径，第 i 条从 (1,i) 到 (n,p_i)，第 i+n 条从 (i,1) 到 (q_i,n)，使得被路径覆盖次数最多的边被覆盖的次数最少。

数据范围：n \le 200。

题解

先把满足 p_i = i 且 q_i = i 的情况判掉，有且仅有这个时候答案等于 1。

接下来我们猜测，答案等于 2。

然后我们构造出 p_i = n-i+1 且 q_i = n-i+1 的方案。这个建议读者自行构造，不会也可以看看我的代码！

观察到如果 p_i>p_{i+1}，那么第 i 条路径一定和第 i+1 条路径相交。这个时候如果我们交换第一个交点后的路径，就可以交换 p_i 和 p_{i+1}。

注意到从满足 p_i = n - i + 1 的排列开始，交换 p_i > p_{i+1}，可以得到任意排列（即对任意排列将从大到小排序的过程倒过来做），因此问题得到解决！

时间复杂度 \Theta(n^3)，可以优化到 \Theta(n^2)。

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int 
#define ld long double 
#define ull unsigned long long 
using namespace std;
const int N = 507;
#define VP vector < pair < int, int > > 
int n, p[N], q[N];
VP G[N * 2];
int vis[N][N];
void fix(VP &u) {
    VP stk;
    for(auto &p : u) {
        int ti = vis[p.first][p.second];
        if(ti) while(sz(stk) >= ti) stk.pop_back();
        stk.emplace_back(p);
        vis[p.first][p.second] = sz(stk);
    }
    u = stk;
    for(auto &p : u) vis[p.first][p.second] = 0;
}
void swp(VP &u, VP &v) {
    L(i, 0, sz(u) - 1) vis[u[i].first][u[i].second] = i + 1;
    L(i, 0, sz(v) - 1) if(vis[v[i].first][v[i].second]) {
        int x = vis[v[i].first][v[i].second] - 1, y = i;
        VP X, Y;
        L(i, x, sz(u) - 1) Y.emplace_back(u[i]);
        L(i, y, sz(v) - 1) X.emplace_back(v[i]);
        u.resize(x + sz(X)), v.resize(y + sz(Y));
        L(i, 0, sz(X) - 1) u[i + x] = X[i];
        L(i, 0, sz(Y) - 1) v[i + y] = Y[i];
        break;
    }
    for(auto &p : u) vis[p.first][p.second] = 0;
    for(auto &p : v) vis[p.first][p.second] = 0; 
    fix(u), fix(v);
}

vi get(int *p) {
    vi cur;
    L(i, 1, n) {
        int pos = 0;
        L(j, i, n) if(p[j] == n - i + 1) pos = j;
        while(pos > i) swap(p[pos], p[pos - 1]), --pos, cur.emplace_back(pos);
    }
    reverse(cur.begin(), cur.end());
    return cur;
} 

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    L(i, 1, n) {
        int mt = n - i + 1;
        if(i <= n / 2) {
            L(j, 1, i) G[i].emplace_back(j, i);
            L(j, i + 1, mt) G[i].emplace_back(i, j);
            L(j, i + 1, n) G[i].emplace_back(j, mt);
        } else {
            L(j, 1, mt) G[i].emplace_back(j, i);
            R(j, i - 1, mt) G[i].emplace_back(mt, j);
            L(j, mt + 1, n) G[i].emplace_back(j, mt);
        }
    }
    L(i, 1, n) {
        int mt = n - i + 1;
        L(j, 1, i) G[i + n].emplace_back(i, j);
        if(i <= n / 2) {
            L(j, i + 1, mt) G[i + n].emplace_back(j, i);
        }
        else {
            R(j, i - 1, mt) G[i + n].emplace_back(j, i);
        }
        L(j, i + 1, n) G[i + n].emplace_back(mt, j);
    }
    L(i, 1, n) {
        cin >> p[i];
    }
    L(i, 1, n) {
        cin >> q[i];
    }
    bool same = true;
    L(i, 1, n) same &= p[i] == i && q[i] == i;
    if(same) {
        L(i, 1, n) {
            cout << n << ' ';
            L(j, 1, n) cout << j << ' ' << i << ' ';
            cout << '\n';
        }
        L(i, 1, n) {
            cout << n << ' ';
            L(j, 1, n) cout << i << ' ' << j << ' ';
            cout << '\n';
        }
        return 0;
    }
    vi a = get(p), b = get(q);
    for(auto u : a) swp(G[u], G[u + 1]);
    for(auto u : b) swp(G[u + n], G[u + n + 1]);
    L(i, 1, n * 2) {
        cout << sz(G[i]) << ' ';
        for(auto u : G[i]) cout << u.first << ' ' << u.second << ' ';
        cout << '\n';
    }
    return 0;
}