团体程序设计天梯赛-练习集 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;
}