「MCOI-05」追杀
「MCOI-05」追杀 洛谷
题目描述
Dream SMP 具有 \(m\) 位玩家，编号为 \(1\) 至 \(m\)。初始时，每一位玩家生命数量为 \(3\)。一位玩家 公认活着（canonically alive） 当且仅当生命值非零。
Dream SMP 经常发生大型战争，于是会有玩家杀（PvP）别的玩家。对于活着玩家 \(u\) 与 \(v\)，如果 \(u\) 杀 \(v\)，\(v\) 的生命数量扣除一次。注意，如果 \(u\) 或 \(v\) 不为公认活着，杀没有影响。
总共按时序记录了 \(n\) 次追杀 \(1,2,\dots,n\)，其中第 \(k\) 次追杀为 \(u_k\) 杀 \(v_k\)。
DreamXD（玩家 \(0\)）解锁了时空穿越超能力。他现在可以选取任何 \(i,v\) 使得 \(1\le i\le n+1\) 并且 \(1\le v\le m\)，穿越到第 \(i-1\) 次追杀之后与第 \(i\) 次追杀之前，并追杀玩家 \(v\)。\(i=n+1\) 表示穿越到第 \(n\) 次追杀后。
不同 \(i\) 和 \(v\) 可能导致最终活着玩家集合不同。对于每一个 \(x\) 使得 \(0\le x\le m\)，DreamXD 想知道，有多少种 \(i,v\) 使最后公认活着玩家集合恰好含有 \(x\) 位玩家？
输入格式
第一行两个正整数 \(n,m\)。
接下来 \(n\) 行，第 \(k\) 行两个正整数 \(u_k,v_k\)，表示在第 \(k\) 时刻，\(u_k\) 追杀 \(v_k\)。
输出格式
输出一行 \(m+1\) 个正整数，其中第 \(x\) 个为最终有 \(x-1\) 位玩家活（不包含 Dream）的方案数。
样例输入
2 2
1 2
1 2
样例输出
0 3 3
提示
对于 \(100\%\) 的数据，\(1\le n\le6\times10^4\)，\(1\le m\le10^3\)，\(1\le u_i,v_i\le m\)。
题目描述有点复杂，大意为一个追杀游戏，共有 \(n\) 轮，对于每一轮，会出现 \(u_i\) 杀 \(v_i\) 的事件，每个人共有三条命，若有一次事件其中一个人没血了，那么相当于没有发生，现在我们可以穿越到 \([1,n]\) 轮前杀一个人，输出为让最后让 \(x(x\in [0,m])\) 个人活下来的方案数。
很容易想到暴力，枚举每一轮，在每一轮前枚举每一个要杀的人，再跑完所有轮，统计。
但是时间复杂度为 \(O(n^2m)\) 是不可以接受的。
考虑在第 \(i\) 轮前追杀 \(j\)，如果 \(j\) 既不是这一轮的追杀者也不是被追杀者，那么这一轮追杀 \(j\) 其实和上一轮追杀 \(j\) 是一样的。
如果 \(j\) 是被追杀者，和上面的情况是一样的。
所以说只需要考虑 \(j\) 是这一轮的追杀者的情况（因为如果你在前面追杀他，说不定他在这一轮就死了，所以需要单独考虑）。
其他的情况直接沿用就行。
最后再把第 \(1\) 轮前的情况单独统计一遍即可。
\(Code:\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int N=6e4+5,M=1e3+5;
int u[N],v[N],hp[M],kill[M],tmp[M],ans[M];
//kill[i]=在某一轮追杀i可以让多少人活下来
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld%lld",&u[i],&v[i]);
for(int i=1;i<=m;i++) hp[i]=3;
for(int i=1;i<=n;i++){
if(hp[u[i]]&&hp[v[i]]){
hp[v[i]]--;
for(int j=1;j<=m;j++) tmp[j]=hp[j];
if(tmp[u[i]]==1){
tmp[u[i]]--;
for(int j=i+1;j<=n;j++) if(tmp[u[j]]&&tmp[v[j]]) tmp[v[j]]--;
kill[u[i]]=0;
for(int j=1;j<=m;j++) if(tmp[j]) kill[u[i]]++;
}
}
for(int j=1;j<=m;j++) ans[kill[j]]++;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++) hp[j]=3;
hp[i]--;kill[i]=0;
for(int j=1;j<=n;j++) if(hp[u[j]]&&hp[v[j]]) hp[v[j]]--;
for(int j=1;j<=m;j++) if(hp[j]) kill[i]++;
}
for(int i=1;i<=m;i++) ans[kill[i]]++;
for(int i=0;i<=m;i++) printf("%lld ",ans[i]);
return 0;
}