WEEK16 csp模拟 宇宙狗的危机

题解

测试时，想当然的觉得很难，就没想好方法，就想着骗骗分了。检测了几个成树的必要条件然后判断Yes或No，竟然有60分。
没用什么算法，暴力加剪枝也能做出来。bool型二维数组visr记录是否已经计算过i-j能否作为i-1的右子树，bool型二维数组ansr记录i-j能否作为i-1的右子树，bool型二维数组visl记录是否已经计算过i-j能否作为j+1的左子树，bool型二维数组ansr记录i-j能否作为j+1的左子树，int型二维数组记录每两对树的最大公因数。
先相互两两求最大公因数，计算完gcd_ans数组，再循环检查第i个数能否作为1~n的根。若有一个数可做1_n的根，则输出Yes，否则输出No。
检查从l到r构造以now为根的二叉树是否可行，这步要经常用到，变成一个函数。这是一个递归函数。若l=r=now说明没有左右子树了，只有自己，可以成树，返回true。否则分别检查l_now-1能否作为now的左子树和now+1_r能否作为now的右子树（先检查visl和visr数组，已经检查过则直接调用ansl和ansr的结果）。以左子树为例，若左子树为空（l==now-1）则now的左孩子也能成树，不为空则遍历l到now-1，循环检查第i个数能否作为l~now-1的根,先检查i与now的最大公因数，再检查以i为根从l到now-1能否构造二叉树即调用本函数，参数为(l,i,now-1)。每次检查完后都将结果记录进visl、visr、ansl、ansr，以便下次调用。

代码

#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;

int a[710];
int gcd_ans[710][710];
bool visl[710][710];    //是否计算过i-j能否作为j+1的左子树
bool visr[710][710];    //是否计算过i-j能否作为i-1的右子树
bool ansl[710][710];    //记录i-j能否作为j+1的左子树
bool ansr[710][710]; //记录i-j能否作为i-1的右子树

int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } 

bool tree(int l,int now,int r){   
	if(l>=now&&r<=now){
		return true;
	}
	if(!visl[l][now-1]){ 
		bool suc=0;
		if(l==now){suc=1;}  
		for(int i=l;i<now;i++){
			if(gcd_ans[i][now]>1){
				if(tree(l,i,now-1)){suc=true;break;} 
			}
		}   
		visl[l][now-1]=true;
		ansl[l][now-1]=suc;
	}
	if(!visr[now+1][r]){  
		bool suc=0;
		if(now==r){suc=1;} 
		for(int i=r;i>now;i--){
			if(gcd_ans[now][i]>1){
				if(tree(now+1,i,r)){suc=1;} 
			}
		}   
		visr[now+1][r]=true;
		ansr[now+1][r]=suc;
	}
	return (ansl[l][now-1]&&ansr[now+1][r]);  
}

int main(){
	int t;scanf("%d",&t);
	while(t--){
		memset(visl,0,sizeof(visl));
		memset(visr,0,sizeof(visr));
		memset(ansl,0,sizeof(ansl));
		memset(ansr,0,sizeof(ansr));
		int n;scanf("%d",&n);
		for(int j=1;j<=n;j++){
			scanf("%d",&a[j]);
		}
		for(int j=1;j<=n;j++){
			for(int k=j;k<=n;k++){
				gcd_ans[j][k]=gcd_ans[k][j]=gcd(a[j],a[k]);
			}
		}
		
		bool suc=0;
		for (int j=1;j<=n;j++){
			if(tree(1,j,n)){
				suc=1;break;
			}
		}
		if (suc==1){cout<<"Yes\n";}
		else{cout<<"No\n";}
	}
	return 0;
}