$24
问题 A: Complete binary tree
题目描述
Alice has a binary tree of n nodes. These nodes are numbered from 1 to n, she does not know if this tree is a complete binary tree or not. She turns to you for help. We guarantee that the input is a binary tree.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 14). For each test case, the first line will be an integer n (1<=n<=150000). Then followed by n lines, each line will be two integers x and y, the i-th line means the left child of node i is x, the right child of node i is y. If node i has no left child, then x will be 0, if node i has no right child, then ywill be 0.
输出
For each test output Yes or No in one line.
样例输入
1
5
3
4 0
5 0
0 0
0 0
样例输出
No
问题 B: Judgement
题目描述
Please judge whether given tree can be a binary search tree or not.
输入
The first line will be an integer T, which is the number of test cases. (1 <= T <= 10). For each test case, the first line will be an integer n(1 <= n <= 105). The second line will be n integers, a1……an(1 <= ai <= 109), ai
represents the value of the i-th node, then followed by n - 1 lines, each line will be two integers x and y, x is the father of y. y can be any position child of x.
输出
For each test, print the number of the test cases first, then print YES when the tree is a binary search tree, else print NO.
We guarantee that (1 <= x, y <= n) and input is a tree.
样例输入
2
4
1 2 3 4
1
4
2
1 2 3
2 1
2 3
样例输出
Case #1: NO
Case #2: YES
问题 C: AVL-tree
题目描述
Carol has a binary tree of n nodes. These nodes are numbered from 1 to n, she does not know if this tree is a AVL-tree or not. Then, she turns to you for help.
The AVL-tree should be:
The key of x is larger than all the keys in the left subtree of x, the key of x is smaller than all the keys in the right subtree of x. The height of the left subtree and right subtree of each node can not have a difference larger than 1.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 100). For each test case, the first line will be an integer n(1 <= n <= 10000). The second line will be integers, a1……an, ai means the key of
the i-th node(1 <= ai <= 2*109). Then followed by n lines, each line will be two integers x and y, the i-th line means the left child of node i is x, the right child of node i is y. If node i has no left child, then x will be 0, if node i has no right child, then y will be 0.
输出
For each test output Yes or No in one line.
样例输入
2
5
4 2 5 1 3
3
4 5
0 0
0 0
0 0
5
4 2 5 1 4
3
5
0 0
0 0
0 0
样例输出
Yes
No
问题 D: K-th
题目描述
David has numbers, and he wants to know the K-th biggest number among them.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 12). For each test case, the first line will be two integers n and K(1 <= n <= 5*105, K <= 5000 or K = 0.99n). The second line will be n integers, a1……an(1 <= ai <= 109).
输出
For each test output the K-th biggest element in one line.
样例输入
1
10 1
1 2 3 4 5 6 7 8 9 10
样例输出
10
问题 E: Bubble sort
题目描述
Ella has a sequence of n integers. After she learns the 'Bubble sort'(in ascending order), she wants to apply it. There is a question asking what the sequence is like after K times 'Bubble operation'. One 'Bubble operation' is like this:
for(int i = 1; i < n; ++i) { if(a[i] a[i + 1]) swap(a[i], a[i + 1]); }
The sequence starts from 1, and its length is n.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n and K(1 <= K <= n <= 200000). The second line will be n integers, a1……an(1 <=
ai <= 109), representing the original sequence. It queries what the sequence is like after K times 'Bubble sort' from the original sequence.
输出
For each query, print the sequence in one line, do not print extra space in the end of one line.
样例输入
1
1
4 3 2 1
样例输出
4 3 2 1 5
问题 F: Balanced Binary Tree
题目描述
In a company, there are thousands of employees, your work is to check the information about the salary. There is a minimum salary(it is the same for everyone), whenever someone’s salary is less than this minimum salary, he(or she) will leave the company. There are n operations, and each operation is one of the following cases:
Insert x: a fresh man joins the company, whose salary is x.
Add x: increase everyone’s salary by x.
Subtract x: reduce everyone’s salary by x.
Query x: print the k-th maximum salary in this company.
At first, the company has 0 employees.
输入
The first line will be an integer T, which is the number of test cases. (1 <= T <= 10). For each test case, the first line will be two integers n(1 <= n <= 105) and m(1 <= m <= 106), n is the number of operations, m is the minimum salary. Then followed by n lines, each line will be one of the following cases:
I x: Insert x.
A x: Add x.
S x: Subtract x.
Q x: Query x.
输出
For each “Query”, print the k-th maximum salary in this company, if the number of employees is less than k, print “-1”. At last, print the number of employees who has leave the company. We guarantee that no one will come back to the company after he(or she) leaves.
样例输入
1
10 I 60 I 70 S 50 Q 2 I 30 S 15 A 5 Q 1 Q 2
样例输出
10
20
-1
2
提示
Please find extra material to learn how to construct the balanced binary tree.
问题 G: Skipping inquiry
题目描述
Grace has n numbers, ther are a1……an . Let M = sqrt(n), the biggest integer less or equal to the square root
of n. And there are n queries. For each query, there are two integers x and y. You need to answer the M-th biggest number among ax, ax+y……(x + ky <= n) . If the number of the elements is less than M, please output -1.
输入
The first line will be an integer T, which is the number of test cases. (1 <= T <= 5). For each test case, the first line will be an integer n(1 <= n <= 40000). The second line will be n integers a1……an(1 <= ai <= 109). Then followed by n lines, each line contains two integers x and y
输出
For each test output the M-th biggest element or -1 in one line.
样例输入
1
5
1 2 3 4 5
1 1
2 2
3 3
4 4
5 5
样例输出
4
2
-1
-1
-1
