0531 第 12 场 小白入门赛/强者挑战赛

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

T1. 六一献礼【算法赛】

问题描述

六月的阳光热情似火，孩子们的笑声洋溢着快乐。六一儿童节，是属于每一位孩子的节日。

快乐成长，梦想起航。正是无数孩子的天真无邪，才有了我们五彩斑斓的世界。

现在，为了庆祝这个属于孩子们的节日，蓝桥云课特别准备了一份礼物，希望能够带给每一位孩子、参赛者惊喜和欢乐。

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

输入格式

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

输出格式

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

T2. 六一晚餐【算法赛】

问题描述

随着六一儿童节的临近，蓝桥学院的校长决定组织所有班级的学生外出共享一顿丰盛的晚餐以庆祝这一特别的日子。餐厅已经准备好了 $n$ 张餐桌，每个班级将占用一张餐桌。为了让大家坐得舒适，他们需要为每张桌子添加 $x$ 把椅子。

餐厅有 $m$ 种颜色的椅子供选择，其中第 $i$ 中颜色的椅子有 $a_i$ 把。因为每个班级都有 $x$ 名学生，所以每张桌子都需要配备 $x$ 把椅子。

为了让餐厅的氛围更加和谐美好，校长提出了以下两个要求：

1. 每张桌子的所有椅子必须是同一种颜色。
2. 每种颜色的椅子至少要被用在一张桌子上。

现在，请你帮助校长判断能否在满足上述条件的情况下安排好椅子。

输入格式

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

对于每组数据：

第一行包含三个整数 $n$, $m$, $x$（$1\leq n,m,x \leq 10^3$），分别表示餐桌数量、椅子颜色数量和每张桌子需要的椅子数量。

第二行包含 $m$ 个整数 $a_1$, $a_2$, ..., $a_m$（$1\leq a_i \leq 10^3$），表示每种颜色的椅子数量。

输出格式

对于每组数据，如果能够满足校长的要求，输出 Yes，否则输出 No。

样例输入

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

样例输出

No
Yes

T3. 字符串连接计数【算法赛】

问题描述

给定 $N$ 个字符串 $S_1, S_2, \cdots, S_N$，请计算任选其中两个不同的字符串 $S_i, S_j$，并按照 $S_i S_j$ 的顺序连接所形成的字符串 $T$ 共有多少种不同的结果。

输入格式

输入包含多行，第一行为一个整数 $N$（$2 \leq N \leq 100$），表示字符串的数量。

接下来的 $N$ 行，每行为一个字符串 $S_i$（$1 \leq |S_i| \leq 100$），由英文小写字母组成。

输出格式

输出一个整数，表示不同结果的数量。

样例输入

3
abc
def
ghi

样例输出

6

示例解释

在给定样例中，共有 $3$ 个字符串：$S_1 = \text{abc}$，$S_2 = \text{def}$，$S_3 = \text{ghi}$。

我们可以选择以下几种连接方式：

1. $S_1 S_2 = \text{abcdef}$
2. $S_1 S_3 = \text{abcghi}$
3. $S_2 S_1 = \text{defabc}$
4. $S_2 S_3 = \text{defghi}$
5. $S_3 S_1 = \text{ghiabc}$
6. $S_3 S_2 = \text{ghidef}$

共有 $6$ 种不同的字符串连接结果，因此答案为 $6$。

T4. 字符串加法【算法赛】

问题描述

字符串王国也是存在加减乘除计算法则的，只不过与我们熟悉的法则有所不同。

以加法为例：两个数字 $13$ 和 $14$，按照正常加法来说结果为 $27$。但在字符串王国的加法中，它们相加的结果为 $1314$，即直接将两个数字进行拼接。

现在，给定两个数字 $A$ 和 $B$，请你按照字符串王国的加法法则计算 $A+B$ 的结果。

请注意答案可能很大，你需要将答案对 $10^9+7$ 进行取模后再输出。

输入格式

第一行输入一个数字 $A(1 \leq A \leq 10^{100000})$。

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

保证 $A,B$ 为合法数字。

输出格式

输出一个整数表示答案。

输入样例

12345
54321

输出样例

234554314

T5. 体育课【算法赛】

问题描述

蓝桥学院共有 $N$ 名同学，他们正在体育老师的带领下玩丢手绢的游戏。具体地说，$N$ 名同学会围成一个圆圈，体育老师会给其中一些同学拿上手绢，然后每 $1$ 秒可以选择其中一位携带手绢的同学进行以下操作:

• 将手绢传递给其左手边（顺时针）第一位未拿手绢的同学。
• 将手绢传递给其右手边（逆时针）第一位未拿手绢的同学。

现在体育老师给同学们一个问题：最少需要多少秒才可以让所有带手绢的同学靠在一起？

作为蓝桥学院最聪明的学生，请你回答这个问题。

输入格式

第一行输入一个整数 $N(1 \leq N \leq 10^5)$ 表示同学的数量。

第二行输入一个长度为 $N$ 的字符串 $S(S_i \in[0,1])$，$S_i$ 等于 $0$ 表示第 $i$ 位同学未拿手绢，$S_i$ 等于 $1$ 表示第 $i$ 位同学拿手绢。

输出格式

输出一个整数表示答案。

输入样例

9
111011100

输出样例

1

说明

对于样例，我们可以操作 $1$ 次，将第 $7$ 位同学的手绢传递给第 $4$ 位同学，这样 $111011100$ 将会变为 $1111111000$。

T6. 六一手拉手【算法赛】

问题描述

在六一儿童节的庆祝活动中，蓝桥学院组织了一个游戏。游戏邀请了 $n$ 个孩子参与，每个孩子被赋予了一个独一无二的编号，从 $1$ 到 $n$。

游戏开始前，孩子们将按照给定的编号序列 $\{a_1, a_2, \dots, a_n\}$ 手拉手排成一个圈。编号为 $a_1$ 的孩子与编号为 $a_2$、$a_n$ 的孩子手拉手，编号为 $a_2$ 的孩子与编号为 $a_1$、$a_3$ 的孩子手拉手，以此类推。

游戏过程中，老师会进行 $q$ 次操作。每次操作，老师会选择两个不同编号的孩子，并交换他们的位置。

在每次交换后，孩子们需要从圈中选出两个相邻的孩子松开手，形成一个队列。这个队列可以从任意方向观察，如果队列的编号是有序的（单调递增或单调递减），那么孩子们将获得礼物；反之，孩子们将无法获得礼物。

图片描述

现在，请你帮助孩子们判断，在每次交换后，是否存在一种方式，能够通过让一对相邻孩子松手，使得剩下的孩子排成一个有序的队列。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$（$3\leq n\leq 10^5,1\leq q\leq 10^5$），表示孩子的数量和操作的次数。

接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i \leq n$，$a_1,a_2,\dots, a_n$ 各不相同），表示初始时孩子们的编号序列。

接下来 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1\leq x,y \leq n$，$x\ eq y$），表示一次操作中需要交换位置的两个孩子的编号。

输出格式

输出共 $q$ 行，每行输出一个字符串，表示每次操作后是否存在一种方式使得剩下的孩子排成一个有序的队列。如果存在，输出 Yes，否则输出 No。

样例输出

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

样例输出

No
Yes
No

样例说明

在第一次操作后，孩子们的编号序列为 $\lbrace 1, 4, 3, 2, 5\rbrace$，无法通过让一对相邻孩子松手使得剩下的孩子排成有序队列。

在第二次操作后，孩子们的编号序列为 $\lbrace 5, 4, 3, 2, 1\rbrace$，可以通过让编号为 $1$ 和 $5$ 的孩子松手，使得剩下的孩子排成有序的队列：

$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$$

在第三次操作后，孩子们的编号序列为 $\lbrace 5, 4, 1, 2, 3\rbrace$，无法通过让一对相邻孩子松手使得剩下的孩子排成有序队列。

T7. 猜测数字【算法赛】

问题描述

在一个偏远的小城镇里，有一群热爱猜谜游戏的青年。他们组织了一场活动，并邀请了 $N$ 个参与者。

活动的具体过程是这样的：从 $1\sim M$（$M \geq N$） 之间随机选出 $N$ 个数字，将其分别分给 $N$ 个参与者。

小蓝，活动的策划人，试图猜出每个参与者手中的数字是什么。他做出了 $N$ 个猜测，其中第 $i$ 个猜测的内容为“第 $i$ 个人手中的数字是 $A_i$”。

现在，请你帮小蓝计算一下，在他的这些猜测中，正确的数量最多会是多少？最少又会是多少呢？正确猜测指的是小蓝猜测的数字与参与者实际持有的数字恰好一致。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1\leq N \leq M \leq 10^5$），表示参与者人数和待选择的数字范围。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1\leq A_i \leq M$），表示小蓝的 $N$ 个猜测。

输出格式

输出两个整数，分别表示小蓝正确猜测的最多和最少个数。

样例输入

3 4
1 2 3

样例输出

3 0

样例说明

当 $N$ 个参赛者手中的数字分别为 $\lbrace 1,2,3 \rbrace$ 时，小蓝正确猜测的个数为 $3$。

当 $N$ 个参赛者手中的数字分别为 $\lbrace 2,3,4 \rbrace$ 时，小蓝正确猜测的个数为 $0$。

T8. 气球大比拼【算法赛】

问题描述

六一儿童节即将到来。

为庆祝这个充满欢乐的节日，蓝桥学院邀请了两位优秀学员小蓝和小桥共同参与一项名为的 “气球大比拼” 活动，活动规则如下：

学院准备了 $n$ 个气球，每个气球有一个颜色，用数字 $a_i$ 表示。这些气球整齐地排成一排，排头的第一个气球和排尾的最后一个气球都是可以取的。小蓝和小桥需要轮流从气球排的左右两端取走一个气球，小蓝先开始。如果其中一人取走的气球的颜色是之前没有取过的，那么他就能得到 $1$ 分。当所有气球都被取走后，游戏结束。

小蓝和小桥都希望最大化各自的得分。假设他们都足够聪明，且都会采用最优策略来取气球。请问，在游戏结束后，小蓝和小桥分别能获得多少分？

输入格式

第一行包含一个整数 $n$（$1\leq n \leq 3000$），表示气球的数量。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1\leq a_i \leq n$），表示每个气球的颜色。

输出格式

输出一行，包含两个整数，分别表示小蓝最终获得的分数、小桥最终获得的分数。如果 $1$ 分也未获得，则对应的分数为 $0$。

样例输入

4
1 1 2 1

样例输出

2 0

样例说明

小蓝可以先取走最左端的气球，获得 $1$ 分。取走之后，剩余的气球颜色序列为 $[1, 2, 1]$。

此时，无论小桥取最左端的气球，还是取最右端的气球，都无法获得分数（因为颜色都会重复）。

当小桥取走最左端或最右端的气球后，剩余的气球颜色序列为 $[2,1]$ 或 $[1,2]$。小蓝可以根据情况取走颜色为 $2$ 的气球，获得 $1$ 分，并留下一个颜色为 $1$ 的气球。

小桥取走最后一个气球，无法获得分数。

最终小蓝获得 $2$ 分，小桥获得 $0$ 分。

T9. 国赛训练【算法赛】

问题描述

蓝桥杯国赛即将到来，小梗和小蓝、小桥都期待在比赛中取得出色成绩。

三人共进行了 $n$ 场训练赛，每场训练赛他们都有各自的成绩记录。第 $i$ 场训练赛中，小梗、小蓝和小桥的成绩分别为 $a_i$、$b_i$ 和 $c_i$。

小梗的斗志异常旺盛，他希望找出一个最长的区间 $[L, R]$，使得在该区间内小梗的总成绩不小于小蓝和小桥的总成绩中的较大值，即满足以下条件:

$$\sum_{i=L}^R a_i \ge \max\left(\sum_{i=L}^R b_i, \sum_{i=L}^R c_i\right)$$

您只需要告诉小梗这个最长区间的长度，无需给出具体的区间。

输入格式

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

接下来 $n$ 行每行输入三个整数 $a_i,b_i,c_i(1\leq a_i,b_i,c_i \leq 10^6)$ 表示小梗、小蓝和小桥的训练成绩。

输出格式

输出一个整数表示答案。

输入样例

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

输出样例

4