title: 【模板】快速读入

background: 制约解除作战！

description: 给你 $n$ 个数，你需要求和并输出。

inputFormat:
第一行一个整数 $n$。

之后一行 $n$ 个整数以空格隔开，表示给定的 $n$ 个数。

outputFormat: 一行一个数表示给定的数的和。

hint:
对于 $25\%$ 的数据，满足 $n=10^5$。

对于 $25\%$ 的数据，满足 $n=10^6$。

对于 $25\%$ 的数据，满足 $n=10^7$。

对于 $25\%$ 的数据，满足 $n=10^8$。

对于 $100\%$ 的数据，满足所有数在 $[-n,n]$ 之间。

数据保证对于序列的任何前缀，这个前缀的和在 32 位有符号整形的存储范围内。


title: [EGOI2024] Infinite Race / 无限赛跑

type: P

background:
Day 1 Problem A.

题面译自 [EGOI2024 infiniterace](https://wiki.egoi2024.nl/tasks/infiniterace/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

description:
每年在埃因霍温都会举行一场马拉松。今年，组织者们想出了一个特别的点子，比赛不再在 42 公里后结束，而是无限进行下去！为了简化组织工作，比赛在埃因霍温大学的一个跑道上进行，参赛者在跑道上无限循环。

Anika 很高兴成为 $N$ 名参赛者之一，编号从 $0$ 到 $N - 1$。她很快报名，因此她是参赛者 $0$。她在终点线后起跑，其他参赛者都在她前面。Anika 无法记住她跑了多少圈，但她记得何时超越了某人或何时被某人超越。她至少需要多少次越过终点线？没有人会后退，也不会在终点线上发生超车。此外，参赛者的速度不一定是恒定的。

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

inputFormat:
输入的第一行包含一个整数 $N$，表示参赛者的数量。

第二行包含一个整数 $Q$，表示事件的数量。

接下来的 $Q$ 行按比赛过程中发生的顺序描述事件。第 $i$ 行包含一个整数 $x_i$。

- 如果 $x_i > 0$，表示 Anika 超越了参赛者 $x_i$。
- 如果 $x_i < 0$，表示参赛者 $-x_i$ 超越了 Anika。

outputFormat: 输出一个整数，表示 Anika 至少穿过终点线的次数。

hint:
**样例解释**

在第一个样例中，有 $N = 4$ 名参赛者和 $Q = 5$ 个事件。Anika 首先被参赛者 $2$ 超越，后者现在比她快一整圈。然后她反超 $2$，接着超越 $1$，随后被 $3$ 超越。在此时，Anika 仍然可以在她的第一圈。最后，她再次超越 $2$，为了实现这一点，意味着她至少穿过了终点线一次。

在第二个样例中，除了 Anika 之外只有一个参赛者。Anika 四次超越了另一个参赛者，这意味着 Anika 至少穿过终点线三次。

---

**数据范围**

对于全部数据，$2 \le N \le 2\times 10^5$，$1 \le Q \le 2\times 10^5$，$1 \le x \le N - 1$ 或 $-(N - 1) \le x \le -1$。

- 子任务一（$29$ 分）：$N=2$。
- 子任务二（$34$ 分）：$x_i > 0$。
- 子任务三（$22$ 分）：$N,Q\le 100$。
- 子任务四（$15$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。


title: [EGOI2024] Bouquet / 花束制作

background:
Day 1 Problem B.

题面译自 [EGOI2024 bouquet](https://wiki.egoi2024.nl/tasks/bouquet/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

description:
参观了世界上最大的花园之一库肯霍夫后，Lieke 非常喜欢花，因此她决定收集一些路边生长的郁金香来制作一个漂亮的花束。然而，在收集花朵时，她必须遵守荷兰严格的郁金香保护法的一些规定。

沿着道路从左到右有 $N$ 株郁金香，编号从 $0$ 到 $N - 1$。郁金香保护法为郁金香 $i$ 分配了两个整数，$l_i$ 和 $r_i$。如果郁金香 $i$ 被包含在花束中，则郁金香 $i$ 左边紧邻的 $l_i$ 株郁金香和右边紧邻的 $r_i$ 株郁金香不能包含在花束中。注意，如果郁金香 $i$ 左边的郁金香少于 $l_i$ 株，或者右边的郁金香少于 $r_i$ 株，那么该侧所有的郁金香仍然不能包含在花束中（允许溢出）。

Lieke 想知道如果她最佳地选择花朵，最多能摘取多少株郁金香。帮她找到这个问题的答案，制作一个漂亮的花束吧！

inputFormat:
输入的第一行包含一个整数 $N$，表示沿路生长的郁金香数量。

接下来的 $N$ 行描述了郁金香保护法的信息：第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，表示郁金香 $i$ 的保护限制。

outputFormat: 输出一个整数，表示 Lieke 在遵守保护法的情况下可以摘取的最大郁金香数量。

hint:
**样例解释**

在第一个样例中，如果 Lieke 摘取郁金香 $0$，她不能摘取右边的两朵郁金香。摘取郁金香 $1$ 并不禁止她摘取郁金香 $2$，但郁金香 $2$ 禁止她摘取郁金香 $1$，因此她不能同时摘取它们。所以，Lieke 可以摘取的最大花朵数量是 $1$。

在第二个样例中，Lieke 可以摘取的郁金香数量最多是 $3$，获得此结果的方式如图所示。其他摘取郁金香的方式会导致更小的答案。

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

在第三个样例中，通过摘取郁金香 $0, 1, 3$ 和 $6$ 可以获得最多的 $4$ 朵郁金香。

---

**数据范围**

对于全部数据，$1\le N\le 2\times 10^5$，$0\le l_i,r_i\le N$。

- 子任务一（$8$ 分）：对于任意 $(i,j)$，$l_i=r_i=l_j=r_j$。
- 子任务二（$16$ 分）：$r_i=0$。
- 子任务三（$28$ 分）：$N\le 1000$。
- 子任务四（$18$ 分）：$l_i,r_i\le 2$。
- 子任务五（$30$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。


title: [EGOI2024] Team Coding / 团队编程

background:
Day 1 Problem C.

题面译自 [EGOI2024 teamcoding](https://wiki.egoi2024.nl/tasks/teamcoding/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

description:
埃因霍温巨型开源研究所（Eindhoven Gigantic Open-Source Institute，EGOI）公司有着非常严格的层级结构。除了 CEO Anneke，公司里的其他 $N - 1$ 名员工每人都有一个唯一的上司，并且层级结构中没有循环。你可以将公司的层级结构看作是以 Anneke 为根的树。由于这是一个多元化的公司，员工使用 $K$ 种不同的编程语言，但每位员工都有一种首选的编程语言。

Anneke 为公司团队准备了一个大型的新项目，她希望能投入尽可能多的资源。为了决定哪个团队来负责这个项目，她执行以下操作：

1. 选择一个人来领导团队。这也将确定项目使用的编程语言。每个在该团队领导下的子树中的员工且首选编程语言与团队领导相同的员工将参与这个项目。
2. 通过将首选编程语言与团队领导相同的员工调入她的团队来增加参与项目的员工数量。

    为了最大化参与项目的员工数量，她可以多次执行以下调换操作：
    1. 她选择两名员工：
        - 一名当前在团队领导的子树中且首选编程语言与团队领导不同的员工。
        - 一名当前不在此子树中且首选编程语言与团队领导相同的员工。此外，这名员工需要与另一名被选中的员工处于相同的层级，即他们在向 Anneke 报告的链中有相同数量的上司。如果你将公司层级结构看作一棵树，那么这两名员工处于树的同一层级。
    2. 这两名员工（且**仅**他们）交换公司层级结构中的位置。注意，报告给这两名员工的员工保持不变，只是更改了他们报告的对象。在下面的例子中，选择员工 $4$ 作为团队领导时，我们可以交换员工 $3$ 和 $2$，但不能交换员工 $1$ 和 $8$。

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

找出能够参与新项目的最大员工数量，以及实现这一目标所需的最少调换次数。

inputFormat:
输入的第一行包含两个整数，$N$ 和 $K$，分别表示 EGOI 的员工数量和员工可能使用的编程语言的数量。

EGOI 的员工编号从 $0$ 到 $N - 1$，CEO Anneke 的编号为 $0$。下一行包含 $N$ 个整数 $l_i$，其中 $0 \le l_i < K$，表示员工的首选编程语言。

接下来的 $N - 1$ 行包含公司的结构。第 $i$ 行包含一个整数 $b_i$，其中 $0 \le b_i < N$，表示第 $i$ 号员工的直接上司。注意，$i$ 的取值范围是 $1$ 到 $N - 1$（包含两端），因为 CEO Anneke 没有上司。

outputFormat: 输出一行包含两个整数，$P$ 和 $S$，表示通过任意次数的调换能够达到的最大参与项目的员工数量（包括团队领导）和实现这一目标所需的**最少**调换次数。

hint:
**样例解释**

在前两个样例中，公司结构如下所示，其中模式编码了编程语言（0 = “条纹”，1 = “点状”，2 = “纯色”）：

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

在样例 1 中，我们可以选择员工 $1$ 作为团队负责人，员工 $4$ 喜欢相同的编程语言，并且没有可能的交换来改善这一点。在样例 2 中，整个公司有 $3$ 名员工喜欢语言 $0$，这也是 Anneke 喜欢的语言，所以选择 Anneke 作为团队负责人会形成一个大小为 $3$ 的团队，不需要进行交换。

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

在样例 3 中，我们选择员工 $4$ 作为团队负责人，然后可以让员工 $1$ 和 $8$ 以及 $2$ 和 $3$ 交换团队，从而得到总共 $4$ 名员工喜欢与 $4$ 相同的语言，即语言 $2$（纯色）。在样例 4 中，选择员工 $6$ 作为团队负责人，并交换员工 $4$ 和 $7$ 以及 $1$ 和 $5$ 可以获得最大分数。注意，我们不能在选择团队负责人之前交换员工 $6$ 和 $3$ 以获得分数 $4$，因为我们必须首先确定团队负责人。

---

**数据范围**

对于全部数据，$1\le N\le 10^5$，$1\le K\le N$。

- 子任务一（$12$ 分）：第 $i$ 名员工的上司是 $i - 1$。
- 子任务二（$19$ 分）：$K\le 2$。
- 子任务三（$27$ 分）：对于每种编程语言，最多有 $10$ 名员工首选它。
- 子任务四（$23$ 分）：$N\le 2000$。
- 子任务五（$19$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。


title: [EGOI2024] Circle Passing / 传球游戏

background:
Day 2 Problem A.

题面译自 [EGOI2024 circlepassing](https://wiki.egoi2024.nl/tasks/circlepassing/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

description:
这是 Anouk 高中的第一天；作为热身活动，她的体育老师让班级玩记忆名字的游戏。班上有 $2N$ 名学生。他们中的大多数人彼此不认识，但有 $M$ 对最好的朋友，他们一起做任何事情。每个学生最多有一个最好的朋友。

老师把所有学生安排成一个圆圈，连续给每个学生分配一个从 $0$ 到 $2N - 1$ 的编号。更具体地，对于每个 $0 \le i < 2N - 1$，学生 $i$ 和 $i + 1$ 站在一起。此外，学生 $0$ 和 $2N - 1$ 也站在一起。

由于老师希望每个人都能结识新同学，所以最好的朋友必须尽可能远离彼此，即相对而站。也就是说，形成第 $i$ 对好朋友的学生分别站在位置 $k_i$ 和 $k_i + N$，其中 $0 \le k_i < N$。

老师选择了两个学生 $x$ 和 $y$ 并将一个球交给学生 $x$。目标是将球传给学生 $y$，但每个学生只能将球传给另一个他们已经知道名字的学生。当然，最好的朋友彼此知道对方的名字。在老师解释规则期间，每个学生都认识了直接站在他们旁边的两个学生的名字。除此之外，没有人知道其他人的名字。

游戏玩了 $Q$ 次；每次老师选择两个学生。由于学生们没有注意，他们在游戏过程中不会学到任何新名字。在每场游戏中，从学生 $x$ 到学生 $y$ 需要的最少传球次数是多少？

inputFormat:
输入的第一行包含三个整数，$N, M$ 和 $Q$，其中 $2N$ 是 Anouk 班上的学生数，$M$ 是最好朋友的对数，$Q$ 是进行的游戏次数。

第二行包含 $M$ 个整数 $k_0 ,\cdots, k_{M-1}$，其中 $k_i$ 描述了第 $i$ 对好朋友。对于每个 $i$，最好朋友分别站在位置 $k$ 和 $k + N$。每个学生最多有一个最好的朋友。

接下来的 $Q$ 行每行包含两个整数，$x_i$ 和 $y_i$，即第 $i$ 场游戏中选择的两个学生。

outputFormat: 输出 $Q$ 行，第 $i$ 行包含一个整数，即第 $i$ 场游戏中所需的最少传球次数。

hint:
**样例解释**

以下两图描述了第一个样例和第四个样例中的排列情况。如果两个学生彼此认识，他们之间就有一条边连接。

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

在第一个样例的第一个游戏中，球被传给学生 $1$。学生 $1$ 将球传给他们的好朋友学生 $5$。球在学生 $5$ 传给学生 $4$ 后到达学生 $4$，总共需要两次传球。

---

**数据范围**

对于全部数据，$2\le N\le 5\times 10^8$，$1\le M\le 5\times 10^5$ 且 $M\le N$，$1\le Q\le 2\times 10^4$，$0\le k_0<k_1<\cdots<k_{M-1}<N$，$0\le x_i,y_i < 2N$ 且 $x_i\ne y_i$。

- 子任务一（$14$ 分）：$M=1$ 且 $x_i=k_0$。换句话说，仅有一对最好的朋友，且在每局游戏中，最开始有球的人有一个最好的朋友。
- 子任务二（$20$ 分）：$N,M,Q\le 1000$。
- 子任务三（$22$ 分）：$N\le 10^7$ 且 $M,Q\le 1000$。
- 子任务四（$17$ 分）：$x_i=0$。
- 子任务五（$27$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。


title: [EGOI2024] Bike Parking / 车位分配

background:
Day 2 Problem B.

题面译自 [EGOI2024 bikeparking](https://wiki.egoi2024.nl/tasks/bikeparking/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

description:
Sanne 最近想出了一个有利可图的商业点子：在埃因霍温火车站出租高级自行车停车位。为了最大化她的利润，她将自行车停车位分成了 $N$ 个不同的级别，编号从 $0$ 到 $N - 1$。级别 $0$ 是高级级别，位置非常靠近火车站台。编号越高的级别停车位越差。级别 $t$ 的停车位数量为 $x_t$。

用户通过一个应用程序来分配他们的停车位。每个用户都有一个订阅等级，并期望在相应的级别获得一个停车位。然而，服务条款并不保证用户在他们的相应级别获得一个停车位。

如果订阅等级为 $s$ 的用户被分配到级别 $t$ 的停车位，那么会发生以下三种情况之一：

1. 如果 $t < s$，用户会感到高兴，并会为应用点赞。
2. 如果 $t = s$，用户会感到满意，不会有任何反应。
3. 如果 $t > s$，用户会感到生气，并会给应用差评。

今天，Sanne 的应用有 $y_0 + y_1 + \cdots + y_{N-1}$ 名用户，其中 $y_s$ 是订阅等级为 $s$ 的用户数量。她需要你的帮助来将用户分配到停车位。每个用户应该得到一个停车位。不能将一个停车位分配给多个用户，但可以有一些停车位不分配给任何用户。此外，用户总数不超过可用停车位总数。

Sanne 希望最大化她的应用评分。设 $U$ 为点赞数，$D$ 为差评数。你的任务是通过最佳分配用户到停车位来最大化 $U - D$。

inputFormat:
第一行包含一个整数 $N$，表示级别或订阅等级的数量。

第二行包含 $N$ 个整数 $x_0,x_1,\cdots,x_{N-1}$，表示不同级别的停车位数量。

第三行包含 $N$ 个整数 $y_0,y_1,\cdots,y_{N-1}$，表示每个订阅等级的用户数量。

outputFormat: 输出一个整数，表示通过最佳分配用户到停车位所能得到的最大可能值 $U - D$。

hint:
**样例解释**

在第一个样例中，你可以将订阅级别为 $0$ 的用户分配到 $0$ 级停车位，将两个级别为 $1$ 的用户分配到 $0$ 级停车位（获得 2 次赞），并将剩余的级别为 $1$ 的用户分配到 $1$ 级停车位。这导致评分为 $2$。

在第二个样例中，你可以将级别 $1$ 的用户分配到 $0$ 级停车位，将级别 $2$ 的用户分配到 $1$ 级停车位，并将级别 $0$ 的用户分配到 $2$ 级停车位。这将导致 2 次赞和 1 次踩，评分为 $1$。

在第三个样例中，你可以将级别 $1$ 的用户分配到 $0$ 级停车位，将级别 $0$ 的用户分配到 $2$ 级停车位，并将级别 $4$ 的用户分配到 $3$ 级停车位。这将再次导致 2 次赞和 1 次踩，评分为 $1$。

第四个样例如下图所示。你可以将级别 $1$ 的用户分配到 $0, 0, 3, 3$ 级停车位，导致 2 次赞和 2 次踩。接下来，将级别 $2$ 的用户分配到 $1, 2, 3, 3$ 级停车位，导致 1 次赞和 2 次踩。这相当于 3 次赞和 4 次踩，评分为 $-1$。

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

在第五个样例中，你可以将每个人分配到匹配其自身订阅级别的停车位，因此评分为 $0$。

---

**数据范围**

对于全部数据，$1\le N\le 3\times 10^5$，$0\le x_i,y_i\le 10^9$，$y_0+y_1+\cdots+y_{N-1}\le x_0+x_1+\cdots+x_{N-1}\le 10^9$。

- 子任务一（$16$ 分）：$N=2$，$x_i\le 100$，$y_i\le 100$。
- 子任务二（$9$ 分）：对于任意 $(i,j)$，$x_i=x_j=y_i=y_j$。
- 子任务三（$19$ 分）：$x_i,y_i\le 1$。
- 子任务四（$24$ 分）：$N,x_i,y_i\le 100$。
- 子任务五（$32$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。


title: [EGOI2024] Light Bulbs / 灯泡安装

background:
Day 2 Problem C.

题面译自 [EGOI2024 lightbulbs](https://wiki.egoi2024.nl/tasks/lightbulbs/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

**本题是一道交互题。**

description:
在 1891 年在埃因霍温创立他的灯泡公司后不久，Frederik Philips 取得了一个伟大的发现：可以在水平方向或垂直方向上点亮无限射线的灯泡。凭借这一新发现，他希望革新现代家庭的室内设计。

他和他的儿子 Gerard 计划进行一个复杂的安装。他们在一个房间内的 $N \times N$ 网格中安装了 $N^2$ 个灯泡。他们希望尽可能少地打开灯泡来点亮整个房间，以节省电力。每个灯泡要么是垂直的，意味着它点亮其列中的所有格子，要么是水平的，意味着它点亮其行中的所有格子。

下图显示了一个垂直灯（左）和一个水平灯（右）的示例。

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

不幸的是，他们在安装灯泡时没有注意，不记得哪些灯泡是水平点亮的，哪些是垂直点亮的。相反，他们进行了些实验来弄清楚使用哪些灯泡可以点亮整个房间。Gerard 留在有灯泡的房间里，而 Frederik 在另一个房间操作开关。

在每次实验中，Frederik 会打开或关闭每个灯泡，而 Gerard 会报告点亮了多少个格子；由两个或更多独立灯泡点亮的格子只算作一次。实验期间打开多少灯泡并不重要，但他们时间紧迫，理想情况下希望尽可能少地进行实验。

帮助他们找到一种使用最少灯泡点亮整个房间的安排。他们最多可以进行 $2000$ 次实验。然而，如果他们使用更少的实验次数，你将获得更高的分数。

---

**交互方式**

本题是一道交互题。

- 你的程序应首先读取一个整数 $N$，即网格的高度和宽度。
- 然后，程序应与评测系统进行交互。进行实验时，你应首先打印一行问号 `?`。在接下来的 $N$ 行中，输出一个 $N \times N$ 的网格，指定哪些灯泡被点亮。具体来说，在每行中，输出一个长度为 $N$ 的字符串，由 $0$（关闭）和 $1$（打开）组成。然后，程序应读取一个整数 $l$（$0 \le l \le N^2$），表示通过指定的灯泡点亮的格子数量。
- 当你想要回答时，打印一行感叹号 `!`，后跟 $N$ 行，格式与上面相同。在你的回答被接受前，**灯泡必须点亮整个网格，且打开的灯泡数量必须最少**。

之后，你的程序应退出。

评测系统是非自适应的，这意味着灯泡网格在交互开始前已经确定。

每次进行实验后，请确保刷新标准输出；否则，程序可能会被判定为 TLE。在 Python 中，只要使用 `input()` 读取行，就会自动刷新。在 C++ 中，`cout << endl;` 除了打印换行符外还会刷新；如果使用 `printf`，请使用 `fflush(stdout)`。

inputFormat: 见【交互方式】部分。

outputFormat: 见【交互方式】部分。

hint:
**样例解释**

在样例交互中，程序首先读取网格大小 $N = 5$。下图展示了隐藏的网格（程序不知道）和众多可能答案之一，使用五盏灯点亮整个网格。标记的灯是打开的，较暗的方块是被照亮的。

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

程序进行了如下所示的两个实验。在第一个实验中，使用左上角的两个垂直灯照亮了总共 10 个方块。第二个实验照亮了总共 13 个方块。最后，程序写出了它的答案（如上图所示）并退出。

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

---

**数据范围**

对于全部数据，$3\le N\le 100$。你最多可以进行 $2000$ 次实验（输出最终答案不计入实验次数）。如果你超过了限制，程序会被判定为 WA。

- 子任务一（$11$ 分）：$N=3$。
- 子任务二（$11$ 分）：$N\le 10$。
- 子任务三（至多 $78$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。

---

**评分方式**

在子任务三中，你按照下面的公式**根据进行实验的次数得分**：

$$
\textrm{score}=
\begin{cases}
(2000-Q)\cdot 29/900&\text{if }200\le Q\le 2000\\
58+(200-Q)\cdot 4/23&\text{if }85\le Q\le 200\\
78&\text{if }Q\le 85\\
\end{cases}
$$

其中 $Q$ 是这个子任务的所有测试点中最多的实验次数。你的得分将被取整到最接近的整数。

下面是总分关于子任务三中 $Q$ 的函数图象。要想得到满分，你需要进行不超过 $85$ 次实验解决子任务三中的每个测试点。

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


title: [EGOI2024] Make Them Meet / 活动面基

background:
Day 2 Problem D.

题面译自 [EGOI2024 makethemmeet](https://wiki.egoi2024.nl/tasks/makethemmeet/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

**警告：滥用本题评测将会封号。**

description:
Mila 和 Laura 在网上已经是很长时间的朋友了；但她们从未在现实中见过面。现在，她们都参加了同一个现场活动，这意味着她们肯定会见面。然而，她们所住的酒店非常大且复杂。因此，经过几天后，她们仍未碰面。

酒店由 $N$ 个房间组成，编号从 $0$ 到 $N - 1$。每个房间都有一个可以更换颜色的灯。你找到了酒店的电力服务房，允许你改变灯的颜色。你的目标是使用这些灯引导 Mila 和 Laura 最终见面。

酒店可以表示为一个有 $N$ 个顶点（房间）和 $M$ 条边（连接房间的走廊）的图。Mila 和 Laura 最初在两个不同的房间开始，但你不知道是哪些房间。你可以进行若干次移动。每次移动包括打印一个包含 $N$ 个整数的列表 $c_0,c_1,\cdots,c_{N-1}$，表示房间 $i$ 的灯变为颜色 $c_i$，其中 $i = 0, 1,\cdots, N - 1$。然后，Mila 和 Laura 会查看她们当前所在房间的灯的颜色，并走向相邻房间中灯颜色相同的房间。如果没有这样的相邻房间，她们将留在原地。如果有多个这样的相邻房间，她们将任意选择一个。

如果在你的移动过程中，Mila 和 Laura 在同一个房间或同时使用同一个走廊，那么你就成功地让她们见面了。你最多可以进行 $2\times 10^4$ 次移动，但如果你使用更少的移动次数，你的得分会更高。

注意，你不知道 Mila 和 Laura 最初在哪个房间，也不知道如果她们有多个相同颜色的房间可以选择时会如何走。**你的解决方案必须在无论她们的起始房间是哪些或如何走动的情况下都是正确的。**

inputFormat:
第一行包含两个整数 $N$ 和 $M$，分别表示酒店的房间数和走廊数。

接下来的 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示房间 $u_i$ 和 $v_i$ 由一个走廊连接。

outputFormat:
输出一行一个整数 $K$，表示移动次数。

在接下来的 $K$ 行中，每行输出 $N$ 个整数 $c_0,c_1,\cdots,c_{N-1}$，其中对所有的 $i$ 都有 $0 \le c_i \le N$。这 $K$ 行代表按时间顺序的你的移动。

hint:
**样例解释**

样例情况是一个长度为 $3$ 的路径，因此它可能属于测试组 $3, 4$ 或 $5$。如果房间的灯根据样例输出进行着色，那么 Mila 和 Laura 总会见面。

例如，假设 Mila 开始在房间 $0$，Laura 开始在房间 $1$：

- 第一步：Mila 必须走到房间 $1$。如果 Laura 走到房间 $0$，那么她们将在 $0$ 和 $1$ 之间的走廊上相遇。假设 Laura 走到房间 $2$。
- 第二步：Mila 走回房间 $0$，Laura 留在房间 $2$。
- 第三步：Mila 再次走到房间 $1$，Laura 留在房间 $2$。
- 第四步：Mila 走到房间 $2$，Laura 走到房间 $1$。于是她们将在房间 $1$ 和 $2$ 之间的走廊上相遇。
- 第五步：Mila 和 Laura 交换位置并再次相遇（但这并不重要，因为她们已经见面了）。

下图显示了样例的前四步。

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

注意，这仅仅是朋友从房间 $0$ 和 $1$ 开始的情况。可以验证，无论她们从哪里开始以及如何行走，相同的移动顺序都能确保她们见面。

---

**数据范围**

对于全部数据，$2\le N\le 100$，$N-1\le M\le \frac{N(N-1)}{2}$，$0\le u_i,v_i\le N-1$ 且 $u_i\ne v_i$。保证你可以从每个房间到达所有房间，且没有走廊连接一个房间和它自己，也没有多个走廊连接相同的两个房间。你最多可以使用 $2\times 10^4$ 步（即 $K\le 2\times 10^4$）。

- 子任务一（至多 $10$ 分）：$M=N-1$ 且走廊是 $(0,1),(0,2),(0,3),\cdots,(0,N-1)$。也就是说，图为菊花图。
- 子任务二（至多 $13$ 分）：$M=\frac{N(N-1)}{2}$，即任意两个房间之间都有一条走廊。也就是说，图为完全图。
- 子任务三（至多 $11$ 分）：$M=N-1$ 且走廊是 $(0,1),(1,2),(2,3),\cdots,(N-2,N-1)$。也就是说，图为一条链。
- 子任务四（至多 $36$ 分）：$M=N-1$。也就是说，图为一棵树。
- 子任务五（至多 $30$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。

---

**评分方式**

对于每个你的程序正确解决的子任务，你会根据以下公式获得分数：

$$
\textrm{score}=\left\lfloor S_g\cdot\min\left(1,\frac{2000}{K_g+1900}+\frac{1}{5}\right)\right\rfloor
$$

其中 $S_g$ 是这个子任务的满分，$K_g$ 是你的程序在这个子任务的所有测试点中使用的最大步数。这意味着要想得到满分，你需要用不超过 $600$ 步解决每个测试点。下面是得分关于 $K_g$ 的函数图象。

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


title: [语言月赛 202409] 数字

type: B

description:
你需要求出一个 $n$ 位数 $x$，满足以下两个条件：

- 1. $x$ 的**各位数字之和**除以 $p$ 的**余数**尽可能小。
- 2. 在**已经满足 1** 的情况下，$x$ 的值尽可能小。

各位数字之和：一个数的每个位置上的数字加起来的总和。例如，$123$ 的各位数字之和为 $1+2+3=6$

inputFormat: 输入共一行，两个整数 $n,p$。

outputFormat: 输出一个整数，表示上述问题的答案。


title: [语言月赛 202408] 游戏与共同语言

background: > 风与清都喜欢玩某款游戏。

description:
在该游戏的职业联赛中，战队 A 和战队 B 的排名先后关系取决于胜局数、净胜数、平局记录数。具体排名规则如下：

- 胜局数**高**者排名靠前
- 若胜局数相同，净胜数**高**者排名靠前
- 若净胜数仍相同，平局记录**低**者排名靠前
- 不存在平局记录仍相同的情况

现在，给出两支战队相关数据，请给出排名更靠前的战队。

inputFormat:
输入的第一行为三个整数 $w_a,c_a,t_a$，依次表示战队 A 的胜局数、净胜数和平局记录数。

输入的第二行为三个整数 $w_b,c_b,t_b$，依次表示战队 B 的胜局数、净胜数和平局记录数。

outputFormat: 输出一行一个字符 `A` 或 `B`，表示排名靠前的战队。


title: [语言月赛 202408] 于抑郁中支持

background: > 感谢清曾在风最脆弱的时候给过支持。

description:
那是一段混沌的时期，风的记忆裂变为 $n$ 块碎片，第 $i$ 块的特征值为 $a_i$。

定义整数 $x$ 的后 $p$ 位的值为 $x \bmod 10^p$。特征值后 $t$ 位相同的记忆碎片，从属于同一事件。

请问，$n$ 块碎片共从属于多少不同的事件。

inputFormat:
第一行为两个整数 $n,t$。

第二行为 $n$ 个整数，第 $i$ 个为 $a_i$。

outputFormat: 输出一行一个整数，表示事件个数。


title: [语言月赛 202408] 蓝色的网易云

background:
> 你也在听吗
> 落单的孩子啊
> 别害怕 别害怕
> 黑夜不会太长
> 悬崖上的花
> 让我为你摘下
> 数一瓣 落一瓣
> 就少一朵忧伤

description:
风的歌单中共有 $n$ 首歌，这些歌曲可以根据题材分为 $m$  类，第 $i$ 首歌的题材为 $c_i$。风并不偏好任何一种题材，因此歌单中各题材的歌曲数量相同。

现在，请你给出一个歌曲播放顺序，使得相邻播放的歌曲题材不相同。

inputFormat:
第一行为两个整数 $n,m$。

第二行为 $n$ 个整数，第 $i$ 个为 $c_i$。

outputFormat:
输出 $n$ 行，每行一个整数，从上至下表示歌曲播放顺序。

**符合题意的答案可能有多种，你只需要输出其中任意一种即可。**

hint:
对于 $30\%$ 的测试数据，$n=m$；
对于 $100\%$ 的测试数据，$1 \le n \le 10^3$，$2 \le m \le 10^3$，$n$ 是 $m$ 的倍数，$1 \le c_i \le m$。


title: 『DABOI Round 1』Develop a Tree

background: 小 Z 看不惯树，所以他总想在树上随机添加一些边。他认为二分图是很和谐的，所以他想知道将一棵树变为二分图的方案数。你能否回答他的询问？

description:
对于一颗无向有根树，定义 $f(i,k)$ 表示在以 $i$ 为根的子树中，在其内部连 $k$ 条边，使得这颗子树变为一个二分图的方案数。请注意，加边时允许与原树边重边，但任意两条新加的边都不能重合。

给定一棵 $n$ 个点的无向有根树，根节点为 $1$ 号点。对于每个 $i\in [1,n]$，求 $f(i,k)$ 对 $p_i$ 取模的值。

inputFormat:
输入共 $n+1$ 行。

第 $1$ 行 $2$ 个整数，分别表示树的点数 $n$ 和参数 $k$。

接下来，第 $2$ 至 $n$ 行，每行 $2$ 个正整数，分别表示一条边连接的两个点的编号 $u_i$ 与 $v_i$。

第 $n+1$ 行 $n$ 个整数，分别表示每次询问时的模数 $p_i$。

outputFormat: 输出共 $1$ 行 $n$ 个整数，分别表示每次询问的答案。


title: 「LAOI-6」[太阳]] 请使用最新版手机 QQ 体验新功能

background:
[English statement](https://www.luogu.com.cn/problem/U481351). You must submit your code at the Chinese version of the statement.

---

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

description:
你的 QQ 收到了一条新消息！但是你很生气，因为你看不到别人在手机 QQ 上发送的超级表情。

消息形如一个字符串 $S$，包含且仅包含一个超级表情。具体地，我们将 $S$ 的拼音采用驼峰命名法，可以化为如下形式的消息：

```plain
[AaaBbbCcc......]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng
```

也就是说，将 $\texttt [w\texttt{]]请使用最新版手机QQ体验新功能}$ 中的每个汉字替换为其拼音，其中 $w$ 为 *实际中文名称*，保证其包含 $\geq 1$ 个音节。

为了在电脑上也能发出这个表情，你需要键入一个正斜杠（$\texttt /$）加它的 **拼音缩写**。例如 `[TaiYang]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng` 的拼音缩写为 $\texttt{/ty}$，`[YueLiang]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng` 的拼音缩写为 $\texttt{/yl}$。更具体地，表情 $w$ 的 **拼音缩写** 即为 $w$ 的 *实际中文名称* 中，每个拼音音节的首字母转为小写后拼接的结果。

最终请你输出在电脑端表示发送这个表情的字符串。**请注意：这个字符串可能在 QQ 中实际上不能表示这个表情，例如 `NiZhenBangBang`（一个超级 QQ 表情） 不能在 QQ 中用 $\texttt{/nzbb}$ 来打出，但是在本题中，我们认为其是合法的**。

inputFormat: 输入仅一行：一个字符串 $S$。

outputFormat: 输出一行一个字符串，表示答案。

hint:
**本题采用捆绑测试。**

对于 $100 \%$ 的数据，保证给出的字符串 $S$ 满足题目中所写的 `[AaaBbbCcc......]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng` 的格式，且保证 $\lvert S\rvert \leq 100$；给出的 $S$ 描述一个真实存在的 QQ 超级表情。


title: [HBCPC2024] Long Live

description:
In Minecraft, there are three dimensions in the simple world, one of which is known as “The End”. In this dimension, the Ender Dragon is usually symbolized as the final boss of Minecraft.

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

Now we, you, and Steve want to beat the dragon. However, we find that the dragon is telling a puzzle. We must solve it before fighting against the dragon. Please stand by our side to fight against the dragon. The puzzle goes as follows.

Given two positive integers $x$ and $y$, please find two integers $a$ and $b$, such that

$$\sqrt{\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}}=a\sqrt{b}$$

and to maximize $a \cdot b$.

Here, $\gcd(a, b)$ represents the greatest common divisor of $a, b$, while $\operatorname{lcm}(a, b)$ represents the least common multiple of $a, b$.

inputFormat:
The first line contains an integer $T (1 \leq T \leq 10^4)$ indicating the number of test cases.

Of the following $T$ lines, each contains two integers $x$ and $y (1 \leq x, y \leq 10^9)$, representing the puzzle.

outputFormat: Output $T$ lines. Each contains two integers $a$ and $b$, indicating the answer to each test case.

translation:
### 题目描述
在 Minecraft 中，简单世界中有三个维度，其中一个被称为“The End”。在这个维度中，末影龙通常被象征为 Minecraft 的最终 Boss。

现在，我们、你和Steve想要打败这条龙。然而，我们发现这条龙出了一道谜题来困扰我们。在与龙战斗之前，我们必须先解开这个谜题。请站在我们这边，与龙一同战斗。谜题如下：

给定两个正整数 $x$ 和 $y$，请找到两个整数 $a$ 和 $b$，使得

$$\sqrt{\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}}=a\sqrt{b}$$

并使 $a \cdot b$ 最大化。

其中，$\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数，而 $\operatorname{lcm}(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数。

### 输入格式

第一行包含一个整数 $T \ (1 \leq T \leq 10^4)$，表示测试用例的数量。

接下来的 $T$ 行中，每行包含两个整数 $x$ 和 $y \ (1 \leq x, y \leq 10^9)$，表示这个谜题。

### 输出格式

输出 $T$ 行，每行包含两个整数 $a$ 和 $b$，表示每个测试用例的答案。

### 说明/提示
亲爱的所有参赛者：

这个问题可能是故事的开篇，但绝不是故事的结尾。请一直相信自己，愿我的歌声伴随你们，“致我们曾一起翻越的高山，与你并肩战斗巨龙的时光，我度过了生命中最美好的时光”。

翻译者：[Immunoglobules](https://www.luogu.com.cn/user/1066251)

hint:
Dear all participants:

This problem may be the very first page, but not where the story line ends. Please believe in yourself all the time, wishing you with my singing, “Long live all the mountains we moved, I had the time of my life fighting dragons with you”.


title: [HBCPC2024] Nana Likes Polygons

description:
Nana’s electronic pet, MACARON, enjoys moving around in the room. Nana wants to create a boundedarea where MACARON can roam within.

The positions in the room can be represented using a two-dimensional coordinate system, and Nana provides a set of vertices on it. Nana likes polygons and now wants to select a subset of vertices that can form a convex polygon as its endpoints. However, Nana also wants to ensure that the selected area is not too big.

Thus, she is going to determine the minimum possible area of the convex polygon ending on a subset of given vertices. If such a convex polygon doesn’t exist, please output `-1` (without quotes).

inputFormat:
The first line contains a single integer $T (1 \leq T \leq 10)$ — the number of test cases.

For each test case, the first line contains a single integer $n (1 \leq n \leq 100)$ — the number of given vertices.

The following $n$ lines each contain two integers, and the $i$-th line contains $x_i, y_i (-1000 \leq x_i, y_i \leq 1000)$ — the coordinate of the $i$-th vertex.

outputFormat:
For each test case, if no such convex polygon, please output `-1` without quotes; otherwise output a single real number denoting the minimum possible area of the convex polygon ending on these given vertices.

Let $a$ and $b$ denote the answer and your output respectively. Your output will be accepted if the absolute or relative error of $b$ does not exceed $10^{-6}$. Formally, your output is accepted if and only if $\dfrac{|a-b|}{\max(a,b)} \leq 10^{-6}$

hint:
For the first test case, choose $(2, 2), (−3, 0)$, and $(0, 2)$ as endpoints of a convex polygon with area $2$. It can be proved that this is the minimized area in this case.

For the second test case, no convex polygon can be formed by these three vertices.


title: [HBCPC2024] Lili Likes Polygons

description:
Lili and Nana are weeding in the backyard of Lili’s house. They are repeatedly selecting rectangular areas and removing all the grass within them.

The backyard can be visualized as a 2D grid, each square cell representing one unit area. They have performed a total of $n$ operations. During the $i$-th operation, they choose the left, bottom, right, and top sides of a rectangle, denoted as $l_i, b_i, r_i, t_i$, and clear all the cells within this rectangle using a lawnmower. **Note that these rectangles may overlap with each other.**

Let $[l_i, r_i]\times[b_i, t_i]$ denote a rectangle.

Here is an example illustrated in the following figure.  They have selected $2$ rectangles, with the first rectangle being $[1, 5]\times[2, 3]$ and the second rectangle being $[2, 3]\times[1, 4]$.

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

After the $n$ weeding operations, the union of the bare area may not be connected but all the sides are horizontal or vertical. Thus, the union becomes orthogonal polygon(s), some of which contain polygon holes.  Moreover, there can be bare cells inner some holes. Please see the example inputs for more details and illustrations.

Now, they want to restore the land by planting some plants on the bare cells. Lili likes polygons, especially rectangles. Therefore, they want to select several rectangles, and these rectangles do not overlap with each other and exactly cover all the bare cells. Then, they plant different plants in different rectangles they selected.

For example, here is a feasible selection of rectangles for the aforementioned case: choose $[1, 1]\times [2, 3]$, $[2, 3]\times[1, 4]$ and $[4, 5]\times [2, 3]$.

After playing for a while, these two little girls have become tired, so they want to know the minimum number of non-overlapping rectangles that can cover all the bare cells.

inputFormat:
The first line contains a single integer $n$ ($1\leq n\leq 300$) --- the number of rectangles when they weed.

The following $n$ lines each contain $4$ integers, and the $i$-th line contains $l_i, b_i, r_i, t_i$ ($1\leq l_i, b_i, r_i, t_i\leq 10^9, l_i\leq r_i, b_i\leq t_i$) --- the left, bottom, right, and top sides of the $i$-th rectangle.

It is guaranteed the sum of the endpoints of the bare area (polygon(s) with polygonal holes) does not exceed $2000$.

outputFormat: Output a single integer on a single line denoting the minimum number of rectangles they need to select to plant plants on all the bare cells.

translation:
### 题目描述
莉莉和娜娜正在莉莉家后院除草。她们反复选择矩形区域，并移除其中的所有草坪。

后院可以被视为一个二维网格，每个方格表示一个单位面积。她们共进行了 $n$ 次操作。在第 $i$ 次操作中，她们选择了一个矩形的左、下、右、上的边界，分别表示为 $l_i, b_i, r_i, t_i$，并使用割草机清除该矩形内的所有方格。**注意，这些矩形可能会相互重叠。**

用 $[l_i, r_i] \times [b_i, t_i]$ 表示一个矩形。

以下是一个例子，如图所示。她们选择了 $2$ 个矩形，第一个矩形是 $[1, 5] \times [2, 3]$，第二个矩形是 $[2, 3] \times [1, 4]$。

经过 $n$ 次除草操作后，裸露区域的联合可能不连通，但所有边都是水平或垂直的。因此，联合区域变成了一个或多个直角多边形，其中一些可能包含多边形孔洞。此外，在某些孔洞内部可能会有裸露的方格。更多细节和图示请参见示例输入。

现在，她们想通过在裸露的方格上种植植物来恢复土地。莉莉喜欢多边形，特别是矩形。因此，她们想选择若干个矩形，这些矩形之间不重叠，并且能够完全覆盖所有的裸露方格。然后，她们将在选择的不同矩形中种植不同的植物。

例如，下面是上述情况的一个可行的矩形选择：选择 $[1, 1] \times [2, 3]$、$[2, 3] \times [1, 4]$ 和 $[4, 5] \times [2, 3]$。

玩了一会儿，这两个小女孩已经累了，所以她们想知道覆盖所有裸露方格的最小不重叠矩形数量。

### 输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 300$) —— 表示除草时使用的矩形数量。

接下来的 $n$ 行每行包含 $4$ 个整数，第 $i$ 行包含 $l_i, b_i, r_i, t_i$ ($1 \leq l_i, b_i, r_i, t_i \leq 10^9, l_i \leq r_i, b_i \leq t_i$) —— 表示第 $i$ 个矩形的左、下、右、上边界。

保证裸露区域的端点总数（多边形及其孔洞）不超过 $2000$。

### 输出格式

在一行上输出一个整数，表示覆盖所有裸露方格所需选择的最小矩形数量。

### 说明/提示

对于第一个例子，最优选择是 $[1, 1] \times [1, 3]$、$[2, 1] \times [2, 1]$、$[2, 3] \times [2, 3]$ 和 $[3, 1] \times [3, 3]$。

对于第二个例子，最优选择是 $[1, 1] \times [100, 100]$ 和 $[1, 501] \times [100, 600]$。

对于第三个例子，最优选择是 $[1, 1] \times [4, 1]$、$[1, 4] \times [5, 4]$、$[1, 2] \times [1, 3]$、$[4, 2] \times [4, 3]$ 和 $[4, 5] \times [4, 5]$。

对于第四个例子，裸露区域如下图所示。

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

翻译者：[Immunoglobules](https://www.luogu.com.cn/user/1066251)

hint:
For the first example, an optimal selection is $[1, 1]\times [1, 3]$, $[2, 1]\times [2, 1]$,  $[2, 3]\times [2, 3]$ and $[3, 1]\times [3, 3]$.

For the second example, an optimal selection is $[1, 1]\times [100, 100]$ and $[1, 501]\times [100, 600]$.

For the third example, an optimal selection is $[1, 1]\times [4, 1]$, $[1, 4]\times [5, 4]$,  $[1, 2]\times [1, 3]$, $[4, 2]\times [4, 3]$ and $[4, 5]\times [4, 5]$.

For the fourth example, the bare area is illustrated in the following figure.

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


title: [HBCPC2024] MACARON Likes Happy Endings

description:
MACARON is going to read a book, which contains $n$ chapters, and the $i$-th chapter has $a_i$ characters.
MACARON wants to read this book in the next $k$ days.
On each day, he either reads several chapters from the first unread chapter, or just takes a rest (does not read the book), but he should finish his reading in $k$ days.

MACARON enjoys his reading time and likes happy endings, so he does not want to be too sad during these days.
He has an unlucky number $d$, because he thinks number $d$ will lead to a bad ending.
We use a sadness value to quantify his mood on each day.
On the $i$-th day, if he reads, suppose that he reads chapters from $L_i$ to $R_i$.
The sadness value of this day is the number of intervals $[l, r]$ such that $L_i\leq l\leq r\leq R_i$ and $\bigoplus_{i=l}^r a_i=d$.
The $\oplus$ denotes the bitwise XOR operator.
If he doesn't read, let the sadness value be $0$.

MACARON wants to arrange his reading schedule to minimize the sum of sadness value in $k$ days.
Can you help him find the minimum value?

inputFormat:
The first line contains three integers $n, k$ and $d$ ($1\leq n\leq 10^5, 1\leq k\leq \min(n, 20), 0\leq d\leq 10^6$) --- the number of chapters, the days for reading, and the unlucky number.

The second line contains $n$ integers $a_i$ ($0\leq a_i\leq 10^6$) --- the number of characters in each chapter.

outputFormat: Output a single integer denoting the minimized sum of the sadness value.

hint:
Here is an optimal schedule for reading:

- on the first day, just take a rest, and the sadness value is 0;
- on the second day, read from chapter 1 to chapter 3, and the sadness value is 0;
- on the third day, read from chapter 4 to chapter 7, and the sadness value is 2;
- on the fourth day, read from chapter 8 to chapter 10, and the sadness value is 1.


title: [HBCPC2024] Spicy or Grilled?

description:
Since a regular programming contest lasts for five hours, it's a big problem to prepare contestants' food during the contest.

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

In the 20XX International Collegiate Programming Contest in Hubei Province, China, there were $n$ contestants participating in the contest. The host wanted to prepare a Spicy Chicken Burger Set for every contestant, which was $a$ dollars per set at that time. But since there were some people who could not bear the spiciness like Walk Alone, a Grilled Chicken Burger Set was prepared for these people, which was $b$ dollars per set. Before the contest, the host had collected the number $x$ of people who wanted to eat a Grilled Chicken Burger Set.

But Walk Alone was too stupid and lazy to calculate how much the host would spend. Please help him to calculate.

inputFormat:
In the first line,there is an integer $T$ ($1 \leq T \leq 10^4$) denoting the number of test cases.

For each test case, there are four integers $n$, $x$, $a$ and $b$ ($1 \leq n, a, b \leq 10^4, 0 \le x \le n$) in each line, representing the number of contestants in total, the number of contestants who want Grilled Chicken Burger Set, the price of Spicy Chicken Burger Set and Grilled Chicken Burger Set per set.

outputFormat: For each test case, output a single integer denoting the total money the host would spend.

hint: In the first test case, there were $400$ people chosen the Spicy Chicken Burger Set and $200$ people chosen the Grilled one. So the total money is $400 \times 27 + 200 \times 26 = 16\ 000$ dollars.


title: [HBCPC2024] Enchanted

description:
In Minecraft, one way to become stronger is to have the armors and weapons enchanted. Enchanted books play an important role.

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

The most important attribute of an enchanted book is its level. The higher the level is, the better the book is. We could merge two books with the same level  $l$ into one new book(the older two will disappear). The level of the new book is $l+1$ and the merger costs $2^{l+1}$.

Now, Steve has $n$ enchanted books numbered from $1$ to $n$. Initially, the $i$-th book's level is $a_i$. Steve asks you to help him with the following four operations.

1. Given two integers $l,r(1 \le l \le r \le n)$, calculate the maximum level Steve can reach by merging books numbered from $l$ to $r$.
2.  Given three integers $l,r(1 \le l \le r \le n)$ and $k$, then follow the steps:
Step $1$: Steve merges all the books numbered from $l$ to $r$ until there does not exist two books with the same level.
Step $2$: Steve adds one new book with level $k$ to the books he gets in Step $1$.
Step $3$: Steve needs to merge books he gets in Step $2$ and he wants to maximize the times he merges the books.
Please calculate and output the total cost modulo $10^9+7$ in Step $3$.
$\textbf{Note that, after calculating, the sequence is restored. That is, this operation does NOT actually change the sequence.}$

3. Given two integers $pos,k$, Steve changes the level of the book numbered $pos$ to $k$.

4. Given one integer $t$, Steve restores the sequence to the state after the $t$-th operation. If $t=0$, then Steve restores the sequence to the beginning state.

inputFormat:
The first and the only line contains 5 integers $n,m,A,p,q$.($1 \leq n \leq 10^6$, $1 \leq m \leq 10^6$, $1 \leq A \leq 19\,260\,817$, $1 \leq p \leq 4$, $1 \leq q \leq 30$)

Please pay attention! To avoid large input file, the true input is constructed through the following strategy:

$\textbf{Function rnd():}\ \ \ \\
A \leftarrow (7A+13) \bmod 19\,260\,817\ \ \ \\ \textbf{return } A$

Firstly, $n$ integers $a_1,a_2,\cdots,a_n$ are generated in turn, $a_i \leftarrow rnd() \bmod q + 1$.

Then, the parameters of all operations are generated.

For each operation, the number of operation(representing by $opt$) is firstly generated, $opt \leftarrow rnd() \bmod p + 1$.

According to the number of operation, the different method is applied to generate parameters for different operation.

- For operation 1: we need to get $l$ and $r$ by using:
  - $L \leftarrow rnd() \bmod n + 1$
  - $R \leftarrow rnd() \bmod n + 1$
  - $l \leftarrow \min(L,R)$
  - $r \leftarrow \max(L,R)$

- For operation 2: we need to get $l,r$ and $k$ by using:
  - $L \leftarrow rnd() \bmod n + 1$
  - $R \leftarrow rnd() \bmod n + 1$
  - $l \leftarrow \min(L,R)$
  - $r \leftarrow \max(L,R)$
  - $k \leftarrow rnd() \bmod q + 1$

- For operation 3: we need to get $pos$ and $k$ by using:
  - $pos \leftarrow rnd() \bmod n + 1$
  - $k \leftarrow rnd() \bmod q + 1$

- For operation 4: we need to get $t$ by using:

  - $t \leftarrow rnd() \bmod i$

Here, $i$ represents the $i$-th operation.

outputFormat: For each operation 1 and 2, you need to output one single line with an integer, representing the answer to operation 1 and 2 modulo $10^9 + 7$.

hint:
Function `max` means the maximum one between the parameters. Function `min` means the minimum one between the parameters.

In example 1, the initial books are $[1,2,3,1,2,3]$. The three operations' ranges are $[4,4]$, $[1,3]$ and $[4,5]$.


title: 移言丁真：Unavoided linyue

background:
**注：你不需要阅读此题题目背景。**

"$\textsf{linyue}$" 是我起过的唯一一个人名，所以 $\textsf{linyue}$ 成了唯一一个由我想象出来的角色。她是我脑海中所有故事的主角，对我而言非常地重要，以至于不知道为什么，每次我看到她的名字被写出来或是被读出来都会感到无所适从，所以我总是会想办法避免这样，比如说这个题的题面里我就用的是拼音作代替。

“跑团”这种游戏我最初了解的时候简直是“绝望地想要跟不管是谁玩随便什么”。可是疫情却让我的好多和同学玩的计划纷纷泡汤，所以我甚至走投无路到把它也纳入了计划的考虑范畴，不过由于它实在是太复杂了，没过多久我就把它抛诸脑后了（

“黑影杀”是一款在泞之翼官方交流群里兴起的游戏，玩家将会探索《泞之翼》原作的旅馆，躲避黑影以求逃出生天——对我而言没有比这更完美的事了！它完全实现了我上一段里的愿望，只要一有空，我便可以在群里“开鲨”！我给这个游戏准备了便于主持的程序，写了许多特殊规则，甚至还以它为背景出了题——尽管这题投到的比赛咕了（

《怪商一克拉》是一部我很喜欢的漫画。它的特点就是主角好像在每段故事里都只会最小程度地完成任务，然后哪怕这个故事还有好多未解之谜都只会跳到下一段故事。尽管这看起来像是没写好，但我相信这种效果作者是刻意为之。所以我期待着在未来看到这些故事的伏笔被精妙地解决，带来一个震撼的结局。可是有一天，我没有在漫画派对上看到这部漫画。这意味着以上就都不会发生了……我当时心态崩了好长时间，甚至都到泞之翼群里发癫了，不过事实上作者只是请了一个月假，接下来这漫画还会照常更新（

前两天，我终于又找到机会和同学出去玩了！这一次我们打算上一个主营镜土 TRPG 的店里试试跑团。要知道，这对我而言还是很有吸引力的，因为之前不管是玩什么，都是"我"在玩，跟 $\textsf{linyue}$ 没有什么关系。但要是玩跑团做角色卡的话，是不是就能填补这个遗憾了呢？所以这次我是有备而来！我提前十分费力地给 $\textsf{linyue}$ 画了一张简单的画，然后输入名字的时候，我决定不再回避——用她那两个汉字的真名，而非六个字母的替代。

然而，尽管我这一天听到和看到她名字的次数前所未有，但最后却并没什么很好的效果。我在游戏里确实是主打一个不入戏，对话内容有种全人类取平均的美，没推理出什么剧情的关键，也没想到什么新奇的点子。相信把我换成 Kimi AI 游戏绝对会更有趣……

——不过当然啦，这倒也在我意料之中，因为我知道我本来就非常非常不擅长这种角色扮演……看来对我而言，创造 $\textsf{linyue}$ 的故事会比别人更加困难。

所以我不会太受这个问题的困扰，一是因为习惯了，二是因为——我们出题组的比赛没过审。

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

“移言丁真”是这场比赛的原定 E 题之一，可是它被鉴定为了典……显然这最主要是我的锅。所以我现在的当务之急是要想一个新的 idea……

description:
定义一个括号串的权值为其中可配对的括号组数。也就是你重复地在里面删除掉某个为 ```()``` 的子串，最多可以删除的次数。

你会遇到 $m$ 个括号串，第 $i$ 个的长度是 $l_i$。你可以将它们按照任意顺序连接起来，然后连成一个长的括号串，而你的目标就是让最终的串的权值最小。

如果这 $m$ 个串是等概率随机生成的，而你的操作是最优的，请你求出最终权值的期望。也就是说你要对于初始括号串的所有可能性求出最小权值的和再除以 $2^n$，$n$ 为这些字符串的总长。对 $10^9+7$ 取模。

inputFormat:
第一行一个整数 $m$。

第二行 $m$ 个整数，表示 $l_1$ 到 $l_m$。

outputFormat: 一行一个整数表示答案，对 $10^9+7$ 取模。


title: 【烂题杯 Round 1】糖果色的梦

background: 感谢 @wukaichen888 指出本题数据过水，已将 hack 数据加入到每组 subtask 最后一个点。

description:
小 A 做了一个糖果色的梦，于是他打算买一些糖果送给他的 $n$ 个小朋友。

小 A 可以零售地购买糖果，也可以批发地购买糖果，他还可以批发地回收糖果。

- 零售地购买糖果：每次小 A 可以给一个小朋友购买一个糖果，这将会花费 $1$ 元；

- 批发地购买糖果：每次小 A 可以给连续且不少于 $k$ 个小朋友分别购买一个糖果，设小朋友的个数为 $l$，这将会花费 $l-B$ 元；

- 批发地回收糖果：每次小 A 可以给连续且不少于 $k$ 个小朋友分别收回一个糖果，这将会获得 $C$ 元；

第 $i$ 个小朋友都希望自己得到不少于 $a_i$ 个糖果。求小 A 满足所有小朋友的希望的最小代价。

inputFormat:
第一行输入两个正整数 $n$、$k$，表示小朋友数量、批发最少需要的小朋友数量。

接下来输入两个整数 $B$、$C$。

接下来一行 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，表示每个小朋友希望的糖果个数。

outputFormat: 输出一行一个整数，表示最小代价。

hint:
**样例 1 解释：**

我们给 $[1,2]$ 小朋友批发分别购买 $1$ 个糖果，代价为 $1$；给 $[3,4]$ 小朋友批发分别购买 $3$ 个糖果，代价为 $3$；给 $2$ 小朋友单独购买糖果，代价为 $1$；给 $4$ 小朋友单独购买糖果，代价为 $1$。总共代价为 $6$。

对于 $20\%$ 数据，满足 $1\le k\le n\le 10$。

对于 $40\%$ 数据，满足内存限制至少为 512 MB。

对于 $100\%$ 数据，满足 $1\le k\le n\le 1000$，$0\le B\le k$，$0\le C\le k-B$，$0\le a_i\le 10^9$。满足内存限制至少为 10 MB。


title: 【烂题杯 Round 1】可持久化糖果树

background:
感谢 @zhouhuanyi
 提出本题数据过水。

**本题数据生成器经过修改，部分题解里的代码将无法通过，并非题解出现错误！**

如果复制题解可能只会拿到 10 分。很好毙的。

description:
小 A 有一棵糖果树，树上有 $n$ 个节点，编号为 $1,2,\cdots,n$。每个节点里有 $m$ 位小朋友，编号为 $1,2,\cdots,m$。每个小朋友可以进行 $k$ 次祈愿，编号为 $1,2,\cdots,k$。节点 $i$ 中的第 $j$ 位小朋友的第 $x$ 次祈愿可以获得 $a_{i,j,x}$ 个糖果。我们称未被修改的糖果树为第 $0$ 个版本树。

一个小朋友被称为开心的，当且仅当她经过 $k$ 轮祈愿后可以获得的糖果数量可以被 $3$ 整除，这样就可以把糖果平均地分给她和她的父母。也就是说，第 $i$ 个节点的第 $j$ 个小朋友是开心的当且仅当 $\sum_{x=1}^k a_{i,j,x}\bmod 3=0$。

一个节点被称为是快乐的，当且仅当上面的 $m$ 位小朋友都是开心的。

小 A 可以施加魔法：他将会有 $q$ 次修改，下标从 $1$ 开始的第 $i$ 次修改可以描述为 $(x,y,z)$，表示将第 $x$ 个版本树上所有节点中的所有小朋友的第 $y$ 次祈愿获得的糖果数量乘上 $z$，得到第 $i$ 个版本树。要求你求出每个版本树中有多少个点是快乐的。

inputFormat:
由于输入文件过大无法上传，接下来我们将会以一种诡异的方式读入数据。

第一行有 $4$ 个整数 $n$、$m$、$k$、$X$，分别表示节点个数、每个节点上的小朋友个数、每个小朋友的祈愿次数、随机种子。

那么 $a_{i,j,x}=(X+X\times i+(X\oplus (j\times x+i\times i))\bmod 10^9$。

对于 C++，代码实现如下：

```cpp
a[i][j][x] = (X + 1ll * X * i + (X ^ (1ll * j * x + 1ll * i * i))) % 1000000000;
```

接下来一行一个正整数 $q$，表示修改次数。

对于下标从 $1$ 开始的第 $i$ 次修改，$x=(X\oplus i)\bmod i$，$y=(X\oplus i)\bmod k+1$，$z=(X+(X\oplus i))\bmod (10^9-1)$，表示将第 $x$ 个版本树上所有节点中的所有小朋友的第 $y$ 次祈愿获得的糖果数量乘上 $z$，得到第 $i$ 个版本树。

对于 C++，代码实现如下：

```cpp
x = (X ^ i) % i, y = (X ^ i) % k + 1, z = (X + (X ^ i)) % 999999999;
```

outputFormat:
由于输出文件过大无法上传，接下来我们将会以一种诡异的方式输出数据。

输出一行，表示第 $0\sim q$ 个版本树中快乐的节点数的异或和。


title: [语言月赛 202408] 皆与生物有缘

background: > 他们都是生物课代表。

description:
某次试卷共有 $n$ 道题，一份试卷由两名老师评阅，最终的得分为两名老师评分总分的平均值，向上取整。

现在，给出每名老师为风试卷每一题打的分数，请问风生物最终的得分是多少？

inputFormat:
输入的第一行为一个整数 $n$。

第二行为 $n$ 个非负整数，表示第一名老师给每题的得分。

第三行为 $n$ 个非负整数，表示第二名老师给每题的得分。

outputFormat: 输出一行一个整数，表示风聆最终的得分。


title: 【MX-J2-T0】Turtle and Equations

description:
给你四个正整数 $a, b, c, d$。

现在你有一条算式 $(a\ \Box\ b)\ \Box\ c$。你需要判断能否在两个方框内分别填入三种运算符 $+, -, \times$ 之一（运算符可以重复使用），使得算式运算的结果等于 $d$。

inputFormat: 第一行包含四个正整数 $a, b, c, d$。

outputFormat: 如果能使得运算结果等于 $d$，输出 `Yes`，否则输出 `No`。

hint:
#### 【样例解释 #1】

因为 $(1 + 1) + 1 = 3$，可以在第一个方框内填入 $+$，第二个方框内填入 $+$。

#### 【样例解释 #2】

因为 $(5 - 2) \times 9 = 27$，可以在第一个方框内填入 $-$，第二个方框内填入 $\times$。

#### 【样例解释 #3】

无论填什么运算符都不能使得算式的结果为 $514$。

#### 【数据范围】

对于所有数据，满足 $1 \le a, b, c \le 10$，$1 \le d \le 1000$。


title: 【MX-X2-T6】「Cfz Round 4」Ad-hoc Master

background:
意気込むことはないけれど
尽管不会每天干劲十足

生きていけるよ　君をさがして
但我会继续一边寻找着你一边生活

description:
给定一个正整数 $h$。我们令 $n=2^h-1$。

现给出对于每个不大于 $n$ 的正整数 $u$ 和不大于 $2h-2$ 的正整数 $k$ 所对应的 $f_{u,k}$ 的值，你需要构造一组数对 $(r,w)$，满足 $1 \le r \le n$，$0 \le w \lt 2^{30}$，且存在一棵层数为 $h$ 的**满**二叉树 $T$ 满足：

- 满二叉树 $T$ 中所有结点的编号形成 $1 \sim n$ 的一个排列，且每个结点都有权值；
- 满二叉树 $T$ 的根结点为结点 $r$；
- 满二叉树 $T$ 中每个结点的权值都为小于 $2^{30}$ 的非负整数，且根结点的权值为 $w$；
- 对于每个不大于 $n$ 的正整数 $u$ 和不大于 $2h-2$ 的正整数 $k$，所有满足 $\operatorname{dis}(u,v)=k$ 的结点 $v$ 的权值的**异或和**为 $f_{u,k}$；特殊地，若没有满足条件的结点 $v$，则需要满足 $f_{u,k}=0$。

其中，$\operatorname{dis}(u,v)$ 的值等于结点 $u$ 和结点 $v$ 之间的简单路径所包含的边的数量。特殊地，$\operatorname{dis}(u,u)=0$。

题目保证至少存在一组满足条件的数对 $(r,w)$。

inputFormat:
**本题有多组测试数据。**

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

接下来依次输入每组测试数据。对于每组测试数据：

- 第一行一个正整数 $h$。
- 接下来 $n$ 行，第 $u$ 行包括 $2h-2$ 个整数，其中第 $k$ 个整数表示 $f_{u,k}$ 的值。

outputFormat:
对于每组测试数据，输出一行两个整数，分别表示你构造的数对 $(r,w)$ 中 $r$ 与 $w$ 的值。

- 若你构造的数对 $(r,w)$ 满足条件，则你可以获得该测试点 $100\%$ 的分数；
- 否则，若你构造的数对 $(r,w)$ 不满足条件，但存在一组满足条件的数对 $(r',w')$ 满足 $r'=r$，则你可以获得该测试点 $50\%$ 的分数；
- 否则，若你构造的数对 $(r,w)$ 不满足条件，但存在一组满足条件的数对 $(r',w')$ 满足 $w'=w$，则你可以获得该测试点 $50\%$ 的分数；
- 否则，你不能获得该测试点的分数。

hint:
**【样例解释 #1】**

对于第一组测试数据：

当构造的数对 $(r,w)=(2,1)$ 时，存在一棵如图所示的二叉树符合题意，其中结点 $1,2,3$ 的权值分别为 $2,1,0$。

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

当你输出 `2 2` 时，你可以获得该测试点 $50\%$ 的分数，因为 $(r,w)=(2,2)$ 虽然不满足条件，但存在一组满足条件的数对 $(r',w')=(2,1)$ 满足 $r'=r=2$。

当你输出 `1 1` 时，你也可以获得该测试点 $50\%$ 的分数。

但当你输出 `1 2` 时，你将不能获得该测试点的分数。

**【数据范围】**

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有测试数据，$1\le T \le 1000$，$2 \le h \le 16$，$\sum n \le 2^{16}$，$0 \le f_{u,k}\lt2^{30}$，保证至少存在一组满足条件的数对 $(r,w)$。

**本题采用捆绑测试。**

- Subtask 1（20 points）：$h=2$。
- Subtask 2（20 points）：满足特殊性质。
- Subtask 3（60 points）：无特殊限制。

特殊性质：存在一组数对 $(r,w)$，满足 $1 \le r \le n$，$0 \le w \lt 2^{30}$，且在此基础上存在一棵符合题意的满二叉树，其所有结点的权值均为 $w$。


title: 【MX-X2-T1】「Cfz Round 4」Awaken

background:
能否等到梦醒了的时候。

![图片与题目做法无关，图片来源网络，侵删。QWQ。](https://cdn.luogu.com.cn/upload/image_hosting/wksp5b48.png?x-oss-process=image/resize,m_lfit,h_500,w_500)

description:
月做了一个梦。在梦中，她拿到了一个长度为 $n$ 的**整数**序列 $a_1, \ldots, a_n$，**其中 $\bm{n \ge 5}$**。

梦醒了。月忘记了这个序列中的一部分元素，留下了空白。所幸，月还记得 $m$ 个非空白的位置。月希望将空白的位置填上，还原整个序列。

月还记得梦中的序列有性质：对于所有满足 $x_2+x_3=x_1+x_4$ 的互异下标 $x_1,x_2,x_3,x_4$，总有 $a_{x_2}+a_{x_3}=a_{x_1}+a_{x_4}$ 成立。

月想知道是否可以还原出一个满足性质的序列（如果不能的话，就是她记错了）。若可以，输出 ```Yes```；否则输出 ```No```。

inputFormat:
**本题有多组测试数据。**

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

接下来依次输入每组测试数据。对于每组测试数据：

- 第一行两个整数 $n,m$，其中 $n \ge 5$，$m$ 表示 $a_i$ 中不为空的位置的个数。
- 接下来 $m$ 行，每行两个整数 $p_i,x_i$，表示 $a_{p_i}$ 不为空，且 $a_{{p_i}}=x_i$。保证 $p_i$ 两两不同。

outputFormat:
对于每组测试数据，输出一个字符串 `Yes` 或 `No`，表示原序列是否存在。

本题中字符串大小写不敏感，即 `yes`、`yeS`、`yEs`、`Yes`、`YEs`、`YeS`、`yES`、`YES` 都被认为是 `Yes`，`No` 同理。

hint:
**【样例解释 #1】**

对于第 $1$ 组测试数据，当前序列为 $[1,?,?,4,5]$。可以构造出原序列 $[1,2,3,4,5]$，你可以检查此序列满足性质。

对于第 $2$ 组测试数据，当前序列为 $[1,4,7,1,5,4]$。可以证明不存在满足性质的原序列。这组样例提醒你，**$\bm p$ 不一定升序给出**。

对于第 $3$ 组测试数据，当前序列为 $[?,?,?,?,?]$。可以构造出原序列 $[0,0,0,0,0]$，当然 $[-1,-1,-1,-1,-1]$ 也可以。这组样例提醒你，$m$ 可以等于 $0$，以及原序列可以含有负数或 $0$。

**【数据范围】**

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有测试数据，$1 \le T\le 4\times10^4$，$5\le n\le2\times 10^5$，$\sum n\le 2\times10^5$，$0\le m\le n$，$1\le p_i\le n$，$-10^{9} \le x_i \le 10^{9}$。保证在同一组数据内 $p_i$ 两两不同。

**本题采用捆绑测试。**

- Subtask 1（20 points）：$n\le2000$ 且 $m=n$。
- Subtask 2（30 points）：$n\leq 6$，$|x|\le7$。
- Subtask 3（20 points）：$m=2$。
- Subtask 4（30 points）：无特殊限制。


title: 【MX-X2-T4】「Cfz Round 4」Gcd with Xor

background:
ねえ もしも全て投げ捨てられたら
呐 若然能将一切舍弃的话

笑って生きることが楽になるの
笑着活下去这样的事就会变的轻松吗

description:
给定两个正整数 $n,k$。

定义 $\displaystyle f(x)=\sum_{i=1}^x \gcd(i,i\oplus x)^k$。计算 $\displaystyle \sum_{i=1}^n f(i)$。其中 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公因数，$\oplus$ 表示**按位异或**，即 C++ 中的 `^`。

由于答案可能很大，所以你只需要输出答案对 $10^9+7$ 取模的结果。

inputFormat:
**本题有多组测试数据。**

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

接下来依次输入每组测试数据。对于每组测试数据，输入一行两个正整数 $n,k$。

outputFormat: 对于每组测试数据，输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。

hint:
**【样例解释】**

对于第 $1$ 组测试数据：

$f(1)=\gcd(1,0)^2=1$。

$f(2)=\gcd(1,3)^2+\gcd(2,0)^2=5$。

$f(3)=\gcd(1,2)^2+\gcd(2,1)^2+\gcd(3,0)^2=11$。

$f(1)+f(2)+f(3)=17$。

**【数据范围】**

对于所有测试数据，$1\le T\le 1000$，$1\le n\le 2\times 10^5$，$\sum n\le 2\times 10^5$，$1\le k\le 10^9$。

**本题采用捆绑测试。**

设 $\sum n$ 表示单个测试点中 $n$ 的和。

- Subtask 1（10 points）：$\sum n\le 2000$。
- Subtask 2（12 points）：$\sum n\le 10^4$。
- Subtask 3（15 points）：$k=1$。
- Subtask 4（45 points）：$\sum n\le 10^5$。
- Subtask 5（18 points）：无特殊限制。


title: 【MX-X2-T2】「Cfz Round 4」Xor Counting

background:
生きてもいいような　気がして
或者　就这样活着也不错吧

繰返し笑い合うんだ　居たくなる旅
想要有一段充满欢笑的旅程啊

description:
给定一个长度为 $n$ 的**非负整数**序列 $a_1, \ldots, a_n$。

请你求出满足 $a_i \le (a_i \oplus a_j) \le a_j$ 的下标对 $(i, j)$ 的数量。其中 $\oplus$ 表示**按位异或**，即 C++ 中的 `^`。

inputFormat:
**本题有多组测试数据。**

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

接下来依次输入每组测试数据。对于每组测试数据：

- 第一行一个整数 $n$。
- 第二行 $n$ 个整数 $a_1, \ldots, a_n$。

outputFormat: 对于每组测试数据，输出一行一个整数，表示满足条件的下标对 $(x,y)$ 的数量。

hint:
**【样例解释】**

对于第 $1$ 组测试数据，满足条件的下标对有 $(2,1),(2,2),(2,3),(2,4),(3,1),(3,4)$。

**【数据范围】**

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有测试数据，$1 \le T \le 1000$，$1 \le n \le 5\times10^5$，$0 \le a_i \lt 2^{30}$，$\sum n \le 5\times10^5$。

**本题采用捆绑测试。**

- Subtask 1（30 points）：$\sum n \le 1000$。
- Subtask 2（30 points）：$a_i \ge 1$。
- Subtask 3（40 points）：无特殊限制。


title: 【MX-X2-T5】「Cfz Round 4」Xor-Forces

background: ✿(。◕ᴗ◕。)✿

description:
给定一个长度为 $n=2^k$ 的数组 $a$，下标从 $0$ 开始，维护 $m$ 次操作：

1. 操作一：给定 $x$，设数列 $a'$ 满足 $a'_i=a_{i\oplus x}$，将 $a$ 修改为 $a'$。其中 $\oplus$ 表示按位异或运算。
2. 操作二：给定 $l,r$，查询 $a$ 的下标在 $l,r$ 之间的子数组有多少颜色段。**不保证 $\bm {l\le r}$，若 $\bm{l > r}$，请自行交换 $\bm{l,r}$。**

其中，一个极长的所有数都相等的子数组称为一个颜色段。

部分测试点要求强制在线。

inputFormat:
第一行三个整数 $T,k,m$，其中 $T \in \{ 0, 1 \}$ 为决定是否强制在线的参数。

第二行 $n$ 个整数 $a_0, \ldots, a_{n-1}$。

接下来 $m$ 行，每行两或三个整数，描述一次操作。第一个整数 $\mathit{op}$ 表示操作类型。

- 若 $op=1$，为操作一，接下来一个整数 $x'$，满足 $x=x'\oplus(T\times \mathit{lst})$。
- 若 $op=2$，为操作二，接下来两个整数 $l',r'$，满足 $l=l'\oplus(T\times \mathit{lst})$，$r=r'\oplus(T\times \mathit{lst})$。**不保证 $\bm{l \le r}$，若 $\bm{l > r}$，请自行交换 $\bm{l, r}$。**
- 其中 $\mathit{lst}$ 表示上次询问的答案。特别地，如果此前没有询问操作，则 $\mathit{lst}=0$。

outputFormat: 输出若干行，每行包含一个整数，依次表示每个询问的答案。

hint:
**【样例解释 #1】**

此样例允许离线。

初始时 $a=[1,2,1,3,2,4,5,1]$。

$a$ 的下标在 $1,5$ 之间的子数组为 $[2,1,3,2,4]$，它的颜色段数为 $5$。

进行重排操作后，$a=[3,1,2,1,1,5,4,2]$。

$a$ 的下标在 $5,1$ 之间的子数组为 $[1,2,1,1,5]$，它的颜色段数为 $4$。

**【样例解释 #2】**

此样例除强制在线外，与样例 \#1 完全一致。

**【数据范围】**

对于所有测试数据，$T \in \{ 0, 1 \}$，$0\le k\le 18$，$n=2^k$，$1\le m\le 2\times 10^5$，$1\le a_i\le n$，$\mathit{op} \in \{ 1, 2 \}$，$0\le x,l,r < n$。

**本题采用捆绑测试。**

- Subtask 1（15 points）：$T=1$，$k\le 10$，$m\le 10^3$。
- Subtask 2（15 points）：$T=1$，不存在操作一。
- Subtask 3（20 points）：$T=1$，对于所有操作二，要么 $l=0,r=n-1$，要么 $l=n-1,r=0$。
- Subtask 4（20 points）：$T=0$。
- Subtask 5（30 points）：$T=1$。

**注意：Subtask 5 依赖前四个 Subtask，只有通过前四个 Subtask 才能尝试获得该 Subtask 的分数。**


title: 【MX-X2-T3】「Cfz Round 4」Ninelie

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

沿着单侧无尽响彻的旋律 流经眼前的街道 伴随着落幕的爱 渐行渐远
那无法传达的理想构图日渐扭曲沉寂的抵抗在此刻觉醒 冲动也在此刻姗姗来迟
支离破碎的哭喊和美梦 理想只剩下装饰的门面
哪怕城市乐于被喧嚣嘈杂所淹没
我也会继续高歌舍弃那掌控我的一切
所以只愿那静谧 再度响彻
> 无需畏惧 黎明已然降临

description:
给定一个长为 $n$ 的 $01$ 序列 $a_1, \ldots, a_n$ 以及一个正整数 $r$。

你可以对序列 $a$ 进行操作。每次操作需选定一个下标 $p$，满足 $p$ 为 $1$ 或 $n$ 或 $a_{p-1}\neq a_{p+1}$，然后将 $a_p$ 翻转（即将 $0$ 变为 $1$，将 $1$ 变为 $0$）。

请你在 $r$ 次操作内将序列 $a$ 变成全 $0$ 或全 $1$。**你不需要最小化操作次数**。如果无法完成，你需要报告无解。

**数据保证 $\bm{r = 2 \times 10^6}$ 或 $\bm{10^6}$，具体细节请参见【数据范围】一节。**

inputFormat:
第一行两个正整数 $n,r$。

第二行 $n$ 个整数 $a_1, \ldots, a_n$。

outputFormat:
若无法在 $r$ 次操作内将序列 $a$ 变成全 $0$ 或全 $1$，则输出一行一个整数 $-1$。

若存在一种构造方案，则输出两行：

- 第一行包含一个非负整数 $m$，表示你的操作次数；你需要保证 $m\le r$，**你不需要最小化 $\bm m$**；
- 第二行包含 $m$ 个正整数，依次表示每次操作的下标 $p$。

hint:
**【样例解释 #1】**

每次操作后的序列 $a$ 分别为：

- $[0,1,1,0]$；
- $[0,1,1,1]$；
- $[1,1,1,1]$。

此时序列 $a$ 中的全部元素均相同。

**【数据范围】**

对于所有测试数据，$2\le n\le 2\times 10^3$，$a_i\in\{0,1\}$，$r = 2 \times 10^6$ 或 $10^6$。

**本题采用捆绑测试。**

- Subtask 1（20 points）：$n\le 10$，$r=2\times 10^6$。
- Subtask 2（30 points）：$r=2\times 10^6$。
- Subtask 3（50 points）：$r=10^6$。


title: [语言月赛 202409] 灵感

description:
这天，迅风在欣赏某地的美景时，灵感大作，在上午及下午**分别**写下了两篇文章，而且迅风很喜欢数文章的字数。

具体地，如果迅风在下午写下的文章的字数之和**严格大于**他在上午写下的文章的字数之和，则认定他的灵感随着时间的推移越积越多。

现在给出迅风所写的四篇文章的字数，请你回答他的灵感是否随着时间的推移越积越多。

inputFormat: 共一行，包含四个正整数 $a,b,c,d$ 分别表示迅风在上午写下的两篇文章的字数及他在下午写下的两篇文章的字数。

outputFormat: 答案共一行，若迅风的灵感随着时间的推移越积越多，则输出 `Yes`；否则，输出 `No`。

hint:
### 样例解释 1
第一个样例中，迅风在上午写下的文章的字数之和为 $3+2=5$，在下午写下的文章的字数之和为 $4+5=9$，由于 $9>5$，所以认定他的灵感随着时间的推移越积越多。
### 样例解释 2
第二个样例中，迅风在上午写下的文章的字数之和为 $3+3=6$，在下午写下的文章的字数之和为 $4+2=6$，由于 $6=6$，所以认定他的灵感不会随着时间的推移越积越多。

### 数据范围

对于 $100\%$ 的数据，$1\le a,b,c,d\le100$。


title: 【MX-X6-T1】Subtask Dependency

description:
现在有一道 OI 题。这道题有 $n$ 个子任务，编号从 $1$ 到 $n$。编号为 $i$ 的子任务依赖 $d_i$ 个子任务，这些子任务的编号分别为 $a_{i,1},a_{i,2},\dots,a_{i,d_i}$。保证对于所有 $1\leq i\leq n,1\leq j\leq d_i$，有 $a_{i,j}<i$，即**一个子任务只会依赖编号小于自己的子任务**。注意一个子任务可能不依赖任何子任务。

一个选手的程序可以描述为一个长度为 $n$ 的 $0/1$ 序列 $p_1,p_2,\dots,p_n$，分别表示该程序能否通过第 $i$ 个子任务。

评测一个程序时，评测机会按照编号从小到大依次考虑每一个子任务。当考虑到第 $i$ 个子任务时：

- 如果该子任务依赖的子任务中存在一个子任务的状态为错误，则该子任务的状态为错误；
- 否则，评测机测试该子任务。如果选手的程序能通过该子任务，则该子任务状态为正确；否则状态为错误。

一个程序的得分是评测后状态为正确的子任务个数。

现在有 $m$ 个选手提交程序，你需要分别计算它们的得分。

inputFormat:
第一行一个整数 $n$ 表示子任务个数。

接下来 $n$ 行，第 $i$ 行首先输入一个整数 $d_i$ 表示第 $i$ 个子任务依赖的子任务个数；接下来输入 $d_i$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,d_i}$ 表示依赖的子任务编号。保证所有 $a_{i,j}<i$。

接下来一行一个整数 $m$，表示选手程序个数。

接下来 $m$ 行，每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数 $p_{i,j}$ 为 $0$ 表示第 $i$ 个选手的程序不能通过第 $j$ 个子任务；为 $1$ 表示第 $i$ 个选手的程序能通过第 $j$ 个子任务。

outputFormat: 输出 $m$ 行，第 $i$ 行输出第 $i$ 个选手的得分。

hint:
**【样例解释 #1】**

- 选手 1 的程序可以通过所有子任务，因此所有 $3$ 个子任务的结果均为正确；
- 选手 2 的程序不能通过子任务 2，因此子任务 2 会被判定为错误；由于子任务 3 依赖子任务 2，因此即使选手 2 的程序可以通过子任务 3，子任务 3 也会被判定为错误。该选手的程序的评测结果只有子任务 1 正确。
- 选手 3 的程序不能通过任何子任务，因此所有子任务结果均为错误。

**【数据范围】**

对于所有数据，满足 $1\leq n,m\leq 100$，$0\leq d_i<i$，$1\leq a_{i,j}<i$，$0\leq p_{i,j}\leq 1$，不存在 $i$ 和 $j_1\neq j_2$ 使得 $a_{i,j_1}=a_{i,j_2}$。

共 $10$ 组数据，具体限制如下：

- 对于第 $1,2$ 组数据，满足 $n=1$；
- 对于第 $3,4,5$ 组数据，满足对所有 $i$，有 $d_i\leq 1$；
- 对于其他数据，不满足任何附加限制。


title: 【烂题杯 Round 1】消灭劳嗝

description:
你需要消灭劳嗝。

给定一个长度为 $n$ 的排列 $A=a_1,a_2,\cdots,a_n$，定义 $S_i=\{x|x\ge i\land \max_{i\le k\le x}a_k\le a_x\}$，您可以把它理解为以 $i$ 开头的后缀的前缀最大值的下标集合。例如对于 $A=\{3,5,2,1,4\}$，$S_1=\{1,2\}$，$S_3=\{3,5\}$。

有 $q$ 次询问，每次询问给出 $l,r$，求：

$$
\left(\left(\sum_{l\le x\le y\le r} |S_x\cup S_y|-\sum_{\substack{{1\le x<l}\\{r<y\le n}}} |S_x\cup S_y|\right)\bmod P+P\right)\bmod P
$$

其中，$P=998244353$。

inputFormat:
由于输入文件过大无法上传，接下来我们将会以一种诡异的方式读入数据。

第一行输入两个非负整数 $n$、$X$。表示排列长度、随机种子。

初始令 $a_i=i$，接下来输入一行一个整数 $c$，表示对排列的操作次数。

接下来我们将会对排列 $A$ 进行 $c$ 次操作，对于下标从 $1$ 开始的第 $i$ 次操作，令 $l=(X\times (X\oplus i))\bmod n+1,r=(X\oplus(i\times i))\bmod n+1$，你需要交换 $a_l$ 与 $a_r$。$\oplus$ 表示按位异或。

对于 C++，代码实现如下：

```cpp
l = (1ll * X * (X ^ i)) % n + 1;
r = (X ^ (1ll * i * i)) % n + 1;
```

接下来输入一行一个整数 $q$，表示询问组数。

对于下标从 $1$ 开始的第 $i$ 次询问，我们令 $l=\min((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1,r=\max((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1$。表示询问的参数。

对于 C++，代码实现如下：

```cpp
l = min((1ll * X * i + (X ^ (1ll * X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
r = max((1ll * X * i + (X ^ (1ll * X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
```

outputFormat:
由于输出文件过大无法上传，接下来我们将会以一种诡异的方式输出数据。

输出一行一个整数，表示 $q$ 次询问中所有答案的异或和。


title: [语言月赛 202409] 种子

description:
迅风种下了一粒种子。起初，种子的成长值为 $0$，**当某一天过完后**，它的成长值大于等于 $k$ 时，则代表它已经破土而出。

从第 $1$ 天开始，种子会开始生长。原本这粒种子在第 $i$ 天会增加 $\lfloor\frac{i}{w}\rfloor$ 的成长值，但由于各种因素的干扰，从第 $x$ 天开始（包含第 $x$ 天），它每天都会**额外**增加 $y$ 的成长值。

请你求出这粒种子是在**第几天**破土而出的。

提示：$\lfloor x \rfloor$ 表示取不大于 $x$ 的最大整数。例如 $\lfloor 2.5 \rfloor = 2$。在 C++ 中，可以使用 `floor` 函数进行向下取整。例如 `floor(2.9)=2`，函数返回值为浮点型。对于本题，在 C++ 中，$\lfloor\frac{i}{w}\rfloor$ 可以用 `int(i/w)` 表示。

inputFormat: 一行四个正整数 $x,y,w,k$，含义见题面。

outputFormat: 一行一个**正整数** $p$ 表示种子在第 $p$ 天结束时破土而出。

hint:
### 样例解释 #1

第 $1$ 天成长值为：$0+\lfloor\frac{1}{2}\rfloor=0$，\
第 $2$ 天成长值为：$0+(\lfloor\frac{2}{2}\rfloor+2)=3$，\
第 $3$ 天成长值为：$3+(\lfloor\frac{3}{2}\rfloor+2)=6$。
因此该种子在第 $3$ 天结束时破土而出。

### 数据范围

对于前 $20\%$ 的数据，满足种子在第 $x$ 天以内（包含第 $x$ 天）破土而出。

对于前 $50\%$ 的数据，满足 $1\le x,k,w\le 1000$，$0\le y \le 1000$。

对于 $100\%$ 的数据，满足 $1\le x,k,w\le 10^6$，$0\le y \le 10^6$。


title: 『STA - R7』求和

description:
Lloyd 有一个正整数 $t$，初始 $t=2$ 或 $t=3$。每次他可以令 $t$ 加上 $2^t$ 或者 $\lfloor\log_2(t-1)\rfloor$。

令 $f(x)$ 是操作得到 $t=x$ 的最小操作次数，若无法操作得到 $x$ 则 $f(x)=0$。

现在给定一个正整数 $n$，你需要求 $\sum_{i=1}^nf(i)$ 的值。答案可能很大，对 $998244353$ 取模。

inputFormat:
**本题有多组测试。**

第一行一个正整数 $T$ 表示数据组数。

后 $T$ 行一行一个正整数 $n$ 描述一组询问。

outputFormat: $T$ 行，每行回答一个询问。答案对 $998244353$ 取模。

hint:
数据范围：
- Subtask 1 (10pts)：$n\le 10^7$。
- Subtask 2 (30pts)：$T=1$。
- Subtask 3 (30pts)：$n\le2^{40}$。
- Subtask 4 (30pts)：无特殊限制。

对于全部数据，$1\le T\le 10^4$，$1\le n\le2^{60}$。


title: [HBCPC2024] Genshin Impact Startup Forbidden II

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

Blue-edged Shot is forbidden from playing Genshin Impact by LeavingZ, so she turned to Go game.

A game of Go involves two players, one playing with Black stones and the other with White stones. Two players take turns making moves, with the Black stones going first. The Go board is composed of a grid of $19\times 19$ intersections, and we use $(x,y)$ to represent the intersection at the $x$-th row and $y$-th column. The stones are placed on the intersections. The top left corner is $(1,1)$, while the bottom right corner is $(19,19)$.

The intersections $(x_1,y_1)$ and $(x_2,y_2)$ are adjacent if and only if $|x_1-x_2| + |y_1-y_2| = 1$. Adjacent intersections with stones of the same color belong to the same group of stones. The number of `liberties` for a stone is equal to the number of adjacent intersections to the stone's intersection that do not have any stones on them. The liberties of a group of stones equal the sum of the liberties of all the stones belonging to that group. A group of stones with zero liberties is considered dead and must be removed from the board.

Note that after Black plays, priority is given to removing any dead White stones, and then recalculating the liberties for Black stones. This is because there might be situations where, after Black plays, both Black and White stones have zero liberties, but removing the dead White stones increases the liberties for Black stones. As for White, process the stones similarly. After White plays, priority is given to removing any dead Black stones, and then recalculating the liberties for White stones.

Now there is a game of Go, starting with an empty board, and a total of $m$ moves have been made by both players. Given the positions where each stone is placed, output after each move, how many Black and White stones are removed respectively causing by this move. Obviously, black stones are played on odd-numbered moves, and white stones are played on even-numbered moves. It's guaranteed that stones are placed on empty intersections. Note that stones can be placed on $\textbf{any}$ intersections that do not have stones on them at the moment, regardless of violating the Go rules in real life.

inputFormat:
Input $m$ ($1 \le m \le 5\times 10^5)$ lines, the $i$-th line contains two integers $x_i,y_i$ ($1 \le x_i,y_i \le 19$), representing the $i$-th move puts stone on $(x_i,y_i)$.

It's guaranteed that stones are placed on intersections that do not have stones on them at the moment.

outputFormat: Output $m$ lines, each line contains two integers. The first integer in the $i$-th line represents the number of Black stones removed after the $i$-th move, while the second for White stones.

translation:
### 弹窗内容

LeavingZ：你被禁止玩《原神》。

### 题目描述

蓝边铅球因LeavingZ的禁止而无法玩《原神》，所以她转向了围棋。

围棋游戏由两名玩家进行，一方使用黑子，另一方使用白子。两名玩家轮流下子，黑子先行。围棋棋盘由$19\times 19$的交叉点组成，我们用$(x,y)$表示第$x$行第$y$列的交叉点。棋子放置在交叉点上。左上角为$(1,1)$，右下角为$(19,19)$。

如果$|x_1-x_2| + |y_1-y_2| = 1$，那么交叉点$(x_1,y_1)$和$(x_2,y_2)$是相邻的。相邻的交叉点上放置相同颜色的棋子属于同一组棋子。一个棋子的“气”数等于该棋子所在交叉点的相邻交叉点上没有棋子的个数。一组棋子的“气”数等于该组棋子中所有棋子的“气”数之和。一组棋子如果“气”数为零，则被视为“死棋”并且必须从棋盘上移除。

注意，在黑子落子后，优先移除任何死掉的白子，然后重新计算黑子的“气”数。这是因为可能出现这样的情况：黑子落子后，黑白两方的棋子都没有“气”，但移除死掉的白子会增加黑子的“气”。白子落子的处理方式类似。在白子落子后，优先移除任何死掉的黑子，然后重新计算白子的“气”数。

现在有一局围棋，从空棋盘开始，总共进行了$m$步。给定每步棋子的放置位置，请输出每步棋子落子后，分别有多少颗黑子和白子被移除。显然，黑子在奇数步落子，白子在偶数步落子。保证棋子放置在空的交叉点上。注意，棋子可以放置在$\textbf{任意}$当前没有棋子的交叉点上，无论是否违反了现实中的[围棋规则](https://zhuanlan.zhihu.com/p/440794632)$^{(1)}$。

注释：
- (2):译者补充

### 输入格式

输入包含 $m$ 行（$1 \le m \le 5\times 10^5$），第 $i$ 行包含两个整数 $x_i, y_i$ （$1 \le x_i, y_i \le 19$），表示第 $i$ 步在 $(x_i, y_i)$ 位置放置棋子。

保证棋子放置在当前没有棋子的交叉点上。

### 输出格式

输出包含 $m$ 行，每行包含两个整数。第 $i$ 行的第一个整数表示第 $i$ 步后被移除的黑子数量，第二个整数表示被移除的白子数量。

翻译者：[Immunoglobules](https://www.luogu.com.cn/user/1066251)


title: [HBCPC2024] Genshin Impact Startup Forbidden III

description:
Blue-edged Shot is forbidden from playing Genshin Impact by LeavingZ. However, today LeavingZ went to Huazhong University of Science and Technology, School of Cyber Science and Engineering, to harvest the gold medal of the 2024 International Collegiate Programming Contest in Hubei Province, China.

An activity of Genshin Impact called `Dodoco's Bomb-Tastic Adventure` has begun. This is a single-player game, where each game involves a pond. The pond can be divided into an $n$ by $m$ grid, with the cell in the $i$-th row and $j$-th column represented by $(i,j)$. Among these, $k$ cells contain fish, and you will play as the Spark Knight Klee, who fishes with explosives.

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

If Klee drops a bomb at $(a,b)$, all the cells $(x,y)$ satisfying $|x-a|+|y-b|\le 1$ will be covered by the explosion. For every cell covered by the explosion, Klee will catch one fish from it. Klee can drop bombs at any location. The question is, to catch all the fish, how many `Jumpy Dumpty` bombs are needed at a minimum?

inputFormat:
The first line contains three integers $n,m,k$ ($1 \le n,m \le 10^3, 1 \le k \le 10$) --- the size of the grid and the number of cells containing fish.

The following $k$ lines, each line contains three integers $x_i,y_i,a_i$ ($1\le x_i \le n, 1 \le y_i \le m, 1 \le a_i \le 3$), representing there are $a_i$ fish in cell $(x_i,y_i)$.

It is guaranteed that the input cell $(x_i,y_i)$ are unique.

outputFormat: Output a single integer, denoting the minimum number of bombs needed.

hint:
One possible way is to drop two bombs at $(1,2)$ and another two at $(5,5)$.

It can be proven that there is no solution with a smaller answer.


title: [HBCPC2024] Colorful Tree

description:
You are given a tree with $n$ nodes numbered from $1$ to $n$ and $n - 1$ edges. Each node has a color. Initially, all of them are white.

We are going to perform $q$ operations. In each operation, two vertices $u$ and $v$ will be given, and we will color black to the points along the simple path from $u$ to $v$ ($u,v$ inclusive). Note that a simple path in the tree is defined as a path that does not pass through any vertex more than once.

After each operation, you are required to determine the length of the longest simple path in the tree where all nodes on the path are the same color. The length of a path is defined as the number of nodes on the path.

inputFormat:
The first line contains a single integer $T$ ($1 \le T \le 100$) indicating the number of test cases.

For each test case, the first line contains two integers $n$ ($1 \le n \le 2\times 10^5$) and $q$ ($1 \le q \le 2\times 10^5$), indicating the number of nodes in the tree and the number of operations, respectively.

In the following $n-1$ lines, each contains two integers $u$ and $v$, representing an edge from vertex $u$ to $v$ in the tree.

Then follow $q$ lines, each contains two integers $u$ and $v$, representing an operation that colors black to the points along the path from vertex $u$ to $v$.

It is guaranteed that the sum of $n$ and $q$ of all the test cases in a test does not exceed $2\times 10^5$ respectively.

outputFormat: For each test case, output $q$ lines, each line should contain an integer representing the length of the longest simple path in the tree where all nodes on the path are the same color after the corresponding operation.

translation:
### 题目描述

给你一棵有 $n$ 个节点的树，节点编号从 $1$ 到 $n$，并且有 $n-1$ 条边。每个节点都有一个颜色。起初，所有节点的颜色都是白色。

我们将进行 $q$ 次操作。在每次操作中，会给出两个顶点 $u$ 和 $v$，然后我们将沿着从 $u$ 到 $v$ 的简单路径上的所有节点（包括 $u$ 和 $v$）染成黑色。注意，树中的简单路径定义为路径上的任意顶点都不会被重复经过。

在每次操作之后，你需要确定树中最长的简单路径，其路径上的所有节点的颜色相同。路径的长度定义为路径上的节点数目。

### 输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ ($1 \le n \le 2\times 10^5$) 和 $q$ ($1 \le q \le 2\times 10^5$)，分别表示树中节点的数量和操作的数量。

紧接着$^{(1)}$的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$，表示树中顶点 $u$ 和 $v$ 之间的一条边。

接下来 $q$ 行，每行包含两个整数 $u$ 和 $v$，表示将从顶点 $u$ 到顶点 $v$ 的路径上的所有节点染成黑色的操作。

保证一个测试中所有测试用例的 $n$ 和 $q$ 的总和均不超过 $2\times 10^5$。$^{(2)}$

注释：
- (1):也可以译为接下来，此处译者只是想区分下条的语句。
- (2)可以用以下数学表达式表示：

$$
\sum_{i=1}^{T} n_i \leq 2 \times 10^5 \quad \text{且} \quad \sum_{i=1}^{T} q_i \leq 2 \times 10^5
$$

其中 $n_i$ 和 $q_i$ 分别表示第 $i$ 个测试用例中的节点数量和操作数量。

### 输出格式

对于每个测试用例，输出 $q$ 行，每行应包含一个整数，表示在执行相应操作后，树中所有节点颜色相同的最长简单路径的长度。

翻译者：[Immunoglobules](https://www.luogu.com.cn/user/1066251)


title: [HBCPC2024] Points on the Number Axis A

description:
Alice is playing a single-player game on the number axis.

There are $n$ points on the number axis. Each time, the player selects two points. The two points will be removed, and their midpoint will be added. When there is only one point on the axis, the game ends. Formally, if the two chosen points is $x_i$ and $x_j$, then $\dfrac{x_i+x_j}{2}$ will be added after the operation.

In order to play this game happily, Alice will always select two points randomly.

Now Alice have a question: where is the expected position of the last point.

It can be proven that the answer can be expressed in the form $\dfrac{p}{q}$, you only need to output the value of $p\cdot q^{-1} \bmod 998\,244\,353$.

inputFormat:
The first line contains one integer $n$ ($1 \le n \le 10^6$).

The second line contains $n$ integers $x_i$ ($0 \le x_1 \le \dots \le x_n < 998\,244\,353$), denoting the position of the $i$-th point.

Note that two points may be in the same position.

outputFormat: Output one integer, the answer modulo $998\,244\,353$.


title: [HBCPC2024] Points on the Number Axis B

description:
Bob is playing a single-player game on the number axis.

There are $n$ points on the number axis. Each time, the player selects two points. The two points will be removed, and their midpoint will be added. When there is only one point on the axis, the game ends. Formally, if the two chosen points is $x_i$ and $x_j$, then $\dfrac{x_i+x_j}{2}$ will be added after the operation.

In order to play this game happily, Bob will always select two adjacent points randomly. Initially, the $i$-th point and the $(i+1)$-th point are adjacent. When Bob added a new point, it inherits its left point's left adjacent point and its right point's right adjacent point.

Now Bob have a question: where is the expected position of the last point.

It can be proven that the answer can be expressed in the form $\dfrac{p}{q}$, you only need to output the value of $p\cdot q^{-1} \bmod 998\,244\,353$.

inputFormat:
The first line contains one integer $n$ ($1 \le n \le 10^6$).

The second line contains $n$ integers $x_i$ ($0 \le x_1 \le \dots \le x_n < 998\,244\,353$), describing the position of the $i$-th point.

Note that two points may be in the same position.


title: [HBCPC2024] LCMs

description:
Walk Alone has a number axis with only positive integers on it. The cost of walking from point on integer $a$ to point on integer $b$ is ${\rm lcm}(a, b)$, where ${\rm lcm}(a, b)$ means the least common multiple of integers $a$ and $b$. Due to the hatred of the integer $1$, Walk Alone forbids anyone from moving to points on integers $\textbf{smaller than or equal to}$ $1$.

Given two integers $a$ and $b$, you need to calculate the minimal cost of walking from point on integer $a$ to $b$.

inputFormat:
There are $T$ ($1 \le T \le 1000$) test cases.

In each test case, there is only one line containing two integers $a$ and $b$ ($2 \le a \le b \le 10^7$), denoting the start and end point.

outputFormat: For each test case, output a single integer denoting the minimal cost.

hint: In the first test case, you can walk such a path: $3 \to 2 \to 4$, where the total cost is ${\rm lcm}(3, 2) + {\rm lcm}(2, 4) = 6 + 4 = 10$, which can be proved to be the minimum.


title: [COTS/CETS 2022] 皇后  Kraljice

background: 译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D1T1。$\texttt{1s,0.5G}$。

description:
有一块 $N\times N$ 的国际象棋棋盘，**依次**在空格子上放置皇后，最大化放置皇后的数量。你需要构造一组方案。

能在一个格子上放置皇后，当且仅当这个格子被偶数个皇后攻击。

一个皇后攻击一个格子，当且仅当皇后所在的格子与被攻击格子处于同一行/列/对角线上。

inputFormat: 一行一个整数 $N$。

outputFormat:
第一行一个整数 $K$，表示能放置的最多皇后数量。

接下来 $K$ 行，每行两个整数 $x,y$，描述放置皇后的位置。


title: [COTS/CETS 2022] 移位 Maliand

background:
译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D1T2。$\texttt{2s,0.5G}$。

[SPJ link](https://www.luogu.com.cn/paste/9qlivbk0)。

description:
圆写下了非负整数 $N,K,L$，让焰构造两个 $01$ 序列 $S,T$，满足：

- $S,T$ 的长度为 $N$；
- $S$ 中恰好有 $K$ 个 $1$，$T$ 中恰有 $L$ 个 $1$；
- $f(S,T)$ 是所有可能的 $f(S,T)$ 中最小的。

定义 $f(S,T)$ 为**任意**循环移位 $S,T$ 后，$\sum_{i=1}^{N} S_i\operatorname{and} T_i$  的最大值，其中 $\mathrm{and}$ 表示按位与运算。

请你帮焰构造 $S,T$。

inputFormat: 一行三个整数 $N,K,L$。

outputFormat:
第一行一个整数 $F$，表示 $f(S,T)$ 的最小值；

接下来两行分别描述序列 $S,T$。相邻元素之间不需要加空格。

若有多解，输出任意一个均可。

hint:
对于 $100\%$ 的数据，保证 $1\le N\le 5\times 10^5$，$0\le K,L\le N$。

| 子任务编号 | 分值 | 约束  |
|:-----:|:------:|:-------:|
| $1$  | $5$  | $1\le N\le 13$  |
| $2$  | $50$  | $1\le N\le 5\, 000$  |
| $3$  | $45$  | 无额外约束 |

【评分方式】

如果你回答对了 $F$，可以得到 $20\%$ 的分数；

在此基础下，如果你的 $S,T$ 满足条件，将获得剩下 $80\%$ 的分数。

如果只打算回答第一问，也要任意输出两个符合条件 $1,2$ 的 $01$ 序列，否则不保证能得到分数。


title: [COTS/CETS 2022] 帽子 Šeširi

background:
译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D1T3。$\texttt{3s,0.5G}$。

喜欢小圆！

description:
$N$ 个 OIer 头上戴着红色或者白色的帽子。每个人只能看到别人的帽子颜色，他们会根据别人的帽子颜色猜测自己头上帽子的颜色。

小圆想要请他们共进晚餐，前提是，必须满足以下条件：

- 设有 $b$ 人戴了白色帽子，其中**至少**有 $\lfloor\frac{b}{2}\rfloor$ 人猜对自己帽子的颜色。
- 设有 $c$ 人戴了红色帽子，其中**至少**有 $\lfloor\frac{c}{2}\rfloor$ 人猜对自己帽子的颜色。

OIer 们都想和小圆共进晚餐，帮助他们找到一种策略，使得在 $2^N$ 种可能的情况中，他们都能和小圆共进晚餐。

outputFormat:
输出 $N$ 行，每行一个长度为 $2^{N-1}$ 的字符串，由 $\texttt{B},\texttt{C}$ 组成。

第 $i$ 行的字符串描述了第 $i$ 个 OIer 的策略。具体地说：

- 定义 $f(S)$ 为：将所有长度为 $(N-1)$ 的由 $\texttt{B},\texttt{C}$ 组成的字符串按照字典序排序后，$S$ 的排名。
- 记 $x$ 为第 $i$ 行输出的字符串，$s_i\in \{\texttt{B},\texttt{C}\}$ 为第 $i$ 个 OIer 头上戴的帽子颜色。其中 $\texttt{B}$ 是白色（克罗地亚语「bijela」），$\texttt{C}$ 是红色（克罗地亚语「crvena」）。
- 记 $y=\overline{s_1s_{2}\cdots s_{i-1}s_{i+1}\cdots s_n}$。注意左边是高位。
- 第 $i$ 个 OIer 会猜测的颜色为 $x_{f(y)}$。

可参阅【样例解释】。


title: [COTS/CETS 2022] 旅程 Dugput（民间数据）

background:
译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D2T1。$\texttt{5s,0.5G}$。

- **输入格式有微调。**
- **官方数据有误。** 部分 out 文件是使用树姐姐 [
hhoppitree](https://www.luogu.com.cn/user/183609) 的代码生成的。如果出现了分数 $\gt 100$ 的情况，欢迎联系搬题人更新数据。

description:
构造一个 $N\times M$ 的网格图，边权均为 $1$，每条边可以存在或者不存在。

在连通的前提下，最大化 $(A,B)$ 到 $(C,D)$ 的最短路长度。

**此处路径长度定义为路径经过的节点个数。**

inputFormat:
**本题单个测试点内含有多组测试数据。**

第一行，两个整数 $\mathrm{type},T$，表示测试数据类型和测试数据组数。

接下来 $T$ 行，每行 $6$ 个整数 $N,M,A,B,C,D$，含义见题面。

outputFormat:
每组测试数据输出若干行。

- $\mathrm{type}=0$：「构造」类数据

此类数据中，你需要构造一个网格图。输出 $(2N-1)$ 行，每行 $(3M-2)$ 个字符。

其中，第 $(2i-1)$ 行的第 $(3j-2)$ 个字符代表点 $(i,j)$。当 $(i,j)=(A,B)$ 或 $(S,T)$ 时，用 `*`（ASCII 42）表示；否则用 `o`（ASCII 111）表示。

对于同一行的两个点 $(i,j),(i,j+1)$，若有边，则用 `--`（ASCII 45）填充它们之间的两个空格；否则不填充。

对于同一列的两个点 $(i,j),(i+1,j)$，若有边，则用 `|`（ASCII 124）填充它们之间的一个空格；否则不填充。

未填充的区域均用空格补齐。不要输出多余的空格和空行。

可参阅样例输出。

- $\mathrm{type}=1$：「传统」类数据

只需要输出一行一个整数，表示最短的最长路长度。


title: [COTS/CETS 2022] 游戏 M

background: 译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D2T2。$\texttt{3s,0.5G}$。

description:
圆和焰在玩游戏。

有一张 $N$ 个节点的无向图，焰会依次向图中添加 $M$ 条边。

焰有 $Q$ 个询问，每次询问给定 $u,v$，问：至少添加前多少条边，才能使得 $u,v$ 间没有割边（换言之，割去任意一条边，都不影响 $u,v$ 的连通性）。特别地，如果 $u,v$ 始终不连通或者始终有割边，则输出 $-1$。

圆准备要去军训了，所以找来了你解决这个问题。

inputFormat:
第一行，两个整数 $N,M$，含义见题面；

接下来 $M$ 行，第 $i$ 行包含两个整数 $s_i,t_i$，表示第 $i$ 条边为 $(s_i,t_i)$。

第 $(M+2)$ 行，一个整数 $Q$，含义见题面；

接下来 $Q$ 行，每行两个整数 $u,v$，描述一个询问。

outputFormat: 输出 $Q$ 行，每行一个整数，表示询问的答案。


title: [COTS/CETS 2022] 点组 Točkice

background: 译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D2T3。$\texttt{1s,0.5G}$。

description:
鱼和光在玩游戏。

焰在二维平面上画了 $N$ 个点 $(x_i,y_i)$，其中任意三点不共线。

从鱼开始，两人轮流玩游戏：

- 选择两个点 $(x_i,y_i),(x_j,y_j)$（$i\neq j$）。若连接这两点的线段不与之前的线段相交，则在两点间连一条线段。
- 不能操作的玩家负。

需要注意的是：**线段可以在顶点处相交**（即可以共用一个顶点）。

鱼和光都绝顶聪明，焰想知道鹿死谁手。

inputFormat:
第一行，一个整数 $N$；

接下来 $N$ 行，每行两个整数 $x_i,y_i$。

outputFormat: 如果先手（鱼）胜，输出 `Alenka`；否则输出 `Bara`。


title: Inversion Pair

description:
对于一个序列 $p$，我们定义：$p$ 中的逆序对个数为 $\mathrm{W}(p)$。

注：这里的逆序对即为满足 $p_i>p_j$ 且 $i<j$ 的一对数。

现在，给定一个序列 $a$，其为整数 $1\sim n$ 的排列。也就是说，对于任意的 $1\le i\le  n$，都有 $1\le a_i\le n$，$a_i$ 均为整数且互不相同。

现有一张图，上有 $n$ 个节点，编号为整数 $1\sim n$。对于任意的两个编号为 $i,j(1\le i< j\le n)$ 的节点，我们将在它们之间连一条权值为 $\mathrm{W}([a_i,a_{i+1},\dots,a_{j-1},a_j])$ 的无向边。

现有 $q$ 次询问。每次询问给出两个编号为 $x,y$ 节点，求它们之间的最短路径。

inputFormat:
第一行两个整数 $n,q$。

第二行 $n$ 整数表示序列 $a$。

接下来 $q$ 行，每行两个整数表示一次询问的 $x,y$。

outputFormat:
对于每一次询问：

一个整数表示所求的最短路径。


title: 【MX-S3-T1】「FeOI Round 1」野心

description: 给出一个 $1 \sim n$ 的排列 $p$，询问存在多少个数 $i$（$1 \le i <n$）满足 $[p_1,p_2,\cdots,p_i]$ 和 $[p_{i+1},p_{i+2},\cdots,p_n]$ 排序后都是等差数列。

inputFormat:
**本题单个测试点内包含多组数据。**

第一行一个整数 $T$ 表示数据组数。

接下来，对于每组数据，格式如下：

第一行一个数 $n$ 表示排列长度。

接下来一行 $n$ 个数表示排列 $p$。

outputFormat: 对于每组测试数据，输出一行一个数表示询问的答案。


title: 【MX-X5-T6】「GFOI Round 1」Abiogenesis

background:
> [Abiogenesis - Juggernaut.](https://music.163.com/#/song?id=1416321652)

本题为 [Codeforces 1981 E. Turtle and Intersected Segments](https://codeforces.com/contest/1981/problem/E) 改编。

description:
给 $n$ 条线段 $[l_i, r_i]$，第 $i$ 条线段有一组权值 $a_i, b_i$。

有一个无向图 $G$，其初始有 $n$ 个结点，$0$ 条边。对于每一对正整数 $i, j$ 满足 $1 \le i < j \le n$，若编号为 $i, j$ 的线段相交，就在 $G$ 中连一条两个端点分别为 $i, j$，边权为 $a_i + a_j + |b_i - b_j|$ 的边。

求 $G$ 最小生成树边权之和，或报告 $G$ 不连通。

如果两条线段 $[l_1, r_1]$ 和 $[l_2, r_2]$ 满足 $\max(l_1, l_2) \le \min(r_1, r_2)$，就认为它们是相交的。

inputFormat:
**本题有多组测试数据。**

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

对于每组测试数据：

第一行包含一个正整数 $n$，表示线段的个数。

之后的 $n$ 行中的第 $i$ 行包含四个正整数 $l_i, r_i, a_i, b_i$。

outputFormat: 对于每组数据，输出一行一个整数，表示 $G$ 最小生成树边权之和。特别地，若 $G$ 不连通，输出 $-1$。


title: [COCI 2017-2018#2] Doktor

background:
搬运自 [COCI 2017/2018 Contest #2](https://hsin.hr/coci/archive/2017_2018/) T3「Doktor」，[原题题面](https://hsin.hr/coci/archive/2017_2018/contest2_tasks.pdf)。

Special Judge 由搬题人提供，如果有锅请私信，谢谢。

description:
> And the Mrs, Ms, says:
>
>"I've been riding horses for fifteen years, and it is impossible to shoe a horse upside down!"
>
> (…)

"Yes, that's upside down" - whispers Domagoj, looking at Mate's hand while playing, for the purposes of this task, a heavily modified version of the card game Hanabi. For the sake of simplicity, Mate is holding $N$ cards in his hands, numbered from $1,2,\dots,N$
 in a certain order. (Each number from $1$ to $N$
appears exactly once.) As when playing the real game, he cannot voluntarily change the card order.

Just so the task is at least somewhat related to the story, Domagoj will point for Mate to a contiguous subarray of cards. (He can point to a single card too, but he will point to at least one card.) Mate will then "rotate" that contiguous subarray and put it back.

(The rotating can be thought of as taking all the cards in the given subarray and rotating all of them for 180 degrees. This means that the first and last card swap places, as well as the second and the second to last card, and so on.)

Like all of us, Domagoj is very fond of fixed points. In other words, cards whose numbers match their position in hand, counting from Domagoj's left side. Therefore, he'd like the number of fixed points to be as great as possible after rotating the given subarray.

Help Domagoj find out which contiguous subarray he needs to point out so that the number of fixed points in Mate's hand after rotating that subarray is maximal.

inputFormat:
 The first line of input contains the positive integer $N (1 \leq N \leq 500000)$, the number of cards in Mate's hand.

 The following line contains the numbers on the cards in Mate's hand in the order that Domagoj sees them.

outputFormat:
 You must output a single line containing $A$ and
$B$, the numbers on the cards that are the beginning and the end of the required contiguous subarray, in that order. If there are multiple options, output any of them.

translation:
有一个长为 $N(N\leq 5\times 10^5)$ 的排列 $a$，其价值定义为 $\sum\limits_{i=1}^N [a_i=i]$。即，排列中满足 $a_i = i$  的 $i(1\leq i \leq n)$ 的个数。

你可以反转某一段区间，求一次操作之后最大的价值。反转指的是将序列前后颠倒，例如反转 `3 2 1 4` 会得到 `4 1 2 3`。

注意，你需要输出的**并不是**最大价值，而是满足操作之后可以取到最大价值的**反转区间的左右端点上原序列中的值**。例如样例 1 中，反转 $[1,3]$ 是最优解，而应当输出原序列中的反转区间的端点下标对应的值 $a_1=3$ 以及 $a_3=1$。

可能有多组解，你可以输出任意一组。

hint:
In the first test case, after rotating the contiguous subarray that starts with 3 and ends with 1, the cards will be ordered 1 2 3 4, and now all the cards are fixed points. In this example, the given output is the only correct output.

 In the second test case, rotating any subarray consisting of only one card results with the same card order, the one that produces the maximal number of fixed points.


title: [COCI 2017-2018#2] San

background:
搬运自 [COCI 2017/2018 Contest #2](https://hsin.hr/coci/archive/2017_2018/) T4「San」，[原题题面](https://hsin.hr/coci/archive/2017_2018/contest2_tasks.pdf)。

根据原题，时间限制 1 秒，空间限制 64 MB，满分 120 分。

description:
Have you ever dreamt that you were the main character in a computer game? The protagonist of this story, Branimir, is having that dream right now.

The world in Branimir's dream consists of $N$ skyscrapers ordered from left to right. For the $i^{th}$ skyscraper, we know the height $H_i$ and the number of gold coins $G_i$ on the roof of the skyscraper. The game begins with a jump on any of the skyscrapers and consists of several steps. In each step, Branimir can jump on a skyscraper to the right from the one he's currently on (it is possible for him to jump over a couple of them too) and if it is not lower than the current one. On each skyscraper roof he's on, Branimir will collect all the gold coins. Branimir can end the game after any number of steps (zero as well), but he must collect at least $K$ gold coins in order to advance to the next level.

Branimir wants to know the number of different ways for him to play the game in order to advance to the next level. Two games are played in different ways if there is a skyscraper that was visited in one game, and not in the other.

inputFormat:
The first line of input contains positive integers $N(1\leq N \leq 40)$ and $K(1\leq K\leq 4\times 10^{10}$), the numbers from the task.

The $i^{th}$ of the following
$N$ lines contains two positive integers, $H_i$ and $G_i(1\leq H_i,G_i \leq 10^9$), the numbers from the task.

outputFormat: You must output the number of different ways to play the game from the task.

translation:
有 $N$ 栋楼从左到右排列，第 $i$ 栋楼的高度为 $H_i$，楼上有 $G_i$ 个金币。

玩家可以从任意一个楼开始，每一步可以从当前位置向右跳到任意不低于当前楼的高度的楼上。然后可以获得每栋楼上的金币。

玩家可以一直跳，并且随时结束游戏，但是要保证获得的金币数 $\geq K$。

现在想知道共有多少不同的方案。

---
输入格式：

第一行输入 $N,K$。

接下来 $N$ 行，每行两个整数，表示 $H_i,G_i$。

---
对于 $40\%$ 的数据，有 $N\leq 20$。

hint:
#### Explanation for Sample Output 1

The following three games will take Branimir to the next level (the numbers represent the labels of the skyscrapers he visited): {1, 2, 3}, {1, 4} and {4}.

#### Scoring

In test cases worth 40% of total points, it will hold
$N\leq 20$.


title: [COTS/CETS 2021] 菜 Jelo

background:
译自 [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D1T1。$\texttt{1s,0.5G}$。

由于本题特殊的 SPJ，将本题的 TL 和 ML 分别改为 $\texttt{10s,2G}$。但是对于选手程序，本题的时空限制和原题相同。

如果使用压缩包上传答案：将文件分别命名为 $\texttt{jelo-1.out}\sim \texttt{jelo-5.out}$。

description:
给定正偶数 $N$。构造一个最大的集合 $S\subseteq \{0,1,\cdots,2^{N}-1\}$，使得 $\left|\bigcup_{i,j\in S,i\lt j} \{i\oplus j\}\right|={|S|\choose 2}$ 。换言之，在 $S$ 中任意选定 $(a,b),(c,d)$（$a,b,c,d\in S$，$a\lt b$，$c\lt d$，$(a,b)\neq (c,d)$），都有 $a\oplus b\neq c\oplus d$ 成立。

其中 $\oplus$ 表示按位异或运算。

inputFormat: 一行一个正整数 $N$。

outputFormat:
第一行一个整数 $|S|$。

接下来 $|S|$ 个数描述 $S$。


title: [COTS/CETS 2021] 虫 Kukac

background:
译自 [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D1T2。$\texttt{3s,0.5G}$。

众所周知，昆虫只对顺逆时针方向有感觉。

由于没有 std，**不保证 SPJ 正确性**。如果怀疑 SPJ 有误，请联系搬题人。[SPJ 代码](https://www.luogu.com.cn/paste/94gufjh7)。

description:
**这是一道交互题。**

二维平面上有一个 $N$ 个点的多边形 $P$。注意 $P$ **不一定**是凸的（它可以是凹包）。我们将多边形上的点**依次**编号为 $1\sim N$。

此外，还有一个额外的点 $0$。试通过交互来确定它是否在 $P$ 内部。

**保证多边形的线段不交。保证这 $(N+1)$ 个点两两不同。保证无三点共线。**

定义：$A,B,C$ **逆时针排列**当且仅当从 $A$ 看向 $B$ 时，$C$ 在直线 $AB$ 左侧。如左图。

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

【实现细节】

交互开始前，需要读入一行两个整数 $N,Q$，表示多边形点数，和允许的最大询问数。

接下来，你的程序通过标准输入输出流与交互库交互。以下是允许的询问：

- $\texttt{? a b c}$：询问点 $a,b,c$ 是否逆时针排列。必须保证 $a,b,c$ 两两不同，且 $0\le a,b,c\le N$。

    如果 $a,b,c$ 逆时针排列，回答为 $1$；否则回答为 $0$。

确定答案后，按照以下格式回答：

- $\texttt{! x}$：如果 $x=1$，则代表 $0$ 号点在多边形内部；$x=0$ 代表 $0$ 号点不在多边形内部。

每次输出后，别忘了刷新缓冲区。如：`std::cout.flush()`。

inputFormat: 见【实现细节】。

outputFormat: 见【实现细节】。


title: 【MX-X5-T4】「GFOI Round 1」epitaxy

background: > [epitaxy - かめりあ](https://music.163.com/#/song?id=2600753558)

description:
给你两个正整数 $n, m$。

定义一个 $1 \sim n$ 的排列 $p$ 的**价值**为所有的 $n - m + 1$ 个长度为 $m$ 的连续子串内最大值的最大公因数。
（规定单个数的最大公因数为其自身。）

请你求出一个在所有 $1 \sim n$ 的排列中价值最大的排列，如果有多个，求出任意一个均可。

本题将使用**自定义校验器**检查你构造的排列是否正确，即输出任意一个价值最大的排列都会被认为通过。

inputFormat:
**本题有多组测试数据。**

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

对于每组测试数据：

第一行包含两个正整数 $n, m$。

outputFormat:
对于每组数据，输出一行 $n$ 个正整数，表示符合要求的排列 $p_1, p_2, \ldots, p_n$。

本题将使用**自定义校验器**检查你构造的排列是否正确，即输出任意一个价值最大的排列都会被认为通过。


title: 【MX-J3-T0】37

description: 输入自然数 $a$，判断 $37\times a$ 是否各个数位都相等。

inputFormat: 输入含一行一个自然数 $a$。

outputFormat: 如果 $37a$ 各个数位都相等，则输出 `Yes`，否则输出 `No`。

hint:
**【样例解释 #1】**

$37\times 6 = 222$，其三个数位都是 $2$，符合题意。

**【样例解释 #2】**

$37\times 33 = 1221$，有的数位不相等（如千位和百位），不符合题意。

**【数据范围】**

本题共 $20$ 个测试点，每个 $5$ 分。

保证 $0\le a \le 3737$。


title: 【MX-X3-T0】「RiOI-4」宾果游戏

background:
第**五**市。第**五**音。

在一个似乎处处都是「**五**」的世界。

如果，能再次将时序绚乱的**五**人连成**一线**的话——

那就会是将自己带出黑暗的**一线**阳光吧。

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

（图片来自[妄想症：Deliver Me](https://store.steampowered.com/app/779640/Deliver_Me/)，侵删。）

description:
有一个 $5$ 行 $5$ 列的棋盘，棋盘上的 $25$ 个格子可能有棋子也可能没有。

有如下图左侧所示的 $12$ 条线，我们称一个棋盘是**宾果的**当且仅当**至少**有一条线上的每个格子都有棋子。试判断给定的棋盘是否是宾果的。下图右侧给出了一些示例。（深色表示有棋子，浅色表示没有）

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

你可以前往[这个链接](https://www.desmos.com/calculator/zq45krhafo?lang=zh-CN)来自己测试不同的情况。

inputFormat: 共 $5$ 行，每行 $5$ 个数，如果第 $i$ 行第 $j$ 列有棋子，则第 $i$ 行第 $j$ 个数为 $1$，否则第 $i$ 行第 $j$ 个数为 $0$。

outputFormat: 如果有至少一条线上有 $5$ 个棋子，输出 `Yes`，否则输出 `No`。

hint:
**【样例解释 #1】**

这个样例给出的棋盘是图中左上角的棋盘，它不是宾果的。

**【样例解释 #3】**

这个样例给出的棋盘是图中左下角的棋盘，它是宾果的。

**【数据范围】**

对于 $100\%$ 的数据，保证输入的数都是 $0$ 或 $1$。


title: [蓝桥杯 2024 国 B] 合法密码

description:
小蓝正在开发自己的 OJ 网站。他要求网站用户的密码必须符合以下条件：

1. 长度大于等于 $8$ 个字符，小于等于 $16$ 个字符。
2. 必须包含至少 $1$ 个数字字符和至少 $1$ 个符号字符。

例如 `lanqiao2024!`、`+-*/0601`、`8((>w<))8` 都是合法的密码。

而 `12345678`、`##**##**`、`abc0!#`、`lanqiao20240601!?` 都不是合法的密码。

请你计算以下的字符串中，有多少个子串可以当作合法密码？只要两个子串的开头字符和末尾字符在原串中的位置不同，就算作不同的子串。

字符串为：

```plain
kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th
```

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


title: [蓝桥杯 2024 国 B] 选数概率

description:
一个数组中有 $a$ 个 $1$，$b$ 个 $2$，$c$ 个 $3$。设 $P_{i,j}$ 表示在数组中随机选取两个数，其中一个数为 $i$，另一个数为 $j$ 的概率。比如 $P_{1,2} = \dfrac{ab}{C(a+b+c,2)}$，其中 $C(N, M)$ 为组合数，表示从 $N$ 个不同元素中任取 $M$ 个的方案数。

当 $a=\text{?},b=\text{?},c=\text{?}$ 时，满足 $P_{1,2}=\dfrac{517}{2091},P_{2,3}=\dfrac{2632}{10455},P_{1,3}=\dfrac{308}{2091}$，且 $a + b + c$ 最小。保证 $a + b + c$ 最小的解是唯一的。

你需要提交一个格式为 $a,b,c$ 的字符串。例如假设你计算的结果是 $a =12, b = 34, c = 56$，那么你需要提交的字符串是 `12,34,56`。

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


title: [蓝桥杯 2024 国 B] 蚂蚁开会

description:
二维平面上有 $n$ 只蚂蚁，每只蚂蚁有一条线段作为活动范围，第 $i$ 只蚂蚁的活动范围的两个端点为 $(u_i^
x,u_i^y), (v_i^x,v_i^y)$。现在蚂蚁们考虑在这些线段的交点处设置会议中心。为了尽可能节省经费，它们决定只在所有交点为整点的地方设置会议中心，请问需要设置多少个会议中心？

inputFormat:
输入共 $n + 1$ 行。

第一行为一个正整数 $n$。

后面 $n$ 行，每行 $4$ 个由空格分开的整数表示 $u_i^x, u_i^y,v_i^x,v_i^y$。

outputFormat: 输出共 $1$ 行，一个整数表示答案。

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

所有线段之间共有 $3$ 个不同的交点：$(0, 4), (\frac{4}{3}, \frac{4}{3}), (2, 2)$, 其中整点有 $2$ 个：$(0, 4), (2, 2)$。

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

对于 $20\%$ 的评测用例，保证 $0 \le u_i^x, u_i^y, v_i^x, v_i^y\le 100$。
对于 $100\%$ 的评测用例，保证 $n \le 500$，$0 \le u_i^x, u_i^y, v_i^x, v_i^y \le 10000$，保证任意蚂蚁的活动范围不会退化成一个点，**不保证**任意两条线段之间交点数量有限。


title: [蓝桥杯 2024 国 B] 立定跳远

description:
在运动会上，小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时，小明可以自行再增加 $m$ 个检查点让自己跳得更轻松。

在运动会前，小明制定训练计划让自己单次跳跃的最远距离达到 $L$，并且学会一个爆发技能可以在运动会时使用一次，使用时可以在该次跳跃时的最远距离变为 $2L$。小明想知道，$L$ 的最小值是多少可以完成这个项目？

inputFormat:
输入共 $2$ 行。

第一行为两个正整数 $n,m$。

第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \cdots, a_n$。

outputFormat: 输出共 $1$ 行，一个整数表示答案。


title: [蓝桥杯 2024 国 B] 最小字符串

description:
给定一个长度为 $N$ 且只包含小写字母的字符串 $S$，和 $M$ 个小写字母 $c_1, c_2, \cdots, c_M$。现在你要把 $M$ 个小写字母全部插入到字符串 $S$ 中，每个小写字母都可以插入到任意位置。

请问能得到的字典序最小的字符串是什么？

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

第二行包含一个长度为 $N$ 的字符串 $S$。
第三行包含 $M$ 个小写字母 $c_1, c_2, \cdots, c_M$。

outputFormat: 输出一个长度为 $N + M$ 的字符串代表答案。

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

对于 $20\%$ 的评测用例，$M = 1$。
对于 $100\%$ 的评测用例，$1 \le N, M \le 10^5$。


title: [蓝桥杯 2024 国 B] 数位翻转

description:
小明创造了一个函数 $f(x)$ 用来翻转 $x$ 的二进制的数位（无前导 $0$）。比如 $f (11) = 13$，因为 $11 = (1011)_2$，将其左右翻转后，变为 $13 = (1101)_2$；再比如 $f (3) = 3$，$f (0) = 0$，$f (2) = f (4) = f (8) = 1$ 等等。

小明随机出了一个长度为 $n$ 的整数数组 $\{a_1, a_2,\cdots, a_n\}$，他想知道，在这个数组中选择最多 $m$ 个不相交的区间，将这些区间内的数进行二进制数位翻转（将
$a_i$ 变为 $f (a_i)$）后，整个数组的和最大是多少？

inputFormat:
输入共 $2$ 行。

第一行为两个正整数 $n,m$。

第二行为 $n$ 个由空格分开的整数 $a_1, a_2, \cdots, a_n$。

outputFormat: 输出共 $1$ 行，一个整数表示答案。


title: 【MX-J3-T3+】Tuple+

description: 你有 $m$ 个三元组 $(u_i,v_i,w_i)$，保证 $1\le u_i<v_i<w_i\le n$ 且三元组两两不同。有多少组 $(a,b,c,d)$ 满足 $1\le a<b<c<d\le n$，且在这 $m$ 个三元组当中，存在四个三元组 $(a,b,c),(a,b,d),(a,c,d),(b,c,d)$？

inputFormat:
输入的第一行有两个正整数 $n,m$ 表示三元组数字范围和三元组个数。

之后 $m$ 行，每行一组 $u_i,v_i,w_i$ 表示一个三元组。

outputFormat: 输出一行一个自然数表示答案。


title: [蓝桥杯 2024 国 B] 数星星

description:
小明正在一棵树上数星星，这棵树有 $n$ 个结点 $1, 2,\cdots, n$。他定义树上的一个子图 $G$ 是一颗星星，当且仅当 $G$ 同时满足：

1. $G$ 是一棵树。
2. $G$ 中存在某个结点，其度数为 $|V_G| - 1$。其中 $|V_G|$ 表示这个子图含有的结点数。

两颗星星不相同当且仅当它们包含的结点集合 $V_G$ 不完全相同。小明想知道这棵树上有多少颗不同的星星包含的结点的数量在区间 $[L, R]$ 中，答案对 $1000000007$ 取模。

inputFormat:
输入共 $n + 1$ 行。

第一行为一个正整数 $n$。

后面 $n - 1$ 行，每行两个正整数表示树上的一条边。

第 $n + 1$ 行，两个正整数 $L, R$。

outputFormat: 输出共 $1$ 行，一个整数表示答案。


title: [蓝桥杯 2024 国 B] 套手镯

description:
小蓝在 LQ 集市上发现一个套手镯的游戏，在一个大小为 $10^8 \times 10^8$ 矩形平面上摆放着 $N$ 个圆形的手镯。玩家可以将一个大小为 $w \times h$ 的矩形方框放置在这个平面上（玩家只可以沿着水平/垂直方向放置方框，即可以将方框旋转 $90$ 度，但不可以旋转至其他角度），位于这个矩形方框内部的手镯就是玩家获得的奖励。

可以将这个矩形平面看作是一个二维坐标系，左下角的坐标为  $(0, 0)$。手镯和方框的厚度可以忽略不计, 允许多个手镯重叠放置。

小蓝想要尝试一次，请问他最多可以获得多少手镯？

inputFormat:
第一行输入三个整数 $N$、$w$、$h$。

接下来输入 $N$ 行，每行三个整数 $x, y, r$，表示第 $i$ 个手镯的圆心坐标和半径。

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

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

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

上图展示了一种可能的答案。

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

对于 $50\%$ 的评测用例：$1 \le N \le 100$，$1 \le w, h, x, y, r \le 200$。
对于 $100\%$ 的评测用例：$1 \le N \le 1000$，$1 \le w, h, x, y, r \le 10^8$，$1 \le \min\{w, h\} \le 200$。保证所有手镯都位于平面内部。


title: [蓝桥杯 2024 国 B] 跳石头

description:
小明正在和朋友们玩跳石头的小游戏，一共有 $n$ 块石头按 $1$ 到 $n$ 顺序排成一排，第 $i$ 块石头上写有正整数权值 $c_i$。

如果某一时刻小明在第 $j$ 块石头，那么他可以选择跳向第 $j + c_j$ 块石头（前提 $j + c_j \le n$）或者跳向第 $2j$ 块石头（前提 $2j \le n$），没有可跳跃的目标时游戏结束。

假如小明选择从第 $x$ 块石头开始跳跃，如果某块石头**有可能**被小明经过（“经过” 指存在某一时刻小明在这个石头处），则将这块石头的权值纳入得分集合 $S_x$，那么小明从第 $x$ 块石头开始跳跃的得分为 $|S_x|$。

比如如果小明从第 $x$ 块石头出发，所有可能经过的石头上的权值分别为 $5,3,5,2, 3$，那么 $S_x = \{5, 3, 2\}$ 得分为 $|S_x| = 3$。小明可以任选一块石头开始跳跃，请求出小明最多能获得的分数。

inputFormat:
输入共 $2$ 行。

第一行为一个正整数 $n$。

第二行为 $n$ 个由空格分开的正整数 $c_1, c_2,\cdots, c_n$。

outputFormat: 输出共 $1$ 行，一个整数表示答案。

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

从第一块石头出发得分最多，路径有以下几种：

1. $1$ 号 $\to 5$ 号：选择从 $1$ 号跳到 $1 + c_1=5$ 号。
2. $1$ 号 $\to 2$ 号 $\to 5$ 号：第一次选择从 $1$ 号跳到 $2 \times 1=2$ 号，第二次选择从 $2$ 号跳到 $2 + c_2 = 5$ 号。
3. $1$ 号 $\to 2$ 号 $\to 4$ 号：第一次选择从 $1$ 号跳到 $2 \times 1=2$ 号，第二次选择从 $2$ 号跳到 $2 \times 2 = 4$ 号。

所以所有可能经过的石头的权值的集合为 $S_1 = \{c_1, c_2, c_4, c_5\} = \{4, 3, 2, 1\}$，得分为 $|S_1| = 4$。

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

对于 $20\%$ 的评测用例，保证 $n \le 20$。
对于 $100\%$ 的评测用例，保证 $n \le 40000$，$c_i \le n$。


title: 「KDOI-10」反回文串

background:
[English Statement](https://www.luogu.com.cn/problem/T519008). You must submit your code at the Chinese version of the statement.

**本场比赛所有题目从标准输入读入数据，输出到标准输出。**

description:
我们称一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i=r_{m+1-i}$ 对所有 $1\le i\le m$ 均成立。

给定一个长度为 $n$ 的字符串 $s$，你需要把 $s$ 分成若干个非空子序列，使得每一个子序列都**不是**回文的，并最大化划分成的子序列数。

形式化地说，你需要给出一组序列 $(a_1,a_2,\ldots,a_k)$，满足：

- 对于任意 $1\le i\le k$，记 $l_i$ 为 $a_i$ 的长度，则 $l_i\ge 1$，且 $1\le a_{i,1}<a_{i,2}<\cdots<a_{i,l_i}\le n$；
- 对于任意 $1\le i\le n$，恰好存在一个二元组 $(p,q)$，使得 $a_{p,q}=i$；
- 对于任意 $1\le i\le k$，记字符串 $t=s_{a_{i,1}}s_{a_{i,2}}\ldots s_{a_{i,l_i}}$，则 $t$ 不是回文的。

在此基础上，你需要最大化 $k$ 的值；或者判断不存在一种合法的方案。

特别地，如果 $k$ 的值不是最大的，你也可能获得一定的部分分。

inputFormat:
从标准输入读入数据。

**本题有多组测试数据。**

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $q$，表示测试数据组数。

对于每组测试数据：

- 第一行包含一个正整数 $n$，表示字符串 $s$ 的长度；
- 第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 中仅包含小写英文字母。

outputFormat:
输出到标准输出。

对于每组测试数据：

- 如果不存在一种合法的方案，输出一行一个字符串 `Shuiniao`；
- 否则，你需要：
  - 在第一行输出一个字符串 `Huoyu`；
  - 第二行输出一个正整数 $k$ $(1\le k\le n)$，表示你划分成的子序列个数；
  - 接下来 $k$ 行，对于第 $i$ 行 $(1\le i\le k)$：
    - 首先输出一个正整数 $l_i$ $(1\le l_i\le n)$，表示第 $i$ 个子序列的长度；
    - 接下来输出 $l_i$ 个正整数 $a_{i,1},a_{i,2},\ldots, a_{i,l_i}$ $(1\le a_{i,j}\le n)$，表示第 $i$ 个子序列。

请注意，你的输出需要满足题目描述中所有的限制，否则，你将会得到 $0$ 分。

samples:
0
4
4
kdoi
7
ccccccc
7
sszcdjr
7
abacaca

hint:
**【样例 1 解释】**

对于第一组测试数据，显然输出构成一个合法的子序列划分，并且

- 对于第一个子序列，$t=\tt{kd}$ 不是回文的；
- 对于第二个子序列，$t=\tt{oi}$ 不是回文的。

故这是一组合法的输出。可以证明，对于这组测试数据，$2$ 是 $k$ 的最大可能值。

对于第二组数据，它的任意一个子序列都是回文的， 故显然不存在合法的划分方案。

**【样例 2】**

见选手目录下的 `anti/anti2.in` 与 `anti/anti2.ans`。

这个样例共有 $10$ 组数据，均满足 $n=1\,000$。其中第 $1\sim 3$ 组数据满足特殊性质 A，第 $4\sim 6$ 组数据满足特殊性质 B。

***

**【评分方式】**

本题共有 $20$ 个测试点，每个测试点满分 $5$ 分。

本题采用自定义校验器（special judge）评测。每组测试数据可能有多组解，你只需要给出**任意**一组。

在每个测试点中，你的得分是在所有测试数据上得分的最小值。对于每组测试数据：

- 如果你错误地判断了是否有解或者给出了一组不合法的序列，你将会获得 $0$ 分；
- 如果你正确判断了是否有解，并在有解时给出了一组合法的序列：
  - 如果 $k$ 的值不是最大的，你将会获得 $2$ 分；
  - 如果 $k$ 的值是最大的，你将会获得 $5$ 分。

***

**【数据范围】**

对于全部的测试数据，保证：

- $1\le q\le 10$；
- $1\le n\le 10^5$；
- $s$ 中仅包含小写英文字母。

|测试点|$n\le$|特殊性质|
|:--:|:--:|:--:|
|$1,2$|$5$|无|
|$3\sim 5$|$18$|无|
|$6\sim 8$|$1\,000$|B|
|$9\sim 11$|$1\,000$|无|
|$12\sim 14$|$10^5$|A|
|$15\sim 17$|$10^5$|B|
|$18\sim 20$|$10^5$|无|

- 特殊性质 A：保证 $n$ 是偶数，且 $s$ 中每个字符的出现次数都不超过 $\frac{n}{2}$；
- 特殊性质 B：保证 $s$ 中仅有 `a` 和 `b`。

***

**【如何使用校验器】**

为了方便选手测试，在附件的 `anti` 目录下我们下发了 `checker.cpp` 文件作为样例校验器，选手可以编译该程序，并使用它校验自己的输出文件的结果是否**合法**。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为：

```sh
g++ -o checker -std=c++14 -O2 checker.cpp
```

`checker` 的使用方式为：

```sh
checker <input-file> <output-file>
```

其中，参数 ` <input-file>` 与 `<output-file>` 依次表示输入文件与你的输出文件。

若你的输出中的数字大小范围不合法，则校验器会给出相应提示并立即退出。否则，校验器输出以下内容：

- 在第 $i$ 行 $(1\le i\le q)$ 中，输出第 $i$ 组测试数据的详细提示信息；
- 在第 $(q+1)$ 行，输出这个测试点的总结信息。

例如，对于样例 1 的输入与输出，校验器将会向屏幕打印如下内容：

```plain
Test case 1: OK. Participant's answer is YES (Huoyu), and k=2.
Test case 2: OK. Participant's answer is NO (Shuiniao).
Test case 3: OK. Participant's answer is YES (Huoyu), and k=3.
Test case 4: OK. Participant's answer is YES (Huoyu), and k=3.
ok 4 / 4 test cases passed. (4 test cases)
```

若将输出改为如下：

```plain
Huoyu
2
2 1 2
2 3 4
Huoyu
1
7 1 2 3 4 5 6 7
Huoyu
3
3 1 2 3
2 4 5
2 6 7
Huoyu
3
2 1 4
3 2 3 5
2 6 7
```

则会向屏幕打印如下内容：

```plain
Test case 1: OK. Participant's answer is YES (Huoyu), and k=2.
Test case 2: Wrong answer. The string t obtained in the subsequence a[1] is palindrome.
Test case 3: OK. Participant's answer is YES (Huoyu), and k=3.
Test case 4: OK. Participant's answer is YES (Huoyu), and k=3.
wrong answer 3 / 4 test cases passed.
```

**请注意：** 样例校验器只会检查你的输出是否合法，而**不会**：

- 检查有解性是否判断正确；
- 检查 $k$ 是否被最大化。

例如，将样例 1 的输出改为如下：

```plain
Shuiniao
Shuiniao
Shuiniao
Shuiniao
```

此时，样例校验器仍会返回 `ok` 的检查结果。


title: [蓝桥杯 2024 国 B] 最长回文前后缀

description:
小明特别喜欢回文串，然而回文串太少见了，因此他定义了一个字符串的相同长度的、不相交的前缀和后缀是“回文前后缀”，当且仅当这个前缀和后缀拼起来是个回文串。那么字符串 $S=c_1c_2c_3,\cdots,c_n$ 的“最长回文前后缀” 的长度 $L(S)$ 即为 $\argmax\limits_{x}{S_{[1,x]} = (S_{[n-x+1,n]})^T}$ 其中 $S_{[i,j]}$ 表示 $S$ 的一个子串 $c_ic_{i+1}\cdots c_j$，$S^T$ 表示翻转 $S$ 得到的字符串。

对于一个给定的字符串 $S$，小明希望对其进行改造使得 $L(S ^\prime)$ 尽可能大。改造允许将字符串中一个任意长度的子串删除。比如删除 $S = \texttt{abcdebijbba}$ 中
的子串 $S_[3,5]$ 后 $S$ 变成了 $\texttt{abbijbba}$。

小明想知道改造后的新字符串 $S^\prime$ 的“最长回文前后缀”的长度 $L(S^\prime)$ 最大是多少？

inputFormat: 输入共 $1$ 行，一个字符串 $S$。

outputFormat: 输出共 $1$ 行，一个整数表示答案。

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

如题干中的方案删除 $S_{[3,5]}$ 后，$S^\prime = \texttt{abbijbba}$，$L(S^\prime) = 3$。

**【评测用例规模与约定】**
对于 $20\%$ 的评测用例，保证 $|S| \le 500$。
对于 $100\%$ 的评测用例，保证 $|S| \le 500000$，$S$ 仅包含小写字母。


title: [蓝桥杯 2023 国 Python A] 跑步计划

description:
小蓝计划在某天的日期中出现 $1$ 时跑 $5$ 千米，否则只跑 $1$ 千米。注意日期中出现 $1$ 不仅指年月日也指星期。

请问按照小蓝的计划，$2023$ 年小蓝总共会跑步锻炼多少千米？

例如，$5$ 月 $1$ 日、$1$ 月 $13$ 日、$11$ 月 $5$ 日、$4$ 月 $3$ 日（星期一）小蓝会跑 $5$ 千米，而 $5$ 月 $23$ 日小蓝会跑 $1$ 千米。

（示例日期均为 $2023$ 年）

inputFormat: 无。

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


title: [蓝桥杯 2024 省 Java B] 报数游戏

description:
小蓝和朋友们在玩一个报数游戏。由于今年是 $2024$ 年，他们决定要从小到大轮流报出是 $20$ 或 $24$ 倍数的正整数。前 $10$ 个被报出的数是：$20,24,40,48,60,72,80,96,100,120$。请问第 $202420242024$ 个被报出的数是多少？

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

inputFormat: 本题无输入。

outputFormat: 一行一个整数，表示你算出的答案。


title: [蓝桥杯 2023 国 Python A] 残缺的数字

description:
七段码显示器是一种常见的显示数字的电子元件，它有七个发光管组成：

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

上图依次展示了数字 $0\sim 9$ 用七段码来显示的状态，其中灯管为黄色表示点亮，灰色表示熄灭。根据灯管的亮暗状态，我们可以用一个状态码（状态码是一个 $7$ 位的二进制数字）来表示一个七段码，令灯管点亮时状态为 $1$，灯管熄灭时状态为 $0$，按照灯管 $\rm ABCDEFG$ 的顺序标识一个七段码，则数字 $0 \sim 9$ 的状态码为：

|数字|状态码|数字|状态码|
|:-:|:-:|:-:|:-:|
|$0$|$1111110$|$5$|$1011011$|
|$1$|$0110000$|$6$|$1011111$|
|$2$|$1101101$|$7$|$1110000$|
|$3$|$1111001$|$8$|$1111111$|
|$4$|$0110011$|$9$|$1111011$|

小蓝有一个喜爱的数字，长度为 $18$ 位，每一位用一个七段码显示器来展示
（每位只能是 $0 \sim 9$，可以包含前导零），由于灯管故障，一些本该点亮的灯管
处于了熄灭状态。例如，对于一个长度为 $2$ 的数字来说，当两个七段码对应的
状态码分别为：$1011111$（高位）、$1110011$（低位）时，原本的数字可能会是：
$68$、$69$、$88$、$89$，有 4 种可能的值。

$18$ 个七段码显示器对应的状态码分别为：

$0000011$，$1001011$，$0000001$，$0100001$，$0101011$，$0110110$，
$1111111$，$0010110$，
$0101001$，$0010110$，
$1011100$，$0100110$，
$1010000$，$0010011$，
$0001111$，$0101101$，
$0110101$，$1101010$。

其中每个表示一个七段码对应的的状态码（按照数字的高位到低位给出）。请你
判断下小蓝喜爱的数字有多少种可能的值。

outputFormat: 一行一个整数表示答案。


title: [蓝桥杯 2024 省 C] 拼正方形

description: 小蓝正在玩拼图游戏，他有 $7385137888721$ 个 $2 \times 2$ 的方块和 $10470245$ 个 $1 \times 1$ 的方块，他需要从中挑出一些来拼出一个正方形，比如用 $3$ 个 $2 \times 2$ 和 $4$ 个 $1 \times 1$ 的方块可以拼出一个 $4 \times 4$ 的正方形，用 $9$ 个 $2 \times 2$ 的方块可以拼出一个 $6 \times 6$ 的正方形，请问小蓝能拼成的最大的正方形的边长为多少。

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


title: [蓝桥杯 2024 省 Java B] 类斐波那契循环数

description:
对于一个有 $n$ 位的十进制数 $N = d_1d_2d_3\dots d_n$，可以生成一个类斐波那契数列 $S$，数列 $S$ 的前 $n$ 个数为 $\{S_1=d_1,S_2=d_2,S_3=d_3,\dots,S_n=d_n\}$，数列 $S$ 的第 $k(k>n)$ 个数为 $\sum^{k−1}_{i=k−n} S_i$。如果这个数 $N$ 会出现在对应的类斐波那契数列 $S$ 中，那么 $N$ 就是一个类斐波那契循环数。

例如对于 $197$，对应的数列 $S$ 为 $\{1, 9, 7, 17, 33, 57, 107, 197, \dots \}$，$197$ 出现在 $S$ 中，所以 $197$ 是一个类斐波那契循环数。

请问在 $0$ 至 $10^7$ 中，最大的类斐波那契循环数是多少？

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

outputFormat: 一行一个整数，表示你算出的答案。


title: [蓝桥杯 2024 省 Java B] 分布式队列

description:
小蓝最近学习了一种神奇的队列：分布式队列。简单来说，分布式队列包含 $N$ 个节点（编号为 $0$ 至 $N−1$，其中 $0$ 号为主节点），其中只有一个主节点，其余为副节点。主、副节点中都各自维护着一个队列，当往分布式队列中添加元素时都是由主节点完成的（每次都会添加元素到队列尾部）；副节点只负责同步主节点中的队列。可以认为主/副节点中的队列是一个长度无限的一维数组，下标为 $0,1,2,3,\dots$，同时副节点中的元素的同步顺序和主节点中的元素添加顺序保持一致。

由于副本的同步速度各异，因此为了保障数据的一致性，元素添加到主节点后，需要同步到所有的副节点后，才具有可见性。

给出一个分布式队列的运行状态，所有的操作都按输入顺序执行。你需要回答在某个时刻，队列中有多少个元素具有可见性。

inputFormat:
第一行包含一个整数 $N$，表示节点个数。

接下来包含多行输入，每一行包含一个操作，操作类型共有以下三个：add、sync 和 query，各自的输入格式如下：

1. `add element`：表示这是一个添加操作，将元素 $element$ 添加到队列中；

2. `sync follower_id`：表示这是一个同步操作，$follower\_id$ 号副节点会从主节点中同步下一个自己缺失的元素；

3. `query`：查询操作，询问当前分布式队列中有多少个元素具有可见性。

outputFormat: 对于每一个 query 操作，输出一行，包含一个整数表示答案。

samples:
3
add 1
add 2
query
add 1
sync 1
sync 1
sync 2
query
sync 1
query
sync 2
sync 2
sync 1
query

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

执行到第一个 query 时，队列内容如下：

- 节点 $0$：$[1,2]$
- 节点 $1$：$[]$
- 节点 $2$：$[]$

两个副节点中都无元素，因此答案为 $0$。

执行到第二个 query 时，队列内容如下：

- 节点 $0$：$[1,2,1]$
- 节点 $1$：$[1,2]$
- 节点 $2$：$[1]$

只有下标为 $0$ 的元素被所有节点同步，因此答案为 $1$。

执行到第三个 query 时，队列内容如下：

- 节点 $0$：$[1,2,1]$
- 节点 $1$：$[1,2,1]$
- 节点 $2$：$[1]$

只有下标为 $0$ 的元素被所有节点同步，因此答案为 $1$。

执行到第四个 query 时，队列内容如下：

- 节点 $0$：$[1,2,1]$
- 节点 $1$：$[1,2,1]$
- 节点 $2$：$[1,2,1]$

三个元素都被所有节点同步，因此答案为 $3$。

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

设输入的操作数为 $q$。

对于 $30\%$ 的评测用例：$1\leq q \leq 100$。

对于 $100\%$ 的评测用例：$1\leq q\leq 2000$，$1\leq N\leq 10$，$1\leq follower\_id<N$，$0\leq element\leq10^5$。

**数据保证执行同步操作时，$follower\_id$ 号副节点一定缺失元素**。


title: [蓝桥杯 2024 省 Java B] 食堂

description: S 学校里一共有 $a_2$ 个两人寝、$a_3$ 个三人寝，$a_4$ 个四人寝，而食堂里有 $b_4$ 个四人桌和 $b_6$ 个六人桌。学校想要安排学生们在食堂用餐，并且满足每个寝室里的同学都在同一桌就坐，请问这个食堂最多同时满足多少同学用餐？

inputFormat:
**本题采用多组数据输入。**

输入共 $q+1$ 行。

第一行为一个正整数 $q$ 表示数据组数。

后面 $q$ 行，每行五个非负整数 $a_2,a_3,a_4,b_4,b_6$ 表示一组数据。

outputFormat: 输出共 $q$ 行，每行一个整数表示对应输入数据的答案。

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

对于第一组数据，只有一个六人桌，因此最多安排三个两人寝的同学就餐，答案为 $(2+2+2)=6$。

对于第二组数据，用一个六人桌安排两个三人寝的同学，用一个四人桌安排一个四人寝的同学，答案为 $(3+3)+(4)=10$。

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

对于 $20\%$ 的评测用例，保证 $a_2+a_3+a_4\leq 8$。

对于 $100\%$ 的评测用例，保证 $q\leq 100$，$b_4+b_6\leq a_2+a_3+a_4\leq 100$。


title: [蓝桥杯 2024 省 Java B] 最优分组

description:
小蓝开了一家宠物店，最近有一种 X 病毒在动物之间进行传染，小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。

为了减少使用的测试剂数目，小蓝想到了一个好方法：将 $N$ 个宠物平均分为若干组，使得每组恰好有 $K$ 只宠物，这样对同一组的宠物进行采样并混合后用一个试剂进行检测，如果测试结果为阴性则说明组内宠物都未感染 X 病毒；如果是阳性的话则需要对组内所有 $K$ 只宠物单独检测，需要再消耗 $K$ 支测试剂（当 $K=1$ 时，就没必要再次进行单独检测了，因为组内只有一只宠物，一次检测便能确认答案）。

现在我们已知小蓝的宠物被感染的概率为 $p$，请问 $K$ 应该取值为多少，才能使得期望的测试剂的消耗数目最少？如果有多个答案，请输出最小的 $K$。

inputFormat:
第一行，一个整数 $N$。

第二行，一个浮点数 $p$。

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

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

对于 $30\%$ 的评测用例：$1\leq N\leq 10$。

对于 $60\%$ 的评测用例：$1\leq N\leq 1000$。

对于 $100\%$ 的评测用例：$1\leq N\leq 10^6$，$0\leq p\leq 1$。


title: [蓝桥杯 2023 国 Python A] 整数变换

background: 建议使用 PyPy3 提交本题。

description:
小蓝有一个整数 $n$。每分钟，小蓝的数都会发生变化，变为上一分钟的数
减去上一分钟的数的各个数位和。

例如，如果小蓝开始时的数为 $23$，则下一分钟变为 $23 - (2 + 3) = 18$，再下一分钟变为 $18 - (1 + 8) = 9$，再下一分钟变为 $9 - 9 = 0$，共经过了 $3$ 分钟变为 $0$。

给定一个正整数，请问这个数多少分钟后变为 $0$。

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

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

hint:
对于 $30\%$ 的评测用例，$1 \le n \le 1000$；

对于 $60\%$ 的评测用例，$1 \le n \le 10^6$；

对于所有评测用例，$1 \le n \le 10^9$。


title: [蓝桥杯 2024 省 C] 劲舞团

description:
小蓝最近迷上了一款名为“劲舞团”的游戏，具体来说，只要按照游戏中给出的键位提示依次按出对应的键位，游戏人物便可以跟随节奏跳舞。对于连续的 $K$ 次正确敲击，如果任意连续的两次敲击间间隔时间都小于等于 $1\texttt s$，那么
我们称这是一次 $K$ 连击。现在给出一局小蓝的游戏记录文件，log.txt 中记录了 $N$ 条记录，每条记录有三个字段，依次为正确的敲击字符、小蓝打出的字符、打出字符的时间对应的毫秒时间戳。现在请你计算下最长的 $K$ 连击是多少，你
只需要输出 $K$ 的值。

inputFormat: 为了方便评测，输入数据已替换为 log.txt。在洛谷评测时，你可以从标准输入读取 log.txt，也可以从下发文件中下载。

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


title: [蓝桥杯 2024 省 C] 数字诗意

description:
在诗人的眼中，数字是生活的韵律，也是诗意的表达。

小蓝，当代顶级诗人与数学家，被赋予了“数学诗人” 的美誉。他擅长将冰冷的数字与抽象的诗意相融合，并用优雅的文字将数学之美展现于纸上。

某日，小蓝静坐书桌前，目光所及，展现着 $n$ 个数字，它们依次为 $a_1, a_2, \cdots, a_n$，熠熠生辉。小蓝悟到，如果一个数能够以若干个（至少两个）**连续的正整数**相加表示，那么它就蕴含诗意。例如，数字 $6$ 就蕴含诗意，因为
它可以表示为 $1 + 2 + 3$。而 $8$ 则缺乏诗意，因为它无法用连续的正整数相加表示。

小蓝希望他面前的所有数字都蕴含诗意，为此，他决定从这 $n$ 个数字中删除一部分。请问，小蓝需要删除多少个数字，才能使剩下的数字全部蕴含诗意？

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

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔，表示展示的数字。

outputFormat: 输出一行包含一个整数，表示小蓝需要删除的数字个数，以使剩下的数字全部蕴含诗意。

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

在样例中，数字 $3$ 可以表示为 $1 + 2$，数字 $6$ 可以表示为 $1 + 2 + 3$，数字 $8$ 无法表示为连续的正整数相加，因此，需要删除的数字个数为 $1$。

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

对于 $30\%$ 的评测用例，$1 \le n \le 10^3$，$1 \le a_i \le 10^3$。
对于所有评测用例，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^{16}$。


title: [蓝桥杯 2024 省 C] 封闭图形个数

description:
在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。

封闭图形是指数字中完全封闭的空间，例如数字$1$、$2$、$3$、$5$、$7$ 都没有形成封闭图形，而数字 $0$、$4$、$6$、$9$ 分别形成了 $1$ 个封闭图形，数字 $8$ 则形成了 $2$ 个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字 $68$，由于 $6$ 形成了 $1$ 个封闭图形，而 $8$ 形成了 $2$ 个，所以 $68$ 形成的封闭图形的个数总共为 $3$。

在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 $41$ 和数字 $18$，它们对应的封闭图形的个数分别为 $1$ 和 $2$，因此数字 $41$ 小于数组 $18$。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 $14$ 和数字 $41$，它们的封闭图形的个数都是 $1$，但 $14 < 41$，所以数字 $14$ 小于数字 $41$。如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。

小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 $n$ 个数 $a_1, a_2,\cdots, a_n$，请你按照蓝桥王国的数字大小规则，将这 $n$ 数从小到大排序，并输出排序后结果。

inputFormat:
输入的第一行包含一个整数 $n$，表示给定的数字个数。

第二行包含 $n$ 个整数 $a_1, a_2,\cdots, a_n$，相邻整数之间使用一个空格分隔，表示待排序的数字。

outputFormat: 输出一行包含 $n$ 个整数，相邻整数之间使用一个空格分隔，表示按照蓝桥王国的数字大小规则从小到大排序后的结果。

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

对于给定的数字序列 $[18, 29, 6]$，数字 $18$ 的封闭图形个数为 $2$，数字 $29$ 的封闭图形个数为 $1$，数字 $6$ 的封闭图形个数为 $1$。按照封闭图形个数从小到大排序后，得到 $[29, 6, 18]$。

由于数字 $29$ 和数字 $6$ 的封闭图形个数相同，因此需要进一步按照数值大小对它们进行排序，最终得到 $[6, 29, 18]$。

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

对于 $50\%$ 的评测用例，$1\le n \le 2 \times 10^3$，$1 \le a_i \le 10^5$。
对于所有评测用例，$1 \le n\le 2 \times 10^5$，$1 \le a_i \le 10^9$。


title: [蓝桥杯 2024 省 C] 回文数组

description: 小蓝在无聊时随机生成了一个长度为 $n$ 的整数数组，数组中的第 $i$ 个数为 $a_i$，他觉得随机生成的数组不太美观，想把它变成回文数组，也是就对于任意 $i\in [1,n]$ 满足 $a_i=a_{n-i+1}$。小蓝一次操作可以指定相邻的两个数，将它们一起加 $1$ 或减 $1$；也可以只指定一个数加 $1$ 或减 $1$，请问他最少需要操作多少次能把这个数组变成回文数组？

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

第二行包含 $n$ 个整数 $a_1, a_2,\cdots, a_n$，相邻整数之间使用一个空格分隔。

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

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

第一次操作将 $a_1, a_2$ 加 $1$，变为 $2, 3, 3, 4$；

后面两次操作将 $a_1$ 加 $1$，变为 $4,3,3,4$。

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

对于 $20\%$ 的评测用例，$1 \le n \le 10$；
对于所有评测用例，$1 \le n \le 10^5$，$10^6 \le a_i \le 10^6$。


title: [蓝桥杯 2024 省 C] 商品库存管理

description:
在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 $1$ 至 $n$。初始时，每种商品的库存量均为 $0$。

为了高效地监控和调整库存量，小蓝的管理团队设计了 $m$ 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 $[L, R]$）。执行这些操作时，区间内每种商品的库存量都将增加 $1$。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 $0$。对此，请你为管理团队计算出，对于每个操作，如果不执行该操作而执行其它操作，库存量为 $0$ 的商品的种类数。

inputFormat:
输入的第一行包含两个整数 $n$ 和 $m$，分别表示商品的种类数和操作的个数。

接下来的 $m$ 行，每行包含两个整数 $L$ 和 $R$，表示一个操作涉及的商品区间。

outputFormat: 输出 $m$ 行，每行一个整数，第 $i$ 行的整数表示如果不执行第 $i$ 个操作，则最终库存量为 $0$ 的商品种类数。

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

考虑不执行每个操作时，其余操作对商品库存的综合影响：

- **不执行操作 $1$**：剩余的操作是操作 $2$（影响区间 $[2, 4]$）和操作 $3$（影响区间 $[3, 5]$）。执行这两个操作后，商品库存序列变为 $[0, 1, 2, 2, 1]$。在这种情况下，只有编号为 $1$ 的商品的库存量为 $0$。因此，库存量为 $0$ 的商品种类数为 $1$。

- **不执行操作 $2$**：剩余的操作是操作 $1$（影响区间 $[1, 2]$）和操作 $3$（影响区间 $[3, 5]$）。执行这两个操作后，商品库存序列变为 $[1, 1, 1, 1, 1]$。在这种情况下，所有商品的库存量都不为 $0$。因此，库存量为 $0$ 的商品种类数为 $0$。

- **不执行操作 $3$**：剩余的操作是操作 $1$（影响区间 $[1, 2]$）和操作 $2$（影响区间 $[2, 4]$）。执行这两个操作后，商品库存序列变为 $[1, 2, 1, 1, 0]$。在这种情况下，只有编号为 $5$ 的商品的库存量为 $0$。因此，库存量为 $0$ 的商品种类数为 $1$。

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

对于 $20\%$ 的评测用例，$1 \le n,m \le 5 \times 10^3$，$1\le L \le R \le n$。
对于所有评测用例，$1 \le n,m \le 3 \times 10^5$，$1 \le L \le R \le n$。


title: [蓝桥杯 2024 省 C] 挖矿

description:
小蓝正在数轴上挖矿，数轴上一共有 $n$ 个矿洞，第 $i$ 个矿洞的坐标为 $a_i$。小蓝从 $0$ 出发，每次可以向左或向右移动 $1$ 的距离，当路过一个矿洞时，就会进行挖矿作业，获得 $1$ 单位矿石，但一个矿洞不能被多次挖掘。小蓝想知道在
移动距离不超过 $m$ 的前提下，最多能获得多少单位矿石？

inputFormat:
输入的第一行包含两个正整数 $n,m$，用一个空格分隔。

第二行包含 $n$ 个整数 $a_1, a_2,\cdots, a_n$，相邻整数之间使用一个空格分隔。

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

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

路径：$0\to -1\to 0\to 1\to 2$，可以对 $\{0,-1,1,2\}$ 四个矿洞挖掘并获得最多 $4$ 块矿石。

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

对于 $20\%$ 的评测用例，$1 \le n \le 10^3$；
对于所有评测用例，$1 \le n \le 10^5$，$-10^6 \le a_i \le 10^6$，$1 \le m \le 2 \times 10^6$。


title: [蓝桥杯 2024 省 Python B] 连连看

description: 小蓝正在和朋友们玩一种新的连连看游戏。在一个 $n \times m$ 的矩形网格中，每个格子中都有一个整数，第 $i$ 行第 $j$ 列上的整数为 $A_{i,j}$。玩家需要在这个网格中寻找一对格子 $(a,b)$ 和 $(c,d)$ 使得这两个格子中的整数 $A_{a,b}$ 和 $A_{c,d}$ 相等，且它们的位置满足 $|a-c| = |b-d| > 0$。请问在这个 $n \times m$ 的矩形网格中有多少对这样的格子满足条件。

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $m$，用一个空格分隔。

接下来是 $n$ 行，第 $i$ 行包含 $m$ 个正整数 $A_{i,1}, A_{i,2}, \dots, A_{i,m}$，相邻整数之间用一个空格分隔。

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


title: [蓝桥杯 2024 省 C] 回文字符串

description: 小蓝最近迷上了回文字符串，他有一个只包含小写字母的字符串 $S$，小蓝可以往字符串 $S$ 的开头处加入任意数目个指定字符：`l`、`q`、`b`（ASCII 码分别为：$108$、$113$、$98$）。小蓝想要知道他是否能通过这种方式把字符串 $S$ 转化为一个回文字符串。

inputFormat:
输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每组数据一行包含一个字符串 $S$。

outputFormat: 输出 $T$ 行，每行包含一个字符串，依次表示每组数据的答案。如果可以将 $S$ 转化为一个回文字符串输出 `Yes`，否则输出 `No`。

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

对于 `gmgqlq`，可以在前面加上 `qlq` => `qlqgmgqlq` 转化为一个回文字符串；

对于 `pdlbll`，无法转化为一个回文字符串；

对于 `aaa`，本身就是一个回文字符串。

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

对于 $50\%$ 的评测用例，$1 \le |S| \le 1000$，其中 $|S_j|$ 表示字符串 $S$ 的长度；
对于所有评测用例，$1 \le T \le 10$，$1 \le \sum |S| \le 10^6$。


title: [蓝桥杯 2023 国 Python A] 2023

background: 建议使用 PyPy3 提交本题。

description:
给定 $n, m$，请求出所有 $n$ 位十进制整数中有多少个数中恰好出现了 $m$ 个 $2023$。

例如 $00202312023$ 是一个 $11$ 位的出现了 $2$ 个 $2023$ 的十进制整数。

由于结果可能很大，请输出答案对 $998,244,353$ 取模的结果。

inputFormat: 输入一行包含两个整数 $n,m$，用一个空格分隔。

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

hint:
对于 $40\%$ 的评测用例，$n \le 10^5,m \le 10$；

对于所有评测用例，$4 \le n \le 10^5,0 \le 4m \le n$。


title: [蓝桥杯 2024 省 Python B] 神奇闹钟

description:
小蓝发现了一个神奇的闹钟，从纪元时间（$1970$ 年 $1$ 月 $1$ 日 $00:00:00$）开始，每经过 $x$ 分钟，这个闹钟便会触发一次闹铃（纪元时间也会响铃）。这引起了小蓝的兴趣，他想要好好研究下这个闹钟。

对于给出的任意一个格式为 `yyyy-MM-dd HH:mm:ss` 的时间，小蓝想要知道在这个时间点之前（包含这个时间点）的最近的一次闹铃时间是哪个时间？

注意，你不必考虑时区问题。

inputFormat:
输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每组数据一行，包含一个时间（格式为 `yyyy-MM-dd HH:mm:ss`）和一
个整数 $x$，其中 $x$ 表示闹铃时间间隔（单位为分钟）。

outputFormat:
输出 $T$ 行，每行包含一个时间（格式为 `yyyy-MM-dd HH:mm:ss`），依
次表示每组数据的答案。

hint: 对于所有评测用例，$1 \le T \le 10，1 \le x \le 1000$，保证所有的时间格式都是合法的。