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

Description:

将一系列给定数字顺序插入一个初始为空的小顶堆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的一个子结点。

Input:

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

Output:

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

Sample Input:

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

Sample Output:

F
T
F
T

题目链接

根据题意通过数组及其下标关系建立二叉树，并在添加新数时不断维护二叉树，建立好二叉树后便可以根据输入命题进行判断，这里命题提取和判断有一些麻烦。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
const double eps = 1e-5;
const double e = 2.718281828459;

int n, m, num;
int cnt = 0;
// 二叉树数组
int tree[maxn];

// 判断插入数字和父节点的大小关系
void Judge_change_tree(int self) {
    // 若搜索到根节点则返回
    if (self == 1) {
        return;
    }
    // 若根节点下标为0：设节点下标为n，此节点左孩子下标为2*n+1,右孩子下标为2*n+2
    // 若根节点下标为1：设节点下标为n，此节点左孩子下标为2*n,右孩子下标为2*n+1
    // 此处逆推寻找父节点的数组下标
    int parent;
    if (self % 2) {
        parent = (self - 1) >> 1;
    }
    else {
        parent = self >> 1;
    }
    // 若父节点大则交换并继续递归向根节点方向判断替换
    if (tree[self] < tree[parent]) {
        int temp = tree[self];
        tree[self] = tree[parent];
        tree[parent] = temp;
        Judge_change_tree(parent);
    }
}

void Build_tree() {
    // 将新插入的数放到最后
    tree[++cnt] = num;
    // 判断插入的数和父节点的大小关系并调整二叉树
    Judge_change_tree(cnt);
}

void Judge_Output(string be_judge_str) {
    int len = be_judge_str.length();
    int x = 0, y = 0;
    // 设置bool变量判断是否为负数
    bool x_pm_flag = 0, y_pm_flag= 0;
    // 字符串中第一个数为x，第二个数为y
    bool number_changr_flag= 1;
    string x_str, y_str;
    for (int i = 0; i < len; ++i) {
        // 若为数字则判断是x还是y并相应改变x和y的值
        if (be_judge_str[i] >= '0' && be_judge_str[i] <= '9') {
            if (number_changr_flag) {
                // 判断x是否为负数
                if (i != 0 && be_judge_str[i - 1] == '-') {
                    x_pm_flag = 1;
                }
                x = x * 10 + be_judge_str[i] - '0';
                x_str += be_judge_str[i];
            }
            else {
                // 判断y是否为负数
                if (i != 0 && be_judge_str[i - 1] == '-') {
                    y_pm_flag = 1;
                }
                y = y * 10 + be_judge_str[i] - '0';
                y_str += be_judge_str[i];
            }
        }
        else {
            // 若不是数字且不是第一个x数的负号则改变相应的bool变量使下次循环到数字时添加y值
            if (i != 0) {
                number_changr_flag = 0;
            }
        }
    }
    // 若x为负数则改变x为相反数
    if (x_pm_flag) {
        x = -x;
        string x_pm_temp;
        x_pm_temp = '-';
        x_pm_temp += x_str;
        x_str = x_pm_temp;
    }
    // 若y为负数则改变x为相反数
    if (y_pm_flag) {
        y = -y;
        string y_pm_temp;
        y_pm_temp = '-';
        y_pm_temp += y_str;
        y_str = y_pm_temp;
    }
    // 第一种命题
    if (be_judge_str == (x_str + " is the root")) {
        // 若根节点和x值相等则正确
        if (x == tree[1]) {
            cout << "T" << endl;
        }
        else {
            cout << "F" << endl;
        }
    }
    // 第二种命题
    else if (be_judge_str == (x_str + " and " + y_str + " are siblings")) {
        bool brother_flag = 0;
        for (int i = 2; i <= n; i += 2) {
            // 若存在x为偶数且tree[x]和tree[x+1]一个等于x一个等于y则命题正确，x、y为兄弟节点，改变相应的bool判断变量
            if (tree[i] == x && tree[i + 1] == y) {
                brother_flag = 1;
                break;
            }
            if (tree[i] == y && tree[i + 1] == x) {
                brother_flag = 1;
                break;
            }
        }
        if (brother_flag) {
            cout << "T" << endl;
        }
        else {
            cout << "F" << endl;
        }
    }
    // 第三种命题
    else if (be_judge_str == (x_str + " is the parent of " + y_str)) {
        bool father_flag = 0;
        for (int i = 1; i <= n; ++i) {
            // 若存在i等于x且tree[i]两个孩子有一个等于y则命题正确，改变相应的bool判断变量
            if (tree[i] == x && (tree[i * 2] == y || tree[i * 2 + 1] == y)) {
                father_flag = 1; 
                break;
            }
        }
        if (father_flag) {
            cout << "T" << endl;
        }
        else {
            cout << "F" << endl;
        }
    }
    // 第四种命题
    else {
        // 与第三种命题正好相反，交换变量即可
        bool son_flag = 0;
        for (int i = 1; i <= n; ++i) {
            if (tree[i] == y && (tree[i * 2] == x || tree[i * 2 + 1] == x)) {
                son_flag = 1;
                break;
            }
        }
        if (son_flag) {
            cout << "T" << endl;
        }
        else {
            cout << "F" << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // 初始化二叉树数组为数据范围外的“正无穷”
    mem(tree, INF);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        // 输入数并添加到二叉树数组
        cin >> num;
        Build_tree();
    }
    cin.get();
    while (m--) {
        string ask_str;
        // 获取一行命题询问信息
        getline(cin, ask_str);
        // 判断命题是否正确并进行相应输出
        Judge_Output(ask_str);
    }
    return 0;
}