作者： liuchuo

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用来标记一个结点是否是别人的结点，以便判断出谁是树的根结点。本题比较简单，在找到根结点后，从根结点开始进行搜索，首先输出一个 ‘(‘ 如果当前结点同时存在左右孩子，那么就分别继续搜索左右孩子，接下来输出当前结点的内容，如果只有右子树（语法树不会存在只有左子树没有右子树的情况），那么就在输出当前结点内容后进入右孩子结点继续搜索，最后输出一个 ‘)’ ~ 

 

Given two singly linked lists L1​=a1​→a2​→⋯→an−1​→an​ and L2​=b1​→b2​→⋯→bm−1​→bm​. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1​→a2​→bm​→a3​→a4​→bm−1​⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

Input Specification:

Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1​ and L2​, plus a positive N (≤105) which is the total number of nodes given. 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 a positive integer no more than 105, and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

Output Specification:

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

Sample Input:

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

Sample Output:

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

题目大意：给定两个单链表L1 = a1 → a2 → … → an-1 → an，和L2 = b1 → b2 → … → bm-1 → bm，如果n ≥2m，你的任务是将较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如a1 → a2 → bm → a3 → a4 → bm-1 … 的结果，例如给定两个链表分别为6→7和1→2→3→4→5，你应该输出1→2→7→3→4→6→5。输入首先在第一行中给出两个链表L1和L2的头结点的地址、以及给定的结点总数N，一个结点的地址是一个5位数的非负整数，空地址 NULL用-1表示。随后N行，每行按以下格式给出一个结点的信息：Address Data Next，其中Address是结点的地址，Data是不超过10的5次方的正整数，Next是下一个结点的地址，题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。按顺序输出结果列表，每个结点占一行，格式与输入相同。
分析：用vector<int> L1、L2存储题目中给定的两个链表，vector<int> ans保存合并后的链表。将较长的一个链表存储在L1中，如果原本L1较短，则将L1与L2用swap函数互相置换~在链表合并的过程中，i从0开始，将L1中每个结点添加到ans中，如果当前i是奇数（i & 1不等于0）就把L2的一个结点添加到ans中，直到L2中没有剩余元素~如此反复，就大功告成啦。 

 

“Forever number” is a positive integer A with K digits, satisfying the following constrains:

• the sum of all the digits of A is m;
• the sum of all the digits of A+1 is n; and
• the greatest common divisor of m and n is a prime number which is greater than 2.

Now you are supposed to find these forever numbers.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1<m<90), of which the meanings are given in the problem description.

Output Specification:

For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.

Sample Input:

2
6 45
7 80

Sample Output:

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

题目大意：“天长地久数”是指一个K位正整数A，其满足条件为A的各位数字之和为m，A+1的各位数字之和为n，且m与n的最大公约数是一个大于2的素数。本题就请你找出这些天长地久数。输入在第一行给出正整数N（≤5），随后N行，每行给出一对K（3<K<10）和m（1<m<90）。对每一对输入的K和m，首先在一行中输出Case X，其中X是输出的编号（从1开始）；然后一行输出对应的n和A，数字间以空格分隔。如果解不唯一，则每组解占一行，按n的递增序输出；若仍不唯一，则按A的递增序输出。若解不存在，则在一行中输出No Solution。
分析：sum记录A的各位数字之和，sum2记录A+1的各位数字之和，I与II分别为数A与A+1。由打表观察可得，所有天长地久数最后两位为”99″，那么将末尾的两个’9’隐藏后可直接带入暴力循环判断。将所有可能答案存储后排序输出即可~ 

 

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

• A is the root
• A and B are siblings
• A is the parent of B
• A is the left child of B
• A is the right child of B
• A and B are on the same level
• It is a full tree

Note:

• Two nodes are on the same level, means that they have the same depth.
• A full binary tree is a tree in which every node other than the leaves has two children.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than 103 and are separated by a space.

Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both A and B in the statements are in the tree.

Output Specification:

For each statement, print in a line Yes if it is correct, or No if not.

Sample Input:

9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree

Sample Output:

Yes
No
Yes
No
Yes
Yes
Yes

题目大意：假设二叉树中的所有值都是不同的正整数，给定后序和中序遍历可以唯一确定一棵二叉树。给出一系列关于二叉树结构的语句，判断它们是否正确，语句是以下之一：A是根结点，A和B是兄弟姐妹，A是B的父结点，A是B的左孩子，A是B的右孩子，A和B在同一层，这是一棵full tree。（两个结点在同一层，意味着这两个结点具有同样深度；full binary tree是指除了叶子结点外，每个结点都有两个孩子）。输入样例：第一行给出正整数N，即二叉树中结点的总数；第二行给出后序遍历序列，第三行给出中序遍历序列。一行中所有数字不超过10的3次方，并且用空格分隔。然后给出一个正整数M，然后是M行语句，保证语句的A和B都在树中。输出样例：对于每条语句，如果正确，则输出Yes，否则输出No。
分析：中序存储在In数组中，后序存储在Post数组中，根据中序和后序建树，Tree中存储树上结点的相关信息，下标即表示结点的值，其中lchild存储左孩子下标，rchild存储右孩子下标，parent存储父结点下标，将这些初始化为-1表示不存在，level存储深度，此外，root为根节点的值，Full标记是否是full tree，f判断当前语句是否正确，最后根据f的值输出Yes或No~