「Codeforces 1738D」Permutation Addicts - 图论 + DFS

发表于 分类于 ， 阅读次数： Disqus：

题意描述

Codeforces 链接

有一个 \(n\) 个数的排列 \(a\) 和一个数 \(k (0 \le k \le n)\)，你计算出了一个有 \(n\) 个数的序列 \(b\)，计算方法如下：

  • 当 \(a_i \le k\) 时，若存在 \(a_j > k (1 \le j < i)\) 且 \(i - j\) 最小，则 \(b_{a_i} = a_j\)，否则 \(b_{a_i} = n + 1\)；
  • 当 \(a_i > k\) 时，若存在 \(a_j \le k (1 \le j < i)\) 且 \(i - j\) 最小，则 \(b_{a_i} = a_j\)，否则 \(b_{a_i} = 0\)。

目前你知道 \(b\) 与 \(n\)，请求出任意一种 \(a\) 及对应的 \(k\)。

解题思路

分析可得对于 \(i \le k\)，满足 \(b_i > i\)；对于 \(i > k\)，满足 \(b_i < i\)。证明显然。这样我们可求出 \(k\)。

对于每个 \(b_i\)，若 \(i \neq n + 1\) 且 \(i \neq 0\)，显然 \(b_i\) 在 \(i\) 的后面，若有 \(m\) 个 \(b_i = 0\) 或 \(b_i = n + 1\)，则这 \(m\) 个数必定在前 \(m\) 位，且 \(b_i = 0\) 和 \(b_i = n + 1\) 两者必定有且只有一者出现。于是我们可以直接建树，连边 \(i \rightarrow b_i\)，然后对 \(0\) 或 \(n + 1\) 进行 DFS 即可。对于一个节点 \(u\)，它的子节点中若有以节点 \(v\) 为根的子树大于 \(1\)，就最后遍历 \(v\) 即可。显然对于每个节点至多只有一个子节点为根的子树大小大于 \(1\)。

代码演示

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
#include <cstdio>
#include <iostream>
#include <vector>

const int MAXN = 1e5;

struct Node {
    int size, p;
    Node(int p) : p(p) {}
};

int n;
std::pair<int, std::vector<int>> e[MAXN + 2];

int dfs1(int p) {
    e[p].first = 1;
    if (e[p].second.size() == 0) return 1;
    for (int each : e[p].second) e[p].first += dfs1(each);
    return e[p].first;
}

void dfs2(int p) {
    if (p != 0 && p != n + 1) printf("%d ", p);
    int max = 0;
    for (int each : e[p].second) max = std::max(max, e[each].first);
    for (int each : e[p].second) {
        if (e[each].first != max) {
            dfs2(each);
        }
    }
    for (int each : e[p].second) {
        if (e[each].first == max) {
            dfs2(each);
        }
    }
}

void solve() {
    static int b[MAXN + 1];

    scanf("%d", &n);

    int k = 0;
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        if (b[i] > i) k = i;
        if (b[i] == 0) flag = false;
    }
    printf("%d\n", k);

    for (int i = 0; i <= n + 1; i++) e[i].second.clear();
    for (int i = 1; i <= n; i++) e[b[i]].second.push_back(i);

    if (flag) {
        dfs1(n + 1);
        dfs2(n + 1);
    } else {
        dfs1(0);
        dfs2(0);
    }
    putchar('\n');
}

int main() {
    int t;

    scanf("%d", &t);

    while (t--) solve();

    return 0;
}