1005 第 19 场 小白入门赛/强者挑战赛

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

T1. 上交文物【算法赛】

问题描述

话说小哥张起灵、吴邪和胖子盗墓归来，小哥惜字如金，只说了三个字：“上交国”。胖子一听，顿时急眼了：“啥？上交？那胖爷我下半辈子吃啥喝啥？好歹给胖爷留点养老钱啊！”

吴邪赶紧打圆场：“胖子，小哥的意思是，把文物上交给国家。咱们这次一共发现了七星鲁王宫的青铜鼎、蛇眉铜鱼、玉俑、鬼玺以及战国帛书，一共五件文物。按照规定，每件文物可以获得 $1000$ 个金币奖励，所以我们一共能获得 $5000$ 块奖金。这 $5000$ 块钱咱们三个平分！”

胖子一听，乐了：“哎！这还差不多！那胖爷我就勉为其难，同意吧！”

现在，请你计算一下，每人可以分到多少钱？

如果无法均匀分配（即结果不是整数），请将结果向下取整，即算出每人可以分到的整数金额。

输入格式

无

输出格式

输出一个整数，表示每人可以分到的钱数。

T2. 打开石门【算法赛】

问题描述

小哥和天真迷上了探索古墓，最近他们发现了一条通往西王母宫的密道，但密道入口处有一扇刻满符号的石门。 这些符号组成了一个符号串 $S$ ，符号串 $S$ 仅包含字符 $L$ 和 $Q$ 。为了打开石门，他们需要先解读门上的符号。

古籍记载，解读符号的方法如下：

1. 首先，需要在 $L$ 和 $Q$ 中选择一种字符作为“机关字符”。
2. 之后，可以多次（含 $0$ 次）选择符号串 $S$ 中任意两个相邻的“机关字符”，并将它们替换成一个“机关字符”。

举个例子，假设初始符号串为 $\text{LLQQ}$，如果你选择 $L$ 作为“机关字符”，那么你可以将两个相邻的 $L$ 替换为一个 $L$，得到 $\text{LQQ}$；如果你选择 $Q$ 作为“机关字符”，那么你可以将两个相邻的 $Q$ 替换为一个 $Q$，得到 $\text{LLQ}$。

请问，小哥和天真最终能将符号串缩短到多短呢？

输入格式

输入一行，包含一个由字符 $L$ 和 $Q$ 组成的字符串 $S$，长度介于 $1\sim 10^5$。

输出格式

输出一个整数，表示小哥和天真最终能将符号串缩短到的最小长度。

样例输入

LLLQQ

样例输出

3

样例说明

选择 $L$ 作为“机关字符”：

$$\text{LLLQQ} \rightarrow \text{LLQQ} \rightarrow \text{LQQ}$$

可将符号串的长度缩短至 $3$。

T3. 青铜门上的涂鸦【算法赛】

问题描述

闷油瓶去长白山闭关修炼了，留下吴邪一人在家百无聊赖。为了排解寂寞，吴邪决定研究研究青铜门上的涂鸦。通过观察他发现，青铜门上的涂鸦是由两种特定的符号组成：代表闷油瓶的画像 $L$ 和代表吴邪自己的画像 $Q$。

闲来无事，吴邪便开始琢磨能不能修改一下这些符号，搞点新花样出来。他的改造方法很简单：每次选取门上连续的两个符号，然后把这两个符号都变成代表他自己的画像 $Q$。

比方说，如果涂鸦是 $\text{LQL}$，那么吴邪可以选择替换前两个符号 $\text{LQ}$，得到 $\text{QQL}$；当然，他也可以选择替换后两个符号 $\text{QL}$，得到 $\text{LQQ}$。

现在，请你帮吴邪算算，在只进行一次修改操作的前提下，吴邪可以创作出多少种不同的涂鸦图案呢？

输入格式

输入一行，包含一个长度介于 $2 \sim 10^5$、仅包含字符 $L$ 和字符 $Q$ 的字符串，表示青铜门上的涂鸦图案。

输出格式

输出一行，包含一个整数，表示吴邪可以创作出的不同涂鸦图案的数量。

样例输入

LQL

样例输出

2

T4. 敲打骷髅兵【算法赛】

问题描述

在一个昏暗的地下古墓里，胖子、小哥和你正在面对一只不安分的骷髅兵，这家伙的初始生命值为 $N$。

每当你们用洛阳铲狠狠敲一下骷髅兵的脑袋，它就会消失，然后诡异地冒出两只新的骷髅兵！这两只新骷髅兵的生命值均为敲打前的骷髅兵的生命值的一半（向下取整）。例如，如果敲打前的骷髅兵的生命值为 $3$，那么敲打后就会冒出两只生命值为 $\lfloor \frac{3}{2} \rfloor = 1$ 的骷髅兵。如果敲打前的骷髅兵的生命值为 $4$，那么敲打后就会冒出两只生命值为 $\lfloor \frac{4}{2} \rfloor = 2$ 的骷髅兵。

如果敲打前的骷髅兵的生命值的一半（向下取整）为 $0$，则不会冒出新的骷髅兵。

第一次见到这场面，你吓得差点把铲子掉了！见状，胖子拍了拍你的肩膀，语气坚定地说：“伙计，敲脑袋的事就交由你胖爷来。不过，这骷髅兵可不简单！每次你敲它一下，它就会分裂出两只新的，真的是让人想哭啊！”

小哥在旁边插嘴：“是啊！也不知道要敲到什么时候！”

现在，请你计算出使初始以及后来不断冒出来的所有骷髅兵都消失所需要的最少敲打次数。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个整数 $n$ $(1 \leq n \leq 10^9)$，表示初始骷髅兵的生命值。

输出格式

对于每个测试用例，输出一行，表示使初始以及后来不断冒出来的所有骷髅兵都消失所需要的最少敲打次数。

样例输入

2
1
2

样例输出

1
3

T5. 净化王胖子【算法赛】

问题描述

吴邪和王胖子决定前往青铜古树寻找三叔的下落！

在青铜古树中，共有 $n$ 个房间排成一排。其中第 $i$ 个房间的编号为 $a_i$，两人将从编号为 $1$ 的房间开始找寻。

每个房间都有着关于三叔的线索，且这些线索之间相互关联。具体地，对于编号为 $i$（$i>1$） 的房间，只有当编号为 $[1, i-1]$ 之间的所有的房间线索都被解开时，该房间的线索才能被解开。而一旦他们获得了所有房间的线索，就能得知三叔的下落。

然而，王胖子在进入古树时不慎被怪物抓伤，伤口感染程度为 $k$。在离开之前，必须将他的感染程度成功降至 $0$，否则将会产生意想不到的后果。

由于时间紧迫，吴邪无法停下为王胖子净化，两人将仍然按照最优策略寻找线索（移动步数最少），但他可以在行动前在任意两个相邻的房间之间建立净化站点。每当他们从一个房间经过净化站点到达另一个房间时，如果王胖子的感染程度仍为正数，就会减少 $1$。

请你帮助吴邪计算出至少需要建立多少个净化站点，才能确保在离开青铜古树时将王胖子的感染程度降为 $0$。如果无法做到这一点，则输出 $-1$。

注意：在任意两个相邻房间之间最多只能建立 $1$ 个净化站点。

输入格式

第一行输入两个整数 $n,k(2 \leq n \leq 2 \times 10^5,1 \leq k \leq 10^9)$ 表示房间数量和王胖子受感染程度。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\dots,a_n(1 \leq a_i \leq n)$ 表示每个房间的编号，保证 $a$ 为一个 $1 \sim n$ 的排列。

输出格式

输出一个整数表示答案。

样例输入

5 6
1 4 3 2 5

样例输出

2

样例说明

可以在 $(4,3)$ 号房间和 $(3,2)$ 号房间之间建立净化站。

1. 从 $1$ 号房间走到 $2$ 号房间时，会经过 $2$ 个净化站，此时受感染程度降为 $4$。
2. 从 $2$ 号房间走到 $3$ 号房间时，会经过 $1$ 个净化站，此时受感染程度降为 $3$。
3. 从 $3$ 号房间走到 $4$ 号房间时，会经过 $1$ 个净化站，此时受感染程度降为 $2$。
4. 从 $4$ 号房间走到 $5$ 号房间时，会经过 $2$ 个净化站，此时受感染程度降为 $0$。

T6. 云顶天宫【算法赛】

问题描述

在云顶天宫中，吴邪和他的团队不幸陷入了裘德考设下的陷阱，被困在一个巨大的密室里。如果无法快速破解，他们将面临海猴子的攻击。

他们来到密室的石门前，门口从左到右摆放着 $n$ 根石柱，每根石柱上都放置了一个数字圆盘，圆盘可以设置一个正整数，且最大值不超过 $m$。根据石门的提示，他们知道需要将这些数字圆盘设置成一个 "完美序列"。

"完美序列" 的定义：

对于一个序列，你可以选择一个严格大于其相邻元素的元素，并执行以下操作之一：

• 从序列中删除该元素，剩余元素拼接成新序列。
• 从序列中删除该元素所有相邻元素，剩余元素拼接成新序列。

如果通过若干次操作（包括 $0$ 次），最终能使序列仅剩下一个值为 $m$ 的元素，那么这个序列就被称为完美序列。

吴邪和他的团队很快完成了这个简单的任务，但裘德考的考验并没有结束。大门还需要输入一个密码，这个密码是石柱可以设置出的 "完美序列" 的数量。

这个问题似乎难倒了吴邪和他的团队，现在请你帮助他们计算出答案。由于结果可能会非常庞大，你只需输出答案对 $998244353$ 取模后的结果。

输入格式

输入一行两个整数 $n,m(1 \leq n, m \leq 10^3)$ 表示石柱的数量和数字圆盘可设置的值域。

输出格式

输出一个整数表示答案，答案需要对 $998244353$ 取模。

样例输入

4 5

样例输出

304

样例说明

其中一种 "完美序列" 的摆放方式可能为 $[1,2,1,5]$。

1. 先选择 $2$ 然后删除其相邻元素，序列变为 $[2,5]$。
2. 选择 $5$ 然后删除其相邻元素，序列变为 $[5]$。

T7. 古墓机关【算法赛】

问题描述

闷油瓶最近又双叒叕失忆了！为了帮助闷油瓶恢复记忆，吴邪决定带他去寻找记忆碎片。

他们来到一座古墓，根据线索，想要打开通往下一层的墓门，需要破解一个机关。机关上刻着 $n$ 个数字，分别是 $1,2,3,\dots, n$。

吴邪刚想上前查看，突然机关启动，这 $n$ 个数字被复制了 $m$ 次，变成了一个长度为 $n \times m$ 的数字阵列：

$$\underbrace{(1,2,\dots, n), (1,2,\dots , n),\dots ,(1,2\dots ,n)}_{m 个 (1,2,\dots, n)}$$

机关旁边还写着一行小字：想要打开墓门，必须从这个数字阵列中选择 $n$ 个数字，使得这 $n$ 个数字按照在数字阵列中的先后顺序排列后，依次为 $1, 2, 3, \dots, n$。

“这…这该怎么选啊？”吴邪挠了挠头，向你投来了求助的目光。

现在，请你帮吴邪算出，一共有多少种不同的选取方法吗？由于答案可能很大，你只需要输出方案数对 $998244353$ 取模的结果即可。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$，表示测试用例的数量。

接下来的 $t$ 行，每行包含两个整数 $n$ 和 $m$ $(2 \leq n, m \leq 10^5)$，表示数字的数量和复制的次数。

输出格式

对于每个测试用例，输出一个整数，表示从数字阵列中选择 $n$ 个数字，使得它们依次为 $1, 2, 3, \ldots, n$ 的不同选取方法的总数对 $998244353$ 取模后的结果。

样例输入

1
2 2

样例输出

3

样例说明

在给定样例中，数字阵列为：

$$1,2,1,2$$

可选取的方案数共有 $3$ 种，分别为：

$$\textcolor{red}{1},\textcolor{red}{2},1,2$$

$$\textcolor{red}{1},2,1,\textcolor{red}{2}$$

$$1,2,\textcolor{red}{1},\textcolor{red}{2}$$

T8. 倒斗【算法赛】

问题描述

吴邪、闷油瓶、王胖子最近发现了一个巨大的古墓，于是又开始他们的老本行——“倒斗”。

由于不清楚墓内结构以及是否存在怪物，三人决定全副武装，准备了洛阳铲、指南针、炸弹等工具，总共有 $n$ 个工具。为了方便表示，他们给第 $i$ 个工具设定一个编号 $a_i$。如果两个工具相同，那么它们的编号一定相同，否则编号不同。

根据约定，三人打算按照以下规则分配工具：

• 选择两个下标 $i,j(1 \leq i < j <n)$，将区间 $[1,i]$ 的工具分配给吴邪，将区间 $[i+1,j]$ 的工具分配给闷油瓶，将区间 $[j+1,n]$ 的工具分配给王胖子。

如果某个工具能够被三人同时拥有，他们的满意度就增加 $1$。

现在，三人想知道如何分配才能使得他们的满意度最大。你无需给出具体的分配方案，只需给出可达到的最大满意度即可。

输入格式

第一行输入一个整数 $n(1 \leq n \le 2 \times 10^5)$ 表示工具的数量。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\dots,a_n(1 \leq a_i \leq 2 \times 10^5)$ 表示每个工具的编号。

输出格式

输出一个整数表示答案。

样例输入

10
1 2 1 3 1 2 3 1 2 4

样例输出

2

样例说明

一种可能的分组方式为 $[1,2,1,3]$，$[1,2,3]$，$[1,2,4]$，满意度为 $2$。

T9. 没时间了！【算法赛】

问题描述

吴邪和胖子意外掉进了一个古老的墓穴，四周阴暗潮湿，似乎随时会有机关启动，令人不寒而栗。

“快看，墙上有个古老的石碑，上面写着一段话！”胖子指着墙壁，声音颤抖。

“若想逃出这座墓，就必须求出所有满足以下条件的等差数列的个数：

1. 数列的长度（项数）为 $10^{999999999}$。
2. 首项和公差均为正整数；
3. 所有小于等于 $2n$ 的项的总和大于 $2n$。”

吴邪一边研究石碑上的文字，一边嘀咕：“这都什么跟什么啊？这墓的主人是数学家吗？”

“别闲聊了吴哥！快！告诉我满足这些条件的等差数列有多少个！没时间了！我们可能会被困在这里！”胖子焦急地说道，额头上已渗出细密的汗珠。

吴邪深吸一口气，迅速开始分析这道题目。时间在流逝，墓穴的阴影似乎在逼近…

“快，给我个答案！”胖子的声音在耳边回响。

帮帮吴邪！由于答案可能很大，你只需要求出所有满足条件的等差数列的个数对 $998244353$ 取模后的结果即可。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个整数 $n$ （$1 \leq n \leq 10^9$），其含义如题所述。

输出格式

对于每个测试用例，输出一个整数，表示所有满足条件的等差数列的个数对 $998244353$ 取模后的结果。

样例输入

2
1
2

样例输出

1
5

样例说明

当 $n = 1$ 时，满足条件的等差数列仅有 $1$ 个，为：

$$1, 2, 3,4,5,\dots$$

当 $n = 2$ 时，满足条件的等差数列为 $5$ 个，分别为：

$$\begin{aligned} &1,2,3,4,5,\dots \\\\ &1,4,7,10,13,\dots \\\\ &2,3,4,5,6,\dots \\\\ &2,4,6,8,10,\dots\\\\ &3,4,5,6,7\dots \end{aligned}$$