题解 CF1025D 【Recovering BST】

ezoixx130

2018-12-22 22:15:44

Solution

看来大家写的都是正解啊。。 只有我一个场上写了时间和空间复杂度都不对然而过掉的乱搞的吗??? 我的做法是这样的:设计一个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"); } ```