[ROI 2018] Viruses

GitHub 跳转原题关系图返回列表

稳定病毒只可能是本细胞最强病毒；可行病毒则枚举终点细胞，判断所有更强病毒能否被更弱的安全病毒逐个消灭。

OJ: luogu

题目 ID: P9287

难度:提高+/省选-

标签:思维构造

日期: 2026-06-19 02:18

题意

有 n 个细胞、n 个病毒。

初始时第 i 个细胞感染第 i 个病毒。每个细胞对所有病毒都有一套从强到弱的排名。

如果一个感染了病毒 x 的细胞攻击另一个当前感染病毒 y 的细胞 j，并且细胞 j 认为 x 比 y 更强，那么细胞 j 就会改感染 x。

所有攻击顺序都可以任意安排，直到再也没有感染能发生为止。

输入最后一个参数 p：

p = 1：要求输出所有稳定病毒，也就是无论怎么安排攻击顺序，最终都一定不会灭绝的病毒。
p = 2：要求输出所有可行病毒，也就是至少存在一种攻击顺序，使它最终不会灭绝的病毒。

思路

先看最直接的做法：把当前每个细胞感染的病毒都维护下来，然后暴力枚举所有可能的攻击顺序，搜索所有终局：

cpp

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解。
// 直接搜索所有可能的感染过程，收集所有终局，再统计稳定 / 可行病毒。
const int MAXN = 8;

int n, p;
int a[MAXN][MAXN];
int rk[MAXN][MAXN];

vector<vector<int>> states;
map<vector<int>, int> id_of;
queue<int> que;
vector<vector<int>> terminal_states;

int get_id(const vector<int> &state) {
    map<vector<int>, int>::iterator it = id_of.find(state);
    if (it != id_of.end()) {
        return it->second;
    }
    int id = (int)states.size();
    states.push_back(state);
    id_of[state] = id;
    que.push(id);
    return id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= n; k++) {
            cin >> a[i][k];
            rk[i][a[i][k]] = k;
        }
    }
    cin >> p;

    vector<int> start(n + 1);
    for (int i = 1; i <= n; i++) {
        start[i] = i;
    }
    get_id(start);

    while (!que.empty()) {
        int id = que.front();
        que.pop();

        vector<int> cur = states[id];
        bool moved = false;

        for (int from = 1; from <= n; from++) {
            int virus = cur[from];
            for (int to = 1; to <= n; to++) {
                if (from == to) {
                    continue;
                }
                if (rk[to][virus] < rk[to][cur[to]]) {
                    moved = true;
                    vector<int> nxt = cur;
                    nxt[to] = virus;
                    get_id(nxt);
                }
            }
        }

        if (!moved) {
            terminal_states.push_back(cur);
        }
    }

    vector<int> feasible(n + 1, 0);
    vector<int> stable(n + 1, 1);

    for (int idx = 0; idx < (int)terminal_states.size(); idx++) {
        vector<int> used(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            used[terminal_states[idx][i]] = 1;
        }
        for (int v = 1; v <= n; v++) {
            if (used[v]) {
                feasible[v] = 1;
            } else {
                stable[v] = 0;
            }
        }
    }

    vector<int> ans;
    if (p == 1) {
        for (int v = 1; v <= n; v++) {
            if (stable[v]) {
                ans.push_back(v);
            }
        }
    } else {
        for (int v = 1; v <= n; v++) {
            if (feasible[v]) {
                ans.push_back(v);
            }
        }
    }

    cout << ans.size() << '\n';
    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

这个暴力只能做很小的数据，但它能帮助我们看清题目结构。

稳定病毒

先处理 p = 1。

如果病毒 i 在细胞 i 心中就是最强的，那么细胞 i 永远不可能被别的病毒感染，因此病毒 i 一定不会灭绝。

反过来，如果病毒 i 不是细胞 i 心中的最强病毒，那么总存在某个更强病毒可以在合适时机感染细胞 i，于是病毒 i 不一定能保住。

所以稳定病毒的判定非常简单：

a[i][1] == i

也就是在细胞 i 的强弱排名里，第 1 名恰好是病毒 i。

可行病毒

再处理 p = 2。

枚举一个病毒 i，思考它能不能在某个终局里活下来。

如果它能活下来，那么终局里它一定至少占据某个细胞 j。于是我们继续枚举这个目标细胞 j。

要让终局时细胞 j 感染病毒 i，首先必须满足：

病毒 i 对细胞 j 来说，至少不比初始病毒 j 更弱。
否则从头到尾，病毒 i 都没有机会感染到 j。

接下来考虑哪些病毒会阻止这个终局成立。

如果某个病毒 x 在细胞 j 心中比病毒 i 更强，而且终局时它还活着，那么任意一个感染 x 的细胞都还能继续攻击 j，说明这就不是终局。

因此，所有在细胞 j 心中比 i 更强的病毒，都必须能够被消灭。

一个更强病毒怎么被消灭

固定这样一个更强病毒 x。

想消灭它，只需要找到某个病毒 y：

在细胞 j 心中，y 不能比 i 更强。
否则就算 y 帮我们消灭了 x，它自己也会继续威胁 j。
在细胞 x 心中，y 要比 x 更强。
这样 y 才能去感染细胞 x，把病毒 x 杀掉。

所以对每个 (i, j)，我们只要检查：

在细胞 j 心中所有比 i 更强的病毒 x
是否都存在一个“安全病毒” y，满足
- y 在细胞 j 心中不比 i 更强
- y 在细胞 x 心中比 x 更强

如果每个这样的 x 都能被某个安全病毒消灭，那么病毒 i 就可以在细胞 j 活下来。

如何优化

为了快速判断“是否存在这样的安全病毒 y”，我们预处理：

best[j][x] = 在细胞 x 心中比 x 更强的所有病毒里，它们在细胞 j 心中的最靠后排名

如果 best[j][x] >= rank[j][i]，说明确实存在一个病毒 y：

它在细胞 x 心中比 x 强；
它在细胞 j 心中排在 i 后面或就是 i，因此是安全的。

这样枚举病毒 i、目标细胞 j、再检查所有更强病毒 x 即可，总复杂度 $O(n^3)$ 。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n, p;
int a[MAXN][MAXN];     // a[i][k] 表示在细胞 i 心中第 k 强的病毒编号
int rk[MAXN][MAXN];    // rk[i][v] 表示病毒 v 在细胞 i 心中的排名，1 表示最强
int best_pos[MAXN][MAXN]; // best_pos[j][x]：在细胞 x 心中比 x 强的病毒里，它们在细胞 j 心中的最靠后排名

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= n; k++) {
            cin >> a[i][k];
            rk[i][a[i][k]] = k;
        }
    }
    cin >> p;

    // 预处理 best_pos[j][x]。
    // 枚举“被消灭的病毒 x”，以及在细胞 x 心中比它更强的病毒 y，
    // 再看这些 y 在目标细胞 j 心中的最大排名是多少。
    for (int x = 1; x <= n; x++) {
        for (int pos = 1; pos < rk[x][x]; pos++) {
            int y = a[x][pos];
            for (int j = 1; j <= n; j++) {
                best_pos[j][x] = max(best_pos[j][x], rk[j][y]);
            }
        }
    }

    vector<int> ans;

    if (p == 1) {
        // 稳定病毒：自己在自己家里就是最强。
        for (int i = 1; i <= n; i++) {
            if (a[i][1] == i) {
                ans.push_back(i);
            }
        }
    } else {
        // 可行病毒：枚举病毒 i，再枚举它最终停留的细胞 j。
        for (int i = 1; i <= n; i++) {
            bool alive = false;

            for (int j = 1; j <= n && !alive; j++) {
                // 病毒 i 至少要有机会感染到细胞 j。
                if (rk[j][i] > rk[j][j]) {
                    continue;
                }

                int pos_i = rk[j][i];
                bool ok = true;

                // 在细胞 j 心中比 i 更强的每个病毒 x，都必须能够被某个“安全病毒”杀掉。
                for (int pos = 1; pos < pos_i; pos++) {
                    int x = a[j][pos];
                    if (best_pos[j][x] < pos_i) {
                        ok = false;
                        break;
                    }
                }

                if (ok) {
                    alive = true;
                }
            }

            if (alive) {
                ans.push_back(i);
            }
        }
    }

    cout << ans.size() << '\n';
    for (int idx = 0; idx < (int)ans.size(); idx++) {
        if (idx) {
            cout << ' ';
        }
        cout << ans[idx];
    }
    cout << '\n';

    return 0;
}

复杂度

时间复杂度： $O(n^3)$
空间复杂度： $O(n^2)$

总结

这题最容易误判的地方是把感染过程本身想得太复杂。

稳定病毒只和“自己在自己家里是不是第一名”有关；
可行病毒则只需要固定一个终点细胞，再判断所有更强病毒能不能被更安全的病毒逐个清掉。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P9287 [ROI 2018] Viruses

题目背景

译自 ROI 2018 Day1 T2. Вирусы (Viruses)。

题目描述

现在有 $n$ 只细胞与 $n$ 个病毒， $i$ 号细胞的初始病毒的序号也为 $i$ ，每个细胞心中对每位病毒都有一定的易感染度。

细胞之间可以互相攻击，如果细胞甲攻击了细胞乙，且乙「对甲现在的病毒的易感染度」比「对自家病毒的易感染度」高，那么乙就会被甲的病毒感染（成为甲的病毒的细胞）。

细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时，游戏宣告结束。

如果存在一种攻击顺序，使得病毒 $i$ 最终拥有一只或以上的细胞，那么我们则称病毒 $i$ 为「可行的病毒」。如果对于任意一种攻击顺序，都使得病毒 $i$ 最终拥有一只或以上的细胞，那么我们则称病毒 $i$ 为「稳定的病毒」。

现在病毒们想知道，有多少个可行的病毒与稳定的病毒。

输入格式

第一行一个正整数 $n$ ，表示细胞与病毒的数量。

下面 $n$ 行，每行 $n$ 个正整数，表示每名病毒按当前细胞心中的易感染度降序排列后的病毒编号序列。

比如输入了 2 1 3，则表示该细胞对 $2$ 号病毒的易感染度最高，对 $1$ 号病毒的易感染度第二高，对 $3$ 号病毒的易感染度最差。

最后一行一个整数 $p$ 。

输出格式

第一行，一个整数 $x$ 。如果 $p=1$ ，输出稳定的病毒数量；如果 $p=2$ ，输出可行的病毒的数量。

接下来一行， $x$ 个整数，表示这 $x$ 个病毒的编号，按升序排列。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
22
1 2

输入输出样例 #2

输入 #2

text

输出 #2

text

1
21
3

输入输出样例 #3

输入 #3

text

输出 #3

text

1
23
1 3 4

说明/提示

对于所有的数据， $1 \leq n \leq 500$ 。

子任务编号	$n$	$p$
$1$	$1 \leq n \leq 5$	$p = 1$
$2$	$1 \leq n \leq 500$	$p = 1$
$3$	$1 \leq n \leq 5$	$p = 1,2$
$4$	$1 \leq n \leq 50$	$p = 1,2$
$5$	$1 \leq n \leq 500$	$p = 1,2$

[ROI 2018] Viruses

目录

题意

思路

稳定病毒

可行病毒

一个更强病毒怎么被消灭

如何优化

代码

复杂度

总结

一图流解析