自动搬运

查看原文

来自洛谷，原作者为

	MnZnOIer The name in the past : Y_QWQ_Y

搬运于2025-08-24 22:47:02，当前版本为作者最后更新于2024-08-26 16:26:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

分类讨论

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;
}