自动搬运

查看原文

来自洛谷，原作者为

	littleKtian MoVe yoUR BoDy

搬运于2025-08-24 22:31:07，当前版本为作者最后更新于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]);
}