0504 第 10 场 小白入门赛/强者挑战赛

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

T1. 五一礼物【算法赛】

问题描述

五月的阳光温暖明媚，劳动者的汗水闪耀着光芒。五一劳动节，是属于每一位辛勤劳动者的节日。

劳动创造价值，奋斗成就梦想。正是无数劳动者的辛勤付出，才有了我们今天的美好生活。让我们怀着感恩的心，向每一位劳动者致敬，感谢他们的辛勤付出和无私奉献。

为了庆祝这个属于劳动者的节日，蓝桥云课特别准备了一份礼物，希望能够带给每一位劳动者、参赛者快乐和祝福。

请你输出 51，领取这份礼物！

输入格式

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

输出格式

输出一个字符串，领取礼物。

T2. 合成贤者之石【算法赛】

问题描述

炼金术士小蓝毕生梦想是合成贤者之石。

合成贤者之石需三种水晶：红水晶、蓝水晶以及黄水晶。红水晶能量最强，蓝水晶次之，黄水晶最弱。

对此，小蓝准备了 $n$ 个坩埚来合成贤者之石，第 $i$ 个坩埚最多容纳 $a_i$ 颗水晶。为保证能量平衡，每个坩埚需满足：

• 若坩埚中有红水晶，则红水晶数量 < 蓝水晶数量 < 黄水晶数量。
• 若坩埚中没有红水晶，但有蓝水晶，则蓝水晶数量 < 黄水晶数量。
• 若坩埚中只有黄水晶，则无需满足任何条件。

在合成关键时刻，嫉妒小蓝的黑魔法师小桥，向每个坩埚中放入了若干蓝水晶和黄水晶试图破坏平衡。小桥并不知道能量配比规则，只是随意放入了一些，且蓝水晶数量 < 黄水晶数量，蓝水晶数量 + 黄水晶数量 $\leq$ 坩埚的容量。

现在，小蓝需尽快调整水晶数量以确保能力平衡。请问，在所有可能的情况中，他最多能向这 $n$ 个坩埚中放入多少颗红水晶？

输入格式

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

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i \leq 10^5$），其中 $a_i$ 表示第 $i$ 个坩埚的容量。

输出格式

输出一个整数，表示在所有可能的情况中，小蓝最多能向这 $n$ 个坩埚中放入的红水晶数量。

样例输入

3
1 1 6

样例输出

1

样例说明

无论如何，小蓝也无法想第 $1$、$2$ 个坩埚中放入红水晶。

对于 $3$ 个坩埚，最优情况为：小桥向第 $3$ 个坩埚中放入了 $3$ 个黄水晶、$2$ 个蓝水晶，此时，小蓝可以向其放入 $1$ 个红水晶。

T3. 咒语融合【算法赛】

问题描述

一场盛大的魔法比赛即将举行。

小蓝，是一位初出茅庐却天赋异禀的法师。为了在比赛中脱颖而出，他翻遍了图书馆中所有积满灰尘的魔法书，终于找到了一种失传已久的组合魔法。这种魔法需要将两个基础咒语融合，从而创造出威力强大的全新咒语。

每个基础咒语都对应着一个神秘的数字，当两个咒语融合时，它们的数字会相加，得到新咒语的威力值。然而，魔法世界总是充满了奇奇怪怪的规则。如果两个咒语在相同数位上有相同的数字，那么新咒语的威力就会受到削弱，需要减去这些数字。

例如，如果小蓝选择的咒语是 $345$ 和 $543$，那么新咒语的威力值最初为 $345 + 543 = 888$。但是，由于 $345$ 和 $543$ 在十位上都有数字 $4$，因此新咒语的威力值需要减去 $4$，最终变为 $884$。

魔法书中记载了 $n$ 个咒语，分别用 $\lbrace a_1, a_2, \dots a_n\rbrace$ 表示。小蓝可以从中任意选择两个咒语进行组合。

请问，小蓝能组合出的咒语的最大威力是多少？

输入格式

第一行包含一个整数 $n$（$2\leq n \leq 10^5$），表示魔法书中基础咒语的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i \leq 10^5$），表示每个基础咒语对应的数字。

输出格式

输出一个整数，表示小蓝能够组合出的咒语的最大威力值。

样例输入

3
9 9 8

样例输出

17

T4. Yaya 与加减法【算法赛】

问题描述

在小学二年级的数学课上， Yaya 学会了加减法。出于对学到新知识的兴奋，她迫不及待地想要 Clrlss 考一考她。

于是，Clrlss 给了 Yaya 一个序列。这个序列一共有 $n$ 个整数，分别为 $a_{1},a_{2},...,a_{n}$ 。 除此之外， Clrlss 还给了 Yaya $A$ 个加号和 $B$ 个减号。Clrlss 问：在这些加号和减号中选出 $n-1$ 个，填到序列中，会形成一个数学表达式。那么，这个表达式的最大值是多少？

具体而言，对于表达式 $(a_1) op_1 (a_2) op_2 (a_3)...op_{n-1}(a_n)$ ，Yaya 需要在 $op_1$ 到 $op_{n-1}$ 这 $n-1$ 个位置上填入加号或者减号，加号总数不超过$A$，减号总数不超过$B$，且让表达式的值最大。

亲爱的见证者啊，这种题目对您来说肯定不在话下。至于 Yaya， 让我们祝她算得出来。

输入格式

第一行输入三个整数 $n,A,B$ （$1 \le A,B \le n \le 10^5 , A+B \ge n-1$），分别表示序列的长度、加号的数量和减号的数量。

第二行输入 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ , 表示给定的序列 ($-10^9 \le a_i \le 10^9$)。

输出格式

输出一个整数，表示可以形成的表达式的最大值。

样例输入

5 4 2
1 -3 -5 -4 1

样例输出

8

说明

对于样例，我们有 $4$ 个加号，$2$ 个减号。取到最大值 $8$ 时，表达式可以为 $1 + (-3) - (-5) - (-4) + 1$ 。

T5. Yaya 与字符画【算法赛】

问题描述

初中时， Yaya 接触到了除了玩游戏之外的电脑操作。作为一个喜欢画画的女孩子，她觉得字符画是一个非常美妙的发明：利用为数不多的字符种类，通过各式各样的排列与组合，能够创造出赏心悦目的画境。

这一天，Yaya 微笑着找到 Clrlss ，说给他画了一幅字符画。 这幅画由一个 $n$ 行 $m$ 列的矩形组成，其中每个字符都是星号 * 或者点号 . 。 由于艺术细胞的缺失， Clrlss 没能欣赏到字符画的美，而是在思考另外一个问题：在这幅字符画中，最大的 $V$ 字形的大小是多少？

$V$字形定义为： 一个星号 * 向左上、右上四十五度引出两条由相同个数的星号 * 构成的斜线。$V$ 字形的大小定义为一条斜线上星号的个数（不算最底下、两边共有的这一个星号）。

亲爱的见证者啊，这种题目对您来说肯定不在话下。至于 Yaya， 让我们祝她画得开心。

输入格式

第一行输入两个整数 $n,m$ （$1 \le n,m \le 2000$） ，表示字符画的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，都是星号 * 或者点号 . ，描绘一幅字符画。

输出格式

一行一个整数，表示最大的 $V$ 字形的大小。

样例输入

6 6
***..*
.*....
*...*.
.*.*..
..*...
..*.*.

样例输出

2

T6. Yaya 与游戏【算法赛】

问题描述

到了高中，Yaya 和 Clrlss 被分到了隔壁班。然而，他们仍旧总是在一起玩游戏。虽然，游戏的结果通常是 Clrlss 获胜，但这并没有打消 Yaya 的积极心。

果然，到了这一天，Yaya 又找到了 Clrlss ，想玩一个新的游戏。游戏的规则是这样的：

Clrlss 和 Yaya 各自带领了一支队伍进行比拼。Clrlss 一共有 $X$ 元钱 , 他的队内有 $n$ 个人，第 $i$ 个人有 $a_i$ 元钱； Yaya 一共有 $Y$ 元钱 , 她的队内有 $m$ 个人，第 $i$ 个人有 $b_i$ 元钱。

有无穷多个商店排成一排，编号依次为 $1,2,3...$ 。 其中，编号为 $i$ 的商店售卖编号为 $i$ 的彩票，且一张彩票的价格为 $i$ 元钱 。

在每一队的所有人各自进行商量之后，对于每一个人，他可以任意在每个商店中购买任意张彩票，但花费的金额不能超过他拥有的钱数，也不能向别人借钱。

在每个人购买完成之后，两支队伍的所有人共同将他们买到的彩票放在一起。在其中挑出只出现过一次的、编号最小的彩票，拥有这张彩票的人所在的队伍获得游戏的胜利。

例如，假如 Clrlss 队在商店 $1,4$ 各买了一张彩票，在商店 $2$ 买了两张彩票；Yaya 队在商店 $1,3$ 各买了一张彩票，那么最终获胜的是 Yaya 队，因为两队的彩票合起来的编号为 $1,1,2,2,3,4$ ，其中 $3$ 是只出现过一次的、编号最小的彩票，而这张彩票属于 Yaya 队。

在多年的磨炼下， Clrlss 和 Yaya 都已经绝顶聪明了，他们都可以找到令自己这一队最优的决策。那么，哪一队会赢得最终的胜利呢？

亲爱的见证者啊，这种题目对您来说肯定不在话下。至于 Yaya， 让我们祝她比赛胜利。

输入格式

第一行两个整数 $n,X$ ，表示 Clrlss 队内的人数和他拥有的钱数。

第二行 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ ，表示 Clrlss 队内每个人各自拥有的钱数。

第三行两个整数 $m,Y$ ，表示 Yaya 队内的人数和她拥有的钱数。

第四行 $m$ 个整数 $b_{1},b_{2},...,b_{m}$ ，表示 Yaya 队内每个人各自拥有的钱数。

$1 \le X,Y \le 10^6 , 1 \le n,m \le 20, 1 \le a_i,b_i \le 16$

输出格式

一行，一个字符串。

如果 Clrlss 会获得游戏的胜利，那么输出 "Clrlss"；

如果 Yaya 会获得游戏的胜利，那么输出 “Yaya"；

如果游戏会以平局告终，输出 "Draw"。

均不包括引号。

样例输入

2 12
5 4
3 5
1 7 2

样例输出

Clrlss

说明

对于 Clrlss ，他可以选择自己购买彩票 $1,2,3,6$ ，然后让他的队友分别购买彩票 $5$ 与彩票 $4$ 。在这种情况下，无论 Yaya 队怎么决策，Clrlss 都将获得最终的胜利。

T7. Yaya 与区间【算法赛】

问题描述

在上大学之后， Yaya 和 Clrlss 在课上接触了一种神秘而又富有吸引力的时代产物：数据结构。这是一种用只言片语无法准确描述的东西，但是它的神奇与巧妙使得 Clrlss 和 Yaya 赞叹不已。

为了试试不同的数据结构究竟能做到什么操作，他们拿出了一个序列。这个序列一共有 $n$ 个整数，分别为 $a_{1},a_{2},...,a_{n}$ 。然后，他们要对这个序列做什么呢？这让他们犯了难。

突然， Clrlss 一拍脑门，兴奋地说：“不如我们来数一数这个序列有多少子区间，满足区间内众数的出现次数恰好超过区间长度的一半！”

由于刚刚接触数据结构， Yaya 听了这个问题之后陷入了沉思。但是， Clrlss 却已经悄悄把这个问题解决了。

亲爱的见证者啊，这种题目对您来说肯定不在话下。至于 Yaya， 让我们祝她不要思考到低血糖。

简化题意：给定一个长度为 $n$ 的序列 $a_{1}..a_{n}$ ,问存在多少个子区间 $a_{l}..a_{r}$ $(1\le l \le r \le n)$ ,满足区间众数出现的次数为$(R-L+1)/2+1$。

其中，"/" 的定义为整除并且向下取整。

输入格式

第一行输入一个整数 $n$ （$1 \le n \le 10^5$） ,表示序列的长度。

第二行输入 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ , 表示给定的序列 ($1 \le a_i \le 10^9$)。

输出格式

一行一个整数，表示符合条件的区间个数。

样例输入

6
1 1 4 5 1 4

样例输出

9

说明

合法的区间有：

• 所有长度为 $1$ 的区间，共 6 个；
• $a_{1}..a_{2}$ ， $a_{1}..a_{3}$ 以及 $a_{1}..a_{5}$ 。

T8. Yaya 与排列【算法赛】

问题描述

不久之后，或者说许多年之后， Clrlss 和 Yaya 都顺利从大学毕业，逐渐步入了社会。此时的他们似乎失去了往日对思考的热爱，取而代之的则是对生活苟且的无尽考量。不知何时，往日解题带给他们的激情似乎再也不能激起他们的兴趣。但是在生活中，他们却延续了学生时期的做法，依旧喜欢找个有空的下午，坐在一起，对着一道看似束手无策的难题发呆。

在这一天也是如此。他们碰到了一个有趣的排列计数问题：

给定一个长度为 $n$ 的序列 $a_{1..n}$ , 问存在多少个排列 $p_{1..n}$ , 满足 $\Sigma ^{n} _{i=1} \min\{{a_i,a_{p_i}}\} = k$ ？

由于这个答案可能非常大，所以他们只感兴趣答案对 $998244353$ 取模之后的结果。

输入格式

第一行输入两个整数 $n,k$ （$2 \le n \le 100 , 0 \le k \le 10000$） ,表示序列的长度和题意中给定的阈值 $k$ 。

第二行输入 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ , 表示给定的序列 ($1 \le a_i \le 100$)。

输出格式

一行一个整数，表示合法的排列的数量，对 $998244353$ 取模。

样例输入

3 5
1 2 3

样例输出

2

说明

对于样例，合法的排列 $p$ 有:

• $1,3,2$
• $2,1,3$

共两个。

T9. Yaya 与数数【算法赛】

问题描述

在几十年以后的一个晚上， Yaya 和 Clrlss 吃完晚饭，在阳台依偎着，把全部的注意力无私地献给静谧的夜空。几十年的风风雨雨与不可抗的衰老，让他们的视线无法避免地变得浑浊，思维难以抵抗地变得迟钝。

为了活跃一下年迈的大脑， Clrlss 转头对 Yaya 说，我来给你出个数数的问题吧。

题目是这样的：

给定 $l,r$ ，求有多少对有序二元组 $(i,j)$ 满足：

• $i,j \ge 0$
• $l \le i^2+j^2 \le r$
• $p|i^2+j^2$

其中，$p=606745820232 = 2^3×3^3×53^2×1000003$ .

亲爱的见证者啊，这种题目对您来说肯定不在话下。至于 Yaya， 让我们祝她听清了题面。

（有序二元组：若 $i \neq j$ ，则 ($i,j$) 与 ($j,i$) 算两个不同的二元组，否则算一个二元组。）

输入格式

一行两个整数 $l,r$ ($0 \le l \le r < 10^{28}$)。

输出格式

一个整数，表示满足条件的有序二元组的数量。

样例输入

0 100

样例输出

1

说明

在样例的范围内，只有 ($0,0$) 一个有序二元组符合条件。