2025大二转专业机考

面向大二转计算机与大数据学院（软件学院）、人工智能学院的同学。

注意事项

使用PTA考试平台，在线实时OJ，提交就会显示分数，可无限提交，取最高分。
共8题，均为编程题，满分800分。
按点给分。
不得使用除了PTA考试平台以外的任何编译器和IDE，可以使用C/C++、Java、Python进行作答。
不得携带任何材料，包括纸质资料。
题目可以看到实时通过率，题目排列并非完全按照难度，建议先通读题目再做。
参考人数：计算机类13进6，人工智能8进2，信息安全4进1，软件工程13进4，大数据4进1。

1.判断素数

第一行给定一个\(n\)（要判断的数的个数），后面连续\(n\)行每行给出一个需要判断的数

输出，如果是输出Yes，不是输出No（换行）

2.加油站

数轴上面有几个加油站，现在你要选取两个加油站之间建立一条道路，使得这条道路的长度最短，并输出有多少种方案可以实现这个要求

输入格式：

输入，给出一个\(n\)，表示加油站的数量，第二行给出\(n\)个数，表示每个加油站的位置，如（-2，3，6，5，1），需要判断最近两个加油站

之间的距离，还有有多少个这样的加油站对

输出格式

一行一个整数，表示最近之间的距离和加油站对的个数

3.开关灯

一栋酒店有\(N\)层，每一层有\(N\)间房间（\(1 \leq N \leq 9\)），现在有\(m\)次操作，你可以选取酒店中的一间房间按下开关，每个房间门牌号的第一位表示所在楼层，第三位表示所在楼层的序号。按下开关后，同一层楼灯的状态将会改变，不同层楼但同一位置的灯也将改变，求在这个过程中最多有多少灯亮着，默认初始是关闭的状态。

输入格式：

第一行输入\(N\)和\(m\)，表示酒店的层数和操作次数

下面\(m\)行，每行输入一个整数（如101，202，303……），表示开关的房间

输出格式：

一行，输出这个过程中最多有多少灯亮着

4.艾莲的化学实验

艾莲有许多药品，她想要探讨两种药品之间是否能够相溶解，如果A可以溶于B，C可以溶于A，则我们认为C也可以溶于B。

输入格式：

第一行输入\(T\)，表示有几组测试样例

第二行输入\(n\)与\(m\)，表示有\(n\)种药剂以及\(m\)种相溶关系。

下面\(m\)行，每行输入两个数，分别表示可以相溶的两种药剂编号。

下面一行，输入\(k\)，艾莲要查询的k种药剂是否可以两两相溶

下面一行给出\(k\)个数，表示查询的药剂。

输出格式：

如果每组测试样例查询的药剂都可以两两相溶，那么输出"YES"，否则输出"NO"。

5.迷宫

给定一个\(R×C\)大小的迷宫，起点在迷宫第一行的某一格，终点在最后一行的某一格，并且不同格子之间有墙壁隔开，是否可以走出这个迷宫。

输入格式：

第一行输入两个整数，分别表示\(R\)与\(C\)。

下面\(2R-1\)行，奇数行输入\(C-1\)个整数，偶数行输入\(C\)个整数，且只为0和1。

1表示g[i][j]与g[i][j+1]的格子之间有墙壁，0则相反。

输出格式：

一行，如果能走出迷宫，则输出走出迷宫要的最小步数，如果不行，则输出"No Way"

6.兄弟数

给定\(n\)个整数，其中第\(i\)个整数为\(A_i\)，兄弟数指的是在它右边第一个不小于它的数，你的目标是找出所有数的兄弟数并输出它们，如果有一个数没有兄弟数，则对应位置输出-1。

输入格式：

一行一个整数\(n\)，表示数的个数

第二行\(n\)个整数。

输出格式：

一行，输出所有数的兄弟数下标，如果不存在兄弟数，则输出-1。

7.最长子序列

给定一个长度为n的数组，并给定一个闭区间\([m,k]\)。现在你需要找出一段子序列，使得这段子序列最大值和最小值之间的差落在那个区间内并且找到满足条件的最长子序列长度。

输入格式：

第一行输入一个整数\(n,m,k\)，表示有\(n\)个数字，\(m\)为左区间，\(k\)为右区间。

第二行输入\(n\)个整数，表示数组中的元素。

输出格式：

一行，输出满足条件的最长子序列长度。

8.染色

现在有一棵tree，给定\(n\)个节点，\(m\)条边和每个节点的权重（数组A）。现在你需要做的是把这些节点全部染成黑色。但请注意，这些节点

染色是有对应代价的，第\(i\)个节点染成黑色的代价为A[i]。

（现在你可以从这些操作中选取一个：选取一个点\(i\)，将其染成黑色，消耗代价2*A[i]。）

选取一条边的两个点，分别为点\(i\)与点\(j\)，可以将\(i\)到\(j\)之间的一般性路线都染成黑色，消耗代价为A[i]+A[j]。

现在，你需要找出将这些节点全部染色成功的最低代价，且可以每个节点可以重复染色，并输出。

输入格式：

第一行两个整数\(n\)与\(m\)，表示有\(n\)个节点，\(m\)条边。

下面一行\(n\)个数（数组A），表示每个节点染色的代价。

下面\(m\)行，每行两个整数\(u\)与\(v\)，表示\(u\)和\(v\)之间有道路相连。

输出格式：

一行，输出一个整数，表示最低代价。