分类： Code

A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

Input Specification:

Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

Output Specification:

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

10
8 15 3 4 1 5 12 10 18 6

Sample Output:

1 3 5 8 4 6 15 10 12 18

题目大意：笛卡尔树，是由一系列不同数字构成的二叉树。树是堆排序的，中序遍历返回原始序列。例如，给定序列{8, 15, 3, 4, 1, 5, 12, 10, 18, 6}，小顶堆笛卡尔树如图所示。你的工作是输出小顶堆笛卡尔树的层序遍历序列。输入格式：给一个正整数N，接下来一行给出N个不同的数字，用空格分隔。所有数字都在int范围内。输出格式：在一行中输出小顶堆笛卡尔树的层序遍历。一行中的所有数字必须用一个空格隔开，并且行首和行尾不得有多余的空格。
分析：中序遍历保存在In数组中，层序遍历结果保存在映射map<int, int> ans中。本题需要将小顶堆的中序遍历转化为层次遍历。我们知道，在小顶堆中，数值最小的那个元素为根结点，对于其任何子树也一样。所以我们只要在中序遍历中找到最小的那个数作为当前的根结点，左边的所有数都归左子树，右边所有数都归右子树。将根结点的序号设为1，左孩子的序号为它的两倍，右孩子的序号为它的两倍+1，最后根据序号顺序输出ans即为层序遍历的顺序。哇呜。

A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.

Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.

Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤ N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.

Output Specification:

For each of the K areas, print in a line your advice in the following format:

• if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK..
• if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.
• if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.

Here X is the index of an area, starting from 1 to K.

Sample Input:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
2 4 6
3 3 2 1

Sample Output:

Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.

题目大意：为峰会安排休息区，一个理想的安排是邀请这些领导人，每个人互相之间都是直接朋友。给定一套暂定的安排，判断每个区域是否都已准备就绪。输入格式：第一行给一个正整数N，表示峰会的首领数量，以及一个正整数M，表示友谊关系的数量。接下来是M行，每行给出一对互为朋友的领导人的编号。领导人的编号从1到N。然后给出另一个正整数K，接下来是K行暂定的休息区，每行给出一个正整数L，然后是一系列L个不同的领导人编号。一行中所有数字都用空格分隔。输出格式：对于K个休息区的每一个，请按以下格式将您的建议输出在一行中：如果在这个休息区每个人都互相是直接朋友，并且没有朋友漏掉（即没有其他人是这个休息区每个人的直接朋友），就输出Area X is OK.如果在这个休息区每个人都是每个人的直接朋友，但在不破坏理想安排的情况下，可能还会邀请一些其他领导人，就输出Area X may invite more people, such as H. H是可以被邀请的领导人的最小编号。如果该休息区的安排不理想，则输出Area X needs help. 这样主持人可以提供一些特别的服务帮助领导人们互相了解。
分析：二维数组A作为邻接矩阵存储两个人是否是好朋友，如果是u和v好朋友就将数组A[u][v] = A[v][u] = 1；集合temp存储待检查的序列号。先检查所有的人是不是互相都为好朋友，如果不是的话，直接输出needs help。然后，检查剩下的所有人中，是否有人是他们所有人的好朋友、但是没有被邀请的，如果没有，就输出is OK. 否则输出may invite more people, such as f. 其中f为可以被邀请的领导人的最小编号~

 

Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the size of a block. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218

Sample Output:

71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1

题目大意：给定一个单链表L，将每K个结点看成一个区块（链表最后若不足K个结点，也看成一个区块），请编写程序将L中所有区块的链表反转。例如：给定L为1→2→3→4→5→6→7→8，K为3，则输出应该为7→8→4→5→6→1→2→3。每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(≤10的五次方)、以及正整数K(≤N)，即区块的大小。结点的地址是5位非负整数，NULL 地址用−1表示。接下来有N行，每行格式为：Address Data Next，其中Address是结点地址，Data是该结点保存的整数数据，Next是下一个结点的地址。对于每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
分析：L为输入链表，ans为答案链表，二维数组E为区块链表。先将链表数据记录在结构体A中，遍历A将链表正确顺序记录在链表L中，然后需要重新定义链表长度n（因为有输入中有无效的假结点信息）。遍历链表L，将每K个结点所分隔成的区块保存在二维数组E中，再从后往前将区块链表E中的值添加到答案链表ans中，最后根据格式输出ans链表就好啦~

 

When your interviewer asks you to write “Hello World” using C, can you do as the following figure shows?

Input Specification:

Each input file contains one test case. For each case, the first part gives the 26 capital English letters A-Z, each in a 7×5 matrix of C‘s and .‘s. Then a sentence is given in a line, ended by a return. The sentence is formed by several words (no more than 10 continuous capital English letters each), and the words are separated by any characters other than capital English letters.

It is guaranteed that there is at least one word given.

Output Specification:

For each word, print the matrix form of each of its letters in a line, and the letters must be separated by exactly one column of space. There must be no extra space at the beginning or the end of the word.

Between two adjacent words, there must be a single empty line to separate them. There must be no extra line at the beginning or the end of the output.

Sample Input:

Sample Output:

题目大意：输入首先给出26个英文大写字母A-Z，每个字母用7×5的、由C和.组成的矩阵构成。最后在一行中给出一个句子，以回车结束。句子是由若干个单词（每个包含不超过10个连续的大写英文字母）组成的，单词间以任何非大写英文字母分隔。题目保证至少给出一个单词。输出要求：对于每个单词，将其中每个字母用矩阵形式在一行中输出，字母间有一列空格分隔。单词的首尾不得有多余空格。相邻的两个单词间必须有一空行分隔。输出的首尾不得有多余空行。
分析：三维数组a中储存26个字母对应的图形矩阵，out中储存每行要输出的图形矩阵，同时初始化out所有元素为空格。字符串中可能存在乱七八糟的字符，所以用getline做句子的输入。句子的单词间以任何非大写字母分隔，用while循环遍历找到下标j为非大写字母所在下标，i为当前单词首下标，然后根据单词中每一个字母，将输出图形记录到out中，最后输出out数组~flag用来标记之前是否输出过一个单词，如果输出过，flag=1，则当再次需要输出单词之前需要先输出一个’\n’~

Dijkstra’s algorithm is one of the very famous greedy algorithms.
It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let’s call it Dijkstra sequence, is generated by Dijkstra’s algorithm.

On the other hand, for a given graph, there could be more than one Dijkstra sequence. For example, both { 5, 1, 3, 4, 2 } and { 5, 3, 1, 2, 4 } are Dijkstra sequences for the graph, where 5 is the source. Your job is to check whether a given sequence is Dijkstra sequence or not.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers Nv​ (≤103) and Ne​ (≤105), which are the total numbers of vertices and edges, respectively. Hence the vertices are numbered from 1 to Nv​.

Then Ne​ lines follow, each describes an edge by giving the indices of the vertices at the two ends, followed by a positive integer weight (≤100) of the edge. It is guaranteed that the given graph is connected.

Finally the number of queries, K, is given as a positive integer no larger than 100, followed by K lines of sequences, each contains a permutationof the Nv​ vertices. It is assumed that the first vertex is the source for each sequence.

All the inputs in a line are separated by a space.

Output Specification:

For each of the K sequences, print in a line Yes if it is a Dijkstra sequence, or No if not.

Sample Input:

5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4

Sample Output:

Yes
Yes
Yes
No

题目大意：Dijkstra算法用来解决单源最短路径问题，用来寻找从一个特定源顶点到给定图的所有其他顶点的最短路径。在每一步中，我们找到一个尚未包含且与源顶点距离最小的顶点，并将其收集到集合中。通过Dijkstra算法逐步生成的一个有序的序列称之为Dijkstra序列。对于给定的图，可能有多个Dijkstra序列。你的工作是检查给定的序列是否是Dijkstra序列。输入样例：第一行输入两个正整数Nv和Ne，分别是顶点和边的总数量。顶点的编号是1到Nv，然后是Ne行，每行通过给出两端顶点的编号来描述一条边，外加一个正整数，表示边的权重。保证给定的图是连通的。最后，给出一个正整数K表示查询的次数，然后是K行序列，每行包含Nv个顶点的排列，假设第一个顶点是每个序列的源点。一行中的所有输入由空格分隔。输出格式：对于K个序列中的每一个，如果它是Dijkstra序列，则输出一行Yes，否则输出No。
分析：V和E表示顶点和边的数量，二维数组Edge中存储两点之间的距离，数组Path为当前需要判断的序列，数组Distance为Dijskra最短路径起点到各个点的最短距离，flag记录当前路径是否为真，book标记确定好最短距离的点。直接丢到Dijskra算法里，判断每一步能不能由给定的路径完成，最后根据flag的值输出Yes或No~ 

 

Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 20) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:

data left_child right_child

where data is a string of no more than 10 characters, left_child and right_child are the indices of this node’s left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by −1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.

Output Specification:

For each case, print in a line the postfix expression, with parentheses reflecting the precedences of the operators.There must be no space between any symbols.

Sample Input 1:

8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
– -1 6
c -1 -1

Sample Output 1:

(((a)(b)+)((c)(-(d))*)*)

Sample Input 2:

8
2.35 -1 -1
* 6 1
– -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1

Sample Output 2:

(((a)(2.35)*)(-((str)(871)%))+)

题目大意：给一个语法树，输出相应的后缀表达式，用括号反映运算符的优先级。输出样例：第一行给一个正整数N，表示语法树结点的总数量。然后是N行，每行给出一个结点的信息（第i行对应第i个结点），格式为data left_child right_child，其中data是不超过10个字符的字符串，left_child和right_child分别是该结点的左右子结点的下标。结点的下标从1到N。NULL用-1表示。输出样例：对于每种情况，在一行中输出后缀表达式，括号反映运算符的优先级。任何符号之间没有多余的空格。
分析：lc中存储左孩子下标，rc中存储右孩子下标，mark用来标记一个结点是否是别人的结点，以便判断出谁是树的根结点。本题比较简单，在找到根结点后，从根结点开始进行搜索，首先输出一个 ‘(‘ 如果当前结点同时存在左右孩子，那么就分别继续搜索左右孩子，接下来输出当前结点的内容，如果只有右子树（语法树不会存在只有左子树没有右子树的情况），那么就在输出当前结点内容后进入右孩子结点继续搜索，最后输出一个 ‘)’ ~