P9287【Viruses】题解

· · 题解

个人认为，这题完全跟模拟没关系，只要充分理解题意，然后分两种情况讨论，最后再枚举即可。

分类讨论

  1. 对于 p 为 1 的时候，只有不会被感染的细胞的病毒才是 \lceil 稳定的病毒 \rfloor，所以输出所有对本身病毒易感染度最高的病毒即可。

  2. 对于 p 为 2 的情况，我们令病毒 i 攻击细胞 j，再枚举 j 的可能病毒 k。对于 k，病毒 k 必须可以感染细胞 j。对于所有满足条件的 k，记 i 的易感染度最低的 k 的易感染度为 minx_{i,j}，记 t_i 为最大的 minx_{i,x},1\le x\le n。对于任意 {i,j}(1\le i,j \le n)，如果病毒 i 可以感染细胞 j，且病毒 j 的所有可感染细胞的最大易感染度低于细胞 j 对病毒 i 的易感染度，则病毒 i 可以通过感染 j 来感染所有病毒 j 可以感染的细胞，那么病毒 i 就是 \lceil 可行的病毒 \rfloor。

代码部分

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, v[505][505], p, cnt, ans[505], f[505][505], t[505];
signed main ()
{
    ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
    cin >> n;
    //因为没有给出具体的易感染度，只有相对值，所以用 f[i][j] 记录细胞 i 对病毒 j 的易感染度优先级。
    for (int i = 1; i <= n; ++ i)for (int j = 1; j <= n; ++ j){cin >> v[i][j];f[i][v[i][j]] = j;}
    cin >> p;
    //稳定的病毒，按分类讨论中的结论统计即可。
    if (p == 1)
    {
        for (int i = 1; i <= n; ++ i)if (v[i][1] == i)ans[++ cnt] = i;
        cout << cnt << '\n';
        for (int i = 1; i <= cnt; ++ i)cout << ans[i] << ' ';
        return 0;
    }
    for (int i = 1; i <= n; ++ i)
    {
        t[i] = n;
        for (int j = 1; j <= n; ++ j)
        {
            //优先级越大易感染度越小，最小的优先级易感染度最大。
            int ma = 0;
            for (int k = 1; k <= n; ++ k)if (f[j][k] <= f[j][j] && ma < f[i][k])ma = f[i][k];
            t[i] = min (ma, t[i]);
        }
    }
    for (int i = 1; i <= n; ++ i)for (int j = 1; j <= n; ++ j)if (t[j] >= f[j][i] && f[j][i] <= f[j][j])//按分类讨论的结论判定即可
    {
        ans[++ cnt] = i;
        break;
    }
    cout << cnt << '\n';
    for (int i = 1; i <= cnt; ++ i)cout << ans[i] << ' ';
    return 0;
}