宇宙狗的危机

时间限制	空间限制
5s	256MB

题目描述

在瑞神大战宇宙射线中我们了解到了宇宙狗的厉害之处，虽然宇宙狗凶神恶煞,但是宇宙狗有一个很可爱的女朋友。

最近，他的女朋友得到了一些数,同时，她还很喜欢树，所以她打算把得到的数拼成一颗树。

这一天,她快拼完了，同时她和好友相约假期出去玩。贪吃的宇宙狗不小心把树的树枝都吃掉了。所以恐惧包围了宇宙狗，他现在要恢复整棵树，但是它只知道这棵树是一颗二叉搜索树，同时任意树边相连的两个节点的gcd(greatest common divisor)都超过1。

但是宇宙狗只会发射宇宙射线，他来请求你的帮助，问你能否帮他解决这个问题。

补充知识:

GCD:最大公约数,两个或多个整数共有约数中最大的一一个，例如8和6的最大公约数是2。

一个简短的用辗转相除法求gcd的例子:

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

输入描述

输入第一行一个t,表示数据组数。

对于每组数据,第一行输入一个n, 表示数的个数

接下来一行有n个数

a_ i

, 输入保证是升序的。

输出描述

每组数据输出一行, 如果能够造出来满足题目描述的树，输出Yes, 否则输出No。

无行末空格

样例输入1

163 6 9 18 36 108

样例输出1

Yes

样例输入2

227 1794 8 10 12 15 18 33 44 81

样例输出2

No
Yes

样例解释

样例1可以构造为如下图的树

数据组成

数据点数	t	n	$a_i$
1,2,3	5	15	$10^9$
4,5,6	5	35	$10^9$
7,8,9,10	5	700	$10^9$

解释

这是一道dp题，而需要构造的正是一棵二叉搜索树。二叉搜索树的特性是若它的左子树不为空，那么左子树上所有的节点均小于根节点值，反之，其右子树上所有节点值大于根节点值。
那么利用二叉搜索树的这个特性，我们进行dp构造，它的条件就是
if(gc[j-1][k]==1) rt[j-1][len]=1;
if(gc[k][len+1]==1) lt[j][len+1]=1;
也就是说相当于通过dp将节点插入这棵树中。

Codes

#include
   
    #include
    
     using namespace std;int t,n,e[720],gc[720][720],rt[720][720],lt[720][720];int gcd(int a,int b){
   return b==0 ? a : gcd(b,a%b);}//求公约数void ini(){
   	memset(gc,0,sizeof(gc));	memset(rt,0,sizeof(rt));	memset(lt,0,sizeof(lt));	for(int i=1;i<=n;i++){
   		for(int j=1;j<=n;j++)			if(i!=j && gcd(e[i],e[j])>1)				gc[i][j]=1;//gc用来记录两个公约数大于1的节点关系		rt[i][i]=lt[i][i]=1;	}}bool f(){
   //dp过程	for(int i=0;i
     
      >t;	while(t--){
   		cin>>n;		for(int i=1;i<=n;i++)			cin>>e[i];		ini();		if(f()) cout<<"Yes"<

转载地址：http://ccwzi.baihongyu.com/

你可能感兴趣的文章