题解：P9287 [ROI 2018] Viruses

· · 题解

注意到，这是一道假扮成 OI 题的语文阅读理解题。

题意

有 n 个细胞和 n 种病毒，编号均 1 \sim n。

每个时刻每个细胞都会感染恰好一个病毒。令当前细胞 i 中感染的病毒编号为 c_i。最开始第 i 个细胞感染的病毒是 i，即 c_i = i。

在每个细胞心目中都有对每个病毒的能力的排名。即给定一个 n \times n 的矩阵 a，其中 a_{i, j} 表示在第 i 个细胞心目中，病毒 j 是第几强的。例如若 a_{1,1}=2,a_{1,2}=1,a_{1,3}=3 则表示细胞 1 认为病毒 2 最强，病毒 1 其次，病毒 3 最菜。

细胞会互相攻击。当细胞 i 攻击细胞 j 时，如果 a_{j,c_i} > a_{j,c_j}，则细胞 j 将会感染病毒 c_i，即 c_j \gets c_i。即当细胞 j 认为 i 的病毒更强时，它会放弃自己现有的病毒，而感染更强的。

细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时，游戏宣告结束。显然游戏的最终局面（c_1\dots c_n）可能不唯一。

我们定义在某个游戏的最终局面里，一个病毒是「牛的」，这个病毒没有灭绝，即存在至少一个细胞感染了这个病毒。

你需要解决两个问题：

Part.1 「稳定的病毒」

考虑求解哪些病毒是「稳定的」。

我们断言病毒 i 是「稳定的」当且仅当 a_{i, 1} = i，即细胞 i 认为病毒 i 是最强的。

我们考虑题目中描述的能够发生感染的条件：

当细胞 i 攻击细胞 j 时，……，当细胞 j 认为 i 的病毒更强时，它会放弃自己现有的病毒，而感染更强的。

我们知道细胞 i 最开始感染的是病毒 i，所以细胞 i 最开始感染的就是它认为的最强的病毒。而接下来的感染过程如果能够发生，就代表感染源是一种（细胞 i 认为的）更强的病毒。显然这矛盾。

Part.2 「可行的病毒」

考虑求解哪些病毒是「可行的」。

首先以 \mathcal O(n) 的复杂度枚举 i，表示我们要判断病毒 i 是否「可行」。

根据题目描述，如果病毒 i 可行，那么当游戏结束时它一定存在于某个细胞内。不妨再以 \mathcal O(n) 的复杂度枚举 j 表示判断是否存在一种游戏的最终局面，使得细胞 j 感染了病毒 i。如果不存在这样的 j 则病毒 i 不是「可行的」。

游戏结束的条件是不存在任何一对细胞可以攻击。那么如果病毒 k 满足它在细胞 i 心中比病毒 j 要强（即 a_{i, k} < a_{i, j}），而且存在一个细胞 l（l \ne i） 感染了病毒 k，那么当前游戏是不能结束的。因为细胞 l 还可以攻击细胞 j。

这给我们的启发是，只有在当前局面里，细胞 i 心目中比病毒 j 强的病毒都灭绝（即不存在任何一个细胞感染这个病毒）时，游戏才会在此时结束。而此时结束就满足了我们的设想：细胞 j 感染了病毒 i。

所以我们现在要判断是否每个（在细菌 j 心目中）比病毒 i 强的病毒 k 都存在至少一种方案灭绝。

如何把病毒 k 灭绝？我们知道（在细菌 j 心目中）比病毒 i 弱的病毒存在是没有影响的，所以我们可以用这些病毒把病毒 k 灭绝。

把病毒 k 灭绝还需要满足一个条件，就是杀它的病毒（在细菌 k 心目中）要比病毒 k 强。因此我们把满足上个条件的病毒标记，然后枚举（在细菌 k 心目中）比病毒 k 强即可。

代码

int n, p, a[N][N], b[N][N];
// a[i][j] 表示在细菌 i 心目中第 j 强的病毒
// b[i][j] 表示在细菌 i 心目中第 j 个病毒的排名
bool st[N];     // 把在细菌 j 心目中比病毒 i 强的病毒标记

signed main() {
    cin >> n;

    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j <= n; ++ j ) {
            cin >> a[i][j];
            b[i][a[i][j]] = j;
        }

    vector<int> res;
    cin >> p;
    if (p == 1) {
        for (int i = 1; i <= n; ++ i )
            if (a[i][1] == i) res.push_back(i);
    } else {
        for (int i = 1; i <= n; ++ i ) {        // 判断病毒 i 能否活下来
            bool Alive = false;         // 判断病毒 i 能否在任意一个细菌 j 中活下来
            for (int j = 1; j <= n && !Alive; ++ j )
                if (b[j][i] <= b[j][j]) {               // 首先它要比细菌 j 中最初的病毒（病毒 j）要强，不然没机会
                    memset(st, 0, sizeof st);

                    for (int k = 1; k < b[j][i]; ++ k ) {
                        st[a[j][k]] = true;     // 把在细菌 j 心目中比病毒 i 强的病毒标记
                    }

                    bool all_destroyed = true;      // 判断在细菌 j 心目中比病毒 i 强的病毒标记是否都灭绝
                    for (int k = 1; k < b[j][i] && all_destroyed; ++ k ) {
                        int x = a[j][k];        // 取出一个在细菌 j 心目中比病毒 i 强的病毒

                        bool ok = false;        // 判断是否存在一个没有标记的病毒，且在细菌 x 心目中比病毒 x 强
                        for (int l = 1; l < b[x][x] && !ok; ++ l )
                            if (!st[a[x][l]]) ok = true;

                        if (!ok) all_destroyed = false;
                    }

                    if (all_destroyed) Alive = true;
                }

            if (Alive) res.push_back(i);
        }
    }

    cout << res.size() << '\n';
    for (int v : res) cout << v << ' ';

    return 0;
}