title: [蓝桥杯 2019 国 C] 最长子序列

description: 我们称一个字符串 $S$ 包含字符串 $T$ 是指 $T$ 是 $S$ 的一个子序列，即可以从字符串 $S$ 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 $T$ 完全一样。给定两个字符串 $S$ 和 $T$，请问 $T$ 中从第一个字符开始最长连续多少个字符被 $S$ 包含？

inputFormat: 输入两行，每行一个字符串。第一行的字符串为 $S$，第二行的字符串为 $T$。两个字符串均非空而且只包含大写英文字母。

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

hint:
对于 $20\%$ 的评测用例，$1 \le |T| \le |S| \le 20$；

对于 $40\%$ 的评测用例，$1 \le |T| \le |S| \le 100$；

对于所有评测用例，$1 \le |T| \le |S| \le 1000$。

蓝桥杯 2019 年国赛 C 组 F 题。


title: [蓝桥杯 2019 国 B] 最优包含

type: P

description:
我们称一个字符串 $S$ 包含字符串 $T$ 是指 $T$ 是 $S$ 的一个子序列，即可以从字符串 $S$ 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 $T$ 完全一样。

给定两个字符串 $S$ 和 $T$，请问最少修改 $S$ 中的多少个字符，能使 $S$ 包含 $T$。

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

hint:
对于 $20 \%$ 的评测用例, $1 \leq|T| \leq|S| \leq 20$;

对于 $40 \%$ 的评测用例, $1 \leq|T| \leq|S| \leq 100$;

对于所有评测用例, $1 \leq|T| \leq|S| \leq 1000$。

蓝桥杯 2019 年国赛 B 组 F 题。


title: [蓝桥杯 2019 国 B] 排列数

description:
在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。

对于一个 $1 ∼ n$ 的排列，如果可以将这个排列中包含 $t$ 个折点，则它称为一个 $t + 1$ 单调排列。

例如，排列 $(1, 4, 2, 3)$ 是一个 $3$ 单调排列，其中 $4$ 和 $2$ 都是折点。

给定 $n$ 和 $k$，请问 $1 ∼ n$ 的所有排列中有多少个 $k$ 单调排列？

inputFormat: 输入一行包含两个整数 $n$, $k$。

outputFormat:
输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列
数量除以 $123456$ 的余数即可。

hint:
对于 $20 \%$ 的评测用例, $1 \leq k \leq n \leq 10$;

对于 $40 \%$ 的评测用例, $1 \leq k \leq n \leq 20$; 对于 $60 \%$ 的评测用例, $1 \leq k \leq n \leq 100$;

对于所有评测用例， $1 \leq k \leq n \leq 500$ 。

蓝桥杯 2019 年国赛 B 组 G 题。


title: [蓝桥杯 2019 国 B] 解谜游戏

description:
小明正在玩一款解谜游戏。谜题由 $24$ 根塑料棒组成，其中黄色塑料棒 $4$ 根，红色 $8$ 根，绿色 $12$ 根 (后面用 `Y` 表示黄色、`R` 表示红色、`G` 表示绿色)。初始时这些塑料棒排成三圈，如上图所示，外圈 $12$ 根，中圈 $8$ 根，内圈 $4$ 根。

小明可以进行三种操作：

1. 将三圈塑料棒都顺时针旋转一个单位。例如当前外圈从 $0$ 点位置开始顺时针依次是 `YRYGRYGRGGGG`，中圈是 `RGRGGRRY`，内圈是 `GGGR`。那么顺时针旋转一次之后，外圈、中圈、内圈依次变为：`GYRYGRYGRGGG`、`YRGRGGRR` 和 `RGGG`。
2. 将三圈塑料棒都逆时针旋转一个单位。例如当前外圈从 $0$ 点位置开始顺时针依次是 `YRYGRYGRGGGG`，中圈是 `RGRGGRRY`，内圈是 `GGGR`。那么逆时针旋转一次之后，外圈、中圈、内圈依次变为：`RYGRYGRGGGGY`、`GRGGRRYR` 和 `GGRG`。
3. 将三圈 $0$ 点位置的塑料棒做一个轮换。具体来说：外圈 $0$ 点塑料棒移动到内圈 $0$ 点，内圈 $0$ 点移动到中圈 $0$ 点，中圈 $0$ 点移动到外圈 $0$ 点。例如当前外圈从 $0$ 点位置开始顺时针依次是 `YRYGRYGRGGGG`，中圈是 `RGRGGRRY`，内圈是 `GGGR`。那么轮换一次之后，外圈、中圈、内圈依次变为：`RRYGRYGRGGGG`、`GGRGGRRY` 和 `YGGR`。

小明的目标是把所有绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈。给定初始状态，请你判断小明是否可以达成目标？

inputFormat:
第一行包含一个整数 $T$，代表询问的组数。$(1 \le T \le 100)$。

每组询问包含 $3$ 行：

第一行包含 $12$ 个大写字母，代表外圈从 $0$ 点位置开始顺时针每个塑料棒的颜色。

第二行包含 $8$ 个大写字母，代表中圈从 $0$ 点位置开始顺时针每个塑料棒的颜色。

第三行包含 $4$ 个大写字母，代表内圈从 $0$ 点位置开始顺时针每个塑料棒的颜色。

outputFormat: 对于每组询问，输出一行 `YES` 或者 `NO`，代表小明是否可以达成目标。

samples:
2
GYGGGGGGGGGG
RGRRRRRR
YRYY
YGGGRRRRGGGY
YGGGRRRR
YGGG

hint: 蓝桥杯 2019 年国赛 B 组 H 题。


title: [蓝桥杯 2019 国 B] 第八大奇迹

background:
在一条 R 河流域，繁衍着一个古老的名族 Z。他们世代沿河而居，也在河边发展出了璀璨的文明。

Z 族在 R 河沿岸修建了很多建筑，最近，他们热衷攀比起来。他们总是在比谁的建筑建得最奇特。

幸好 Z 族人对奇特的理解都差不多，他们很快给每栋建筑都打了分，这样评选谁最奇特就轻而易举了。

于是，根据分值，大家很快评出了最奇特的建筑，称为大奇迹。后来他们又陆续评选了第二奇特、第二奇特、……、第七奇特的建筑，依次称为第二大奇迹、第三大奇迹、……、第七大奇迹。

最近，他们开始评选第八奇特的建筑，准备命名为第八大奇迹。在评选中，他们遇到了一些问题。

description:
首先，Z 族一直在发展，有的建筑被拆除又建了新的建筑，新建筑的奇特值和原建筑不一样，这使得评选不那么容易了。

其次，Z 族的每个人所生活的范围可能不一样，他们见过的建筑并不是所有的建筑，他们坚持他们自己所看到的第八奇特的建筑就是第八大奇迹。

Z 族首领最近很头疼这个问题，他害怕因为意见不一致导致 Z 族发生分歧。他找到你，他想先了解一下，民众自己认为的奇迹是怎样的。

现在告诉在 R 河周边的建筑的变化情况，以及在变化过程中一些人的生活范围，请编程求出每个人认为的第八大奇迹的奇特值是多少。

inputFormat:
输入的第一行包含两个整数 $L$, $N$，分别表示河流的长度和要你处理的信息的数量。开始时河流沿岸没有建筑，或者说所有的奇特值为 $0$。接下来 $N$ 行，每行一条你要处理的信息。

如果信息为 `C p x`，表示流域中第 $p$ 个位置 $(1 \le p \le L)$ 建立了一个建筑，其奇特值为 $x$。如果这个位置原来有建筑，原来的建筑会被拆除。

如果信息为 `Q a b`，表示有个人生活的范围是河流的第 $a$ 到 $b$ 个位置（包含 $a$ 和 $b$，$a \le b$），这时你要算出这个区间的第八大奇迹的奇特值，并输出。如果找不到第八大奇迹，输出 $0$。

outputFormat: 对于每个为 $Q$ 的信息，你需要输出一个整数，表示区间中第八大奇迹的奇特值。

hint:
对于 $20\%$ 的评测用例，$1 \le L \le 1000$，$1 \le N \le 1000$。

对于 $40\%$ 的评测用例，$1 \le L \le 10000$，$1 \le N \le 10000$。

对于 $100\%$ 的评测用例，$1 \le L \le 10^5$，$1 \le N \le 10^5$。所有奇特值为不超过 $10^9$ 的非负整数。

蓝桥杯 2019 年国赛 B 组 I 题。


title: [蓝桥杯 2019 国 B] 燃烧权杖（暂无正解）

background:
目前上传了 $50 \%$ 的数据点。

后 $50 \%$ 的数据点输出 $0$ 即可通过。

description:
小 C 最近迷上了一款游戏。现在，在游戏中，小 C 有一个英雄，生命值为 $x$；敌人也有一个英雄，生命值为 $y$。除此以外，还有 $k$ 个士兵，生命值分别为 $a_1,a_2,\cdots,a_k$。现在小 C 打算使用一个叫做“燃烧权杖”的技能。

“燃烧权杖”会每次等概率随机选择一个活着的角色（英雄或士兵），扣减其 $10$ 点生命值，然后如果该角色的生命值小于或等于 $0$，则该角色死亡，不会再被“燃烧权杖”选中。“燃烧权杖”会重复做上述操作，直至任意一名英雄死亡。小 C 想知道使用“燃烧权杖”后敌方英雄死亡（即，小 C 的英雄存活）的概率。为了避免精度误差，你只需要输出答案模一个质数 $p$ 的结果，具体见输出格式。

inputFormat:
输入包含多组数据。

输入第一行包含一个正整数 $T$，表示数据组数。

接下来 $T$ 组，每组数据第一行包含四个非负整数 $x$、$y$、$p$、$c$，分别表示小 C 的英雄的生命值、敌方英雄的生命值，模数和士兵个数。

第二行包含 $k$ 个正整数 $a_1,a_2,\cdots,a_k$，分别表示每个士兵的生命值。

outputFormat:
对于每组数据，输出一行一个非负整数，表示答案模质数 p 的余数。
可以证明，答案一定为有理数。设答案为 $a/b$（$a$ 和 $b$ 为互质的正整数），你输出的数为 $x$，则你需要保证 $a$ 与 $b\times x$ 模 $p$ 同余；也即，$x \equiv a\times b^{-1} \pmod p$，其中 $b^{-1}$ 表示 $b$ 模 $p$ 的逆元。

hint:
【样例说明】
对于第一组数据，所求概率即为“燃烧权杖”第一次就扣减敌方英雄 $10$ 点生命值的概率，即 $1/2$。$2 \times 51$ 模 $101$ 余 $1$。

对于第二组数据，答案为 $1023/1024$，$1024 \times 37$ 与 $1023$ 模 $101$ 同余。

对于第三组数据，答案为 $99/128$。

【评测用例规模与约定】

对于 $10\%$ 的评测用例，$x, y, a_1,\cdots, a_k \le 10$。

对于 $20\%$ 的评测用例，$x, y, a_1,\cdots, a_k \le 100$。

对于 $50\%$ 的评测用例，$x, y, a_1,\cdots, a_k \le 1000$。

对于全部评测用例，$1 ≤ x, y, a_1,\cdots, a_k ≤ 10^9$，$3 \le p \le 10000$ 且 $p$ 为质数，$0 \le k \le 10$。

蓝桥杯 2019 年国赛 B 组 J 题。


title: [蓝桥杯 2020 省 A2] 填空问题

description:
## 试题 A ：门牌制作

### 【问题描述】

小蓝要为一条街的住户制作门牌号。

这条街一共有 $2020$ 位住户，门牌号从 $1$ 到 $2020$ 编号。

小蓝制作门牌的方法是先制作 $0$ 到 $9$ 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 $1017$ 需要依次粘贴字符 `1`、`0`、`1`、`7`，即需要 $1$ 个字符 `0`，$2$ 个字符 `1`，$1$ 个字符 `7`。

请问要制作所有的 $1$ 到 $2020$ 号门牌，总共需要多少个字符 $2$?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B ：既约分数

### 【问题描述】

如果一个分数的分子和分母的最大公约数是 $1$ ，这个分数称为既约分数。

例如，$\frac{3}{4},\frac{5}{2},\frac{1}{8},\frac{7}{1}$ 都是既约分数。

请问，有多少个既约分数，分子和分母都是 $1$ 到 $2020$ 之间的整数（包括 $1$ 和 $2020$)?

### 【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：蛇形填数

### 【问题描述】

如下图所示，小明用从 $1$ 开始的正整数 “蛇形” 填充无限大的矩阵。

$\begin{array}{cccccc}1 & 2 & 6 & 7 & 15 & \ldots \\ 3 & 5 & 8 & 14 & \ldots & \\ 4 & 9 & 13 & \ldots & & \\ 10 & 12 & \ldots & & & \\ 11 & \ldots & & & & \\ \ldots & & & & & \end{array}$

容易看出矩阵第二行第二列中的数是 $5$。请你计算矩阵中第 $20$ 行第 $20$ 列的数是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：七段码

### 【问题描述】

小蓝要用七段码数码管来表示一种特殊的文字。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_7ff7a90fd65c5962b43dg-05.jpg)

上图给出了七段码数码管的一个图示，数码管中一共有 $7$ 段可以发光的二极管，分别标记为 $a,b,c,d,e,f,g$。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。

例如：$\mathrm{b}$ 发光，其他二极管不发光可以用来表达一种字符。

例如：$\mathrm{c}$ 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。

例如：$a,b,c,d,e$ 发光，$f,g$ 不发光可以用来表达一种字符。

例如：$b,f$ 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：平面分割

### 【问题描述】

$20$ 个圆和 $20$ 条直线最多能把平面分成多少个部分?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
        "The answer of task C", // 双引号中替换为 C 题的答案
        "The answer of task D", // 双引号中替换为 D 题的答案
        "The answer of task E", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2020 省 B2] 填空问题

description:
## 试题 A ：门牌制作

### 【问题描述】

小蓝要为一条街的住户制作门牌号。

这条街一共有 $2020$  位住户，门牌号从 $1$  到 $2020$  编号。

小蓝制作门牌的方法是先制作 $0$  到 $9$  这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 $1017$  需要依次粘贴字符 `1`、`0`、`1`、`7`，即需要 $1$ 个字符 `0`，$2$ 个字符 `1`，$1$ 个字符 `7` 。

请问要制作所有的 $1$  到 $2020$  号门牌，总共需要多少个字符 $2$ ?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B ：既约分数

### 【问题描述】

如果一个分数的分子和分母的最大公约数是 $1$ ，这个分数称为既约分数。

例如，$\frac{3}{4},\frac{5}{2},\frac{1}{8},\frac{7}{1}$ 都是既约分数。

请问，有多少个既约分数，分子和分母都是 $1$  到 $2020$  之间的整数（包括 $1$  和 $2020$ )?

### 【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：蛇形填数

### 【问题描述】

如下图所示，小明用从 $1$  开始的正整数 “蛇形” 填充无限大的矩阵。

$\begin{array}{cccccc}1 & 2 & 6 & 7 & 15 & \ldots \\ 3 & 5 & 8 & 14 & \ldots & \\ 4 & 9 & 13 & \ldots & & \\ 10 & 12 & \ldots & & & \\ 11 & \ldots & & & & \\ \ldots & & & & & \end{array}$

容易看出矩阵第二行第二列中的数是 $5$ 。请你计算矩阵中第 $20$  行第 $20$ 列的数是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：跑步锻炼

### 【问题描述】

小蓝每天都锻炼身体。

正常情况下，小蓝每天跑 $1$  千米。如果某天是周一或者月初（1日，为了激励自己，小蓝要跑 $2$  千米。如果同时是周一或月初，小蓝也是跑 $2$  千米。

小蓝跑步已经坚持了很长时间，从 $2000$  年 $1$  月 $1$  日周六（含）到 $2020$  年 $10$  月 $1$  日周四（含）。请问这段时间小蓝总共跑步多少千米?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：七段码

### 【问题描述】

小蓝要用七段码数码管来表示一种特殊的文字。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_7ff7a90fd65c5962b43dg-05.jpg)

上图给出了七段码数码管的一个图示，数码管中一共有 $7$  段可以发光的二极管，分别标记为 $a,b,c,d,e,f,g$。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。

例如：b 发光，其他二极管不发光可以用来表达一种字符。

例如：$\mathrm{c}$ 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。

例如：$a,b,c,d,e$ 发光，$f,g$ 不发光可以用来表达一种字符。

例如：$b,f$ 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
        "The answer of task C", // 双引号中替换为 C 题的答案
        "The answer of task D", // 双引号中替换为 D 题的答案
        "The answer of task E"  // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2020 省 AB2] 子串分值

description:
对于一个字符串 $S$, 我们定义 $S$ 的分值 $f(S)$ 为 $S$ 中恰好出现一次的字符个数。例如 $f\left({ }^{\prime \prime} \mathrm{aba}{ }^{\prime \prime}\right)=1$，$f\left({ }^{\prime \prime} \mathrm{abc}{ }^{\prime \prime}\right)=3$，$f\left({ }^{\prime \prime} \mathrm{aaa} \mathrm{a}^{\prime \prime}\right)=0$ 。

现在给定一个字符串 $S[0 . . n-1]$（长度为 $n$），请你计算对于所有 $S$ 的非空 子串 $S[i . . j](0 \leq i \leq j<n)$，$f(S[i . . j])$ 的和是多少。

inputFormat: 输入一行包含一个由小写字母组成的字符串 $S$。

outputFormat: 输出一个整数表示答案。

hint:
对于 $20 \%$ 的评测用例, $1 \leq n \leq 10$;

对于 $40 \%$ 的评测用例, $1 \leq n \leq 100$;

对于 $50 \%$ 的评测用例, $1 \leq n \leq 1000$;

对于 $60 \%$ 的评测用例, $1 \leq n \leq 10000$;

对于所有评测用例, $1 \leq n \leq 100000$。

蓝桥杯 2020 第二轮省赛 A 组 H 题（B 组 H 题）。


title: [蓝桥杯 2020 省 AB2] 回文日期

description:
2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 `yyyymmdd` 的格式写成一个 $8$ 位数是 `20200202`，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 `20200202` 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：`20211202` 即 2021 年 12 月 2 日。

也有人表示 `20200202` 并不仅仅是一个回文日期，还是一个 `ABABBABA` 型的回文日期。对此小明也不认同，因为大约 $100$ 年后就能遇到下一个 `ABABBABA` 型的回文日期：`21211212` 即 2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 `ABABBABA` 型的回文日期各是哪一天。

inputFormat: 输入包含一个八位整数 $N$，表示日期。

outputFormat:
输出两行，每行 $1$ 个八位数。第一行表示下一个回文日期，第二行表示下
一个 `ABABBABA` 型的回文日期。

hint:
对于所有评测用例，$10000101 \le N \le 92200229$，保证 $N$ 是一个合法日期的 $8$ 位数表示。

蓝桥杯 2020 第二轮省赛 A 组 G 题（B 组 G 题）。


title: [蓝桥杯 2020 省 AB2] 成绩分析

description:
小蓝给学生们组织了一场考试，卷面总分为 $100$ 分，每个学生的得分都是一个 $0$ 到 $100$ 的整数。

请计算这次考试的最高分、最低分和平均分。

inputFormat:
输入的第一行包含一个整数 $n$，表示考试人数。

接下来 $n$ 行，每行包含一个 $0$ 至 $100$ 的整数，表示一个学生的得分。

outputFormat:
输出三行。

第一行包含一个整数，表示最高分。

第二行包含一个整数，表示最低分。

第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。

hint:
对于 $50 \%$ 的评测用例, $1 \leq n \leq 100$。

对于所有评测用例, $1 \leq n \leq 10000$。

蓝桥杯 2020 第二轮省赛 A 组 F 题（B 组 F 题）。


title: [蓝桥杯 2020 省 A2] 荒岛探测

description:
科学家小蓝来到了一个荒岛, 准备对这个荒岛进行探测考察。

小蓝使用了一个超声定位设备来对自己进行定位。为了使用这个设备，小蓝需要在不同的点分别安装一个固定的发射器和一个固定的接收器。小蓝手中还有一个移动设备。定位设备需要从发射器发射一个信号到移动设备, 移动设备收到后马上转发，最后由接收器接收，根据这些设备之间传递的时间差就能计算出移动设备距离发射器和接收器的两个距离，从而实现定位。

小蓝在两个位置已经安装了发射器和接收器, 其中发射器安装在坐标 $\left(x_{A},y_{A}\right)$，接收器安装在坐标 $\left(x_{B},y_{B}\right)$ 。小蓝的发射器和接收器可能在岛上，也可能不在岛上。

小蓝的定位设备设计有些缺陷, 当发射器到移动设备的距离加上移动设备 到接收器的距离之和大于 $L$ 时, 定位设备工作不正常。当和小于等于 $L$ 时，定位设备工作正常。为了安全，小蓝只在定位设备工作正常的区域探测考察。

已知荒岛是一个三角形, 三个顶点的坐标分别为 $\left(x_{1}, y_{1}\right)$，$\left(x_{2},y_{2}\right)$，$\left(x_{3},y_{3}\right)$。

请计算，小蓝在荒岛上可以探测到的面积有多大。

outputFormat:
输出一行, 包含一个实数, 四舍五入保留 $2$ 位小数，表示答案。

考虑到计算中的误差，只要你的输出与参考输出相差不超过 $0.01$ 即可得分。

hint:
**【样例说明】**

荒岛的形状和定位设备工作正常的区域如下图所示, 蓝色的三角形表示荒岛, 红色的曲线围成的区域为定位设备工作正常的区域。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_7ff7a90fd65c5962b43dg-14.jpg)

当输出为 $39.98、39.99$ 或 $40.00$ 时可以得分。

**【评测用例规模与约定】**

对于所有评测用例, 保证发射器的两个坐标不同, $-1000 \leq x_{A}, y_{A}, x_{B}, y_{B} \leq$ $1000,-1000 \leq x_{1}, y_{1}, x_{2}, y_{2}, x_{3}, y_{3} \leq 1000,-1000 \leq L \leq 1000$ 。

蓝桥杯 2020 第二轮省赛 A 组 I 题。


title: [蓝桥杯 2020 省 AB2] 字串排序

description:
小蓝最近学习了一些排序算法, 其中冒泡排序让他印象深刻。

在冒泡排序中, 每次只能交换相邻的两个元素。

小蓝发现, 如果对一个字符串中的字符排序, 只允许交换相邻的两个字符, 则在所有可能的排序方案中, 冒泡排序的总交换次数是最少的。

例如, 对于字符串 lan 排序, 只需要 $1$ 次交换。对于字符串 qiao 排序, 总共需要 $4$ 次交换。

小蓝的幸运数字是 $V$, 他想找到一个只包含小写英文字母的字符串, 对这个串中的字符进行冒泡排序, 正好需要 $V$ 次交换。请帮助小蓝找一个这样的字符串。如果可能找到多个, 请告诉小蓝最短的那个。如果最短的仍然有多个, 请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。

inputFormat: 输入的第一行包含一个整数 $V$，小蓝的幸运数字。

outputFormat: 题面要求的一行字符串。

hint:
对于 $30 \%$ 的评测用例, $1 \leq V \leq 20$。

对于 $50 \%$ 的评测用例, $1 \leq V \leq 100$。

对于所有评测用例, $1 \leq V \leq 10000$。

蓝桥杯 2020 第二轮省赛 A 组 J 题（B 组 J 题）。


title: [蓝桥杯 2020 省 B2] 平面切分

description:
平面上有 $N$ 条直线, 其中第 $i$ 条直线是 $y=A_{i} \cdot x+B_{i}$ 。

请计算这些直线将平面分成了几个部分。

inputFormat:
第一行包含一个整数 $N$。

以下 $\mathrm{N}$ 行, 每行包含两个整数 $A_{i}, B_{i}$。

outputFormat: 一个整数代表答案。

hint:
对于 $50 \%$ 的评测用例, $1 \leq N \leq 4,-10 \leq A_{i}, B_{i} \leq 10$。

对于所有评测用例, $1 \leq N \leq 1000,-10^5 \leq A_{i}, B_{i} \leq 10^5$。

蓝桥杯 2020 第二轮省赛 B 组 I 题


title: [蓝桥杯 2020 国 A] 填空问题

description:
## 试题 A ：合数个数

### 【问题描述】

一个数如果除了 $1$  和自己还有其他约数，则称为一个合数。例如：$1,2,3$ 不是合数，4,6 是合数。

请问从 $1$  到 $2020$  一共有多少个合数。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B ：含 $2$  天数

### 【问题描述】

小蓝特别喜欢 $2$ ，今年是公元 $2020$ 年，他特别高兴，因为每天日历上都可以看到 $2$ 。

如果日历中只显示年月日，请问从公元 $1900$  年 $1$  月 $1$  日到公元 $9999$  年 $12$  月 $31$  日，一共有多少天日历上包含 $2$ 。即有多少天中年月日的数位中包含数字 $2$ 。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：本质上升序列

### 【问题描述】

小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

例如，在字符串 lanqiao 中，如果取出字符 $\mathrm{n}$ 和 $\mathrm{q}$，则 $\mathrm{nq}$ 组成一个单调递增子序列。类似的单调递增子序列还有 Inq、i、ano 等等。

小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 $\mathrm{ao}$，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个?

例如，对于字符串 lanqiao,本质不同的递增子序列有 $21$  个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、 anq。

请问对于以下字符串（共 $200$  个小写英文字母，分四行显示)：(如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt,内容与下面的文本相同）

```
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl
```

本质不同的递增子序列有多少个?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：咫尺天涯

### 【问题描述】

皮亚诺曲线是一条平面内的曲线。

下图给出了皮亚诺曲线的 $1$  阶情形，它是从左下角出发，经过一个 $3 \times 3$ 的方格中的每一个格子，最终到达右上角的一条曲线。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-05.jpg)

设每个格子的边长为 $1$ ，在上图中，有的相邻的方格（四相邻）在皮亚诺曲线中也是相邻的，在皮亚诺曲线上的距离是 $1$ ，有的相邻的方格在皮亚诺曲线中不相邻，距离大于 $1$ 。

例如，正中间方格的上下两格都与它在皮亚诺曲线上相邻，距离为 $1$ ，左右两格都与它在皮亚诺曲线上不相邻，距离为 $3$ 。

下图给出了皮亚诺曲线的 $2$  阶情形，它是经过一个 $3^{2} \times 3^{2}$ 的方格中的每一个格子的一条曲线。它是将 $1$  阶曲线的每个方格由 $1$  阶曲线替换而成。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-06.jpg)

下图给出了皮亚诺曲线的 $3$  阶情形，它是经过一个 $3^{3} \times 3^{3}$ 的方格中的每一个格子的一条曲线。它是将 $2$  阶曲线的每个方格由 $1$  阶曲线替换而成。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-07.jpg)

皮亚诺曲线总是从左下角开始出发，最终到达右上角。

小蓝对于相邻的方格在皮亚诺曲线上的相邻关系很好奇，他想知道相邻的方格在曲线上的距离之和是多少。

例如，对于 $1$  阶皮亚诺曲线，距离和是 $24$ ，有 $8$  对相邻的方格距离为 $1$ ，2 对相邻的方格距离为 $3$ ,2 对相邻的方格距离为 $5$ 。

再如，对于 $2$  阶皮亚诺曲线，距离和是 $816$ 。

请求出对于 $12$  阶皮亚诺曲线，距离和是多少。

提示：答案不超过 $10^{18}$。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：玩具蛇

### 【问题描述】

小蓝有一条玩具蛇，一共有 $16$  节，上面标着数字 $1$  至 $16$ 。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 $90$  度角。

小蓝还有一个 $4 \times 4$ 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 $\mathrm{A}$ 到 $\mathrm{P}$ 共 $16$  个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:

![](https://cdn.luogu.com.cn/upload/image_hosting/o83c5jqw.png)

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2020 国 B] 填空问题

description:
## 试题 A ：美丽的 $2$

### 【问题描述】

小蓝特别喜欢 $2$ ，今年是公元 $2020$  年，他特别高兴。

他很好奇，在公元 $1$  年到公元 $2020$  年（包含）中，有多少个年份的数位中包含数字 $2$ ?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：扩散

### 【问题描述】

小蓝在一张无限大的特殊画布上作画。

这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。

小蓝在画布上首先点了一下几个点：$(0,0),(2020,11),(11,14),(2000,2000)$。只有这几个格子上有黑色，其它位置都是白色的。

每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色 (如果原来就是黑色，则还是黑色)。

请问，经过 $2020$  分钟后，画布上有多少个格子是黑色的。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C：阶乘约数

### 【问题描述】

定义阶乘 $n !=1 \times 2 \times 3 \times \cdots \times n$。

请问 $100$  （（100 的阶乘）有多少个约数。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：本质上升序列

### 【问题描述】

小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

例如，在字符串 lanqiao 中，如果取出字符 $\mathrm{n}$ 和 $\mathrm{q}$，则 $\mathrm{nq}$ 组成一个单调递增子序列。类似的单调递增子序列还有 Inq、i、ano 等等。

小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 $\mathrm{ao}$，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个?

例如，对于字符串 lanqiao,本质不同的递增子序列有 $21$  个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、 anq。

请问对于以下字符串（共 $200$  个小写英文字母，分四行显示)：(如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt,内容与下面的文本相同）

```
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl
```

本质不同的递增子序列有多少个?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：玩具蛇

### 【问题描述】

小蓝有一条玩具蛇，一共有 $16$  节，上面标着数字 $1$  至 $16$ 。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 $90$  度角。

小蓝还有一个 $4 \times 4$ 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 $\mathrm{A}$ 到 $\mathrm{P}$ 共 $16$  个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:

![](https://cdn.luogu.com.cn/upload/image_hosting/o83c5jqw.png)

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2020 国 C] 填空问题

description:
## 试题 A ：美丽的 $2$

### 【问题描述】

小蓝特别喜欢 $2$ ，今年是公元 $2020$  年，他特别高兴。

他很好奇，在公元 $1$  年到公元 $2020$  年（包含）中，有多少个年份的数位中包含数字 $2$ ?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：合数个数

### 【问题描述】

一个数如果除了 $1$ 和自己还有其他约数，则称为一个合数。例如：$1$，$2$，$3$ 不是合数，$4$，$6$ 是合数。

请问从 $1$ 到 $2020$ 一共有多少个合数。

### 【答案提交】

提交一个整数。

## 试题 C：扩散

### 【问题描述】

小蓝在一张无限大的特殊画布上作画。

这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。

小蓝在画布上首先点了一下几个点：$(0,0),(2020,11),(11,14),(2000,2000)$。只有这几个格子上有黑色，其它位置都是白色的。

每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色 (如果原来就是黑色，则还是黑色)。

请问，经过 $2020$  分钟后，画布上有多少个格子是黑色的。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：阶乘约数

### 【问题描述】

定义阶乘 $n !=1 \times 2 \times 3 \times \cdots \times n$。

请问 $100$  （（100 的阶乘）有多少个约数。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：本质上升序列

### 【问题描述】

小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

例如，在字符串 lanqiao 中，如果取出字符 $\mathrm{n}$ 和 $\mathrm{q}$，则 $\mathrm{nq}$ 组成一个单调递增子序列。类似的单调递增子序列还有 Inq、i、ano 等等。

小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 $\mathrm{ao}$，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个?

例如，对于字符串 lanqiao,本质不同的递增子序列有 $21$  个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、 anq。

请问对于以下字符串（共 $200$  个小写英文字母，分四行显示)：(如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在附件中有一个文件 inc.txt,内容与下面的文本相同）

```
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl
```

本质不同的递增子序列有多少个?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2020 国 ABC] 皮亚诺曲线距离

description:
皮亚诺曲线是一条平面内的曲线。

下图给出了皮亚诺曲线的 1 阶情形, 它是从左下角出发, 经过一个 $3 \times 3$ 的 方格中的每一个格子, 最终到达右上角的一条曲线。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-05.jpg)

下图给出了皮亚诺曲线的 2 阶情形, 它是经过一个 $3^{2} \times 3^{2}$ 的方格中的每一 个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-06.jpg)

下图给出了皮亚诺曲线的 3 阶情形, 它是经过一个 $3^{3} \times 3^{3}$ 的方格中的每一 个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-07.jpg)

皮亚诺曲线总是从左下角开始出发, 最终到达右上角。

我们将这些格子放到坐标系中, 对于 $k$ 阶皮亚诺曲线, 左下角的坐标是 $(0,0)$, 右上角坐标是 $\left(3^{k}-1,3^{k}-1\right)$, 右下角坐标是 $\left(3^{k}-1,0\right)$, 左上角坐标是 $\left(0,3^{k}-1\right)$ 。

给定 $k$ 阶皮亚诺曲线上的两个点的坐标, 请问这两个点之间, 如果沿着皮 亚诺曲线走, 距离是多少?

inputFormat:
输入的第一行包含一个正整数 $k$, 皮亚诺曲线的阶数。

第二行包含两个整数 $x_{1}, y_{1}$, 表示第一个点的坐标。 第三行包含两个整数 $x_{2}, y_{2}$, 表示第二个点的坐标。

outputFormat: 输出一个整数, 表示给定的两个点之间的距离。


title: [蓝桥杯 2020 国 AB] 出租车

background: 小蓝在 $L$ 市开出租车。

description:
$L$ 市的规划很规整，所有的路都是正东西向或者正南北向的，道路都可以看成直线段。东西向的道路互相平行, 南北向的道路互相平行，任何一条东西向道路垂直于任何一条南北向道路。

从北到南一共有 $n$ 条东西向道路，依次标号为 $H_{1}, H_{2}, \cdots, H_{n}$ 。从西到东 一共有 $m$ 条南北向的道路，依次标号为 $S_{1}, S_{2}, \cdots, S_{m}$ 。

每条道路都有足够长，每一条东西向道路和每一条南北向道路都相交，$H_{i}$ 与 $S_{j}$ 的交叉路口记为 $(i, j)$ 。

从 $H_{1}$ 和 $S_{1}$ 的交叉路口 $(1,1)$ 开始，向南遇到的路口与 $(1,1)$ 的距离分别 是 $h_{1}, h_{2}, \cdots, h_{n-1}$，向东遇到路口与 $(1,1)$ 的距离分别是 $w_{1}, w_{2}, \cdots, w_{m-1}$ 。

道路的每个路口都有一个红绿灯。

时刻 $0$ 的时候，南北向绿灯亮，东西向红灯亮，南北向的绿灯会持续一段时间（每个路口不同)，然后南北向变成红灯，东西向变成绿灯，持续一段时间后，再变成南北向绿灯，东西向红灯。

已知路口 $(i, j)$ 的南北向绿灯每次持续的时间为 $g_{i j}$, 东西向的绿灯每次持续的时间为 $r_{i j}$, 红绿灯的变换时间忽略。

当一辆车走到路口时，如果是绿灯，可以直行、左转或右转。如果是红灯，可以右转，不能直行或左转。如果到路口的时候刚好由红灯变为绿灯，则视为看到绿灯；如果刚好由绿灯变为红灯，则视为看到红灯。

每段道路都是双向道路，道路中间有隔离栏杆，在道路中间不能掉头, 只能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时间可以忽略。

小蓝时刻 $0$ 从家出发。今天，他接到了 $q$ 个预约的订单，他打算按照订单 的顺序依次完成这些订单，就回家休息。中途小蓝不准备再拉其他乘客。小蓝的家在两个路口的中点，小蓝喜欢用 $x_{1}, y_{1}, x_{2}, y_{2}$ 来表示自己家的位 置, 即路口 $\left(x_{1}, y_{1}\right)$ 到路口 $\left(x_{2}, y_{2}\right)$ 之间的道路中点的右侧, 保证两个路口相邻 (中间没有其他路口)。请注意当两个路口交换位置时，表达的是路的不同两边，路中间有栏杆，因此这两个位置实际要走比较远才能到达。

小蓝的订单也是从某两个路口间的中点出发，到某两个路口间的中点结束。小蓝必须按照给定的顺序处理订单，而且一个时刻只能处理一个订单，不能图省时间而同时接两位乘客，也不能揷队完成后面的订单。

小蓝只对 $L$ 市比较熟，因此他只会在给定的 $n$ 条东西向道路和 $m$ 条南北向道路上行驶，而且不会驶出 $H_{1}, H_{n}, S_{1}, S_{m}$ 这几条道路所确定的矩形区域 (可 以到边界。

小蓝行车速度一直为 $1$，乘客上下车的时间忽略不计。

请问，小蓝最早什么时候能完成所有订单回到家。

inputFormat:
输入第一行包含两个整数 $n, m$，表示东西向道路的数量和南北向道路的数 量。

第二行包含 $n-1$ 个整数 $h_{1}, h_{2}, \cdots, h_{n-1}$ 。

第三行包含 $m-1$ 个整数 $w_{1}, w_{2}, \cdots, w_{m-1}$ 。

接下来 $n$ 行, 每行 $m$ 个整数，描述每个路口南北向绿灯的时间，其中的第 $i$ 行第 $j$ 列表示 $g_{i j}$ 。

接下来 $n$ 行, 每行 $m$ 个整数，描述每个路口东西向绿灯的时间，其中的第 $i$ 行第 $j$ 列表示 $r_{i j}$ 。

接下来一行包含四个整数 $x_{1}, y_{1}, x_{2}, y_{2}$，表示小蓝家的位置在路口 $\left(x_{1}, y_{1}\right)$ 到路口 $\left(x_{2}, y_{2}\right)$ 之间的道路中点的右侧。

接下来一行包含一个整数 $q$，表示订单数量。

接下来 $q$ 行，每行描述一个订单，其中第 $i$ 行包含八个整数 $x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2}$，$x_{i 3}, y_{i 3}, x_{i 4}, y_{i 4}$，表示第 $i$ 个订单的起点为路口 $\left(x_{i 1}, y_{i 1}\right)$ 到路口 $\left(x_{i 2}, y_{i 2}\right)$ 之间的道 路中点的右侧，第 $i$ 个订单的终点为路口 $\left(x_{i 3}, y_{i 3}\right)$ 到路口 $\left(x_{i 4}, y_{i 4}\right)$ 之间的道路中 点的右侧。

outputFormat: 输出一个实数，表示小蓝完成所有订单最后回到家的最早时刻。四舍五入保留一位小数。

hint:
**【样例说明】**

蓝有一个订单, 他的行车路线如下图所示。其中 $\mathrm{H}$ 表示他家的位置, $\mathrm{S}$ 表示订单的起点, $\mathrm{T}$ 表示订单的终点。小小明在最后回家时要在直行的红绿灯路 口等绿灯, 等待时间为 $20$。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-15.jpg)

**【评测用例规模与约定】**

对于 $20 \%$ 的评测用例, $1 \leq n, m \leq 5,1 \leq q \leq 10$ 。

对于 $50 \%$ 的评测用例, $1 \leq n, m \leq 30,1 \leq q \leq 30$ 。

对于所有评测用例, $1 \leq n, m \leq 100,1 \leq q \leq 30,1 \leq h_{1}<h_{2}<\cdots<h_{n-1} \leq$ $100000,1 \leq w_{1}<w_{2}<\cdots<w_{m-1} \leq 100000,1 \leq g_{i j} \leq 1000,1 \leq r_{i j} \leq 1000$, 给定的路口一定合法。


title: [蓝桥杯 2020 国 ABC] 答疑

description:
有 $n$ 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。

一位同学答疑的过程如下:

1. 首先进入办公室，编号为 $i$ 的同学需要 $s_{i}$ 毫秒的时间。

2. 然后同学问问题老师解答，编号为 $i$ 的同学需要 $a_{i}$ 毫秒的时间。

3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。

4. 最后同学收拾东西离开办公室，需要 $e_{i}$ 毫秒的时间。一般需要 $10$ 秒、$20$ 秒或 $30$ 秒，即 $e_{i}$ 取值为 $10000$、$20000$ 或 $30000$。

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

答疑从 $0$ 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群里面发消息的时刻之和最小。

inputFormat:
输入第一行包含一个整数 $n$，表示同学的数量。

接下来 $n$ 行, 描述每位同学的时间。其中第 $i$ 行包含三个整数 $s_{i}, a_{i}, e_{i}$，意义如上所述。

outputFormat: 输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。


title: [蓝桥杯 2020 国 C] 补给

description:
小蓝是一个直升飞机驾驶员，他负责给山区的 $n$ 个村庄运送物资。

每个月，他都要到每个村庄至少一次，可以多于一次，将村庄需要的物资运送过去。

每个村庄都正好有一个直升机场，每两个村庄之间的路程都正好是村庄之间的直线距离。

由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过 $D$。每个直升机场都有加油站，可以给直升机加满油。

每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果方便，小蓝中途也可以经过总部来加油。

总部位于编号为 $1$ 的村庄。

请问，要完成一个月的任务，小蓝至少要飞行多长距离？

inputFormat:
输入的第一行包含两个整数 $n$，$D$，分别表示村庄的数量和单次飞行的距离。

接下来 $n$ 行描述村庄的位置，其中第 $i$ 行两个整数 $x_i$，$y_i$ 分别表示编号为 $i$ 的村庄的坐标。村庄 $i$ 和村庄 $j$ 之间的距离为 $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$。

outputFormat: 输出一行，包含一个实数，四舍五入保留正好 $2$ 位小数，表示答案。

hint:
对于所有数据，保证，$1\le n\le20,1\le x_i,y_i\le10^4,1\le D\le10^5$。

蓝桥杯 2020 年国赛 C 组 I 题。


title: [蓝桥杯 2020 国 A] 奇偶覆盖

description:
在平面内有一些矩形，它们的两条边都平行于坐标轴。

我们称一个点被某个矩形覆盖，是指这个点在矩形的内部或者边界上。

请问，被奇数个矩形覆盖和被偶数 $(\geq 2)$ 个矩形覆盖的点的面积分别是多少?

inputFormat:
输入的第一行包含一个整数 $n$，表示矩形的个数。

接下来 $n$ 行描述这些矩形，其中第 $i$ 行包含四个整数 $l_{i}, b_{i}, r_{i}, t_{i}$，表示矩形的两个对角坐标分别为 $\left(l_{i}, b_{i}\right),\left(r_{i}, t_{i}\right)$ 。

outputFormat:
输出两行。

第一行包含一个整数，表示被奇数个矩形覆盖的点的面积。

第二行包含一个整数，表示被偶数 $(\geq 2)$ 个矩形覆盖的点的面积。


title: [蓝桥杯 2020 国 A] 蓝跳跳

description:
小蓝制作了一个机器人，取名为蓝跳跳，因为这个机器人走路的时候基本靠跳跃。

蓝跳跳可以跳着走，也可以掉头。蓝跳跳每步跳的距离都必须是整数，每步可以跳不超过 $k$ 的长度。由于蓝跳跳的平衡性设计得不太好，如果连续两次都是跳跃，而且两次跳跃的距离都至少是 $p$，则蓝跳跳会摔倒，这是小蓝不愿意看到的。

小蓝接到一个特别的任务，要在一个长为 $L$ 舞台上展示蓝跳跳。小蓝要控制蓝跳跳从舞台的左边走到右边，然后掉头，然后从右边走到左边，然后掉头，然后再从左边走到右边，然后掉头，再从右边走到左边，然后掉头，如此往复。

为了让观者不至于太无趣，小蓝决定让蓝跳跳每次用不同的方式来走。小蓝将蓝跳跳每一步跳的距离记录下来，按顺序排成一列，显然这一列数每个都不超过 $k$ 且和是 $L$。这样走一趟就会出来一列数。如果两列数的长度不同，或者两列数中存在一个位置数值不同，就认为是不同的方案。

请问蓝跳跳在不摔倒的前提下，有多少种不同的方案从舞台一边走到另一边。

inputFormat: 输入一行包含三个整数 $k, p, L$。

outputFormat: 输出一个整数, 表示答案。答案可能很大, 请输出答案除以 $20201114$ 的余数。


title: [蓝桥杯 2020 国 B] 游园安排

description:
$\mathrm{L}$ 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 $\mathrm{L}$ 星球 游乐园的管理员。

为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟 $0$ 个或多个小写英文字母。游客可能重名。

小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。

一个名字 $A$ 小于另一个名字 $B$ 是指：存在一个整数 $i$，使得 $A$ 的前 $i$ 个字母与 $B$ 的前 $i$ 个字母相同，且 $A$ 的第 $i+1$ 个字母小于 $B$ 的第 $i+1$ 个字母。(如果 $A$ 不存在第 $i+1$ 个字母且 $B$ 存在第 $i+1$ 个字母, 也视为 $A$ 的第 $i+1$ 个字母小于 $B$ 的第 $i+1$ 个字母)

作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

inputFormat: 输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。

outputFormat: 按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。

samples: WoAiLanQiaobei AiLanQiaobei

hint:
对于 $20 \%$ 的评测数据, 输入的总长度不超过 $20$ 个字母。

对于 $50 \%$ 的评测数据, 输入的总长度不超过 $300$ 个字母。

对于 $70 \%$ 的评测数据, 输入的总长度不超过 $10000$ 个字母。

对于所有评测数据, 每个名字的长度不超过 $10$ 个字母, 输入的总长度不超过 $10^6$ 个字母。

蓝桥杯 2020 年国赛 B 组 G 题。


title: [蓝桥杯 2020 国 B] 质数行者

background: 小蓝在玩一个叫质数行者的游戏。

description:
游戏在一个 $n \times m \times w$ 的立体方格图上进行, 从北到南依次标号为第 $1$ 行到 第 $n$ 行, 从西到东依次标号为第 $1$ 列到第 $m$ 列, 从下到上依次标号为第 $1$ 层到 第 $w$ 层。

小蓝要控制自己的角色从第 $1$ 行第 $1$ 列第 $1$ 层移动到第 $n$ 行第 $m$ 列第 $w$ 层。每一步, 他可以向东走质数格、向南走质数格或者向上走质数格。每走到 一个位置, 小蓝的角色要稍作停留。

在游戏中有两个陷阱, 分别为第 $r_{1}$ 行第 $c_{1}$ 列第 $h_{1}$ 层和第 $r_{2}$ 行第 $c_{2}$ 列第 $h_{2}$ 层。这两个陷阱的位置可以跨过, 但不能停留。也就是说, 小蓝不能控制角 色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。

小蓝最近比较清闲, 因此他想用不同的走法来完成这个游戏。所谓两个走法不同, 是指小蓝稍作停留的位置集合不同。

请帮小蓝计算一下，他总共有多少种不同的走法。

提示：请注意内存限制, 如果你的程序运行时超过内存限制将不得分。

inputFormat:
输入第一行包含两个整数 $n, m, w$, 表示方格图的大小。

第二行包含 $6$ 个整数, $r_{1}, c_{1}, h_{1}, r_{2}, c_{2}, h_{2}$ ，表示陷阱的位置。

outputFormat: 输出一行, 包含一个整数, 表示走法的数量。答案可能非常大, 请输出答 案除以 $1000000007$（即 $10^9+7$） 的余数。


title: [蓝桥杯 2020 国 C] 天干地支

description:
古代中国使用天干地支来记录当前的年份。

天干一共有十个，分别为：甲（jiǎ）、乙（yǐ）、丙（bǐng）、丁（dīng）、戊
（wù）、己（jǐ）、庚（gēng）、辛（xīn）、壬（rén）、癸（guǐ）。

地支一共有十二个，分别为：子（zǐ）、丑（chǒu）、寅（yín）、卯（mǎo）、辰（chén）、巳（sì）、午（wǔ）、未（wèi）、申（shēn）、酉（yǒu）、戌（xū）、亥（hài）。

将天干和地支连起来，就组成了一个天干地支的年份，例如：甲子。2020 年是庚子年。

每过一年，天干和地支都会移动到下一个。例如 2021 年是辛丑年。

每过 60 年，天干会循环 6 轮，地支会循环 5 轮，所以天干地支纪年每 60年轮回一次。例如 1900 年，1960 年，2020 年都是庚子年。

给定一个公元纪年的年份，请输出这一年的天干地支年份。

inputFormat: 输入一行包含一个正整数，表示公元年份。

outputFormat: 输出一个拼音，表示天干地支的年份，天干和地支都用小写拼音表示（不表示声调），之间不要加入任何多余的字符。

hint:
对于所有评测用例，输入的公元年份为不超过 $9999$ 的正整数。

蓝桥杯 2020 年国赛 C 组 F 题。


title: [蓝桥杯 2020 国 C] 重复字符串

description:
如果一个字符串 $S$ 恰好可以由某个字符串重复 $K$ 次得到，我们就称 $S$ 是 $K$ 次重复字符串。例如 `abcabcabc` 可以看作是 `abc` 重复 $3$ 次得到，所以 `abcabcabc` 是 $3$ 次重复字符串。

同理 `aaaaaa` 既是 $2$ 次重复字符串、又是 $3$ 次重复字符串和 $6$ 次重复字符串。

现在给定一个字符串 $S$，请你计算最少要修改其中几个字符，可以使 $S$ 变为一个 $K$ 次字符串？

inputFormat:
输入第一行包含一个整数 $K$。

第二行包含一个只含小写字母的字符串 $S$。

outputFormat: 输出一个整数代表答案。如果 $S$ 无法修改成 $K$ 次重复字符串，输出 $−1$。

hint:
其中，$1 \le K \le 10^5$，$1 \le |S| \le 10^5$。其中 $∣S∣$ 表示 $S$ 的 长度。

蓝桥杯 2020 年国赛 C 组 G 题。


title: [蓝桥杯 2021 省 A] 填空问题

description:
## 试题 A：卡片

### 【问题描述】

小蓝有很多数字卡片，每张卡片上都是数字 $0$  到 $9$ 。

小蓝准备用这些卡片来拼一些数，他想从 $1$  开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从 $1$  拼到多少。

例如，当小蓝有 $30$  张卡片，其中 $0$  到 $9$  各 $3$  张，则小蓝可以拼出 $1$  到 $10$ ，但是拼 $11$  时卡片 $1$  已经只有一张了，不够拼出 $11$ 。

现在小蓝手里有 $0$  到 $9$  的卡片各 $2021$  张，共 $20210$  张，请问小蓝可以从 $1$  拼到多少?

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：直线

### 【问题描述】

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。

给定平面上 $2 \times 3$ 个整点 $\{(x,y) \mid 0 \leq x<2,0 \leq y<3,x \in \mathbb{Z},y \in \mathbb{Z}\}$，即横坐标是 $0$  到 $1$  (包含 $0$  和 $1$ ) 之间的整数、纵坐标是 $0$  到 $2$  (包含 $0$  和 $2$ ) 之间的整数的点。这些点一共确定了 $11$  条不同的直线。

给定平面上 $20 \times 21$ 个整点 $\{(x,y) \mid 0 \leq x<20,0 \leq y<21,x \in \mathbb{Z},y \in \mathbb{Z}\}$，即横坐标是 $0$  到 $19$  (包含 $0$  和 $19$ ) 之间的整数、纵坐标是 $0$  到 $20$  (包含 $0$  和 $20$ ) 之间的整数的点。请问这些点一共确定了多少条不同的直线。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：货物摆放

### 【问题描述】

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 $n$ 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、 宽、高。

小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 $L 、 W 、 H$ 的货物，满足 $n=L \times W \times H$。

给定 $n$，请问有多少种堆放货物的方案满足要求。

例如，当 $n=4$ 时，有以下 $6$  种方案：$1 \times 1 \times 4 、 1 \times 2 \times 2 、 1 \times 4 \times 1 、 2 \times 1 \times 2$ 、 $2 \times 2 \times 1 、 4 \times 1 \times 1$

请问，当 $n=2021041820210418$ (注意有 $16$  位数字) 时，总共有多少种方案?

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：路径

### 【问题描述】

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 $2021$  个结点组成，依次编号 $1$  至 $2021$ 。

对于两个不同的结点 $a,b$，如果 $a$ 和 $b$ 的差的绝对值大于 $21$ ，则两个结点之间没有边相连; 如果 $a$ 和 $b$ 的差的绝对值小于等于 $21$ ，则两个点之间有一条长度为 $a$ 和 $b$ 的最小公倍数的无向边相连。

例如：结点 $1$  和结点 $23$  之间没有边相连; 结点 $3$  和结点 $24$  之间有一条无向边，长度为 $24$  ; 结点 $15$  和结点 $25$  之间有一条无向边，长度为 $75$ 。

请计算，结点 $1$  和结点 $2021$  之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：回路计数

### 【问题描述】

蓝桥学院由 $21$  栋教学楼组成，教学楼编号 $1$  到 $21$ 。对于两栋教学楼 $a$ 和 $b$，当 $a$ 和 $b$ 互质时，$a$ 和 $b$ 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路)，请问他有多少种不同的访问方案? 两个访问方案不同是指存在某个 $i$，小蓝在两个访问方法中访问完教学楼 $i$ 后访问了不同的教学楼。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2021 省 B] 填空问题

description:
## 试题 A ：空间

### 【问题描述】

小蓝准备用 $256 \mathrm{MB}$ 的内存空间开一个数组，数组的每个元素都是 $32$  位二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 $256 \mathrm{MB}$ 的空间可以存储多少个 $32$  位二进制整数?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B ：卡片

### 【问题描述】

小蓝有很多数字卡片，每张卡片上都是数字 $0$  到 $9$ 。

小蓝准备用这些卡片来拼一些数，他想从 $1$  开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从 $1$  拼到多少。

例如，当小蓝有 $30$  张卡片，其中 $0$  到 $9$  各 $3$  张，则小蓝可以拼出 $1$  到 $10$ ，但是拼 $11$  时卡片 $1$  已经只有一张了，不够拼出 $11$ 。

现在小蓝手里有 $0$  到 $9$  的卡片各 $2021$  张，共 $20210$  张，请问小蓝可以从 $1$  拼到多少?

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：直线

### 【问题描述】

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。

给定平面上 $2 \times 3$ 个整点 $\{(x,y) \mid 0 \leq x<2,0 \leq y<3,x \in \mathbb{Z},y \in \mathbb{Z}\}$，即横坐标是 $0$  到 $1$  (包含 $0$  和 $1$ ) 之间的整数、纵坐标是 $0$  到 $2$  (包含 $0$  和 $2$  ) 之间的整数的点。这些点一共确定了 $11$  条不同的直线。

给定平面上 $20 \times 21$ 个整点 $\{(x,y) \mid 0 \leq x<20,0 \leq y<21,x \in \mathbb{Z},y \in \mathbb{Z}\}$，即横坐标是 $0$  到 $19$  (包含 $0$  和 $19$ ) 之间的整数、纵坐标是 $0$  到 $20$  (包含 $0$  和 $20$ ) 之间的整数的点。请问这些点一共确定了多少条不同的直线。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D ：货物摆放

### 【问题描述】

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 $n$ 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、 宽、高。

小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 $L 、 W 、 H$ 的货物，满足 $n=L \times W \times H$。

给定 $n$，请问有多少种堆放货物的方案满足要求。

例如，当 $n=4$ 时，有以下 $6$  种方案：$1 \times 1 \times 4 、 1 \times 2 \times 2 、 1 \times 4 \times 1 、 2 \times 1 \times 2$ 、 $2 \times 2 \times 1 、 4 \times 1 \times 1$

请问，当 $n=2021041820210418$ (注意有 $16$  位数字) 时，总共有多少种方案?

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E ：路径

### 【问题描述】

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 $2021$  个结点组成，依次编号 $1$  至 $2021$ 。

对于两个不同的结点 $a,b$，如果 $a$ 和 $b$ 的差的绝对值大于 $21$ ，则两个结点之间没有边相连; 如果 $a$ 和 $b$ 的差的绝对值小于等于 $21$ ，则两个点之间有一条长度为 $a$ 和 $b$ 的最小公倍数的无向边相连。

例如：结点 $1$  和结点 $23$  之间没有边相连; 结点 $3$  和结点 $24$  之间有一条无向边，长度为 $24$  ; 结点 $15$  和结点 $25$  之间有一条无向边，长度为 $75$ 。

请计算，结点 $1$  和结点 $2021$  之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2021 省 AB] 砝码称重

description:
你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_{1}, W_{2}, \cdots, W_{N}$ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

inputFormat:
输入的第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数: $W_{1}, W_{2}, W_{3}, \cdots, W_{N}$ 。

outputFormat: 输出一个整数代表答案。


title: [蓝桥杯 2021 省 A] 异或数列

description:
Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 $a$ 和 $b$, 有一个给定的长度为 $n$ 的公共数列 $X_{1}, X_{2}, \cdots, X_{n}$ 。

Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种:

选项 1: 从数列中选一个 $X_{i}$ 给 Alice 的数异或上, 或者说令 $a$ 变为 $a \oplus X_{i}$ 。（其中 $\oplus$ 表示按位异或）

选项 2: 从数列中选一个 $X_{i}$ 给 Bob 的数异或上，或者说令 $b$ 变为 $b \oplus X_{i}$ 。

每个数 $X_{i}$ 都只能用一次, 当所有 $X_{i}$ 均被使用后（$n$ 轮后）游戏结束。游戏结束时, 拥有的数比较大的一方获胜，如果双方数值相同，即为平手。

现在双方都足够聪明，都采用最优策略，请问谁能获胜?

inputFormat:
每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 $T$，表示询问数。

接下来 $T$ 行每行包含一组询问。其中第 $i$ 行的第一个整数 $n_{i}$ 表示数列长度，随后 $n_{i}$ 个整数 $X_{1}, X_{2}, \cdots, X_{n_{i}}$ 表示数列中的每个数。

outputFormat:
输出 $T$ 行，依次对应每组询问的答案。

每行包含一个整数 $1$、$0$ 或 $-1$ 分别表示 Alice 胜、平局或败。

hint:
对于所有评测用例, $1 \leq T \leq 2\times 10^5,1 \leq \sum\limits_{i=1}^{T} n_{i} \leq 2\times10^5,0 \leq X_{i}<2^{20}$ 。

蓝桥杯 2021 第一轮省赛 A 组 G 题。


title: [蓝桥杯 2021 省 A] 左孩子右兄弟

description:
对于一棵多叉树，我们可以通过“左孩子右兄弟”表示法，将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含 $N$ 个结点的多叉树，结点从 $1$ 至 $N$ 编号，其中 $1$ 号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过"左孩子右兄弟"表示法转化成的二叉树，高度最高是多少。（只有根结点这一个结点的树高度为 $0$）

例如如下的多叉树：

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_d8f144a59f4c0ce9322ag-11.jpg)

可能有以下 $3$ 种 (这里只列出 $3$ 种, 并不是全部) 不同的 “左孩子右兄弟” 表示:

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_d8f144a59f4c0ce9322ag-12.jpg)

其中最后一种高度最高, 为 $4$。

inputFormat:
输入的第一行包含一个整数 $N$ 。

以下 $N-1$ 行, 每行包含一个整数, 依次表示 $2$ 至 $N$ 号结点的父结点编号。

hint:
对于 $30 \%$ 的评测用例，$1 \leq N \leq 20$;

对于所有评测用例，$1 \leq N \leq 10^5$ 。

蓝桥杯 2021 第一轮省赛 A 组 H 题。


title: [蓝桥杯 2021 省 AB] 括号序列

description:
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列 `((()`，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：`()()()` 、`()(())`、`(())()`、`(()())` 和 `((()))`。

inputFormat: 输入一行包含一个字符串 $s$，表示给定的括号序列，序列中只有左括号和右括号。

outputFormat: 输出一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$（即 $10^{9}+7$）的余数。

hint:
对于 $40 \%$ 的评测用例，$|s| \leq 200$。

对于所有评测用例，$1 \leq|s| \leq 5000$。

蓝桥杯 2021 第一轮省赛 A 组 I 题（B 组 J 题）。


title: [蓝桥杯 2021 省 A] 分果果

description:
小蓝要在自己的生日宴会上将 $n$ 包糖果分给 $m$ 个小朋友。每包糖果都要分出去，每个小朋友至少要分一包，也可以分多包。

小蓝已经提前将糖果准备好了，为了在宴会当天能把糖果分得更平均一些，小蓝要先计算好分配方案。

小蓝将糖果从 $1$ 到 $n$ 编号, 第 $i$ 包糖果重 $w_{i}$ 。小朋友从 $1$ 到 $m$ 编号。每个小朋友只能分到编号连续的糖果。小蓝想了很久没想出合适的分配方案使得每个小朋友分到的糖果差不多重。因此需要你帮他一起想办法。为了更好的分配糖果，他可以再买一些糖果，让某一些编号的糖果有两份。当某个编号的糖果有两份时，一个小朋友最多只能分其中的一份。

请找一个方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，请输出这个差。

例如，小蓝现在有 5 包糖果, 重量分别为 $6,1,2,7,9$，如果小蓝要分给两个小朋友，则他可以将所有糖果再买一份，两个小朋友都分到 $1$ 至 $5$ 包糖果，重量都是 $25$, 差为 $0$。

再如，小蓝现在有 $5$ 包糖果, 重量分别为 $6,1,2,7,9$，如果小蓝要分给三个小朋友，则他可以将第 $3$ 包糖果再买一份，第一个小朋友分 $1$ 至 $3$ 包，第二个小朋友分 $3$ 至 $4$ 包，第三个小朋友分第 $5$ 包，每个小朋友分到的重量都是 $9$，差为 $0$。

再如, 小蓝现在有 5 包糖果, 重量分别为 $6,1,2,7,9$, 如果小蓝要分给四个小朋友，则他可以将第 $3$ 包和第 $5$ 包糖果再买一份, 仍然可以每个小朋友分到的重量都是 $9$，差为 $0$。

再如, 小蓝现在有 $5$ 包糖果, 重量分别为 $6,1,2,7,9$, 如果小蓝要分给五个小朋友, 则他可以将第 $4$ 包和第 $5$ 包糖果再买一份, 第一个小朋友分第 $1$ 至 $2$ 包重量为 $7$ , 第二个小朋友分第 $3$ 至 $4$ 包重量为 $9$, 第三个小朋友分第 $4$ 包重 量为 $7$, 第四个和第五个小朋友都分第 $5$ 包重量为 $9$。差为 $2$。

inputFormat:
输入第一行包含两个整数 $n$ 和 $m$, 分别表示糖果包数和小朋友数量。

第二行包含 $n$ 个整数 $w_{1}, w_{2}, \cdots, w_{n}$, 表示每包糖果的重量。

outputFormat: 输出一个整数, 表示在最优情况下小朋友分到的糖果的最大重量和最小重量的差。

hint:
对于 $30 \%$ 的评测用例, $1 \leq n \leq 10,1 \leq m \leq 10,1 \leq w_{i} \leq 10$;

对于 $60 \%$ 的评测用例, $1 \leq n \leq 30,1 \leq m \leq 20,1 \leq w_{i} \leq 30$;

对于所有评测用例, $1 \leq n \leq 100,1 \leq m \leq 50,1 \leq w_{i} \leq 100$ 。在评测数据 中, $w_{i}$ 随机生成, 在某个区间均匀分布。

蓝桥杯 2021 第一轮省赛 A 组 J 题。


title: [蓝桥杯 2021 省 B] 双向排序

description:
给定序列 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)=(1,2, \cdots, n)$，即 $a_{i}=i$ 。

小蓝将对这个序列进行 $m$ 次操作，每次可能是将 $a_{1}, a_{2}, \cdots, a_{q_{i}}$ 降序排列，或者将 $a_{q_{i}}, a_{q_{i}+1}, \cdots, a_{n}$ 升序排列。

请求出操作完成后的序列。

inputFormat:
输入的第一行包含两个整数 $n, m$，分别表示序列的长度和操作次数。

接下来 $m$ 行描述对序列的操作，其中第 $i$ 行包含两个整数 $p_{i}, q_{i}$ 表示操作类型和参数。

当 $p_{i}=0$ 时，表示将 $a_{1}, a_{2}, \cdots, a_{q_{i}}$ 降序排列;

当 $p_{i}=1$ 时，表示将 $a_{q_{i}}, a_{q_{i}+1}, \cdots, a_{n}$ 升序排列。

outputFormat: 输出一行，包含 $n$ 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

hint:
**【样例说明】**

原数列为 $(1,2,3)$。

第 1 步后为 $(3,2,1)$。

第 2 步后为 $(3,1,2)$。

第 3 步后为 $(3,1,2)$。与第 2 步操作后相同, 因为前两个数已经是降序了。

**【评测用例规模与约定】**

对于 $30 \%$ 的评测用例, $n, m \leq 1000$;

对于 $60 \%$ 的评测用例, $n, m \leq 5000$;

对于所有评测用例, $1 \leq n, m \leq 10^5,0 \leq p_{i} \leq 1,1 \leq q_{i} \leq n$ 。

蓝桥杯 2021 第一轮省赛 B 组 I 题。


title: [蓝桥杯 2021 省 B] 时间显示

description:
小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要 显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

inputFormat: 输入一行包含一个整数，表示时间。

outputFormat: 输出时分秒表示的当前时间, 格式形如 $\mathrm{HH}: \mathrm{MM}: \mathrm{SS}$, 其中 $\mathrm{HH}$ 表示时, 值 为 $0$ 到 $23, \mathrm{MM}$ 表示分。值为 $0$ 到 $59$。$\mathrm{SS}$ 表示秒, 值为 $0$ 到 $59$。时、分、秒不足两位时补前导 `0` 。

hint:
对于所有评测用例, 给定的时间为不超过 $10^{18}$ 的正整数。

蓝桥杯 2021 第一轮省赛 B 组 F 题。


title: [蓝桥杯 2021 省 B] 杨辉三角形

description:
下面的图形是著名的杨辉三角形:

![](https://cdn.mathpix.com/cropped/2022_09_29_08f7179868ee6cb62df7g-11.jpg?height=350&width=704&top_left_y=944&top_left_x=676)

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

$1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, \ldots$

给定一个正整数 $N$，请你输出数列中第一次出现 $N$ 是在第几个数。

inputFormat: 输入一个整数 $N$ 。

hint:
对于 $20 \%$ 的评测用例, $1 \leq N \leq 10$;

对于所有评测用例, $1 \leq N \leq 10^9$ 。

蓝桥杯 2021 第一轮省赛 B 组 H 题。


title: [蓝桥杯 2021 省 A2] 填空问题

description:
## 试题 A ：双阶乘

### 【问题描述】

一个正整数的双阶乘，表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。$n$ 的双阶乘用 $n ! !$ 表示。

例如:

$3 ! !=3 \times 1=3$。

$8 ! !=8 \times 6 \times 4 \times 2=384$。

$11 ! !=11 \times 9 \times 7 \times 5 \times 3 \times 1=10395$。

请问，$2021 ! !$ 的最后 $5$  位（这里指十进制位）是多少?

注意：$2021 ! !=2021 \times 2019 \times \cdots \times 5 \times 3 \times 1$。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：格点

### 【问题描述】

如果一个点 $(x,y)$ 的两维坐标都是整数，即 $x \in \mathbb{Z}$ 且 $y \in \mathbb{Z}$，则称这个点为一个格点。

如果一个点 $(x,y)$ 的两维坐标都是正数，即 $x>0$ 且 $y>0$，则称这个点在第一象限。

请问在第一象限的格点中，有多少个点 $(x,y)$ 的两维坐标乘积不超过 $2021$ ，即 $x \cdot y \leq 2021$。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：整数分解

### 【问题描述】

将 $3$  分解成两个正整数的和，有两种分解方法，分别是 $3=1+2$ 和 $3=2+1$。注意顺序不同算不同的方法。

将 $5$  分解成三个正整数的和，有 $6$  种分解方法，它们是 $1+1+3=1+2+2=$ $1+3+1=2+1+2=2+2+1=3+1+1$。

请问，将 $2021$  分解成五个正整数的和，有多少种分解方法?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：城邦

### 【问题描述】

小蓝国是一个水上王国，有 $2021$  个城邦，依次编号 $1$  到 $2021$ 。在任意两个城邦之间，都有一座桥直接连接。

为了庆祝小蓝国的传统节日，小蓝国政府准备将一部分桥装饰起来。

对于编号为 $a$ 和 $b$ 的两个城邦，它们之间的桥如果要装饰起来，需要的费用如下计算：找到 $a$ 和 $b$ 在十进制下所有不同的数位，将数位上的数字求和。

例如，编号为 $2021$  和 $922$  两个城邦之间，千位、百位和个位都不同，将这些数位上的数字加起来是 $(2+0+1)+(0+9+2)=14$。注意 $922$  没有千位，千位看成 $0$ 。

为了节约开支，小蓝国政府准备只装饰 $2020$  座桥，并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。

请问，小蓝国政府至少要花多少费用才能完成装饰。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：游戏

### 【问题描述】

小蓝闲着无聊开始自己和自己做游戏。

首先规定一个正整数 $n$。

他首先在纸上写下一个 $1$  到 $n$ 之间的数。在之后的每一步，小蓝都可以选择上次写的数的一个约数 (不能选上一个写过的数)，写在纸上。直到最终小蓝写下 $1$ 。

小蓝可能有多种游戏的方案。

例如，当 $n=6$ 时，小蓝有 $9$  种方案：(1)，$(2,1),(3,1),(4,1),(4,2,1),(5,1)$，$(6,1),(6,2,1),(6,3,1)$。

请问，当 $n=20210509$ 时有多少种方案?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

本题的答案比较大，如果你编程解决本题，请注意使用合适的数据类型。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
        "The answer of task C", // 双引号中替换为 C 题的答案
        "The answer of task D", // 双引号中替换为 D 题的答案
        "The answer of task E", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2021 省 B2] 填空问题

description:
## 试题 A:求余

### 【问题描述】

在 $\mathrm{C} / \mathrm{C}++/ \mathrm{Java} /$ Python 等语言中，使用。表示求余，请问 $2021 \% 20$ 的值是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：双阶乘

### 【问题描述】

一个正整数的双阶乘，表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。$n$ 的双阶乘用 $n ! !$ 表示。

例如:

$3 ! !=3 \times 1=3$。

$8 ! !=8 \times 6 \times 4 \times 2=384$。

$11 ! !=11 \times 9 \times 7 \times 5 \times 3 \times 1=10395$。

请问，$2021 ! !$ 的最后 $5$  位（这里指十进制位）是多少?

注意：$2021 ! !=2021 \times 2019 \times \cdots \times 5 \times 3 \times 1$。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C：格点

### 【问题描述】

如果一个点 $(x,y)$ 的两维坐标都是整数，即 $x \in \mathbb{Z}$ 且 $y \in \mathbb{Z}$，则称这个点为一个格点。

如果一个点 $(x,y)$ 的两维坐标都是正数，即 $x>0$ 且 $y>0$，则称这个点在第一象限。

请问在第一象限的格点中，有多少个点 $(x,y)$ 的两维坐标乘积不超过 $2021$ ，即 $x \cdot y \leq 2021$。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：整数分解

### 【问题描述】

将 $3$  分解成两个正整数的和，有两种分解方法，分别是 $3=1+2$ 和 $3=2+1$。注意顺序不同算不同的方法。

将 $5$  分解成三个正整数的和，有 $6$  种分解方法，它们是 $1+1+3=1+2+2=$ $1+3+1=2+1+2=2+2+1=3+1+1$。

请问，将 $2021$  分解成五个正整数的和，有多少种分解方法?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：城邦

### 【问题描述】

小蓝国是一个水上王国，有 $2021$  个城邦，依次编号 $1$  到 $2021$ 。在任意两个城邦之间，都有一座桥直接连接。

为了庆祝小蓝国的传统节日，小蓝国政府准备将一部分桥装饰起来。

对于编号为 $a$ 和 $b$ 的两个城邦，它们之间的桥如果要装饰起来，需要的费用如下计算：找到 $a$ 和 $b$ 在十进制下所有不同的数位，将数位上的数字求和。

例如，编号为 $2021$  和 $922$  两个城邦之间，千位、百位和个位都不同，将这些数位上的数字加起来是 $(2+0+1)+(0+9+2)=14$。注意 $922$  没有千位，千位看成 $0$ 。

为了节约开支，小蓝国政府准备只装饰 $2020$  座桥，并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。

请问，小蓝国政府至少要花多少费用才能完成装饰。

提示：建议使用计算机编程解决问题。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2021 省 B2] 特殊年份

description:
今年是 2021 年，2021 这个数字非常特殊, 它的千位和十位相等, 个位比百位大 $1$，我们称满足这样条件的年份为特殊年份。

输入 $5$ 个年份，请计算这里面有多少个特殊年份。

inputFormat: 输入 $5$ 行，每行一个 $4$ 位十进制数（数值范围为 $1000$ 至 $9999$)，表示一个年份。

outputFormat: 输出一个整数，表示输入的 $5$ 个年份中有多少个特殊年份。

hint:
**【样例说明】**

2021 和 9899 是特殊年份，其它不是特殊年份。

蓝桥杯 2021 第二轮省赛 B 组 F 题。


title: [蓝桥杯 2021 省 AB2] 小平方

description:
小蓝发现，对于一个正整数 $n$ 和一个小于 $n$ 的正整数 $v$，将 $v$ 平方后对 $n$ 取余可能小于 $n$ 的一半，也可能大于等于 $n$ 的一半。

请问，在 $1$ 到 $n-1$ 中, 有多少个数平方后除以 $n$ 的余数小于 $n$ 的一半。

例如，当 $n=4$ 时，$1,2,3$ 的平方除以 $4$ 的余数都小于 $4$ 的一半。

又如，当 $n=5$ 时, $1$，$4$ 的平方除以 $5$ 的余数都是 $1$，小于 $5$ 的一半。而 $2$，$3$ 的平方除以 $5$ 的余数都是 $4$, 大于等于 $5$ 的一半。

inputFormat: 输入一行包含一个整数 $n$ 。

outputFormat: 输出一个整数，表示满足条件的数的数量。

hint:
对于所有评测用例, $1 \leq n \leq 10000$。

蓝桥杯 2021 第二轮省赛 A 组 F 题（B 组 G 题）。


title: [蓝桥杯 2021 省 AB2] 完全平方数

description:
一个整数 $a$ 是一个完全平方数，是指它是某一个整数的平方，即存在一个 整数 $b$，使得 $a=b^{2}$ 。

给定一个正整数 $n$，请找到最小的正整数 $x$，使得它们的乘积是一个完全平方数。

inputFormat: 输入一行包含一个正整数 $n$。

outputFormat: 输出找到的最小的正整数 $x$。

hint:
对于 $30 \%$ 的评测用例, $1 \leq n \leq 1000$，答案不超过 $1000$。

对于 $60 \%$ 的评测用例，$1 \leq n \leq 10^{8}$，答案不超过 $10^{8}$。

对于所有评测用例，$1 \leq n \leq 10^{12}$，答案不超过 $10^{12}$。

蓝桥杯 2021 第二轮省赛 A 组 G 题（B 组 H 题）。


title: [蓝桥杯 2021 省 AB2] 负载均衡

description:
有 $n$ 台计算机，第 $i$ 台计算机的运算能力为 $v_{i}$ 。

有一系列的任务被指派到各个计算机上，第 $i$ 个任务在 $a_{i}$ 时刻分配，指定计算机编号为 $b_{i}$, 耗时为 $c_{i}$ 且算力消耗为 $d_{i}$。如果此任务成功分配，将立刻开始运行, 期间持续占用 $b_{i}$ 号计算机 $d_{i}$ 的算力, 持续 $c_{i}$ 秒。

对于每次任务分配，如果计算机剩余的运算能力不足则输出 $-1$，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。

inputFormat:
输入的第一行包含两个整数 $n, m$，分别表示计算机数目和要分配的任务数。

第二行包含 $n$ 个整数 $v_{1}, v_{2}, \cdots v_{n}$，分别表示每个计算机的运算能力。

接下来 $m$ 行每行 $4$ 个整数 $a_{i}, b_{i}, c_{i}, d_{i}$，意义如上所述。数据保证 $a_{i}$ 严格递增，即 $a_{i}<a_{i+1}$ 。

outputFormat: 输出 $m$ 行，每行包含一个数，对应每次任务分配的结果。

hint:
**【样例说明】**

时刻 $1$，第 $1$ 个任务被分配到第 $1$ 台计算机，耗时为 $5$，这个任务时刻 $6$ 会结束, 占用计算机 $1$ 的算力 $3$。

时刻 $2$，第 $2$ 个任务需要的算力不足，所以分配失败了。

时刻 $3$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，剩余算力不足 $3$，所以失败。

时刻 $4$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，但剩余算力足够，分配后剩余算力 $1$。

时刻 $5$，第 $1$ 个计算机仍然正在计算第 $1$，$4$ 个任务，剩余算力不足 $4$，失败。

时刻 $6$，第 $1$ 个计算机仍然正在计算第 $4$ 个任务，剩余算力足够，且恰好用完。

**【评测用例规模与约定】**

对于 $20 \%$ 的评测用例, $n, m \leq 200$。

对于 $40 \%$ 的评测用例, $n, m \leq 2000$。

对于所有评测用例, $1 \leq n, m \leq 2\times 10^5,1 \leq a_{i}, c_{i}, d_{i}, v_{i} \leq 10^{9}, 1 \leq b_{i} \leq n$。

蓝桥杯 2021 第二轮省赛 A 组 H 题（B 组 I 题）。


title: [蓝桥杯 2021 省 AB2] 国际象棋

description:
众所周知， “八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹末尽。作为一个国际象棋迷，他想研究在 $N \times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 $1000000007$ (即 $\left.10^{9}+7\right)$ 的余数。

如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字, 位于 $(x, y)$ 格的马（第 $x$ 行第 $y$ 列）可以攻击 $(x+1, y+2),(x+1, y-2),(x-1, y+2),(x-1, y-2),(x+2, y+1),(x+2, y-1),(x-2, y+1),(x-2, y-1)$ 共 $8$ 个 格子。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_68f9131d5c14c1f27e68g-12.jpg)

inputFormat: 输入一行包含三个正整数 $N, M, K$, 分别表示棋盘的行数、列数和马的个数。

outputFormat: 输出一个整数，表示摆放的方案数除以 $1000000007\left(\right.$ 即 $\left.10^{9}+7\right)$ 的余数。

hint:
对于 $5 \%$ 的评测用例, $K=1$;

对于另外 $10 \%$ 的评测用例, $K=2$;

对于另外 $10 \%$ 的评测用例, $N=1$;

对于另外 $20 \%$ 的评测用例, $N, M \leq 6, K \leq 5$;

对于另外 $25 \%$ 的评测用例, $N \leq 3, M \leq 20 ， K \leq 12$;

对于所有评测用例, $1 \leq N \leq 6,1 \leq M \leq 100,1 \leq K \leq 20$。

蓝桥杯 2021 第二轮省赛 A 组 I 题（B 组 J 题）。


title: [蓝桥杯 2021 省 A2] 完美序列

description:
一个序列中取出一些元素按照原来的顺序排列成新的序列称为该序列的一个子序列。子序列的价值为子序列中所有元素的和。

如果一个序列是单调递减的，而且除了第一个数以外的任何一个数都是上一个数的因数，则称这个序列为一个完美序列。

一个序列中的一个子序列如果是完美序列，则称为该序列的一个完美子序列。一个序列的最长完美子序列长度，称为该序列的完美长度。

给定正整数 $n$，$1$ 至 $n$ 的所有排列的完美长度的最大值，称为 $n$ 阶最大完美长度。

给定正整数 $n$，请求出 $1$ 至 $n$ 的所有排列中长度正好为 $n$ 阶最大完美长度的所有完美子序列的价值的和。

inputFormat:
每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 $T$, 表示询问数。

接下来 $T$ 行, 每行包含一个整数 $n$, 表示一个给定的 $n$ 。

outputFormat:
输出 $T$ 行，依次对应每组询问的答案。

每行包含一个整数，表示对应的答案除以 $1000000007$（即 $10^{9}+7$）的余数。


title: [蓝桥杯 2021 国 A] 填空问题

description:
## 试题 A ：纯质数

### 【问题描述】

如果一个正整数只有 $1$  和它本身两个约数，则称为一个质数（又称素数）。

前几个质数是：$2,3,5,7,11,13,17,19,23,29,31,37,\cdots$。

如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：2,$3,5,7,23,37$ 都是纯质数，而 $11,13,17,19,29,31$ 不是纯质数。当然 $1,4,35$ 也不是纯质数。

请问，在 $1$  到 $20210605$  中，有多少个纯质数?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：完全日期

### 【问题描述】

如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。

例如：2021 年 $6$  月 $5$  日的各位数字之和为 $2+0+2+1+6+5=16$，而 $16$  是一个完全平方数，它是 $4$  的平方。所以 $2021$  年 $6$  月 $5$  日是一个完全日期。

例如：2021 年 $6$  月 $23$  日的各位数字之和为 $2+0+2+1+6+2+3=16$，是一个完全平方数。所以 $2021$  年 $6$  月 $23$  日也是一个完全日期。

请问，从 $2001$  年 $1$  月 $1$  日到 $2021$  年 $12$  月 $31$  日中，一共有多少个完全日期?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：最小权值

### 【问题描述】

对于一棵有根二叉树 $T$，小蓝定义这棵树中结点的权值 $W(T)$ 如下:

空子树的权值为 $0$ 。

如果一个结点 $v$ 有左子树 $L$，右子树 $R$，分别有 $C(L)$ 和 $C(R)$ 个结点，则

$W(v)=1+2 W(L)+3 W(R)+(C(L))^{2} C(R)$。

树的权值定义为树的根结点的权值。

小蓝想知道，对于一棵有 $2021$  个结点的二叉树，树的权值最小可能是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：覆盖

### 【问题描述】

小蓝有一个国际象棋的棋盘，棋盘的大小为 $8 \times 8$，即由 $8$  行 $8$  列共 $64$  个方格组成。棋盘上有美丽的图案，因此棋盘旋转后与原来的棋盘不一样。

小蓝有很多相同的纸片，每张纸片正好能覆盖棋盘的两个相邻方格。小蓝想用 $32$  张纸片正好将棋盘完全覆盖，每张纸片都覆盖其中的两个方格。

小蓝发现，有很多种方案可以实现这样的覆盖。如果棋盘比较小，方案数相对容易计算，比如当棋盘是 $2 \times 2$ 时有两种方案，当棋盘是 $4 \times 4$ 时有 $36$  种方案。但是小蓝算不出他自己的这个 $8 \times 8$ 的棋盘有多少种覆盖方案。

请帮小蓝算出对于这个 $8 \times 8$ 的棋盘总共有多少种覆盖方案。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

提示：建议使用计算机计算，答案是一个 $8$  位十进制整数。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
        "The answer of task C", // 双引号中替换为 C 题的答案
        "The answer of task D", // 双引号中替换为 D 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2021 国 B] 填空问题

description:
## 试题 A：带宽

### 【问题描述】

小蓝家的网络带宽是 $200 \mathrm{Mbps}$，请问，使用小蓝家的网络理论上每秒钟最多可以从网上下载多少 $\mathrm{MB}$ 的内容。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B ：纯质数

### 【问题描述】

如果一个正整数只有 $1$  和它本身两个约数，则称为一个质数（又称素数）。

前几个质数是：$2,3,5,7,11,13,17,19,23,29,31,37,\cdots$。

如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：2,$3,5,7,23,37$ 都是纯质数，而 $11,13,17,19,29,31$ 不是纯质数。当然 $1,4,35$ 也不是纯质数。

请问，在 $1$  到 $20210605$  中，有多少个纯质数?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：完全日期

### 【问题描述】

如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。

例如：2021 年 $6$  月 $5$  日的各位数字之和为 $2+0+2+1+6+5=16$，而 $16$  是一个完全平方数，它是 $4$  的平方。所以 $2021$  年 $6$  月 $5$  日是一个完全日期。

例如：2021 年 $6$  月 $23$  日的各位数字之和为 $2+0+2+1+6+2+3=16$，是一个完全平方数。所以 $2021$  年 $6$  月 $23$  日也是一个完全日期。

请问，从 $2001$  年 $1$  月 $1$  日到 $2021$  年 $12$  月 $31$  日中，一共有多少个完全日期?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：最小权值

### 【问题描述】

对于一棵有根二叉树 $T$，小蓝定义这棵树中结点的权值 $W(T)$ 如下:

空子树的权值为 $0$ 。

如果一个结点 $v$ 有左子树 $L$，右子树 $R$，分别有 $C(L)$ 和 $C(R)$ 个结点，则

$W(v)=1+2 W(L)+3 W(R)+(C(L))^{2} C(R)$。

树的权值定义为树的根结点的权值。

小蓝想知道，对于一棵有 $2021$  个结点的二叉树，树的权值最小可能是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2021 国 C] 填空问题

description:
## 试题 A: 整数范围

### 【问题描述】

  用 $8$ 位二进制（一个字节）来表示一个非负整数，表示的最小值是 $0$，则一般能表示的最大值是多少？

### 【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：带宽

### 【问题描述】

小蓝家的网络带宽是 $200 \mathrm{Mbps}$，请问，使用小蓝家的网络理论上每秒钟最多可以从网上下载多少 $\mathrm{MB}$ 的内容。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：纯质数

### 【问题描述】

如果一个正整数只有 $1$  和它本身两个约数，则称为一个质数（又称素数）。

前几个质数是：$2,3,5,7,11,13,17,19,23,29,31,37,\cdots$。

如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：2,$3,5,7,23,37$ 都是纯质数，而 $11,13,17,19,29,31$ 不是纯质数。当然 $1,4,35$ 也不是纯质数。

请问，在 $1$  到 $20210605$  中，有多少个纯质数?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：完全日期

### 【问题描述】

如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。

例如：2021 年 $6$  月 $5$  日的各位数字之和为 $2+0+2+1+6+5=16$，而 $16$  是一个完全平方数，它是 $4$  的平方。所以 $2021$  年 $6$  月 $5$  日是一个完全日期。

例如：2021 年 $6$  月 $23$  日的各位数字之和为 $2+0+2+1+6+2+3=16$，是一个完全平方数。所以 $2021$  年 $6$  月 $23$  日也是一个完全日期。

请问，从 $2001$  年 $1$  月 $1$  日到 $2021$  年 $12$  月 $31$  日中，一共有多少个完全日期?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E ：最小权值

### 【问题描述】

对于一棵有根二叉树 $T$，小蓝定义这棵树中结点的权值 $W(T)$ 如下:

空子树的权值为 $0$ 。

如果一个结点 $v$ 有左子树 $L$，右子树 $R$，分别有 $C(L)$ 和 $C(R)$ 个结点，则

$W(v)=1+2 W(L)+3 W(R)+(C(L))^{2} C(R)$。

树的权值定义为树的根结点的权值。

小蓝想知道，对于一棵有 $2021$  个结点的二叉树，树的权值最小可能是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2021 国 BC] 大写

description: 给定一个只包含大写字母和小写字母的字符串，请将其中所有的小写字母转换成大写字母后将字符串输出。

inputFormat: 输入一行包含一个字符串。

outputFormat: 输出转换成大写后的字符串。

samples: LanQiao LANQIAO

hint:
对于所有评测用例, 字符串的长度不超过 $100$。

蓝桥杯 2021 国赛 B 组 E 题（C 组 E 题）。


title: [蓝桥杯 2021 国 ABC] 123

description:
小蓝发现了一个有趣的数列, 这个数列的前几项如下:

$1,1,2,1,2,3,1,2,3,4, \ldots$

小蓝发现, 这个数列前 $1$ 项是整数 $1$ , 接下来 $2$ 项是整数 $1$ 至 $2$ , 接下来 $3$ 项是整数 $1$ 至 $3$ , 接下来 $4$ 项是整数 $1$ 至 $4$ , 依次类推。

小蓝想知道, 这个数列中, 连续一段的和是多少。

inputFormat:
输入的第一行包含一个整数 $T$, 表示询问的个数。

接下来 $T$ 行, 每行包含一组询问, 其中第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$, 表示 询问数列中第 $l_{i}$ 个数到第 $r_{i}$ 个数的和。

outputFormat: 输出 $T$ 行, 每行包含一个整数表示对应询问的答案。


title: [蓝桥杯 2021 国 ABC] 异或变换

description:
小蓝有一个 01 串 $s=s_{1} s_{2} s_{3} \cdots s_{n}$。

以后每个时刻, 小蓝要对这个 01 串进行一次变换。每次变换的规则相同。 对于 01 串 $s=s_{1} s_{2} s_{3} \cdots s_{n}$, 变换后的 01 串 $s^{\prime}=s_{1}^{\prime} s_{2}^{\prime} s_{3}^{\prime} \cdots s_{n}^{\prime}$ 为：

$$
\begin{aligned}
&s_{1}^{\prime}=s_{1} \\
&s_{i}^{\prime}=s_{i-1} \oplus s_{i}
\end{aligned}
$$

其中 $a \oplus b$ 表示两个二进制的异或, 当 $a$ 和 $b$ 相同时结果为 $0$ , 当 $a$ 和 $b$ 不同时结果为 $1$ 。

请问, 经过 $t$ 次变换后的 01 串是什么?

inputFormat:
输入的第一行包含两个整数 $n, t$, 分别表示 01 串的长度和变换的次数。

第二行包含一个长度为 $n$ 的 01 串。

outputFormat: 输出一行包含一个 01 串, 为变换后的串。

hint:
**【样例说明】**

初始时为 `10110` , 变换 1 次后变为 `11101` , 变换 2 次后变为 `10011` , 变换 3 次后变为 `11010`。

**【评测用例规模与约定】**

对于 $40 \%$ 的评测用例, $1 \leq n \leq 100,1 \leq t \leq 1000$。

对于 $80 \%$ 的评测用例, $1 \leq n \leq 1000,1 \leq t \leq 10^{9}$。

对于所有评测用例, $1 \leq n \leq 10000,1 \leq t \leq 10^{18}$。

蓝桥杯 2021 国赛 A 组 F 题（B 组 G 题，C 组 G 题）。


title: [蓝桥杯 2021 国 BC] 二进制问题

description: 小蓝最近在学习二进制。他想知道 $1$ 到 $N$ 中有多少个数满足其二进制表示中恰好有 $K$ 个 `1`。你能帮助他吗?

inputFormat: 输入一行包含两个整数 $N$ 和 $K$。

outputFormat: 输出一个整数表示答案。

hint:
对于 $30 \%$ 的评测用例, $1 \leq N \leq 10^{6}, 1 \leq K \leq 10$ 。

对于 $60 \%$ 的评测用例, $1 \leq N \leq 2 \times 10^{9}, 1 \leq K \leq 30$ 。

对于所有评测用例, $1 \leq N \leq 10^{18}, 1 \leq K \leq 50$ 。

蓝桥杯 2021 国赛 B 组 H 题（C 组 J 题）。


title: [蓝桥杯 2021 国 AB] 翻转括号序列

description:
给定一个长度为 $n$ 的括号序列，要求支持两种操作:

1. 将 $\left[L_{i}, R_{i}\right]$ 区间内（序列中的第 $L_{i}$ 个字符到第 $R_{i}$ 个字符）的括号全部翻转(左括号变成右括号，右括号变成左括号)。

2. 求出以 $L_{i}$ 为左端点时，最长的合法括号序列对应的 $R_{i}$ （即找出最大的 $R_{i}$ 使 $\left[L_{i}, R_{i}\right]$ 是一个合法括号序列）。

inputFormat:
输入的第一行包含两个整数 $n, m$，分别表示括号序列长度和操作次数。

第二行包含给定的括号序列，括号序列中只包含左括号和右括号。

接下来 $m$ 行，每行描述一个操作。如果该行为 `1 L R`, 表示第一种操作，区间为 $\left[L, R\right]$；如果该行为 `2 L` 表示第二种操作，左端点为 $L$ 。

outputFormat: 对于每个第二种操作，输出一行，表示对应的 $R_{i}$。如果不存在这样的 $R_{i}$，请输出 $0$ 。

hint:
对于 $20 \%$ 的评测用例，$n, m \leq 5000$;

对于 $40 \%$ 的评测用例，$n, m \leq 30000$;

对于 $60 \%$ 的评测用例，$n, m \leq 100000$;

对于所有评测用例，$1 \leq n \leq 10^{6}, 1 \leq m \leq 2 \times 10^{5}$ 。

蓝桥杯 2021 国赛 A 组 H 题（B 组 I 题）。


title: [蓝桥杯 2021 国 AB] 异或三角

description:
给定 $T$ 个数 $n_{1}, n_{2}, \cdots, n_{T}$, 对每个 $n_{i}$ 请求出有多少组 $a, b, c$ 满足:

1. $1 \leq a, b, c \leq n_{i}$;

2. $a \oplus b \oplus c=0$ ，其中 $\oplus$ 表示二进制按位异或;

3. 长度为 $a, b, c$ 的三条边能组成一个三角形。

inputFormat:
输入的第一行包含一个整数 $T$ 。

接下来 $T$ 行每行一个整数, 分别表示 $n_{1}, n_{2}, \cdots, n_{T}$ 。

outputFormat: 输出 $T$ 行, 每行包含一个整数, 表示对应的答案。


title: [蓝桥杯 2021 国 A] 冰山

description:
一片海域上有一些冰山，第 $i$ 座冰山的体积为 $V_{i}$ 。

随着气温的变化，冰山的体积可能增大或缩小。第 $i$ 天, 每座冰山的变化量都是 $X_{i}$。当 $X_{i}>0$ 时，所有冰山体积增加 $X_{i}$；当 $X_{i}<0$ 时，所有冰山体积减少 $-X_{i}$；当 $X_{i}=0$ 时，所有冰山体积不变。

如果第 $i$ 天某座冰山的体积变化后小于等于 $0$，则冰山会永远消失。

冰山有大小限制 $k$。如果第 $i$ 天某座冰山 $j$ 的体积变化后 $V_{j}$ 大于 $k$，则它会分裂成一个体积为 $k$ 的冰山和 $V_{j}-k$ 座体积为 $1$ 的冰山。

第 $i$ 天结束前（冰山增大、缩小、消失、分裂完成后），会漂来一座体积为 $Y_{i}$ 的冰山（$Y_{i}=0$ 表示没有冰山漂来）。

小蓝在连续的 $m$ 天对这片海域进行了观察，并准确记录了冰山的变化。小蓝想知道, 每天结束时所有冰山的体积之和（包括新漂来的）是多少。

由于答案可能很大，请输出答案除以 $998244353$ 的余数。

inputFormat:
输入的第一行包含三个整数 $n, m, k$, 分别表示初始时冰山的数量、观察的 天数以及冰山的大小限制。

第二行包含 $n$ 个整数 $V_{1}, V_{2}, \cdots, V_{n}$，表示初始时每座冰山的体积。

接下来 $m$ 行描述观察的 $m$ 天的冰山变化。其中第 $i$ 行包含两个整数 $X_{i}, Y_{i}$，意义如前所述。

outputFormat: 输出 $m$ 行，每行包含一个整数，分别对应每天结束时所有冰山的体积之和除以 $998244353$ 的余数。

hint:
**【样例说明】**

在本样例说明中, 用 $\left[a_{1}, a_{2}, \cdots, a_{n}\right]$ 来表示每座冰山的体积。

初始时的冰山为 [1]。

第 $1$ 天结束时，有 $3$ 座冰山： $[1,1,6]$ 。

第 $2$ 天结束时，有 $6$ 座冰山： $[1,1,2,3,3,6]$ 。

第 $3$ 天结束时，有 $5$ 座冰山： $[1,1,2,2,5]$ 。

**【评测用例规模与约定】**

对于 $40 \%$ 的评测用例, $n, m, k \leq 2000$;

对于 $60 \%$ 的评测用例, $n, m, k \leq 20000$;

对于所有评测用例, $1 \leq n, m \leq 10^5,1 \leq k \leq 10^{9}, 1 \leq V_{i} \leq k, 0 \leq Y_{i} \leq k$, $-k \leq X_{i} \leq k$ 。

蓝桥杯 2021 国赛 A 组 G 题。


title: [蓝桥杯 2021 国 A] 积木

description:
小蓝有大量正方体的积木（所有积木完全相同），他准备用积木搭一个巨大的图形。

小蓝将积木全部平铺在地面上，而不垒起来，以便更稳定。他将积木摆成一行一行的，每行的左边对齐，共 $n$ 行，形成最终的图形。

第一行小蓝摆了 $H_{1}=w$ 块积木。从第二行开始，第 $i$ 行的积木数量 $H_{i}$ 都 至少比上一行多 $L$，至多比上一行多 $R$ (当 $L=0$ 时表示可以和上一行的积木数量相同)，即

$$
H_{i-1}+L \leq H_{i} \leq H_{i-1}+R_{\circ}
$$

给定 $x, y$ 和 $z$, 请问满足以上条件的方案中，有多少种方案满足第 $y$ 行的积木数量恰好为第 $x$ 行的积木数量的 $z$ 倍。

inputFormat: 输入一行包含 $7$ 个整数 $n, w, L, R, x, y, z$，意义如上所述。

outputFormat: 输出一个整数，表示满足条件的方案数，答案可能很大，请输出答案除以 $998244353$ 的余数。

hint:
**【样例说明】**

符合条件的积木如图所示
![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_ca697d8d2e5bb8d06fa0g-17.jpg)

**【评测用例规模与约定】**

对于 $10 \%$ 的评测用例, $1 \leq n \leq 10,1 \leq w \leq 10,0 \leq L \leq R \leq 3$;

对于 $20 \%$ 的评测用例, $1 \leq n \leq 20,1 \leq w \leq 10,0 \leq L \leq R \leq 4$;

对于 $35 \%$ 的评测用例, $1 \leq n \leq 500,0 \leq L \leq R \leq 10$;

对于 $50 \%$ 的评测用例, $1 \leq n \leq 5000,0 \leq L \leq R \leq 10$;

对于 $60 \%$ 的评测用例, $1 \leq n \leq 20000,0 \leq L \leq R \leq 10$;

对于 $70 \%$ 的评测用例, $1 \leq n \leq 50000,0 \leq L \leq R \leq 10$;

对于 $85 \%$ 的评测用例, $1 \leq n \leq 3\times10^5,0 \leq L \leq R \leq 10$;

对于所有评测用例, $1 \leq n \leq 5\times10^5, 0 \leq w \leq 10^{9}, 0 \leq L \leq R \leq 40$, $1 \leq x<y \leq n, 0 \leq z \leq 10^{9}$ 。

蓝桥杯 2021 国赛 A 组 J 题。


title: [蓝桥杯 2021 国 C] 巧克力

description:
小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。

一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 $x$ 天的巧克力。

inputFormat:
输入的第一行包含两个整数 $x$，$n$，分别表示需要吃巧克力的天数和巧克力的种类数。

接下来 $n$ 行描述货架上的巧克力，其中第 $i$ 行包含三个整数 $a_i$，$b_i$，$c_i$，表示第 $i$ 种巧克力的单价为 $a_i$，保质期还剩 $b_i$ 天（从现在开始的 $b_i$ 天可以吃），数量为 $c_i$。

outputFormat: 输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 $x$ 天的购买方案，输出 $−1$。

hint:
**【样例说明】**

一种最佳的方案是第 $1$ 种买 $5$ 块，第 $2$ 种买 $2$ 块，第 $3$ 种买 $3$ 块。前 $5$ 天吃第 $1$ 种，第 $6$、$7$ 天吃第 $2$ 种，第 $8$ 至 $10$ 天吃第 $3$ 种。

**【评测用例规模与约定】**

对于 $30\%$ 的评测用例，$n,x \le 1000$。

对于所有评测用例，$1\le n,x\le 10^5$，$1 ≤ a_i,b_i ,c_i\le10^9$。

蓝桥杯 2021 国赛 C 组 I 题。


title: [蓝桥杯 2022 省 A] 填空问题

description:
## 试题 A ：裁纸刀

### 【问题描述】

小蓝有一个裁纸刃，每次可以将一张纸沿一条直线裁成两半。

小蓝用一张纸打印出两行三列共 $6$  个二维码，至少使用九次裁出来，下图给出了一种裁法。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_ce76de7bbf570735a440g-02.jpg)

在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁 $4$  次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。

如果小蓝要用一张纸打印出 $20$  行 $22$  列共 $440$  个二维码，他至少需要裁多少次?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：灭鼠先锋

### 【问题描述】

灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。

灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。

小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况:

```plaintext
X000 XX00 OXOO OXXO
0000 0000 0000 0000
```

其中 `O` 表示棋盘上的一个方格为空，`X` 表示该方格已经放置了棋子。

请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来玩游戏，小蓝是否能获胜。如果获胜，请用 `V` 表示，否则用 `L` 表示。请将四种情况的胜负结果按顺序连接在一起提交。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个长度为 $4$  的由大写字母 `V` 和 `L` 组成的字符串，如 `VVLL`，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

inputFormat: 输入格式输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2022 省 B] 填空问题

description:
## 试题 A：九进制转十进制

### 【问题描述】

九进制正整数 $(2022)_{9}$ 转换成十进制等于多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：顺子日期

### 【问题描述】

小明特别喜欢顺子。顺子指的就是连续的三个数字：`123`、`456` 等。顺子日期指的就是在日期的 `уyyymmdd` 表示法中，存在任意连续的三位数是一个顺子的日期。例如 `20220123` 就是一个顺子日期，因为它出现了一个顺子：`123`; 而 `20221023` 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入格式输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2022 省 A] 求和

description:
给定 $n$ 个整数 $a_{1}, a_{2}, \cdots, a_{n}$, 求它们两两相乘再相加的和，即

$$
S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n}
$$

inputFormat:
输入的第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \cdots a_{n}$ 。

outputFormat: 输出一个整数 $S$，表示所求的和。请使用合适的数据类型进行运算。

hint:
对于 $30 \%$ 的数据, $1 \leq n \leq 1000,1 \leq a_{i} \leq 100$ 。

对于所有评测用例, $1 \leq n \leq 2\times10^5,1 \leq a_{i} \leq 1000$ 。

蓝桥杯 2022 省赛 A 组 C 题。


title: [蓝桥杯 2022 省 A] 选数异或

description: 给定一个长度为 $n$ 的数列 $A_{1}, A_{2}, \cdots, A_{n}$ 和一个非负整数 $x$, 给定 $m$ 次查询, 每次询问能否从某个区间 $[l, r]$ 中选择两个数使得他们的异或等于 $x$ 。

inputFormat:
输入的第一行包含三个整数 $n, m, x$ 。

第二行包含 $n$ 个整数 $A_{1}, A_{2}, \cdots, A_{n}$。

接下来 $m$ 行，每行包含两个整数 $l_{i}, r_{i}$ 表示询问区间 $\left[l_{i}, r_{i}\right]$ 。

outputFormat: 对于每个询问, 如果该区间内存在两个数的异或为 $x$ 则输出 `yes`, 否则输出 `no`。

hint:
**【样例说明】**

显然整个数列中只有 2,3 的异或为 1 。

**【评测用例规模与约定】**

对于 $20 \%$ 的评测用例, $1 \leq n, m \leq 100$;

对于 $40 \%$ 的评测用例, $1 \leq n, m \leq 1000$;

对于所有评测用例, $1 \leq n, m \leq 10^5,0 \leq x<2^{20}, 1 \leq l_{i} \leq r_{i} \leq n$ ， $0 \leq A_{i}<2^{20}$ 。

蓝桥杯 2022 省赛 A 组 D 题。


title: [蓝桥杯 2022 省 A] 爬树的甲壳虫

description: 有一只甲壳虫想要爬上一颗高度为 $n$ 的树，它一开始位于树根, 高度为 $0$，当它尝试从高度 $i-1$ 爬到高度为 $i$ 的位置时有 $P_{i}$ 的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。

inputFormat:
输入第一行包含一个整数 $n$ 表示树的高度。

接下来 $n$ 行每行包含两个整数 $x_{i}, y_{i}$, 用一个空格分隔，表示 $P_{i}=\frac{x_{i}}{y_{i}}$ 。

outputFormat: 输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 $998244353$ 取模的结果。其中有理数 $\frac{a}{b}$ 对质数 $P$ 取模的结果是整数 $c$ 满足 $0 \leq c<P$ 且 $c \cdot b \equiv a\pmod P$ 。


title: [蓝桥杯 2022 省 A] 青蛙过河

description:
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 $1$，当石头的高度下降到 $0$ 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 $0$ 是允许的)。

小青蛙一共需要去学校上 $x$ 天课，所以它需要往返 $2x$ 次。当小青蛙具有一个跳跃能力 $y$ 时，它能跳不超过 $y$ 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 $x$ 次课。

inputFormat:
输入的第一行包含两个整数 $n, x$, 分别表示河的宽度和小青蛙需要去学校的天数。请注意 $2x$ 才是实际过河的次数。

第二行包含 $n-1$ 个非负整数 $H_{1}, H_{2}, \cdots, H_{n-1}$, 其中 $H_{i}>0$ 表示在河中与 小青蛙的家相距 $i$ 的地方有一块高度为 $H_{i}$ 的石头，$H_{i}=0$ 表示这个位置没有石头。

outputFormat: 输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

hint:
**【样例解释】**

由于只有两块高度为 $1$ 的石头，所以往返只能各用一块。第 $1$ 块石头和对岸的距离为 $4$，如果小青蛙的跳跃能力为 $3$ 则无法满足要求。所以小青蛙最少需要 $4$ 的跳跃能力。

**【评测用例规模与约定】**

对于 $30 \%$ 的评测用例，$n \leq 100$;

对于 $60 \%$ 的评测用例，$n \leq 1000$;

对于所有评测用例，$1 \leq n \leq 10^{5}, 1 \leq x \leq 10^{9}, 0 \leq H_{i} \leq 10^{4}$ 。

蓝桥杯 2022 省赛 A 组 F 题。


title: [蓝桥杯 2022 省 A] 最长不下降子序列

description:
给定一个长度为 $N$ 的整数序列：$A_{1}, A_{2}, \cdots, A_{N}$。现在你有一次机会，将其中连续的 $K$ 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

inputFormat:
输入第一行包含两个整数 $N$ 和 $K$ 。

第二行包含 $N$ 个整数 $A_{1}, A_{2}, \cdots, A_{N}$ 。

outputFormat: 输出一行包含一个整数表示答案。

hint:
对于 $20 \%$ 的评测用例, $1 \leq K \leq N \leq 100$;

对于 $30 \%$ 的评测用例, $1 \leq K \leq N \leq 1000$;

对于 $50 \%$ 的评测用例, $1 \leq K \leq N \leq 10000$;

对于所有评测用例, $1 \leq K \leq N \leq 10^{5}, 1 \leq A_{i} \leq 10^{6}$ 。

蓝桥杯 2022 省赛 A 组 G 题。


title: [蓝桥杯 2022 省 A] 扫描游戏

description:
有一根围绕原点 $O$ 顺时针旋转的棒 $OA$，初始时指向正上方（Y 轴正向）。平面中有若干物件，第 $i$ 个物件的坐标为 $\left(x_{i}, y_{i}\right)$，价值为 $z_{i}$。当棒扫到某个物件时，棒的长度会瞬间增长 $z_{i}$，且物件瞬间消失（棒的顶端恰好碰到物件也视为扫到)，如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去（它和上述那个点视为同时消失）。

如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同，请输出每个物件的排名，如果物件永远不会消失则输出 $-1$。

inputFormat:
输入第一行包含两个整数 $n$、$L$，用一个空格分隔，分别表示物件数量和棒的初始长度。

接下来 $n$ 行每行包含第三个整数 $x_{i}, y_{i}, z_{i}$。

注意存在 $(x_{i}, y_{i})=(0,0)$ 的情况，这些点视为一开始就立刻被碰到。

outputFormat: 输出一行包含 $n$ 整数，相邻两个整数间用一个空格分隔，依次表示每个物件的排名。

hint:
对于 $30 \%$ 的评测用例，$1 \leq n \leq 500$ ；

对于 $60 \%$ 的评测用例，$1 \leq n \leq 5000$;

对于所有评测用例，$1 \leq n \leq 2\times10^5,-10^{9} \leq x_{i}, y_{i} \leq 10^{9}, 1 \leq L, z_{i} \leq 10^{9}$ 。

样蓝桥杯 2022 省赛 A 组 H 题。


title: [蓝桥杯 2022 省 A] 数的拆分

description: 给定 $T$ 个正整数 $a_{i}$，分别问每个 $a_{i}$ 能否表示为 $x_{1}^{y_{1}} \cdot x_{2}^{y_{2}}$ 的形式，其中 $x_{1}, x_{2}$ 为正整数，$y_{1}, y_{2}$ 为大于等于 $2$ 的正整数。

inputFormat:
输入第一行包含一个整数 $T$ 表示询问次数。

接下来 $T$ 行，每行包含一个正整数 $a_{i}$ 。

outputFormat: 对于每次询问，如果 $a_{i}$ 能够表示为题目描述的形式则输出 `yes`，否则输出 `no`。


title: [蓝桥杯 2022 省 A] 推导部分和

description:
对于一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \cdots A_{N}$，小蓝想知道下标 $l$ 到 $r$ 的部分和 $\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}$ 是多少?

然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i}$ 的部分和 $\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}$, 值是 $S_{i}$ 。

inputFormat:
第一行包含 3 个整数 $N 、 M$ 和 $Q$。分别代表数组长度、已知的部分和数量 和询问的部分和数量。

接下来 $M$ 行，每行包含 $3$ 个整数 $l_{i}, r_{i}, S_{i}$。

接下来 $Q$ 行，每行包含 $2$ 个整数 $l$ 和 $r$，代表一个小蓝想知道的部分和。

outputFormat: 对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 `UNKNOWN`。


title: [蓝桥杯 2022 省 B] 刷题统计

description: 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 $a$ 道题目，周六和周日每天做 $b$ 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 $n$ 题?

inputFormat: 输入一行包含三个整数 $a, b$ 和 $n$.

outputFormat: 输出一个整数代表天数。


title: [蓝桥杯 2022 省 B] 修剪灌木

description:
爱丽丝要完成一项修剪灌木的工作。

有 $N$ 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌木，让灌木的高度变为 $0$ 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

灌木每天从早上到傍晩会长高 $1$ 厘米, 而其余时间不会长高。在第一天的早晨, 所有灌木的高度都是 $0$ 厘米。爱丽丝想知道每棵灌木最高长到多高。

inputFormat: 一个正整数 $N$ ，含义如题面所述。

outputFormat: 输出 $N$ 行, 每行一个整数, 第行表示从左到右第 $i$ 棵树最高能长到多高。


title: [蓝桥杯 2022 省 B] X 进制减法

description:
进制规定了数字在数位上逢几进一。

$X$ 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 $X$ 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 $X$ 进制数 `321` 转换为十进制数为 `65`。

现在有两个 $X$ 进制表示的整数 $A$ 和 $B$，但是其具体每一数位的进制还不确定，只知道 $A$ 和 $B$ 是同一进制规则，且每一数位最高为 $N$ 进制，最低为二进制。请你算出 $A-B$ 的结果最小可能是多少。

请注意，你需要保证 $A$ 和 $B$ 在 $X$ 进制下都是合法的, 即每一数位上的数字要小于其进制。

inputFormat:
第一行一个正整数 $N$，含义如题面所述。

第二行一个正整数 $M_{a}$，表示 $X$ 进制数 $A$ 的位数。

第三行 $M_{a}$ 个用空格分开的整数，表示 $X$ 进制数 $A$ 按从高位到低位顺序各个数位上的数字在十进制下的表示。

第四行一个正整数 $M_{b}$，表示 $X$ 进制数 $B$ 的位数。

第五行 $M_{b}$ 个用空格分开的整数，表示 $X$ 进制数 $B$ 按从高位到低位顺序各个数位上的数字在十进制下的表示。

请注意，输入中的所有数字都是十进制的。

outputFormat: 输出一行一个整数，表示 $X$ 进制数 $A-B$ 的结果的最小可能值转换为十进制后再模 $1000000007$（即 $10^9+7$）的结果。

hint:
**【样例说明】**

当进制为：最低位 $2$ 进制, 第二数位 $5$ 进制, 第三数位 $11$ 进制时, 减法得到的差最小。此时 $A$ 在十进制下是 $108$，$B$ 在十进制下是 $14$，差值是 $94$。

**【评测用例规模与约定】**

对于 $30 \%$ 的数据，$N \leq 10,M_{a}, M_{b} \leq 8$.

对于 $100 \%$ 的数据，$2 \leq N \leq 1000,1 \leq M_{a}, M_{b} \leq 10^5,A \geq B$。

蓝桥杯 2022 省赛 B 组 E 题。


title: [蓝桥杯 2022 省 B] 统计子矩阵

description: 给定一个 $N \times M$ 的矩阵 $A$，请你统计有多少个子矩阵 (最小 $1 \times 1$, 最大 $N \times M)$ 满足子矩阵中所有数的和不超过给定的整数 $K$。

inputFormat:
第一行包含三个整数 $N, M$ 和 $K$。

之后 $N$ 行每行包含 $M$ 个整数, 代表矩阵 $A$。

outputFormat: 一个整数代表答案。

hint:
**【样例说明】**

满足条件的子矩阵一共有 $19$，包含:

大小为 $1 \times 1$ 的有 $10$ 个。

大小为 $1 \times 2$ 的有 $3$ 个。 大小为 $1 \times 3$ 的有 $2$ 个。

大小为 $1 \times 4$ 的有 $1$ 个。

大小为 $2 \times 1$ 的有 $3$ 个。

**【评测用例规模与约定】**

对于 $30 \%$ 的数据, $N, M \leq 20$.

对于 $70 \%$ 的数据, $N, M \leq 100$.

对于 $100 \%$ 的数据, $1 \leq N, M \leq 500,0 \leq A_{i j} \leq 1000,1 \leq K \leq 2.5\times10^8$.

蓝桥杯 2022 省赛 B 组 F 题。


title: [蓝桥杯 2022 省 B] 积木画

description:
小明最近迷上了积木画，有这么两种类型的积木，分别为 $I$ 型（大小为 $2$ 个单位面积) 和 $L$ 型 (大小为 $3$ 个单位面积):

![I 型积木](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_3d61ad9326a0012c9fdag-10.jpg)

同时，小明有一块面积大小为 $2 \times N$ 的画布，画布由 $2 \times N$ 个 $1 \times 1$ 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式? 积木可以任意旋转，且画布的方向固定。

inputFormat: 输入一个整数 $N$，表示画布大小。

outputFormat: 输出一个整数表示答案。由于答案可能很大，所以输出其对 $1000000007$（即 $10^9+7$）取模后的值。

hint:
**【样例说明】**

五种情况如下图所示, 颜色只是为了标识不同的积木:
![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_3d61ad9326a0012c9fdag-11.jpg)

**【评测用例规模与约定】**

对于所有测试用例，$1 \leq N \leq 10^7$。

蓝桥杯 2022 省赛 B 组 G 题。


title: [蓝桥杯 2022 省 B] 李白打酒加强版

description:
话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 $2$ 斗。他边走边唱：

> 无事街上走，提壶去打酒。
> 逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 $N$ 次，遇到花 $M$ 次。已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序，有多少种不同的可能?

注意：壶里没酒（$0$ 斗）时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

inputFormat: 第一行包含两个整数 $N$ 和 $M$。

outputFormat: 输出一个整数表示答案。由于答案可能很大，输出模 $1000000007$（即 $10^9+7$）的结果。


title: [蓝桥杯 2022 省 B] 砍竹子

description:
这天，小明在砍竹子，他面前有 $n$ 棵竹子排成一排，一开始第 $i$ 棵竹子的高度为 $h_{i}$.

他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 $H$，那么使用一次魔法可以把这一段竹子的高度都变为 $\left\lfloor\sqrt{\left\lfloor\frac{H}{2}\right\rfloor+1}\right\rfloor$, 其中 $\lfloor x\rfloor$ 表示对 $x$ 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 $1$。

inputFormat:
第一行为一个正整数 $n$，表示竹子的棵数。

第二行共 $n$ 个空格分开的正整数 $h_{i}$，表示每棵竹子的高度。

outputFormat: 一个整数表示答案。

hint:
**【样例说明】**

其中一种方案:

$214267\rightarrow 214262\rightarrow 214222\rightarrow 211222\rightarrow 111222\rightarrow 111111$

共需要 5 步完成

**【评测用例规模与约定】**

对于 $20 \%$ 的数据，保证 $n \leq 1000, h_{i} \leq 10^{6}$ 。

对于 $100 \%$ 的数据，保证 $n \leq 2 \times 10^{5}, h_{i} \leq 10^{18}$ 。

蓝桥杯 2022 省赛 B 组 J 题。


title: [蓝桥杯 2022 国 A] 填空问题

description:
## 试题 A ：小蓝与钥匙

### 【问题描述】

小蓝是幼儿园的老师，他的班上有 $28$  个孩子，今天他和孩子们一起进行了一个游戏。

小蓝所在的学校是寄宿制学校，28 个孩子分别有一个自己的房间，每个房间对应一把钥匙，每把钥匙只能打开自己的门。现在小蓝让这 $28$  个孩子分别将自己宿舍的钥匙上交，再把这 $28$  把钥匙随机打乱分给每个孩子一把钥匙，有 $28 !=28 \times 27 \times \cdots \times 1$ 种分配方案。小蓝想知道这些方案中，有多少种方案恰有一半的孩子被分到自己房间的钥匙（即有 $14$  个孩子分到的是自己房间的钥匙，有 $14$  个孩子分到的不是自己房间的钥匙）。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：排列距离

### 【问题描述】

小蓝最近迷上了全排列，现在他有一个长度为 $17$  的排列，里面包含的元素有：abcdefghijklnopqr,即 a 至 $r$ 中除了 $\mathrm{m}$ 以外的所有小写字母，这 $17$  个字母在任何一个排列中都恰好出现一次。前面几个排列依次是：

第 $1$  个排列为：abcdefghijklnopqr;

第 $2$  个排列为：abcdefghijklnoprq;

第 $3$  个排列为：abcdefghijklnoqpr;

第 $4$  个排列为：abcdefghijklnoqrp;

第 $5$  个排列为：abcdefghijklnorpq;

第 $6$  个排列为：abcdefghijklnorqp;

第 $7$  个排列为：abcdefghijklnpogr;

第 $8$  个排列为：abcdefghijklnporq;

第 $9$  个排列为：abcdefghijklnpqor;

第 $10$  个排列为：abcdefghijklnpqro。

对于一个排列，有两种转移操作:

1）转移到其下一个排列。如果当前排列已经是最后一个排列，那么下一个排列就是第一个排列。

2）转移到其上一个排列。如果当前排列是第一个排列，那么上一个排列就是最后一个排列。

小蓝现在有两个排列，分别为排列 $A:$ aejcldbhpiogfqnkr,以及排列 $B:$ ncfjboqiealh krpgd，他现在想知道，在只有上述两种转移操作的前提下，排列 $A$ 最少转移多少次能得到排列 $B$。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入格式输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2022 国 B] 填空问题

description:
## 试题 A：2022

### 【问题描述】

将 $2022$  拆分成 $10$  个互不相同的正整数之和，总共有多少种拆分方法?

注意交换顺序视为同一种方法，例如 $2022=1000+1022$ 和 $2022=$ $1022+1000$ 就视为同一种方法。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：钟表

### 【问题描述】

在 $12$  小时制的钟表中，有分针、时针、秒针来表示时间。记分针和时针之间的夹角度数为 $A(0 \leq A \leq 180)$ 、分针和秒针之间的夹角度数为 $B$ $(0 \leq B \leq 180)$。而恰好在 $s$ 时 $f$ 分 $m$ 秒时，满足条件 $A=2 B$ 且 $0 \leq s \leq 6$; $0 \leq f<60 ; 0 \leq m<60$，请问 $s,f,m$ 分别是多少。

注意时针、分针、秒针都围绕中心匀速转动。

提交格式为三个由一个空格隔开的整数，分别表示 $s,f,m$。如 `3 11 58` 表示 $3$ 点 $11$ 分 $58$ 秒。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为三个由一个空格隔开的整数，在提交答案时只填写为三个由一个空格隔开的整数，填写多余的内容将无法得分。

inputFormat: 输入格式输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2022 国 AC] 内存空间

description:
小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。

为了简化问题，变量的类型只有以下三种：

`int`：整型变量，一个 int 型变量占用 $4$ Byte 的内存空间。

`long`：长整型变量，一个 long 型变量占用 $8$ Byte 的内存空间。

`String`：字符串变量，占用空间和字符串长度有关，设字符串长度为 $L$，则字符串占用 $L$ Byte 的内存空间，如果字符串长度为 $0$ 则占用 $0$ Byte 的内存空间。

定义变量的语句只有两种形式，第一种形式为：

```
type var1=value1,var2=value2...;
```

定义了若干个 type 类型变量 var1、var2、……，并且用 value1、value2……初始化。

多个变量之间用 `,` 分隔，语句以 `;` 结尾，type 可能是 `int`、`long` 或 `String`。例如 `int a=1,b=5,c=6;` 占用空间为 $12$ Byte；`long a=1,b=5;` 占用空间为 $16$ Byte；`String s1="",s2="hello",s3="world";` 占用空间为 $10$ Byte。

第二种形式为：

```
type[] arr1=new type[size1],arr2=new type[size2]…;
```

定义了若干 type 类型的一维数组变量 arr1、arr2……，且数组的大小为 size1、size2……，多个变量之间用 `,` 进行分隔，语句以 `;` 结尾，type 只可能是 `int` 或 `long`。例如 `int[] a1=new int[10]`；占用的内存空间为 $40$ Byte；`long[] a1=new long[10],a2=new long[10];` 占用的内存空间为 $160$ Byte。

已知小蓝有 $T$ 条定义变量的语句，请你帮他统计下一共占用了多少内存空间。结果的表示方式为：$\texttt{aGBbMBcKBdB}$，其中 $a$、$b$、$c$、$d$ 为统计的结果，$\texttt{GB}$、$\texttt{MB}$、$\texttt{KB}$、$\texttt{B}$ 为单位。优先用大的单位来表示，$1\texttt{GB}=1024\texttt{MB}$，$1\texttt{MB}=1024\texttt{KB}$，$1\texttt{KB}=1024\texttt{B}$，其中 `B` 表示 Byte。如果 $a$、$b$、$c$、$d$ 中的某几个数字为 $0$，那么不必输出这几个数字及其单位。题目保证一行中只有一句定义变量的语句，且每条语句都满足题干中描述的定义格式，所有的变量名都是合法的且均不重复。题目中的数据很规整，和上述给出的例子类似，除了类型后面有一个空格，以及定义数组时 `new` 后面的一个空格之外，不会出现多余的空
格。

inputFormat:
输入的第一行包含一个整数 $T$，表示有 $T$ 句变量定义的语句。

接下来 $T$ 行，每行包含一句变量定义语句。

outputFormat: 输出一行包含一个字符串，表示所有语句所占用空间的总大小。

samples:
4
int a=0,b=0;
long x=0,y=0;
String s1="hello",s2="world";
long[] arr1=new long[100000],arr2=new long[100000];

hint:
**【样例说明】**

样例 1，占用的空间为 $131072 \times 8 = 1048576$ ，换算过后正好是 $1\texttt{MB}$，其它三个单位 $\texttt{GB}$、$\texttt{KB}$、$\texttt{B}$ 前面的数字都为 $0$，所以不用输出。

样例 2，占用的空间为 $4 \times 2 + 8 \times 2 + 10 + 8 \times 100000 \times 2$ B，换算后是 $1\texttt{MB}538\texttt{KB}546\texttt{B}$。

**【评测用例规模与约定】**

对于所有评测用例，$1 \leq T \leq 10$，每条变量定义语句的长度不会超过 $1000$。所有的变量名称长度不会超过 $10$，且都由小写字母和数字组成。对于整型变量，初始化的值均是在其表示范围内的十进制整数，初始化的值不会是变量。对于 String 类型的变量，初始化的内容长度不会超过 $50$，且内容仅包含小写字母和数字，初始化的值不会是变量。对于数组类型变量，数组的长度为一个整数，范围为：$[0, 2^{30}]$，数组的长度不会是变量。$T$ 条语句定义的变量所占的内存空间总大小大于 $0$ B 且小于 $1024$ GB。

蓝桥杯 2022 国赛 A 组 C 题（C 组 D 题）。


title: [蓝桥杯 2022 国 A] 最大公约数

description: 给定一个数组，每次操作可以选择数组中任意两个相邻的元素 $x, y$ 并将其中的一个元素替换为 $\gcd(x, y)$，其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。请问最少需要多少次操作才能让整个数组只含 $1$。

inputFormat:
输入的第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $a_1, a_2,\dots, a_n$，相邻两个整数之间用一个空格分隔。

outputFormat: 输出一行包含一个整数，表示最少操作次数。如果无论怎么操作都无法满足要求，输出 $-1$。

hint:
**【评测用例规模与约定】**

- 对于 $30\%$ 的评测用例，$n \leq 500$，$a_i \leq 1000$；
- 对于 $50\%$ 的评测用例，$n \leq 5000$，$a_i \leq 10^6$；
- 对于所有评测用例，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。

蓝桥杯 2022 国赛 A 组 D 题。


title: [蓝桥杯 2022 国 A] owo

description:
小蓝很喜欢 `owo`，他现在有一些字符串，他想将这些字符串拼接起来，使得最终得到的字符串中出现尽可能多的 `owo`。

在计算数量时，允许字符重叠，即 `owowo` 计算为 $2$ 个，`owowowo` 计算为 $3$ 个。请算出最优情况下得到的字符串中有多少个 `owo`。

inputFormat:
输入的第一行包含一个整数 $n$，表示小蓝拥有的字符串的数量。

接下来 $n$ 行，每行包含一个由小写英文字母组成的字符串 $s_i$。

outputFormat: 输出 $n$ 行，每行包含一个整数，表示前 $i$ 个字符串在最优拼接方案中可以得到的 `owo` 的数量。

hint:
**【评测用例规模与约定】**

- 对于 $10\%$ 的评测用例，$n \leq 10$；
- 对于 $40\%$ 的评测用例，$n \leq 300$；
- 对于 $60\%$ 的评测用例，$n \leq 5000$；
- 对于所有评测用例，$1 \leq n \leq 10^6$，$1 \leq |s_i|,\sum|s_i| \leq 10^6$，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。字符不是 $\tt o$ 就是 $\tt w$。

蓝桥杯 2022 国赛 A 组 E 题。


title: [蓝桥杯 2022 国 A] 环境治理

description:
LQ 国拥有 $n$ 个城市，从 $0$ 到 $n - 1$ 编号，这 $n$ 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 $D$，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。

LQ 国很看重居民的出行环境，他们用一个指标 $P$ 来衡量 LQ 国的出行环境，$P$ 定义为：

$$P=\sum \limits_{i=0}^{n-1} \sum \limits_{j=0}^{n-1} d(i,j)$$

其中 $d(i,j)$ 表示城市 $i$ 到城市 $j$ 之间灰尘度最小的路线对应的灰尘度的值。

为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 $1$，但每条道路都有一个灰尘度的下限值 $L$，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。

具体的计划是这样的：

- 第 $1$ 天，$0$ 号城市对与其直接相连的道路环境进行改善；
- 第 $2$ 天，$1$ 号城市对与其直接相连的道路环境进行改善；

……
- 第 $n$ 天，$n - 1$ 号城市对与其直接相连的道路环境进行改善；
- 第 $n + 1$ 天，$0$ 号城市对与其直接相连的道路环境进行改善；
- 第 $n + 2$ 天，$1$ 号城市对与其直接相连的道路环境进行改善；

……

LQ 国想要使得 $P$ 指标满足 $P \leq Q$。请问最少要经过多少天之后，$P$ 指标可以满足 $P \leq Q$。如果在初始时就已经满足条件，则输出 $0$；如果永远不可能满足，则输出 $-1$。

inputFormat:
输入的第一行包含两个整数 $n, Q$，用一个空格分隔，分别表示城市个数和期望达到的 $P$ 指标。

接下来 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格分隔，其中第 $i$ 行第 $j$ 列的值 $D_{i,j} (D_{i,j}=D_{j,i},D_{i,i} = 0)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的那条道路的灰尘度。

接下来 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格分隔，其中第 $i$ 行第 $j$ 列的值 $L_{i,j} (L_{i,j} = L_{j,i}, L_{i,i} = 0)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的那条道路的灰尘度的下限值。

outputFormat: 输出一行包含一个整数表示答案。

hint:
**【样例说明】**

初始时的图如下所示，每条边上的数字表示这条道路的灰尘度：

![](https://cdn.luogu.com.cn/upload/image_hosting/5lz6auke.png)

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

- $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3$；
- $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1$；
- $d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0$。

初始时的 $P$ 指标为 $(2 + 3 + 1) \times 2 = 12$，不满足 $P \leq Q = 10$;

第一天，$0$ 号城市进行道路改善，改善后的图示如下：

![](https://cdn.luogu.com.cn/upload/image_hosting/mrhf5wx6.png)

注意到边 $(0, 2)$ 的值减小了 $1$，但 $(0, 1)$ 并没有减小，因为 $L_{0,1} = 2$ ，所以 $(0, 1)$ 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

- $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3$，
- $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1$，
- $d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0$。

此时 $P$ 仍为 $12$。

第二天，1 号城市进行道路改善，改善后的图示如下：

![](https://cdn.luogu.com.cn/upload/image_hosting/tjxis3yb.png)

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

- $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 2$，
- $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 0$，
- $d(2, 0) = 2, d(2, 1) = 0, d(2, 2) = 0$。

此时的 $P$ 指标为 $(2 + 2) \times 2 = 8 < Q$，此时已经满足条件。

所以答案是 $2$。

**【评测用例规模与约定】**

- 对于 $30\%$ 的评测用例，$1 \leq n \leq 10$，$0 \leq L_{i,j} \leq D_{i,j} \leq 10$；
- 对于 $60\%$ 的评测用例，$1 \leq n \leq 50$，$0 \leq L_{i,j} \leq D_{i,j} \leq 10^5$；
- 对于所有评测用例，$1 \leq n \leq 100$，$0 \leq L_{i,j} \leq D_{i,j} \leq 10^5$，$0 \leq Q \leq 2^{31} - 1$。

蓝桥杯 2022 国赛 A 组 F 题。


title: [蓝桥杯 2022 国 A] 选素数

description:
小蓝有一个数 $x$，每次操作小蓝会选择一个小于 $x$ 的素数 $p$，然后在 $x$ 成为 $p$ 的倍数前不断将 $x$ 加 $1$，（如果 $x$ 一开始就是 $p$ 的倍数则 $x$ 不变）。

小乔看到了小蓝进行了 $2$ 次上述操作后得到的结果 $n$，他想知道 $x$ 在一开始是多少。如果有多种可能，他想知道 $x$  一开始最小可以是多少，而如果不存在任何解，说明小乔看错了，此时请输出 $-1$。

inputFormat: 输入一行包含一个整数 $n$，表示经过两次操作后 $x$ 的值。

outputFormat: 输出一行包含一个整数表示 $x$ 的初始值。如果有多个解，输出最小的。如果不存在解，请输出 $-1$。

hint:
**【评测用例规模与约定】**

- 对于 $60\%$ 的评测用例，$1 \leq n \leq 5000$；
- 对于所有评测用例，$1 \leq n \leq 10^6$。

蓝桥杯 2022 国赛 A 组 G 题。


title: [蓝桥杯 2022 国 AC] 替换字符

description: 给定一个仅含小写英文字母的字符串 $s$，每次操作选择一个区间 $[l_i,r_i]$ 将 $s$ 的该区间中的所有字母 $x_i$ 全部替换成字母 $y_i$，问所有操作做完后，得到的字符串是什么。

inputFormat:
输入的第一行包含一个字符串 $s$。

第二行包含一个整数 $m$。

接下来 $m$ 行，每行包含 $4$ 个参数 $l_i,r_i,x_i,y_i$，相邻两个参数之间用一个空格分隔，其中 $l_i,r_i$ 为整数，$x_i, y_i$ 为小写字母。

outputFormat: 输出一行包含一个字符串表示答案。

samples:
abcaaea
4
1 7 c e
3 3 e b
3 6 b e
1 4 a c

hint:
**【评测用例规模与约定】**

- 对于 $40\%$ 的评测用例，$|s|, m \leq 5000$；
- 对于所有评测用例，$1 \leq |s|, m \leq 10^5$，$1 \leq l_i \leq r_i \leq |s|$，$x_i\neq y_i$，其中 $|s|$ 表示字符串 $s$ 的长度。

蓝桥杯 2022 国赛 A 组 H 题（C 组 J 题）。


title: [蓝桥杯 2022 国 A] 三角序列

background: 感谢 [Lotuses](https://www.luogu.com.cn/user/414231) 提供的数据

description:
给定 $n$ 组成对的数 $a_i, b_i$，每组数表示一个 $a_i$ 行 $a_i$ 列的如图所示的三角形：

![](https://cdn.luogu.com.cn/upload/image_hosting/hp3n8ozb.png)

其中 $b_i$ 为 $0$ 时左边较低，为 $1$ 时右边较低。

将每组数对应的三角按数的顺序从左到右拼接起来。

现给出 $m$ 组询问 $l_i, r_i, v_i$，对每组询问求最低高度 $h_i$ 使得 $l_i$ 到 $r_i$ 列之间的高度在 $h_i$ 以内的 $o$ 的数量大于等于 $v_i$。

inputFormat:
输入的第一行包含两个整数 $n, m$，用一个空格分隔。

接下来 $n$ 行，每行包含两个整数 $a_i, b_i$，用一个空格分隔。

接下来 $m$ 行，每行包含三个整数 $l_i,r_i,v_i$，相邻两个整数之间用一个空格分隔。

outputFormat: 输出一行包含一个字符串表示答案。

hint:
**【样例说明】**

第一个询问对应的范围如图所示

![](https://cdn.luogu.com.cn/upload/image_hosting/iu9yky3i.png)

**【评测用例规模与约定】**

- 对于 $30\%$ 的评测用例，$1 \leq n, m, a_i \leq 500$；
- 对于 $50\%$ 的评测用例，$1 \leq n, m, a_i \leq 5000$；
- 对于所有评测用例，$1 \leq n, m \leq 2\times10^5$，$1 \leq a_i \leq 10^6$，$0 \leq b_i \leq 1$，$1 \leq l_i \leq r_i \leq \sum a_i$，$1 \leq v_i \leq 10^{18}$。

蓝桥杯 2022 国赛 A 组 I 题。


title: [蓝桥杯 2022 国 A] 括号序列树

description:
有一棵二叉树，根结点上有一个空字符串，每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号，右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 $n$ 对括号组成的合法括号序列一一对应。

给定 $n$，求此时这棵树的最大匹配所含的边数。

inputFormat: 输入一行包含一个整数 $n$。

outputFormat: 输出一行包含一个整数表示满足条件的序列的数量，答案可能很大，请输出答案除以 $998244353$ 的余数。

hint:
**【评测用例规模与约定】**

- 对于 $20\%$ 的评测用例，$n \leq 10$；
- 对于 $40\%$ 的评测用例，$n \leq 300$；
- 对于 $60\%$ 的评测用例，$n \leq 5000$；
- 对于 $85\%$ 的评测用例，$n \leq 10^5$；
- 对于所有评测用例，$1 \leq n \leq 10^6$。

蓝桥杯 2022 国赛 A 组 J 题。


title: [蓝桥杯 2022 国 B] 卡牌

description:
这天，小明在整理他的卡牌。

他一共有 $n$ 种卡牌，第 $i$ 种卡牌上印有正整数数 $i(i \in[1, n])$, 且第 $i$ 种卡牌现有 $a_{i}$ 张。

而如果有 $n$ 张卡牌，其中每种卡牌各一张，那么这 $n$ 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了 $m$ 张空白牌, 他可以在上面写上数 $i$，将其当做第 $i$ 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 $i$ 种牌最多手写 $b_{i}$ 张。

请问小明最多能凑出多少套牌?

inputFormat:
输入共 3 行，第一行为两个正整数 $n$，$m$ 。

第二行为 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$ 。

第三行为 $n$ 个正整数 $b_{1}, b_{2}, \ldots, b_{n}$ 。

outputFormat: 一行，一个整数表示答案。

hint:
**【样例说明】**

这 $5$ 张空白牌中，拿 $2$ 张写 $1$，拿 $1$ 张写 $2$，这样每种牌的牌数就变为了 $3,3,3,4$，可以凑出 $3$ 套牌，剩下 $2$ 张空白牌不能再帮助小明凑出一套。

**【评测用例规模与约定】**

对于 $30 \%$ 的数据，保证 $n \leq 2000$;

对于 $100 \%$ 的数据，保证 $n \leq 2 \times 10^{5} ; a_{i}, b_{i} \leq n ; m \leq n^{2}$ 。

蓝桥杯 2022 国赛 B 组 C 题。


title: [蓝桥杯 2022 国 B] 最大数字

description:
给定一个正整数 $N$。你可以对 $N$ 的任意一位数字执行任意次以下 2 种操作:

1. 将该位数字加 $1$。如果该位数字已经是 $9$，加 $1$ 之后变成 $0$。

2. 将该位数字减 $1$。如果该位数字已经是 $0$，减 $1$ 之后变成 $9$。

你现在总共可以执行 $1$ 号操作不超过 $A$ 次，$2$ 号操作不超过 $B$ 次。

请问你最大可以将 $N$ 变成多少?

inputFormat: 第一行包含 3 个整数：$N$，$A$，$B$ 。

hint:
**【样例说明】**

对百位数字执行 $2$ 次 $2$ 号操作，对十位数字执行 $1$ 次 $1$ 号操作。

**【评测用例规模与约定】**

对于 $30 \%$ 的数据，$1 \leq N \leq 100 ; 0 \leq A, B \leq 10$

对于 $100 \%$ 的数据, $1 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100$

蓝桥杯 2022 国赛 B 组 D 题。


title: [蓝桥杯 2022 国 B] 出差

description:
$\mathrm{A}$ 国有 $N$ 个城市，编号为 $1 \ldots N$ 小明是编号为 $1$ 的城市中一家公司的员工，今天突然接到了上级通知需要去编号为 $N$ 的城市出差。

由于疫情原因，很多直达的交通方式暂时关闭，小明无法乘坐飞机直接从城市 $1$ 到达城市 $N$，需要通过其他城市进行陆路交通中转。小明通过交通信息网，查询到了 $M$ 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。

同样由于疫情原因，小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络，小明也查询到了各个城市的隔离信息。（由于小明之前在城市 $1$，因此可以直接离开城市 $1$，不需要隔离）

由于上级要求，小明希望能够尽快赶到城市 $\mathrm{N}$, 因此他求助于你，希望你能帮他规划一条路线，能够在最短时间内到达城市 $N$ 。

inputFormat:
第 $1$ 行：两个正整数 $N, M$ 表示 A 国的城市数量, $M$ 表示末关闭的路线数量。

第 $2$ 行: $N$ 个正整数，第 $i$ 个整数 $C_{i}$ 表示到达编号为 $\mathrm{i}$ 的城市后需要隔离的时间。

第 $3 \ldots M+2$ 行: 每行 $3$ 个正整数, $u, v, c$, 表示有一条城市 $u$ 到城市 $v$ 的双向路线仍然开通着，通过该路线的时间为 $c$。

outputFormat: 第 $1$ 行：$1$ 个正整数，表示小明从城市 $1$ 出发到达城市 $N$ 的最短时间。（到达城市 $N$，不需要计算城市 $N$ 的隔离时间）

hint:
**【样例说明】**

![](https://cdn.mathpix.com/cropped/2022_09_29_8ee8d95d6d0319bca20dg-09.jpg?height=464&width=478&top_left_y=1249&top_left_x=309)

**【评测用例规模与约定】**

对于 $100 \%$ 的数据, $1 \leq N \leq 1000,1 \leq M \leq 10000,1 \leq C_{i} \leq 200,1 \leq u, v \leq$ $N, 1 \leq c \leq 1000$

蓝桥杯 2022 国赛 B 组 E 题。


title: [蓝桥杯 2022 国 B] 费用报销

description:
小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。

为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 $K$ 天，且总金额不得超过实际差旅费用 $M$。

比如财务要求 $K=7$ 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票据，1 月 1 日及之前和 1 月 15 日及之后的票据则可以提交。

公司的同事们一起给小明凑了 $N$ 张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据, 并使总金额尽可能接近 $M$ 。

需要注意，由于这些票据都是同一年的，因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。

inputFormat:
第 $1$ 行：$3$ 个整数, $N, M, K$。

第 $2 \ldots N+1$ 行：每行 3 个整数 $m_{i}, d_{i}, v_{i}$, 第 $i+1$ 行表示第 $i$ 张票据时间的月份 $m_{i}$ 和日期 $d_{i}$，$v_{i}$ 表示该票据的面值。

outputFormat: 第 $1$ 行：$1$ 个整数, 表示小明能够凑出的最大报销金额。

hint:
**【样例说明】**

选择 1 月 3 日和 1 月 6 日的票据

**【评测用例规模与约定】**

对于 $100 \%$ 的评测用例, $1 \leq N \leq 1000,1 \leq M \leq 5000,1 \leq K \leq 50,1 \leq m_{i} \leq$ $12,1 \leq d_{i} \leq 31,1 \leq v_{i} \leq 400$

日期保证合法。

蓝桥杯 2022 国赛 B 组 F 题。


title: [蓝桥杯 2022 国 B] 故障

description:
在软件或系统开发中，我们会遇到各种各样的故障。为了从故障现象反推故障原因，工程师们会总结一种叫做相关性矩阵的二维表格，来表示故障原因与故障现象之间的关系。比如:

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/P8804.png)

其中每行表示一种故障原因，每一列表示一种故障现象。该矩阵表示故障原因 $A$ 可能产生故障现象 $2$、$3$、$4$，故障原因 $B$ 可能产生故障现象 $1$、$3$。

在实际开发过程中，如果出现了故障原因，工程师就可以根据故障现象，去计算每种故障原因产生的概率，并按照概率大小对故障原因进行排查，以达到快速定位故障原因的目的。

现在，我们假设系统开发中同一时间只会出现一种故障原因, 并且故障原 因引起各故障现象是独立事件。举个例子来说:

假设系统现在发生了故障原因 $A$, 有 $\frac{1}{3}$ 的概率出现故障现象 $2$，有 $\frac{1}{4}$ 的概率出现故障现象 $3$，有 $\frac{1}{2}$ 的概率出现故障现象 $4$。由于 $3$ 种现象是独立发生的，因此有 $\frac{1}{2 \times 3 \times 4}$ 的概率同时出现故障 $2$、$3$、$4$。

约定若相关性矩阵中没有 `x` 记号, 则表示该故障原因一定不会产生某故障现象，比如故障原因 $A$，一定不会产生故障现象 $1$。根据历史经验数据，我们统计得到了每一种故障原因出现的概率以及每一种故障原因对应的故障现象产生概率。

现在已知系统出现的故障现象，求问各个故障原因发生的概率。

inputFormat:
第 $1$ 行：$2$ 个正整数 $N, M, N$ 表示故障原因的个数（编号 $1 \ldots N)，M$ 表示故障现象的个数（编号 $1 \ldots M$）。

第 $2$ 行: $N$ 个整数，第 $i$ 个数表示故障原因 $i$ 产生的概率 $P_{i}$。

第 $3 \ldots N+2$ 行：每行 $M$ 个整数，第 $i+2$ 行第 $j$ 个整数 $P_{i j}$ 表示故障原因 $i$ 出现故障现象 $j$ 的概率（百分比）。

第 $N+3$ 行：$1$ 个正整数 $K$，表示目前出现的故障现象数量。

第 $N+4$ 行：$K$ 个正整数，依次为当前出现的故障现象编号，不会重复。

outputFormat: 第 $1 \ldots N$ 行：按概率从高到低输出每种故障原因及其可能的概率，若出现 概率相同则优先输出编号小的故障原因。第 $1$ 个数为故障原因编号, 第 $2$ 个数为故障概率（百分比），保留 $2$ 位小数。

hint:
对于所有测试用例，$1 \leq N \leq 40,1 \leq M \leq 20,0 \leq P_{i} \leq 100, \sum\left(P_{i}\right)=100$, $0 \leq P_{i j} \leq 100$。

蓝桥杯 2022 国赛 B 组 G 题。


title: [蓝桥杯 2022 国 B] 机房

description:
这天，小明在机房学习。

他发现机房里一共有 $n$ 台电脑，编号为 1 到 $n$，电脑和电脑之间有网线连接，一共有 $n-1$ 根网线将 $n$ 台电脑连接起来使得任意两台电脑都直接或者间接地相连。

小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连，而信息在网线中的传播时间可以忽略。比如如果某台电脑用网线直接连接了另外 $d$ 台电脑, 那么任何经过这台电脑的信息都会延迟 $d$ 单位时间 (发送方和接收方也会产生这样的延迟，当然如果发送方和接收方都是 同一台电脑就只会产生一次延迟)。

小明一共产生了 $m$ 个疑问：如果电脑 $u_{i}$ 向电脑 $v_{i}$ 发送信息，那么信息从 $u_{i}$ 传到 $v_{i}$ 的最短时间是多少?

inputFormat:
输入共 $n+m$ 行，第一行为两个正整数 $n, m$ 。

后面 $n-1$ 行，每行两个正整数 $x, y$ 表示编号为 $x$ 和 $y$ 的两台电脑用网线 直接相连。

后面 $m$ 行，每行两个正整数 $u_{i}, v_{i}$ 表示小明的第 $i$ 个疑问。

outputFormat: 输出共 $m$ 行，第 $i$ 行一个正整数表示小明第 $i$ 个疑问的答案。

hint:
**【样例说明】**

这四台电脑各自的延迟分别为 $2,2,1,1$ 。

对于第一个询问, 从 $2$ 到 $3$ 需要经过 $2,1,3$, 所以时间和为 $2+2+1=5$。对于第二个询问，从 $3$ 到 $4$ 需要经过 $3,1,2,4$，所以时间和为 $1+2+2+1=6$。

对于第三个询问，从 $3$ 到 $3$ 只会产生一次延迟, 所以时间为 1。

**【评测用例规模与约定】**

对于 $30 \%$ 的数据，保证 $n, m \leq 1000$;

对于 $100 \%$ 的数据，保证 $n, m \leq 10^5$。

蓝桥杯 2022 国赛 B 组 H 题。


title: [蓝桥杯 2022 国 B] 齿轮

description:
这天，小明在组装齿轮。

他一共有 $n$ 个齿轮，第 $i$ 个齿轮的半径为 $r_{i}$, 他需要把这 $n$ 个齿轮按一定顺序从左到右组装起来，这样最左边的齿轮转起来之后，可以传递到最右边的齿轮，并且这些齿轮能够起到提升或者降低转速（角速度）的作用。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_8ee8d95d6d0319bca20dg-17.jpg)

小明看着这些齿轮，突然有 $Q$ 个疑问: 能否按一定顺序组装这些齿轮使得最右边的齿轮的转速是最左边的齿轮的 $q_{i}$ 倍?

inputFormat:
输入共 $Q+2$ 行，第一行为两个正整数 $n, Q$, 表示齿轮数量和询问数量。

第二行为 $n$ 个正整数 $r_{1}, r_{2}, \ldots, r_{n}$，表示每个齿轮的半径。

后面 $Q$ 行，每行一个正整数 $q_{i}$ 表示询问。

outputFormat: $Q$ 行，对于每个询问，如果存在至少一种组装方案满足条件，输出 `YES`, 否则输出 `NO`。

hint:
**【样例说明】**

询问 $1$ 方案之一：`23341`。

询问 $2$ 方案之一：`42331`。

询问 $3$ 没有方案。

**【评测用例规模与约定】**

对于 $15 \%$ 的数据，保证 $n, Q \leq 100$;

对于 $30 \%$ 的数据，保证 $n, Q \leq 2000$;

对于 $100 \%$ 的数据，保证 $n\ge 2,n, Q \leq 2 \times 10^{5} ; a_{i}, q_{i} \leq 2 \times 10^{5}$。

蓝桥杯 2022 国赛 B 组 I 题。


title: [蓝桥杯 2022 国 B] 搬砖

description:
这天，小明在搬砖。

他一共有 $n$ 块砖，他发现第 $i$ 砖的重量为 $w_{i}$，价值为 $v_{i}$。他突然想从这些砖中选一些出来从下到上堆成一座塔，并且对于塔中的每一块砖来说，它上面所有砖的重量和不能超过它自身的价值。

他想知道这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。

inputFormat:
输入共 $n+1$ 行, 第一行为一个正整数 $n$, 表示砖块的数量。

后面 $n$ 行, 每行两个正整数 $w_{i}, v_{i}$ 分别表示每块砖的重量和价值。

outputFormat: 一行，一个整数表示答案。

hint:
**【样例说明】**

选择第 $1$、$2$、$4$ 块砖，从上到下按照 $2$、$1$、$4$ 的顺序堆成一座塔，总价值为 $4+1+5=10$。

**【评测用例规模与约定】**

对于 $20 \%$ 的数据，保证 $n \leq 10$;

对于 $100 \%$ 的数据，保证 $n \leq 1000 ; w_{i} \leq 20 ; v_{i} \leq 20000$ 。

蓝桥杯 2022 国赛 B 组 J 题。


title: [蓝桥杯 2022 国 C] 取模

description: 给定 $n, m$，问是否存在两个不同的数 $x,y$ 使得 $1 \le x < y \le m$ 且 $n \bmod x = n \bmod y$。

inputFormat:
输入包含多组独立的询问。

第一行包含一个整数 $T$ 表示询问的组数。

接下来 $T$ 行每行包含两个整数 $n,m$，用一个空格分隔，表示一组询问。

outputFormat: 输出 $T$ 行，每行依次对应一组询问的结果。如果存在，输出单词 `Yes`；如果不存在，输出单词 `No`。


title: [蓝桥杯 2022 国 C] 斐波那契数组

description:
如果数组 $A = (a_0,a_1,\cdots,a_{n − 1})$ 满足以下条件，就说它是一个斐波那契数组：

1. $n>2$。
2. $a_0=a_1$。
3. 对于所有的 $i\ge2$ 都有 $a_i=a_{i-1}+a_{i-2}$。

现在，给出一个数组 $A$，你可以执行任意次修改，每次修改将数组中的某个位置的元素修改为一个大于 $0$ 的整数。请问最少修改几个元素之后，数组 $A$ 会变成一个斐波那契数组。

inputFormat:
输入的第一行包含一个整数 $n$，表示数组 $A$ 中的元素个数。

第二行包含 $n$ 个整数 $a_0,a_1,\cdots,a_{n−1}$，相邻两个整数之间用一个空格分隔。

outputFormat: 输出一行包含一个整数表示最少需要修改数组 $A$ 中的几个元素之后，数组 $A$ 可以变为一个斐波那契数组。

hint:
**【样例说明】**

将原数组修改为 $(1,1,2,3,5)$，最少修改三个元素变成了一个斐波那契数组。

**【评测用例规模与约定】**

对于所有评测用例， $3 ≤ n ≤ 10^5$，$1 ≤ a_i ≤ 10^6$。

蓝桥杯 2022 国赛 C 组 E 题。


title: [蓝桥杯 2022 国 C] 近似 GCD

description:
 小蓝有一个长度为 $n$ 的数组 $A = (a_1,a_2,\cdots,a_n)$，数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数组中所有元素的最大公约数。如果最多更改数组中的一个元素之后，数组的最大公约数为 $g$，那么称 $g$ 为这个数组的近似 GCD。一个数组的近似 GCD 可能有多种取值。

具体的，判断 $g$ 是否为一个子数组的近似 GCD 如下：

1. 如果这个子数组的最大公约数就是 $g$，那么说明 $g$ 是其近似 GCD。
2. 在修改这个子数组中的一个元素之后（可以改成想要的任何值），子数组的最大公约数为 $g$，那么说明 $g$ 是这个子数组的近似 GCD。

小蓝想知道，数组 $A$ 有多少个长度大于等于 $2$ 的子数组满足近似 GCD 的值为 $g$。

inputFormat:
输入的第一行包含两个整数 $n,g$，用一个空格分隔，分别表示数组 $A$ 的长度和 $g$ 的值。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$，相邻两个整数之间用一个空格分隔。

outputFormat: 输出一行包含一个整数表示数组 $A$ 有多少个长度大于等于 $2$ 的子数组的近似 GCD 的值为 $g$。

hint:
**【样例说明】**

满足条件的子数组有 $5$ 个 ：

$[1,3]$：将 $1$ 修改为 $3$ 后，这个子数组的最大公约数为 $3$，满足条件。

$[1,3,6]$：将 $1$ 修改为 $3$ 后，这个子数组的最大公约数为 $3$，满足条件。

$[3,6]$：这个子数组的最大公约数就是 $3$，满足条件。

$[3,6,4]$：将 $4$ 修改为 $3$ 后，这个子数组的最大公约数为 $3$，满足条件。

$[6,4]$：将 $4$ 修改为 $3$ 后，这个子数组的最大公约数为 $3$，满足条件。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$2\le n\le100$；

对于 $40\%$ 的评测用例，$2\le n\le1000$；

对于所有评测用例，$2\le n\le10^5$，$1\le g,a_i \le10^9$。

蓝桥杯 2022 国赛 C 组 F 题。


title: [蓝桥杯 2022 国 C] 数组个数

description:
  小蓝有一个长度为 $n$ 的数组 $B = (b_0,b_1,\cdots,b_{n−1})$，数组 $B$ 是由另一个长度为 $n$ 的环形数组 $A = (a_0,a_1,\cdots,a_{n−1})$ 经过一次相邻最大化操作得到的，其中 $a_i$ 与 $a_{i+1}$ 相邻，$a_0$ 与 $a_{n−1}$ 相邻。

形式化描述为：

$$
b_i=
\begin{cases}
\max\{a_{n-1},a_0,a_1\}& i=0\\
\max\{a_{i-1},a_i,a_{i+1}\}& 0<i<n-1\\
\max\{a_{n-2},a_{n-1},a_0\}& i=n-1\\
\end{cases}
$$

小蓝想知道，可能有多少个满足条件的数组 $A$，经过一次相邻最大化操作后能得到数组 $B$，注意 $A$ 中的每个元素都要求为非负整数。

inputFormat:
输入的第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $b_0,b_1,\cdots,b_{n−1}$，相邻两个整数之间用一个空格分隔。

outputFormat: 输出一行包含一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$（即 $10^9+7$）后的余数。


title: [蓝桥杯 2022 国 C] 六六大顺

description:
六六大顺，本指农历六月初六。多用于祝福中年人士家庭幸福，工作顺利，事业有成，身体健康。源自《左传》“君义，臣行，父慈，子孝，兄爱，弟敬，此数者累谓六顺也。”

$6$ 在我国自古以来是一个吉祥的数字，定义数列 $A = (a_1,a_2,\cdots,a_i,\cdots)$，其中 $a_1 = 6, a_2 = 66, \cdots, a_i = 10\cdot a_{i−1}+6$。

定义一个数列 $B = (b_1,b_2,\cdots,b_i,\cdots)$，其中 $b_1 = 6 \times 6, b_2 = 66\times66, \cdots, b_i = a_i \times a_i$。

现在小蓝想知道数列 $B$ 的前 $n$ 项的和是多少，你能帮帮小蓝吗？

inputFormat: 输入一行包含一个正整数 $n$。

outputFormat: 输出一行包含一个整数表示数列 $B$ 前 $n$ 项的和。


title: [蓝桥杯 2022 国 C] 打折

description:
小蓝打算采购 $n$ 种物品，每种物品各需要 $1$ 个。

小蓝所住的位置附近一共有 $m$ 个店铺，每个店铺都出售着各种各样的物品。

第 $i$ 家店铺会在第 $s_i$ 天至第 $t_i$ 天打折，折扣率为 $p_i$，对于原件为 $b$ 的物品，折后价格为 $\lfloor\frac {b\cdot p_j}{100}\rfloor$。其它时间需按原价购买。

小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花多少钱才能买到需要的所有物品。

题目保证小蓝一定能买到需要的所有物品。

inputFormat:
输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示物品的个数和店铺的个数。

接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包含四个整数 $s_i,t_i, p_i,c_i$，相邻两个整数之间用一个空格分隔，分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接 $c_i$ 行，每行包含两个整数 $a_j,b_j$，用一个空格分隔，分别表示该商店的第 $j$ 个商品的类型和价格。商品的类型由 $1$ 至 $n$ 编号。

outputFormat: 输出一行包含一个整数表示小蓝需要花费的最少的钱数。

hint:
对于 $40\%$ 的评测用例，$n,m≤500，s_i ≤t_i ≤100，\sum c_i ≤2000$；

对于 $70\%$ 的评测用例，$n,m≤5000，\sum c_i ≤20000$；

对于所有评测用例，$1 ≤ n,m ≤ 10^5，1 ≤ c_i ≤ n，\sum c_i ≤ 4\times10^5，1 ≤ s_i ≤t_i ≤10^9，1 < p_i < 100，1≤a_j ≤n，1≤b_j ≤10^9$。

蓝桥杯 2022 国赛 C 组 I 题。


title: [NOI2022] 树上邻域数点

background:
**这是一道交互题。**

**在提交本题前请务必仔细阅读以下内容。**

本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。

由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 ```#include "count.h"``` 语句，并将下发文件 **`count_.h`** （注意并不是 `count.zip` 里的 `count.h`）中的内容粘贴到代码最开头，然后提交。

如果您无法打开 `count_.h`，那么可以复制下面的内容。

```cpp
#ifndef CIRCLE_H
#define CIRCLE_H
#include<vector>
struct info{
  unsigned val;
  unsigned poi[2];
};
const info emptyinfo=info{0,(unsigned)-1,(unsigned)-1};
info MR(info a,info b);
info MC(info a,info b);
void init(int T,int n,int q,std::vector<int>dad,std::vector<info>ve,int M);
bool isempty(info a);
info ask(int x,int d);

#endif
```

如果您在提交本题时出现了任何意外的情况，请咨询管理员。

description:
给出五元组 $(T, I, S_V, S_E, \iota)$，其中：

- $T$ 是一棵 $n$ 个点的有根树 $T = (V, E)$，其中 $V$ 为 $T$ 的点集，$E$ 为 $T$ 的边集。树的节点被编号为 $1, 2, \ldots, n$，其中根节点编号为 $1$。
- $I$ 是一个集合，集合中的元素称作**信息**。其中有两个不同的特殊元素：单位元 $\epsilon$ 和不合法信息 $\bot$。

对于一般的信息，其都具有**点集合**和**边集合**两个属性。特别的，对于单位元，其只有边集合的属性，而对于不合法信息，其没有以上两种属性。

- 对于信息 $o \in I \setminus \{ \epsilon, \bot \}$，$o$ 的**点集合**是 $V$ 的一个二元子集，记作 $S_V(o)$，满足 $S_V(o) \subseteq V$ 且 $\lvert S_V(o) \rvert = 2$。其中，两个集合 $A, B$ 的差 $A \setminus B$ 被定义为 $A \setminus B = \{ x \in A \hspace{3mu}\vert\hspace{3mu} x \notin B \}$。
- 对于信息 $o \in I \setminus \{ \bot \}$，$o$ 的**边集合**是 $E$ 的一个子集，记作 $S_E(o)$，满足 $S_E(o) \subseteq E$。规定单位元的边集合为空，也即 $S_E(\epsilon) = \varnothing$。
- 对于树上的任何一条边 $e \in E$，记 $e = (u, v)$，存在一个关于 $e$ 的信息 $\iota(e) \in I$，它以其端点为点集合、自身为边集合，即 $S_V(\iota(e)) = \{ u, v \}$、$S_E(\iota(e)) = \{ e \}$。

信息有两种合并的方式，分别记作 $R$ 和 $C$。对于 $\forall a, b \in I$，记 $r = R(a, b), c = C(a, b)$，满足 $r, c \in I$，则：

- 单位元和任何信息合并都得到对方。也即，如果 $a = \epsilon$，那么 $r = c = b$；如果 $b = \epsilon$，那么 $r = c = a$。
- 不合法信息和任何信息合并都得到不合法信息。也即，如果 $a = \bot$ 或者 $b = \bot$，那么 $r = c = \bot$。
- 对于剩下的情况，如果两个信息的**边集合**的交集非空，或者**点集合**的交集的大小不为 $1$，则合并得到不合法信息。也即，如果 $S_E(a) \cap S_E(b) \ne \varnothing$ 或 $\lvert S_V(a) \cap S_V(b) \rvert \ne 1$，则 $r = c = \bot$。
- 否则，有
  $$ S_E(r) = S_E(c) = S_E(a) \cup S_E(b) \text{,} $$
  $$ S_V(r) = S_V(a) \text{,} $$
  $$ S_V(c) = S_V(a) \oplus S_V(b) \text{,} $$
  其中 $\oplus$ 表示集合的对称差运算，也即 $A \oplus B = (A \cup B) \setminus (A \cap B)$。

定义 $T$ 中两个点的树上距离为树上以两个点为端点的唯一简单路径经过的边数。

给出评分参数 $M$ 和 $q$ 次询问，每次询问给出树上的一个点 $u$ 和一个非负整数 $d$。记点集 $X$ 为 $T$ 中所有与 $u$ 的树上距离不超过 $d$ 的点构成的集合，又记边集 $Y = \{ (a, b) \in E \hspace{3mu}\vert\hspace{3mu} a, b \in X \}$ 为 $X$ 内部的边集。可以证明，从 $\epsilon$ 和所有 $\iota(e)$（$e \in E$）出发，总是能通过有限次 $R, C$ 的调用得到信息 $o \ne \bot$ 满足 $S_E(o) = Y$。

每组询问中，你需要在 $R$ 和 $C$ 的调用次数总和不超过 $M$ 的限制下构造出一个满足这样的要求的信息 $o$。特别地，如果 $d = 0$，则直接返回单位元 $\epsilon$ 即可。

----

**【实现细节】**

请确保你的程序开头有 `#include "count.h"`。

头文件 `count.h` 中实现了如下内容：

1. 定义了信息对应的数据类型 `info`；
2. 定义了 $\epsilon$ 所对应的 `info` 类型常量 `emptyinfo`，你可以在程序中直接使用。
3. 定义并实现了以下两个信息合并函数，你可以在程序中直接调用：

   ```cpp
   info MR(info a,info b);
   info MC(info a,info b);
   ```

   - 两个函数分别返回 $R(a, b)$ 与 $C(a, b)$ 对应的信息。

   **你需要保证调用 $\boldsymbol{R(a, b)}$ 与 $\boldsymbol{C(a, b)}$ 时结果不为 $\boldsymbol{\bot}$，否则程序可能会出现异常行为。**
4. 定义并实现了判定一个信息是否为单位元的函数，你可以在程序中直接调用：
   ```cpp
   bool isempty(info a);
   ```
   - 这个函数返回真当且仅当 $a$ 为单位元。

可以查看参考交互库了解更多实现细节。

**你不需要，也不应该实现主函数。** 你需要实现如下几个函数：

```cpp
void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);
```

- `T` 表示测试点编号，`n` 表示树的点数，`q` 表示询问数，`M` 表示该测试点的评分参数。
- `fa` 和 `e` 的长度均为 $n - 1$。对于 $0 \le i < n - 1$，$fa[i]$ 和 $i + 2$ 为第 $i$ 条边 $e_i$ 的两个端点，$e[i]$ 为题目描述中提到的 $\iota(e_i)$ 所对应的 `info` 类型元素。数据保证 $fa[i]$ 小于 $i + 2$。

```cpp
info ask(int u, int d);
```

给出一个询问，参数的意义见题目描述。你需要在函数结束时返回一个满足题设条件的信息。

最终测试时，在每个测试点，交互库会**恰好**调用一次 `init` 函数，随后调用 $q$ 次 `ask`函数。交互库会使用特殊的实现方式，单个 `info` 类型的变量会恒定消耗 $12$ 字节内存，**这与下发的参考交互库不同**。为保证程序运行时内存使用在题目限制内，你需要保证运行过程中没有过多的 `info` 类型变量同时存在。

保证在满足调用次数限制且不进行 `isempty` 函数调用的情况下，最终测试的交互库运行所需的时间不超过 0.6 秒，交互库本身所消耗的内存不超过 16 MiB。保证在只执行 ${10}^8$ 次 `isempty` 函数调用的情况下，最终测试的交互库运行的时间不超过 0.25 秒。

在下发文件中包含一个名为 `count.cpp` 的文件，作为示例程序，选手可以在此基础上继续实现本题。在下发文件中还额外包含一个名为 `count_backup.h` 的备份文件，我们保证其与 `count.h` 文件完全相同。

----

**【测试程序方式】**

本题目录下提供了两个交互库的参考实现 `grader.o`、`checker.o`，其为两个不同的交互库编译产生的可链接文件。最终测试时所用的交互库实现与该实现有不同，因此选手的解法**不应依赖交互库的具体实现**，同时也不应该依赖 `count.h` 中 `info` 类型的具体实现。

你需要修改下发的 `count.h` 来帮助进行链接。具体的，在将源代码 `count.cpp` 和程序 `grader.o` 进行链接的时候，你需要注释掉 `count.h` 代码的第 5 行，并保留第 4 行的代码。链接 `checker.o` 方法类似，需要注释掉 `count.h` 代码的第 4 行，并保留第 5 行的代码。选手可以对 `count.h` 的实现自行修改来实现不同程序的编译。

修改后，选手可以在本题目录下使用如下命令编译得到可执行程序：

```bash
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o grader.o -o count
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o checker.o -o count
```

其中第一行命令会编译当前 `count.cpp` 后与 `grader.o` 链接起来，生成可执行文件 `count`，第二行命令则会编译当前 `count.cpp` 后与 `checker.o` 链接起来，生成可执行文件 `count`。

按上述方法编译得到的可执行文件 `count`，其运行方式如下：

- 可执行文件将从标准输入读入以下格式的数据：
  - 第一行四个整数 $id, n, q, M$，分别表示测试点编号、树的点数、询问数和评分参数；
  - 第二行 $n - 1$ 个整数 $p_2, p_3, \ldots, p_n$，分别表示 $2$ 至 $n$ 的父亲节点编号，在本地调试时你需要保证 $\forall i \in [2, n]$，$p_i < i$；
  - 接下来 $q$ 行每行两个整数 $u, d$，描述一次询问。
- 读入之后，交互库会进行测试。如果你的程序不满足交互库限制，其会在输出中返回对应的错误信息。否则，对于链接的可执行文件，其输出如下：
  - 总共一行三个整数 $C_1, C_2, C_3$，其中：
    - $C_1$ 表示程序在 `init` 函数中调用交互库函数的总次数；
    - $C_2$ 表示程序在运行过程中调用交互库函数的总次数；
    - $C_3$ 表示程序在 $q$ 次 `ask` 函数中调用交互库函数的次数的最大值。
    - 对于上述三个统计量，我们只会计入 `MR`、`MC` 函数的调用次数，而不会计入 `isempty` 函数的调用次数。
- 在链接不同文件的时候，其能够进行的检查也不同，具体地：
  - `grader.o`：其在运行时不会检查 `ask` 函数返回的信息是否正确，但可以帮助选手判断交互操作是否符合要求。这份程序运行时间最接近评测时的交互库，因此选手可以利用该程序测试运行速度，但不保证程序正确性。
  - `checker.o`：其在运行时会检查 `ask` 函数返回的信息是否正确，也可以帮助选手判断交互操作是否符合要求。同时其会检查 `ask` 函数返回的信息是否正确。这份程序可以进行答案正确性的检查。

选手在调试时需要保证输入可执行文件 `count` 的数据满足上述输入格式，否则不保证输出结果正确。

inputFormat: 见【测试程序方式】。

outputFormat: 见【测试程序方式】。

hint:
**【评分方式】**

最终评测**只会**收取 `count.cpp`，修改选手目录下其他文件不会对评测结果产生影响。**注意：**

- **未初始化的 `info` 类型的变量不保证是 `emptyinfo`。**
- **请不要尝试访问或修改 `info` 类型的成员变量，否则将被视为攻击交互库。**
- **请不要在 `init` 函数调用之前调用 `MR` 和 `MC` 函数，否则可能会发生未定义行为。**
- **你只能访问自己定义的变量和交互库返回的 `info` 类型变量，尝试访问其他空间将可能导致编译错误或运行时错误。**

**本题首先会受到和传统题相同的限制**，例如编译错误会导致整道题目得 0 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。

在上述条件以外，在一个测试点中，若程序执行了非法的函数调用或询问操作中给出了错误回答，该测试点将会获得 0 分。否则，记 $C_1, C_3$ 分别表示你的程序在 `init` 函数中调用交互库函数的次数，和你的程序在所有 $q$ 次 `ask` 函数中调用交互库函数的次数的最大值。如果 $C_1 \le 3 \cdot {10}^7$ 且 $C_3$ 不超过该测试点的评分参数 $M$，你将获得该测试点的分数，否则你无法获得该测试点的分数。注意：计算 $C_1, C_3$ 时只会计入 `MR`、`MC` 函数的调用次数，而不会计入 `isempty` 函数的调用次数。

----

**【样例 \#1】**

见附件中的 `count/count1.in` 与 `count/count1.ans`。

----

**【样例 \#2】**

见附件中的 `count/count2.in` 与 `count/count2.ans`。

该组样例满足数据范围中的特殊性质 A。

----

**【样例 \#3】**

见附件中的 `count/count3.in` 与 `count/count3.ans`。

该组样例满足数据范围中的特殊性质 B。

----

**【样例 \#4】**

见附件中的 `count/count4.in` 与 `count/count4.ans`。

----

**【数据范围】**

对于所有测试点，$1 \le n \le 2 \times {10}^5$，$1 \le q \le {10}^6$；每组询问中，有 $1 \le u \le n$，$1 \le d \le n - 1$。

| 测试点   | $n=$              | $q=$            | 特殊性质 | $M=$  |
|:-----:|:-----------------:|:---------------:|:----:|:-----:|
| $1$   | $1000$            | $10^4$          |      | $500$ |
| $2$   | $2000$            | $10^4$          |      | $500$ |
| $3,4$ | $10^5$            | $10^6$          | A    | $5$   |
| $5,6$ | $6 \times 10^4$   | $6\times 10^4$  | B    | $50$  |
| $7$   | $6 \times 10^4$   | $6 \times 10^4$ | B    | $5$   |
| $8$   | $10^5$            | $10^5$          | B    | $5$   |
| $9$   | $7500$            | $5 \times 10^4$ | C    | $500$ |
| $10$  | $10^4$            | $5 \times 10^4$ |      | $500$ |
| $11$  | $1.5 \times 10^4$ | $5 \times 10^4$ |      | $500$ |
| $12$  | $2 \times 10^4$   | $5 \times 10^4$ |      | $50$  |
| $13$  | $2.5 \times 10^4$ | $5 \times 10^4$ |      | $5$   |
| $14$  | $3 \times 10^4$   | $10^5$          |      | $5$   |
| $15$  | $6 \times 10^4$   | $10^6$          | D    | $5$   |
| $16$  | $6 \times 10^4$   | $10^6$          |      | $5$   |
| $17$  | $8 \times 10^4$   | $10^6$          |      | $5$   |
| $18$  | $10^5$            | $10^6$          |      | $5$   |
| $19$  | $1.5 \times 10^5$ | $10^6$          |      | $5$   |
| $20$  | $2 \times 10^5$   | $10^6$          |      | $1$   |

特殊性质 A：保证 $\forall i \in [1, n - 1]$，编号为 $i + 1$ 的点的父节点为 $i$。
特殊性质 B：保证所有询问均满足 $u = 1$。
特殊性质 C：保证所有询问均满足 $d \le 100$。
特殊性质 D：保证所有询问均满足 $d \ge 1000$。