2024 婺城区信息素养大赛 题面／测试数据／标程

压缩包（未改动，包含题面、测试数据、标程、测评配置）：2024婺城区信息素养大赛.rar

题面、测试数据已上传洛谷，根据《洛谷主题库题目规范》进行了一些格式修改，标签为主观判断。

以下为题面（同步于洛谷）：

T1

学生分组

题目描述

学校里有 $n$ 个学生，其中 $n$ 一定是偶数。每个学生有一定的编程能力，第 $i$ 个学生的能力是 $a_i$。

学校里的老师希望把学生组成 $\frac{n}{2}$ 个队伍，每个队伍里面有 $2$ 个学生，每个学生只能属于一个队伍。两个学生可以组队，当且仅当他们的能力是相同的，否则他们就不能理解对方。

由于开始的时候，学生的能力参差不齐，可能无法顺利组队。但是学生可以通过做题来提高自己的能力，每做一题，能力就可以提高 $1$。

学校的老师希望计算出这些学生最少需要做多少题，才能顺利的组队。

输入格式

输入的第一行是一个正整数 $n$，表示学生的数量，保证 $n$ 一定是偶数。

接下来一行有 $n$ 个正整数，第 $i$ 个整数表示第 $i$ 个学生当前的编程能力。

输出格式

输出只有一行一个整数，表示所有学生最少需要做的总题数，才能使得顺利组队。

样例 #1

样例输入 #1

6
5 10 2 3 14 5

样例输出 #1

5

样例 #2

样例输入 #2

2
1 100

样例输出 #2

99

提示

【样例解释】

在第一个样例中，第 3 个人和第 4 个人组队，第 1 个人和第 6 个人组队，第 2 个人和第 5 个人组队，然后第 3 个人做 1 题，第 2 个人做 4 题，总共做 5 题，他们就能顺利组队了。

在第二个样例中，由于只有 2 个人，所以组队方案只有 1 种，第 1 个人需要做 99 题才能组队。

【数据范围】

对于 $50\%$ 的数据，$1 \le n \le 1000$，所有学生的能力最多只有 2 种不同的取值。

对于 $100\%$ 的数据，$1 \le n \le 100000$，$1 \le a_i \le 100$。

T2

交换游戏

题目描述

为了新班级的凝聚力，让每个同学尽快熟悉彼此。班主任老师决定组织 $N$ 个同学在操场上进行游戏活动。老师要求这 $N$ 个同学站成一排，编号为 $1 \dots N$ 。然后给每个同学发了一张白纸，纸上每个同学自己都写下了一个小写英文字母（可能会有同学的字母重复）。

但是同学们开始排队的时候，都喜欢跟自己熟悉的同学排在一起。老师觉得这样不利于大家熟悉彼此。所以他决定，选出一对同学，让他们俩交换位置。

老师想知道，交换后，从 $1$ 到 $N$ 个人手上的字母序列排成的字符串有多少种。聪明的你来帮助老师完成这个任务！

输入格式

一行，一个字符串 $S$，表示初始 $1$ 到 $N$ 个同学手上的字母的序列。

输出格式

从最初的 $N$ 个人序列，交换两个人后会有多少种不同的字符串。

样例 #1

样例输入 #1

abc

样例输出 #1

3

样例 #2

样例输入 #2

bbbbb

样例输出 #2

1

提示

【样例说明】

对于样例 1，交换 $(1,2)$ 构成 bac，交换 $(1,3)$ 构成 cba，交换 $(2,3)$ 构成 acb，所以答案是 $3$。交换任意的两个人得到的字符串都是一样的，因此只有以一种答案。

对于样例 2，交换任意的两个人得到的字符串都是一样的，因此只有以一种答案。

【数据范围】

对于 $10\%$ 的数据，所有字母都相同。

对于 $40\%$ 的数据，$2 \le n \le 1000$。

对于 $100\%$ 的数据，$2 \le n \le 1000000$。

T3

连续质数和

题目描述

质数又称为素数，是大于 $1$ 的正整数，除了 $1$ 和它本身外不能被其他自然数整除，有无限个。比如，$2$、$3$、$5$、$7$ 等都是质数，但 $9$ 就不是质数，因为它能被 $3$ 整除。

数学老师最近对某些整数非常感兴趣，因为他发现有这些数能通过连续的质数相加得到。比如 $53$ 可以由 $5$、$7$、$11$、$13$、$17$ 相加得到，$5+7+11+13+17=53$。有时相加的方案还不止一种，比如 $41$ 就有 $3$ 种不同的连续质数相加方案：$2+3+5+7+11+13=41$，$11+13+17=41$，$\textbf{41=41}$。

但是也有的数没有这样的相加方案，比如$20$就找不到连续质数和相加的方案，虽然 $3+17=20$ 或 $3+5+5+7=20$ ，但前者没有连续，后者质数重复相加了。

数学老师在纸上下了 $N$ 个数，他想知道每个整数 $M_i$ 到底有多少种连续质数相加的方案，请你编程帮他一下吧。

输入格式

第一行一个整数 $N$，表示有 $N$ 个整数。

第二行到第 $N+1$ 行，第 $i+1$ 行一个整数 $Mi$。

输出格式

输出共 $N$ 行，第 $i$ 行表示整数 $M_i$ 有多少种连续质数相加的方案。

样例 #1

样例输入 #1

4
2
12
17
20

样例输出 #1

1
1
2
0

提示

【样例解释】

样例中有 $4$ 个整数，分别是 $2$，$12$，$17$ 和 $20$。

因为 $2=2$，所以 $2$ 有 $1$ 种方案。

因为 $5+7=12$，所以 $12$ 有 $1$ 种方案。

因为 $2+3+5+7=17$，$17=17$，所以 $17$ 有 $2$ 种方案。

$20$ 没有满足条件的额方案，所以输出 $0$。

【数据范围】

对于 $30\%$ 的数据：$1 \le N \le 100$，$2 \le M_i \le 100$。

对于 $50\%$ 的数据，$1 \le N \le 1000$，$2 \le M_i \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$2 \le M_i \le 10^5$。

T4

魔幻地图

题目描述

老师在求学期间，除了修炼魔法课，还开发了一种能创造虚拟的魔幻地图的技能。在不同的地图中，大家可以进行不同的闯关游戏，深受大家的喜爱。这天，经历了一整天疲惫的学习之后，魔幻之旅又开始了。

首先，老师将将游玩者移送至图中的出发点。地图可以看成是一个的网格。从上到下，从左到右，编号都为 $1 \dots N$。其中：

• 位于最左上角的网格 $(1,1)$，就是游玩者的出发点。
• 位于最右下角的网格 $(N,N)$，就是游玩者的结束点。

在魔幻地图中，游玩者会被赋予魔法能力，但是使用魔法需要消耗元气值。初始时，游玩者的元气值为 $0$。游玩者的目标是尽早地到达结束点。

游玩者在位置 $(i,j)$ 时，每一秒，他都有三种选择：

• 停留在原地，则恢复元气值 $a_{i,j}$；
• 使用魔法，消耗 $b_{i,j}$ 元气值，则可以移动到 $(i,j+1)$；
• 使用魔法，消耗 $c_{i,j}$ 元气值，则可以移动到 $(i+1,j)$；

老师还规定，任何时刻，在魔幻地图内游玩者的元气值不能低于 $0$。老师需要大家来帮忙计算出从出发点到结束点所需的最少时间，第一个计算出的同学可以优先进入魔幻地图体验。

输入格式

第一行，一个整数 $N$。接下来 $N$ 行 $N$ 列的数组，其中 $a_{i,j}$ 表示在地图的 $(i,j)$ 处每秒钟能恢复的元气值：

$$\begin{matrix} a_{1,1} & a_{1,2} & \dots & a_{1,N} \\ a_{2,1} & a_{2,2} & \dots & a_{2,N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N,1} & a_{N,2} & \dots & a_{N,N} \end{matrix}$$

接下来 $N$ 行 $N-1$ 列的数组，其中 $b_{i,j}$ 表示从 $(i,j)$ 移动到 $(i,j+1)$ 需要消耗的元气值：

$$\begin{matrix} b_{1,1} & b_{1,2} & \dots & b_{1,N-1} \\ b_{2,1} & b_{2,2} & \dots & b_{2,N-1} \\ \vdots & \vdots & \ddots & \vdots \\ b_{N,1} & b_{N,2} & \dots & b_{N,N-1} \end{matrix}$$

接下来 $N-1$ 行 $N$ 列的数组，其中 $c_{i,j}$ 表示从 $(i,j)$ 移动到 $(i+1,j)$ 需要消耗的元气值：

$$\begin{matrix} c_{1,1} & c_{1,2} & \dots & c_{1,N} \\ c_{2,1} & c_{2,2} & \dots & c_{2,N} \\ \vdots & \vdots & \ddots & \vdots \\ c_{N-1,1} & c_{N-1,2} & \dots & c_{N-1,N} \end{matrix}$$

输出格式

计算游玩者到达结束点所需的最少时间。

样例 #1

样例输入 #1

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

样例输出 #1

8

提示

【样例1解释】

• 停留在 $(1,1)$ 处 $1$ 秒，当前元气值为 $1$；
• 消耗 $1$ 点元气值，移至 $(2,1)$, 当前总用时 $2$ 秒，当前剩余元气值为 $0$；
• 停留在 $(2,1)$ 处 $3$ 秒，当前总用时 $5$ 秒，当前元气值为 $9$；
• 消耗 $4$ 点元气值，移至 $(2,2)$，当前总用时 $6$ 秒，当前剩余元气值为 $5$；
• 消耗 $3$ 点元气值，移至 $(3,2)$，当前总用时 $7$ 秒，当前剩余元气值为 $2$；
• 消耗 $2$ 点元气值，移至 $(3,3)$，当前总用时 $8$ 秒，当前剩余元气值为 $0$；

可能存在其他的移动方案，但是可以证明用时 $8$ 秒是最少需要的时间。

【数据范围】

对于 $10\%$ 的数据，数组 $a$，数组 $b$，数组 $c$ 的数值均相等。

对于 $100\%$ 的数据，数组 $a$，数组 $b$，数组 $c$ 的数值范围为：$[1,10^9]$

对于 $100\%$ 的数据，$2 \le N \le 80$。