构造

1427D Unshuffling a Deck

题意

每次把序列分成 \(k\) 块， 然后把这 \(k\) 块逆序排雷。块内的元素按照原来的顺序。求一个可行的操作序列，把给定的序列排序成顺序排列

分析

我们发现，每次操作后，所有的数都会倒过来。我们可以每次把 \(1\) 个数字排到正确的位置上。然后最多排 \(n\) 此就可以了。比如 \(4, 3,1,2\) 这个序列，我们先排 \(1\) : \([4,3],[1,2]\) 排列后 \([1,2],[4,3]\) 那么 \(1\) 就被排到正确的位置了，然后我们排 \(n\) : \([1],[2],[4,3]\) 排序后 \([4,3],[2],[1]\) 这样 \(4\) 就排到正确的位置了。已经排好序的拆散排。就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}

inline int len(int l, int r) {
    if (l > r) return 0;
    return r - l + 1;
}

int n, m, A[maxn];

void operate(vector<int> &cur) {
    vector<vector<int>> a;
    int j = 1;
    for (auto x : cur) {
        a.push_back(vector<int>());
        for (int i = j;i < j + x; ++i) a.back().push_back(A[i]);
        j = j + x;
    }
    reverse(a.begin(), a.end()); int tot = 0;
    for (auto v : a) for (auto x : v) A[++tot] = x;
}

bool sorted() { 
    for (int i = 1;i <= n; ++i) if (A[i] != i) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        cin >> A[i];
    }
    vector<vector<int>> ans; int k; int l, r;
    for (int i = 1;i <= n; ++i) {
        if (sorted()) break;
        k = (i+1)/2; if (i % 2 == 0) k = n - i/2 + 1;
        l = 1 + i/2; r = n - (i+1)/2 + 1; 
        int pos = 0;
        for (int j = 1;j <= n; ++j) {
            if (A[j] == k) { pos = j; break; }
        }
        ans.push_back(vector<int>());
        for (int j = 1;j <= l-1; ++j) ans.back().push_back(1);
        if (len(l, pos-1) > 0) ans.back().push_back(len(l, pos-1));
        if (len(pos, r) > 0) ans.back().push_back(len(pos, r));
        for (int j = r+1;j <= n; ++j) ans.back().push_back(1);
        if (sz(ans.back()) == 1) { ans.pop_back(); continue; }
        operate(ans.back());
    }
    cout << sz(ans) << endl;
    for (auto v : ans) {
        cout << sz(v) << " ";
        for (auto x : v) cout << x << " ";
        cout << endl;
    }
    return 0;
}