CF1919D 01 Tree 题解

FFTotoro · 2024-01-07 16:56:34 · 题解

赛时做掉一个 *2100 却没有上紫名。怎么回事呢。

考虑如何快速减少树上的结点以简化问题。记 w_i 为结点 i 的权值；对于一个结点 x，如果它有儿子 x_1,x_2，那么两个儿子的权值必然一个是 w_x，一个是 w_x+1。这启发我们把两个儿子结点合并成一个父结点；这个操作等价于删除权值为 w_x+1 的结点。

但是我们不知道哪些节点是同父亲的两个叶子之一。于是从具有最大的权值的结点开始枚举（可以证明它一定是同父亲的两个叶子之一），如果在序列中相邻位置有权值比它小 1 的那么把它本身删掉，继续进行以上的过程；否则无解。

但是有可能有权值相同的结点，此时我们只需对于每种权值用一个 std::vector 把结点存下来。因为我们不知道它们的删除顺序，所有有一种暴力做法：每次从序列中找到可以删的删掉，然后再扫一遍序列继续删……这种做法是 O(n^2) 的，有两种优化方式可以供参考：

• 使用 BFS 优化：显然一个结点被删了只会影响到左右两边离它最近（这里的距离定义为数组间的下标之差）的权值相同的结点，于是每次如果将可以删的数入队，向两边拓展即可，本人考场上写的是该做法；

• 正反扫两遍：注意到每次不需要把整个序列都遍历一遍，因为每次可能影响它的只有它左边或右边最近的权值相等的结点，该做法更容易实现。

最后注意特判数列中必须有且仅有 1 个 0。

删数的实现可以借助链表。总时间复杂度 O(n)。

放代码：

#include<bits/stdc++.h>
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n; bool f=true; cin>>n;
    vector<int> a(n),l(n),p(n);
    for(int i=0;i<n;i++)l[i]=i-1,p[i]=i+1; // 链表初始化
    vector<vector<int> > v(n);
    for(auto &i:a)cin>>i;
    auto pd=[&](int x){
      return l[x]>=0&&a[l[x]]==a[x]-1||p[x]<n&&a[p[x]]==a[x]-1;
    }; // 判断是否可以删
    auto del=[&](int c){
      if(l[c]>=0)p[l[c]]=p[c];
      if(p[c]<n)l[p[c]]=l[c];
    }; // 删数过程
    for(int i=0;i<n;i++)
      v[a[i]].emplace_back(i);
    for(int i=n-1;i&&f;i--){
      if(v[i].empty())continue;
      vector<bool> b(v[i].size());
      queue<int> q;
      for(int j=0;j<v[i].size();j++)
        if(pd(v[i][j]))b[j]=true,q.emplace(j);
      while(!q.empty()){
        int x=q.front(); q.pop(),del(v[i][x]);
        if(x&&!b[x-1]&&pd(v[i][x-1]))b[x-1]=true,q.emplace(x-1);
        if(x+1<v[i].size()&&!b[x+1]&&pd(v[i][x+1]))b[x+1]=true,q.emplace(x+1);
      } // 广搜过程
      if(!*min_element(b.begin(),b.end()))f=false; // 是否都搜到了
    }
    cout<<(f&&v[0].size()==1?"Yes\n":"No\n");
  }
  return 0;
}