P10537 [APIO2024] 九月 题解

· · 题解

场外选手来凑热闹。

先考虑 M=1 怎么做。从左往右扫描记录序列并进行删叶子的操作，注意如果当前操作到一个结点但是它的子树还没有删空，那么就先不对其进行操作并对其进行标记；如果它的子树已经删空了就代表可以对其进行操作，操作后从它开始不断往父亲跳，如果到了某个祖先后，该祖先被标记且其子树内没有标记，那么就去掉该祖先的标记；否则结束跳父亲的过程。以上所有操作结束后如果树里面没有被标记的结点，那么就代表可以结束一天（即结束了该操作后正好有若干个完整的一天过去），答案加一即可。

如果 M>1 即有多个志愿者，对于每个志愿者维护上面的过程；一个操作结束后，可以得出“所有志愿者对应的树内都没有被标记的结点”是“可以结束一天”的必要不充分条件。为什么不充分？因为对于每个志愿者，对于某一天他们记录下来的树叶的集合应相同，而上面的过程没有考虑这一点；判断这个条件是否成立等价于判断对于每个志愿者这些“操作前缀”内的所有元素构成的集合（即不考虑顺序）是否相同；可以用 \cos 和来维护这一点（出题人卡了 \sin 和）。

于是签到题就做完了。时间复杂度 O(NM\log N)。

参考代码（GNU C++17）：

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
int solve(int n,int m,vector<int> f,vector<vector<int> > s){
  int c=0;
  vector g(m,vector<set<int> >(n));
  // 每个志愿者的树
  vector v(m,vector<bool>(n));
  // 每个志愿者的树里面的结点是否在之前尝试删除过
  vector<set<int> > t(m);
  // 每个志愿者的树里面有标记的结点
  for(int i=0;i<m;i++)
    for(int j=1;j<n;j++)
      g[i][f[j]].emplace(j);
  vector<double> a(m);
  // 记录前缀 cos 和
  for(int i=0;i<n-1;i++){
    bool b=true;
    for(int j=0;j<m;j++){
      int x=s[j][i];
      v[j][x]=true,t[j].emplace(x),a[j]+=cos(x);
      // 打标记
      if(g[j][x].empty()){
        while(x&&v[j][x]&&g[j][x].empty())
          t[j].erase(x),g[j][f[x]].erase(x),x=f[x];
      } // 可以删除，进行跳父亲删标记
      b&=t[j].empty(); // 判断是否有被标记的点
    }
    for(int j=1;j<m&&b;j++)
      b&=fabs(a[j]-a[j-1])<eps;
      // 判断前缀构成的集合是否相等
    c+=b;
  }
  return c;
}