1214 第 24 场 小白入门赛/强者挑战赛

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

T1. 分配辣条【算法赛】

问题描述

蓝桥杯国赛的硝烟即将燃起，为了让麾下的编程新星们以最佳状态应战，贴心的小蓝教练包下了一列高铁，带着 $302$ 位参赛选手风驰电掣地赶往赛场。

高铁上，气氛有些紧张。为了舒缓学生们的心情（以及填饱他们咕咕叫的肚子），小蓝教练决定购买一大批辣条，并平均分给每位学生。

只是，小蓝教练突然想起还有 $3$ 位爱徒——小蓝、小桥和小宝，因为临时有事耽搁了，没能赶上这趟高铁 。虽然如此，但小蓝教练仍然希望把他们算在辣条分配的名单里。

现在，已知高铁上辣条的库存量为 $20250601$ 包。小蓝想知道，他最多能购买多少包辣条，使得所有学生（包括 $3$ 位未能参赛的徒弟）都能获得相同数量的辣条。

T2. 决出国特【算法赛】

问题描述

在蓝桥杯的国赛场上，有两名选手，小蓝和小桥，凭借着对算法的深刻理解，双双获得了满分。只是，按照蓝桥杯国赛的既定规则，特等奖名额仅有一个，只能有一位选手能够获此殊荣。

对此，组委会经过一番商讨，决定临时增设一道题目，期望通过这道题目来决出最终的特等奖归属。

新增题目的内容是这样的：给定一个正整数 $n$，要求找出一个最小的、大于 $1$ 的正整数，使得这个数不能被前 $n$ 个质数整除。

题目十分简短，但让人意想不到的是，组委会出完题后，突然发现这道题有点难度，他们忘记了答案，或者说，他们根本不会计算答案$\ldots$场面一度十分尴尬。

现在，组委会焦急地等待着你的帮助。请你写出程序，帮助组委会找到这个数，让这场精彩的蓝桥杯国赛画上一个圆满的句号。

输入格式

输入一个整数 $n$ $(1 \leq n \leq 10^5)$，表示给定的数字。

输出格式

输出一个整数，表示最小的、大于 $1$ 的自然数，使得这个数不能被前 $n$ 个质数整除。

样例输入

2

样例输出

5

T3. 录入成绩【算法赛】

问题描述

蓝桥杯全国总决赛的颁奖典礼结束后，小蓝被分配了一个任务——录入部分获奖选手的奖项信息。

他用 "G"、"G1"、"G2"、"G3"、"GG"、"1"、"2"、"3" 这些字符串分别表示国特、国一、国二、国三、国优、省一、省二、省三等级。为了提高效率，小蓝写了个 Python 脚本来自动录入这些字符串。但是，小蓝过于粗心，竟忘记在各个奖项代码之间加分隔符！这就导致运行完脚本后，所有的奖项信息都挤在一起变成了一串长长的字符串，例如 "GG123G1G2G3123G1"。

小蓝的头发都快掉光了！他知道这部分选手中，每个奖项都至少有一位获奖选手，且国特只有一位。现在，他对着这串乱糟糟的字符串 $S$，想知道这部分选手中最多可能有多少位选手获得了国一("G1")。

对此，请你帮帮可怜的小蓝，找出字符串 $S$ 中最多可能有多少个 "G1"。

输入格式

输入一个字符串 $S$，包含了所有的奖项信息，字符串长度不超过 $2\times 10^3$。

$S$ 由 "G"、"G1"、"G2"、"G3"、"GG"、"1"、"2"、"3" 组成，保证 $S$ 是合法的。

输出格式

输出一个整数，表示字符串 $S$ 中最多可能包含的 "G1" 的个数。

样例输入

GG123GG2G1G2G3123

样例输出

2

T4. 标记名字【算法赛】

问题描述

蓝桥杯大赛的颁奖典礼马上就要开始了。

本次颁奖典礼，组委会制作了一条超长的空白横幅，并打算在横幅上标记每个选手的名字。标记规则如下：

把横幅的两端分别标记为 0 和 1。

首先，在横幅的正中间 1/2 处标记上第一个决赛选手的名字。

然后，把横幅三等分，在 1/3 和 2/3 处分别标记上另外两名决赛选手的名字。

接下来，把横幅四等分，在 1/4，2/4（也就是 1/2），3/4 处标记选手的名字。但由于 1/2 处已经标记过选手了，所以这次只需在 1/4 和 3/4 两个位置，标记另外两名选手的名字。

以此类推，每次把横幅 $N$ 等分（$N$ 从 2 开始递增），并在每个新的 $\frac{k}{N}$ 的位置 ($1 \le k < N$) 标记选手。如果这个位置已经有标记了，就不用再标记。

用 $f(N)$ 表示每次新增的标记数量（下图红色表示新增的标记，蓝色表示已被标记）：

f(2) = 1

│

f(3) = 2

|

|

f(4) = 2

│

│

│

现在，组委会想知道，当 $N$ 为某个特定值时，新增的标记数量 $f(N)$ 是多少。

输入格式

输入仅一行，包含一个整数 $N$ $(2 \leq N \leq 10^{10})$，表示横幅被分为 $N$ 等分的次数。

输出格式

输出一个整数，表示在将横幅分为 $N$ 等分时新增的标记数量 $f(N)$。

样例输入 1

4

样例输出 1

2

样例输入 2

5

样例输出 2

4

T5. 奖杯排列【算法赛】

问题描述

2340 年 6 月 1 日，蓝桥杯决赛现场，气氛紧张刺激。选手们奋笔疾书，键盘敲得啪啪响。

突然，你的屏幕上弹出了一道题目，题目是这样的：组委会准备了 $N$ 个大小不同的奖杯，每个奖杯上都刻着一个数字 $A_i$，代表奖杯的价值。组委需要从这 $N$ 个奖杯中选出一些奖杯，使得这些奖杯的价值，按照它们在原序列中的顺序排列，能够组成一个长度大于 1、公差为 $K$ 的等差数列。

现在，请你帮组委算算，有多少种不同的等差数列方案？为了避免数字过大，最终结果请对 $10^9 + 7$ 取模。

对于两个等差数列，只要它们所对应的奖杯在原序列中的位置不同，即使数值相同，也视为不同的方案。

输入格式

第一行包含两个整数 $N$ 和 $K$（$2\leq N \leq 2\times 10^5$，$0\leq K \leq 10^9$），分别表示奖杯的个数和等差数列的公差。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1\leq A_i \leq 10^9$），表示每个奖杯上的数字。

输出格式

输出一个整数，表示不同的等差数列方案数对 $10^9+7$ 取模后的结果。

样例输入

3 1
1 2 2

样例输出

2

T6. 估算分数【算法赛】

问题描述

$2121$ 年 $4$ 月 $10$ 日，蓝桥杯软件类省赛如期举办。小蓝摩拳擦掌，跃跃欲试，经过一番激烈的角逐，终于完成了比赛。现在，小蓝迫不及待地想要估算一下自己的分数，看看能不能拿到梦寐以求的省一奖项！

小蓝估算分数的公式是这样的：

$$F(N) = \begin{cases} 0 & \text{if } B \times N - C = 0 \\\\ \frac{A}{B \times N - C} & \text{if } B \times N - C \ eq 0 \end{cases}$$

其中，$A$ 表示小蓝确定自己能够得分的题目数量，$B$ 表示小蓝确定自己无法得分的题目数量，$C$ 表示小蓝不确定能不能得分的题目数量，而 $N$ 则代表着今年蓝桥杯的参赛总人数。小蓝听说，如果他的估分满足 $\lfloor F(N) \rfloor < F(N) < |F(N)|$ ，他就一定能够获得省一。

可是，蓝桥杯组委并不会公布参赛人数，这可急坏了小蓝！现在，他迫切地想知道，有多少个可能的参赛人数 $N$（$N \geq 1$），能够让他稳拿省一。请你帮帮小蓝吧。

输入格式

输入一行包含三个整数 $A$, $B$, $C$，表示小蓝确定能够得分的题目数量、确定无法得分的题目数量和不确定能否得分的题目数量，满足 $1 \leq A, B, C \leq 10^{10}$。

输出格式

输出一行，包含一个整数，表示所有满足条件的参赛人数 $N$ 的数量。

样例输入

5 1 5

样例输出

3

样例说明

满足条件的 $N$ 有 $1$、$2$、 $3$。

T7. 抵御攻击【算法赛】

问题描述

2345 年 4 月 13 日，蓝桥杯省赛即将开办。参与本届蓝桥杯的人数高达 $14$ 亿人。每位参赛选手都使用一台编号唯一的电脑参赛，编号从 1 到 $1400000000$。所有电脑按编号顺序排列成一排。

为了保障网络安全，大赛组委会事先在 $N$ 台电脑（编号 $A_1, A_2, \ldots, A_N$）上安装了防火墙软件。

开赛在即，有情报显示，本次比赛共会有 $M$ 台电脑（编号 $B_1, B_2, \ldots , B_M$）遭受到 DDOS 攻击，这 $M$ 台电脑的编号分别为 $B_1, B_2, \ldots , B_M$。

只有安装了防火墙的电脑才能抵御 DDOS 攻击。对此，组委会设计了一种共享机制：已安装防火墙的电脑可以通过数据线与相邻电脑连接，并共享其防火墙保护。

请问，要保护所有将遭受攻击的电脑，至少需要多少条数据线？

输入格式

第一行输入两个整数 $N$ 和 $M$（$1\leq N,M \leq 10^5$），表示已安装防火墙的电脑数量和将遭受攻击的电脑数量。

第二行输入 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1\leq A_i \leq 10^9$），表示安装了防火墙的电脑编号。

第三行输入 $M$ 个整数 $B_1, B_2, \ldots, B_M$（$1\leq B_i \leq 10^9$），表示将遭受攻击的电脑编号。

数据保证 $A_1, A_2, \ldots, A_N$ 各不相同，$B_1, B_2, \ldots , B_M$ 各不相同。

输出格式

输出一个整数，表示保护所有将遭受攻击的电脑所需的最少的数据线的数量。

样例输入 1

5 3
1 2 3 4 5
1 2 3

样例输出 1

0

样例输入 2

3 1
1 2 3
4

样例输出 2

1

T8. 灵活区间【算法赛】

问题描述

蓝桥杯大赛的报名人数再创新高。今年，蓝桥杯总共设置了 $N$ 个考场，每个考场初始座位数为 $A_i$。

为了应对参赛人数的波动，老蓝希望考场座位安排更加灵活。他知道，如果相邻几个考场的座位数量接近，那么调整座位将变得十分容易。

于是，他设计了一个指标 $F(L,R)$ 来衡量调整座位的难度。即对于任意连续的考场区间 $[L, R]$（$1 \leq L \leq R \leq N$），$F(L,R)$ 表示将区间内所有考场的座位数调整到相同数量所需的最小操作次数（每次操作可以增加或减少一个座位）。操作次数越少，$F(L,R)$ 越小。

老蓝认为，如果一个区间的 $F(L, R)$ 值不超过某个阈值 $M$，那么这个区间就足够灵活，可以应对参赛人数的波动。

现在，老蓝需要你计算有多少个足够灵活的区间，即满足 $F(L, R) \leq M$ 的区间 $[L, R]$ 的数量。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1\leq N \leq 2\times 10^5$，$0 \leq M \leq 10^{14}$），分别表示考场的数量和灵活度阈值。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1\leq A_i \leq 10^9$），表示每个考场的初始座位数。

输出格式

输出一个整数，表示满足 $F(L, R) \leq M$ 的区间数量。

样例输入

3 5
1 2 8

样例输出

4

样例说明

$[1, 1]$：$F(1, 1) = 0$

$[2, 2]$：$F(2, 2) = 0$

$[3, 3]$：$F(3, 3) = 0$

$[1, 2]$：$F(1, 2) = 1$

$[2, 3]$：$F(2, 3) = 6$ (不满足)

$[1, 3]$：$F(1, 3) = 7$ (不满足)

因此，满足条件的区间数量为 $4$。

T9. 代码知音【算法赛】

问题描述

公元 $2556$ 年，蓝桥杯省赛又改革了。今年最大的变化就是：题目数量从原来的 10 道减少到了 8 道，这可让许多选手欢呼雀跃。为了让大家适应新赛制，赛前组委会特地安排了一场模拟赛，并计划根据模拟赛排名帮大家组建学习小组。

模拟赛后，组委会随机选择一个排名区间 $[L, R]$（包含 $L$ 和 $R$）。在这个区间内，如果两位选手的排名分别是 $a$ 和 $b$（$a$ 小于 $b$），并且满足 $a$ 的 $b$ 次方和 $b$ 的 $a$ 次方模 8 同余（即 $a^b \equiv b^a \pmod{8}$，那么这两位选手将被视为“代码知音”，组成学习小组，共同备战蓝桥杯。一位选手可以和多位选手成为“代码知音”。

现在，组委会已经选定了排名区间 $[L, R]$，请你编写一个程序，帮助组委会计算该区间内“代码知音”的对数。为了避免数字过大，最终结果请对 $10^9 + 7$ 取模。

输入格式

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

接下来的 $T$ 行，每行包含两个整数 $L$ 和 $R$ $(1 \leq L < R \leq 10^{18})$，表示排名区间的左端点和右端点。

输出格式

对于每组数据，输出一个整数，表示在区间 $[L, R]$ 内符合条件的“代码知音”的对数对 $10^9+7$ 取模后的结果。

样例输入

2
1 3
2 4

样例输出

0
1