题解 CF1025D 【Recovering BST】
ezoixx130
2018-12-22 22:15:44
看来大家写的都是正解啊。。
只有我一个场上写了时间和空间复杂度都不对然而过掉的乱搞的吗???
我的做法是这样的:设计一个check(l,r,root)表示当前子树的根为root时,是否能用l~r之间的数构造出一个满足题意的子树。
实现很简单,就是暴力枚举l~r之间那一个数作儿子,再递归判断即可。
然而这样太暴力了,随随便便都能卡到TLE。
但是我们发现,实际上我们在搜索的过程中有大量重复搜索的地方,于是我们加上一个记忆化。
然后我们发现开700的三维数组会MLE。
由于这个数组只用存储bool值,那我们就把它开成bitset。
接着这个做法就过了。
代码:
```
#include<bits/stdc++.h>
using namespace std;
int n,a[701];
bitset<701> vis2[701][701],ans[701][701];
bool ok[701][701];
int check(int l,int r,int root)
{
if(r<l)return true;
if(l==r)return ok[l][root];
if(vis2[l][r][root])return ans[l][r][root];
for(int i=l;i<=r;++i)
if(ok[i][root] &&check(l,i-1,i) && check(i+1,r,i))
{
vis2[l][r][root]=1;
ans[l][r][root]=1;
return true;
}
vis2[l][r][root]=2;
return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",a+i);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
ok[i][j]=__gcd(a[i],a[j])!=1;
ok[0][i]=true;
ok[i][0]=true;
}
if(check(1,n,0))puts("Yes");else puts("No");
}
```