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

最长严格上升子串-AI夏令营第一批

题目描述

著名的小 P 是一个热爱旅游的人！这一天他来到了神秘的 ZYL 国度。入海关的时候他被问到了一个题目，如果答对他就可以顺利到达 ZYL 的首都 ZY 了！小 P 居然还花了 $10^{-233}$ 秒才想出来做法，实在是有点难的！于是他决定拿来考考你。

给定长度为 $n$ 的序列 $a$，保证 $a_i$ 是正整数。你需要选择一个位置 $i$ 并将 $a_i$ 修改为一个任意的整数。最大化最长严格上升子串的长度。

所谓严格上升子串，就是从序列中选出位置连续的若干个数字，满足后一个数字比前一个大（而不能相等或小于）。

如序列 $[1,4,2,3,5]$ 中，子序列 $[2,3,5]$ 就是严格上升子串，而 $[4,2,3]$（不上升）和 $[1,2,3]$（不连续）则不是。

输入格式

第一行，一个正整数 $n$，表示序列的长度。

第二行，$n$ 个正整数 $a_1,a_2,\dots ,a_n$，表示序列 $a$。

输出格式

输出一行一个整数，表示修改后，你最大化的最长严格上升子串的长度。

数据范围

对于前 $20\%$ 的数据，满足 $n\le 5$，$a_i\le 5$。

对于前 $40\%$ 的数据，满足 $n\le 10$，$a_i\le 10$。

对于前 $70\%$ 的数据，满足 $n\le 300$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le a_i\le 10^9$。

输入样例1

5
1 4 2 2 3

输出样例1

3

输入样例2

5
1 2 3 2 1

输出样例2

4

单词方阵-AI夏令营第一批

题目描述

给一个 $n\times n$ 的字母方阵，内可能蕴含多个 yizhong 单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 $8$ 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉，因此有可能共用字母。输出时，将不是单词的字母用 * 代替，以突出显示单词。

输入格式

第一行输入一个数 $n$ $(7\le n\le 100)$。

第二行开始输入 $n\times n$ 的字母矩阵。

输出格式

突出显示单词的 $n\times n$ 矩阵。

数据范围

$7\le n\le 100$

输入样例1

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

输出样例1

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

最大加权矩形-AI夏令营第一批

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长给她们一个 $n\times n$ 矩阵，要求找出最大加权矩形（即子矩阵的元素和最大）。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 $[-127,127]$。

例如，对于矩阵：

0 –2 –7  0 
 9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

在左下角：

 9   2
-4   1
-1   8

其和为 $15$。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行输入整数 $n$，接下来 $n$ 行每行 $n$ 个整数，表示矩阵。

输出格式

输出一个整数，表示最大子矩阵的和。

数据范围

$1\le n\le 120$

输入样例1

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

输出样例1

15

螺旋矩阵-AI夏令营第一批

题目描述

一个 $n$ 行 $n$ 列的螺旋矩阵可由如下方法生成：

从矩阵的左上角（第 $1$ 行第 $1$ 列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入 $1,2,3,\dots ,n^2$，便构成了一个螺旋矩阵。

4×4 的螺旋矩阵如下：

$$\left(\begin{array}{cccc}1& 2& 3& 4\\ 12& 13& 14& 5\\ 11& 16& 15& 6\\ 10& 9& 8& 7\end{array}\right)$$

现给出矩阵大小 $n$ 以及 $i$ 和 $j$，请你求出该矩阵中第 $i$ 行第 $j$ 列的数是多少。

输入格式

共一行，包含三个整数 $n$, $i$, $j$，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。

输出格式

一个整数，表示相应矩阵中第 $i$ 行第 $j$ 列的数。

数据范围

对于 $50\%$ 的数据，$1⩽n⩽100$；

对于 $100\%$ 的数据，$1⩽n⩽30,000$, $1⩽i⩽n$, $1⩽j⩽n$。

输入样例1

4 2 3

输出样例1

14

素数回文数的个数-人工智能夏令营第二批

题目描述

求 $11$ 到 $n$ 之间（包括 $n$），既是素数又是回文数的整数有多少个。

输入格式

一个大于 $11$ 小于 $10000$ 的整数 $n$。

输出格式

$11$ 到 $n$ 之间的素数回文数个数。

数据范围

$11<n<10000$

输入样例1

23

输出样例1

1

数列-人工智能夏令营第二批

题目描述

给定一个正整数 $k$（$3\le k\le 15$），把所有 $k$ 的方幂及所有有限个互不相等的 $k$ 的方幂之和构成一个递增的序列。

例如，当 $k=3$ 时，这个序列是：$$1,3,4,9,10,12,13,\dots$$（该序列实际上就是：$3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,\dots$）

请你求出这个序列的第 $N$ 项的值，用十进制数表示。

输入格式

两个由空格隔开的正整数 $k,N$（$3\le k\le 15$，$10\le N\le 1000$）。

输出格式

一个正整数。整数前不要有空格和其他符号。

数据范围

$3\le k\le 15$

$10\le N\le 1000$

输入样例1

3 100

输出样例1

981

产生数-人工智能夏令营第二批

题目描述

给出一个整数 $n$ 和 $k$ 个变换规则。

规则：一位数可变换成另一个一位数，规则的右部不能为零。

例如：$n=234$，$k=2$。有以下两个规则：

$2\to 5$
$3\to 6$
上面的整数 $234$ 经过变换后可能产生出的整数为（包括原数）:

$234$
$534$
$264$
$564$
共 $4$ 种不同的产生数。

现在给出一个整数 $n$ 和 $k$ 个规则。求出经过任意次的变换（$0$ 次或多次），能产生出多少个不同整数。仅要求输出个数。

输入格式

第一行两个整数 $n,k$，含义如题面所示。

接下来 $k$ 行，每行两个整数 $x_i,y_i$，表示每条规则。

输出格式

共一行，输出能生成的数字个数。

数据范围

$n<10^{30}$，$k\le 15$

输入样例1

234 2
2 5
3 6

输出样例1

4

神经网络-人工智能夏令营第二批

题目描述

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连。

神经元（编号为$i$）图中，$X_1\sim X_3$是信息输入渠道，$Y_1\sim Y_2$是信息输出渠道，$C_i$表示神经元目前的状态，$U_i$是阈值，可视为神经元的一个内在参数。

神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经元分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定，$C_i$服从公式（其中$n$是网络中所有神经元的数目）：

$$C_i=\left(\sum _{(j,i)\in E}{W}_{ji}{C}_j\right)-U_i$$

公式中的$W_{ji}$（可能为负值）表示连接$j$号神经元和$i$号神经元的边的权值。当$C_i$大于$0$时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为$C_i$。

如此，在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（$C_i$），要求你的程序运算出最后网络输出层的状态。

输入格式

输入文件第一行是两个整数$n$（$1\le n\le 100$）和 $p$。

接下来$n$行，每行$2$个整数，第$i+1$行是神经元 $i$ 最初状态和其阈值（$U_i$），非输入层的神经元开始时状态必然为$0$。

再下面$p$行，每行有两个整数$i,j$及一个整数$W_{ij}$，表示连接神经元$i,j$的边权值为$W_{ij}$。

输出格式

输出文件包含若干行，每行有$2$个整数，分别对应一个神经元的编号，及其最后的状态，$2$个整数间以空格分隔。

仅输出最后状态大于$0$的输出层神经元状态，并且按照编号由小到大顺序输出。

若输出层的神经元最后状态均小于等于$0$，则输出NULL。

数据范围

$1\le n\le 100$

输入样例1

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

输出样例1

3 1
4 1
5 1