共有 \(m\) 位玩家,每位玩家初始生命数量为 \(3\),一位玩家公认活着当且仅当生命值非 \(0\)。
对于活着的玩家 \(u\) 与 \(v\),若 \(u\) 追杀 \(v\) 则 \(v\) 生命数量扣除一次。注意,如果 \(u\) 或 \(v\) 不为公认活着,则没有影响。
共有 \(n\) 次追杀,地 \(i\) 次为 \(u_i\) 追杀 \(v_i\)。
现在你可以选择任意的 \(i, v\) 使得 \(1 \le i \le n+1\) 且 \(1 \le v \le m\),穿越到第 \(i-1\) 次追杀之后,第 \(i\) 次追杀之前,并追杀玩家 \(v\)。特殊地,\(i = n+1\) 表示穿越到第 \(n\) 次追杀后。
对于每一个 \(x\) 使得 \(1 \le x \le m\),求有多少种 \(i, v\) 使得最终有 \(x\) 个玩家公认活着。
\(1 \le n \le 6\times10^4\),\(1 \le m \le 10^3\),\(1 \le u_i, v_i \le m\)。
暴力模拟即可。
枚举 \(i, v\) 然后 \(O(n)\) 统计剩余玩家数量,时间复杂度 \(O(n^2m)\)。
我们发现穿越之后的模拟追杀过程很难优化,于是可以考虑优化穿越次数。
我们不希望进行两次结果相同的穿越,例如对于 \([(1, 2), (2, 3), (1, 3)]\),插入 \((0, 1)\) 到四个不同的位置,结果不变。
考虑在 \((u_i, v_i)\) 前插入怎样的追杀不会导致结果相同。
追杀玩家 \(x\),\(x \neq u_i\),\(x \neq v_i\)。我们发现 \([(0, x), (u_i, v_i)]\) 与 \([(u_i, v_i), (0,x)]\) 结果相同,所以无效。
追杀玩家 \(v_i\)。我们发现 \([(0, x), (u_i, v_i)]\) 与 \([(u_i, v_i), (0,x)]\) 结果相同,所以无效。
于是 \(u_i, v_i\) 之前只需要尝试追杀 \(u_i\),时间复杂度降为 \(O(n^2)\)。
当然这档部分分也可以用暴力+比较好的剪枝水过
再次观察发现,如果 \(u_i\) 或 \(v_i\) 已经非公认活着,那么所有穿越都无效。
考虑到每位玩家只有三滴血,所以最多只需要穿越 \(3m\) 次,时间复杂度复杂度降为 \(O(nm)\)。
#include <bits/stdc++.h> using namespace std; const int L = 1e5 + 5; int n, m, cnt, tmp, u[L], v[L], a[L], b[L], ans[L], las[L]; bool f[L]; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d %d", &u[i], &v[i]); for (int j = 1; j <= m; j++) b[j] = 3; for (int j = 1; j <= n; j++) if (b[u[j]] != 0 && b[v[j]] != 0) b[v[j]]--, f[j] = true; for (int i = 1; i <= m; i++) if (b[i] != 0) tmp++; for (int i = 1; i <= n; i++) { if (!f[i]) continue; cnt = 0; for (int j = 1; j <= m; j++) a[j] = 3; for (int j = 1; j <= n; j++) { if (i == j && a[u[i]] != 0) a[u[i]]--; if (a[u[j]] != 0 && a[v[j]] != 0) a[v[j]]--; } for (int j = 1; j <= m; j++) if (a[j] != 0) cnt++; ans[cnt] += i - las[u[i]]; las[u[i]] = i; } for (int i = 1; i <= m; i++) ans[tmp - (b[i]==1)] += n + 1 - las[i]; for (int i = 0; i <= m; i++) printf("%d ", ans[i]); return 0; }