题面

给出一些数，若要求两数\(gcd>1\)才能连边，询问他们是否能构成一棵二叉搜索树。

• \(n\leq700\)

  解析

  如果没注意到二叉搜索树这一条件，这题绝对做不出来。。。

二叉搜索树的定义是，对同一节点，左儿子权值比它小，右儿子权值比它大。

于是有一个很重要的性质，中序遍历上点权从小到大。

可以得出推论：

• 一棵子树（在中序遍历上可视为一段区间\([l,r]\)），把它作为左儿子，根结点的父亲一定为\(r+1\)；把它作为右儿子，根节点父亲一定为\(l-1\)。

然而注意到，如果暴力设\(f[i][j][k][0/1]\)表示以\(k\)为根，\([i,j]\)作为其左/右儿子是否合法是会\(MLE\)，而且有许多无效状态。

于是需应用上面推论，设两个判合法性的数组：

• \(L[i][j]\)表示区间\([i,j-1]\)作为\(j\)的左儿子是否合法
• \(R[i][j]\)表示区间\([i+1,j]\)作为\(j\)的右儿子是否合法

转移：

设\(k\)为区间\([i,j]\)的根，

如果\(L[i][k]=1\)且\(r[k][j]=1\)，则该状态合法，可以转移；

没地方转移了就\(puts("Yes")\)。

如果\(k\)可以与\(l-1\)相连，说明以\(l-1\)为根，\([l,r]\)为右儿子的状态合法。

如果\(k\)可以与\(r+1\)相连，说明以\(r+1\)为根，\([l,r]\)为左儿子的状态合法。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define re register#define il inline#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;il ll gi(){ re ll x=0,p=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') p=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return p*x;}const int N=710;int n,a[N],f[N][N],L[N][N],R[N][N];int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>a[i],L[i][i]=R[i][i]=1; fp(i,1,n) fp(j,i,n) if(__gcd(a[i],a[j])>1) f[i][j]=f[j][i]=1; fq(l,n,1) fp(r,l,n) fp(k,l,r) if(L[l][k]&&R[k][r]) { if(l==1&&r==n) {puts("Yes");return 0;} if(f[l-1][k]) R[l-1][r]=1; if(f[k][r+1]) L[l][r+1]=1; } puts("No"); return 0;}