总时间限制: 1000ms 内存限制: 65536kB
描述
给定初始整数顺串，以及大小固定并且初始元素已知的二叉最小堆（为完全二叉树或类似完全二叉树，且父元素键值总小于等于任何一个子结点的键值），要求利用堆实现置换选择排序，并输出第一个顺串。例如给定初始顺串 29,14,35,13, 以及堆（记为 16 19 31 25 21 56 40）， 置换选择排序得到的第一个顺串为 16 19 21 25。

输入

第一行包含两个整数，m 为初始顺串的数的个数，n 为二叉最小堆的大小
第二行包含 m 个整数，即初始顺串
第三行包含 n 个整数，即已经建好的堆的元素（有序，按照从堆顶到堆底，从左到右的顺序）

输出

输出包含一行，即第一个顺串。

样例输入

1
2
3

4 7
29 14 35 13
16 19 31 25 21 56 40

样例输出

总时间限制: 10000ms 内存限制: 1000kB

描述

给出一个图的结构，输出其拓扑排序序列，要求在同等条件下，编号小的顶点在前

输入

若干行整数，第一行有 2 个数，分别为顶点数 v 和弧数 a，接下来有 a 行，每一行有 2 个数，分别是该条弧所关联的两个顶点编号

输出

若干个空格隔开的顶点构成的序列 (用小写字母)

样例输入

1
2
3
4
5
6
7
8
9

6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5

总时间限制: 1000ms 内存限制: 10000kB

描述

很久很久以前，森林里住着一群兔子。兔子们无聊的时候就喜欢研究星座。如图所示，天空中已经有了 n 颗星星，其中有些星星有边相连。兔子们希望删除掉一些边，然后使得保留下的边仍能是 n 颗星星连通。他们希望计算，保留的边的权值之和最小是多少？

输入

第一行只包含一个表示星星个数的数 n，n 不大于 26，并且这 n 个星星是由大写字母表里的前 n 个字母表示。接下来的 n-1 行是由字母表的前 n-1 个字母开头。最后一个星星表示的字母不用输入。对于每一行，以每个星星表示的字母开头，然后后面跟着一个数字，表示有多少条边可以从这个星星到后面字母表中的星星。如果 k 是大于 0，表示该行后面会表示 k 条边的 k 个数据。每条边的数据是由表示连接到另一端星星的字母和该边的权值组成。权值是正整数的并且小于 100。该行的所有数据字段分隔单一空白。该星星网络将始终连接所有的星星。该星星网络将永远不会超过 75 条边。没有任何一个星星会有超过 15 条的边连接到其他星星（之前或之后的字母）。在下面的示例输入，数据是与上面的图相一致的。

输出

输出是一个整数，表示最小的权值和。

样例输入

1
2
3
4
5
6
7
8
9

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

总时间限制: 1000ms 内存限制: 65536kB

描述

Background
Binary trees are a common data structure in computer science. In this problem we will look at an infinite binary tree where the nodes contain a pair of integers. The tree is constructed like this:
The root contains the pair (1, 1).
If a node contains (a, b) then its left child contains (a + b, b) and its right child (a, a + b)

Problem

Given the contents (a, b) of some node of the binary tree described above, suppose you are walking from the root of the tree to the given node along the shortest possible path. Can you find out how often you have to go to a left child and how often to a right child?

输入

The first line contains the number of scenarios.
Every scenario consists of a single line containing two integers i and j (1 <= i, j <= 2*109) that represent
a node (i, j). You can assume that this is a valid node in the binary tree described above.

输出

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing two numbers l and r separated by a single space, where l is how often you have to go left and r is how often you have to go right when traversing the tree from the root to the node given in the input. Print an empty line after every scenario.

总时间限制: 1000ms 内存限制: 262144kB

描述

Freda 报名参加了学校的越野跑。越野跑共有 N 人参加，在一条笔直的道路上进行。这 N 个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这 N 个人同时沿着道路向相同的方向跑去。换句话说，这 N 个人可以看作 x 轴上的 N 个点，在比赛开始后，它们同时向 x 轴正方向移动。
假设越野跑的距离足够远，这 N 个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生 “赶超” 的事件呢？

输入

第一行 1 个整数 N。
第二行为 N 个非负整数，按从前到后的顺序给出每个人的跑步速度。
对于 50% 的数据，2<=N<=1000。
对于 100% 的数据，2<=N<=100000。

输出

一个整数，表示有多少对参赛者之间发生赶超事件。

样例输入

1
2

5
1 3 10 8 5

总时间限制: 1000ms 内存限制: 65535kB

描述

给定一棵二叉树，在二叉树上执行两个操作：

1. 节点交换
   把二叉树的两个节点交换。
2. 前驱询问
   询问二叉树的一个节点对应的子树最左边的节点。

输入

第一行输出一个整数 t (t <= 100)，代表测试数据的组数。

对于每组测试数据，第一行输入两个整数 n m，n 代表二叉树节点的个数，m 代表操作的次数。

随后输入 n 行，每行包含 3 个整数 X Y Z，对应二叉树一个节点的信息。X 表示节点的标识，Y 表示其左孩子的标识，Z 表示其右孩子的标识。

再输入 m 行，每行对应一次操作。每次操作首先输入一个整数 type。

总时间限制: 2000ms 内存限制: 65536kB

描述

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点 N (0<=N<=100000)，牛位于点 K (0<=K<=100000)。农夫有两种移动方式：

1、从 X 移动到 X-1 或 X+1，每次移动花费一分钟
2、从 X 移动到 2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入

两个整数，N 和 K

输出

一个整数，农夫抓到牛所要花费的最小分钟数

总时间限制: 10000ms 内存限制: 65536kB

描述

在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

输入

无输入。
输出
按给定顺序和格式输出所有八皇后问题的解（见 Sample Output）。

样例输入

1

(null)

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

No. 1
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
No. 2
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
No. 3
1 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
No. 4
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
No. 5
0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
No. 6
0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 7
0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 8
0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 9
0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
...以下省略

总时间限制: 1000ms 内存限制: 65535kB

描述

给定一棵二叉树，求该二叉树的深度

二叉树深度定义：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的节点个数为树的深度

输入

第一行是一个整数 n，表示二叉树的结点个数。二叉树结点编号从 1 到 n，根结点为 1，n <= 10
接下来有 n 行，依次对应二叉树的 n 个节点。
每行有两个整数，分别表示该节点的左儿子和右儿子的节点编号。如果第一个（第二个）数为 - 1 则表示没有左（右）儿子

输出

输出一个整型数，表示树的深度

样例输入

总时间限制: 1000ms 内存限制: 131072kB

描述

给定一些文档，要求求出某些单词的倒排表。

对于一个单词，它的倒排表的内容为出现这个单词的文档编号。

输入

第一行包含一个数 N，1 <= N <= 1000，表示文档数。
接下来 N 行，每行第一个数 ci，表示第 i 个文档的单词数。接下来跟着 ci 个用空格隔开的单词，表示第 i 个文档包含的单词。文档从 1 开始编号。1 <= ci <= 100。
接下来一行包含一个数 M，1 <= M <= 1000，表示查询数。
接下来 M 行，每行包含一个单词，表示需要输出倒排表的单词。
每个单词全部由小写字母组成，长度不会超过 256 个字符，大多数不会超过 10 个字符。

输出

对于每一个进行查询的单词，输出它的倒排表，文档编号按从小到大排序。
如果倒排表为空，输出 "NOT FOUND"。

样例输入