0713 第 14 场 小白入门赛/强者挑战赛

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

T1. 银色情人节【算法赛】

问题描述

七月的阳光炽热灿烂，智慧的火花闪耀天际。7.14 银色情人节，是传递爱意的美好时光。

分享甜蜜，珍藏浪漫。正是彼此的真心相伴，才有了我们温馨美满的情感。

让我们用心感受爱情的美好，开启浪漫的甜蜜之旅，用真情温暖心灵，用爱书写未来。

对此，请你输出 7.14，共享甜蜜时刻！

输入格式

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

输出格式

输出一个字符串，共享甜蜜时刻。

T2. 书籍标签【算法赛】

问题描述

小蓝，一位热爱阅读的青年，常常沉浸在书的世界里。

这天在他逛书店的时候，发现书店里的每一类书籍都有一定的库存数量，而且部分书籍还被贴上了特别的标签。这些标签往往是一些负面评价，比如“印刷存在错误”或者“页码混乱”等等。

小蓝仔细观察了每个书架，并记录下了每类书籍的库存总数以及被贴特别标签的数量。现在，他需要你的帮助来分析这些数据，找出哪一类书籍被贴上特别标签的比例最低，即从该类书籍中随机选择一本时，拿到带有特别标签书籍的概率最小。

输入格式

输入的第一行包含一个整数 $N$ （$1 \leq N \leq 10^5$），表示书籍的类别数量。

接下来的 $N$ 行，每行包含两个整数 $t_i$ 和 $p_i$ （$1 \leq p_i \leq t_i \leq 100$），分别表示第 $i$ 类书籍的库存总数和被贴特别标签的数量。

输出格式

输出一个整数，表示被贴特别标签比例最低的书籍类别的索引（索引从 $1$ 开始）。如果有多个答案，则输出索引值最小的那个。

样例输入

3
20 5
30 8
40 10

样例输出

1

样例说明

第 $1$ 类书籍和第 $3$ 类书籍被贴上特别标签的比例最低，为 $25\%$ 。由于 $1$ 索引值更小，因此输出 $1$ 。

T3. 帕鲁服务器崩坏【算法赛】

问题描述

“那个帕鲁我已经观察你很久了，我对你是有些失望的，进了这个营地，不是把事情做好就可以的，你需要有体系化思考的能力。”

《幻兽帕鲁》火遍全网，成为了一款现象级游戏。

猫猫作为顶级帕鲁自然是首当其冲搭好了游戏私服，叫上好兄弟开始了愉快私服开荒。

但是这个游戏好玩归好玩，服务器有一堆 bug。比如说众所周知的内存泄漏问题。猫猫很无奈，写了一个脚本去检测服务器的内存占用问题，当超过一定数值就自杀。

但是问题又来了，服务器自杀了之后还要猫猫亲自去手动重启，配置守护进程的诸多方法都不适合。

最终，猫猫决定一分钟监听一次服务器端口是否正常放通。并记录下日志。

具体如下：脚本每隔一分钟监听一次服务端口是否正常，如果服务没有正常运行，则输出 1 并重启服务，否则输出 0。

现在日志形如一段 $01$ 字符串，$0$ 代表正常运行，$1$ 代表端口关闭。在定时任务监听中遇到端口关闭时会自动重启一次服务器。

现在拿到日志之后，猫猫想知道 $[l,r)$ 区间内到底有多少次重启成功。（$l$ 为起点时刻，$r$ 为终点时刻。）

注：重启成功为服务从端口关闭状态转换为端口正常运行状态。如果日志的最后一分钟为 $1$，那么你可以视作最后一分钟为重启失败。

输入格式

第一行输入一个正整数 $n$。$(1\le n\le 2\times 10^5)$

第二行输入一个长度为 $n$ 的 $01$ 字符串 $S$。$(|S|=n,s_i \in {\lbrace 0,1 \rbrace},1\le i\le n)$。

第三行输入一个正整数 $m$。$(1\le m\le 2\times 10^5)$

接下来 $m$ 行，每行输入两个正整数 $l,r$，表示区间 $[l,r)$。$(1\le l< r\le n+1)$。

输出数据

输出 $m$ 行，表示对于 $m$ 次查询的结果。

样例输入

5
10110
4
1 2
1 3
2 4
2 5

样例输出

1
1
0
1

说明

对于第 $1$ 分钟，在重启后第 $2$ 分钟变成 $0$，说明第 $1$ 分钟重启成功。

对于第 $3$ 分钟，在重启后第 $4$ 分钟依旧是 $1$，说明第 $3$ 分钟重启失败。

对于第 $4$ 分钟，在重启后第 $5$ 分钟变成 $0$，说明第 $4$ 分钟重启成功。

T4. 能力爆表【算法赛】

问题描述

给定一个长度为 $N$ 的序列，每个位置 $i$ 上有一个能力值要求 $V_i$。

你初始时位于位置 $1$，并且初始能力值为 $V_1$。你可以通过向后移动一步来到达位置 $i+1$。在移动过程中，你必须保证你的当前能力值大于等于即将到达位置的能力值要求 $V_{i+1}$。在每个位置 $i$ ，你可以提供一次花费 $A_i$ 来提升你的能力值 $B_i$。对于每个位置，提升操作只能使用一次。

你的目标是从位置 $1$ 移动到位置 $N$，求使得你能够到达位置 $N$ 的最小花费。如果无法到达位置 $N$，输出 $-1$。

你只能从位置 $i$ 移动到位置 $i+1$，不可以跳跃。

输入格式

第一行包含一个整数 $N$，表示序列的长度。$(1\le N\le1000)$

第二行包含 $N$ 个整数 $V_1, V_2, \ldots, V_N$，表示每个位置的能力值要求。$(0\le V_i\le 1000,1\le i\le N)$

第三行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，表示每个位置提升能力值的花费。$(1\le A_i\le 10^9,1\le i\le N)$

第四行包含 $N$ 个整数 $B_1, B_2, \ldots, B_N$，表示每个位置可提升的能力值。$(1\le B_i\le 1000,1\le i\le N)$

输出格式

输出一个整数，表示从位置 $1$ 到位置 $N$ 的最小花费， 若不可达，输出 $-1$。

样例输入

5
3 2 4 5 1
2 4 3 1 5
3 5 4 2 8

样例输出

2

说明

以下是从位置 $1$ 到位置 $N$ 的一种最优方案：

• 在位置 $1$ 花费 $2$ 点 提升当前能力值为 $6$。

T5. 9 面数字墙【算法赛】

问题描述

在隐秘的角落里，你发现了 $9$ 面奇怪的数字墙。这些数字墙从左到右排成一排，其中第 $i$ 面墙的编号为 $i$。

当你仔细观察这些墙时，你发现，每面墙上都可刻有一个数字，分别记为 $c_1, c_2,\dots, c_9$，其意义为：编号为 $1$ 的墙后藏着 $c_1$ 个数字 $1$，编号为 $2$ 的墙后藏着 $c_2$ 个数字 $2$，以此类推，编号为 $9$ 的墙后藏着 $c_9$ 个数字 $9$。

现在，你的任务是把这些数字重新排列，形成一个整数 $X$，并计算所有可能的 $X$ 的和。这个任务看似简单，但结果可能会非常巨大，因此你需要对 $998244353$ 取余数以得到最终答案。

输入格式

输入仅一行，包含 $9$ 个整数 $c_1, c_2, ..., c_9$（$1\leq c_i \leq 10^5$，且 $\sum_{i=1}^9 c_i \leq 10^5$），分别表示数字 $1$ 到 $9$ 的数量。

输出格式

输出一个整数，表示所有可能的 $X$ 的和对 $998244353$ 取余的结果。

样例输入 1

1 1 0 0 0 0 0 0 0

样例输出 1

33

样例输入 2

2 1 0 0 0 0 0 0 0

样例输出 2

444

样例解释

可能的 $X$ 有 $12, 21$，它们的和为 $33$，对 $998244353$ 取余为 $33$。

T6. 字串截取【算法赛】

问题描述

给定一个数字字符串，你需要从该字符串中找出满足条件的连续子数字对的数量。这里所说的连续子数字是指数字字符串截去任意长度的前缀和后缀（可以为零）得到的剩余数字表示，截取出的剩余数字不能有前导 $0$。

例如，对于数字字符串 $1234567$，其中一个合法的连续子数字是 $456$，但 $124$ 和 $235$ 都不合法。

现在的任务是找到两个不重叠的连续子数字，使得这两个连续子数字满足以下条件：

• 子数字 $1$ 是子数字 $2$ 的逆序。

然后求出满足条件的连续子数字对的数量。

输入格式

第一行输入一个正整数 $n$，表示字符串的长度。$(1\le n\le 5\times 10^3)$

第二行输入一个字符串 $s$。$(|s|=n,1\le i\le n,s_i\in \lbrace 0,1,...,8,9\rbrace)$

输入数据不包含前导 $0$。

输出格式

输出一个整数，为满足条件的连续子数字对的数量。

样例输入 1

4
1001

样例输出 2

1

样例输入 2

8
12100121

样例输出 2

10

说明

对于样例 $1$：只有 $s_1$ 与 $s_4$ 是逆序关系。

对于样例 $2$：$s_1,s_3,s_6,s_8$ 共形成 $6$ 对逆序关系，$s_2,s_7$ 形成 $1$ 对逆序关系，$s_{1\sim 2},s_{7\sim 8}$ 形成 $1$ 对逆序关系，$s_{2\sim 3},s_{6\sim7}$ 形成 $1$ 对逆序关系，$s_{1\sim 3},s_{6\sim8}$ 形成 $1$ 对逆序关系。共计 $10$ 对。

T7. 字符串博弈游戏【算法赛】

问题描述

给定两个字符串 $s_1$ 和 $s_2$，小红和小蓝可以轮流对字符串 $s_1$ 进行操作。每次他们可以从以下两种操作中任选一种：

• 将字符串 $s_1$ 进行翻转。

• 将当前字符串 $s_1$ 的最后一位删除。

现在小红希望字符串从 $s_1$ 变成 $s_2$，而小蓝不希望字符串 $s_1$ 能够变成 $s_2$。由小红先手，在两人均采取最优策略的前提下，如果小红的目的可以达到，则输出 red；反之，如果小蓝的目的可以达到，则输出 blue。

输入格式

第一行输入一个正整数 $t$，表示测试用例组数。（$1\le t\le 10^4$）。

对于每组测试数据：

第一行输入两个正整数 $n,m$，表示字符串 $s_1,s_2$ 的长度。（$1\le n,m\le 10^5$）。

第二行输入字符串 $s_1$。

第三行输入字符串 $s_2$。

数据保证 $1\le \sum_{i=1}^{t}n_i\le 10^5,1\le \sum_{i=1}^{t}m_i\le 10^5$。且字符串 $s_1,s_2$ 所有字符均为小写字母。

输出格式

对于每组测试数据：

在二人已最优策略进行操作的前提下，如果小红的目的可以达到，则输出 red，反之，如果小蓝的目的可以达到，则输出 blue。

样例输入

3
3 5
abc
abbbc
1 1
a
a
5 1
aabaa
b

样例输出

blue
red
blue

说明

对于第一组测试数据：$|s1|<|s2|$，小红一定不可能成功。

对于第二组测试数据：$s_1=s_2$，小红成功。

对于第三组数据：小蓝可以使得翻转操作进入一个循环状态，使得小红无论如何都得不到 $s_2$。

T8. 涂涂画画【算法赛】

问题描述

小蓝和小桥在学校里上美术课，老师正在教他们画正多边形。

小蓝突发奇想，给每个正多边形的边涂上了不同的颜色，并保证正多边形每条边的颜色互不相同。

小桥看见了，非常好奇，如果给 $n$ 个完全相同的正 $m$ 边形的每条边涂上颜色，并且任意两个正 $m$ 边形经过旋转也不会重合，至少需要多少种不同的颜料呢？

重合指的是两个正 $m$ 边形在二维平面上重叠，对应重合的 $m$ 条边中至少有一条颜色不一致。

输入格式

第一行输入一个正整数 $t$，表示测试用例组数。$(1\le t\le 10)$

对于每组测试数据：

输入一行，为 $2$ 个正整数 $n,m$。$(1\leq n \leq 10^9,3\le m\le 10^9)$

输出格式

对于每组测试数据：

输出一行，为至少需要的不同颜色数。

样例输入

2
2 4
3333 7

样例输出

4
8

说明

对于测试样例 $1$：

图片描述

对于样例，我们最少只需要四种颜色即可保证两个正四边形任意旋转不完全重合。

T9. 二维扫雷【算法赛】

问题描述

扫雷是一款经典游戏，如果一个格子是地雷，则其周围九宫格中数字均会增加 $1$，表示该位置有一颗地雷。

图片描述

现在给定一个 $n\times m$ 的矩阵 $A$，$A_{i,j}$ 表示的是该格子周围的 $8$ 个格子及自身有多少个地雷，你需要求出该矩阵中一共有多少个地雷。

输入格式

第一行输入两个正整数 $n,m$。$(2\le n,m\le 500)$

接下来 $n$ 行，每行输入 $m$ 个正整数，表示 $A_{i,j}$。$(0\le A_{i,j}\le 9,1\le i\le n,1\le j\le m)$。

保证数据合法且有唯一解。

输出格式

输出一个正整数，表示地雷数量。

样例输入

3 3
1 2 2
1 2 2
1 2 2

样例输出

2