0405 第 29 场 蓝桥·算法入门赛

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

T1. 不油腻的星座【算法赛】

问题描述

"我们只欢迎不油腻的星座！"

在「非哺乳动物星座联盟」的派对上，主持人突然宣布："请在场的 12 星座中，名字里包含哺乳动物的立刻离场"，结果白羊、金牛、狮子、摩羯 $4$ 个星座红着脸拖着行李箱走了。

现在，请问还有多少星座留在现场？

输入格式

无。

输出格式

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

T2. 守护神开会【算法赛】

问题描述

白羊座、金牛座和双子座的守护神正在一条直线上开会。起初，他们分别位于坐标 $A$、$B$ 和 $C$ 三个不同的位置上。由于他们说话声音都很小，为了能彼此听得更清楚，每次，最外侧（位置坐标最大或最小）的一位守护神要移动到另外两位守护神之间的空隙处，以便他们三靠得更近。

对此，请你算算，他们最多可以进行多少次这样的移动？注意，他们的位置需始终保持不同。

样例输入

第一行包含一个整数 $T$（$1\leq T \leq 10^5$），表示测试用例的个数。

接下来 $T$ 行，每行包含三个整数 $A$、$B$ 和 $C$（$1\leq A < B < C \leq 10^9$），表示三位守护神初始的位置坐标。

样例输出

输出 $T$ 行，每行一个整数，表示他们最多可以进行多少次移动。

样例输入

3
1 2 3
1 3 5
1 4 6

样例输出

0
1
2

T3. 守护射手座【算法赛】

问题描述

射手星座正遭受来自外星系的攻击！星座中有 $N$ 户居民排成一条直线，第 $i$ 户居民有 $A_i$ 人。只有当某户居民人数不少于 $M$ 时，该户才能形成防护罩抵御攻击。

国王可以进行迁移操作：每次选择某一户的所有居民，将他们整体迁移到相邻的左边或右边住户。由于每次迁移都会消耗大量资源，请计算最少需要多少次迁移，才能使所有住户都形成防御罩低于攻击。

如果无论如何都无法实现，输出 $-1$。

注意：两户居民合并后为一户，不会存在一个空的户。

输入格式

第一行两个整数 $N,M(1 \leq N \leq 10^5,1 \leq M \leq 10^9)$ 表示射手星座居民数量以及开始防御罩的需要人数。

第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N(1 \leq A_i \leq 10^4)$ 表示每户居民的数量。

输出格式

输出一个整数表示答案。

样例输入

6 3
1 1 2 3 2 1

样例输出

3

说明

将 $1,2,3$ 户居民合并为 $1$ 户，需要迁移 $2$ 次。

将 $5,6$ 户居民合并为 $1$ 户，需要迁移 $1$ 次。

最终居民分布为 $[4,3,3]$，可以抵御住攻击，总共需要迁移 $3$ 次。

T4. 星座骑士【算法赛】

问题描述

在一次盛大的十二星座大会上，各星座代表齐聚一堂，共同商议组建一支星座守护军队，以应对可能出现的突发情况。这支军队不仅需要强大的战斗力，还需要有卓越的领导才能。经过严格的选拔，最终从十二星座中挑选出了 $N$ 位星座骑士，他们各自展现出独特的能力值，记为 $A_i$。

为了确保军队的高效运作，会议决定选出两位星座骑士作为左右统帅。然而，统帅的选择并非随意，而是有着特殊的要求：这两位统帅的能力值之和必须与剩余骑士的能力值之和保持相同的奇偶性。这一规定旨在确保军队在战斗时的稳定性，避免潜在的混乱和冲突。

请你帮忙计算一下最终能选出多少种符合条件的统帅组合。

输入格式

第一行输入一个整数 $N$（$2 \leq N \leq 10^5$），表示星座骑士的数量。

第二行输入 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1 \leq A_i \leq 10^9$），表示每位星座骑士的能力值。

输出格式

输出一个整数，表示符合条件的统帅组合的数量。

样例输入

5
3 4 4 6 7

样例输出

10

T5. 狮子座的试炼【算法赛】

问题描述

2025 年，在狮子座最明亮的那一夜，草原上将举行一场庄严的仪式： $N$ 头年轻的狮子从左到右排成一行，依次编号为 $1$ 到 $N$，准备接受试炼。

每只狮子都有一种内在特质：犹豫迟疑（用 $0$ 表示）或自信坚定（用 $1$ 表示）。其中，第 $i$ 头狮子的特质为 $A_i$，取值为 $0$ 或 $1$。

试炼的核心目标是检验群体是否具备王者的凝聚力。狮子座的王者精神不仅体现在个体的勇气中，更体现在群体的信念共振上。因此，试炼要求：

• 当这群狮子排成一行时，任意连续的、至少包含 $2$ 头狮子的群体中，犹豫迟疑的数量不能超过自信坚定的数量。

为帮助年轻狮子通过试炼，狮子王请来了大祭司。大祭司可施展魔法：将某头狮子的犹豫特质（$0$）转化为自信特质（$1$）。 对此，请你计算，最少需要进行多少次魔法，才能使狮群通过试炼。

输入格式

第一行包含一个整数 $N$（$2\leq N \leq 10^5$），表示狮子的数量。

第二行包含 $N$ 个整数 $A_1, A_2, ..., A_N$（$0\leq A_i \leq 1$），表示每只狮子的特质。

输出格式

输出一个整数，表示最少需要进行的魔法次数。

样例输入

5
1 0 1 0 0

样例输出

1

T6. 星座解密【算法赛】

问题描述

在一次盛大的星座大会上，各星座代表聚集在一起，讨论如何管理他们的星座力量。每个星座代表都有一个整数值，代表他们的力量，记为 $x$。

现在，他们面临一个挑战：需要将 $x$ 转换为 $0$。可以通过以下两种操作来改变这个整数：

1. 将 $x$ 增加 $1$（即 $x + 1$）。
2. 将 $x$ 改为 $x \And (x + 1)$（按位与操作）。

星座代表们希望找到将 $x$ 转换为 $0$ 所需的最小操作次数，请你帮助他们计算。

输入格式

输入一行一个整数 $x$ $(1 \leq x \leq 10^6)$。

输出格式

输出一个整数，表示将 $x$ 转换为 $0$ 所需的最小操作次数。

样例输入

5

样例输出

3

说明

在给定的样例中，整数 $5$ 可以通过以下步骤转换为 $0$：

1. $5 \rightarrow 6$ (增加 $1$)
2. $6 \rightarrow 7$ (增加 $1$)
3. $7 \rightarrow 0$ (按位与操作)

因此，总共需要 $3$ 次操作。