「MCOI-05」追杀 题解

发布于 2021-05-04  101 次阅读


题意

题目链接

题意有点复杂,大意是有一个猎杀游戏,有 $m$ 名玩家,每名玩家初始有 $3$ 点生命。有 $n$ 个时刻,每个时刻会发生形如 $u_i$ 杀 $v_i$ 的事件,若 $u_i$ 和 $v_i$ 都存活,则 $v_i$ 生命值减 $1$,若生命值为 $0$ 则死亡。现在发生了一次特殊事件:穿越者穿越到某一次追杀后(可以是第 $0$ 次也可以是最后一次)对某一名玩家造成一点伤害。求对于每一个 $x \in[0,m]$,有多少种穿越方案使最后有 $x$ 名玩家活着。

解析

记穿越者编号为 $0$。我们发现一件事情,对于一个事件 $(u_i,v_i)$,若 $x$ 不为 $u_i$ ,在它之前插入 $(0,x)$ 和在它之后插入 $(0,x)$ 是等价的。证明:若 $x$ 为 $v_i$ 相当于依次攻击 $v_i$,是谁攻击的是没有区别的,因此与 $(0,x)$ 的位置前后无关;若 $x$ 不为 $u_i$ 且不为 $v_i$,则该事件与 $u_i,v_i$ 均无关,显然也是等价的。

因此,我们考虑在每一个事件前尝试插入 $(0,u_i)$,容易发现每一次插入后模拟进程的复杂度是 $O(n)$。再考虑一个显然的优化:如果 $u_i$ 或 $v_i$ 已死亡,则不用尝试。我们称 $u_i$ 和 $v_i$ 均未死亡发生的事件为有效事件,则至多进行 $3m-1$ 个有效事件(最后只剩一个人活着且只有 $1$ 滴血)。因此最终时间复杂度为 $O(mn)$。

接着考虑统计答案,我们可以用 $now$ 数组记录每一个玩家当前已统计到的位置,然后每次插入后,更新 $now_x$($x$ 为尝试攻击的玩家),并将对应的答案加上 $p-now_x $($p$ 为插入位置)。最后再在所有操作结束之后尝试攻击每一个人,并将对应的答案加上 $n+1-now_x$。因为除了插入位置以外,其他位置都等价于在其下一个位置插入,所以对应答案可以直接用当前位置减去上一个插入的位置(即 $now_x$)。详见代码,配有注释。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=6e4+5;
int n,m,v[N],u[N],a[N],ans[N],b[N],now[N];
inline void attack(int p,int x){
    for(int i=1;i<=m;i++) b[i]=a[i];
    b[x]--;//插入的攻击
    for(int i=p;i<=n;i++) if(b[u[i]]&&b[v[i]]) b[v[i]]--;//简单的模拟
    int t=0;
    for(int i=1;i<=m;i++) if(b[i]) t++;//统计存活人数
    ans[t]+=(p-now[x]);now[x]=p;//更新对应答案和 now[x]
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&u[i],&v[i]);
    for(int i=1;i<=m;i++) a[i]=3;//初始生命值
    for(int i=1;i<=n;i++){
        if(a[u[i]]&&a[v[i]]){//如果是有效攻击
            attack(i,u[i]);//尝试插入
            a[v[i]]--;//血量减 1
        }
    }
    int t=0;
    for(int i=1;i<=m;i++) if(a[i]) t++;
    for(int i=1;i<=m;i++){//最后再尝试攻击每一个人
        if(a[i]==1) ans[t-1]+=n+1-now[i];
        else ans[t]+=n+1-now[i];
    }//至此,所有可能的情况都被统计完了
    for(int i=0;i<=m;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣