0518 第 11 场 小白入门赛/强者挑战赛

• 小白入门赛：https://www.lanqiao.cn/oj-contest/newbie-11/
• 强者挑战赛：https://www.lanqiao.cn/oj-contest/senior-11/
• 题解回放：https://www.bilibili.com/video/BV1JE421F7W4/

T1. 国际博物馆日【算法赛】

问题描述

$5$ 月 $18$ 日，是国际博物馆日，这是一个弘扬博物馆文化的重要日子。

博物馆不仅是知识的殿堂，更是人们心灵的驿站。通过了解博物馆，我们可以更好地认识自己的文化根源，拓宽视野，丰富知识，提升修养。博物馆藏品丰富多样，涵盖了艺术、历史、科学等各个领域，让人们可以近距离感受到历史的厚重、艺术的魅力和科学的奥秘。

现在，请你输出 museum 来表达对国际博物馆日的祝福和推广博物馆文化的期望！

输入格式

本题为填空题，无需输入即可作答。

输出格式

输出一个字符串，表达对国际博物馆日的祝福和对博物馆文化的推广期望。

T2. 最小值取余【算法赛】

问题描述

给定 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 和一个变量 $x$，初始时 $x=0$。你需要执行 $1$ 次以下操作：

• 首先，选择一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$。
• 然后，按照顺序对 $i=1,2, \ldots, n$，将 $x$ 替换为 $10 \times x+a_{p_i}$。

请问，最终可以得到的 $x$ 的最小值对 $998244353$ 取模后的余数是多少？

输入格式

第一行包含一个整数 $n$（$1\leq n \leq 10^5$），表示整数的数量。

第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1\leq a_i \leq 10^9$）。

输出格式

输出一个整数，最终可以得到的 $x$ 的最小值对 $998244353$ 取模后的余数。

样例输入

3
1 2 3

样例输出

123

样例解释

选择排列 $(1,2,3)$，操作过程如下：

• 初始时，$x=0$。
• 将 $x$ 替换为 $10x+a_1=1$，此时 $x=1$。
• 将 $x$ 替换为 $10x+a_2=12$，此时 $x=12$。
• 将 $x$ 替换为 $10x+a_3=123$，此时 $x=123$。

最终 $x=123$，对 $998244353$ 取模的余数为 $123$，为最小值。

T3. 小蓝方程【算法赛】

问题描述

小蓝是一位著名的数学家，他最近提出了一个有趣的数学方程：

$$a = n \cdot a$$

方程伴随两个整数 $X,Y$ 和两个条件：

1. $0 \leq a \leq X$。
2. $0 \leq n \leq Y$。

现在，你的任务是计算在给定的 $X$ 和 $Y$ 值的情况下有多少对 $(a, n)$ 满足上述方程和限制条件。

输入格式

第一行包含两个整数 $X$ 和 $Y$（$1\leq X,Y \leq 10^9$）。

输出格式

输出一个整数，表示满足条件的 $(a, n)$ 的对数。

样例输入

1 1

样例输出

3

样例说明

当 $X = 1$, $Y = 1$ 时，满足条件的 $(a, n)$ 对有：$(0, 0)$，$(0, 1)$，$(1, 1)$，总共有 $3$ 对符合要求。

T4. 玩偶购买【算法赛】

问题描述

蓝桥学院有两位亲密无间的姐妹，小蓝和小桥。一天，她们决定去当地的玩偶市场，为她们的衣柜增添一些乐趣。市场中的玩偶都是由优秀的巧匠精心制作，每个玩偶的大小均为 $x$，价格均为 $y$ 元。

小蓝，作为姐姐，总想给妹妹小桥带来惊喜。她决定利用手头的 $n$ 元钱，在这个的市场上为她们俩买一些玩偶，放入各自的衣柜。然而，她们的衣柜空间有限。小蓝的衣柜空间为 $a$，而小桥的衣柜空间为 $b$。

姐妹俩希望在不超过衣柜容积和预算的前提下，尽可能多地购入玩偶。同时，小蓝希望为小桥购买的玩偶数量多于自己的玩偶数量，以表达她对小桥的深深爱意。

请问，在这些条件下，她们最多能购买多少个玩偶？

输入格式

第一行包含一个整数 $T$（$1\leq T \leq 10^4$），表示有 $T$ 组数据。

接下来 $T$ 行，每行包含五个整数 $n$、$x$、$y$、$a$、$b$（$1\leq n,x,y,a,b \leq 10^9$），分别表示小蓝手头的钱数、每个玩偶的体积、价格、小蓝的衣柜空间和小桥的衣柜空间。

输出格式

对于每组测试数据，输出一行包含一个整数，表示答案。如果一个玩偶也购买不了，则输出 $-1$。

样例输入

1
3 1 1 1 1

样例输出

1

样例说明

小蓝有购买 $3$ 个玩偶的钱。

小桥的衣柜空间为 $1$，只能放入 $1$ 个玩偶。小蓝的玩偶数量要小于小桥的玩偶数量，因此小蓝的玩偶数量为 $0$。

T5. 数学魔术家【算法赛】

问题描述

小蓝被称之为数字王国的数学魔术家，他总是能将一个数字变换出不同的样子。

现在小蓝遇见了一个考验，给定一个整数 $x$​，小蓝可以从 $x$​ 中任意选择两个数字并调换它们的位置，请问在保证变换后 $x$​ 合法的情况下 $x$​ 可以变成的最大值和最小值分别是多少？

比如数字 $130$，可以变为 $310$，但不能变为 $013$，因为 $0$ 开头的数字不合法。

操作可以进行无限次。

输入格式

输入一行一个整数 $x( 1\leq x \leq 10^{100000})$。

保证 $x$ 是个合法的整数。

输出格式

输出一行两个整数分别表示 $x$ 可以变成的最大值和最小值。

输入样例

1423

输出样例

4321 1234

T6. 矿石样本分析【算法赛】

问题描述

小蓝是一位宇宙探险家。他发明了一对智能机器人，它们能够分析宇宙中各种稀有矿石的属性。

为了进一步检验机器人的能力，小蓝决定进行一项实验。

首先，小蓝会将 $n$ 颗矿石样本在桌上摆放成一排，每颗矿石都具有一个属性值 $a_i$。

接着，小蓝会给这对机器人分别输入一个数字 $X$。一旦机器人找到一颗属性值为 $X$ 的矿石，它就会立即拿起这颗矿石并返回给小蓝。如果找不到属性值为 $X$ 的矿石，机器人将空手而归。

小蓝可以在桌子的任意一端放置机器人，也就是说，他可以选择在桌子的左端放置两个机器人、在桌子的右端放置两个机器人，或者在左右两端各放置一个机器人。放置完后，机器人会同时开始工作，并按照从左往右或从右往左的顺序依次分析矿石样本的属性值。

机器人每分析一颗矿石需要 $1$ 分钟的时间。但机器人可以快速移动，因此移动的时间可以忽略不计。

小蓝想要知道，他需要等待多久才能从机器人那里得到两颗属性值不同，且和为 $K$ 的矿石。请帮助他计算出最短的等待时间（以分钟为单位）。

输入格式

第一行包含两个整数 $n$（$2\leq n\leq 2\times 10^5$） 和 $K$（$2\leq K \leq 10^9$），分别表示矿石样本的数量和目标属性之和。

接下来的一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每颗矿石的属性值。

输出格式

输出一个整数，表示小蓝从机器人那里得到两颗属性之和为 $K$ 的矿石的最短等待时间（以分钟为单位）。如果无法得到两颗属性值之和为 $K$ 的矿石，则输出 $-1$。

样例输入 1

5 7
1 3 5 2 4

样例输出 1

2

样例输入 2

4 10
6 3 8 5

样例输出 2

-1

样例说明

在样例 $1$ 中，小蓝可以将两个机器人分别放置在矿石样本的两端，第一个机器人从左往右分析矿石，第二个机器人从右往左分析矿石。然后，分别向第一个机器人输入数字 $3$，第二个机器人输入数字 $4$。第一个机器人需要 $2$ 分钟找到特性值为 $3$ 的矿石，第二个机器人需要 $1$ 分钟找到特性值为 $4$ 的矿石，因此最短等待时间为 $2$ 分钟。

在样例 $2$ 中，无论小蓝如何放置机器人，都无法得到两颗属性值之和为 $10$ 的矿石，因此输出为 $-1$。

T7. 拔苗助长【算法赛】

问题描述

蓝桥村是蓝桥王国年年的模范村，这是因为他们村的稻田每年都是优美的。

对于一块稻田来说，如果其中任意两根不同的秧苗的高度乘积均为完全平方数，该稻田被称之为优美的稻田。

蓝桥王国的稻田验收日即将到来，但现在蓝桥村还有一块插了 $N$ 根秧苗的稻田不够优美，其中第 $i$ 根秧苗的高度为 $h_i$。

作为蓝桥杯的村长，你可以发动技能拔苗助长：

• 选择一个质数 $x(2 \leq x \leq 10^6)$ ，同时将任意一株高度为 $h$ 的秧苗变为 $h \times x$。

请问你最少需要发动多少次拔苗助长才可以将该稻田变得优美。

输入格式

第一行输入一个整数 $N(1 \leq N \leq 10^5)$ 表示稻田中秧苗的数量。

第二行输入 $N$ 个整数 $h_1,h_2,h_3,\cdots,h_N(1 \leq A_i \leq 10^6)$ 表示秧苗的高度。

输出格式

输出一个整数表示答案。

输入样例

5
1 2 3 4 5

输出样例

3

T8. 皇家守卫【算法赛】

问题描述

在蓝桥王国的边疆有 $N$​ 座高塔，每座高塔上均有一个士兵，他们被称之为皇家守卫。

每座高塔均有一个高度，第 $i$ 座高塔的高度为 $h_i$。对于第 $i$ 座塔，若其右边存在某座塔 $j$，满足：

$$\max(h_i,h_{i+1},h_{i+2},\cdots,h_{j-1})<h_j$$

则称第 $j$ 座塔为第 $i$ 座塔 "暸望塔"。

现在王国传来 $Q$ 个任务，每个任务会给定两个编号 $x,y$，需要你求解第 $x$ 座高塔和 第 $y$ 座高塔的公共 "暸望塔" 数量。

$x,y$ 的公共 "暸望塔" 定义为两者同时拥有的 "暸望塔"。

输入格式

第一行输入两个整数 $N,Q(1 \leq N,Q \leq 10^5)$ 表示高塔个数和任务数。

第二行输入 $N$ 个整数 $h_1,h_2,h_3,\cdots,h_n(1\leq h_i \leq 10^9)$ 表示高塔的高度。

接下来 $Q$ 行，每行输入两个整数 $x,y( 1\le x \leq y \leq N)$ 表示一次任务询问。

输出格式

输出 $Q$ 行，每行一个整数表示答案

输入样例

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

输出样例

2
1
0

说明

对于第一个询问，第 $1$ 座高塔和第 $3$ 座高塔的公共暸望塔有 $4,5$ 号塔。

T9. 分子实验【算法赛】

问题描述

小蓝对医学研究充满了热情，他一直致力于寻找一种能够改善人类健康的特殊药物。他深知，药物的分子结构对其治疗效果至关重要，因此他决定展开一项关于药物分子排列的实验。

实验的第一步，小蓝准备了 $n$ 个不同类型的分子，编号从 $1$ 到 $n$。然后，他设计了一个包含 $k$ 个位置的直线型模拟基座，用于放置这些分子。

实验的规则简单而明确：首先，小蓝会将编号为 $1$ 的分子放置在模拟基座的任意一个位置。接着，他会按照编号 $2$ 到 $n$ 的顺序，将每个分子依次放置在与上一个分子的相邻的任意位置。如果该位置已被占据，则将新分子放置在已有分子的上层。

实验完成后，小蓝会记录模拟基座上每个位置最顶层的分子编号，如果某位置没有分子，则记为 $0$。显然，不同的放置方式可能会导致不同的顶层分子序列。

对此，小蓝想知道，在所有可能的分子放置方式中，有多少种不同的顶层分子序列可能出现。两个序列被视为不同，如果它们在至少一个位置上的分子编号不同。

请你帮助小蓝计算出不同顶层分子序列的总数，并将结果对 $998244353$ 取模。

输入格式

输入仅一行，包含两个整数 $n$ 和 $k$（$1\leq n ,k \leq 2\times 10^3$），分别表示分子的数量和模拟基座的位置数。

输出格式

输出一个整数，表示不同的顶层分子序列的数量，结果对 $998244353$ 取模。

样例输入

3 3

样例输出

6

样例说明

图片描述