Lotuses's Blog

CF1876C Solution

  • ~3.01K 字

给定一个长度为 的序列 。

你可以对这个序列进行任意次操作，每次操作选择一个下标 ，并圈住下标为 的数 。可以多次圈一个数。

请构造出一组操作方案，使得操作选出的下标序列 等于没有被圈过的数构成的序列 。

请注意，下标序列和没有被圈过的数的序列皆有序，后者按照原序列顺序依次排列。

假设我们令操作序列为 ，未被选中序列列为 。

初看题面，有一个很重要的信息：操作选出的下标序列是唯一对应的。

即，要使 ，则第 次选择的位置唯一确定为 。

那么我们可以发现，要是某一个数 要是不选，那么就只有唯一确定的 的位置要被选中，并且选择的顺序要对应上 ​ 的位置。

并不需要考虑位置对应的事，因为一个数刚好只会对应一个操作。

反过来思考，要是某个位置 要是选中了，那么就一定会有不小于一个的 被留在了不圈出的序列里面。

考虑抽象成图论问题。每一个数抽象成一个节点，那么变成了黑白染色问题。

令圈一次以上为黑色 ，令不圈为白色 。连边 ，以上说法可以转换为以下的涂色问题：

  • 白点后面唯一的出边到达的点必须是白点。
  • 一个黑点的所有入边的起点中，至少有一个白点。

关于样例的涂色方案是这样的：

发现这刚好是个内向基环树或森林（每个点只有一个出度，并且环外指向环内）。

考虑在环外跑拓扑排序，依次染色，发现叶子节点必然是白色，那么考虑以下的染色方案即可跑完不含环的部分：

  • 一个点是白点，则指向的节点必然是黑色。
  • 若一个点儿子被拓展完进入队列时还未被染色（即所有儿子都是黑色的），那么染成白色。

图示：（黄色为白，红色为黑）

这样构造是唯一的部分合法的（不那么构造不可能合法）。

把非环的部分跑完，考虑跑环。

如果环上有被染色，那么可以证明一定是黑色。（白色的要求是儿子全部遍历完，那么环不可能遍历完所有儿子进入队列）

两种假设：

  • 要是环上全部没有被染色，那么从任意一个点开始，染成白色（染成白色是不会出现冲突，因为要是冲突会一定被染成黑色，就有部分点被染色了）。

  • 要是环上有点被染色，从任意一个点有颜色的点开始。

开始后按照非环部分一样拓展。有一点小特殊，但也有一般性的是：当前点为黑色，下一个点并未被涂色时给下一个点涂为白色。

涂一圈，判断是否合法的便是在最后看首尾两个点颜色情况了。黑色和黑色撞一起是可以的，因为既然染成了黑色就一定有白色作为起点。但是两个白色就不行了。

最后检查所有白色点，对应到的就是不被选的点，找出它们对应的 ，全部依次推进答案中，输出即可。

一点小细节，环可能不止一个。

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
// Copyright 2023 Lotuses
#define tsz signed
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

const int maxn = 1e6 + 10;
int n, in[maxn], col[maxn], to[maxn];
std::queue<int> q;
std::vector<int> ans;

tsz main() {    
    read(n);
    for (int i = 1; i <= n; i++) {
        read(to[i]);
        in[to[i]]++;
    }
    memset(col, -1, sizeof(col));
    for (int i = 1; i <= n; i++) {
        if (!in[i]) q.push(i), col[i] = 0;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (!col[u]) col[to[u]] = 1;
        in[to[u]]--;
        if (in[to[u]] <= 0) {
            if (!(~col[to[u]])) col[to[u]] = 0;
            q.push(to[u]);
        }
    }
    int rt = -1;
    for (int i = 1; i <= n; i++) {
        if (in[i] > 0) {
            rt = -1;
            int u = i;
            while (to[u] != i) {
                if (~col[u]) {
                    rt = u;
                }
                u = to[u];
            }
            if (~col[u]) {
                rt = u;
            }
            if (!(~rt)) {
                col[i] = 0;
                rt = i;
            } // 找环上有颜色的起点，找不到任选起点

            u = rt;
            in[u]--;
            while (to[u] != rt) {
                if (!col[u]) {
                    col[to[u]] = 1;
                } else if (!(~col[to[u]])) {
                    col[to[u]] = 0;
                }
                in[to[u]]--;
                u = to[u];
            }
            if (!col[u] && !col[to[u]]) {
                puts("-1");
                return 0;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!col[i]) {
            ans.push_back(to[i]);
        }
    }
    writeln(ans.size());
    for (int e : ans) {
        write(e); putchar(' ');
    }
    puts("");
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可