【CF1025D】Recovering BST

Source and Judge

CF1025D

Record

1h

Analysis

请先思考后再展开

这道题出得灰常好
再次%一发rose大爷
首先,所谓BST就是吓唬人的
联想一下splay,其中序遍历不变
这道题同样如此
甚至都帮你排好序了
然后就不知道怎么解决了……

其实可以继续在中序遍历中做文章
因为这是一个一维的序列
然后在一颗子树中,其实是连续的一段(完全忘记的我……)

考虑一下区间dp
然后有个小性质:我的父亲一定在当前区间的旁边,毕竟当初就是这样分开的
而且,这棵树的根节点是可以随便取的

具体实现的话,枚举出当前子树的根节点x,与rt判断是否合法,然后向下
用记忆化会灰常方便
设f(l,r,op)表示可行性,然后op表示rt在那一侧就好了

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}
int a[710];
bool f[710][710][2];
bool v[710][710][2];
bool dp(int l,int r,int op)
{
if(l>r) return 1;
if(v[l][r][op]) return f[l][r][op];
v[l][r][op]=1;
int rt=op?r+1:l-1;
for(int x=l;x<=r;x++)
if(gcd(a[x],a[rt])!=1 and dp(l,x-1,1) and dp(x+1,r,0))
return f[l][r][op]=1;
return f[l][r][op]=0;
}
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(dp(2,n,0)) puts("Yes");
else puts("No");
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/7565.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%