2025北京师范大学保研上机真题
北京师范大学夏令营保研上机真题
在线测评链接：https://pgcode.cn/problem

连续整数序列的最大长度-AI夏令营第一批

题目描述

给定一个可能包含重复数字的整数数组 $arr$（长度为 $m$），请找到最大的整数 $n$，使得数组中包含从 $0$ 到 $n-1$ 的所有整数（每个至少出现一次）。具体规则如下：

1. 数组必须包含至少一个 $0$、至少一个 $1$、……、至少一个 $n-1$。
2. 如果数组中没有 $0$，则返回 $-1$。
3. 如果数组包含 $0$ 但缺少某个中间整数，则 $n$ 为第一个缺失的整数。

输入格式

一个整数数组 $arr$，长度为 $m$（$1\le m\le 10^5$）

数组元素为整数（$-10^9\le arr[i]\le 10^9$）

输出格式

一个整数 $n$，表示从 $0$ 开始的连续整数序列的最大长度

如果数组中没有 $0$，则返回 $-1$

数据范围

• $1\le m\le 10^5$
• $-10^9\le arr[i]\le 10^9$

输入样例1

0 1 2 2 3

输出样例1

4

输入样例2

1 2 3

输出样例2

-1

输入样例3

0 0 1 4

输出样例3

2

输入样例4

0 1 1 3

输出样例4

2

传球问题-AI夏令营第一批

题目描述

$n$ 个人围成一圈，编号为 $0$ 到 $n-1$。从 $0$ 号开始传球，每次传球时，持球人可以将球传给左边或右边的人（即传给编号为 $(j-1)\%n$ 或 $(j+1)\%n$ 的人）。经过 $m$ 次传球后，球回到 $0$ 号手中的传球方式有多少种？

输入格式

一行，包含两个整数 $n$ 和 $m$（$3\le n\le 30$，$1\le m\le 30$）

输出格式

一个整数，表示经过 $m$ 次传球后，球回到 $0$ 号手中的传球方式总数

输入样例1

3 3

输出样例1

2

构造特殊偶数序列-AI夏令营第一批

题目描述

定义一个十进制整数为“特殊偶数”，当且仅当它的所有数位都由偶数数字（0, 2, 4, 6, 8）组成。现在，将所有的非负特殊偶数按升序排列，形成一个序列。任务是找出这个序列中的第 $n$ 个数。

序列起始为：$0,2,4,6,8,20,22,24,26,28,40,\dots$

输入格式

输入一个正整数 $n$ ($1\le n\le 10^{18}$)。

输出格式

输出序列中的第 $n$ 个特殊偶数。

数据范围

$1\le n\le 10^{18}$

输入样例1

5

输出样例1

8

输入样例2

6

输出样例2

20

素数分解问题-AI夏令营第一批

题目描述

找到所有不超过正整数 $m$ 的数 $k$，使得 $k$ 可以被分解为两个不同的素数 $p_1$ 和 $p_2$ 的乘积，且形式为 $k=p_1\times p_2^2$。

例如，当 $m=50$ 时：
$12=3\times 2^2$ ($p_1=3$, $p_2=2$)
$18=2\times 3^2$ ($p_1=2$, $p_2=3$)
$20=5\times 2^2$ ($p_1=5$, $p_2=2$)
$28=7\times 2^2$ ($p_1=7$, $p_2=2$)
…等等

输入格式

一个正整数 $m$ ($1\le m\le 1,000,000$)。

输出格式

所有满足条件的数 $k$，按升序排列，以空格分隔。如果没有满足条件的数，则输出空行。

数据范围

$1\le m\le 1,000,000$

输入样例1

50

输出样例1

12 18 20 28 44 45 50

统计匹配的后三位-AI夏令营第二批

题目描述

给定两个整数 $m$ 和 $n$，接下来输入 $m$ 个6位数字字符串（例如 “001234”、“342311”），以及 $n$ 个3位数字字符串。要求统计这 $m$ 个6位字符串中，有多少个字符串的后三位数字出现在 $n$ 个3位字符串中。

输入格式

第一行包含两个整数 $m$ 和 $n$。
接下来 $m$ 行，每行一个6位数字字符串。
接下来 $n$ 行，每行一个3位数字字符串。

输出格式

输出一个整数，表示满足条件的6位字符串的数量。

数据范围

$1\le m,n\le 1000$

输入样例1

5 3
123456
234567
345678
456789
567890
456
789
890

输出样例1

3

青蛙跳跃-AI夏令营第二批

题目描述

在 $n\times n$ 的方阵中，青蛙从起点 $(0,0)$ 出发，每次跳跃距离恰好为 $\sqrt{m}$，要求计算到达每个点的最少跳跃次数，无法到达则标记为 $-1$，最终返回一个 $n\times n$ 的方阵。

输入格式

输入一行，包含两个整数 $n$ 和 $m$，分别表示方阵的大小和跳跃距离的平方。

输出格式

输出一个 $n\times n$ 的方阵，表示每个点的最少跳跃次数，无法到达则输出 $-1$。

输入样例1

3 5

输出样例1

0 3 2
3 -1 1
2 1 4

最大礼物数量-AI夏令营第二批

题目描述

给定 $n$ 个礼物下标和一个距离 $m$，求所有长度为 $m$ 的滑动窗口 $[x,x+m)$ 内能获得的最大礼物数量。

注意：礼物下标是递增的，且窗口是左闭右开区间 $[x,x+m)$。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示礼物数量和窗口长度。
第二行包含 $n$ 个递增的整数，表示每个礼物的下标。

输出格式

输出一个整数，表示所有滑动窗口内能获得的最大礼物数量。

输入样例1

5 4
1 3 5 10 9

输出样例1

2

圆周路径-AI夏令营第二批

题目描述

给定平面上的 $n$ 个圆，以及起点 $(x_s,y_s)$ 和终点 $(x_t,y_t)$。起点和终点均位于至少一个圆的圆周上。判断是否存在一条从起点到终点的路径，路径要求仅通过圆的圆周（即只能在圆的边界上移动，且只能在两圆相交或相切时切换圆）。

输入格式

第一行一个整数 $n$（$1\le n\le 3000$），表示圆的个数。
第二行四个整数 $x_s,y_s,x_t,y_t$，表示起点和终点的坐标。
接下来 $n$ 行，每行三个整数 $x_i,y_i,r_i$，表示第 $i$ 个圆的圆心坐标和半径。

输出格式

如果存在这样的路径，输出 “Yes”，否则输出 “No”。

数据范围

$1\le n\le 3000$
所有坐标和半径均为整数，且绝对值不超过 $10000$。

输入样例1

3
0 -2 3 3
1 0 2
2 2 2
3 3 2

输出样例1

Yes

旅行商问题

题目描述

一个飞船必须访问n个城市，至少访问每个城市一次，并最终回到出发城市。

此题不完整，仅供参考

输入样例1

输出样例1