B - Bring It To Back

分类讨论题.

  • n=2n=2 时，根据 mm 的奇偶性，答案为 [1,2][1,2] 或者 [2,1][2,1]

  • 当 m≥nm\ge n，直接倒序 [n,n−1,…,1][n,n-1,\dots,1] 即可.

    考虑 [n,n−1,…,1][n,n-1,\dots,1] 和 [n−1,n−2,…,2,1,n][n-1,n-2,\dots,2,1,n] 序列，我们都可以用 n−1n-1 次操作排序好.

    因此，如果 m−(n−1)m-(n-1) 是偶数，我们直接让 1,21,2 之间倒腾；否则如果是奇数，那么先把 nn 换到最后，再让 1,n1,n 之间倒腾.

  • 当 m<nm\lt n 时，让前 mm 个元素从 nn 倒序，剩下的从 11 正序.

AC Code
 
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
#include <bits/stdc++.h>

void run() {
    int n, m;
    std::cin >> n >> m;

    if (n == 1) {
        std::cout << 1 << "\n";
        return;
    }
    if (n == 2) {
        std::cout << (m % 2 == 0 ? "1 2\n" : "2 1\n");
        return;
    }

    m = std::min(m, n);
    std::vector<int> ans(n, -1);

    int v = n;
    for (int i = 0; i < m; i++, v--) ans[i] = v;
    for (int i = m, t = 1; i < n; i++) ans[i] = t++;

    for (int i = 0; i < n; i++) std::cout << ans[i] << " ";
    std::cout << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);

    int t;
    std::cin >> t;
    while (t--) run();
}

C - Challenge to the Reader

考虑 11 前面的符号总是 ++. 令 y=x−1y=x-1. 同时，如果 y<0y\lt 0，我们可以先计算 y>0y\gt 0 的方案，再把符号全部取反. 以下只考虑 y>0y\gt 0.

首先先找到 nn 使得

∑i=2ni≤y<∑i=2n+1i \sum_{i=2}^n i\le y\lt \sum_{i=2}^{n+1} i

然后令 y=k+∑i=2niy=k+\sum_{i=2}^n i.

  • 如果 k=0k=0 那么就结束了
  • 如果 k≡n+1(mod2)k\equiv n+1\pmod 2，那么我们需要选择一些 j∈Sj\in \mathcal S，使得 ∑j∈Sj=n+1−k2\sum_{j\in\mathcal S} j=\frac{n+1-k}{2}
    • 然而，这里 k=n−1k=n-1 时，右式为 11，显然不行. 所以我们需要另外讨论.
  • 如果 k≠n−1 and k≡2n+3(mod2)k\ne n-1 \texttt{ and }k\equiv 2n+3\pmod 2，那么我们选择 ∑j∈Sj=2n+3−k2\sum_{j\in\mathcal S} j=\frac{2n+3-k}{2}
  • 然而如果还不行，那么一定有 k≡3n+6(mod2)k\equiv 3n+6\pmod 2，选择的是 ∑j∈Sj=3n+6−k2\sum_{j\in\mathcal S} j=\frac{3n+6-k}{2}

如果 k=n−1k=n-1

  • 如果 n≡0(mod2)n\equiv 0\pmod2，那么选择 ∑j∈Sj=2n+3−k2\sum_{j\in\mathcal S} j=\frac{2n+3-k}{2}
  • 否则就需要 n+4n+4 了，选择 ∑j∈Sj=4n+10−k2\sum_{j\in\mathcal S} j=\frac{4n+10-k}{2}

所以 subproblem 就是给定 vv 使得 ∑i=v\sum i=v. 这个可以直接 DP\tt DP 计算，同时记录转移. 因为 y<2×105y\lt 2\times 10^5，所以 n=O(V),v=O(V)n=O(\sqrt{V}), v=O(V)，DP\tt DP 的转移为 O(VV)O(V\sqrt{V}).

AC Code
 
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>

int x, y, r, n;
bool rev = false;
std::map<int, int> res;

void find_n(int val) {
    r = 0, n = 2;
    while (r + n <= val) {
        r += n;
        res[n] = 1;
        n++;
    }
    n--;
}

void reverse() {
    for (auto &[k, v] : res) v = -v;
}

void output() {
    if (rev) reverse();
    std::cout << res.rbegin()->first << "\n";
    std::cout << "1";
    for (auto [k, v] : res) {
        std::cout << (v == 1 ? "+" : "-");
        std::cout << k;
    }
    std::cout << "\n";
}

void clear() { res.clear(), rev = false; }

void f(int q, int val) {
    // dp
    std::vector<int> can(val + 1, 0), t(val + 1, -1);
    can[0] = true, t[0] = 0;

    for (int i = 2; i <= q; i++) {
        for (int v = val; v >= i; v--) {
            if (can[v - i]) {
                can[v] |= can[v - i];
                t[v] = i;
            }
        }
    }

    std::vector<int> p;
    int a = val;
    while (a != 0) {
        p.push_back(t[a]);
        a = a - t[a];
    }

    for (auto v : p) res[v] *= -1;
}

void run() {
    std::cin >> x;
    clear();
    if (x == 0) return void(std::cout << "3\n1+2-3\n");
    if (x == 1) return void(std::cout << "1\n1\n");

    y = x - 1;
    if (y < 0) rev = true, y = -y;

    find_n(y);
    int k = y - r;
    if (k == 0) return output();

    if (k == n - 1) {
        if (n % 2 == 0) {
            res[n + 1] = res[n + 2] = 1;
            f(n + 2, (2 * n + 3 - k) / 2);
        } else {
            res[n + 1] = res[n + 2] = res[n + 3] = res[n + 4] = 1;
            f(n + 4, (4 * n + 10 - k) / 2);
        }

        output();
        return;
    }

    if (k % 2 == (n + 1) % 2) {
        res[n + 1] = 1;
        f(n + 1, (n + 1 - k) / 2);
    } else if ((2 * n + 3) % 2 == k % 2) {
        res[n + 1] = res[n + 2] = 1;
        f(n + 2, (2 * n + 3 - k) / 2);
    } else {
        res[n + 1] = res[n + 2] = res[n + 3] = 1;
        f(n + 3, (3 * n + 6 - k) / 2);
    }

    output();
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

M - Merticulous Manipulation

倒着考虑. nn 是放在顶上的，然后被换到某个位置，所以可以直接算出 xnx_n. 然后把序列换回去，把 nn 删去，考虑 n−1n-1. 也是同理. 所以我们只需要一个 Treap 用来维护序列、找最大值即可. 时间复杂度 O(nlog⁡n)O(n\log n).

AC Code
 
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#include <random>
constexpr int N = 2e5 + 10;
using namespace std;

struct Node {
    int l, r;
    int siz;
    int val, key;
    int max;
    bool revs;
};
vector<Node> fhq;
int cnt, root;
std::mt19937_64 rnd(23333);

int create(int val) {
    cnt++;
    fhq[cnt].val = val, fhq[cnt].max = 0;
    fhq[cnt].key = rnd();
    fhq[cnt].siz = 1;
    return cnt;
}
void update_size(int now) {
    int lft = fhq[now].l;
    int rt = fhq[now].r;
    fhq[now].siz = fhq[lft].siz + fhq[rt].siz + 1;
    fhq[now].max = std::max({fhq[lft].max, fhq[lft].val, fhq[rt].val, fhq[rt].max});
}
void split_by_size(int now, int siz, int &x, int &y) {
    if (!now) x = y = 0;
    else {
        int &l = fhq[now].l;
        int &r = fhq[now].r;
        if (fhq[fhq[now].l].siz < siz) {
            x = now;
            split_by_size(fhq[now].r, siz - fhq[fhq[now].l].siz - 1, fhq[now].r, y);
        } else {
            y = now;
            split_by_size(fhq[now].l, siz, x, fhq[now].l);
        }
        update_size(now);
    }
}
int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (fhq[x].key < fhq[y].key) {
        fhq[x].r = merge(fhq[x].r, y);
        update_size(x);
        return x;
    } else {
        fhq[y].l = merge(x, fhq[y].l);
        update_size(y);
        return y;
    }
}
int locateMax(int p) {
    if (p == 0) return 0;
    int l = fhq[p].l, r = fhq[p].r;

    int lmax = std::max({fhq[l].val, fhq[l].max});
    int rmax = std::max({fhq[r].val, fhq[r].max});

    if (fhq[p].val > lmax && fhq[p].val > rmax) return 1 + fhq[l].siz;
    else if (lmax > fhq[p].val && lmax > rmax) return locateMax(l);
    else return fhq[l].siz + 1 + locateMax(r);
}

int n, a[N];

int main() {
    std::cin >> n, fhq.resize(N * 2);
    a[0] = 0, a[n + 1] = 0;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        root = merge(root, create(a[i]));
    }

    std::vector<int> v;
    for (int i = 1, l, r; i <= n; i++) {
        int id = locateMax(root);
        split_by_size(root, id - 1, l, r);

        v.emplace_back((n - i + 1) - id + 1);
        root = merge(r, l);
        split_by_size(root, 1, r, root);
    }
    std::reverse(v.begin(), v.end());
    for (auto f : v) std::cout << f << " ";
    std::cout << "\n";
}
ICPC/APAC/2025
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。