0322 第 27 场 蓝桥月赛

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

T1. 抓猪拿国一【算法赛】

问题描述

蓝桥杯赛场上，选手小王脑洞大开，跑去问裁判：“裁判，蓝桥杯要是改成‘蓝桥抓猪大赛’，得抓多少头猪才能拿国一啊？”裁判愣了愣，但为了显摆幽默，淡定答道：“好说！想拿国一，从第一届开始，每届抓的猪数得是这一届的届数加上前面所有届数的总和。比如，第一届抓 $1$ 头，第二届抓 $1+2=3$ 头，第三届抓 $1+2+3=6$ 头 $\ldots$ 今年是第十六届蓝桥杯，你自己算算吧！”

现在，请你帮小王算算，要拿国一，总共得抓多少头猪？

输入格式

无。

输出格式

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

T2. 蓝桥字符【算法赛】

问题描述

蓝桥杯官方近日收到了一份神秘的包裹，里面包含一个 U 盘和一张纸条，纸条上仅写有一个由小写字母组成的字符串 $S$。经过初步检查，U 盘内存储的内容似乎与即将到来的蓝桥杯大赛有关，但 U 盘被加密，无法直接访问。根据情报提供方的提示，U 盘的密码与字符串 $S$ 中特定子序列的出现次数密切相关。

具体来说，密码等于字符串 $S$ 中子序列 lan 的出现次数。这里的子序列是指从字符串 $S$ 中按顺序选取字符（不一定连续）组成的新字符串。

为了帮助蓝桥杯官方顺利解开 U 盘的密码，你需要编写一个程序，计算字符串 $S$ 中子序列 lan 的出现次数。

输入格式

输入为一个由小写字母组成的字符串 $S$，长度不超过 $10^5$。

输出格式

输出一个整数，表示字符串 $S$ 中子序列 lan 的出现次数。

输入样例

lanlan

输出样例

4

说明

在字符串 lanlan 中，子序列 lan 出现了 $4$ 次。具体来说，可以选取以下位置的字符：

1. 第 $1、2、3$ 个字符（l, a, n）
2. 第 $1、2、6$个字符（l, a, n）
3. 第 $1、5、6$ 个字符（l, a, n）
4. 第 $4、5、6$ 个字符（l, a, n）

T3. 蓝桥大使【算法赛】

问题描述

小蓝和小桥是某学校的蓝桥大使，他们的主要任务是作为宣传人员在校内宣传蓝桥杯比赛。蓝桥杯是一项全国性的编程竞赛，吸引了众多学生参与。为了扩大比赛的影响力，学校决定在每个班级进行宣传，而小蓝和小桥则负责这项工作。

学校共有 $n$ 个班级，每个班级都需要进行宣传。小蓝和小桥可以选择去不同的班级宣传，但为了公平起见，他们决定尽量平均分配任务。具体来说：

• 小蓝将去 $\lfloor \dfrac{n}{2} \rfloor$个班级宣传。
• 小桥将去剩下的 $n - \lfloor \dfrac{n}{2} \rfloor$个班级宣传。

对于第 $i$ 个班级：

• 如果小蓝去宣传，他将获得 $A_i$ 元的酬劳。
• 如果小桥去宣传，她将获得 $B_i$ 元的酬劳。

小蓝和小桥希望最大化他们总共获得的酬劳，请你帮他们计算总酬劳最大值是多少？

输入格式

第一行包含一个整数 $n(1 \leq n \leq 10^5)$，表示班级的数量。

接下来 $n$ 行，每行包含两个整数 $A_i,B_i(1 \leq A_i,B_i \leq 10^9)$，分别表示小蓝和小桥去第 $i$ 个班级宣传时获得的酬劳。

输出格式

输出一个整数表示答案。

输入样例

5
10 20
30 40
100 60
90 80
100 110

输出样例

360

说明

小蓝去第 $3,4$ 个班级宣传，小桥去第 $1,2,5$ 个班级宣传，总共可以获得 $100+90+110+20+40=360$ 元。

T4. 拳头对决【算法赛】

问题描述

蓝桥训练营的日子总是紧张而充实。某天清晨，队员们在连续的高强度训练后，个个眉头紧锁，烦躁在空气中弥漫，甚至有人开始攥紧拳头，想要找个出口释放压力。蓝教练和红教练察觉到这股暗流，交换了一个眼神，灵光一闪：何不来一场“拳头对决赛”？既能让大家舒展筋骨，又能在笑声中拉近彼此的距离。

拳头的大小，成了这场友谊赛的焦点——谁的拳头大，谁就更有气势！两位教练各挑了 $N$ 名队员，蓝队的第 $i$ 个队员的拳头大小为 $A_i$，红队的第 $i$ 个队员的拳头大小为 $B_i$。

比赛的流程是这样的：红教练会按照顺序依次派出他的队员（先派第一位，然后第二位，以此类推）。每当红教练派出一名队员展示拳头后，蓝教练需要从他尚未上场的队员中选择一位应战。裁判会将蓝教练派出的队员的拳头大小与红教练所有已上场队员的拳头大小逐一比较。每当蓝队员的拳头大小大于红队某位已上场队员的拳头，蓝教练便能赢得一次胜利（注意，这不是一对一的较量，而是以一敌多的挑战）。

这场比赛不为胜负，只为放松与切磋，可蓝教练心里却藏着小算盘：既要让队员们开心，也想借机秀一把带队本事，在蓝桥杯的训练营里留下点名声。现在，请你助蓝教练一臂之力，算出在最优策略下，他最多能拿下多少次胜利？

输入格式

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

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1\leq A_i \leq 10^9$），分别是蓝教练队员的拳头大小。

第三行包含 $N$ 个整数 $B_1, B_2, \ldots, B_N$（$1\leq B_i \leq 10^9$），分别是红教练队员的拳头大小。

输出格式

输出一个整数，表示蓝教练在最多能赢下的胜利次数。

样例输入

3
1 3 2
2 1 3

样例输出

3

T5. 未来竞赛【算法赛】

问题描述

时间飞逝，转眼间来到了 5025 年，蓝桥杯大赛已经成为全球瞩目的盛事，吸引了来自世界各地的顶尖选手。每个国家和地区都派出了自己的精英队伍，准备在这场科技盛宴中大显身手。

本次大赛共有 $N$ 位参赛者，第 $i$ 位参赛者的编号位 $i$，来自编号为 $A_i$ 的国家。比赛机房的电脑从左到右依次编号为 $1$ 到 $N$，每位参赛者将在与自己编号相同的电脑上进行比赛。为了确保比赛的公平性，蓝桥杯官方决定对部分参赛者的电脑进行抽样监控。然而，监控方式必须满足以下条件：

1. 监控的电脑数量不能为零。
2. 同一个国家或地区的参赛者最多只能有两台电脑被监控，不能过多集中监控某个国家的选手。
3. 如果同一个国家或地区的两台电脑被监控，它们之间的距离不能超过 $D$。这里的距离定义为两台电脑编号之差的绝对值。

由于可能的监控方式实在太多，官方一时难以计算，于是他们向你求助，希望你能帮忙计算出所有合法的监控方式数量。

由于结果可能非常庞大，请将答案对 $10^9 + 7$ 取模后输出。

输入格式

第一行输入两个整数 $N,D(1 \leq D < N \leq 10^5)$ 表示参赛者数量以及选取的距离要求。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 10^9)$ 表示每位参赛者的国家编号。

输出格式

输出一个整数表示答案，由于答案可能很大，你需要对 $10^9+7$ 取模后输出。

样例输入

5 2
1 2 1 2 2

样例输出

23

说明

对于样例，可能的监控方案有 $[1,2,3,4],[1,2,4]$，但 $[1,2,3,5]$ 不合法，因为 $2$ 号参赛者与 $5$ 号参赛者来自同一国家且两人电脑距离为 $3$，不符合要求。

T6. 备份比赛数据【算法赛】

问题描述

蓝桥杯大赛的组委会最近遇到了一个棘手的问题。他们有 $N$ 台电脑需要备份比赛数据，每台电脑所需的备份时间分别为 $A_1, A_2, \dots, A_N$ 分钟。

备份必须按编号顺序依次进行，即先第 $1$ 台，再第 $2$ 台，依此类推。每台电脑的备份需要工作人员持续操作，且必须安排在同一天内完成。例如，如果某台电脑的备份需要 $5$ 分钟，那这 $5$ 分钟必须安排在同一天，不能拆分到两天。如果当天剩余时间不足以完成某台电脑的备份，那就只能推迟到第二天进行。

每台电脑备份完成后，系统需要等待 $B_i$ 分钟才能开始下一台的备份。这段等待时间不需要工作人员操作，且可以跨天进行。例如，如果第 $1$ 台电脑的备份在第 $1$ 天结束时完成，且 $B_1 = 10$ 分钟，那么第 $2$ 台电脑的备份只需在第 $2$ 天开始后等待 $10$ 分钟就能进行。

现在，组委会希望尽量缩短每天的工作时间，以便工作人员能尽早下班休息。但上级有要求，所有电脑的备份必须在最多 $T$ 天内完成。对此，请你帮助蓝桥杯组委会计算出每天最少需要安排的工作时间 $M$（$M$ 最大不可超过 $3600$），以便所有电脑的备份能在 $T$ 天内顺利完成。如果无论如何都无法满足条件，请直接输出 $-1$。

输入格式

第一行包含两个整数 $N$ 和 $T$（$1 \leq N, T \leq 10^5$），分别表示电脑的数量和最多允许的天数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \leq A_i \leq 3600$），表示每台电脑的备份时间。

第三行包含 $N$ 个整数 $B*1, B_2, \dots, B*{N}$（$1 \leq B_i \leq 3600$），表示每台电脑备份完成后需要等待的时间。

输出格式

输出一个不超过 $3600$ 的整数 $M$，表示每天最少需要安排的工作时间，以确保所有电脑的备份任务能在 $T$ 天内完成。若无法满足条件，则输出 $-1$。

样例输入

3 2
1 2 3
2 2 2

样例输出

5

样例说明

每天工作时间为 $5$ 分钟时，备份任务将按以下方式进行：

• 第 $1$ 天：

  • 第 $1$ 台电脑的备份需要 $1$ 分钟（第 $0\sim 1$ 分钟）。
  • 等待 $B_1 = 2$ 分钟（第 $1\sim 3$ 分钟）。
  • 第 $2$ 台电脑的备份需要 $2$ 分钟（第 $3\sim 5$ 分钟）。

• 第 $2$ 天：

  • 等待 $B_2 = 2$ 分钟（第 $0\sim 2$ 分钟）。
  • 第 $3$ 台电脑的备份需要 $3$ 分钟（第 $2\sim 5$ 分钟）。

所有备份任务可在 $2$ 天内完成。