L2-012 关于堆的判断（模拟堆+字符串处理）

视频讲解

https://www.bilibili.com/video/BV1W3411M72Z/

题目链接

https://pintia.cn/problem-sets/994805046380707840/problems/994805064676261888

思路

我们首先通过模拟实现堆（这里只需要实现堆的插入即可），然后对于四种情况：

• x是根结点，我们只需要判断堆中第一个元素是否为x即可
• x是y的父结点，我们只需要判断 y > > 1 y>>1 y>>1 是否等于 x x x 因为根节点是从1开始的，下面同理
• x是y的一个子结点，我们只需要判断 x > > 1 x>>1 x>>1 是否等于 y y y
• x和y是兄弟结点，我们只需要判断 ( x > > 1 ) = = ( y > > 1 ) (x>>1) == (y>>1) (x>>1)==(y>>1)

注意这里非常有可能想多了，比如子节点是否算孙子节点（这里是不算的），兄弟节点是否算异父兄兄弟（这里也是不算的），然后就写错了，更多详情请看代码

代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair

const int N = 2e6+10;
int n,m,cnt,h[N],hp[N],ph[N];
int k,x;

void heap_swap(int a,int b){//a、b都是下标
	swap(h[a],h[b]);
}
void up(int u) {//向上更新
	while((u>>1) && h[u] >1]) {
		heap_swap(u,u >> 1);
		u >>= 1;
	}
}
void insert(int k){
	cnt++;
	h[cnt] = k;
	up(cnt);
}

map st;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string op;
	cin>>n>>m;
	
	for(int i = 1;i >k;
		insert(k);
	} 
	for(int i = 1;i >x>>op;
		bool ans;
		if(op == "is"){
			cin>>op;
			if(op == "the") {
				cin>>op;
				if(op == "root") {//x是根结点
					if(h[1] == x) ans = true;
					else ans = false;
				} else {//x是y的父结点
					cin>>op>>y;
					x = st[x],y = st[y];
					if(x >1 == x)) ans = true;
					else ans = false;
				}
			} else {//x是y的一个子结点
				cin>>op>>op>>y;
				x = st[x],y = st[y];
				if(x > y && (x>>1 == y)) ans = true;
				else ans = false;
			}
		} else {//x和y是兄弟结点
			cin>>y;
			getline(cin,op);
			x = st[x],y = st[y];
			if((x>>1) == (y>>1)) ans = true;
			else ans = false;
		}
		if(ans) cout