题解：P10537 [APIO2024] 九月

rhn7 · 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;
}