1018. Public Bike Management (30)-PAT甲级真题(Dijkstra + DFS)

1018. Public Bike Management (30)
There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

Snip20160825_77
Figure 1 illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths:

1. PBMC -> S1 -> S3. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3, so that both stations will be in perfect conditions.

2. PBMC -> S2 -> S3. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (<= 100), always an even number, is the maximum capacity of each station; N (<= 500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci (i=1,…N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0->S1->…->Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.

Sample Input:
10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1
Sample Output:
3 0->2->3 0
题目大意:每个自行车车站的最大容量为一个偶数cmax,如果一个车站里面自行车的数量恰好为cmax / 2,那么称处于完美状态。如果一个车展容量是满的或者空的,控制中心(处于结点0处)就会携带或者从路上手机一定数量的自行车前往该车站,一路上会让所有的车展沿途都达到完美。现在给出cmax,车站的数量n,问题车站sp,m条边,还有距离,求最短路径。如果最短路径有多个,求能带的最少的自行车数目的那条。如果还是有很多条不同的路,那么就找一个从车站带回的自行车数目最少的。带回的时候是不调整的
分析:Dijkstra + DFS。如果只有Dijkstra是不可以的,因为minNeed和minBack在路径上的传递不满足最优子结构,不是简单的相加的过程,只有在所有路径都确定了之后才能区选择最小的need和最小的back
Dijkstra求最短路径,dfs求minNeed和minBack和path,dfs的时候模拟一遍需要调整的过程,求出最后得到的need和back,与minNeed和minBack比较然后根据情况更新path,最后输出minNeed path 和 minBack,记得path是从最后一个结点一直到第一个结点的,所以要倒着输出~

 

PAT 1130. Infix Expression (25)-甲级

Given a syntax tree (binary), you are supposed to output the corresponding infix 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 infix expression, with parentheses reflecting the precedences of the operators. Note that there must be no extra parentheses for the final expression, as is shown by the samples. 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))

题目大意:给一个二叉树,输出中缀表达式,且加上括号表示运算的优先级~
分析:首先根据所有孩子结点编号寻找1~n中没有出现过的编号标记为root,即树的根结点~然后进行从root结点开始dfs~如果当前index == -1说明当前没有结点则返回空字符串;当right != -1说明该结点不是叶子节点(不可能存在只有左边没有右边的情况的啦,因为那不符合一个算式~左边可以是空表示0~右边不可以的~),那么就将左右结点的val和自身的val串成字符串,保存在自己的val中~如果当前index又不是根结点,那就在左右两边加上括号~最后输出dfs(root)的结果即可~

 

PAT 1128. N Queens Puzzle (20)-甲级

The “eight queens puzzle” is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general N queens problem of placing N non-attacking queens on an N×N chessboard. (From Wikipedia – “Eight queens puzzle”.)

Here you are NOT asked to solve the puzzles. Instead, you are supposed to judge whether or not a given configuration of the chessboard is a solution. To simplify the representation of a chessboard, let us assume that no two queens will be placed in the same column. Then a configuration can be represented by a simple integer sequence (Q1, Q2, …, QN), where Qi is the row number of the queen in the i-th column. For example, Figure 1 can be represented by (4, 6, 8, 2, 7, 1, 3, 5) and it is indeed a solution to the 8 queens puzzle; while Figure 2 can be represented by (4, 6, 7, 2, 8, 1, 9, 5, 3) and is NOT a 9 queens’ solution.

Input Specification:

Each input file contains several test cases. The first line gives an integer K (1 < K <= 200). Then K lines follow, each gives a configuration in the format “N Q1 Q2 … QN”, where 4 <= N <= 1000 and it is guaranteed that 1 <= Qi <= N for all i=1, …, N. The numbers are separated by spaces.

Output Specification:

For each configuration, if it is a solution to the N queens problem, print “YES” in a line; or “NO” if not.

Sample Input:
4
8 4 6 8 2 7 1 3 5
9 4 6 7 2 8 1 9 5 3
6 1 5 2 6 4 3
5 1 3 5 2 4
Sample Output:
YES
NO
NO
YES

题目大意:给出一个皇后图,以这样的方式给出:一个数组包含n个数字,每个数字表示该列的皇后所在的行数~判断给出的皇后图是否满足不会互相攻击(任意两个皇后都要不在同一行或者同一列,且不在斜对角线上~)
分析:用v[n]存储一张图给出的数字~对于第j个数字,判断前0~j-1个数字中是否有在同一行的(v[j] == v[t])和在斜对角线上的(abs(v[j]-v[t]) == abs(j-t))【因为已经告诉肯定不在同一列了,所以不需要判断是否在同一列啦~】如果发现了不满足的情况,就将result由true标记为false~最后根据result是true还是false输出对应的YES还是NO即可~

PAT 1127. ZigZagging on a Tree (30)-甲级

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” — that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

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 inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1
Sample Output:
1 11 5 8 17 12 20 15

题目大意:给出一个树的中序和后序遍历结果,求它的Z字型层序遍历,也就是偶数层从右往左,奇数层从左往右遍历~
分析:分为3步:1.根据中序和后序建树 保存在tree二维数组中,比如:tree[i][0] = val表示post[i]的左孩子是post[val],tree[i][1] = val表示post[i]的右孩子是post[val]~
2.进行广度优先搜索,将树从根结点开始所有结点层序遍历,保存在result二维数组中,比如:result[i]保存第i层所有结点的序列~
3.进行z字型输出,根据当前层号的奇偶性分别从左往右、从右往左遍历输出~

1. dfs:因为post(后序)是按照左、右、根的顺序遍历的,所以从右往左,最右边的肯定是根结点~所以postRight是当前子树的根结点的下标,将它的赋值给index,并继续dfs tree[index][0]和tree[index][1]~
根据post[postRight]的结点在in里面的下标位置i,可以得到i的左边是左子树,即inLeft 到 i – 1,右边是右子树:i + 1 到 inRight。而对于post来说,根据左子树的结点个数i – inLeft可以得到[postLeft, postLeft + (i – inLeft) – 1]是post中左子树的范围,[postLeft + (i – inLeft), postRight – 1]是post中右子树的范围~
2.广度优先搜索,采用队列q,q中保存的是node结点,node.index表示当前节点在post中的下标,node.depth表示当前结点在树中的层数~
3.当 i % 2 == 0的时候倒序输出,否则正序输出~

 

PAT 1068. 万绿丛中一点红(20)-乙级

对于计算机而言,颜色不过是像素点对应的一个24位的数值。现给定一幅分辨率为MxN的画,要求你找出万绿丛中的一点红,即有独一无二颜色的那个像素点,并且该点的颜色与其周围8个相邻像素的颜色差充分大。

输入格式:

输入第一行给出三个正整数,分别是M和N(<= 1000),即图像的分辨率;以及TOL,是所求像素点与相邻点的颜色差阈值,色差超过TOL的点才被考虑。随后N行,每行给出M个像素的颜色值,范围在[0, 224)内。所有同行数字间用空格或TAB分开。

输出格式:

在一行中按照“(x, y): color”的格式输出所求像素点的位置以及颜色值,其中位置x和y分别是该像素在图像矩阵中的列、行编号(从1开始编号)。如果这样的点不唯一,则输出“Not Unique”;如果这样的点不存在,则输出“Not Exist”。

输入样例1:
8 6 200
0 0 0 0 0 0 0 0
65280 65280 65280 16711479 65280 65280 65280 65280
16711479 65280 65280 65280 16711680 65280 65280 65280
65280 65280 65280 65280 65280 65280 165280 165280
65280 65280 16777015 65280 65280 165280 65480 165280
16777215 16777215 16777215 16777215 16777215 16777215 16777215 16777215
输出样例1:
(5, 3): 16711680
输入样例2:
4 5 2
0 0 0 0
0 0 3 0
0 0 0 0
0 5 0 0
0 0 0 0
输出样例2:
Not Unique
输入样例3:
3 3 5
1 2 3
3 4 5
5 6 7
输出样例3:
Not Exist

分析:首先这个点必须是唯一的,所以用map标记如果不是唯一的点就不用考虑了~接着对于每个点,判断它的周围八个点与它的差值是否大于阈值,如果有一个点没有满足大于阈值就return false~最后记得输入的时候是列、行——m、n,输出的时候也是列、行坐标~

 

PAT 1126. Eulerian Path (25)-甲级

In graph theory, an Eulerian path is a path in a graph which visits every edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Konigsberg problem in 1736. It has been proven that connected graphs with all vertices of even degree have an Eulerian circuit, and such graphs are called Eulerian. If there are exactly two vertices of odd degree, all Eulerian paths start at one of them and end at the other. A graph that has an Eulerian path but not an Eulerian circuit is called semi-Eulerian. (Cited from https://en.wikipedia.org/wiki/Eulerian_path)

Given an undirected graph, you are supposed to tell if it is Eulerian, semi-Eulerian, or non-Eulerian.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (<= 500), and M, which are the total number of vertices, and the number of edges, respectively. Then M lines follow, each describes an edge by giving the two ends of the edge (the vertices are numbered from 1 to N).

Output Specification:

For each test case, first print in a line the degrees of the vertices in ascending order of their indices. Then in the next line print your conclusion about the graph — either “Eulerian”, “Semi-Eulerian”, or “Non-Eulerian”. Note that all the numbers in the first line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:
7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6
Sample Output 1:
2 4 4 4 4 4 2
Eulerian
Sample Input 2:
6 10
1 2
1 3
2 3
2 4
3 4
5 2
6 3
4 5
6 4
5 6
Sample Output 2:
2 4 4 4 3 3
Semi-Eulerian
Sample Input 3:
5 8
1 2
2 5
5 4
4 1
1 3
3 2
3 4
5 3
Sample Output 3:
3 3 4 3 3
Non-Eulerian

题目大意:如果一个连通图的所有结点的度都是偶数,那么它就是Eulerian,如果除了两个结点的度是奇数其他都是偶数,那么它就是Semi-Eulerian,否则就是Non-Eulerian~
分析:用邻接表存储图,判断每个结点的度【也就是每个结点i的v[i].size()】是多少即可得到最终结果~注意:图必须是连通图,所以要用一个深搜判断一下连通性,从结点1开始深搜,如果最后发现统计的连通结点个数cnt != n说明是不是连通图,要输出Non-Eulerian~