标签归档：题解

洛谷 最短网络 Agri-Net 题解

发表评论

题目背景

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000

输入输出格式

输入格式：

第一行： 农场的个数，N（3<=N<=100）。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。

输出格式：

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

输入输出样例

输入样例#1：

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出样例#1：

28

说明

题目翻译来自NOCOW。

USACO Training Section 3.1
继续阅读 →

NOIOJ 比赛排名 题解

发表评论

题目描述

N个人参加比赛，问有多少种排名情况，允许出现并列的情况

输入

输入一个数字N，N小于200
本题有多组数据，请做到-1结束

输出

输出有多少种排名情况

样例输入

2
-1

样例输出

3

数据范围限制

继续阅读 →

NOIOJ 取数游戏

发表评论

题目描述

我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。如果你能算出一共有多少种取法，那么你会被天神Lijiganjun奖励。

输入

仅包含一个数n（1< n < 50）。

输出

仅包含一个数———你的答案。

样例输入

5

样例输出

13

继续阅读 →

洛谷 P1141 01迷宫 题解

发表评论

题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入输出格式

输入格式：

输入的第1行为两个正整数n，m。

下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。

接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式：

输出包括m行，对于每个询问输出相应答案。

输入输出样例

输入样例#1：

2 2

01

10

1 1

2 2

输出样例#1：

4

4

说明

所有格子互相可达。

对于20%的数据，n≤10；

对于40%的数据，n≤50；

对于50%的数据，m≤5；

对于60%的数据，n≤100，m≤100；

对于100%的数据，n≤1000，m≤100000。

继续阅读 →

数据结构 邓俊辉 PA#3 无线广播(Broadcast) 题解

发表评论

无线广播(Broadcast)

描述

某广播公司要在一个地区架设无线广播发射装置。该地区共有n个小镇，每个小镇都要安装一台发射机并播放各自的节目。

不过，该公司只获得了FM104.2和FM98.6两个波段的授权，而使用同一波段的发射机会互相干扰。已知每台发射机的信号覆盖范围是以它为圆心，20km为半径的圆形区域，因此，如果距离小于20km的两个小镇使用同样的波段，那么它们就会由于波段干扰而无法正常收听节目。现在给出这些距离小于20km的小镇列表，试判断该公司能否使得整个地区的居民正常听到广播节目。

输入

第一行为两个整数n，m，分别为小镇的个数以及接下来小于20km的小镇对的数目。 接下来的m行，每行2个整数，表示两个小镇的距离小于20km（编号从1开始）。

输出

如果能够满足要求，输出1，否则输出-1。

输入样例

4 3
1 2
1 3
2 4

输出样例

1

限制

1 ≤ n ≤ 10000

1 ≤ m ≤ 30000

不需要考虑给定的20km小镇列表的空间特性，比如是否满足三角不等式，是否利用传递性可以推出更多的信息等等。

时间：2 sec

空间：256MB

提示

BFS

继续阅读 →

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的情况：
也是栈混洗，把原来的代码搞过来的……（逃）
继续阅读 →