1228 第 5 场 算法季度赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/season-5/
• 题解回放：https://www.bilibili.com/video/BV12V6gYLEzm/

T1. 加油，2025【算法赛】

问题描述

时光如梭，转眼间，$2025$ 年即将来临。
Time flies, and soon, the year $2025$ will arrive.

迎接新的一年，我们要以更加积极的态度去探索、去学习。
As we welcome the new year, let’s adopt a more positive attitude toward exploration and learning.

每一个新的开始都是一次成长的机会，让我们共同努力，实现更大的梦想。
Every new beginning is an opportunity for growth, so let’s work together to achieve greater dreams.

在这个特别的时刻，请你输出 2025，为你的未来加油！
At this special moment, please output 2025 to cheer for your future!

输入格式

本题为填空题，无需输入即可作答。

输出格式

输出一个数字或字符串，迎接 $2025$ 年。

T2. 开赛主题曲【算法赛】

问题描述

蓝桥杯组委会创作了一首气势磅礴的开赛主题曲，其歌词可用一个仅包含小写字母的字符串 $S$ 表示。$S$ 中的每个字符对应一个音高，音高由字母表顺序决定：$a=1, b=2, ..., z=26$。字母越靠后，音高越高。

为了增强歌曲感染力，组委会希望从中选取一段子串作为副歌。该子串需满足以下条件：

• 所有字母都必须唯一。

此外，若副歌包含“lanqiobe”的前缀（例如“l”、“la”、“lan”等），则可额外获得创作灵感加成：

• “l”: 10 分
• “la”: 20 分
• “lan”: 30 分
• “lanq”: 40 分
• “lanqi”: 50 分
• “lanqio”: 60 分
• “lanqiob”: 70 分
• “lanqiobe”: 80 分

注意：创作灵感加成只能加一次，且只加最高的那个分数。例如，如果副歌是“la”，只会加 20 分，而不会再加上 10 分。

副歌的感染力 = 所有字母对应的音高之和 + 最高的创作灵感加成。

现在，请你找出最佳副歌子串。若有多个满足条件的子串，则输出字典序最小的一个。

输入格式

第一行包含一个正整数 $N$ ( $1 \leq N \leq 2\times 10^5$ )，表示字符串 $S$ 的长度。

第二行包含一个仅由小写字母所组成的字符串 $S$，长度为 $N$。

输出格式

输出一个字符串，表示最佳副歌子串。如果有多个满足条件的子串，则输出字典序最小的那个。

样例输入

8
lbcaccla

样例输出

cla

T3. BlueAI【算法赛】

问题描述

2317 年，小蓝终于在蓝桥杯国赛中一举夺魁，成为了新一届的国特选手。这次，他不仅赢得了无上的荣耀，更是获得了一个挑战蓝桥杯组委会秘密训练的超级 AI —— BlueAI 的机会。

挑战项目是在一个 $N\times N$ 的跳棋棋盘上进行对弈。棋盘上有三种符号：

• L：小蓝的棋子。
• Q：BlueAI 的棋子。
• .：空位。

小蓝的棋子 L 可以跳过 BlueAI 的棋子 Q 并吃掉它，但必须满足以下条件：

1. 跳跃方向： 棋子必须沿着棋盘的四个对角线方向（左上、左下、右上、右下）之一进行跳跃。
2. 跳跃条件： 沿着选定的对角线方向，与 L 相邻的第一个位置必须是 Q，第二个位置必须是空位 .。这样，小蓝的棋子就可以跳跃到第二个位置上，并吃掉 Q。吃完 Q 后，原来 Q 所在的位置将变为空位 .。
3. 多次跳跃： 小蓝可以在一次移动中连续吃掉多个 BlueAI 的棋子。每次跳跃之后，都可以重新选择跳跃方向。也就是说，在吃掉一个 Q 后，如果新的位置仍然满足跳跃条件，小蓝可以选择任意一个对角线方向继续跳跃并吃掉下一个 Q，以此类推，直到无法继续吃子为止。

现在，给定当前棋盘的状态，你的任务是计算在小蓝的回合中，他一次移动最多可以吃掉多少个 BlueAI 的棋子 Q。

输入格式

第一行包含一个整数 $N$（$5 \leq N \leq 12$），表示棋盘的大小。

接下来的 $N$ 行，每行包含一个长度为 $N$、仅由 L、Q、. 构成的字符串，表示棋盘的状态。

数据为随机生成，且保证至少存在一个 L。

输出格式

输出一个整数，表示小蓝在一次移动中最多可以吃掉的 Q 的数量。

样例输入

5
L...L
.Q...
.Q...
.Q...
.....

样例输出

2

T4. 秃头风险【算法赛】

问题描述

蓝桥杯组委会的小伙伴们最近可忙坏了。这不，今年蓝桥杯的报名人数蹭蹭上涨，简直比火箭发射还快！虽说这是一件好事，但同时也带来了一个烦恼：组委会成员的头发！面对如此激增的报名人数，组委会成员的头发都快愁白了！

为了更好地规划未来三年的赛事规模，组委会请来了著名的“预测帝”——一位资深蓝桥杯教练。这位教练掐指一算，预测出如果今年蓝桥杯报名人数为 $X$，那么三年后，蓝桥杯报名人数将达到惊人的 $X^{X^X}$！ 更重要的是，教练还发现：如果 $X^{X^X}$ 的约数个数是奇数，那么三年后，组委会成员的头发将全部掉光！

现在，组委会已经预测了 $N$ 个今年蓝桥杯最终可能的报名人数，分别为 $A_1, A_2, \cdots, A_N$。为了避免三年后组委会成员秃头的悲惨局面，请你帮组委会计算一下，这 $N$ 个可能的报名人数中，有多少个会让组委会三年后面临“集体秃头”的风险？

输入格式

第一行包含一个整数 $N$（$1 \leq N \leq 10^5$），表示组委会预测的最终可能的报名人数的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \cdots, A_N$ ( $1 \leq A_i \leq 10^9$ )，表示第 $i$ 个可能的报名人数。

输出格式

输出一个整数，表示会导致组委会三年后面临“集体秃头”风险的报名人数的数量。

样例输入

5
1 2 3 4 5

样例输出

3

T5. 精准难度【算法赛】

问题描述

小蓝，蓝桥杯命题组的核心人物。今年的他出题灵感爆发，一口气出了 $N$ 道题目，难度系数分别为 $A_1, A_2, \dots, A_N$。

只是，这些题目的难度参差不齐，让组委会专家们伤透了脑筋。如何客观地评估这套题目的整体难度呢？

为了更精准地评估这些题目的整体难度，专家组发明了一种计算方式：

1. 首先，找出所有连续的子序列，并计算每个子序列中所有难度系数的乘积。
2. 然后，将每个子序列的乘积对 2025 取余。
3. 最后，将所有取余后的结果进行异或运算。

最终得到的异或和，就是这 $N$ 道题目的“精准难度”。

现在，请你帮助小蓝，计算出这 $N$ 道题目的“精准难度”。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示题目的数量。

第二行包含 $N$ 个正整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^5$)，表示每道题目的难度系数。

输出格式

输出一个整数，表示这 $N$ 道题目的“精准难度”。

样例输入

3
2 2 3

样例输出

13

T6. 排序题目【算法赛】

问题描述

蓝桥云课的题库正在快速扩展，目前已经有 $N$ 道题目，每道题目的难度系数分别为 $A_1, A_2, \ldots, A_N$。为了帮助学员更好地学习，小蓝决定将这些题目按难度升序排列。

由于题量太多，小蓝无法直接对其进行排序。于是，他灵机一动，想到了一种巧妙的方法：使用“循环移位”功能来辅助排序。

他一共构思了 $N$ 种不同的循环移位功能，其中，第 $i$ 种功能会将序列的前 $i$ 个元素进行循环移位。

举个例子：如果当前序列为 $[2, 1, 3, 4]$，那么在使用了第 $2$ 种功能后，前 $2$ 个元素 $[2, 1]$ 会变成 $[1, 2]$，整个序列会变为 $[1, 2, 3, 4]$。

每种循环移位功能的开发耗时与该功能对应的移位元素数量相关。具体来说，第 $i$ 种功能需要消耗 $i$ 个时间单位（功能一旦开发完成，即可无限次使用）。

现在，请你帮小蓝算算，他最少需要消耗多少开发时间，才能确保使用了所开发的循环移位功能后，题目可以按难度升序排列。

输入格式

第一行包含一个整数 $N$ $(1 \leq N \leq 2\times 10^5)$，表示题目的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$ $(1 \leq A_i \leq N)$，表示每道题目的难度系数。

输出格式

输出一个整数，表示题目可以按难度升序排列所需的最少时间单位。

样例输入

4
2 1 3 4

样例输出

2

样例说明

只需开发第 $2$ 种工具，并使用一次：$[2,1,3,4] \rightarrow [1,2,3,4]$。共需消耗 $2$ 个时间单位。

T7. 铺设地砖【算法赛】

问题描述

公元 2127 年，蓝桥杯省赛依约拉开帷幕。此次省赛的赛场呈 $2$ 行 $N$ 列的矩形布局。为助力选手们迅速定位自己的座位，组委会计划在赛场地面铺设地砖，可供选择的地砖颜色有蓝色与白色两种，按照规定，位于入口处（即左上角）的地砖必须为蓝色。

比赛期间，会有一个机器人在赛场内穿梭，负责为每位参赛选手发放草稿纸和笔。该机器人行动存在一定限制，每次仅能移动至相邻（前后左右方向）且颜色相同的地砖上，同时，为了确保比赛的公正性与物资发放的准确性，机器人不能重复踩踏已经走过的地砖。

身为蓝桥杯的场地设计师，小蓝承担着设计地砖铺设方案的重任，要求所设计的方案能够使机器人从入口（左上角）抵达出口（右下角）的有效路径仅有 1 种。

请问，小蓝有多少种不同的赛场路线规划方案呢？为了避免数字过大，最终结果请对 $10^9 + 7$ 取模。

输入格式

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

接下来的 $T$ 行，每行包含一个整数 $N$（$1\leq N \leq 10^9$），表示赛场的列数。

输出格式

对于每组数据，输出一个整数，表示满足条件的方案数量对 $10^9 + 7$ 取模后的结果。

样例输入

2
2
3

样例输出

2
5