总时间限制: 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"。

样例输入

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

描述

在 N（1<=N<10,000 且 N 为奇数）个数中，找到中位数。

输入

第 1 行：N

第 2 至 N+1 行：每行是一个整数

输出

第一行：中位数

样例输入

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

描述

给出 N 个范围在 [0, 65535] 的整数，编程支持以下的操作：

（1）修改操作：C d，所有的数都增加 d。如果超过 65535，把结果模 65536。 0 <= d <= 65535
（2）查询操作：Q i，统计在 N 个正整数中有多少个整数其对应的二进制形式的第 i 位二进制位为非 0。0 <= i <= 15。并且最低位 i 为 0。

最后，输出所有查询操作的统计值。

输入

输入的第一行为两个正整数 N,M, 其中 N 为操作的整数的个数，而 M 为具体有多少个操作。
输入的第二行为 N 个正整数，为进行操作的 N 个正整数。
下面有 M 行，分别表示 M 个操作。

N<=100000,M<=200000

输出

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

描述

你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是，你有一本词典可以帮助你。

输入

首先输入一个词典，词典中包含不超过 100000 个词条，每个词条占据一行。每一个词条包括一个英文单词和一个外语单词，两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行，然后给出一个由外语单词组成的文档，文档不超过 100000 行，而且每行只包括一个外语单词。输入中出现单词只包括小写字母，而且长度不会超过 10。

输出

在输出中，你需要把输入文档翻译成英文，每行输出一个英文单词。如果某个外语单词不在词典中，就把这个单词翻译成 “eh”。

样例输入

1
2
3
4
5
6
7
8
9

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

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

描述

二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

这里，我们想探究二叉树的建立和序列输出。

输入

只有一行，包含若干个数字，中间用空格隔开。（数字可能会有重复）

输出

输出一行，对输入数字建立二叉搜索树后进行前序周游的结果。

样例输入