自动搬运

查看原文

来自洛谷，原作者为

	gyh20 orz Feecle6418

搬运于2025-08-24 22:33:53，当前版本为作者最后更新于2021-09-24 18:43:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑移动的一个过程，每次让原本不相邻的 $x$ 和 $x+1$ 变得相邻，也就是说，我们可以把每一条极长「龙」（即同一列中 $a_i=x+1,a_{i+1}=x$ 的极长连续段）缩在一起，称为一个点，则每次移动后点数 $-1$，也就是说如果有解，那么步数一定是点数 $-1$。

现在先是如何判定有解，应该可以通过暴力找所有可移动的点移动来实现模拟的效果，但这样难写，并且对第二问帮助不大。

考虑建出如下一个图，$i\rightarrow j$ 存在表示 $i$ 需要在 $j$ 之前移动，那么这样的边又分为两种：

$1.$ $i$ 同一牌堆，且比 $i$ 更靠右的点需要先被移开才能移动 $i$。

$2.$ 假设 $i$ 需要移动到的位置是 $x$，则与 $x$ 同一牌堆，且比 $x$ 更靠右的点需要先被移开才能把 $i$ 移到 $x$ 后方。

这两种建边都可以直接后缀优化建图做到 $O(n)$ 的复杂度。

则有解当且仅当这个图是一个 DAG。

第二问的答案也很明显，即对于 $x$ 所对应的点考虑有多少 DAG 上的点可达它，可以直接使用 bitset 做到 $O(\dfrac{n^2}{w})$，注意拓扑排序删不掉的点答案是 $-1$，以及最后一个点（即 $n$ 所属的点）答案为 $-1$。

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
int n,m,fa[50002],sum,px[50002],py[50002],mx[50002],head[50002],cnt,low[50002],d[50002],S,ed[50002],lst;
vector<int>V[50002];
queue<int>q;
bitset<50002>B[50002];
struct edge{int to,next;}e[100002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;++d[y];}
inline int root(re int x){return x==fa[x]?x:fa[x]=root(fa[x]);}
int main(){
	read();
	n=read(),m=read();
	for(re int i=1;i<=n;++i)fa[i]=i,ed[i]=i;
	for(re int i=1;i<=m;++i){
		re int x=read();
		while(x--)V[i].push_back(read());
		for(re int j=1;j<V[i].size();++j)if(V[i][j]==V[i][j-1]-1)fa[V[i][j]]=V[i][j-1],ed[root(V[i][j])]=V[i][j];
		if(V[i].size())lst=V[i][0];
		for(re int j=1;j<V[i].size();++j)if(fa[V[i][j]]==V[i][j])add(V[i][j],lst),lst=V[i][j];
		for(re int j=0;j<V[i].size();++j)px[V[i][j]]=i,py[V[i][j]]=j; 
	}
	for(re int i=1;i<=n;++i)sum+=fa[i]==i;
	for(re int i=1;i<=m;++i)mx[i]=0;
	for(re int i=1;i<=m;++i){
		for(re int j=0;j<V[i].size();++j)
			if(fa[V[i][j]]==V[i][j]&&V[i][j]!=n){
				re int x=ed[root(V[i][j]+1)];
				if(py[x]==V[px[x]].size()-1)continue;
				x=V[px[x]][py[x]+1];
				add(x,V[i][j]);
			}
	}
	for(re int i=1;i<=n;++i)if(!d[i])q.push(i);
	while(!q.empty()){
		re int x=q.front();q.pop();++S;B[x][x]=1;
		if(x==n)continue;
		for(re int i=head[x];i;i=e[i].next){
			B[e[i].to]|=B[x];
			if(!--d[e[i].to])q.push(e[i].to);
		}
	}
	re int ss=0;
	for(re int i=1;i<=n;++i)ss|=d[i];
	if(ss)puts("NO");
	else puts("YES"),printf("%d\n",sum-1);
	B[n].reset();
	for(re int i=1;i<=n;++i){
		re int x=root(i);
		if(!B[x].count()||d[x])puts("-1");
		else printf("%d\n",B[x].count());
	}
}