Easy Tree Query
时间限制: 3 Sec
内存限制: 128 MB
提交: 130
解决: 15
[
提交][
状态][
讨论版]
题目描述
You are given a binary search tree with depth k, whose nodes are valued from 1 to (2k − 1) and then Q queries.
For each query, you are given p nodes. Find the root of a smallest subtree which contains all p nodes and print its
value.
输入
The first line of input contains an integer T (T ≤ 100), the number of test cases. The first line of each test case
contains two integers k (1 ≤ k ≤ 60) and Q (1 ≤ Q ≤ 10 4 ). In next Q lines, each line contains an integer p and then
p integers — the values of nodes in this query. It is guaranteed that the total number of nodes given in each test
case will not exceed 105
.
输出
For each query, print a line contains the answer of that query.
样例输入
1
4 1
3 10 15 13
样例输出
12
提示
也算是个规律题，不过需要把这个树先写出来，然后找出最大值和最小值，从根节点开始遍历就好了，先画个图。。。
开始都没注意到二叉搜索树，然后wyp也是浪了一波，以为题目出错了，然后开始敲，样例都不过，谁给他的勇气！！！狂的一PI
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL INF = 0x7f3f3f3f3f3f3f3f;
int main(){
int T,len,Q,n;
LL tmp,mmax,mmin,root;
scanf("%d", &T );
while(T--) {
scanf("%d%d", &n ,&Q);
for(int i=0;i<Q;i++){
root=(1LL)<<(n-1);
scanf("%d",&len);
mmax=-1,mmin=INF;
for(int j=0;j<len;j++){
scanf("%lld",&tmp);
mmax=max(mmax,tmp);
mmin=min(mmin,tmp);
}
int x=n-1;
while(1){
if(root<=mmax&&root>=mmin) break;
if(root<mmin) root=root+((1LL)<<(x-1));
else root=root-((1LL)<<(x-1));
x--;
}
printf("%lld\n",root);
}
}
return 0;
}
