团体程序设计天梯赛-练习集 - L2-012 关于堆的判断(25 分)

简介: 团体程序设计天梯赛-练习集 - L2-012 关于堆的判断(25 分)

题目链接:点击打开链接

题目大意:略。

解题思路:此题为边插入边建堆,而不是先按层序遍历建好树再调整成堆;注意兄弟结点的判断条件(小偶大奇且(奇 - 偶==1))。


AC 代码

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
intn, res, a[1009];
voidfind_heap(intrt, intd)
{
if(rt>n||rt<=0) return;
if(a[rt]==d){res=rt; return;}
if(a[rt]<d) find_heap(rt*2,d);
if(a[rt]<d) find_heap(rt*2+1,d);
}
intmain()
{
intm,n1,n2,rt;
scanf("%d%d",&n,&m);
for(inti=1;i<=n;i++)
    {
scanf("%d",&a[i]);
make_heap(a+1,a+1+i,greater<int>());
    }
rt=a[1];
getchar();
strings;
while(m--)
    {
getline(cin,s);
intf=0, id1, id2;
if(sscanf(s.c_str(),"%d and %d are siblings",&n1,&n2)==2)
        {
res=0; find_heap(1,n1); id1=res;
res=0; find_heap(1,n2); id2=res;
if(id1>id2) swap(id1,id2);
if(id1%2==0&&id2%2==1&&id2-id1==1) f=1;
        }
elseif(sscanf(s.c_str(),"%d is the parent of %d",&n1,&n2)==2)
        {
res=0; find_heap(1,n1); id1=res;
res=0; find_heap(1,n2); id2=res;
if(id1*2==id2||id1*2+1==id2) f=1;
        }
elseif(sscanf(s.c_str(),"%d is a child of %d",&n1,&n2)==2)
        {
res=0; find_heap(1,n1); id1=res;
res=0; find_heap(1,n2); id2=res;
if(id2*2==id1||id2*2+1==id1) f=1;
        }
elseif(sscanf(s.c_str(),"%d is the root",&n1)==1)
        {
if(n1==rt) f=1;
        }
puts(f?"T":"F");
    }
return0;
}
目录
相关文章
团体程序设计天梯赛-练习集L2篇⑦
团体程序设计天梯赛-练习集L2篇⑦
74 0
|
Perl
团体程序设计天梯赛-练习集L1篇③
团体程序设计天梯赛-练习集L1篇③
131 0
|
测试技术
团体程序设计天梯赛-练习集L2篇⑥
团体程序设计天梯赛-练习集L2篇⑥
110 0
|
C语言 C++
PTA团体程序设计天梯赛-练习集: L1-050 倒数第N个字符串 ( 15分 )
给定一个完全由小写英文字母组成的字符串等差递增序列,该序列中的每个字符串的长度固定为 L,从 L 个 a 开始,以 1 为步长递增。例如当 L 为 3 时,序列为 { aaa, aab, aac, ..., aaz, aba, abb, ..., abz, ..., zzz }。这个序列的倒数第27个字符串就是 zyz。对于任意给定的 L,本题要求你给出对应序列倒数第 N 个字符串。 输入格式: 输入在一行中给出两个正整数 L(2 ≤ L ≤ 6)和 N(≤105)。 输出格式: 在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。 输入样例:
167 0
|
测试技术 C语言 C++
PTA团体程序设计天梯赛-练习集:L1-003 个位数统计
给定一个 k 位整数 N=dk−110k−1+⋯+d1101+d0 (0≤di≤9, i=0,⋯,k−1, dk−1>0),请编写程序统计每种不同的个位数字出现的次数。例如:给定 N=100311,则有 2 个 0,3 个 1,和 1 个 3。 输入格式: 每个输入包含 1 个测试用例,即一个不超过 1000 位的正整数 N。 输出格式: 对 N 中每一种不同的个位数字,以 D:M 的格式在一行中输出该位数字 D 及其在 N 中出现的次数 M。要求按 D 的升序输出。
201 0
【CCCC】PAT : 团体程序设计天梯赛-练习集 L3 答案(01-23)
【CCCC】PAT : 团体程序设计天梯赛-练习集 L3 答案(01-23)
122 0
|
人工智能
【CCCC】PAT : 团体程序设计天梯赛-练习集 L1 答案
【CCCC】PAT : 团体程序设计天梯赛-练习集 L1 答案
384 0
团体程序设计天梯赛-练习集 - L3-016 二叉搜索树的结构 (30 分)
团体程序设计天梯赛-练习集 - L3-016 二叉搜索树的结构 (30 分)
91 0
团体程序设计天梯赛-练习集 - L3-016 二叉搜索树的结构 (30 分)
团体程序设计天梯赛-练习集 - L2-002 链表去重(25 分)
团体程序设计天梯赛-练习集 - L2-002 链表去重(25 分)
118 0
团体程序设计天梯赛-练习集 - L3-008 喊山(30 分)
团体程序设计天梯赛-练习集 - L3-008 喊山(30 分)
121 0