0308 第 27 场 蓝桥入门赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/newbie-27/
• 题解回放：https://www.bilibili.com/video/BV1UZo6YyE3v/

T1. 38 红包【算法赛】

问题描述

$2025$ 年 $38$ 妇女节这天，公司里热闹非凡，老板突发奇想，决定给员工们发发节日红包玩。他召集了全体员工，大手一挥：“咱们公司有 $2025$ 个员工，每人都有个编号，从 $1$ 排到 $2025$。今天是 $38$ 节，凡是编号跟 $3$、$8$、$38$ 沾点边的同事，都能领一个红包！一人一个，不重复领啊！”

小李一听，赶紧问：“老板，啥叫‘沾点边’啊？”

老板笑眯眯地说：“就是编号要是 $3$ 的倍数，或者 $8$ 的倍数，或者 $38$ 的倍数，明白了吧？”

小张凑过来捣乱：“那我编号是 $38$ 的平方，是不是能多领一个？”

老板翻了个白眼：“想得美！说了不重复，你就是 $38$ 的立方，也就一个红包！”

结果，小王跳出来喊：“老板，我编号是 $0$ 咋办？”

老板愣了下，随即哈哈大笑：“咱们从 $1$ 开始编号，哪儿来的 $0$ 啊？你小子是来蹭红包的吧！”

现在，请你算算，老板总共得发多少个红包？

输入格式

无。

输出格式

输出一个整数，表示答案。

T2. 祝福语【算法赛】

问题描述

三月八日国际劳动妇女节即将来临，小蓝和小桥都想为自己的母亲送上一份特别的节日祝福。

小蓝已经用心准备了一条充满深情的祝福语，用仅包含小写字母的字符串 $S$ 表示。小桥同样希望表达对母亲的爱意，但为了避免与小蓝的祝福语重复，她决定设计一条独特的祝福语 $T$，要求 $T$ 不能是 $S$ 的一部分（即 $T$ 不是 $S$ 的子串）。同时，$T$ 也必须仅由小写字母构成。

为了让祝福语更具新意，小桥还希望在所有满足上述条件的祝福语中，$T$ 的字典序是最小的。

输入格式

输入一行，包含一个仅由小写字母构成的字符串 $S$（$1\leq |S| \leq 10^5$），表示小蓝的祝福语。

输出格式

输出一个仅由小写字母构成的字符串 $T$，表示小桥的祝福语。

样例输入

aab

样例输出

aaa

T3. 社区服务【算法赛】

问题描述

为了庆祝妇女节，社区组织了一场“温暖传递”活动。社区中有 $n$ 个服务点排成一列，每个服务点可能有志愿者（用 1 表示）或暂时无人（用 0 表示）。

每个服务点都有居民需要帮助，现在你需要从左往右，为每个无志愿者服务点计算距离最近的有志愿者服务点的距离，若不存在则输出 $-1$。

输入格式

第一行输入一个整数 $n$（$1 \leq n \leq 5000$），表示服务点数量。

第二行输入一个长度为 $n$ 的二进制字符串 $S$，1 表示当前服务点有志愿者，0 表示当前服务点无志愿者。

数据保证 $S$ 至少包含 $1$ 个 0。

输出格式

输出一行若干个整数，表示每个无志愿者服务点到有志愿者服务点的最近距离，若不存在则输出 $-1$。

样例输入

7
1010100

样例输出

1 1 1 2

T4. 表演队【算法赛】

问题描述

三八妇女节当天，蓝桥学院为了感恩母亲，决定组织一支由女同学组成的表演队。学院共有 $N$ 位女同学，每位同学都有一个独特的表演能力值，分别为 $A_1, A_2, \dots, A_N$。学院需要从这 $N$ 位同学中挑选出 $K$ 位，组成一支表演队。

根据《表演队组建指南》，一支表演队的“差异值”定义为：队伍中所有同学的表演能力值之间的绝对差的总和。更正式地说，如果选出的 $K$ 位同学的表演能力值为 $S_1, S_2, \dots, S_K$，那么差异值计算公式为：

$$\sum_{1 \leq i < j \leq K} |S_i - S_j|$$

现在，你的任务是帮助学院组建一只差异值最小的表演队，你只需要求出队伍的最小差异值即可。

输入格式

第一行包含两个整数 $N$ 和 $K$（$1 \leq K \leq N \leq 10^5$），分别表示女同学的总数和需要挑选的同学数量。

第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N$（$1 \leq A_i \leq 10^6$），表示每位同学的表演能力值。

输出格式

输出一个整数，表示选出的 $K$ 位同学的最小差异值。

样例输入

5 3
1 5 10 7 8

样例输出

6

T5. 花束搭配【算法赛】

问题描述

为了庆祝三八妇女节，花店推出了“双花搭配”活动。花店中有 $n$ 种鲜花，每种鲜花有两种属性：

• 放在花束外部时，艳丽度为 $A_i$；
• 放在花束内部时，艳丽度为 $B_i$。

一束花需要由两种 不同的 鲜花组成，一种放在外部，另一种放在内部。如果一束花的“外部艳丽度之和”大于“内部艳丽度之和”，即满足 $A_i + A_j > B_i + B_j$，则这束花被认为是“完美搭配方案”。

现在，给定 $n$ 种鲜花的艳丽度数组 $A$ 和 $B$，请你帮助计算有多少种“完美搭配方案”。

注意，$(i, j)$ 和 $(j, i)$ 被视为不同的组合。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示鲜花的种类数。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$（$1 \leq A_i \leq 10^9$），表示每种鲜花放在外部的艳丽度。

第三行包含 $n$ 个整数 $B_1, B_2, \dots, B_n$（$1 \leq B_i \leq 10^9$），表示每种鲜花放在内部的艳丽度。

输出格式

输出一个整数，表示“完美搭配方案”的数量。

样例输入

3
2 3 4
4 3 2

样例输出

2

说明

对于样例，$(2,3)$ 与 $(3,2)$ 是完美搭配方案。

T6. 妇女唇膏【算法赛】

问题描述

三月八日妇女节当天，蓝桥学院的姐妹团举办了一场“口红配唇膏”活动。她们带来了 $N$ 支口红，每支口红拥有独特的色号，分别为 $A_1, A_2, \dots, A_N$。活动的目标是为所有这些口红调制出一款统一的唇膏，其色号为 $B$，使得每支口红与这款唇膏搭配后都能呈现出最佳的美妆效果。

根据《美妆秘籍》的指引，姐妹们了解到，只有当口红的色号 $A$ 与唇膏的色号 $B$ 满足等式 $A + B = A \oplus B$ 时，二者混合后的色彩效果才能达到巅峰。因此，要实现活动目标，对于每一支口红 $A_i$（其中 $i = 1, 2, \dots, N$），唇膏的色号 $B$ 都必须满足 $A_i + B = A_i \oplus B$。

现在，你的任务是帮助姐妹找出一个最小的正整数 $B$，使得每一支口红 $A_i$ 与该唇膏搭配后都能达到最佳效果。

输入格式

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

第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N$（$1 \leq A_i \leq 10^9$），表示每支口红的色号。

输出格式

输出一个整数，表示满足条件的最小正整数 $B$。

样例输入

3
2 4 6

样例输出

1

样例说明

$B = 1$ 是满足条件的最小正整数：

• $A_1 = 2$：$2 + 1 = 3$，$2 \oplus 1 = 3$，满足 $3 = 3$。
• $A_2 = 4$：$4 + 1 = 5$，$4 \oplus 1 = 5$，满足 $5 = 5$。
• $A_3 = 6$：$6 + 1 = 7$，$6 \oplus 1 = 7$，满足 $7 = 7$。