自动搬运

查看原文

来自洛谷，原作者为

	rhn7 洛谷用户数：1789309

搬运于2025-08-24 22:58:59，当前版本为作者最后更新于2024-05-30 20:13:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

APIO 第一题居然这么简单，感觉大佬们的题解都做复杂了。

由于要求划分的区间数尽可能多，每次划分的位置要尽可能靠前，现在的目标就是 $O(1)$ 判断新划分的区间是否合法。

将区间 $[l,r]$ 是否合法转化为区间 $[1,r]$ 是否合法，因为之前划分完的区间 $[1,l-1]$ 肯定合法。那怎么判断区间 $[1,r]$ 是否合法呢？我们发现每个志愿者的区间 $[1,r]$ 在不考虑顺序的情况下要相等，这个可以用桶判断。而且题目说了只有叶子节点才能掉落，所以要存在一个顺序让每个点掉落时是叶子节点，我们可以维护每个节点的子节点数，某个时候他的子节点数为零，就说明他能掉落。

实现细节看代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],son[N];
int solve(int N,int M,std::vector<int> F,std::vector<std::vector<int>> S){
	for(int i=1;i<N;i++) h[i]=son[i]=0,son[F[i]]++;//多测清空 
	int k=0,cnt=0,cnt2=0;//cnt:出现的节点个数 cnt2: 出现的叶子节点个数
	for(int i=0;i<N-1;i++){
		for(int j=0;j<M;j++){
			int x=S[j][i];
			if(!h[x]){
				cnt++;h[x]=1;son[F[x]]--;
				cnt2+=!son[F[x]]&&h[F[x]];//父亲能掉落了，但是后面不会再访问父亲，所以得在儿子时加cnt2 
				cnt2+=!son[S[j][i]];
			}
		}
		k+=(cnt==i+1&&cnt2==i+1);
	}
	return k;
}