在线测试传送门:PAT(甲级)2021年春仿真卷

7-3 Structure of Max-Heap (25 分)
In computer science, a max-heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree.

Your job is to first insert a given sequence of integers into an initially empty max-heap, then to judge if a given description of the resulting heap structure is correct or not. There are 5 different kinds of description statements:

x is the root
x and y are siblings
x is the parent of y
x is the left child of y
x is the right child of y

Input Specification:
Each input file contains one test case. For each case, the first line gives 2 positive integers: N (≤1,000), the number of keys to be inserted, and M (≤20), the number of statements to be judged. Then the next line contains N distinct integer keys in [-10^​4^,10^4^​​] which are supposed to be inserted into an initially empty max-heap. Finally there are M lines of statements, each occupies a line.

Output Specification:
For each statement, print 1 if it is true, or 0 if not. All the answers must be print in one line, without any space.

Sample Input:

5 6
23 46 26 35 88
35 is the root
46 and 26 are siblings
88 is the parent of 46
35 is the left child of 26
35 is the right child of 46
-1 is the root

Sample Output:

011010

题意

由一个长度为$n$的序列建最大堆,接下来有$m$次询问,以特定字符串格式给出,包括5种询问:根、兄弟(siblings)节点、父节点、左孩子、右孩子。

思路

堆如何建立,点击此篇文章,本文不赘述。

这题比较麻烦的是字符串的处理,我们需要从中提取出一个或两个数字,怎么写比较简便呢?我们以询问siblings为例。(假设之前已定义string s;
1. s.find("siblings")!=s.npos,这句话表示字符串中能找到"siblings"子串,可作为将询问进行分类的依据。find函数能找string的子串,返回子串的起始位置,若找不到则返回string::npos(即s.npos)。
2. sscanf(s.c_str(),"%d and %d are siblings",&x,&y);,这句话能格式化提取出字符串$s$中两个对应位置的数字。

sscanf的作用:从一个字符串中读进于指定格式相符的数据。利用它可以从字符串中取出整数、浮点数和字符串。
sscanf和scanf的区别:scanf是以键盘作为输入源,sscanf是以字符串作为输入源。

最后就是一些小细节了。
比如要注意判断两个节点为兄弟是它们有相同父节点;节点的值可为负数所以要用map映射。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n,m,a[N];
unordered_map<int,int>pos;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) // 建最大堆
    {
        cin>>a[i];
        // 只要比父节点大,就一直与父节点交换,往上跳,直到根或不大于父亲为止
        for(int j=i;j>1&&a[j]>a[j/2];j/=2) // 向上跳到父节点j/2
            swap(a[j],a[j/2]);
    }
    for(int i=1;i<=n;i++)
        pos[a[i]]=i; // 记录每个值对应的下标(a[i]可能为负数,用map映射)
    string ans,s;
    cin.get(); // 清除缓冲区残留的一个换行符,效果同getchar(),但是getchar可能出错
    while(m--)
    {
        getline(cin,s);
        int x,y;
        if(s.find("root")!=s.npos) // 字符串有"root"
        {
            sscanf(s.c_str(),"%d is the root",&x);
            if(pos[x]==1)ans+="1";
            else ans+="0";
        }
        else if(s.find("siblings")!=s.npos) // 字符串有"siblings"
        {
            sscanf(s.c_str(),"%d and %d are siblings",&x,&y);
            if(pos[x]/2==pos[y]/2)ans+="1";
            else ans+="0";
        }
        else if(s.find("parent")!=s.npos) // 字符串有"parent"
        {
            sscanf(s.c_str(),"%d is the parent of %d",&x,&y);
            if(pos[x]==pos[y]/2)ans+="1";
            else ans+="0";
        }
        else if(s.find("left")!=s.npos) // 字符串有"left"
        {
            sscanf(s.c_str(),"%d is the left child of %d",&x,&y);
            if(pos[x]==pos[y]*2)ans+="1";
            else ans+="0";
        }
        else if(s.find("right")!=s.npos) // 字符串有"right"
        {
            sscanf(s.c_str(),"%d is the right child of %d",&x,&y);
            if(pos[x]==pos[y]*2+1)ans+="1";
            else ans+="0";
        }
    }
    printf("%s\n",ans.c_str());
    return 0;
}

后记

考试的时候判断兄弟节点的条件写错了,而且字符串判断写的也极其复杂,丢了一个测试点,7分啊QAQ;

现在学会了两个好东西,find和sscanf,以后多用用!