这道编程题用C++怎么做?

现在有一款小游戏叫做“猜数游戏”。这个游戏的目的是从一个迷宫中找到一个出口。这个迷宫的形状是一棵高度为h的完全二叉树。玩家刚开始站在根部,出口是在某一个叶子结点上面。
现在我们来定义每一个结点的编号:
· 根部是1
· 某个内部结点的编号为 i (i ≤ 2h−1−1) 时,他的左儿子编号为2i,右儿子编号为2i+1。
根的深度定为1,其它结点的深度是他的父亲的深度+1。深度为h的结点是叶子。出口在某个叶子结点上,但是游戏玩家并不知道在哪个叶子,所以他现在要开始猜。
玩家每次会问ancestor(exit, i)属于[L,R]吗?这儿 ancestor(v, i) 表示结点v在第i层的那个祖先。然后游戏会给出"Yes"或"No"的回答。这个游戏的回答也不一定是完全合法的。有一些时候他会骗玩家。
现在有一些询问和回答,要求你从中判断一下,这个游戏有没有在说谎。如果游戏没有说谎,并且出口被推断出来,那么请输出出口,如果游戏没有说谎,但是出口不能被唯一判定出来,请输出“Data not sufficient!”。否则输出“Game cheated!”
结点u是结点v的祖先,当且仅当满足以下条件之一:
· u和v一样,
· u 是 v的父亲,
· u 是v的父亲的祖先。

样例解释:在这个例子中有 8个叶子结点。经过第一个询问之后,出口被确定在 [10, 14]区间内。经过第二个和第三个询问,只有14号符合条件。请结合图例进行理解。

Input
单组测试数据。
第一行有两个整数h, q (1 ≤ h ≤ 50, 1 ≤ q ≤ 10^5),表示树的高度和询问的数量。
接下来q行,每行包含 i, L, R, ans (1 ≤ i ≤ h, 2^(i - 1) ≤ L ≤ R ≤ 2^i - 1, ans∈{0,1}),表示询问出口在第i层的祖先属于L,R吗?ans=1表示YES,否则表示NO。
Output
如果游戏给出的信息是自相矛盾的,那么输出 Game cheated!。
如果可以唯一确定出口。那么输出出口的编号。
否则输出Data not sufficient!。
Input示例
4 3
4 10 14 1
3 6 6 0
2 3 3 1
Output示例
14

2个回答

思路:

1、对于每一个询问的区间【L,R】,因为知道区间所在的层数,所以可以求出最下面一层的区间【L',R'】。比如在第x层的区间【L,R】
,那么在第x+1层的区间就为【L*2,R*2+1].

2、先求出所有询问的最下面一层的区间。

3、然后对这些区间按L从小到大排序。

4、遍历这些区间,维护ans=1/0的区间,如果存在ans=1的区间包含在ans=0的区间,则是矛盾的,反过来可以把ans=1的区间划分为三部分,
前面一部分区间不用考虑了,只需要维护最后面一部分区间就行,因为前面部分的区间已经可以确定了。

5、最后在判断一下ans=1的区间是不是多余1个就行了。

思路:

1、对于每一个询问的区间【L,R】,因为知道区间所在的层数,所以可以求出最下面一层的区间【L',R'】。比如在第x层的区间【L,R】
,那么在第x+1层的区间就为【L*2,R*2+1].

2、先求出所有询问的最下面一层的区间。

3、然后对这些区间按L从小到大排序。

4、遍历这些区间,维护ans=1/0的区间,如果存在ans=1的区间包含在ans=0的区间,则是矛盾的,反过来可以把ans=1的区间划分为三部分,
前面一部分区间不用考虑了,只需要维护最后面一部分区间就行,因为前面部分的区间已经可以确定了。

5、最后在判断一下ans=1的区间是不是多余1个就行了。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问