中国大学MOOC-陈越、何钦铭-数据结构-2022夏

函数题

01-复杂度3 二分查找

本题要求实现二分查找算法。
函数接口定义：

Position BinarySearch( List L, ElementType X );

其中 List 结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};
List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );
int main()
{
    List L;
    ElementType X;
    Position P;
    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d\n", P);
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例1：
5
12 31 55 89 101
31

输出样例1：
2

输入样例2：
3
26 78 233
31

输出样例2：
0

代码长度限制
16 KB
时间限制
100 ms
内存限制
64MB

02-线性结构1 两个有序链表序列的合并

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：

List Merge( List L1, List L2 );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。
裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */
List Merge( List L1, List L2 );
int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：
3
1 3 5
5
2 4 6 8 10

输出样例：
1 2 3 4 5 6 8 10
NULL
NULL

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

04-树7 二叉搜索树的操作集

本题要求实现给定二叉搜索树的5种常用操作。

函数接口定义：

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

• 函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针；
• 函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行Not Found并返回原树的根结点指针；
• 函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针；
• 函数FindMin返回二叉搜索树BST中最小元结点的指针；
• 函数FindMax返回二叉搜索树BST中最大元结点的指针。
  裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};
void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */
BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;
    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3

输出样例：
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

编程题

01-复杂度1 最大子列和问题

给定K个整数组成的序列{ N1​, N2​, …, NK​ }，“连续子列”被定义为{ Ni​, Ni+1​, …, Nj​ }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：与样例等价，测试基本正确性；
• 数据2：102个随机整数；
• 数据3：103个随机整数；
• 数据4：104个随机整数；
• 数据5：105个随机整数；

输入格式:
输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:
6
-2 11 -4 13 -5 -2

输出样例:
20

代码长度限制
16 KB
时间限制
50000 ms
内存限制
64MB
64MB

C语言

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100000
int main()
{
    int i, k;
    int ThisSum = 0;
    int MaxSum = 0;
    int A[MAXSIZE];
    scanf("%d", &k);
    for (i = 0; i < k; i++)
    {
        scanf("%d", &A[i]);
        ThisSum = ThisSum + A[i];
        if (MaxSum < ThisSum) MaxSum = ThisSum;
        else if (ThisSum < 0) ThisSum = 0;
    }
    printf("%d", MaxSum);
    return 0;
}

01-复杂度2 Maximum Subsequence Sum

Given a sequence of K integers { N1​, N2​, …, NK​ }. A continuous subsequence is defined to be { Ni​, Ni+1​, …, Nj​ } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:
10 1 4

代码长度限制
16 KB
时间限制
200 ms
内存限制
64MB
64MB

翻译 最大子序列和

给定一系列K整数{N1​,N2​, …,NK​ }. 连续子序列定义为{Ni​,Ni+1​, …,Nj​}其中1≤i≤j≤K、 最大子序列是连续子序列，其元素之和最大。例如，给定序列{-2,11，-4,13，-5，-2}，其最大子序列是{11，-4,13}，最大和为20。
现在，您应该找到最大和，以及最大子序列的第一个和最后一个数字。

输入规范：
每个输入文件包含一个测试用例。每种情况占据两行。第一行包含一个正整数K(≤10000). 第二行包含由空格分隔的K个数字。

输出规格：
对于每个测试用例，一行输出最大和，以及最大子序列的第一个和最后一个数字。数字必须用一个空格分隔，但行的末尾必须没有额外的空格。如果最大子序列不是唯一的，则输出具有最小索引i和j的子序列（如样本情况所示）。如果所有的K个数字都是负数，那么它的最大和被定义为0，并且你应该输出整个序列的第一个和最后一个数字。

样本输入：
10
-10 1 2 3 4 -5 -23 3 7 -21

样品输出：
10 1 4

代码长度限制
16 KB
时间限制
200毫秒
内存限制
64MB
64MB

C语言

#include<stdio.h>
#define MaxSize 10000
#define INF 0x3f3f3f3f
void MaxSubseqSum2(int A[], int N){
    int ThisSum=0, MaxSum = -INF;
    int i;
    int temp=0, first=0, last=0;

    for(i=0; i<N; i++){
        ThisSum += A[i];

        if(ThisSum < 0){  //ThisSum<0表示 A[i]<0
            ThisSum = 0;
            temp = i + 1;
        }
        else if(ThisSum > MaxSum){
            MaxSum = ThisSum;
            first = temp;
            last = i;
        }
    }
    if(MaxSum < 0)
        printf("0 %d %d", A[0], A[N-1]);
    else
        printf("%d %d %d", MaxSum, A[first], A[last]);
}
int main(){
    int i, N;
    int A[MaxSize];

    scanf("%d", &N);
    for(i=0; i<N; i++)
        scanf("%d", &A[i]);
    MaxSubseqSum2(A, N);

    return 0;
}

02-线性结构2 一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

代码长度限制
16 KB
时间限制
200 ms
内存限制
64MB

C语言

02-线性结构3 Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

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 length of the sublist to be reversed. 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 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 反转链接列表

给定一个常数K和一个单独链接的列表L，你应该反转L上每个K个元素的链接。例如，给定L为1→2→3→4→5→6，如果K=3，那么你必须输出3→2→1→6→5→4; 如果k=4，你必须输出4→3→2→1→5→6.

输入规范：
每个输入文件包含一个测试用例。对于每种情况，第一行包含第一个节点的地址，即正N(≤10^5）是节点的总数，正K(≤N） 这是要反转的子列表的长度。节点的地址是一个5位非负整数，空值由-1表示。
然后是N行，每行描述一个格式的节点：
Address Data Next
其中Address是节点的位置，Data是整数，Next是下一个节点的位置。

输出规格：
对于每种情况，输出结果的有序链接列表。每个节点占据一条线，并以与输入中相同的格式打印。

样本输入：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

样品输出：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

代码长度限制
16 KB
时间限制
400毫秒
内存限制
64MB

02-线性结构4 Pop Sequence

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:
For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:
YES
NO
NO
YES
NO

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 02-线性结构4 Pop序列

给定一个最多可以保存M个数字的堆栈。按1、2、3、…、N和随机弹出的顺序按下N个数字。您应该知道给定的数字序列是否是堆栈中可能的pop序列。例如，如果M是5，N是7，我们可以从堆栈中获得1，2，3，4，5，6，7，但不是3，2，1，7，5，六，4。

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行包含3个数字（均不超过1000）：M（堆栈的最大容量）、N（推送序列的长度）和K（要检查的pop序列的数量）。接着是K行，每行包含一个由N个数字组成的pop序列。一行中的所有数字都用空格分隔。

输出规格：
对于每个pop序列，如果确实是堆栈中可能的pop序列则打印一行“是”，如果不是，则打印“否”。

样本输入：
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

样本输出：
对
不
不
对
不

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

03-树1 树的同构03-树1 树的同构

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
图1
图2
现给定两棵树，请你判断它们是否是同构的。

输入格式:
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。

输出格式:
如果两棵树是同构的，输出“Yes”，否则输出“No”。

输入样例1（对应图1）：
8
A 1 2
B 3 4
C 5 –
D – –
E 6 –
G 7 –
F – –
H – –
8
G – 4
B 7 6
F – –
A 5 1
H – –
C 0 –
D – –
E 2 –

输出样例1:
Yes

输入样例2（对应图2）：
8
B 5 7
F – –
A 0 3
C 6 –
H – –
D – –
G 4 –
E 1 –
8
D 6 –
B 5 –
E – –
H – –
C 0 2
G – 3
F – –
A 1 4

输出样例2:
No

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

03-树2 List Leaves

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

Output Specification:
For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:
8
1 –

• –
  0 –
  2 7
• –
• –
  5 –
  4 6

Sample Output:
4 1 5

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 03-树2.树叶列表

给定一棵树，你应该按照从上到下、从左到右的顺序列出所有的叶子。

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行给出一个正整数N(≤10） 这是树中节点的总数，因此节点的编号从0到N−1.然后跟随N条线，每条线对应于一个节点，并给出该节点左右子节点的索引。如果该子项不存在，则在该位置将放置一个“-”。任何一对孩子都被一个空格隔开。

输出规格：
对于每个测试用例，按从上到下、从左到右的顺序在一行中打印所有叶子的索引。任何相邻数字之间必须正好有一个空格，并且在行尾没有多余的空格。

样本输入：
8.
1 –

• –
  0 –
  2 7
• –
• –
  5 –
  4 6

样本输出：
4 1 5

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

03-树3 Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:
3 4 2 6 5 1

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 03-树再次进行3次树遍历

有序二叉树遍历可以通过堆栈以非递归方式实现。例如，假设遍历一个6节点的二叉树（键的编号从1到6），堆栈操作是：push（1）；推动（2）；推动（3）；pop（）；pop（）；推动（4）；pop（）；pop（）；推动（5）；推动（6）；pop（）；pop（）。然后，可以从这个操作序列生成一个唯一的二叉树（如图1所示）。您的任务是给出此树的后序遍历序列。
图1

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行都包含一个正整数N(≤30），这是树中的节点总数（因此节点的编号从1到N）。接下来是2N行，每行以“Push X”的格式描述堆栈操作，其中X是被推送到堆栈上的节点的索引；或“Pop”，意思是从堆栈中弹出一个节点。

输出规格：
对于每个测试用例，在一行中打印相应树的后序遍历序列。保证存在解决方案。所有数字必须用一个空格分隔，并且在行尾不得有额外的空格。

样本输入：
6.
按1
推2
推3
流行音乐
流行音乐
推4
流行音乐
流行音乐
推5
推6
流行音乐
流行音乐

样本输出：
3 4 2 6 5 1

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

04-树4 是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:
Yes
No
No
鸣谢青岛大学周强老师补充测试数据！

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

04-树5 Root of AVL Tree

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print the root of the resulting AVL tree in one line.

Sample Input 1:
5
88 70 61 96 120

Sample Output 1:
70

Sample Input 2:
7
88 70 61 96 120 90 65

Sample Output 2:
88

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 04-树5.AVL树的根

AVL树是自平衡二叉搜索树。在AVL树中，任何节点的两个子树的高度最多相差一；如果在任何时候它们的差异超过一个，则进行重新平衡以恢复此属性。图1-4说明了旋转规则。
现在，给定一系列插入，您应该知道生成的AVL树的根。

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行都包含一个正整数N(≤20） 其是要插入的键的总数。然后在下一行中给出N个不同的整数键。一行中的所有数字都用空格分隔。

输出规格：
对于每个测试用例，在一行中打印生成的AVL树的根。

样本输入1：
5.
88 70 61 96 120

样本输出1：
70

样本输入2：
7.
88 70 61 96 120 90 65

样本输出2：
88

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

04-树6 Complete Binary Search Tree

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
· The left subtree of a node contains only nodes with keys less than the node’s key.
· The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
· Both the left and right subtrees must also be binary search trees.
A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
· Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
· Input Specification:
· Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
· Output Specification:
· For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
· Sample Input:
· 10
1 2 3 4 5 6 7 8 9 0
· Sample Output:
· 6 3 8 1 5 7 9 0 2 4
· 代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 04-树6.完全二叉搜索树

二叉搜索树（BST）递归定义为具有以下属性的二叉树：
·节点的左子树仅包含键小于节点键的节点。
·节点的右子树仅包含键大于或等于节点键的节点。
·左子树和右子树都必须是二叉搜索树。
完全二叉树（CBT）是一种完全填充的树，但底层可能例外，底层从左到右填充。
·现在，给定一系列不同的非负整数键，如果要求树也必须是CBT，则可以构造唯一的BST。您应该输出此BST的级别顺序遍历序列。
·输入规格：
·每个输入文件包含一个测试用例。对于每种情况，第一行都包含一个正整数N(≤1000). 然后在下一行中给出N个不同的非负整数键。一行中的所有数字都用空格分隔，且不大于2000。
·输出规格：
·对于每个测试用例，在一行中打印相应完整二叉搜索树的级别顺序遍历序列。一行中的所有数字都必须用空格分隔，并且在行尾不得有额外的空格。
·样本输入：
· 10
1 2 3 4 5 6 7 8 9 0
·样本输出：
· 6 3 8 1 5 7 9 0 2 4
· 代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

05-树7 堆中的路径

将一系列给定数字依次插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。

输入格式:
每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

输出格式:
对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。

输入样例:
5 3
46 23 26 24 10
5 4 3

输出样例:
24 23 10
46 23 10
26 10

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

05-树8 File Transfer

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification:
Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:
I c1 c2
where I stands for inputting a connection between c1 and c2; or
C c1 c2
where C stands for checking if it is possible to transfer files between c1 and c2; or
S
where S stands for stopping this case.

Output Specification:
For each C case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are k components." where k is the number of connected components in this network.

Sample Input 1:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

Sample Output 1:
no
no
yes
There are 2 components.

Sample Input 2:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S

Sample Output 2:
no
no
yes
yes
The network is connected.

代码长度限制
16 KB
Go (go)
时间限制

翻译 05-树8文件传输

我们有一个计算机网络和一系列双向连接。每个连接都允许从一台计算机到另一台计算机的文件传输。可以从网络上的任何计算机向任何其他计算机发送文件吗？

输入规格：
每个输入文件包含一个测试用例。对于每个测试用例，第一行包含N（2≤N≤104）、网络中的计算机总数。然后，网络中的每台计算机由1到N之间的正整数表示。然后，在以下行中，输入以以下格式给出：
I c1和c2
其中I表示输入c1和c2之间的连接；或
c1和c2
其中C表示检查是否可以在c1和c2之间传输文件；或
S
其中S代表停止这种情况。

输出规格：
对于每个C类，如果可以或不可能在c1和c2之间分别传输文件，则在一行中打印“是”或“否”。在每个案例的结尾，如果任何一对计算机之间存在路径，则在一行中打印“网络已连接”；或“有k个组件”。其中k是该网络中连接组件的数量。

样本输入1：
5.
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

样本输出1：
不
不
对
有两个组件。

样本输入2：
5.
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S

样本输出2：
不
不
对
对
网络被连接。

代码长度限制
16kb
走
时间限制

05-树9 Huffman Codes

In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another set of code can be given as {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}, but {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

Input Specification:
Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:
c[1] f[1] c[2] f[2] … c[N] f[N]
where c[i] is a character chosen from {‘0’ – ‘9’, ‘a’ – ‘z’, ‘A’ – ‘Z’, ‘_’}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (≤1000), then followed by M student submissions. Each student submission consists of N lines, each in the format:
c[i] code[i]
where c[i] is the i-th character and code[i] is an non-empty string of no more than 63 ‘0’s and ‘1’s.

Output Specification:
For each test case, print in each line either "Yes" if the student’s submission is correct, or "No" if not.
Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.

Sample Input:
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11

Sample Output:
Yes
Yes
No
No

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 05-树9哈夫曼码

1953年，大卫·A·霍夫曼发表了他的论文《构造最小冗余码的方法》，并因此在计算机科学史上发表了自己的名字。作为一名教授，我给出了关于哈夫曼密码的期末考试问题，我遇到了一个大问题：哈夫曼代码不是唯一的。例如，给定一个字符串“aaaxuaxz”，我们可以观察到字符“a”、“x”、“u”和“z”的频率分别为4、2、1和1。我们可以将符号编码为{‘a’=0，’x’=10，’u’=110，’z’=111}，或者以另一种方式编码为｛‘a’=1，’x’=01，’u’=001，’z’=000}，两者都将字符串压缩为14位。另一组代码可以表示为{‘a’=0，’x’=11，’u’=100，’z’=101}，但是{‘a’=0，x’=01，’u’=011，’z’=001}是不正确的，因为“aaaxuaxz”和“aazuax”都可以从代码000010110001中解码。学生们正在提交各种代码，我需要一个计算机程序来帮助我确定哪些代码是正确的，哪些是错误的。

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行给出整数N（2≤N≤63），然后后跟一行，该行包含以下格式的所有N个不同字符及其频率：
c[1]f[1]c[2]f[2]…c[N]f[N]
其中c[i]是从{0′-‘9’，a’-‘z’，a’-‘z’，’_’}中选择的字符，f[i]为c[i’的频率，是不超过1000的整数。下一行给出一个正整数M(≤1000），然后是M个学生提交。每个学生提交的材料由N行组成，每行的格式如下：
c[i]代码[i]
其中c[i]是第i个字符，代码[i]是不超过63’0’和’1’的非空字符串。

输出规格：
对于每个测试用例，如果学生提交的内容正确，则在每行打印“是”，如果不正确，则打印“否”。
注：最优解不一定由霍夫曼算法生成。任何具有最佳码长的前缀码都被认为是正确的。

样本输入：
7.
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4.
十万
B 00001
C 0001
D 001
E 01
F10
G.11
A 01010
B 01011
C 0100
D 011
E10
F 11
G 00
一千
B 001
C 010
D 011
E100
F 101
G 110
十万
B 00001
C 0001
D 001
E 00
F10
G.11

样本输出：
对
对
不
不

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

06-图1 列出连通集

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:
按照"{ v1​ v2​ … vk​ }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5

输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

06-图2 Saving James Bond – Easy Version

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape — he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:
For each test case, print in a line "Yes" if James can escape, or "No" if not.

Sample Input 1:
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

Sample Output 1:
Yes

Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12

Sample Output 2:
No

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 06-图2拯救詹姆斯·邦德-简易版

这一次，让我们考虑一下电影《生死抉择》中的情况，世界上最著名的间谍詹姆斯·邦德被一群毒贩抓获。他被送到湖心的一小块土地上，那里到处都是鳄鱼。在那里，他做出了最大胆的逃跑动作——他跳到了最近一条鳄鱼的头上！在动物意识到发生了什么之前，詹姆斯又跳到了下一个大脑袋上……最后，他在最后一条鳄鱼咬他之前到达了河岸（事实上，特技演员被大嘴巴抓住了，用他那超厚的靴子勉强逃脱）。
假设这个湖是一个100乘100平方米的湖。假设湖的中心位于（0,0），东北角位于（50,50）。中央岛是一个以（0,0）为中心的圆盘，直径为15。许多鳄鱼在湖中的不同位置。考虑到每只鳄鱼的坐标和詹姆斯能跳的距离，你必须告诉他他是否能逃脱。

输入规格：
每个输入文件包含一个测试用例。每种情况都从包含两个正整数N的行开始(≤100）表示鳄鱼的数量，D表示詹姆斯能跳的最大距离。接下来是N行，每行包含鳄鱼的（x，y）位置。请注意，没有两只鳄鱼停留在同一位置。

输出规格：
对于每个测试用例，如果James可以逃逸，请打印一行“是”，如果不可以，请打印“否”。

样本输入1：
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

样本输出1：
对

样本输入2：
4 13
-12 12
12 12
-12 -12
12 -12

样本输出2：
不

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

06-图3 六度空间

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式:
输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤103，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。

输出格式:
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

输入样例:
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

输出样例:
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

代码长度限制
16 KB
时间限制
2500 ms
内存限制
64MB

07-图4 哈利·波特的考试

哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。

输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。

输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。

输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80

输出样例:
4 70

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

07-图5 Saving James Bond – Hard Version

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape — he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:
For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x,y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.

Sample Input 1:
17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

Sample Output 1:
4
0 11
10 21
10 35

Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12

Sample Output 2:
0

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 07-图5拯救詹姆斯·邦德-硬版

这一次，让我们考虑一下电影《生死抉择》中的情况，世界上最著名的间谍詹姆斯·邦德被一群毒贩抓获。他被送到湖心的一小块土地上，那里到处都是鳄鱼。在那里，他做出了最大胆的逃跑动作——他跳到了最近一条鳄鱼的头上！在动物意识到发生了什么之前，詹姆斯又跳到了下一个大脑袋上……最后，他在最后一条鳄鱼咬他之前到达了河岸（事实上，特技演员被大嘴巴抓住了，用他那超厚的靴子勉强逃脱）。
假设这个湖是一个100乘100平方米的湖。假设湖的中心位于（0,0），东北角位于（50,50）。中央岛是一个以（0,0）为中心的圆盘，直径为15。许多鳄鱼在湖中的不同位置。考虑到每只鳄鱼的坐标和詹姆斯能跳的距离，你必须告诉他到达其中一个河岸的最短路径。路径的长度是詹姆斯必须跳跃的次数。

输入规格：
每个输入文件包含一个测试用例。每种情况都从包含两个正整数N的行开始(≤100）表示鳄鱼的数量，D表示詹姆斯能跳的最大距离。接下来是N行，每行包含鳄鱼的（x，y）位置。请注意，没有两只鳄鱼停留在同一位置。

输出规格：
对于每个测试用例，如果James能够逃脱，则在一行中输出他必须进行的最小跳跃次数。然后从下一行开始，输出路径上每只鳄鱼的位置（x，y），每对鳄鱼排成一行，从岛屿到河岸。如果詹姆斯无法通过这种方式逃脱，只需给他0作为跳跃次数。如果有许多最短路径，只需输出第一跳最小的路径，这保证是唯一的。

样本输入1：
17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

样本输出1：
4.
0 11
10 21
10 35

样本输入2：
4 13
-12 12
12 12
-12 -12
12 -12

样本输出2：
0

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

07-图6 旅游规划

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:
3 40

代码长度限制
16 KB
Java (javac)
时间限制

08-图7 公路村村通

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例:
12

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

08-图8 How Long Does It Take

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1), and M, the number of activities. Then M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.

Output Specification:
For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output "Impossible".

Sample Input 1:
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

Sample Output 1:
18

Sample Input 2:
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

Sample Output 2:
Impossible

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 08-图8.需要多长时间

考虑到项目所有活动之间的关系，您应该找到项目的最早完成时间。

输入规格：
每个输入文件包含一个测试用例。每种情况都从包含两个正整数N的行开始(≤100）、活动检查点的数量（因此假设检查点的编号从0到N−1） 和M，活动的数量。接下来是M行，每行都给出了一项活动的描述。对于第i个活动，给出了三个非负数：S[i]、E[i]和L[i]，其中S[i]是开始检查点的索引，E[i]：结束检查点，L[i]为活动的持续时间。一行中的数字用空格分隔。

输出规格：
对于每个测试用例，如果可以安排，则在一行中打印其最早完成时间；或者简单地输出“不可能”。

样本输入1：
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

样本输出1：
18

样本输入2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

样本输出2：
不可能的

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

08-图9 关键活动

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。
但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。
任务调度问题中，如果还给出了完成每个子任务需要的时间，则我们可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天完成，也不会影响全局的工期；但是有些任务必须准时完成，否则整个项目的工期就要因此延误，这种任务就叫“关键活动”。
请编写程序判定一个给定的工程项目的任务调度是否可行；如果该调度方案可行，则计算完成整个工程项目需要的最短时间，并输出所有的关键活动。

输入格式:
输入第1行给出两个正整数N(≤100)和M，其中N是任务交接点（即衔接相互依赖的两个子任务的节点，例如：若任务2要在任务1完成后才开始，则两任务之间必有一个交接点）的数量。交接点按1~N编号，M是子任务的数量，依次编号为1~M。随后M行，每行给出了3个正整数，分别是该任务开始和完成涉及的交接点编号以及该任务所需的时间，整数间用空格分隔。

输出格式:
如果任务调度不可行，则输出0；否则第1行输出完成整个工程项目需要的时间，第2行开始输出所有关键活动，每个关键活动占一行，按格式“V->W”输出，其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是：任务开始的交接点编号小者优先，起点编号相同时，与输入时任务的顺序相反。

输入样例:
7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2

输出样例:
17
1->2
2->4
4->6
6->7

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

09-排序1 排序

给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
· 数据1：只有1个元素；
· 数据2：11个不相同的整数，测试基本正确性；
· 数据3：103个随机整数；
· 数据4：104个随机整数；
· 数据5：105个随机整数；
· 数据6：105个顺序整数；
· 数据7：105个逆序整数；
· 数据8：105个基本有序的整数；
· 数据9：105个随机正整数，每个数字不超过1000。

输入格式:
· 输入第一行给出正整数N（≤105），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。
· 输出格式:
· 在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。
· 输入样例:
· 11
4 981 10 -17 0 -20 29 50 8 43 -5
· 输出样例:
· -20 -17 -5 0 4 8 10 29 43 50 981
· 代码长度限制
16 KB
时间限制
10000 ms
内存限制
64MB

09-排序2 Insert or Merge

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print in the first line either "Insertion Sort" or "Merge Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Sample Output 1:
Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

Sample Output 2:
Merge Sort
1 2 3 8 4 5 7 9 0 6

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 09-排序2.插入或合并

根据维基百科：
插入排序迭代，每次重复使用一个输入元素，并增长排序输出列表。在每次迭代中，插入排序从输入数据中删除一个元素，在排序列表中找到它所属的位置，并将其插入其中。它会重复，直到没有输入元素保留。
合并排序的工作原理如下：将未排序的列表划分为N个子列表，每个子列表包含1个元素（1个元素的列表被视为已排序）。然后重复合并两个相邻的子列表以产生新的排序子列表，直到只剩下1个子列表。
现在，给定整数的初始序列，再加上一个序列，它是某种排序方法多次迭代的结果，你能告诉我们使用的是哪种排序方法吗？

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行给出一个正整数N(≤100). 然后在下一行中，给出N个整数作为初始序列。最后一行包含N个数字的部分排序序列。假设目标序列总是上升的。一行中的所有数字都用空格分隔。

输出规格：
对于每个测试用例，在第一行中打印“插入排序”或“合并排序”，以指示用于获得部分结果的方法。然后再运行此方法进行一次迭代，并在第二行中输出结果序列。保证每个测试用例的答案都是唯一的。一行中的所有数字都必须用空格分隔，并且在行尾不得有额外的空格。

样本输入1：
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

样本输出1：
插入排序
1 2 3 5 7 8 9 4 6 0

样本输入2：
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

样本输出2：
合并排序
1 2 3 8 4 5 7 9 0 6

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB

09-排序3 Insertion or Heap Sort

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print in the first line either "Insertion Sort" or "Heap Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Sample Output 1:
Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

Sample Output 2:
Heap Sort
5 4 3 1 0 2 6 7 8 9

代码长度限制
16 KB
时间限制
400 ms
内存限制
64MB

翻译 09-排序3.插入或堆排序

根据维基百科：
插入排序迭代，每次重复使用一个输入元素，并增长排序输出列表。在每次迭代中，插入排序从输入数据中删除一个元素，在排序列表中找到它所属的位置，并将其插入其中。它会重复，直到没有输入元素保留。
堆排序将其输入分为已排序区域和未排序区域，它通过提取最大元素并将其移动到已排序区域来迭代收缩未排序区域。它涉及使用堆数据结构而不是线性时间搜索来查找最大值。
现在，给定整数的初始序列，再加上一个序列，它是某种排序方法多次迭代的结果，你能告诉我们使用的是哪种排序方法吗？

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行给出一个正整数N(≤100). 然后在下一行中，给出N个整数作为初始序列。最后一行包含N个数字的部分排序序列。假设目标序列总是上升的。一行中的所有数字都用空格分隔。

输出规格：
对于每个测试用例，在第一行中打印“插入排序”或“堆排序”，以指示用于获得部分结果的方法。然后再运行此方法进行一次迭代，并在第二行中输出结果序列。保证每个测试用例的答案都是唯一的。一行中的所有数字都必须用空格分隔，并且在行尾不得有额外的空格。

样本输入1：
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

样本输出1：
插入排序
1 2 3 5 7 8 9 4 6 0

样本输入2：
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

样本输出2：
堆排序
5 4 3 1 0 2 6 7 8 9

代码长度限制
16kb
时间限制
400毫秒
内存限制
64MB