历年浙江大学计算机保研上机真题

2025浙江大学计算机保研上机真题
2024浙江大学计算机保研上机真题
2023浙江大学计算机保研上机真题
在线测评链接：https://pgcode.cn/school?classification=1

最小包围矩形

题目描述

给定一系列二维平面点的坐标 $(x,y)$，其中 $x$ 和 $y$ 均为整数，要求用一个最小的长方形框将所有点框在内。

长方形框的边分别平行于 $x$ 和 $y$ 坐标轴，点落在边上也算是被框在内。

输入格式

测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中 $x$ 和 $y$ 均小于 $2^{31}$；一对 $(0,0)$ 坐标标志着一个测试用例的结束。

注意 $(0,0)$ 不作为任何一个测试用例里面的点。

一个没有点的测试用例标志着整个输入的结束。

输出格式

对每个测试用例，在 $1$ 行内输出 $2$ 对整数，其间用一个空格隔开。

第 $1$ 对整数是长方形框左下角的坐标，第 $2$ 对整数是长方形框右上角的坐标。

输入样例

12 56
23 56
13 10
0 0
12 34
0 0
0 0

输出样例

12 10 23 56
12 34 12 34

Play with Linked List

题目描述

Given a singly linked list $L_1\to L_2\to \cdots \to L_{n-1}\to L_n$ and an integer $1\le k<n$, you are supposed to rearrange the links to obtain a list like $L_k\to L_n\to L_{k-1}\to L_{n-1}\to \dots$. For example, given $L$ being $1\to 2\to 3\to 4\to 5\to 6$ and $k=4$, you must output $4\to 6\to 3\to 5\to 2\to 1$.

输入格式

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive $N$ ($\le 10^5$) which is the total number of nodes, and an integer $1\le k<n$ where $n$ is the number of nodes in the linked list. The address of a node is a 5-digit non-negative 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 $10^5$, and Next is the position of the next node. It is guaranteed that there are at least two nodes on the list.

输出格式

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.

输入样例

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

输出样例

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

Conway’s Conjecture

题目描述

John Horton Conway, a British mathematician active in recreational mathematics, proposed a conjecture in 2014: arrange the factors of any given number in ascending order, and pull the exponents down, we can get another number. Keep doing so we must end up at a prime number. For example:
$18=2\times 3^2\to 232=2^3\times 29\to 2329=17\times 137\to 17137$ (which is a prime).

Now you are supposed to write a program to make one step verification of this conjecture. That is, for any given positive integer $N$, you must factorize it, and then test if the number obtained from its factors is a prime.

By the way, this conjecture has been proven false by James Davis, who has discovered a counterexample: $135323853961879=13\times 53^2\times 3853\times 96179$. Alas…

输入格式

Each input file contains one test case which gives a positive integer $N$ ($<10^5$).

输出格式

For each case, first print in a line the number obtained from $N$’s factors. Then in the next line, print Yes if the above number is a prime, or No if not.

输入样例

2329

输出样例

17137
Yes

计算数字串每位平方和

题目描述

给定一个数字字符串 $S$，计算其每位数字的平方和。

例如，数字串 $123$ 的每位平方和为 $1^2+2^2+3^2=14$。

输入格式

输入一个数字字符串 $S$，长度不超过 $100$。

输出格式

输出一个整数，表示数字串每位数字的平方和。

输入样例

123

输出样例

14

蛇形数字输出

题目描述

将给定的数字按蛇形顺序输出。

例如，输入数字序列为 $1,2,3,4,5,6,7,8,9$，则蛇形输出为：

1 2 3
6 5 4
7 8 9

给定的数字不会连续，需要先对数字进行排序。

可以直接调用排序函数。

输入格式

第一行包含一个整数 $n$，表示数字的个数。

第二行包含 $n$ 个整数，表示需要排序的数字序列。

输出格式

输出按蛇形顺序排列的数字矩阵。

每行的数字之间用空格分隔。

输入样例

9
1 3 5 7 9 2 4 6 8

输出样例

1 2 3
6 5 4
7 8 9

Happy Numbers

题目描述

给你一个数，让你进行循环操作，每次循环把这个数的每一位的平方加在一起变成一个新的数。

若最后变成 $1$ 输出循环次数，若以其他数进入循环则输出这个循环的数。

输入格式

输入一个整数 $n$（$1\le n\le 10^6$）。

输出格式

如果最终变成 $1$，输出循环次数；否则输出进入循环的数。

输入样例

19

输出样例

4

朋友数统计

题目描述

给定若干个人和若干组朋友关系（例如：小 A 和小 B 是朋友，小 C 和小 A 是朋友等），统计每个人的朋友数量，并输出朋友数量最多的前三个人。

如果有多个人朋友数量相同，则按名字的字典序升序排列。

输入格式

第一行包含一个整数 $n$，表示朋友关系的数量。

接下来的 $n$ 行，每行包含两个名字 $name1$ 和 $name2$，表示 $name1$ 和 $name2$ 是朋友关系。

名字由大小写字母和数字组成，长度不超过 $20$。

输出格式

输出朋友数量最多的前三个人，每行包含一个名字及其朋友数量，格式为 名字 数量。

如果不足三人，则输出所有存在的人。

输入样例

4
小A 小B
小C 小A
小D 小E
小A 小D

输出样例

小A 3
小D 2
小B 1

Zigzag Sequence

题目描述

给你 $n$ 个数和一个 $m$，然后把这 $n$ 个数以每行 $m$ 个数进行输出。

若最后一行少于 $m$ 个数就直接换行。

输入格式

输入包含 $n$ 个数和一个整数 $m$。

输出格式

将 $n$ 个数按每行 $m$ 个输出，最后一行不足 $m$ 个时直接换行。

输入样例

1 2 3 4 5 6 7 8 9 10 3

输出样例

1 2 3
4 5 6
7 8 9
10

AVL Tree

题目描述

给你 $n$ 个数，让你构建一棵二叉排序树，判断这棵树是不是平衡树。

输入格式

输入包含多组测试数据。

每组数据第一行为一个整数 $n$，表示数的个数。

接下来一行包含 $n$ 个整数，表示要插入二叉排序树的数。

输出格式

对于每组测试数据，如果构建的二叉排序树是平衡树，输出 “Yes”，否则输出 “No”。

输入样例

5
1 2 3 4 5

输出样例

No

Top3 in Subgraph

题目描述

给你一个图，这个图中的 top3 指的是图中节点度最多的前三个节点。

若度数相同，则按节点编号排序。

现在有若干次询问，每次询问给定一些节点编号，问你由这些节点构成的子图的 top3 是多少。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，表示图的节点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

接下来的一行包含一个整数 $q$，表示询问的次数。

接下来的 $q$ 行，每行包含若干个整数，第一个整数 $k$ 表示该次询问涉及的节点数量，接下来的 $k$ 个整数表示具体的节点编号。

输出格式

对于每个询问，输出由给定节点构成的子图中的 top3 节点编号。

若子图中节点数量不足三个，则输出所有节点编号。

输入样例

5 6
1 2
1 3
2 3
2 4
3 4
4 5
3
2 1 2
3 1 2 3
4 1 2 3 4

输出样例

1 2
1 2 3
2 3 1

多项式标准形式

题目描述

给定一个次数为 $n$ 的多项式 $P(x)$，其标准形式为 $P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_{1}x+a_0$。

已知 $a_n=1$ 且 $P(x)$ 的所有根 { r 1 , r 2 , … , r n } \{r_1, r_2, \ldots, r_n\} {r1​,r2​,…,rn​} 都是整数。

因此，$P(x)$ 可以表示为 $(x-r_1)(x-r_2)\dots (x-r_n)$。

你的任务是根据给定的所有根，将 $P(x)$ 表示为标准形式。

输入格式

每个输入文件包含一个测试用例。

对于每个测试用例，第一行给出一个正整数 $n$（$\le 10$），表示 $P(x)$ 的次数。

接下来的一行给出 $n$ 个整数根，用空格分隔。

输出格式

对于每个测试用例，在一行中输出系数 $a_i$（$i=n-1,\dots ,0$）。

所有数字必须用一个空格分隔，行首或行末不得有多余的空格。

保证所有计算都在 int 范围内。

输入样例

3
-1 4 -1

输出样例

-2 -7 -4

One Way In, Two Ways Out

题目描述

Consider a special queue which is a linear structure that allows insertions at one end, yet deletions at both ends. Your job is to check, for a given insertion sequence, if a deletion sequence is possible. For example, if we insert $1$, $2$, $3$, $4$, and $5$ in order, then it is possible to obtain $1$, $3$, $2$, $5$, and $4$ as an output, but impossible to obtain $5$, $1$, $3$, $2$, and $4$.

输入格式

Each input file contains one test case. For each case, the first line gives $2$ positive integers $N$ and $K$ ($\le 10$), which are the number of insertions and the number of queries, respectively. Then $N$ distinct numbers are given in the next line, as the insertion sequence. Finally $K$ lines follow, each contains $N$ inserted numbers as the deletion sequence to be checked.

输出格式

For each deletion sequence, print in a line yes if it is indeed possible to be obtained, or no otherwise.

输入样例

5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2

输出样例

no
yes
yes
yes

Square Friends

题目描述

对于任意给定的正整数 $n$，如果通过给从 $A$ 开始的 $n$ 个连续数字每个附加 $3$ 位数字，可以得到从 $B$ 开始的 $n$ 个连续数字的平方，则称 $A$ 和 $B$ 为平方朋友。

例如，给定 $n=3$，$A=73$ 和 $B=272$ 是平方朋友，因为 $73984=272^2$，$74529=273^2$，$75076=274^2$。

现在，对于任意给定的 $n$，要求找到所有满足 $A\le MaxA$ 的平方朋友。

输入格式

每个输入文件包含一个测试用例。

每个测试用例给出两个正整数：$n$（$\le 100$）和 $MaxA$（$\le 10^6$），如题目描述中所述。

输出格式

输出所有满足 $A\le MaxA$ 的平方朋友。

每对平方朋友占一行，格式为 $A$ $B$。

如果解不唯一，按 $A$ 的非递减顺序输出；如果仍有并列，按 $B$ 的递增顺序输出。

如果没有解，输出 $NoSolution$。

输入样例

3 85

输出样例

73 272
78 281
82 288
85 293

Reorder Traversal

题目描述

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the last number of the preorder traversal sequence of the corresponding binary tree.

输入格式

Each input file contains one test case. For each case, the first line gives a positive integer $N$ ($\le 50,000$), 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 separated by a space.

输出格式

For each test case, print in one line the last number of the preorder traversal sequence of the corresponding binary tree.

输入样例

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

输出样例

5

ZOJ 问题

题目描述

对给定的字符串（只包含 ${}^{\prime }{z}^{\prime }$、${}^{\prime }{o}^{\prime }$、${}^{\prime }{j}^{\prime }$ 三种字符），判断它是否能 AC。

是否 AC 的规则如下：

1. $zoj$ 能 AC；
2. 若字符串形式为 $xzojx$，则也能 AC，其中 $x$ 可以是 $N$ 个 ${}^{\prime }{o}^{\prime }$ 或者为空；
3. 若 $azbjc$ 能 AC，则 $azbojac$ 也能 AC，其中 $a$、$b$、$c$ 为 $N$ 个 ${}^{\prime }{o}^{\prime }$ 或者为空。

输入格式

输入包含多组测试用例，每行有一个只包含 ${}^{\prime }{z}^{\prime }$、${}^{\prime }{o}^{\prime }$、${}^{\prime }{j}^{\prime }$ 三种字符的字符串，字符串长度小于等于 $1000$。

输出格式

对于给定的字符串，如果能 AC 则请输出字符串 $Accepted$，否则请输出 $WrongAnswer$。

输入样例

zoj
ozojo
ozoojoo
oozoojoooo
zooj
ozoj
ooozojoo
zojoooo

输出样例

Accepted
Accepted
Accepted
Accepted
Accepted
Accepted
Wrong Answer
Wrong Answer

继续 xxx 定律

题目描述

当$n$为$3$时，我们在验证 xxx 定律的过程中会得到一个序列$3,5,8,4,2,1$，将$3$称为关键数，$5,8,4,2$称为覆盖数。

现在输入$n$个数字$a[i]$，根据关键数与覆盖数的理论，我们只需要验证其中部分数就可以确定所有数满足 xxx 定律，输出输入的$n$个数中的关键数。

如果其中有多个关键数的话按照其输入顺序的逆序输出。

输入格式

输入数据包含多个用例，每个用例首先包含一个整数$n$，然后接下来一行有$n$个整数$a[i]$，其中：
$1\le n\le 500$, $1<a[i]\le 1000$

输出格式

请计算并输出数组$a$中包含的关键数，并按照其输入顺序的逆序输出，每个用例输出占一行。

输入样例

3
3 8 4
5
3 8 4 7 15
5
3 8 4 15 7

输出样例

3
15 7 3
7 15 3

A+B for Matrices

题目描述

This time, you are supposed to find $A+B$ where $A$ and $B$ are two matrices, and then count the number of zero rows and columns.

输入格式

The input consists of several test cases, each starts with a pair of positive integers $M$ and $N$ ($\le 10$) which are the number of rows and columns of the matrices, respectively. Then $2\ast M$ lines follow, each contains $N$ integers in $[-100,100]$, separated by a space. The first $M$ lines correspond to the elements of $A$ and the second $M$ lines to that of $B$.

The input is terminated by a zero $M$ and that case must NOT be processed.

输出格式

For each test case you should output in one line the total number of zero rows and columns of $A+B$.

输入样例

2 2
1 1
1 1
-1 -1
10 9
2 3
1 2 3
4 5 6
-1 -2 -3
-4 -5 -6
0

输出样例

1
5

最小长方形

题目描述

给定一系列二维平面点的坐标$(x,y)$，其中$x$和$y$均为整数，要求用一个最小的长方形框将所有点框在内。

长方形框的边分别平行于$x$和$y$坐标轴，点落在边上也算是被框在内。

输入格式

测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中$x$和$y$小于$2^{31}$；一对$0$坐标标志着一个测试用例的结束。

注意$(0,0)$不作为任何一个测试用例里面的点。

一个没有点的测试用例标志着整个输入的结束。

输出格式

对每个测试用例，在$1$行内输出$2$对整数，其间用一个空格隔开。

第$1$对整数是长方形框左下角的坐标，第$2$对整数是长方形框右上角的坐标。

输入样例

12 56
23 56
13 10
0 0
12 34
0 0
0 0

输出样例

12 10 23 56
12 34 12 34

最大报销额

题目描述

现有一笔经费可以报销一定额度的发票。

允许报销的发票类型包括买图书($A$类)、文具($B$类)、差旅($C$类)，要求每张发票的总额不得超过$1000$元，每张发票上，单项物品的价值不得超过$600$元。

现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

输入格式

测试输入包含若干测试用例。

每个测试用例的第$1$行包含两个正数$Q$和$N$，其中$Q$是给定的报销额度，$N$($N\le 30$)是发票张数。

随后是$N$行输入，每行的格式为：
$mTyp{e}_1:pric{e}_{1}Typ{e}_2:pric{e}_2...Typ{e}_m:pric{e}_m$
其中正整数$m$是这张发票上所开物品的件数，$Typ{e}_i$和$pric{e}_i$是第$i$项物品的种类和价值。

物品种类用一个大写英文字母表示。

当$N$为$0$时，全部输入结束，相应的结果不要输出。

输出格式

对每个测试用例输出$1$行，即可以报销的最大数额，精确到小数点后$2$位。

输入样例

200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0

输出样例

123.50
1000.00
1200.50

游船出租

题目描述

现有公园游船租赁处请你编写一个租船管理系统。

当游客租船时，管理员输入船号并按下 $S$ 键，系统开始计时；当游客还船时，管理员输入船号并按下 $E$ 键，系统结束计时。

船号为不超过 $100$ 的正整数。

当管理员将 $0$ 作为船号输入时，表示一天租船工作结束，系统应输出当天的游客租船次数和平均租船时间。

注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有租船没有还船，或者只有还船没有租船的纪录，系统应能自动忽略这种无效纪录。

输入格式

测试输入包含若干测试用例，每个测试用例为一整天的租船纪录，格式为：船号 $(1\sim 100)$ 键值 $(S$ 或 $E)$ 发生时间 $(小时:分钟)$。

每一天的纪录保证按时间递增的顺序给出。

当读到船号为 $-1$ 时，全部输入结束，相应的结果不要输出。

输出格式

对每个测试用例输出 $1$ 行，即当天的游客租船次数和平均租船时间（以分钟为单位的精确到个位的整数时间）。

输入样例

1 S 08:10
2 s 08:35
1 E 10:00
2 E 13:16
0 s 17:00
0 s 17:00
3 E 08:10
1 s 08:20
2 s 09:00
1 E 09:20
0 E 17:00
-1

输出样例

2 196
0 0
1 60