[AGC058C] Planar Tree 题解

FFTotoro · 2022-08-18 19:52:02 · 题解

前言

赛时没做出来，赛后把题补了。果然是 maroonrk 出的，名不虚传啊……真的很好的一道题目。

解法

题目中的圆周有以下几个性质：

• 圆周上如果有相邻的等值，我们可以去掉一个而不改变答案（这个很好证明）；
• 如果 1 和 2 相邻，那么擦去 1 不影响答案；同样的道理，如果 3 和 4 相邻，擦去 4 不影响答案。

我们定义“规范化”为尽可能地多执行以上操作的过程。

任何满足要求的树也都具有满足以下条件的边：

• 边连接的两个点在圆周上相邻；
• 其中一个点是树的叶子。

所以，我们可以通过执行以下操作来形成满足条件的树：

• 选择两个相邻且可连接的点并连接它们；
• 选择其中一个点作为叶子，将它从圆周上擦除。

那么，该如何利用上述操作来简化题目呢？

我们可以发现，在“规范化”后的圆周上，我们只有可能连接编号为 2 和 3 的点。假设我们将 2 当作那片被擦掉的叶子：

• 如果圆周上有这样的一段“弧”：\cdots,4,2,3,\cdots，擦除了 2 之后 3 和 4 相邻，就可以进行“规范化”擦除，间接地相当于擦除了一对 2 和 4；
• 如果圆周上有这样的： \cdots,3,2,3,\cdots，那么按照上面的思路 2 和 3 也将被擦除；
• ……

考虑以下一系列操作：在“规范化”状态下执行上述操作，然后再次“规范化”……

如果我们也考虑把 3 当作叶子（擦除 3），这一系列操作每次可以擦除一对 (2,3),(1,3) 或 (2,4)。

如果可以重复上面的操作，且最终只有 2 和 3 在圆周上，我们就可以构造出满足条件的树。

所以，我们可以推出以下必要条件：

• 设圆环上 i 的数量为 C_i，则 C_2>C_4 且 C_3>C_1。

我们可以看到，实际上它也是充分条件。因为如果有顶点 1 或 4 在圆上，那么我们可以擦除一对 (1,3) 或 (2,4)。

我们可以在 O(n) 的时间复杂度内解决这个问题。

实现

注意到，我的代码中有一个 f 数组，其中 f=\{2,2,3,3\}。但是因为我在实现中为方便处理，将所有输入的数减去了 1，所以代码中 f=\{1,1,2,2\}。

它的作用是什么呢？判断相邻的两个点能否进行规范化操作！我们注意到，如果两个点编号为 i,j，f_i=f_j 的必要条件为 i=j 或 |i-j|=1。

所以，如果 f_i=f_j，假设 f_i=i，就代表 i=2 或 i=3，不管 j 是什么，擦掉 j 都是“规范化”过程中的合法操作。

最后再用 std::map 来统计每个数出现的数量，比较后输出即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
const vector<int> f={1,1,2,2};
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a;
    for(int i=0;i<n;i++){
      int x; cin>>x;
      if(x--;i&&f[x]==f[a.back()]){
        if(f[x]==x)a.back()=x;
      }
      else a.emplace_back(x);
    }
    if(f[a[0]]==f[a.back()]){
      if(f[a[0]]==a.back())a[0]=a.back();
      a.pop_back();
    }
    map<int,int> m; for(int i:a)m[i]++;
    cout<<(m[2]>m[0]&&m[1]>m[3]?"Yes\n":"No\n");
  }
  return 0;
}