L2-012 关于堆的判断

叁歲伎倆 2022-03-15 15:40 153阅读 0赞

L2-012 关于堆的判断 （25 分）

将一系列给定数字顺序插入一个初始为空的小顶堆`H[]`。随后判断一系列相关命题是否为真。命题分下列几种：

*  `x is the root`：`x`是根结点；
 *  `x and y are siblings`：`x`和`y`是兄弟结点；
 *  `x is the parent of y`：`x`是`y`的父结点；
 *  `x is a child of y`：`x`是`y`的一个子结点。

### 输入格式： ###

每组测试第1行包含2个正整数`N`（≤ 1000）和`M`（≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间\[−10000,10000\]内的`N`个要被插入一个初始为空的小顶堆的整数。之后`M`行，每行给出一个命题。题目保证命题中的结点键值都是存在的。

### 输出格式： ###

对输入的每个命题，如果其为真，则在一行中输出`T`，否则输出`F`。

### 输入样例： ###

5 4
    46 23 26 24 10
    24 is the root
    26 and 23 are siblings
    46 is the parent of 23
    23 is a child of 10

### 输出样例： ###

F
    T
    F
    T

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int v[2005];
    int main()
    {
    	memset(v,0x3f,sizeof v);
    	int n,m,i,j,p; 
    	scanf("%d%d",&n,&m);
    	for(i=1;i<=n;i++)
    	scanf("%d",&v[i]);
    	for(i=2;i<=n;i++)
    	{//建堆 
    		int j=i;
    		while(j>1)
    		{
    			if(v[j]<v[j/2])swap(v[j],v[j/2]);
    			j=j/2;
    		}
    	}
    	//for(i=1;i<=n;i++) printf("%d ",v[i]);
    	while(m--)
    	{
    		int a,b,f=0,x,y;
    		char c[150];
    		scanf("%d",&a);
    		scanf("%s",c);
    		if(c[0]=='a')
    		{//a and b are siblings
    			scanf("%d",&b);
    			scanf("%s",c);
    			scanf("%s",c);
    			for(i=1;i<=n;i++)
    			{
    				if(v[i]==a)
    				x=i;
    				if(v[i]==b)
    				y=i;
    			}
    			if(x!=y&&x/2==y/2)f=0;
    			else f=1;
    		}
    		else
    		{
    			scanf("%s",c);
    			if(c[0]=='a')
    			{//a is a child of b
    				scanf("%s",c);
    				scanf("%s",c);
    				scanf("%d",&b);
    				for(i=1;i<=n;i++)
    				{
    					if(v[i]==a)
    					x=i;
    					if(v[i]==b)
    					y=i;
    				}
    				if(x!=y&&(y*2==x||y*2+1==x)) f=0;
    				else f=1;
    			}
    			else
    			{
    				scanf("%s",c);
    				if(c[0]=='r')
    				{//a is the root
    					if(v[1]==a) f=0;
    					else f=1;
    				}
    				else
    				{//a is the parent of b
    					scanf("%s",c);
    					scanf("%d",&b);
    					for(i=1;i<=n;i++)
    					{
    						if(v[i]==a)
    						x=i;
    						if(v[i]==b)
    						y=i;
    					}
    					if(x!=y&&(x*2==y||x*2+1==y)) f=0;
    					else f=1;
    				}
    			}
    		}
    		if(f)printf("F\n");
    		else printf("T\n");
    	}
    }