0111 第 25 场 蓝桥入门赛

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

T1. 哪来的 AC【算法赛】

问题描述

小明参加了蓝桥杯比赛，赛场上，他紧张得手心冒汗，不停地搓手。

突然，他灵光一闪，想到了一个绝妙的算法！他激动地敲击键盘，代码行云流水般地涌现。

提交！AC！

他兴奋地大喊：“AC？是 AC！我终于 AC 了，终于通过了！”。话音刚落，就引来周围选手疑惑的目光。

这时，监考老师走了过来，拍了拍他的肩膀，语重心长地说：“小伙子，蓝桥杯是 OI 赛制的比赛，哪来的 AC 啊？”

“对哦，那我这 AC 哪来的”。说完，小蓝看向了自己的电脑。原来啊，小蓝用手机开了个热点，偷偷给电脑连了网。这不，他竟不小心把代码提交到了第三方平台。

“蓝桥杯比赛过程中不允许连网、更不允许访问第三方平台！为了让你记住这次教训，请你数一下蓝桥杯这三个字的笔画数。你若是答对了，我就给你个弥补错误的机会；但若是答错了，嘿嘿…”

小蓝的脸瞬间涨得通红，他意识到自己犯了多么严重的错误。周围选手窃窃私语的声音更大了，监考老师的眼神也变得严肃起来。他后悔莫及，刚才的兴奋劲儿早已荡然无存，取而代之的是深深的恐惧和懊悔。他甚至不敢去看监考老师，生怕听到那句“嘿嘿…”后面隐藏的严厉处罚。

只见默默地低下头，手指紧紧地攥着鼠标，大脑一片空白，完全不知道该怎么办。

作为小蓝的铁哥们，请你帮助小蓝，算算蓝桥杯 这三个字共有多少笔画吧。

输入格式

无。

输出格式

一个整数，表示答案。

T2. 酒店安排【算法赛】

问题描述

第十六届蓝桥杯比赛太火爆了，赛场周围的酒店早早地就被抢订一空，剩下的房间寥寥无几。作为蓝桥学院的指导老师，小蓝为此头疼不已，因为他需要将同学们分配到不同的酒店去入住。

本次比赛中，小蓝带领了 $M$ 名同学参赛。考场周围仅剩下 $N$ 家酒店有空房，每家酒店的位置用 $A_i$ 表示。酒店 $i$ 和酒店 $j$ 之间的距离为 $|A_i - A_j|$。

每位同学将在其中一家酒店入住，每家酒店只容纳一名同学。由于比赛第二天时间紧迫，小蓝希望同学们早早集合赶往考场。集合时间取决于任意两名同学所住酒店之间的最大距离。现在小蓝想知道这个最大距离可能的最小值是多少。

作为同学中的一员，希望你能帮助指导老师小蓝解决这个问题。

输入格式

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

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots A_N(1 \leq A_i \leq 10^9)$ 表示每家酒店的位置。

输出格式

输出一个整数表示答案。

样例输入

5 3
3 1 6 4 5

样例输出

2

样例说明

当 $3$ 位同学入住第 $1,4,5$ 号酒店时为其中一种最优情况，答案为 $2$。

T3. 男女搭配【算法赛】

问题描述

一年一度的蓝桥杯大赛又要开始了！

今年，组委会突发奇想，搞了个“男女搭配，干活不累”的团队赛（新模式），每个参赛团队必须由两名男生和一名女生组成。

小蓝就读的家里蹲大学也是蓝桥杯的参赛院校之一。听说要举办团队赛后，他摩拳擦掌，准备大展身手。

只是，家里蹲大学的领导却突然宣布，为了鼓励学生全面发展，要从包括小蓝在内的 $N$ 名男生和 $M$ 名女生中，选出 $K$ 名优秀学生，送去参加一个重要的，em……全国青少年挖掘机技能特训冬令营。这个集训的时间正好和蓝桥杯冲突，这意味着被选中的同学将无法参加蓝桥杯比赛。

这突如其来的消息，让小蓝和同学们有点措手不及。现在，大家都想知道，在送走了 $K$ 名同学之后，家里蹲大学最多还能组建多少个团队参加蓝桥杯的团队赛。

输入格式

数据有多组。

第一行输入一个整数 $T$（$1\leq T \leq 10^5$），表示数据的组数。

接下来的 $T$ 行，每行输入三个整数 $N$、$M$、$K$（$0\leq N,M \leq 10^9, 0\leq K\leq N+M$），分别表示男生人数、女生人数和需要派去参加特训的学生人数。

输出格式

对于每组数据，输出一个整数，表示最多可以组建的团队数量。

样例输入

2
2 1 0
7 3 3

样例输出

1
2

T4. 排列高手【算法赛】

问题描述

第十六届蓝桥杯即将来临，组委会的专家们希望此次比赛能够更好地考察选手们的思维能力，因此特邀著名的排列高手——小蓝参与助阵！希望他能为本届蓝桥杯设计一道富有创意的排列题。

小蓝接到任务后，立即动起脑筋，口中大喊：“题来！”于是，一道关于排列的问题浮现：

给定一个大小为 $n$ 的排列，你可以任意调整排列的顺序，以使调整后的排列所有非空子数组的 $\text{mex}$ 之和最小，你需要求出这个最小的 $\text{mex}$ 之和。

其中 $\text{mex}$ 表示最小的不在集合中的正整数，例如 $\text{mex}([1,3,4])=2,\text{mex}([2,3,4])=1$。

排列：一个由 $1$ 到 $n$ 的所有整数组成的序列，其中每个数字恰好出现一次。

现在请你尝试解决小蓝给出的这道问题。

输入格式

输入一行包括一个整数 $n(1 \leq n \leq 10^5)$ 表示排列的大小。

输出格式

输出一个整数表示答案。

样例输入

3

样例输出

11

样例说明

对于样例，一种可能的最优排列情况为 $[1,3,2]$，其所有子数组 $\text{mex}$ 之和为 $11$。

其中 $\text{mex}([1])=2,\text{mex}([1,3])=2,\text{mex}([1,3,2])=4,\text{mex}([3])=1,\text{mex}([3,2])=1,\text{mex}([2])=1$。

T5. 混乱的草稿纸【算法赛】

问题描述

一年一度的蓝桥杯省赛即将开赛，小蓝卧薪尝胆，目标直指省一。

为了实现这个宏伟目标，小蓝偷偷准备了一份 $N$ 行的代码模板，分别写在 $N$ 张草稿纸上（每张草稿纸上都写有一行代码，并用 $1$ 到 $N$ 的数字标记了每一行代码的行号）然后偷偷带入了考场（没错，小蓝作弊了）。

然而，命运弄人！当小蓝从口袋里掏出草稿纸时，竟发现草稿纸的顺序全乱了（毫无规律地堆叠在一起，例如，最顶端可能是行号为 $7$ 的草稿纸，其下依次是行号为 $9$ 、行号为 $2$ 的草稿纸）。

为了不被监考老师发现，小蓝决定进行如下操作：

• 将任意一张草稿纸抽出来，放到最上面。

请问，小蓝最少需要多少次这样的操作，才能将代码按照行号 $1$ 到 $N$ 从上往下的顺序排列好呢？

输入格式

第一行输入一个整数 $N$（$1 \leq N \leq 2\times 10^5$），表示草稿纸的数量，也就是代码的行数。

接下来一行包含 $N$ 个整数，以空格隔开，依次表示混乱堆叠的草稿纸从上往下的行号排列情况。

输出格式

输出一个整数，表示小蓝的最少操作次数。

样例输入

5
1 2 4 5 3

样例输出

3

T6. 完美数对【算法赛】

问题描述

蓝桥杯作为最热门的程序设计竞赛之一，主办方为了更好地评估选手的程序设计能力，新研制了一台用于检测选手程序设计能力的仪器。

主办方邀请了 $N$ 位同学进行检测，以验证机器的准确性。检测结果表示为数组 $A$，其中第 $i$ 位同学检测出的能力值为 $A_i$。

得知这一检测结果后，蓝桥杯的出题人小蓝获得了出题灵感。他希望统计满足以下条件的正整数对 $(a,b)$ 的数量，这些数对被称为 "完美数对"：

完美数对定义：对于数对 $(a,b)$，若在数组 $A$ 中，数值 $a$ 至少出现了 $b$ 次，且数值 $b$ 至少出现了 $a$ 次，则数对 $(a,b)$ 被称为完美数对。

现在，请您协助小蓝解决这个问题。

输入格式

第一行输入一个整数 $N(2 \leq N \leq 10^6)$ 表示接受检测的同学数量。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 10^6)$ 表示每位同学的能力值。

输出格式

输出一个整数表示答案。

样例输入

5
1 1 2 2 3

样例输出

4

样例说明

对于样例，数对 $(1,1),(1,2),(2,1),(2,2)$ 满足条件，所以答案为 $4$。