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

描述

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

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

输入

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

输出

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

样例输入

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

描述

VariantF 的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入

第一行为两个正整数 M 和 N，代表内存容量和文章的长度。
第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
对于 50% 的数据，1<=N、M<=1000；
对于 100% 的数据，1<=N、M<=1000000。

输出

一个整数，为软件需要查词典的次数。

样例输入

1
2

3 7 
1 2 1 5 4 4 1 

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

描述

判断一个由 a-z 这 26 个字符组成的字符串中哪个字符出现的次数最多

输入

第 1 行是测试数据的组数 n，每组测试数据占 1 行，是一个由 a-z 这 26 个字符组成的字符串
每组测试数据之间有一个空行，每行数据不超过 1000 个字符且非空

输出

n 行，每行输出对应一个输入。一行输出包括出现次数最多的字符和该字符出现的次数，中间是一个空格。
如果有多个字符出现的次数相同且最多，那么输出 ascii 码最小的那一个字符

样例输入

1
2
3
4

2
abbccc

adfadffasdf

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

描述

栈和队列都是常用的线性结构，它们都提供两个操作：

Push：加入一个元素。

Pop：弹出一个元素。

不同的是，栈是” 先进后出”，而队列则是” 先进先出”。

给出一个线性结构的进出顺序，判定这个结构是栈还是队列。

输入

第一行输入一个整数 t，代表有 t 组测试数据
对于每组测试数据，第一行输入一个整数 n，代表操作的次数。
随后输入 n 行，每行包含两个整数 type val。
当 type = 1 时，表示该次操作为 push 操作，val 表示进入的数字。当 type=2 时，表示该次操作为 pop 操作，val 代表出来的数字。
3<=n<=2000