题解 P7568 【「MCOI-05」追杀】

littleKtian · 2021-05-02 17:50:19 · 题解

设 f_{i,j} 表示在第 i 次追杀前追杀第 j 名玩家时最后剩余玩家数。

如果第 i 次追杀在正常流程时就没有生效，那么 f_{i,j}=f_{i+1,j}。如果 j 不是第 i 次追杀的执行者（即 j\neq u_i），那么也有f_{i,j}=f_{i+1,j}。这两个的证明都比较显然。

注意到 n 的数值比较大而 m 的数值较小，说明在整个追杀过程中真正生效的追杀次数很少（最多 3m 次），于是我们可以对每个真正生效的追杀重新暴力跑一遍结果，其他直接沿用，总复杂度就是 O(nm) 的了。

小优化：并不是所有生效的追杀都要重新跑一遍，只需要对其中追杀者血量为 1 的追杀再跑一遍。同样能证明这是正确的但并不能从根本上优化复杂度。

#include<bits/stdc++.h>
using namespace std;
int h[1001],lh[1001];
int n,m,u[60001],v[60001];
int li[1001],ans[1001];
int dr()
{
    int xx=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')xx=(xx<<1)+(xx<<3)+ch-'0',ch=getchar();
    return xx;
}
int main()
{
    n=dr(),m=dr();
    for(int i=1;i<=n;i++)u[i]=dr(),v[i]=dr();
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)h[j]=3;
        --h[i];
        for(int j=1;j<=n;j++)if(h[u[j]]&&h[v[j]])--h[v[j]];
        for(int j=1;j<=m;j++)if(h[j])++li[i];
    }
    for(int i=1;i<=m;i++)h[i]=3;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)++ans[li[j]];
        if(h[u[i]]&&h[v[i]])
        {
            --h[v[i]];
            memcpy(lh,h,sizeof(h));
            if(lh[u[i]])
            {
                --lh[u[i]];
                if(lh[u[i]]==0)
                {
                    for(int j=i+1;j<=n;j++)if(lh[u[j]]&&lh[v[j]])--lh[v[j]];
                    li[u[i]]=0;
                    for(int j=1;j<=m;j++)if(lh[j])++li[u[i]];
                }
            }
        }
    }
    for(int i=1;i<=m;i++)++ans[li[i]];
    for(int i=0;i<=m;i++)printf("%d ",ans[i]);
}