题解 CF1025D 【Recovering BST】

· · 题解

看来大家写的都是正解啊。。

只有我一个场上写了时间和空间复杂度都不对然而过掉的乱搞的吗？？？

我的做法是这样的：设计一个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");
}