月度归档：2017年03月

THU2017spring 2-3 Rebuild 题解

发表评论

THU2017spring 2-3 Rebuild

描述

某二叉树的n个节点已经用[1, n]内的整数进行了编号。现给定该二叉树的先序遍历序列和中序遍历序列，试输出其对应的后序遍历序列。

输入

第一行为一个整数n。

第二、三行，即已知的先序、中序遍历序列，数字之间以空格分隔。

输出

仅一行。

若所给的先序、中续遍历序列的确对应于某棵二叉树，则输出其后序遍历序列，数字之间以空格分隔。否则，输出-1。

输入样例1

5
1 2 4 5 3
4 2 5 1 3

输出样例1

4 5 2 3 1

输入样例2

4
2 3 1 4
4 2 1 3

输出样例2

-1

输入样例3

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

输出样例3

4 1 2 7 8 6 3 5

限制

1 <= n <= 500,000

输入和输出的遍历序列均为[1, n]内整数的一个排列，整数间均以空格分隔。

时间：1 sec

空间：256 MB

提示

● 注意观察特殊节点在不同遍历序列中的位置

● 提示(.docx)：

对应输入样例1的树结构:

先序遍历序列：12453
中序遍历序列：42513
注意到根节点就是先序序列的首元素，找到根节点后，根据根节点在中序序列中的位置，可划分出左右子树。

 

代码：（一个点TLE没过，其它都OK）
继续阅读 →

Openjudge Pots

发表评论

Pots

总时间限制:
1000ms
内存限制:
65536kB
描述
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

  1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;
  2. DROP(i)      empty the pot i to the drain;
  3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

输入
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
输出
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.
样例输入
3 5 4
样例输出
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

本来我是不会做的，看了这篇题解 http://blog.csdn.net/kindlucy/article/details/5827794 之后明白的……
继续阅读 →

Openjudge 迷宫问题

发表评论

迷宫问题

总时间限制:
1000ms
内存限制:
65536kB
描述
定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径，格式如样例所示。
样例输入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
样例输出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

继续阅读 →

THU2017spring 1-4 Hospital 题解

发表评论

THU2017spring 1-4 Hospital

描述

有n个村落分布在一条公路的沿线，为方便村民们就医，现打算在公路沿线修建一所医院。

由于各村落人数、年龄分布不同等原因，每个村落对医院的需求程度也不同。这里需求程度以一个非负的权值w表示：w越大，就医需求越大。对于一个选址方案，Σwi*di作为衡量其合理性的指标，其中wi和di分别表示第i个村落的权值和距离医院的距离，该指标越小，对应的选址就越优。请给出医院修建的最优位置。

输入

共n+1行。

第一行包含一个整数n；

以下共n行，每行包含两个整数：第一个为对应村落的一维坐标xi，第二个为对应村落的权值wi。

输出

共两行。

第一行为医院的最优坐标。

第二行为对应的最小权值，即医院选择最优坐标时的Σwi*di。

注意，如果有多个坐标权值均为最小值，请给出这些坐标中的最小者。

输入样例

3
3 5
7 11
5 6

输出样例

5
32

限制

1 <= n <= 300,000

村落的地址坐标是[0, 32767]的整数。

村落的权值是[1, 10^8]的整数。

时间：1 sec

空间：256 MB

提示

一级提示

● 可以在预处理时将坐标相同的村落合并。

二级提示

● 考虑医院选址向左（或向右）移动一个单位对Σwi*di的影响何时为正、何时为负。

● 注意你的程序是否能正确处理“有多个坐标权值均为最小值”的情况。

● 虽然最终选址坐标在int范围内，但计算Σwi*di的中间过程不一定在int范围内；可以使用long long，其表示的范围是[-2^63, 2^63)。

我也实在不知道该怎么做，参考twd2的做法什么“加权中位数”，胡作吧。最后80分。。

继续阅读 →

THU2017spring 2-2 Train 题解

发表评论

THU2017spring 2-2 Train

描述

某列车调度站的铁道联接结构如图所示。

其中，A为入口，B为出口，S为中转盲端。所有铁道均为单轨单向式：列车行驶的方向只能是从A到S，再从S到B；另外，不允许超车。因为车厢可在S中驻留，所以它们从B端驶出的次序，可能与从A端驶入的次序不同。不过S的容量有限，同时驻留的车厢不得超过m节。

设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道，按照以上交通规则，这些车厢能否以{a1, a2, …, an}的次序，重新排列后从B端驶出。

输入

共两行。

第一行为两个整数n，m。

第二行为以空格分隔的n个整数，保证为{1, 2, …, n}的一个排列，表示待判断可行性的驶出序列{a1，a2，…，an}。

输出

仅一行。若驶出序列可行，则输出Yes；否则输出No。

输入样例1

5 2
1 2 3 5 4

输出样例1

Yes

输入样例2

5 5
3 1 2 4 5

输出样例2

No

限制

1 <= n <= 100,000

0 <= m <= 100,000

时间：1 sec

空间：256 MB

提示

无

这题边界条件比MOOC卡的严多了，需要考虑0的情况：
也是栈混洗，把原来的代码搞过来的……（逃）
继续阅读 →

Openjudge 鸣人和佐助

发表评论

鸣人和佐助

总时间限制: 1000ms 内存限制: 65536kB
描述
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？

已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
输入
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10 后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。 输出 输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。 样例输入 样例输入1 4 4 1 #@## **## ###+ **** 样例输入2 4 4 2 #@## **## ###+ **** 样例输出 样例输出1 6 样例输出2 4 继续阅读 →

Openjudge Charm Bracelet

发表评论

Charm Bracelet

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

Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charmiin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability’ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

输入
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
输出
Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
样例输入
4 6
1 4
2 6
3 12
2 7
样例输出
23
来源
USACO 2007 December Silver

继续阅读 →

Openjudge 棋盘问题

发表评论

棋盘问题

总时间限制:
1000ms
内存限制:
65536kB
描述
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
输入
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
输出
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
样例输入
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
样例输出
2
1
来源
蔡错@pku

继续阅读 →

Openjudge A Knight’s Journey

发表评论

A Knight’s Journey

总时间限制:
1000ms
内存限制:
65536kB
描述
Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
输入
The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
输出
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
样例输入
3
1 1
2 3
4 3
样例输出
Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
来源
TUD Programming Contest 2005, Darmstadt, Germany

继续阅读 →