题解 CF1025D Recovering BST

题解 CF1025D Recovering BST

题面

luogu

解析

考虑到 BST 的性质,将 $a$ 排序后区间 $[l,r]$ 是子树中连续的一段.

设 $L_{i,j}$ 表示 区间 $[i,j]$ 能否形成以 $j$ 为根,$[i,j-1]$ 为左子树的 BST,

$R_{i,j}$ 表示区间 $[i,j]$ 能否形成以 $i$ 为根,$[i+1,j]$ 为右子树的 BST.

假设当前枚举到 $[l,r]$,考虑更新 $L_{l,r}$.

在 $[l,r-1]$ 中枚举根节点 $p$,满足 $p$ 可以为这一段区间的根,即 $L_{l,p}=1,R_{p,r-1}=1$.

然后看 $p$ 能否成为 $r$ 的左子树,如果能则 $L_{l,r}=1$.

更新 $R_{l,r}$ 同理.

最后枚举所有节点 $i$,看它能否成为整棵树的根节点,即 $L_{1,i}=1,R_{i,n}=1$.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}
return f*sum;
}

const int N=705;
int n,a[N],L[N][N],R[N][N],f[N][N];

inline int gcd(int x,int y){
return y==0? x:gcd(y,x%y);
}

signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) f[i][j]=gcd(a[i],a[j])>1;
for(int i=1;i<=n;i++) L[i][i]=R[i][i]=1;
for(int i=1;i<=n;i++){
for(int l=1;l<=n-i;l++){
int r=l+i;
for(int j=l+1;j<=r;j++){
if(!f[l][j]) continue;
if(!L[l+1][j]||!R[j][r]) continue;
R[l][r]=1;
}
for(int j=l;j<r;j++){
if(!f[r][j]) continue;
if(!L[l][j]||!R[j][r-1]) continue;
L[l][r]=1;
}
}
}
for(int i=1;i<=n;i++){
if(L[1][i]&&R[i][n]){puts("Yes");return 0;}
}
puts("No");
return 0;
}
感谢您又打赏