title: [蓝桥杯 2023 国 Python A] 火车运输

background: 为照顾 Python 语言的效率，本题时限较大。建议使用 PyPy3 提交本题。

description:
钢厂有一辆用于运送废旧钢材的火车，它具有两节车厢，其中车厢 1 的最大载重量为 $A$，车厢 2 的最大载重量为 $B$。现在一共有 $N$ 件废旧钢材需要被运输，其中第 $i$ 件钢材的重量为 $w_i$，为了最大化运输效率，车长想要一次性运输走重量尽可能多的钢材，请你帮助车长计算出一次运输最多可以带走多大重量的钢材。

每件钢材都是独立的不可分割的，只能被放置在某一节车厢中。在装载钢材时只需要考虑重量条件即可。

inputFormat:
输入的第一行包含三个整数 $N ,A,B$，用一个空格分隔，分别表示钢材的数目以及两节车厢的最大载重。

第二行包含 $N$ 个整数，分别表示 $w_1,w_2, \cdots,w_n$，相邻两个整数之间使用一个空格分隔。

hint:
对于 $30\%$ 的评测用例，$1 \le N \le 10$；

对于所有评测用例，$1 \le N \le 200,1 \le w_i
,A,B \le 1000$。

#### 样例解释

车厢 1 装入第 $2$ 件和第 $3$ 件钢材，车厢 2 装入第 $1$ 件钢材。


title: [蓝桥杯 2024 省 Python B] 蓝桥村的真相

type: P

description:
在风景如画的蓝桥村，$n$ 名村民围坐在一张古老的圆桌旁，参与一场思想
的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要么是无可救药的说谎者。

当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流发言，编号为 $i$ 的村民提出了这样的断言：坐在他之后的两位村民——也就是
编号 $i + 1$ 和 $i + 2$（注意，编号是环形的，所以如果 $i$ 是最后一个，则 $i + 1$ 是
第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。

在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？

请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中，
说谎者的总数。

inputFormat:
输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每个数据一行包含一个整数 $n$，表示村落的人数。

outputFormat: 输出 $T$ 行，每行包含一个整数，依次表示每组数据的答案。

hint:
对于 $10\%$ 的评测用例，$T = 1，3 \le n \le 10$。

对于 $40\%$ 的评测用例，$1 \le T \le 10^2，3 \le n \le 3 \times10^3$。

对于所有评测用例，$1 \le T \le 10^5，3 \le n \le 10^{18}$。

#### 样例解释
在样例中，可能的组合有「假，假，假」「真，真，假」「真，假，真」「假，
真，真」，说谎者的总数为 $3 + 1 + 1 + 1 = 6$。


title: [蓝桥杯 2023 国 Python A] 走方格

description:
给定一个 $N$ 行 $N$ 列的方格，第 $i$ 行第 $j$ 列的方格坐标为 $(i, j)$，高度为
$H_{i,j}$。小蓝从左上角坐标 $(0, 0)$ 出发，目的地是右下角坐标 $(N − 1, N − 1)$。
当小蓝位于第 $r$ 行第 $c$ 列时，他有如下的移动方式：
1. 若 $r + 1 < N$，可以移动到 $(r + 1, c)$，花费 $1$ 秒；
1. 若 $c + 1 < N$，可以移动到 $(r, c + 1)$，花费 $1$ 秒；
1. 对于任意整数 $L$，若 $H_{r,c} > H_{r,c+1} > \cdots > H_{r,c+L}$，可以移动到 $(r, c + L)$，花费 $1$ 秒；
1. 对于任意整数 $L$，若 $H_{r,c} > H_{r,c−1} > \cdots > H_{r,c−L}$，可以移动到 $(r, c − L)$，花费 $1$ 秒。

现在给出方格，请问小蓝从 $(0, 0)$ 移动到 $(N − 1, N − 1)$ 最少需要多少秒？

inputFormat:
输入的第一行包含一个整数 $N$ 表示方格大小。
接下来 $N$ 行，每行包含 $N$ 个整数，表示每个方格上的数字。

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

hint:
对于 $20\%$ 的评测用例，$1 \le N \le 10$；

对于 $50\%$ 的评测用例，$1 \le N \le 100$；

对于所有评测用例，$1 \le N \le 1000,0 \le H_{i, j} \le 100$。

#### 样例解释
移动顺序为：$(0, 0)\rightarrow (1, 0)\rightarrow(2, 0)\rightarrow(3, 0)\rightarrow(3, 2)\rightarrow(3, 3)$，其中坐标 $(3, 0),(3, 1),(3, 2)$ 处的数字分别为 $9 > 8 > 0$，所以可以花费 $1$ 秒从 $(3, 0)$
移动到 $(3, 2)$。


title: [蓝桥杯 2023 国 Python A] 等腰三角形

background: Python 用户建议使用 PyPy3 提交本题。

description:
给定一个包含 $n$ 个数的序列 $A_i$，每次操作可以选择其中任意一个数将其
$+1$ 或 $−1$。

我们要让这个序列满足能够从中任选三个数，这三个数对应长度的三条边总能组成一个等腰三角形。问最少需要多少次操作才能让序列满足条件。

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

第二行包含 $n$ 个整数，分别表示 $A_1, A_2, \cdots, A_n$，相邻两个整数之间使用一个空格分隔。

outputFormat: 输出一行包含一个整数，表示最少的操作次数。

hint:
对于 $40\%$ 的评测用例，$n \le 5000,A_i \le5000$；

对于 $70\%$ 的评测用例，$n \le 2 \times 10^5,A_i \le 10^6$；

对于所有评测用例，$1 \le n \le 2 \times 10^5,1 \le A_i \le 10^9$。

#### 样例解释

将原序列修改为 $4, 4, 4, 7, 7$ 即可。


title: [蓝桥杯 2023 国 Python A] 彩色二叉树

background: 建议使用 PyPy3 提交本题。

description:
给定包含 n 个结点的完全二叉树，如下图是一棵包含 n = 6 个结点的完全
二叉树。

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

给定 $q$ 次操作，操作可以是：
1. $x_i\ y_i\ z_i$，表示将与结点 $x_i$ 距离小于等于 $y_i$ 的结点的颜色全部染成 $z_i$；
1. $x_i$，表示查询结点 $x_i$ 的颜色。

inputFormat:
输入的第一行包含两个整数 $n, q$，用一个空格分隔。

接下来 $q$ 行，每行包含 $1$ 个操作，相邻的整数之间使用一个空格分隔。保证每个操作都是合法的。

outputFormat: 对于每个查询操作，输出一行包含一个整数表示对应的答案。

hint:
对于 $40\%$ 的评测用例，$n, q \le 5000$；

对于所有评测用例，$1 \le n \le 10^6,1\le q \le 2 \times 10^5,1 \le x_i \le n,1 \le y_i \le 10^6,1 \le z_i\le 10^6$。


title: [蓝桥杯 2023 国 Python A] 选段排序

description:
给定一个长度为 $n$ 的序列 $A_i$ 以及两个下标 $p, q(p < q)$。你可以选择任意一个区间 $[L, R]$ 并将序列的这个范围内的元素 $A_L \sim A_R$ 从小到大排序。

求选择一个区间排序后 $A_q − A_p$ 的值最大可以是多少。

inputFormat:
输入的第一行包含三个整数 $n, p, q$，相邻两个整数之间使用一个空格分隔。

第二行包含 $n$ 个整数，分别表示 $A_1, A_2, \cdots, A_n$，相邻两个整数之间使用一个空格分隔。

outputFormat: 输出一行，包含一个整数表示 $A_q − A_p$ 的最大值。

hint:
对于 $20\%$ 的评测用例，$n \le 100 ,A_i \le 200$；

对于 $40\%$ 的评测用例，$n \le 2000 ,A_i \le 3000$；

对于所有评测用例，$1 \le p \le q \le n \le 2 \times 10^5,1 \le A_i \le 10^6$。


title: [蓝桥杯 2023 国 Python A] 最长同类子串

description:
对于两个等长的字符串 $A, B$，如果对于任意 $i, j$，都有 $A_i = A_j$ 和 $B_i = B_j$
同时满足或同时不满足，那么我们称 $A, B$ 是一对同类串。例如，`aabab` 和 `xxkxk` 是一对同类串，而 `abcde` 和  `abcdd` 则不是。

给定 $S, T$，找出一个尽可能大的 $k$ 使得 $S, T$ 分别含有一个长度为 $k$ 的子
串 $S', T'$，且 $S',T'$ 是同类串。

inputFormat: 输入两行，每行包含一个字符串，分别表示 $S, T$。

outputFormat: 输出一行包含一个整数 $k$ 表示答案。

hint:
对于 $40\%$ 的评测用例，$|S |, |T| \le 500$；

对于 $50\%$ 的评测用例，$|S |, |T| \le 2000$；

对于所有评测用例，$1 \le |S |, |T| \le 10^5$，$S, T$ 中仅包含小写英文字母。


title: [蓝桥杯 2024 省 Java B] 星际旅行

background: 备注：原题（Java）时间限制 3.0s，空间限制 512 MB。

description:
小明国庆节准备去某星系进行星际旅行，这个星系里一共有 $n$ 个星球，其中布置了 $m$ 道双向传送门，第 $i$ 道传送门可以连接 $a_i$，$b_i$ 两颗星球（$a_i \neq b_i$ 且任意两颗星球之间最多只有一个传送门）。

他看中了一款 “旅游盲盒”，一共有 $Q$ 个盲盒，第 $i$ 个盲盒里的旅行方案规定了旅行的起始星球 $x_i$ 和最多可以使用传送门的次数 $y_i$。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。

小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买，他想知道能旅行到的不同星球的数量的期望是多少。

inputFormat:
输入共 $m + Q + 1$ 行。

第一行为三个正整数 $n, m, Q$。

后面 $m$ 行，每行两个正整数 $a_i$，$b_i$。

后面 $Q$ 行，每行两个整数 $x_i$，$y_i$。

outputFormat: 输出共一行，一个浮点数（四舍五入保留两位小数）。

hint:
【样例解释】

- 第一个盲盒可以旅行到 $1, 2, 3$。
- 第二个盲盒可以旅行到 $2$。
- 第三个盲盒可以旅行到 $1, 2$。

所以期望是 $(3 + 1 + 2) / 3 = 2.00$。

【数据范围】

- 对于 $20 \%$ 的评测用例，保证 $n \leq 300$。
- 对于 $100 \%$ 的评测用例，保证 $n \leq 1000$，$m \leq \min \left\{\dfrac{n(n - 1)}{2}, 5n\right\}$，$Q \leq 50000$，$0 \leq y_i \leq n$，$1 \leq x_i \leq n$。


title: [蓝桥杯 2024 省 Java B] LITS 游戏

background: 备注：原题（Java）时间限制 3.0s，空间限制 512 MB。

description:
俄罗斯方块是一款风靡全球的游戏，在游戏中有多种方格图案，我们只关注这四个经典的方块图案：**LITS**，如下图所示：

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

LITS 这四种方块都是由四个相同大小的小方块组成的。
现在给出一副大小为 $N \times N$ 的格子图，每个格子上都有一个数字 $0/1$，如果格子处的数字为 $1$ 说明这个格子上有一个小方块，数字为 $0$ 则没有。
你需要判断从这个格子图上是否可以找出 LITS 四个方块图案（每个方块图案之间都是独立的，不存在不同的图案公用同一个小方块的情况）。其中 LITS 方块的形状旋转任意个 $90^\circ$ 都是合法的，但不允许翻转。

inputFormat:
第一行一个整数 $T$，表示有 $T$ 组数据。
每组数据的第一行包含一个整数 $N$，表示格子图大小。
接下来输入 $N$ 行，每行 $N$ 个值为 $0/1$ 的整数，表示格子布局。

outputFormat: 对于每组数据，输出一行包含一个字符串。如果此组数据满足题意则输出 `Yes`，否则输出 `No`。

hint:
【样例解释】

对于样例中的第二个格子图，一种 LITS 的摆放方案如下：

```txt
1 0 0 1 1
L S T T T
L S S T 0
L L S 0 1
0 I I I I
```

【数据范围】

- 对于 $30 \%$ 的评测用例：$1 \leq N \leq 5$。
- 对于 $60 \%$ 的评测用例：$1 \leq N \leq 10$。
- 对于 $100 \%$ 的评测用例：$1 \leq T \leq 10$，$1 \leq N \leq 50$。

【特别备注】

由于讨论情况较多，本题的数据可能存在错误，请大家自由尝试并寻找错误。


title: [蓝桥杯 2024 省 Java B] 拼十字

background: 备注：原题（Java）时间限制 3.0s，空间限制 512 MB。

description:
在 LQ 国神秘的古老森林，有一座被称为 “拼十字” 的神秘遗迹。据传， “拼十字” 是由古代文明建造的，它是一个巨大的石头结构，由两个巨大的矩形交叉叠放在一起，形成了一个庄严而神秘的十字形状。这个遗迹被认为是连接人类和神灵之间的通道，拥有神秘的力量和能量。

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

现在给出 $N$ 个矩形，其中第 $i$ 个矩形的长度和宽度分别为 $l_i$，$w_i$，并且矩形的颜色 $c_i$ 为红 $(0)$、黄 $(1)$、蓝 $(2)$ 中的一种。现在小蓝想知道在这 $N$ 个矩形中有多少对可以“拼十字”？

两个矩形可以“拼十字”的充要条件是：

1. 两个矩形的颜色不同；
2. 矩形 $1$ 的长度严格大于矩形 $2$ 的长度并且矩形 $1$ 的宽度严格小于矩形 $2$ 的宽度。

注意，矩形长度和宽度属性是固定的，是不可以通过旋转矩形而发生转变的。

inputFormat:
第一行一个整数 $N$，表示有 $N$ 个矩形。

接下来 $N$ 行，每行输入三个整数 $l$、$w$、$c$ 表示一个矩形的长、宽和颜色。

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

hint:
【样例解释】

第 $3$ 个矩形可以和第 $1$ 个矩形拼十字，第 $3$ 个矩形也可以和第 $4$ 个矩形拼十字。所以一共有两对矩形可以拼十字，答案为 $2$。

【数据范围】

- 对于 $30\%$ 的评测用例：$1 \leq N \leq 5000$。
- 对于 $100 \%$ 的评测用例：$1 \leq N \leq 10^5$，$1 \leq l,w \leq 10^5$，$0 \leq c \leq 2$。


title: [蓝桥杯 2024 省 Python B] 魔法巡游

description:
在蓝桥王国中，两位魔法使者，小蓝与小桥，肩负着维护时空秩序的使命。他们每人分别持有 $N$ 个符文石，这些石头被赋予了强大的力量，每一块上都刻
有一个介于 $1$ 到 $10^9$ 之间的数字符号。小蓝的符文石集合标记为 $s_1, s_2, \cdots , s_N$，小桥的则为 $t_1, t_2, \cdots , t_N$。

两位魔法使者的任务是通过使用符文石，在各个时空结点间巡游。每次巡游遵循这样一条法则：当小蓝使用了符文石 $s_i$ 到达新的结点后，小桥必须选用一个序号更大的符文石（即某个 $t_j$ 满足 $j > i$）前往下一个结点。同理，小桥抵达之后，小蓝需要选择一个序号 $k > j$ 的符文石 $s_k$ 继续他们的巡游。

为了成功地穿梭时空，两个连续使用的符文石上的数字符号必须有共鸣，这种共鸣只有当数字符号中至少包含一个特定的元素——星火（数字 $0$）、水波
（数字 $2$）或者风语（数字 $4$）时，才会发生。例如，符号序列 $126, 552, 24, 4$ 中的每对连续符文都包含了至少一个共鸣元素，则它们是一系列成功的巡游；而如果是 $15, 51, 5$，则不成立，因为它们之间的共鸣元素不包含星火、水波或风语
中的任意一个。

小蓝总是先启程，使用他的符文石开启巡游。

你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样
的序列形式为 $s_{i_1}, t_{i_2}, s_{i_3}, t_{i_4}, \cdots$，其中序列索引满足 $i_1 < i_2 < i_3 < i_4 < \cdots$，并且序列中每一对相邻的符文石都至少包含一个共鸣元素。

inputFormat:
输入的第一行包含一个整数 $N$，表示每位魔法使者持有的符文石数量。

第二行包含 $N$ 个整数 $s_1, s_2, \cdots , s_N$，相邻整数之间使用一个空格分隔，表示小蓝的符文石上刻有的数字符号。

第三行包含 $N$ 个整数 $t_1, t_2, \cdots , t_N$ ，相邻整数之间使用一个空格分隔，表示小桥的符文石上刻有的数字符号。

outputFormat: 输出一行包含一个整数，表示小蓝和小桥在遵守所有规则的情况下，最多能进行多少次时空巡游。

hint:
对于 $30\%$ 的评测用例，$1 \le N \le 10^3,1 \le s_i
, t_i \le 10^5$。

对于所有评测用例，$1 \le N \le 10^5,1 ≤ s_i
, t_i \le 10^9$。
#### 样例解释
这里，数字 $2$ 作为共鸣元素连接了 $s_1$ 和 $t_3$、$s_4$ 和 $t_5$，数字 $2$、$4$ 作为共鸣元素
连接了 $t_3$ 和 $s_4$。


title: [蓝桥杯 2024 省 Python B] 缴纳过路费

description:
在繁华的商业王国中，$N$ 座城市被 $M$ 条商路巧妙地连接在一起，形成了一个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过
商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。

有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费总和，而是这条路线上最贵的那一次收费。这个标准简单而直接，让他能迅速评估出一条路线是否划算。

于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线成本介于他心中预设的两个数 $L$ 和 $R$ 之间。他相信，这样的路线既不会太廉价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。

作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。

inputFormat:
输入的第一行包含四个整数 $N, M, L, R$，表示有 $N$ 座城市和 $M$ 条双向通行的商路，以及小蓝心中预设的最高过路费的下限 $L$ 和上限 $R$。

接下来 $M$ 行，每行包含三个整数 $u, v,w$，表示城市 $u$ 和城市 $v$ 之间有一条双向通行的商路，过路费为 $w$。保证每对城市之间最多只有一条直接的商路。

outputFormat: 输出一行包含一个整数，表示满足条件的城市对数量。

hint:
对于 30% 的评测用例，$1 \le N \le 10^3,1 \le M \le \min(2 \times 10^3,\frac{N×(N−1)}{2}),
1 \le L \le R \le 10^5，1 \le u, v \le N, u \ne v,1 \le w \le 10^5$。

对于所有评测用例，$1 \le N \le 10^5,1 \le M \le \min(2 \times 10^5,\frac{N×(N−1)}{2}),1 \le L \le
R \le 10^9,1 \le u, v \le N, u \ne v，1 \le w \le 10^9$。
#### 样例解释
在样例中，满足条件的城市对有 $(1, 2),(1, 4),(2, 4)$。


title: [蓝桥杯 2024 省 Python B] 纯职业小组

description:
在蓝桥王国，国王统治着一支由 $n$ 个小队组成的强大军队。每个小队都由
相同职业的士兵组成。具体地，第 $i$ 个小队包含了 $b_i$ 名职业为 $a_i$ 的士兵。

近日，国王计划在王宫广场举行一场盛大的士兵检阅仪式，以庆祝王国的繁荣昌盛。然而，在士兵们入场的过程中，一场突如其来的风暴打乱了他们的行列，使得不同小队的士兵混杂在一起，次序乱成一团，

尽管国王无法知道每个士兵的具体职业，但为了确保仪式能顺利进行，国王打算从这些混乱的士兵中选出一部分，组成 $k$ 个“纯职业小组”进行检阅。一个“纯职业小组”定义为由 $3$ 名同职业的士兵组成的队伍。

请问，国王至少需要选择多少名士兵，才能确保这些士兵可以组成 $k$ 个“纯职业小组”

inputFormat:
输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每组数据的第一行包含两个整数 $n_t$ 和 $k$ ，用一个空格分隔，表示小队的数量和要组成的纯职业小组的数量。

接下来的 $n_t$ 行，每行包含两个整数 $a_i$ 和 $b_i$，用一个空格分隔，表示第 $i$ 个小队中士兵的职业和数量。

outputFormat:
输出 $T$ 行，每行包含一个整数，依次表示每组数据的答案，即为了组成 $k$
个“纯职业小组”，国王至少需要选择的士兵数量。如果无论如何也无法组成 $k$ 个“纯职业小组”，则输出 $-1$。

hint:
对于 $50\%$ 的评测用例，$1\le T \le 10，1 \le
\sum_{t=1}^Tn_t \le 2 \times 10^3,1 \le ai
, b_i \le 10^5,1 \le k \le 10^7$。

对于所有评测用例，$1\le T \le 100，1 \le
\sum_{t=1}^Tn_t \le 2 \times 10^5,1 \le ai
, b_i \le 10^9,1 \le k \le 10^{13}$。

#### 样例解释
在第一个样例中，要想组成 $2$ 个“纯职业小组”，国王至少需要选择 $8$ 名
士兵。若只选择了 $7$ 名士兵，则这 7 名士兵的职业可能为 $1, 1, 1, 2, 2, 3, 3$，无法组成 $2$ 个“纯职业小组”。

在第二个样例中，即使选择了所有士兵，也无法组成 $5$ 个“纯职业小组”，
因此输出 $−1$。


title: [蓝桥杯 2024 省 Python B] 穿越时空之门

description:
随着 $2024$ 年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘
的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。
在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数
位之和。

在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示中各数位之和。

穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等同于四进制领域的力量时，他才能够成功地穿越。

国王选定了小蓝作为领路人，带领着力量值从 $1$ 到 $2024$ 的勇者们踏上了这段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这 $2024$ 位勇者中，有多少人符合穿越时空之门的条件。

outputFormat: 一行一个整数表示答案。


title: [蓝桥杯 2024 省 Python B] 数字串个数

description:
小蓝想要构造出一个长度为 $10000$ 的数字字符串，有以下要求：

1. 小蓝不喜欢数字 $0$，所以数字字符串中不可以出现 $0$；

1. 小蓝喜欢数字 $3$ 和 $7$，所以数字字符串中必须要有 $3$ 和 $7$ 这两个数字。

请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其
对 $10^9 + 7$ 取余后的结果。


title: Katu Puzzle

description:
Katu Puzzle 以一个有向图 $G(V, E)$ 的形式给出，其中每条边 $e(a, b)$ 都被标记为一个布尔运算符 $\text{op}$（AND, OR, XOR 之一）以及一个整数 $c$（$0 \leq c \leq 1$）。如果可以为每个顶点 $V_i$ 找到一个值 $X_i$（$0 \leq X_i \leq 1$），使得对于每条边 $e(a, b)$ 由 $\text{op}$ 和 $c$ 标记的情况下，以下公式成立：

$$X_a \ \text{op} \ X_b = c$$

那么这个 Katu 是可解的。

给定一个 Katu Puzzle，你的任务是确定它是否可解。

inputFormat:
第一行包含两个整数 $N$（$1 \leq N \leq 100$）和 $M$（$0 \leq M \leq 10,000$），分别表示顶点的数量和边的数量。

接下来的 $M$ 行中，每行包含三个整数 $a$（$0 \leq a < N$），$b$（$0 \leq b < N$），$c$ 以及一个操作符 $\text{op}$，描述这条边。

outputFormat: 输出一行，包含 $\texttt{YES}$ 或 $\texttt{NO}$。


title: Cookies

description:
圣诞老人共有 $M$ 个饼干，准备全部分给 $N$ 个孩子。

每个孩子有一个贪婪度，第 $i$ 个孩子的贪婪度为 $g_i$。

如果有 $a_i$ 个孩子拿到的饼干数比第 $i$ 个孩子多，那么第 $i$ 个孩子会产生 $g_i\times a_i$ 的怨气。

给定 $N$、$M$ 和序列 $g$，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。

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

第二行包含 $N$ 个整数表示 $g_1,g_2,\dots,g_n$。

outputFormat:
第一行一个整数表示最小怨气总和。

第二行 $N$ 个空格隔开的整数表示每个孩子分到的饼干数，若有多种方案，输出任意一种均可。

hint: 数据保证，$1\leq N\leq 30$，$N\leq M\leq 5000$，$1\leq g_i\leq 10^7$。


title: I-Country

description:
根据绝密的 A 国计划，I 国被划分为 $N\times M$ 个相等的正方形，每个正方形包含一些石油资源。他们希望占领整个 I 国的领土，但联合国只允许他们占领 $K$ 个正方形。

当然，A 国希望控制尽可能多的石油，但是他们必须守卫他们的全部领土。因此，他们需要他们的领土易于控制，即从任何一个正方形到另一个正方形只能沿着两个方向移动（从下列列表中选择：左、右、上、下；对于不同的正方形对，方向可能不同）。

你需要编写一个程序，确定 A 国将占领哪些正方形。如果有多个解决方案，你可以输出任意一个。

inputFormat:
输入的第一行包含 3 个整数 $N$、$M$、$K$（$1≤N, M≤15$，$0≤K≤N\times M$）。

接下来的 $N$ 行包含每行 $M$ 个整数，表示该正方形上的石油资源数量。每个数字的范围在 $0$ 到 $1000$ 之间。

outputFormat:
输出的第一行是字符串 Oil : X，其中 $X$ 是 A 国可以控制的最大石油数量。

接下来，你应该输出 $K$ 对数字，表示 A 国将占领的正方形的坐标。第一个坐标是行号（从上到下，从 $1$ 开始），第二个是列号（从左到右，从 $1$ 开始）。


title: Coins

description:
银国的人们使用硬币。他们有面值分别为 $A_1, A_2, A_3, \dots, A_n$ 的硬币。有一天，托尼打开了他的储蓄罐，发现里面有一些硬币。他决定去附近的商店购买一块非常漂亮的手表。他想要支付准确的价格（不找零），而他知道手表的价格不会超过 $m$ 。但他不知道手表的确切价格。

你需要编写一个程序，读取 $n$、$m$、$A_1, A_2, A_3, \dots, A_n$ 以及对应的数量 $C_1, C_2, C_3, \dots, C_n$ （表示托尼拥有的每种面值的硬币数量），然后计算托尼可以用这些硬币支付的价格数量（从 1 到 $m$ 的所有价格）。

inputFormat: 输入包含多个测试用例（不超过 $25$ 组）。每个测试用例的第一行包含两个整数 $n (1 ≤ n ≤ 100)$ 和 $m (m ≤ 100000)$。第二行包含 $2n$ 个整数，分别表示 $A_1, A_2, A_3, \dots, A_n$ 和 $C_1, C_2, C_3, \dots, C_n (1 ≤ A_i ≤ 100000, 1 ≤ C_i ≤ 1000)$。最后一个测试用例以两个零结尾。

outputFormat: 对于每个测试用例，在单独的一行输出答案。


title: Accumulation Degree

background: 树木是自然景观的重要组成部分，因为它们可以防止土壤侵蚀，并在其树叶中及其下方提供特定的气候庇护生态系统。研究表明，树木在生产氧气和减少大气中的二氧化碳方面起着重要作用，还可以调节地面温度。它们在园林设计和农业中也是重要的元素，既因为它们的美学吸引力，也因为它们的果园作物（如苹果）。木材也是常见的建筑材料。

description:
树在许多世界神话中也扮演着亲密的角色。许多学者对树的一些特殊属性感兴趣，例如树的中心、树的计数、树的着色等。树的累积度 $A(x)$ 就是其中的一种属性。

我们这么定义 $A(x)$：

- 树的每一条边都有一个正容量。
- 树中度为 $1$ 的节点被称为终端节点。
- 每条边的流量不能超过其容量。
- $A(x)$ 是节点 $x$ 可以流向其他终端节点的最大流量。

树的累积度是指其节点中最大累积度的值。你的任务是找到给定树的累积度。

inputFormat: 输入的第一行是一个整数 $T$，表示测试用例的数量。每个测试用例的第一行是一个正整数 $n$。接下来的 $n - 1$ 行中的每一行包含三个整数 $x,y,z$，用空格分隔，表示节点 $x$ 和节点 $y$ 之间有一条边，并且这条边的容量为 $z$。节点编号从 $1$ 到 $n$。所有元素都是不超过 $200000$ 的非负整数。可以假设测试数据都是树。

outputFormat: 对于每个测试用例，在单独的一行输出结果。


title: Mondriaan's Dream

description:
荷兰著名画家皮特·蒙德里安对正方形和矩形非常着迷。有一天晚上，在创作完他的“厕所系列”画作后（他不得不用厕纸画画，因为他所有的画纸都用完了），他梦见用宽度为 $2$、高度为 $1$ 的小矩形以不同的方式填充一个大矩形。

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

作为这方面的专家，他一眼就看出需要使用计算机来计算填充这个大矩形的不同方式。请帮助他，以免他的梦想变成噩梦！

inputFormat: 输入包含多个测试用例。每个测试用例由两个整数构成：大矩形的高度 $h$ 和宽度 $w$。当 $h = w = 0$ 时输入结束。否则，$1 \leq h, w \leq 11$。

outputFormat: 对于每个测试用例，输出使用大小为 $2\times 1$ 的小矩形填充给定大矩形的不同方式的数量。假设给定的大矩形是定向的，即对称的铺砌方式应多次计算。


title: 统计重复个数

description:
定义 $str = [s, n]$ 表示 $str$ 由 $n$ 个字符串 $s$ 连接构成。

例如，$str == [\texttt{abc}, 3] == \texttt{abcabcabc}$。
如果可以从 $s_2$ 中删除某些字符使其变为 $s_1$，则称字符串 $s_1$ 可以从字符串 $s_2$ 获得。

例如，根据定义，$s1 = \tt{abc}$ 可以从 $s2 = \tt{ab\red{dbe}c}$ 获得，仅需要删除红色标识的字符。

现在给你两个字符串 $s_1$ 和 $s_2$ 和两个整数 $n_1$ 和 $n_2$。由此构造得到两个字符串，其中 $str_1 = [s_1, n_1]$、$str_2 = [s_2, n_2]$。

请你找出一个最大整数 $m$，以满足 $str = [str_2, m]$ 可以从 $str_1$ 获得。

inputFormat:
本题有多组测试数据。测试数据不超过 $100$ 组。

对于每组测试数据，分为两行：
- 第一行输入字符串 $s_1$ 和整数 $n_1$；
- 第二行输入字符串 $s_2$ 和整数 $n_2$；

outputFormat: 对于每组测试数据，输出整数 $m$ 表示答案。

hint: 数据保证，$s_1,s_2$ 全为小写字母构成，且 $1\leq |s_1|,|s_2| \leq 100$，$1\leq n_1,n_2\leq 10^6$，每个测试点的测试数据不超过 $100$ 组。


title: Cut the Sequence

description: 给定一个长度为 $N$ 的整数序列 $\{a_N\}$，你需要将这个序列切分成若干部分，每一部分都是原序列的一个连续子序列。每部分必须满足部分内的整数之和不超过给定的整数 $M$。你的任务是找到一种切分方式，使得每一部分的最大整数之和最小化。

inputFormat: 输入的第一行包含两个整数 $N$ 和 $M$（$0 < N \leq 100000$，$M$ 是 int 范围内的正整数）。接下来的第二行包含 $N$ 个整数，描述了整数序列。序列中的每个整数都在 $0$ 到 $1000000$ 之间（含 $0$ 和 $1000000$）。

outputFormat: 输出一个整数，表示每一部分的最大整数之和的最小值。如果不存在这样的切分方式，输出 $-1$。


title: Fence

description:
一组由 $k$ 名工人组成的团队需要粉刷一堵包含 $N$ 个木板的围栏，这些木板从左到右编号为 $1$ 到 $N$。每个工人 $i$（$1 \leq i \leq k$）应该坐在木板 $S_i$ 前，他只能粉刷一个连续的区间（这意味着区间内的木板应该是连续的）。这个区间必须包含木板 $S_i$。此外，每个工人粉刷的木板数量不能超过 $L_i$ 个，并且每粉刷一个木板他会得到 $P_i$ 美元（$1 \leq P_i \leq 10,000$）。每个木板最多只能由一个工人粉刷。所有的 $S_i$ 都是不同的。

作为团队的领导者，你需要为每个工人确定他们应该粉刷的区间，并且确保总收入最大化。总收入代表工人个人收入的总和。

编写一个程序来确定 $k$ 名工人获得的总最大收入。

inputFormat:
输入的第一行是是两个正整数 $N,k$。

接下来 $k$ 行，每行三个正整数 $L_i,P_i,S_i$。

outputFormat: 输出一个整数，表示总最大收入。


title: 任务安排 2

background: 本题是 P2365 强化版，是 P5785 弱化版，用于让学生循序渐进地了解斜率优化 DP。

description:
机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$，因此序列的排列为 $1 , 2 , 3 \cdots n$。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和。

**注意，同一批任务将在同一时刻完成**。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。

请确定一个分组方案，使得总费用最小。

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

接下来 $n$ 行，每行有一对整数，分别为 $T_i$ 和 $C_i$，表示第 $i$ 个任务单独完成所需的时间是 $T_i$ 及其费用系数 $C_i$。

outputFormat: 一行，一个整数，表示最小的总费用。


title: Connected Graph

background: 本题是 P4841 [集训队作业2013] 城市规划 的弱化版，去除了原题中的多项式部分。

description: 求 $n$ 个结点的有标号无向连通图个数。

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

hint: 数据保证 $1\leq n \leq 1000$。


title: 最大公约数

type: B

description:
定义两个正整数的最大公约数 $\gcd(a,b)$ 为最大的正整数 $d$，使得 $d$ 可以同时整除 $a$ 和 $b$。

例如，$\gcd(9,12)=3$，因为 $9\div 3$ 和 $12\div 3$ 的余数是 $0$，而无法找到一个比 $3$ 更大的正整数满足要求。

现在给定两个正整数 $a,b$，要求出 $\gcd(a,b)$。

inputFormat: 输入两个正整数 $a,b$。

outputFormat: 输出 $\gcd(a,b)$。

hint:
对于 $40\%$ 的数据，$1\leq a,b\leq 1000$。

对于所有的数据，$1\leq a,b\leq 10^9$。


title: [COTS/CETS 2021] 疫苗接种 Cijepise

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

description:
给定以 $1$ 为根的有 $N$ 个节点的有根树，记 $i$ 号点的点权为 $a_i$。

定义一次操作为：

- 初始化 $u$ 为树根。
	1. 设 $u$ 儿子中点权最大的点为 $v$（若有多个，则**等概率随机选取一个**）。令 $a_u\gets a_v$，$a_v\gets 0$。
	2. 若 $v$ 为叶子，则删去 $v$，终止这个过程。否则令 $u\gets v$，回到 1。

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

定义 $f(v)$ 为：**在最坏情况下**，欲让 $a_v$ 尽可能快地（也就是使用尽量少的操作次数）出现在树根上，至少需要更改多少个点的点权（可以不更改）。点权可以被改为 $[0,2\times 10^9]$ 内的任意整数。

$Q$ 次询问给定 $v$，回答 $f(v)$。

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

第二行，$N$ 个正整数 $a_i$。

接下来 $(N-1)$ 行，每行两个正整数 $u,v$，描述一条树边 $(u,v)$。

接下来一行，一个正整数 $Q$。

接下来 $Q$ 行，每行一个正整数 $v$，表示询问 $f(v)$。

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


title: [COTS/CETS 2021] 赛狗游戏 Tiket

background:
Rebirth.

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

description:
圆，焰，光在观看赛狗游戏。

三个人都猜测了狗冲过终点的顺序，即 $P_i$ 表示第 $i$ 只冲过终点的狗的编号。我们假设没有平局。

有 $N$ 条狗，因此 $P_i$ 构成一个 $1\sim N$ 的排列。不妨记第 $j$ 个人猜测的排列为 $P(j)$。

此外，最终狗冲过终点的顺序构成排列 $T$。

计算满足以下条件的数对 $(a,b)$ 的数量：

- 在 $T$ 中，$a$ 在 $b$ 前面；
- $\forall 1\le j\le 3$，要么 $a$ 在所有的 $P(j)$ 中都在 $b$ 前面，要么 $b$ 在所有的 $P(j)$ 中都在 $a$ 前面。

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

第二行，$N$ 个正整数描述 $T$。

接下来三行，第 $j$ 行 $N$ 个正整数，描述 $P(j)$。

outputFormat: 输出一行一个整数，即答案。


title: 「ALFR Round 4」C 粉碎

description:
斌宝在玩纸牌。起初，他有 $n$ 张牌，第 $i$ 张牌的点数为 $A_i$。

斌宝会重复执行 $n$ 轮以下操作，第 $i$ 轮操作如下：

1. 斌宝需要选择将第 $i$ 张牌置于插入牌堆的最左边或者最右边；
2. 若牌堆中存在两张点数相同的牌，则斌宝会**立即**将两张牌之间的所有牌从牌堆取出，扔进碎纸机（包括这两张牌本身）。

总是会先执行插入操作再执行粉碎操作。

牌堆初始为空。

你需要告诉斌宝他最多能粉碎多少张牌。

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

对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个数表示 $A_1,A_2,A_3,\cdots,A_n$。

outputFormat: 对于每组数据，输出斌宝最多能粉碎多少张牌。


title: 【MX-X5-T0】「GFOI Round 1」Hypnotize

background: > [$\small\text{The absolute catastrophe of \textbf{I\&“Ī྄”} .}$](https://music.163.com/#/song?id=2610328481)

description:
Arcaea 中有 $n$ 张谱面，第 $i$ 张谱面的难度为一个正整数 $a_i$。

有一个正整数 $k$，你希望打两张难度差**恰好**为 $k$ 的谱面。

你需要判断是否存在满足条件的两张谱面。如果存在则输出 `Yes`，否则输出 `No`。

inputFormat:
第一行包含两个正整数 $n,k$。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

outputFormat: 如果存在满足条件的两张谱面，输出 `Yes`；否则输出 `No`。

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

第一组样例中，取第 $1$ 张和第 $6$ 张谱面，由于 $a_6-a_1=4$，输出 `Yes`。

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

第二组样例中，不存在两张谱面难度差为 $11$ 的谱面，输出 `No`。

**【数据范围】**

本题数据包含 $20$ 个测试点，每个测试点分值相等。

对于所有数据，满足 $1\le n\le 100$，$1\le k,a_i\le 10^9$。


title: 【MX-X5-T2】「GFOI Round 1」Interstellar

background: > [Interstellar - PIKASONIC](https://music.163.com/#/song?id=1900207101)

description:
你有一个正整数 $x$，你可以对它进行如下操作：
- 选择一个正整数 $y$，把 $x$ 变为它的 $\gcd(x, y)$ 倍，即 $x \gets x \times \gcd(x, y)$。
  （$\gcd(x, y)$ 表示 $x, y$ 的最大公因数。）

$x$ 的初始值为 $n$，你想通过若干次操作（也可不操作）将它变为 $m$。你想知道至少要多少次操作才能达成目标，或报告无解。

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

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

对于每组测试数据：

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

outputFormat:
对于每组数据：

- 若无解，即 $x$ 无论如何操作都不能变成 $m$，输出 $-1$。
- 否则输出一行一个非负整数，表示最小的操作次数。


title: 「KDOI-10」超级演出

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

**本场比赛所有题目从标准输入读入数据，输出到标准输出。**

description:
巡准备了一场超级演出。舞台和候场室可以看作一个包含 $n$ 个点 $m$ 条边的有向图，并且这个图当中没有环，也就是说，这是一张有向无环图（DAG）。

舞台为 $1$ 号节点，**保证所有节点均有到达节点 $\bm 1$ 的路径**。其余的节点均为候场室，每个候场室恰有一个剧团进行等待。

巡可以对一个候场室 $u$ 发布出场命令：

- 如果这个候场室的剧团还没有出场，并且存在一条 $u\to 1$ 的路径上没有其余候场的剧团。那么这个剧团就会沿着这条路径到达舞台进行演出，随后退场。注意：**一个剧团退场后不会重新回到候场室。**
- 否则，这个命令被认为是无效的。

巡有一个命令序列 $a_1,a_2,\dots,a_k$ 和 $q$ 次询问，每次给出一个区间 $[l,r]$。巡想要知道如果依次对候场室 $a_l,a_{l+1},\dots,a_r$ 发布出场命令后，候场室还会剩下多少剧团等待演出。

注意：每次询问相互独立，也就是说，每次询问之前，每个候场室都恰有一个剧团进行等待。

inputFormat:
从标准输入读入数据。

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含四个正整数 $n,m,k,q$，表示图的点数，边数，序列长度，和询问次数。

接下来 $m$ 行，每行两个正整数 $u,v$，表示一条从 $u$ 到 $v$ 的有向边。保证无自环，无重边。

接下来的一行，$k$ 个正整数 $a_1,a_2,\dots,a_k$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问的区间。

outputFormat:
输出到标准输出。

$q$ 行，每行一个非负整数，表示一次询问的答案。

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

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

如图：

- 当询问 $l=1,r=2$ 时：
	- 发布出场命令 $a_1=2$。$2$ 沿着 $2\to 1$ 出场。
   - 发布出场命令 $a_2=4$。$4$ 沿着 $4\to 2\to 1$ 出场。

   此时余下 $3,5$ 两个剧团，输出 $2$。

- 当询问 $l=2,r=3$ 时：
	- 发布出场命令 $a_2=4$。找不到 $4\to 1$ 的且路上没有别的剧团的路线，该指令被认为无效。
   - 发布出场命令 $a_3=4$。找不到 $4\to 1$ 的且路上没有别的剧团的路线，该指令被认为无效。

   此时余下 $2,3,4,5$ 四个剧团，输出 $4$。

**【样例 2】**

见选手目录下的 `show/show2.in` 与 `show/show2.ans`。

这个样例满足测试点 $1,2$ 的限制条件。

**【样例 3】**

见选手目录下的 `show/show3.in` 与 `show/show3.ans`。

这个样例满足测试点 $5\sim 8$ 的限制条件。

**【样例 4】**

见选手目录下的 `show/show4.in` 与 `show/show4.ans`。

这个样例满足测试点 $9\sim 11$ 的限制条件。

**【样例 5】**

见选手目录下的 `show/show5.in` 与 `show/show5.ans`。

这个样例满足测试点 $12,13$ 的限制条件。

**【样例 6】**

见选手目录下的 `show/show6.in` 与 `show/show6.ans`。

这个样例满足测试点 $18,19$ 的限制条件。

***

**【数据范围】**

对于全部的测试数据，保证：

- $1\leq n,k,q\leq2\times10^5$；
- $1\leq m\leq4\times10^5$；
- $1\leq v<u\leq n$，且不存在两组相同的 $(u,v)$；
- 对于任意 $1\le i\le k$，$2\leq a_i\leq n$；
- 对于每组询问，$1\leq l\leq r\leq k$；
- 输入构成一张有向无环图，且所有节点均存在到达节点 $1$ 的路径。

| 测试点 | $n,k,q\leq$ | $m\leq$ | 特殊性质 |
|:--:|:--:|:--:|:--:|
| $1,2$ | $300$ | $600$ | 无 |
| $3,4$ | $2\,000$ | $4\,000$ | A |
| $5\sim 8$ | $2\,000$ | $4\,000$ | 无 |
| $9\sim 11$ | $2\times10^5$ | $4\times10^5$ | A |
| $12,13$ | $2\times10^5$ | $4\times10^5$ | BC |
| $14,15$ | $2\times10^5$ | $4\times10^5$ | C |
| $16,17$ | $2\times10^5$ | $4\times10^5$ | BD |
| $18,19$ | $2\times10^5$ | $4\times10^5$ | D |
| $20\sim 22$ | $2\times10^5$ | $4\times10^5$ | B |
| $23\sim 25$ | $2\times10^5$ | $4\times10^5$ | 无 |

- 特殊性质 A：图退化为一棵内向树，也就是说，除节点 $1$ 外，每个点恰有一条出边，节点 $1$ 没有出边；
- 特殊性质 B：保证对于每组询问，$r=k$；
- 特殊性质 C：保证对于任意 $1\leq i< j\leq k$，$a_i\neq a_j$；
- 特殊性质 D：保证每个点的入度和出度均不超过 $30$。


title: 【MX-X3-T1】「RiOI-4」What beats RiOI

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

但是众所周知 RiOI 是从 KDOI 里面裂出来的，所以这个只是整活……（小声）
KDOI 对不起喵！

description:
定义一个字符串是**好闪**的，当且仅当这个字符串包含子串 `RiOI`（大小写均可，例如含有 `rioi`，`RIOI`，`rIoI` 均算作含有）。

给定两个只包含大小写英文字母的非空字符串 $s,t$：

- 如果两个字符串都是好闪的，那么输出 `Either is ok!`。
- 否则，如果 $s$ 是好闪的，输出 $s$ `for sure!`。
- 否则，如果 $t$ 是好闪的，输出 $t$ `for sure!`。
- 如果两个字符串都不是好闪的，请输出 `Try again!`。

inputFormat: 两行各一个只包含大小写英文字母的非空字符串，分别表示 $s,t$。

outputFormat: 一行一个字符串，表示你的答案。

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

`RiOI` 含有 `RiOI` 子串，而 `KDOI` 不含，所以输出 `RiOI for sure!`。

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

`RiOIroundfour` 和 `RiOIroundnegtiveone` 都含有 `RiOI` 子串，所以输出 `Either is ok!`。

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

`GoInForIOI` 含有 `rIOI` 子串，而 `GoInForNOI` 不含有，所以输出 `GoInForIOI for sure!`。

**【数据范围】**

对于 $50\%$ 的数据，保证 $s,t$ 只包含小写英文字母。
对于 $100\%$ 的数据，保证 $s,t$ 的长度都不超过 $1\ 000$，且均为仅由大小写英文字母组成的非空字符串。


title: 【MX-X6-T0】Arcaea Scoring System

description:
Arcaea 是一款风靡全球的音乐游戏，以其创新式的三维立体游玩界面知名。在 Arcaea 中，玩家通过点击/滑动屏幕的方式随着音乐的节奏游玩对应的谱面。一次谱面游玩的计分方式如下：

- 谱面包含若干个**物件**。每一个物件的判定结果有 **大 Pure**、**小 Pure**、**Far**、**Lost** 四种。
- 对于一个 $n$ 个物件的谱面，其 **基本分** 为 $10^7$ 分，**附加分** 为 $n$ 分，满分为 $10^7+n$ 分。每一个物件分别占 $\dfrac{10^7}{n}$ 分 **基本分** 和 $1$ 分 **附加分**。
- 如果一个物件获得 **大 Pure** 判定，则玩家获得该物件的全部基本分和附加分。
- 如果一个物件获得 **小 Pure** 判定，则玩家仅获得该物件的全部基本分，不获得附加分。
- 如果一个物件获得 **Far** 判定，则玩家仅获得该物件的基本分的一半。
- 如果一个物件获得 **Lost** 判定，则玩家不获得任何分数。
- 游玩分数为玩家所有物件获得的分数总和**下取整**。

玩家在分数的基础上可以获得 **评级**：

- 游玩分数 $\geq 9.9\times 10^6$ 时，获得 **EX+** 评级；
- 游玩分数 $\geq 9.8\times 10^6$ 但 $<9.9\times 10^6$ 时，获得 **EX** 评级；
- 游玩分数 $\geq 9.5\times 10^6$ 但 $<9.8\times 10^6$ 时，获得 **AA** 评级；
- 游玩分数 $\geq 9.2\times 10^6$ 但 $<9.5\times 10^6$ 时，获得 **A** 评级；
- 游玩分数 $\geq 8.9\times 10^6$ 但 $<9.2\times 10^6$ 时，获得 **B** 评级；
- 游玩分数 $\geq 8.6\times 10^6$ 但 $<8.9\times 10^6$ 时，获得 **C** 评级；
- 游玩分数 $<8.6\times 10^6$ 时，获得 **D** 评级。

现在分别给定一次谱面游玩的四种判定的个数，请计算这次游玩的评级。

inputFormat: 一行四个空格分隔的整数 $p_1,p_0,f,l$，分别表示 **大 Pure**、**小 Pure**、**Far**、**Lost** 的个数。其中谱面物件个数 $n=p_1+p_0+f+l$。

outputFormat: 输出一个字符串表示评级，七种评级分别对应输出 `EX+`、`EX`、`AA`、`A`、`B`、`C`、`D`。

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

所有物件的判定结果均为大 Pure，因此玩家获得全部基本分 $10^7$ 分和全部附加分，由于总共有 $44$ 个物件，故额外获得 $44$ 分，故游玩分数为 $10{,}000{,}044$；总分大于等于 $9.9\times 10^6$，从而获得 EX+ 评级。

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

物件个数为 $33 + 10 + 0 + 1 = 44$ 个。$33$ 个物件的判定结果为大 Pure、$10$ 个物件的判定结果为小 Pure、$1$ 个物件的判定结果为 Lost，因此玩家获得 $\dfrac{43}{44} \times 10^7$ 的基本分和 $33$ 分附加分，故分数总和为 $9{,}772{,}760.\dot 2 \dot 7$，游玩分数向下取整到 $9{,}772{,}760$；总分大于等于 $9.5\times 10^6$ 且小于 $9.8\times 10^6$，从而获得 AA 评级。

**【数据范围】**

对于所有数据，保证 $p_0,p_1,f,l\geq 0$，$1\leq n\leq 100$。

共 $10$ 组数据，对于前 $2$ 组数据，保证 $n=1$。


title: [APC001] D - Array Again

description:
你需要维护一个数列，支持 $4$ 种操作：

1. `1 x y`：连续向数列中插入 $y$ 个数 $x$。
2. `2 x y`：连续在数列中删除 $y$ 次 $x$。如果在某一次删除中 $x$ 已经不存在于数列中，则忽略此操作。
3. `3`：对数列进行去重，即，对于每个在数列中出现过的不同的正整数 $x$，如果它在数列中出现了大于 $1$ 次，则只在数列中保留一个 $x$，其余全部删除。
4. `4 x`：查询数列中 $x$ 的出现次数。

对于每个操作 $4$，请求出其答案。

inputFormat:
第一行一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行若干个整数，表示一次操作。

outputFormat:
对于每次操作 $4$ 输出一行，表示其答案。

数据保证至少有一次操作 $4$。

hint:
### 样例解释 $1$

第 $1$ 次操作：插入 $10$ 个 $2$。

第 $2$ 次操作：删除 $5$ 个 $2$。此后数列中只包含 $5$ 个 $2$。

第 $3$ 次操作：查询 $2$ 的出现次数，共 $5$ 次。

第 $4$ 次操作：对数列进行去重。此后数列中只包含一个 $2$。

第 $5$ 次操作：查询 $2$ 的出现次数，共 $1$ 次。

### 样例解释 $2$

请注意答案可能会超过 `int` 的范围。

### 数据范围

对于 $100\%$ 的数据，$1\le q\le 10^5$，$1\le x,y\le 10^9$。

请注意：由于本题所在比赛没有部分分，故只有通过所有的测试点才可以获得满分，否则会获得 $0$ 分。


title: 【MX-X5-T1】「GFOI Round 1」Inverted World

background: > [Inverted World - ARForest](https://music.163.com/#/song?id=2099631232)

description:
给定一个长度为 $n$ 的正整数序列 $(a_1, \ldots, a_n)$，**保证该序列是等差数列**。
（如果你不知道等差数列的定义，请参阅题目末尾处的提示。）

请求出该序列中满足如下条件的连续非空子串 $(a_l, \ldots, a_r)$（$1 \le l \le r \le n$）的数量：
- 该子串中的元素的平均值是整数。
  （即 $(a_l + \cdots + a_r) \div (r - l + 1)$ 是整数。）

该序列可能很长，即 $n$ 可能很大，故不会给出该序列的每一项，而是只给出长度 $n$、首项 $k$ 和公差 $d$。**保证 $\bm{k, d}$ 都是正整数**。

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

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

对于每组测试数据：

第一行包含三个正整数 $n, k, d$。

outputFormat: 对于每组数据，输出一行一个非负整数，表示平均数为整数的子段个数。


title: [COTS/CETS 2020] 王国 Kraljevstvo

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

description:
给定二维平面上的 $N$ 个点。选择 $K$ 个点，最大化这 $K$ 个点的凸包面积。

此外，要求必须选择平面上 $x$ 坐标最小/最大的两个点。保证这两个点所在的与 $y$ 轴平行的直线上没有其他点，且这两个点的 $y$ 坐标为 $0$。

只需要输出最大的面积。

inputFormat:
第一行，两个正整数 $N,K$。

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

outputFormat:
输出一行一个实数，表示凸包的最大面积。

输出不应有多余的前导零或后导零。


title: [COTS/CETS 2020] 定序 Redoslijed

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

鸣谢：SPJ by @[mygr](https://www.luogu.com.cn/user/739552)

description:
圆用一块长 $N\,\mathrm{m}$ 的木板来画画。木板被从左往右划分成 $N$ 个格子，每个格子长 $1\,\mathrm{m}$。

圆在木板上涂了 $M$ 笔，第 $i$ 笔将第 $l_i\sim r_i$ 个格子涂成颜色 $c_i$。

由于年代久远，圆已经不记得她涂色的顺序了。但是她记得木板最后的样子，所以她找到了你，让你还原一种可能的涂色顺序。

当然，可能不存在这样的顺序，也就是圆记错了。

inputFormat:
第一行，两个正整数 $N,M$。

接下来 $M$ 行，每行三个整数 $l_i,r_i,c_i$，描述一个涂色操作。

接下来一行，$N$ 个整数，第 $i$ 个整数表示第 $i$ 个格子最后的颜色 $b_i$。**特别地，若 $b_i=0$，代表 $b_i$ 未被着色。**

outputFormat:
如果无解，输出 $\texttt{NE}$（克罗地亚语「否」）。

否则第一行输出 $\texttt{DA}$（克罗地亚语「是」）；第二行输出一个 $1\sim M$ 的排列表示涂色顺序。

若有多解，任意均可。


title: [COTS/CETS 2020] 辣椒 Sadnice

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

description:
圆在花园里种了辣椒。花园可以被描述为一张 $(N+1)\times (M+1)$ 的网格图，其中辣椒被种在格点上。她还用 $[(N+1)\times (M+1)-1]$ 条绳索连接相邻的格点，使得任意两株辣椒都能通过绳索互相到达。换句话说，绳索构成了这个网格图的生成树上的边。

定义两棵辣椒**连通**，当且仅当它们通过绳索直接或间接相连。

圆知道，晚上焰要来搞破坏。焰会在水平方向或者竖直方向划一刀，将划过的绳索全部切断。切断后，辣椒植株会被分成几个连通块。**焰会让连通块的数量尽量多。**

为了最小化损失，圆找来了你。她想要知道：怎么安排绳索，才能使得被切断后连通块的数量最小？

inputFormat: 一行两个正整数 $N,M$。

outputFormat:
输出 $(2N+1)$ 行，每行 $(3M+1)$ 个字符。

其中，第 $(2i-1)$ 行的第 $(3j-2)$ 个字符代表点 $(i,j)$（第 $i$ 行第 $j$ 列的植株），用 `o`（ASCII 111）表示。

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

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

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

可参阅样例输出。


title: [COTS/CETS 2020] 抗疫 Autoritet

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

description:
有 $N$ 个国家，$M$ 条双向航线连接不同的国家。需要注意的是，两个国家之间可能有多条航线连接。

疫情当下，欲举全球之力共同抗疫，需要将世界联结。定义世界是**联结的**，当且仅当任意两个国家都通过航线直接或间接相连。

我们记 $V=\{1,2,\cdots,N\}$。在一次操作中：

- 任意选择 $u\in V$；
- 令集合 $S$ 为国家 $u$ 通过**恰好一条**航线能够到达的国家的集合；令集合 $T=V\backslash \{u\}\backslash S$。
- $\forall v\in S$，将连接 $u,v$ 的航线删除；$\forall w\in T$，添加连接 $u,w$ 的航线。

可以证明，添加足够多的航线后，一定能够使世界联结。

欲通过最少的操作次数使世界联结。

求出：
- 最少的操作次数 $k$；
- 在最小化操作次数的前提下，不同的操作序列数量。只需要求出对 $(10^9+7)$ 取模后的结果。

定义两个操作序列是不同的，当且仅当存在 $i\in [1,k]$，使得在这两个操作序列中第 $i$ 次选择的国家 $u$ 不同。

inputFormat:
第一行，两个正整数 $N,M$。

接下来 $M$ 行，第 $i$ 行两个正整数 $a_i,b_i$，描述一条航线 $(a_i,b_i)$。

outputFormat:
输出两行，每行一个整数，表示对应的答案。

其中第二问的答案需要对 $(10^9+7)$ 取模。


title: [COTS/CETS 2020] 餐厅 Restoran

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

目前提交可能会出现 100pts WA 的情况，在修了，在修了。

description:
苏联餐厅前有 $N$ 个人在排队，按顺序标号 $1\sim N$。

餐厅内只有一种菜，同时也是招牌菜——煎蛋。餐厅内没有厨师，所以食物由客人自己烹饪。

由于设备有限，**同一时刻最多有一个人可以烹饪，同一时刻最多有一个人可以用餐。**

定义：「用餐总时间」为从第一个人开始准备食物，到最后一个人用完餐，需要的时间。

烹饪和用餐不一定按顺序，先烹饪的客人可以后用餐。

第 $i$ 个人的烹饪时间为 $a_i$，用餐时间为 $b_i$。你需要求出最优情况下，用餐总时间的最小值。

此外，还有 $M$ 个事件：

- $\texttt{DOLAZI a b}$：新来了一位新客人，他的烹饪时间为 $a$，用餐时间为 $b$。设这是第 $i$ 位新来的客人，则标号为 $(N+i)$。
- $\texttt{ODLAZI x}$：第 $x$ 位客人离开队伍。
- $\texttt{POREDAK}$：客人很不耐烦，想要知道最优的策略，使得用餐总时间最短。

对于前两个类型的事件，你需要求出这个事件结束后，用餐总时间的最小值；

对于第三个类型的事件，你需要求出此时最佳的烹饪、用餐顺序。

inputFormat:
第一行，两个正整数 $N,M$。

接下来 $N$ 行，第 $i$ 行两个正整数 $a_i,b_i$。

接下来 $M$ 行，每行描述一个事件。

数据保证事件合法，且每一时刻至少存在一名客人。

outputFormat:
输出 $(M+1)$ 行。

第一行，输出初始时用餐总时间的最小值。

接下来 $M$ 行，对于第 $i$ 行：
- 若第 $i$ 个事件为 $\texttt{DOLAZI}$ 或 $\texttt{ODLAZI}$ ，输出一个整数，表示这个事件结束后，用餐总时间的最小值；
- 否则，设当前有 $k$ 个客人，输出 $2k$ 个整数，描述最优策略：前 $k$ 个整数表示烹饪的顺序，后 $k$ 个整数表示用餐的顺序。

samples:
1 4
4 3
DOLAZI 3 8
DOLAZI 5 2
ODLAZI 1
ODLAZI 3


title: [COTS/CETS 2020] 龙猫 Totoro

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

description:
给定 $K$ 个 $1\sim N$ 的排列 $\pi_1,\pi_2,\cdots,\pi_K$。

求出排列群 $G(S,\circ)$ 中的排列的逆序对期望值。其中二元运算 $\circ$ 为**置换**，$\forall 1\le i\le K$，都有 $\pi_i\in S$。

具体地说，我们定义 $(\pi\circ \tau)(i)=\pi(\tau(i))$。

群 $G(S,\circ)$ 是满足如下性质的代数结构：

- 封闭性：$\forall a,b\in S$，都有 $a\circ b\in S$；
- 结合律：$\forall a,b,c\in S$，都有 $(a\circ b)\circ c=a\circ (b\circ c)$；
- 幺元：存在 $e\in S$，对于 $\forall a\in S$，都有 $a\circ e=e\circ a=a$；
- 逆元：$\forall a\in S$，存在 $b\in S$，使得 $a\circ b=b\circ a=e$。

定义 $\mathcal{L}(\pi)$ 为 $\pi$ 的逆序对数，即 $\displaystyle \mathcal{L}(\pi)=\sum_{1\le i\lt j\le n}[\pi(i)\gt \pi(j)]$，求出 $\displaystyle \frac{1}{|S|}\sum_{\pi \in S} \mathcal{L}(\pi)$。

答案对 $(10^9+7)$ 取模。

inputFormat:
第一行，两个正整数 $K,N$。

接下来 $K$ 行，第 $i$ 行 $N$ 个正整数描述 $\pi_i$。

outputFormat: 输出一行一个整数，即答案对 $(10^9+7)$ 取模后的结果。


title: 【MX-X6-T3】さよならワンダーランド

background:
> _ほら行くよって$\\$
手を引いてくれた君は$\\$
綺麗な目して言うんだ$\\$
僕らあの頃と$\\$
何も変わらないから$\\$
せめて$\\$
二人で夢を見させて_
>
>_—— [さよならワンダーランド - Nanatsukaze](https://music.163.com/#/song?id=2053736409)_

能够带你进入孩童时期的梦境中的那个人，该在哪里寻找呢？

description:
给定序列 $a_1, a_2, \dots, a_n$，请对于每一个 $1\sim n$ 的整数 $i$ 求任意一个整数 $j$ 使得以下条件同时成立，或判断不存在这样的 $j$：

- $1\leq i+j\leq n$；
- $a_i \leq j \leq a_{i+j}$。

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

接下来一行 $n$ 个空格分隔的整数 $a_1,a_2,\dots,a_n$。

outputFormat:
输出 $n$ 行。

对于第 $i$ 行，如果能够找到 $j$ 使得 $1\leq i+j\leq n$ 且 $a_i \leq j \leq a_{i+j}$ 成立，则先输出一个 $1$，再输出你找到的 $j$，空格分隔。如果有多个合法 $j$ 可输出任意一个。如果不存在这样的 $j$，则仅输出一个 $0$。

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

$i=1,j=2$ 时，$a_i=-1$，$a_{i+j}=4$，满足 $a_i\leq j\leq a_{i+j}$。

$i=2,j=1$ 时，$a_i=1$，$a_{i+j}=4$，满足 $a_i\leq j\leq a_{i+j}$。

$i=3$ 时可以证明不存在符合条件的 $j$。

**【数据范围】**

对于所有数据，保证 $1\leq n \leq 3\times 10^5$，$-10^9\leq a_i\leq 10^9$。

**捆绑测试**，共 3 个 Subtask，具体限制如下所示：

- Subtask 1（17 pts）：$n\leq 1000$。
- Subtask 2（39 pts）：对所有 $1\leq i\leq n$ 保证 $a_i\leq -i$。
- Subtask 3（44 pts）：无特殊限制。


title: [IOI2024] 象形文字序列

background:
请在提交时不要引用 `hieroglyphs.h`。

请勿用 C++14 (GCC 9) 提交。

description:
一个研究团队正在研究象形文字序列之间的相似性。他们将每个象形文字表示成一个非负整数。为了开展研究，他们采用了关于序列的如下概念。

对于一个给定的序列 $A$，某个序列 $S$ 被称为是 $A$ 的**子序列**，当且仅当 $S$ 能够通过移除 $A$ 中的某些（也可能零个）元素而得到。

下表给出了序列 $A = [3, 2, 1, 2]$ 的子序列的一部分例子。

| 子序列  | 由 $A$ 得到子序列的方式                          |
| ------------ | -------------------------------------------------------- |
| [3, 2, 1, 2] | 不移除任何元素。                                 |
| [2, 1, 2]    | [~~3~~, 2, 1, 2]                                      |
| [3, 2, 2]    | [3, 2, ~~1~~, 2]                                      |
| [3, 2]       | [3, ~~2~~, ~~1~~, 2] 或者 [3, 2, ~~1~~, ~~2~~] |
| [3]          | [3, ~~2~~, ~~1~~, ~~2~~]                        |
| [ ]          | [~~3~~, ~~2~~, ~~1~~, ~~2~~]                 |

另一方面，$[3, 3]$ 或 $[1, 3]$ 不是 $A$ 的子序列。

考虑有两个象形文字序列 $A$ 和 $B$。某个序列 $S$ 被称为是 $A$ 和 $B$ 的**公共子序列**，当且仅当 $S$ 同时是 $A$ 和 $B$ 的子序列。此外，我们说某个序列 $U$ 是 $A$ 和 $B$ 的一个**最全公共子序列**，当且仅当如下两个条件成立：
* $U$ 是 $A$ 和 $B$ 的一个公共子序列。
* $A$ 和 $B$ 的任意公共子序列，都是 $U$ 的一个子序列。

可以证明，任意两个序列 $A$ 和 $B$ 都至多有一个最全公共子序列。

研究人员发现了两个象形文字序列 $A$ 和  $B$。序列 $A$ 包含 $N$ 个象形文字，而序列 $B$ 包含 $M$ 个象形文字。请帮助研究人员为序列 $A$ 和 $B$ 找到一个最全公共子序列，或者判定这样的序列并不存在。

outputFormat:
```
T
R[0]  R[1]  ...  R[T-1]
```

这里 $R$ 是 `ucs` 所返回的数组，而 $T$ 为其长度。


title: [语言月赛 202409] 考试

description:
迅风和他的好朋友一同参加了 $n$ 场考试，而迅风拥有预知未来和**提升自己分数**的能力。

在第 $i$ 场考试中，迅风知道他自己原来取得 $a_i$ 分，他的好朋友**一定会**取得 $b_i$ 分。

而他们很喜欢争个高下，设迅风在 $x$ 场考试中分数比他的好朋友高，在 $y$ 场考试中分数比他的好朋友低，那么：

- 若 $x>y$，则说明在这 $n$ 场考试中，迅风更胜一筹。
- 若 $x<y$，则说明迅风的好朋友更胜一筹。
- 若 $x=y$，则说明两人打平。

迅风发现自己可能会输给他的朋友，于是他可以选择若干场考试**提升自己的分数**，记增加的分数总和为 $sum$。

迅风想知道，自己要在这 $n$ 场考试中更胜一筹，所需的 $sum$ 最小为多少？

inputFormat:
输入的第一行有一个正整数 $n$ 表示考试数量。

第二行有 $n$ 个正整数 $a_1,\ldots,a_n$，表示迅风每场考试的分数。

第三行有 $n$ 个正整数 $b_1,\ldots, b_n$，表示迅风的朋友每场考试的分数。

outputFormat: 输出一个非负整数 $sum$ 表示答案。

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

只要把第 $3$ 次考试的得分提升 $6$ 分，就可以在第 $2,3$ 次考试中获得比朋友更高的分数，从而 $x=2,y=1$，迅风更胜一筹。

**【样例 2 解释】**

只要把第 $1,3,4$ 次考试的得分各提升 $1$ 分，就可以让 $x=2,y=1$，从而让迅风更胜一筹。

**【样例 3 解释】**

哪怕不提升分数，也有 $x=2,y=0$ 了，迅风已经更胜一筹。

**【数据范围】**

本题共有 $20$ 个测试点，测试点等分。

|测试点编号|$n\le$|特殊性质|
|:-:|:-:|:-:|
|$1\sim 2$|$2$||
|$3\sim 6$|$100$|$a_i,b_i\le 2$|
|$7$|$1000$|每次考试两人成绩都相等|
|$8\sim 11$|$1000$|迅风成绩递增，他朋友成绩递减|
|$12\sim 15$|$1000$|每次考试两人成绩都不相等|
|$16\sim 20$|$1000$||

**关于测试点 $8\sim 11$，这里的递增和递减是不严格的，如 $1,5,5,8,10$ 也视为递增。**

特别地，编号为奇数的测试点 $n$ 为奇数，编号为偶数的测试点 $n$ 为偶数。

对于全体数据，保证 $1\le n\le 1000$，$1\le a_i,b_i\le 10^4$（也就是 $10000$），输入皆为整数。

**【后记】**
祝各位参加 $2024$ 年 CSP 比赛的选手 rp++！


title: [IOI2024] 树上代价

background:
提交时请不要引用 `tree.h`。

请不要使用 C++14 (GCC 9) 提交。

description:
有一棵包括 $N$ 个**结点**的**树**，结点从 $0$ 到 $N-1$ 编号。结点 $0$ 是树的**根**。除根以外的每个结点都有唯一的**父结点**。对所有满足 $1 \leq i < N$ 的 $i$，结点 $i$ 的父结点为 $P[i]$，这里有 $P[i] < i$。我们约定 $P[0] = -1$。

对所有结点 $i$（$0 \leq i < N$），$i$ 的**子树**是如下结点组成的集合：
 * $i$，以及
 * 所有父结点为 $i$ 的结点，以及
 * 所有父结点的父结点为 $i$ 的结点，以及
 * 所有父结点的父结点的父结点为 $i$ 的结点，以及
 * 以此类推。

下图给出了一个包含 $N = 6$ 个结点的树的例子。每个箭头都从某个结点连向它的父结点（根结点除外，因为它没有父结点）。结点 $2$ 的子树包括结点 $2, 3, 4$ 和 $5$。结点 $0$ 的子树包括树中的全部 $6$ 个结点，而结点 $4$ 的子树仅包括结点 $4$ 自己。

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

每个结点都被赋以非负整数的**权重**。我们将结点 $i$（$0 \leq i < N$）的权重记为 $W[i]$。

你的任务是写一个程序来回答 $Q$ 个询问，其中每个询问都用一对正整数 $(L, R)$ 来表示。对于询问的回答，应按照如下要求进行计算。

对树中的每个结点，都指派一个整数，称为**系数**。这样的指派结果被描述成一个序列 $C[0], \ldots, C[N-1]$，这里 $C[i]$（$0 \leq i < N$）是指派给结点 $i$ 的系数。我们称该序列为一个**系数序列**。注意，系数序列中的元素可以取负值、$0$ 或正值。

对某个询问 $(L, R)$，一个系数序列被称为是**有效的**，如果对于每个结点 $i$（$0 \leq i < N$）都有如下条件成立：结点 $i$ 的子树中的系数之和不小于 $L$ 且不大于 $R$。

对于一个给定的系数序列 $C[0], \ldots, C[N-1]$，结点 $i$ 的**代价**为 $|C[i]| \cdot W[i]$，这里 $|C[i]|$ 表示 $C[i]$ 的绝对值。最后，**总体代价**为所有结点的代价之和。你的任务是，对于每个询问，计算出可以由某个有效系数序列达到的**最小总体代价**。

可以证明，对于任意询问，都至少存在一个有效的系数序列。

### 实现细节

你需要实现如下两个函数：

```
void init(std::vector<int> P, std::vector<int> W)
```

* $P$，$W$：两个长度为 $N$ 的整数数组，记录了结点的父结点和权重。
* 对于每个测试样例，在评测程序与你的程序开始交互时，该函数将被恰好调用一次。

```
long long query(int L, int R)
```
* $L$，$R$：两个整数，描述一次询问。
* 对于每个测试样例，在 `init` 被调用后，该函数将被调用 $Q$ 次。
* 该函数应该返回对给定询问的答案。

inputFormat:
评测程序示例读取如下格式的输入：

```
N
P[1]  P[2] ...  P[N-1]
W[0]  W[1] ...  W[N-2] W[N-1]
Q
L[0]  R[0]
L[1]  R[1]
...
L[Q-1]  R[Q-1]
```

这里的 $L[j]$ 和 $R[j]$（$0 \leq j < Q$），是对 `query` 的第 $j$ 次调用的输入参数。注意，输入数据中的第二行中**仅包括 $N-1$ 个整数**，因为评测程序示例并不读取 $P[0]$ 的值。

outputFormat:
评测程序示例按照如下格式打印你的答案：

```
A[0]
A[1]
...
A[Q-1]
```

这里的 $A[j]$（$0 \leq j < Q$），是第 $j$ 次调用 `query` 时返回的值。


title: Game King

description:
你穿越到了游戏王的世界，现在你正在和你的对手——一张 $n$ 个点 $m$ 条边的有向图决斗。

中间忘了。

真正的决斗者，一切都是必然。为了更好的应对面前的决斗，你需要知道有多少个点 $x$ 满足如下条件。

- 对于任意一个点 $y$，均满足 $x$ 能到达 $y$ 或 $y$ 能到达 $x$（我们认为一个点能到达它自己本身）。

inputFormat:
第一行输入两个正整数 $n,m$，分别表示给定有向图的点数与边数。

接下来 $m$ 行每行输入两个正整数 $x,y$，表示一条有向边 $x\to y$。

outputFormat: 输出一行一个整数表示答案，即有多少个点满足所有点均能到达它或被它到达。

hint:
### 样例一解释

可以证明，只有点 $1,4$ 满足要求。

由于点 $3$ 无法到达点 $2$ 且无法被点 $2$ 到达，故点 $2,3$ 不满足要求。

### 样例二

见下发文件下的 `gameh2.in` 与 `gameh2.ans`。

该样例约束与测试点 $2$ 一致。

### 样例三

见下发文件下的 `gameh3.in` 与 `gameh3.ans`。

该样例约束与测试点 $3$ 一致。

### 数据范围

本题共有 $10$ 个测试点，测试点不等分，每个测试点的具体分值如下。

|测试点编号|分值|$n=$|$m=$|
|:-:|:-:|:-:|:-:|
|$1\sim 2$|$5$|$10$|$20$|
|$3\sim 4$|$5$|$100$|$10^3$|
|$5\sim 6$|$5$|$10^3$|$10^4$|
|$7\sim 8$|$15$|$5\times 10^4$|$5\times 10^5$|
|$9\sim 10$|$20$|$10^6$|$3\times 10^6$|

对于所有数据，保证 $10\le n\le 10^6$，$20\le m\le 3\times 10^6$。

对于奇数编号测试点，保证给定的图没有**不同点数 $\mathbf{>1}$** 的环。

### 提示

**本题输入输出规模较大，请使用较为快速的输入输出方式。**


title: [IOI2024] 尼罗河船运

background:
这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

本题仅支持 C++ 语言提交。但请勿使用 C++14 (GCC 9)

description:
你想通过尼罗河来运输 $N$ 件手工艺品。这些手工艺品从 $0$ 到 $N-1$ 编号。第 $i$（$0 \leq i < N$）件手工艺品的重量是 $W[i]$。

为了运输这些手工艺品，你使用了特制的船。每艘船**最多**可以运**两件**手工艺品。

* 如果你决定将单件手工艺品放在一艘船上，那么这件手工艺品的重量可以是任意的。
* 如果你想把两件手工艺品一起放在同一艘船上，你必须保证这艘船的平衡。具体来说，如果手工艺品 $p$ 和 $q$（$0 \leq p < q < N$）的重量差的绝对值不超过 $D$，即满足 $|W[p] - W[q]| \leq D$，那么你可以将它们一起放在同一艘船上。

你必须付费来运一件手工艺品，其运费取决于同一艘船上所运载的手工艺品数量。手工艺品 $i$（$0 \leq i < N$）的运费是：

* $A[i]$，如果你把手工艺品 $i$ 单独放在船上，或者
* $B[i]$，如果你把手工艺品 $i$ 和另一件手工艺品一起放在船上。

注意在第二种情况中，你要为船上两件手工艺品都支付运费。具体来说，如果你决定用同一艘船运输手工艺品 $p$ 和 $q$（$0 \leq p < q < N$），你需要支付 $B[p] + B[q]$。

一件手工艺品单独用一艘船运输的费用，总是比与其他手工艺品合用一艘船时的费用要高，所以对任意满足 $0 \leq i < N$ 的 $i$，都有 $B[i] < A[i]$。

麻烦的是，由于尼罗河变化莫测，导致 $D$ 的值经常改变。你的任务是回答 $Q$ 个问题，从 $0$ 到 $Q-1$ 编号。这些问题用一个长度为 $Q$ 的数组 $E$ 来描述。问题 $j$（$0 \leq j < Q$）的答案，是在 $D$ 的值等于 $E[j]$ 时运输所有 $N$ 件手工艺品的最小总代价。

outputFormat:
评测程序按如下顺序输出：

```plain
R[0]
R[1]
...
R[S-1]
```

这里，$S$ 是 `calculate_costs` 所返回的数组 $R$ 的长度。

hint:
## 实现细节

你需要实现以下函数。

```
std::vector<long long> calculate_costs(
    std::vector<int> W, std::vector<int> A,
    std::vector<int> B, std::vector<int> E)
```

* $W$，$A$，$B$：长度均为 $N$ 的整数数组，分别给出手工艺品的重量和运费。
* $E$：长度为 $Q$ 的整数数组，给出每个问题中的 $D$ 值。
* 该函数应该返回一个包含 $Q$ 个整数的数组 $R$，给出运输手工艺品的最小总代价，其中 $R[j]$ 对应 $D$ 等于 $E[j]$（对每个满足 $0 \leq j < Q$ 的 $j$）时的运费。
* 对于每个测试用例，该函数恰好被调用一次。

## 约束条件

* $1 \leq N \leq 100\,000$。
* $1 \leq Q \leq 100\,000$。
* 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq W[i] \leq 10^{9}$。
* 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq B[i] < A[i] \leq 10^{9}$。
* 对每个满足 $0 \leq j < Q$ 的 $j$，都有 $1 \leq E[j] \leq 10^{9}$。

## 子任务

| 子任务 | 分数 | 额外的约束条件                                               |
| :----: | :--: | ------------------------------------------------------------ |
|   1    | $6$  | $Q \leq 5$；$N \leq 2000$；对每个满足 $0 \leq i < N$ 的 $i$，都有 $W[i] = 1$ |
|   2    | $13$ | $Q \leq 5$；对每个满足  $0 \leq i < N$ 的 $i$，都有 $W[i] = i+1$ |
|   3    | $17$ | $Q \leq 5$；对每个满足  $0 \leq i < N$ 的 $i$，都有 $A[i] = 2$ 且 $B[i] = 1$ |
|   4    | $11$ | $Q \leq 5$；$N \leq 2000$                                    |
|   5    | $20$ | $Q \leq 5$                                                   |
|   6    | $15$ | 对每个满足 $0 \leq i < N$ 的 $i$，都有 $A[i] = 2$ 且 $B[i] = 1$ |
|   7    | $18$ | 没有额外的约束条件。                                         |

## 例子

考虑以下调用。

```
calculate_costs([15, 12, 2, 10, 21],
                [5, 4, 5, 6, 3],
                [1, 2, 2, 3, 2],
                [5, 9, 1])
```

在该例子中，我们有 $N=5$ 件手工艺品和 $Q=3$ 个问题。

在第一个问题中，$D = 5$。你可以把手工艺品 $0$ 和手工艺品 $3$ 放在同一艘船上（因为 $|15 - 10| \leq 5$），而其他手工艺品都各自放在不同的船上。这使得运输所有手工艺品的总代价最小，即 $1+4+5+3+3 = 16$。

在第二个问题中，$D = 9$。你可以把手工艺品 $0$ 和手工艺品 $1$ 放在同一艘船上（因为 $|15 - 12| \leq 9$），而把手工艺品 $2$ 和手工艺品 $3$ 放在同一艘船上（因为 $|2 - 10| \leq 9$）。剩下的手工艺品单独用一艘船运输。这使得运输所有手工艺品的总代价最小，即 $1+2+2+3+3 = 11$。

在最后一个问题中，$D = 1$。你需要把每件手工艺品都单独用一艘船运输。这使得运输所有手工艺品的总代价最小，即 $5+4+5+6+3 = 23$。

因此，该函数应该返回 $[16, 11, 23]$。


title: [IOI2024] 斯芬克斯的谜题

background:
请在提交时不要引用 `sphinx.h`，并在代码开头加入如下内容：

```cpp
#include <vector>
int perform_experiment(std::vector<int> E);
```

请勿用 C++14 (GCC 9) 提交。

description:
斯芬克斯为你准备了一个谜题。给定 $N$ 个顶点的图，顶点从 $0$ 到 $N-1$ 编号。图中有 $M$ 条边，从 $0$ 到 $M-1$ 编号。每条边连接两个不同的顶点，且边是双向的。具体来说，对从 $0$ 到 $M-1$ 的每个 $j$，边 $j$ 连接顶点 $X[j]$ 和 $Y[j]$。任意两个顶点之间最多有一条边。若两个顶点被一条边连接，则它们是**相邻的**。

对顶点序列 $v_0, v_1, \ldots, v_k$（对 $k \ge 0$），若每两个连续顶点 $v_l$ 和 $v_{l+1}$（对所有满足 $0 \le l \lt k$ 的 $l$）是相邻的，则称其为一条**路径**。路径 $v_0, v_1, \ldots, v_k$ **连接**顶点 $v_0$ 和 $v_k$。在给定的图中，每对顶点被某条路径连接。

现在有 $N + 1$ 种颜色，从 $0$ 到 $N$ 编号。其中，颜色 $N$ 是特殊的，称为**斯芬克斯之色**。一开始每个顶点都有一种颜色，顶点 $i$（$0 \le i \lt N$）的颜色是 $C[i]$。多个顶点可以是同一种颜色的，有的颜色可能没有对应的顶点，且不会有顶点的颜色是斯芬克斯之色。也就是说，$0 \le C[i] \lt N$（$0 \le i \lt N$）。

若一条路径 $v_0, v_1, \ldots, v_k$（对 $k \ge 0$）上的所有顶点都是相同颜色的，则称其是**单色**的。也就是说，满足 $C[v_l] = C[v_{l+1}]$（对所有满足 $0 \le l \lt k$ 的 $l$）。此外，两个顶点 $p$ 和 $q$（$0 \le p \lt N$，$0 \le q \lt N$）在同一个**单色分支**中，当且仅当它们被某条单色路径连接。

你知道图中顶点和边的关系，但是你不知道每个顶点的颜色。你希望通过**重新着色实验**来弄清楚顶点的颜色。

在一次重新着色实验中，你可以对任意多的顶点进行重新着色。具体来说，在一次重新着色实验中，你先给出一个长度为 $N$ 的数组 $E$，对每个 $i$（$0 \le i \lt N$），$E[i]$ 的值在 $-1$ 和 $N$ 之间（**包括** $-1$ 和 $N$）。重新着色后，每个顶点 $i$ 的颜色变成了 $S[i]$，其中 $S[i]$ 的值：
* 若 $E[i] = -1$，则是 $C[i]$，也就是重新着色前顶点 $i$ 的颜色；
* 否则，是 $E[i]$。

注意：你可以在重新着色的过程中使用斯芬克斯之色。

在将每个顶点 $i$ 的颜色设为 $S[i]$（$0 \le i \lt N$）之后，斯芬克斯会宣布图中单色分支的数量。新的着色情况仅在本次重新着色实验中有效，因此**当本次实验结束后，所有顶点的颜色会恢复成最初的情况**。

你的任务是至多通过 $2\,750$ 次重新着色实验来确定图中顶点的颜色。如果正确给出了每对相邻顶点是否具有相同颜色，那么也会获得部分分数。

### 实现细节

你要实现以下函数。

```
std::vector<int> find_colours(int N,
    std::vector<int> X, std::vector<int> Y)
```

* $N$：图中顶点的数量。
* $X$，$Y$：两个长度为 $M$ 的数组，描述图中的边。
* 该函数应该返回一个长度为 $N$ 的数组 $G$，表示图中顶点的颜色。
* 对每个测试用例，该函数恰好被调用一次。

以上函数可以通过调用下面的函数来进行重新着色实验：

```
int perform_experiment(std::vector<int> E)
```

* $E$：长度为 $N$ 的数组，指定顶点重新着色的方式。
* 该函数返回根据 $E$ 所给出的方式进行重新着色后单色分支的数量。
* 该函数至多只能调用 $2\,750$ 次。

评测程序**不是自适应的**。也就是说，顶点的颜色在调用 `find_colours` 之前就已经固定下来了。

outputFormat:
评测程序示例按照如下格式打印你的答案：

```
L  Q
G[0]  G[1] ... G[L-1]
```

这里，$L$ 是 `find_colours` 返回的数组 $G$ 的长度，$Q$ 是调用 `perform_experiment` 的次数。

hint:
考虑以下函数调用。

```
find_colours(4, [0, 1, 0, 0], [1, 2, 2, 3])
```

在这个例子中，假设顶点的（隐藏的）颜色是 $C = [2, 0, 0, 0]$，如下图所示。顶点的颜色同时也用数字标注在顶点右上角的标签里。

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

假设该函数以下列方式调用 `perform_experiment`。

```
perform_experiment([-1, -1, -1, -1])
```

这次调用没有重新着色任何顶点，因此所有顶点都保持它们原来的颜色。

顶点 $1$ 和顶点 $2$ 都是颜色 $0$ 的。因此路径 $1, 2$ 是单色路径，从而顶点 $1$ 和顶点 $2$ 在同一个单色分支中。

顶点 $1$ 和顶点 $3$ 都是颜色 $0$ 的。但是由于不存在连接它们的单色路径，因此它们在不同的单色分支中。

总共有 $3$ 个单色分支，分别是顶点集合 $\{0\}$、$\{1, 2\}$ 和 $\{3\}$。因此，本次函数调用返回 $3$。

再假设该函数以下列方式调用 `perform_experiment`。

```
perform_experiment([0, -1, -1, -1])
```

这次调用只把顶点 $0$ 重新着色成颜色 $0$，结果如下图所示。

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

此时所有顶点都属于同一个单色分支，因此本次函数调用返回 $1$。由此可以推断顶点 $1$、$2$ 和 $3$ 都是颜色 $0$ 的。

假设该函数还以下列方式调用 `perform_experiment`。

```
perform_experiment([-1, -1, -1, 2])
```

这次调用把顶点 $3$ 重新着色成颜色 $2$，结果如下图所示。

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

这时有 $2$ 个单色分支，分别是顶点集合 $\{0, 3\}$ 和 $\{1, 2\}$，因此本次函数调用返回 $2$。由此可以推断顶点 $0$ 是颜色 $2$ 的。

然后函数 `find_colours` 返回数组 $[2, 0, 0, 0]$。由于 $C = [2, 0, 0, 0]$，因此可以获得满分。

此外，也还有多种返回值，例如 $[1, 2, 2, 2]$ 或 $[1, 2, 2, 3]$，可以获得 $50\%$ 的分数。

### 约束条件

* $2 \le N \le 250$
* $N - 1 \le M \le \frac{N \cdot (N - 1)}{2}$
* 对所有满足 $0 \le j \lt M$ 的 $j$，都有 $0 \le X[j] \lt Y[j] \lt N$。
* 对所有满足 $0 \le j \lt k \lt M$ 的 $j$ 和 $k$，都有 $X[j] \neq X[k]$ 或 $Y[j] \neq Y[k]$。
* 每对顶点被某条路径连接。
* 对所有满足 $0 \le i \lt N$ 的 $i$，都有 $0 \le C[i] \lt N$。

| 子任务 | 分数  | 额外的约束条件 |
| :-----: | :----: | ---------------------- |
| 1       | $3$    | $N = 2$|
| 2       | $7$    | $N \le 50$|
| 3       | $33$   | 给定的图是一条路径：$M = N - 1$，且顶点 $j$ 和 $j+1$ 是相邻的（$0 \leq j < M$）。 |
| 4       | $21$   | 给定的图是完全图：$M = \frac{N \cdot (N - 1)}{2}$，且任意两个顶点是相邻的。 |
| 5       | $36$   | 没有额外的约束条件。 |

在每个子任务中，如果你的程序正确给出了每对相邻顶点是否具有相同颜色，那么也会获得部分分数。

更准确地说，如果在所有测试用例中 `find_colours` 返回的数组 $G$ 与数组 $C$ 完全一样（也就是对所有满足 $0 \le i \lt N$ 的 $i$，都有 $G[i] = C[i]$），你会获得该子任务的全部分数。否则，如果在某个子任务的所有测试样例中满足下列条件，你会获得该子任务 $50\%$ 的分数：

* 对所有满足 $0 \le i \lt N$ 的 $i$，都有 $0 \le G[i] \lt N$；
* 对所有满足 $0 \le j \lt M$ 的 $j$，都有：
  * $G[X[j]] = G[Y[j]]$ 当且仅当 $C[X[j]] = C[Y[j]]$。


title: 【MX-X6-T2】もしも

background:
> _もしも$\\$
数字がない世界だったら$\\$
生きる期限なんて$\\$
なかったのかな$\\$
もしもの話なら良かった$\\$
また出逢えるからって$\\$
言うんだ$\\$
またね。_
>
>_—— [もしも - Nanatsukaze / Dankidz](https://music.163.com/#/song?id=2102257032)_

除法能够帮我们消除这个世界上的数字吗？

如果不能，又能否让我们再次相见？

description:
假设有正整数序列 $a_1, a_2, \ldots, a_n$，其中：

- 对于 $i\geq 3$，满足 $a_i$ 等于 $\dfrac{a_{i-2}}{a_{i-1}}$ **上取整**；
- 对于任意 $1\leq i\leq n$，满足 $1\leq a_i\leq 10^9$。

现在给定 $n$ 和 $a_n$，求任意一组可能的 $a_1,a_2$。

其中一个数 $x$ 上取整等于最小的 $\geq x$ 的整数。例如 $\dfrac{7}{3}$ 上取整等于 $3$，$4$ 上取整等于 $4$。

inputFormat:
单个测试点包含多组测试数据，第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个空格分隔的整数表示该组数据的 $n,a_n$。

outputFormat: 对于每一组数据输出一行两个整数表示一组可能的 $a_1,a_2$。如有多种解可任意输出一种。可以证明本题数据范围下一定有解。


title: 「QMSOI R1」 生熏鱼

description:
一共有 $n$ 种攻击，第 $i$ 种攻击会先让你得到 $a_i$ 点经验，然后让你失去 $b_i$ 点血量。

你将**依次**受到 $k$ 次攻击，其中，第 $i$ 次攻击的种类是 $c_i$，你的初始血量为 $m$。

为了获得更多的经验，你可以选择 $n$ 种攻击中的任意种，并防止你受到的第一次这种攻击，防止后既不会损失血量，也不会增加经验值。

现在你想知道的是在你的血量降到 $0$ 及以下前，最多能获得多少点经验。

inputFormat:
一行 4 个整数，分别代表 $n,m,k,s$，其中，$s$ 为随机种子，其它变量含义与题目描述相同。

因为本题输入数据过大，选手需要使用如下方式获取数据：
~~~cpp
const int M=1e9,C=1e5+5;
void read(){
    cin>>n>>m>>k>>s;
    mt19937 rand(s);
    for(int i=1;i<=n;i++)  a[i]=rand()%M+1,b[i]=rand()%C+1;
    for(int i=1;i<=k;i++)  c[i]=rand()%n+1;
}
~~~
数组含义与题目描述中相同。

outputFormat: 输出一行一个整数，表示你最多能获得多少点经验。


title: 「QMSOI R1」 三服同构

description:
现在有 $4$ 种扑克牌：红桃 A，红桃 K，黑桃 A，黑桃 K，小 Q 的手上现在有 $n$ 张黑桃牌，$m$ 张红桃牌，其中有 $u$ 张黑桃 A，$v$ 张红桃 A，而对手有 $k$ 张牌。

现在小 Q 知道对手第 $i$ 张牌点数为 A 的概率为 $a_i$，接下来他将持续执行以下操作，直到他的回合结束。

1. 若你手中有至少 $1$ 张红桃 A 或红桃 K，则你**必须**等概率随机弃置 $1$ 张花色为红桃的牌，并与对手进行决斗。
2. 否则，你结束你的回合。

决斗的流程如下：

从对手开始，双方交替进行以下操作：

1. 若其手上有至少 $1$ 张红桃 A 或黑桃 A，则其**必须**等概率随机弃置 $1$ 张点数为 A 的牌。
2. 否则，其受到 $1$ 点伤害,并结束此次决斗。

现在你想要知道在你的回合结束前，对手期望会受到多少点伤害。

inputFormat:
第一行 $5$ 个整数分别表示 $n,m,u,v,k$。

第二行 $k$ 个实数，依次表示 $a_1,a_2,\cdots,a_k$。

outputFormat:
输出一行一个实数，表示期望伤害。

**本题使用 Special Judge 进行评测**，只要你的答案与标准输出**绝对误差**在 $10^{-6}$ 以内，则判定答案正确。

hint:
### 样例解释

可以得出对手牌中有 $0,1,2$ 张 A 的概率分别为 $0.16,0.68,0.16$。

当对手牌中有 $0$ 张 A 时，无论小 Q 每次耗费的哪张红色牌，都能对对手造成伤害，所以这种情况期望伤害为 $0.16*2=0.32$。

当对手牌中有 $1$ 张 A 时，假设小 Q 第一次耗费的是 A 进行决斗，那对手打出 A 后，小 Q 就会打出一张黑桃 A，对手没 A 了就会受到伤害，而小 Q 的另一张红桃 K 依然能被耗费，以进行决斗对对手造成伤害，所以这种情况期望伤害为 $0.68*0.5*2=0.68$。

当对手牌中有 $1$ 张 A 时，假设小 Q 第一次耗费的是 K 进行决斗，那对手打出 A 后，小 Q 打出黑桃 A 或红桃 A 的概率就是相等的，然后对手没 A 了就会受到伤害，但是如果打出的是红桃 A 就无法再进行决斗了，而打出黑桃 A 另一张红桃 A 依然被耗费，进行决斗对对手造成伤害，所以这种情况期望伤害为 $0.68*0.5*0.5*1+0.68*0.5*0.5*2=0.51$。

当对手牌中有 $2$ 张 A，这时如果小 Q 先耗费的 A 进行决斗，那对手打出 A 后，小 Q 就会打出一张黑桃 A，对手再打出 A 后，小 Q 就会受到伤害，而小 Q 的另一张红桃 K 依然能被耗费，以进行决斗对对手造成伤害，所以这种情况期望伤害为 $0.16*0.5*1=0.08$。

当对手牌中有 $2$ 张 A，这时如果小 Q 先耗费的 K 进行决斗，双方就会各打出两张 A，然后敌人受到伤害，小 Q 就不能再进行决斗了，所以这种情况期望伤害同样为 $0.16*0.5*1=0.08$。

所以对手受到的期望伤害就是 $0.32+0.68+0.51+0.08+0.08=1.67$。

### 数据范围
**本题使用 subtask 进行捆绑测试**，每个 subtask 的具体分值如下：
| 子任务 | 值域 | 分值 |
| :----------: | :----------: | :----------: |
| $0$ | $1\le n,m\le 10$ | $30$ |
| $1$ | $1\le n,m\le 2000$ | $70$ |

对于所有的数据，满足 $1 \leq n,m,k \leq 2000,1\le u<n,1\le v <m$。


title: [APC001] Ex - Separation

description:
小 I 有 $n$ 个工厂，坐落在 $A$ 地到 $B$ 地，第 $i$ 个工厂距离 $A$ 地的距离为 $a_i$ 千米。加工厂位于 $B$ 地，距离 $A$ 地 $x$ 千米，小 I 要把这些工厂里的货物运送到 $B$ 地的加工厂。

但是这天下了暴雨，仓库里的货物受潮了，每份货物每在仓库中或小 I 的背包中存放 $1$ 分钟，价值就会减少 $m$ 元钱。已知今天晚上每个工厂会生产出 $b_i$ 份货物，也知道每份货物会在暴雨来临几分钟后生产出来。

小 I 的初始体力为 $c$，速度为每分钟 $1$ 千米，但是他每行走 $1$ 千米就会减少一点体力（当体力为 $0$ 时不允许行走）。每次出发小 I 都要从 $A$ 地前往 $B$ 地，再返回 $A$ 地，他**只**在从 $A$ 地前往 $B$ 地时会带走沿途的工厂的仓库内所有被生产出的货物。他到达 $A$ 地后可以立刻再次出发。特别的，他可以在**负数时间点**出发，假定他的背包是无限大的，且货物重量与体力消耗无关。

小 I 为了亏损更少，制造了一个分身制造器。这个机器可以制造无数个他的分身，但是每一次出发最多只能制造一个分身，制造的分身与本体共用体力，**完全遵循第 $3$ 段所描述的操作**。小 I 需要保证在任何时候，现有体力都能支持每一个分身（包括本体）返回 $A$ 地的家。

小 I 做完准备工作后，发现暴雨已经下了 $k$ 分钟了，他迫切想要知道他最少要亏损（即货物减少的价值）多少元。他不会这个问题，于是他向你求助，想让你给出一种方案。

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

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

接下来，对于每组数据：

第一行五个整数 $n,m,x,c,k$。

接下来一行 $n$ 个整数 $a_1\sim a_n$。

接下来一行 $n$ 个整数 $b_1\sim b_n$。

接下 $n$ 行，每行 $b_i$ 个整数，表示第 $i$ 个工厂内的货物在第 $t_{i,j}$ 分钟后生产。

outputFormat:
对于每组数据：

若小 I 不可能将所有货物运送至加工厂并回家，输出一行一个 `-1`。

否则第一行一个整数，表示小 I 最少要亏损多少元。

接下来若干行，每行两个数，对于第 $i$ 行：

- 第一个数表示小 I 第 $i$ 次出发的时间（从他向你求助时计算），必须从小到大输出，时间可以为负。

- 第二个数表示这次出发是否需要制造一个新的分身，如果需要，输出 $1$，否则输出 $0$。

如果存在方案且方案输出完后，输出一行 `-1 -1`，表示方案结束。

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

对于样例 $3$ 的第一组数据解释：

小 I 在暴雨来临后 $1$ 分钟向你求助，你给出的方案是在暴雨来临后 $3$ 分钟，小 I 出门，在 $4$ 分钟到达 $1$ 号仓库，在 $5$ 分钟到达 $B$ 地，在 $7$ 分钟回到家，亏损 $3$ 元。

**【数据范围】**

对于全部数据，保证 $1\leq t\leq 10$，$1\leq n\leq 2\times 10^5,1\leq m,k,x\leq 10^6$，$1\le a_i\le x$，$0\leq c\leq 200$，$1\leq b_i\leq 10^5$，$\sum b_i\leq 2\times 10^5$，$0\leq t_{i,j}\leq 10^6$。

**本题输入量较大，请使用较快的读入方式。**

[原题面](https://www.luogu.com.cn/paste/iebvx9ko)


title: [IOI2024] 马赛克上色

background:
提交时请不要引用 `mosaic.h`。

请不要使用 C++14 (GCC 9) 提交。

description:
Salma 想给墙上的粘土马赛克上色。该马赛克由 $N \times N$ 片正方形瓷砖组成，共有 $N^2$ 片瓷砖；每片瓷砖的尺寸为 $1 \times 1$，都还没有上色。马赛克从上到下每行瓷砖的行编号从 $0$ 到 $N-1$，从左到右每列瓷砖的列编号从 $0$ 到 $N-1$。位于第 $i$ 行第 $j$ 列（$0 \leq i < N$，$0 \leq j < N$）的瓷砖记为 $(i,j)$。每片瓷砖要么涂成白色（记为 $0$），要么涂成黑色（记为 $1$）。

为了给马赛克上色，Salma 首先选取两个长度为 $N$ 的数组 $X$ 和 $Y$，每个数组都由 $0$ 和 $1$ 组成，并且 $X[0] = Y[0]$。她按照数组 $X$ 对最上面的行（第 $0$ 行）的瓷砖进行上色，使得瓷砖 $(0,j)$ 的颜色为 $X[j]$（$0 \leq j < N$）。她按照数组 $Y$ 对最左边的列（第 $0$ 列）的瓷砖进行上色，使得瓷砖 $(i,0)$ 的颜色为 $Y[i]$（$0 \leq i < N$）。

然后她重复以下步骤直至所有瓷砖都上色完成：
* 她找到任意一片**没有上色**的瓷砖 $(i,j)$，其上方相邻的瓷砖 $(i-1, j)$ 和左边相邻的瓷砖 $(i, j-1)$ 都**已经上色**。
* 然后，如果这两片相邻的瓷砖都是白色，她会把瓷砖 $(i,j)$ 涂成黑色；否则，涂成白色。

可以证明，瓷砖最终的颜色不依赖于 Salma 的上色顺序。

Yasmin 对马赛克瓷砖的颜色非常好奇。她向 Salma 提出 $Q$ 个问题，从 $0$ 到 $Q-1$ 编号。在问题 $k$（$0 \leq k < Q$）中，Yasmin 通过以下信息指定马赛克中的一个长方形：
* 最上面的行 $T[k]$ 和最下面的行 $B[k]$（$0 \leq T[k] \leq B[k] < N$）；
* 最左边的列 $L[k]$ 和最右边的列 $R[k]$（$0 \leq L[k] \leq R[k] < N$）。

问题的答案是该长方形中黑色瓷砖的数量。具体来说，Salma 应当找出有多少片瓷砖 $(i,j)$ 满足  $T[k] \leq i \leq B[k]$，$L[k] \leq j \leq R[k]$，且颜色为黑色。

请编写程序回答 Yasmin 的问题。

### 实现细节

你要实现以下函数。

```
std::vector<long long> mosaic(
	std::vector<int> X, std::vector<int> Y,
    std::vector<int> T, std::vector<int> B,
    std::vector<int> L, std::vector<int> R)
```

* $X$，$Y$：长度为 $N$ 的数组，分别描述最上方行和最左边列的瓷砖的颜色。
* $T$，$B$，$L$，$R$：长度为 $Q$ 的数组，分别描述 Yasmin 所提出的问题。
* 该函数应返回一个长度为 $Q$ 的数组 $C$，使得 $C[k]$ 给出问题 $k$（$0 \leq k < Q$）的答案。
* 对每个测试用例，该函数恰好被调用一次。

outputFormat:
评测程序示例按照如下格式打印你的答案：

```
C[0]
C[1]
...
C[S-1]
```

其中 $S$ 是  `mosaic` 所返回的数组 $C$ 的长度。


title: [语言月赛 202409] 重聚

description:
小紫和小蓝是一对双胞胎，但是在游乐场里走散了。然而她们有超能力。

当她们分开一段时间后，可以感应对方的位置，让二人重聚——然而如果距离太远，那么感应也无可奈何。

具体地：
- 小紫在分离时间 $\ge t_1$ 分钟时开启感应，如果她和小蓝距离不超过 $d_1$，那么可以感应到小蓝的位置。
- 小蓝在分离时间 $\ge t_2$ 分钟时开启感应，如果她和小紫距离不超过 $d_2$，那么可以感应到小紫的位置。

当双胞胎的一个人能感应到另一个人的位置，就可以行动使得两人重聚。

现在小紫和小蓝已经分离了 $t$ 分钟，当前距离为 $d$。她们都在原地等候。

请判断至少还需要几分钟，才能让双胞胎中的一个人感应到另一个人的位置？

inputFormat: 输入共有一行六个正整数 $t,d,t_1,d_1,t_2,d_2$，含义如题目描述所示。

outputFormat: 输出一行一个整数，表示至少还需要等几分钟。特别地，如果无论等待多久都无法感应到，输出 $-1$。

hint:
【样例 1 解释】

小紫在等待至少 $10$ 分钟后，能在距离不超过 $8$ 时感应到小蓝的位置。

小蓝在等待至少 $12$ 分钟后，能在距离不超过 $15$ 时感应到小紫的位置。

目前已经等待 $7$ 分钟，且两人距离为 $2$。再等待 $3$ 分钟，就能让小紫开启感应，并感应到小蓝了。

【样例 2 解释】

目前已经等待了 $11$ 分钟，小蓝在 $1$ 分钟前已经开启感应，并感应到小紫了，不需要额外等待。

【样例 3 解释】

无论双胞胎等多久，感应范围都达不到 $100$，所以永远无法感应到对方。

【数据范围】

对于全体数据，保证 $1\le t,d,t_1,d_1,t_2,d_2 \le 100$。


title: [语言月赛 202409] 距离

description:
迅风的班上一共有 $n$ 个人，学号为 $1\sim n$。每个同学都对班里其他所有同学有一个**好感度**，这个好感度始终是自然数。一开始每个人对其他人的**好感度**为 $0$。

接下来在这个班级里按时间顺序发生了 $m$ 件事情。每件事情发生后，会让一位同学对另一位同学的好感度增加或减少。

迅风想在**每一件事发生后**，立刻知道如果他随便选两个同学 $p,q$，那么 $p$ 对 $q$ 好感度的最大值是多少。你能帮帮他吗？

注意：好感度不是相互的。$p$ 对 $q$ 的好感度可以不等于 $q$ 对 $p$ 的好感度。

inputFormat:
输入的第一行有两个正整数 $n,m$，分别表示同学的人数和事情的个数。

之后有 $m$ 行，每行有四个正整数 $op,a,b,c$ 描述一次事情。
- 如果 $op$ 为 $1$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度增加了 $c$。
- 如果 $op$ 为 $2$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度减少了 $c$。

outputFormat: 输出共 $m$ 行，每行一个整数，表示一个同学对另一个同学的好感度最大值。


title: [语言月赛 202409] 始终

description:
如果一个只包含小写的字符串**首字母**与**尾字母**相同，那么字符串是“好的”。

给出一个由小写字母组成的字符串 $s$，请你求出它有多少**子串**是“好的”。

**子串**：一个字符串中，任意**连续**的字符构成的子字符串称为子串。
例如，字符串 `abc` 一共包含 7 个子串，分别为：空串（不包含任何字符)，`a`，`ab`，`abc`，`b`，`bc`，`c`。注意，字符串 `ac` **不是** `abc` 的子串。

inputFormat: 输入共一行，一个字符串 $s$。

outputFormat: 输出共一行，表示 $s$ “好的”子串的个数。

hint:
### 样例解释

对于第一组样例，只有 `a`，`b`，`c` 三个“好的”子串。

对于第二组样例，共有 `a`，`b`，`c`，`b`，`a`，`bcb`，`abcba` 七个“好的”子串。

### 数据范围

$|s|$ 表示字符串 $s$ 的长度。

对于 $20\%$ 的数据，$1 \le |s| \le 30$，字符串只包含小写字母 `a`。

对于 $30\%$ 的数据，$1 \le |s| \le 30$。

对于 $60\%$ 的数据，$1 \le |s| \le 500$，字符串由小写字母组成。

对于 $100\%$ 的数据，$1 \le |s| \le 5000$，字符串由小写字母组成。


title: [APC001] E - Linear Map

background:
**请注意本题的特殊时间限制，并酌情使用较快的输入输出方式**。

在广阔的 florr 世界中，有一个不为人知的角落，它的建立是为了方便快速测试新 mob，而现在它被废弃了，但没有消失。

冒险者 MF 找到了这里，并发现其名字为：Linear map。

description:
Linear map 可看作一个字符串，每个字符都是一个 $0\sim 9$ 的数字。

MF 认为，如果一个字符串存在两段长度均 $>1$ 的不同区间的和相同，那么该字符串是无趣的。

比如，$3421$ 就是无趣的字符串，因为 $3+4=4+2+1$，而 $5023$ 也是无趣的字符串，因为 $5+0=2+3$。相反，$13$ 和 $285$ 都不是无趣的字符串。

MF 打算将 Linear map 划分为若干非空连续且不重复的子段，这些子段包含了整个字符串的所有字符，且满足每个子段都不是无趣的字符串。

MF 是一个有趣的人，于是它想算出划分的方案数，并对 $998244353$ 取模。

inputFormat: 一行一个字符串 $s$。

outputFormat: 一行一个整数表示答案对 $998244353$ 取模后的结果。


title: 【MX-X4-T0】「Jason-1」x!

description:
给定一个非负整数 $n$，判断 $n!$ 是否是 $n+1$ 的倍数，如果是则输出 `YES`，否则输出 `NO`。

其中 $n!$ 表示 $n$ 的阶乘，其值为所有小于等于 $n$ 的正整数的乘积。例如 $3! = 1 \times 2 \times 3 = 6$。并额外规定 $0! = 1$。

inputFormat: 仅一行，一个非负整数 $n$。

outputFormat: 仅一行一个字符串 `YES` 或 `NO`，表示 $n!$ 是否是 $n+1$ 的倍数。

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

$0! = 1$，而 $1$ 是 $1$ 的倍数，故输出 `YES`。

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

$3! = 1 \times 2 \times 3 = 6$，而 $6$ 不是 $4$ 的倍数，故输出 `NO`。

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

$6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$，而 $720$ 不是 $7$ 的倍数，故输出 `NO`。

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

$7! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7= 5040$，而 $5040$ 是 $8$ 的倍数，故输出 `YES`。

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

$15! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 \times 11 \times 12 \times 13 \times 14 \times 15 = 1{,}3076{,}7436{,}8000$，而 $1{,}3076{,}7436{,}8000$ 是 $16$ 的倍数，故输出 `YES`。

**【数据范围】**

本题共有 $20$ 个测试点，第 $i$ 个测试点的 $n$ 为 $i-1$。

对于 $100\%$ 的数据，$0 \le n \le 19$。


title: 【MX-X4-T1】「Jason-1」IO++

description:
有一类只有输入语句与输出语句的程序，我们用一个非负整数序列 $[a_1, a_2, \ldots]$ 描述它。

该程序将从前往后依次执行，对于第 $i$ 个元素 $a_i$：

- 若 $a_i = 0$，表示一条输入语句：
	- 程序将从输入中读取一个整数。
- 否则，表示一条输出语句：
	- 程序将输出第 $a_i$ 次输入读取到的整数。
	- 对于给出的程序，保证执行本语句前，程序至少进行了 $a_i$ 次输入。对于你编写的程序，你同样需要保证这一点。

特别地，一个长度为 $0$ 的空程序也是合法的。

给定一个长度为 $n$ 的程序 $[b_1, \ldots, b_n]$，你需要求出能够实现相同的功能的程序所需的最短长度。

两个程序能实现相同功能，当且仅当对于任意的长度为 $10^{10^{10}}$、值为 $[1, 10^{10^{10}}]$ 之内整数的输入，两个程序执行的输出语句次数相同，且每一次输出的结果均一致。

inputFormat:
第一行，一个正整数 $n$，表示程序的长度。

第二行，$n$ 个非负整数 $b_1, \ldots, b_n$，描述了一个程序。

outputFormat: 仅一行一个整数，表示要实现相同功能的程序所需要的最小长度。

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

长度为 $4$ 的程序 $[0,0,1,2]$，$[0,1,0,2]$ 均可以实现相同的功能。可以证明不存在长度 $\leq 3$ 且实现了相同功能的程序，所以答案为 $4$。

- 对于输入 $[2, 3, 4, \ldots]$，程序 $[0, 0, 0, 1, 2]$ 和 $[0, 0, 1, 2]$ 和 $[0, 1, 0, 2]$ 的输出均为 $[2, 3]$，符合题意。
- 可以验证，对于任意的长度为 $10^{10^{10}}$、值为 $[1, 10^{10^{10}}]$ 之内整数的输入，两个程序执行的输出语句次数相同，且每一次输出的结果均一致。

但是，程序 $[0,1,1]$ 无法实现相同的功能，因为对于输入 $[2, 3, 4, \ldots]$，该程序的输出为 $[2, 2]$，与原程序的 $[2, 3]$ 不相同，故不能实现相同功能。

程序 $[0,1,2]$ 是不合法的程序，因为运行第 $3$ 条指令（即一条输出语句 $a_i = 2$）时，只执行了 $1$ 次输入语句。

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

不存在更短的程序能实现相同功能。

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

长度为 $5$ 的程序 $[0,1,0,2,1]$ 可以实现相同功能。

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

由于没有输出语句，因此长度为 $0$ 的空程序即可实现相同功能。

**【数据范围】**

对于 $50\%$ 的数据，保证 $b_1, \ldots, b_n$ 非严格单调递增，即对于任意 $2 \le i \le n$ 均有 $b_{i-1} \le b_i$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le b_i \le n$，且保证执行任何输出语句 $b_i$ 前，程序至少进行了 $b_i$ 次输入。


title: 「KDOI-10」水杯降温

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

**本场比赛所有题目从标准输入读入数据，输出到标准输出。**

description:
小 S 有一棵包含 $n$ 个节点的有根树，且根为节点 $1$。节点 $i$ $(1\le i\le n)$ 上放置了一个初始水温为 $a_i$ 的水杯。

在不知道水温的情况下拿起水杯喝水并被烫了 inf 次的小 S 决定将这些水杯的水温全部变为 $0$ 后再喝它们。

现在，小 S 可以分别进行以下两种操作任意次：

* 使用一个在节点 $i$ 的加热装置。这会使以 $i$ 为根的子树内所有水杯里的水温均增加 $1$；
* 或者，从某个**叶子**节点 $i$ 向根方向吹一阵风。这会使 $i$ 到根所有水杯里的水温均减少 $1$。

请你帮小 S 判断：能否将所有节点上的水杯的水温都变为 $0$。

inputFormat:
从标准输入读入数据。

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

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

- 第一行包含一个正整数 $n$，表示节点数量。
- 第二行 $n-1$ 个正整数 $f_2,\dots,f_n$，$f_i$ 表示 $i$ 节点的父亲节点编号。保证 $f_i<i$。
- 第三行 $n$ 个整数 $a_i$，表示初始水温。

outputFormat:
输出到标准输出。

对于每组测试数据：

- 如果可以将水温变为 $0$，输出一行一个字符串 `Huoyu`；
- 如果无法将水温变为 $0$，输出一行一个字符串 `Shuiniao`。


title: [入门赛 #27] 数字 (Hard Ver.)

background:
> 如果我说不吻你不罢休\
> 谁能逼我将就\
> ——李荣浩《不将就》

人生不能将就，是否做出了最好的选择，取决于每个人自己。

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

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

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

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

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


title: [GESP202409 一级] 小杨购物

description:
小杨有 $n$ 元钱用于购物。商品 A 的单价是 $a$ 元，商品 B 的单价是 $b$ 元。小杨想购买**相同数量**的商品 A 和商品 B。

请你编写程序帮助小杨计算出他最多能够购买多少个商品 A 和商品 B。

inputFormat:
第一行包含一个正整数 $n$，代表小杨用于购物的金额。

第二行包含一个正整数 $a$，代表商品 A 的单价。

第三行包含一个正整数 $b$，代表商品 B 的单价。

outputFormat: 输出一行，包含一个整数，代表小杨最多能够购买的商品 A 和商品 B 的数量。

hint:
### 样例 1 解释

对于样例 1，由于需要购买相同数量的两种商品，因此⼩杨最多能够购买 $4$  件商品 $A$ 和 $4$ 件商品 $B$，共花费 $1 \times 4 + 2 \times 4 = 12$ 元。因此，样例 1 的答案为 $4$。

### 样例 2 解释

对于样例 1，由于需要购买相同数量的两种商品，因此⼩杨最多能够购买 $4$  件商品 $A$ 和 $4$ 件商品 $B$，共花费 $1 \times 4 + 2 \times 4 = 12$ 元。因此，样例 1 的答案为 $4$。如果小杨想购买 $5$ 件商品 $A$ 和商品 $B$，则需要花费 $1 \times 5 + 2 \times 5 = 15$ 元，超过了小样的预算 $13$ 元。因此，样例 2 答案为 $4$。

### 数据规模与约定

对全部的测试数据，保证 $1 \leq n,a,b \leq 10^5$。


title: [GESP202409 一级] 美丽数字

description:
小杨有 $n$ 个正整数，他认为一个正整数是美丽数字当且仅当该正整数是 $9$ 的倍数但不是 $8$ 的倍数。

小杨想请你编写一个程序计算 $n$ 个正整数中美丽数字的数量。

inputFormat:
第一行包含一个整数 $n$，代表正整数个数。
第二行有 $n$ 个正整数 $a_1, a_2, \dots a_n$。

outputFormat: 输出一个整数，表示其中美丽数字的数量。

hint:
### 样例 1 解释

- $1$ 既不是 $9$ 的倍数也不是 $8$ 的倍数。
- $9$ 是 $9$ 的倍数不是 $8$ 的倍数。
- $72$ 既是 $9$ 的倍数又是 $8$ 的倍数。

### 数据规模与约定

对全部的测试数据，保证 $1 \leq n, a_i \leq 10^5$。


title: 「CMOI R1」图上交互题 / Constructive Minimum Xor Path

background:
2024 年 1 月 13 日 15:59:31，随着最后一发交互 J 题的提交出现了 Wrong Answer，小 G 的 EC-Final 比赛结束了，也意味着在 ICPC 生涯中第一次打铁。

痛定思痛，小 G 决定批量生产交互题给自己做。如何批量生产交互题？只要在一个数据结构中有若干个未知量 $a_i$，每次询问给定向量 $x$，交互库会返回关于 $a_i$ 的函数 $f(x)$，这样就能批量生产交互题了！

~~那为什么这题并不是交互题呢。~~

description:
给定一个 $n$ 个点，$m$ 条边的**无向图**。第 $i$ 条边 $(u_i,v_i)$ 有一个**未知边权** $a_i$。

对于任何一条**路径**，定义其**代价**如下：设路径为 $(p_0,p_1,...,p_k)$，其中要求 $(p_{i-1},p_i)$ 是无向图中的边，设其为第 $e_i$ 条边。那么路径的代价即为 $\bigoplus\limits_{i=1}^{k} a_{e_i}$。其中 $\bigoplus$ 表示异或。（该路径可以经过重复点和重复边，即 $p$ 和 $e$ 可以包含重复的数）

定义 $f(x,y)$ 为从 $x$ 到 $y$ 的所有路径中代价的**最小值**。特别地，当 $x=y$ 时，$f(x,y)=0$。

给定 $n,m$，再对于每条边 $(u_i,v_i)$ 给定 $f(u_i,v_i)$，你需要求出是否存在一组合法的 $a_i$，如果有解，你还需要构造一组解。

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

第 $2\sim m+1$ 行每行两个正整数 $u_i,v_i$ 和一个非负整数 $f(u_i,v_i)$。

**请注意：本题并不保证图连通；可能会存在重边和自环。**

outputFormat:
如果不存在解，则仅输出 `No`。

否则，在第一行输出 `Yes`，在第二行输出 $m$ 个非负整数 $a_i$ 表示一组合法的解。

答案可能有很多组，此时输出任意一组解即可。你需要保证 输出的 $0\le a_i<2^{63}$。

hint:
### 样例解释

答案输出的图如下：

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

考虑 $f(1,2)$：

+ 考虑路径 $1\rightarrow 2$，路径的代价为 $2$。

+ 考虑路径 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2$，路径的代价为 $2\oplus3\oplus114514\oplus2=114513$。

此外还存在其他路径，但可以证明不存在代价比 $2$ 更小的路径，故 $f(1,2)=2$。

### 数据范围

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

|$\text{Subtask}$ |特殊性质|分数|
|-:|-:|-:|
|$1$|保证有解|$20$|
|$2$|$m\le n+10$|$30$|
|$3$||$50$|

对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^5$，$1\le u_i,v_i\le n$，$0\le f(u_i,v_i)<2^{31}$。


title: [ROI 2024 Day 1] 机器人物流

background:
翻译自 [ROI 2024 D1T1](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day1.pdf)。

在 ROI 2224 举办之时，一群能够克隆自身的机器人负责送货。人们不用出门，可以直接通过窗户拿到货物。

最开始只有一个送货机器人。在任何时候，最上面的机器人可以在自己上方克隆出一个或多个新的机器人，形成一个“机器人柱”。每个机器人的高度等于一层楼。

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

在送货过程中，机器人柱会沿着宿舍楼从左到右移动。机器人的数据库中包含了订单列表，每个订单都指定了一个需要送货的窗户。当机器人队列经过一个窗户时，如果队列中有机器人位于窗户所在的高度，则可以直接完成送货。

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

在移动过程中，机器人柱可能会碰到障碍物。碰到障碍物后，只有位于障碍物高度上方的机器人能够继续移动。这些机器人在经过障碍物后会立刻重新排成一个机器人柱，并且可以继续移动、克隆和完成送货任务。

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

障碍物和窗户之间的距离足够大，因此机器人在经过障碍物时不会同时经过窗户。

description:
每完成一个订单，机器人公司会获得 $p$ 个虚拟货币，而克隆一个新机器人的成本是 $c$ 个虚拟货币。最终利润等于订单配送的总收入减去所有机器人克隆的总成本。公司希望最大化利润。请你确定公司可以获得的最大利润。

公司不需要完成所有订单，且机器人可以在任何时候停止送货。

inputFormat:
第一行包含四个整数 $n, m, c, p$（$0 \le n, m \le 100000$，$1 \le c, p \le 1000000$），分别表示障碍物的数量、订单的数量、克隆一个机器人的成本和每个订单的配送收入。

接下来的 $n + m$ 行描述了障碍物和窗户的详细信息，按从左到右的顺序给出。每行包含两个整数 $t_i$ 和 $h_i$（$1 \le t_i \le 2$，$1 \le h_i \le 1000000$），其中 $t_i$ 表示对象的类型（$1$ 为障碍物，$2$ 为窗户），$h_i$ 表示障碍物的高度或窗户所在的楼层。

保证有 $n$ 个障碍物，剩余 $m$ 个为窗户。

outputFormat: 输出一个整数，表示可以获得的最大利润。

hint:
样例 $1$ 解释：

以下是订单配送的最佳策略之一，如果选择配送到第二个窗户，不会增加公司的利润。

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

样例 $2$ 解释：

只需要克隆一次机器人，用来配送到第一个窗户，因为这个新克隆的机器人可以继续用来配送到第二个窗户。为了配送到第三个窗户而进行额外的克隆在经济上是不划算的。

下面是各个子任务的分值和特殊性质表格。全部数据范围见输入格式。

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $24$ | $n\le100,m\le100,h_i\le100$ |
| $2$ | $12$ | $n=0$ |
| $3$ | $14$ | $n=1$ |
| $4$ | $15$ | $m=1$ |
| $5$ | $17$ | $c=1,p=10^6$ 且障碍物高度均为 $1$ |
| $6$ | $18$ | 无 |


title: [ROI 2024 Day 1] 2026

background:
翻译自 [ROI 2024 D1T2](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day1.pdf)。

一款新的游戏《2026》在一个 $m$ 行 $n$ 列的矩形盘面上进行。盘面被划分为 $m \times n$ 个 $1 \times 1$ 的小格子。在一些格子上放置了大小为 $1 \times 1$ 的方块，每个方块上写有一个英文字母。

你需要进行 $q$ 次操作，每次操作都是将所有方块向一个方向移动到底。因此，操作序列由一个长度为 $q$ 的字符串 $s$ 给出，字符串中每个字符表示一个方向：`L` 表示向左移，`R` 表示向右移，`U` 表示向上移，`D` 表示向下移。

具体操作与游戏《2048》相类似：在棋盘上，只要有一个方块在指定方向上相邻的格子是空的，该方块就会移动到该空格子上，包括它后面的那些方块也会连带着向那个方向一起移动，直到前方没有空格。

description: 给出棋盘的初始状态和操作序列，请确定所有操作执行完成后盘面的状态。

inputFormat:
输入包含多组数据。

- 第一行输入一个整数 $t$ ，表示测试数据的组数（$1 \le t \le 200 000$）。
- 对于每组数据：
  - 第一行输入整数 $m$ 和 $n$，代表盘面的大小（$1 \le m, n \le 10^6$，$1 \le m \times n \le 10^6$）。
  - 接下来的 $m$ 行，输入盘面的初始状态：
    - 其中的第 $i$ 行（$1 \le i \le m$）包含一个长度为 $n$ 的字符串 $a_{i1}a_{i2}\dots a_{in}$，表示第 $i$ 行的盘面状态。
    - 每个字符 $a_{ij}$ 要么是小写英文字母（从 `a` 到 `z`），要么是点号 `.`。如果 $a_{ij}$ 是 `.`，则表示第 $i$ 行第 $j$ 列的格子为空，否则表示该格子上有一个标有字母 $a_{ij}$ 的方块。
  - 最后一行输入一个字符串 $s$，由 $q$ 个字符组成，表示操作的序列（$1 \le q \le 10^6$）。每个字符都是 `L`，`R`，`U`，`D` 之一。

所有测试数据中 $m \times n$ 的总和不超过 $2 \times 10^6$，$q$ 的总和不超过 $2 \times 10^6$。

outputFormat: 对于每组数据，输出执行完所有操作后的盘面，格式与输入相同。

samples:
4
4 4
.a.b
..e.
....
.cd.
LRU
1 1
.
UULLRRDD
1 6
.a.aa.
LLURDDD
5 7
.ba.b..
ac..c.d
e......
....da.
d.eae..
DLDDRULRRR

hint:
样例解释：

在第一组输入数据中，盘面最初看起来是这样的：

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

第一次操作将所有方块向左移动。接着，盘面会变成这样：

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

第二次操作将所有方块向右移动。接着，盘面会变成这样：

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

第三次，也是最后一次操作将所有方块向上移动。所有操作结束后，盘面会变成这样：

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

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $9$ | $t=1,q=1,n,m\le100$ |
| $2$ | $7$ | $s_i$ 只可能为 `L` 或 `R` |
| $3$ | $13$ | $\sum mnq\le10^7$ |
| $4$ | $14$ | $s_i$ 只可能为 `L` 或 `R` 或 `U` |
| $5$ | $12$ | 棋盘上所有字母都是 `a`，$\sum mq\le10^7$ |
| $6$ | $11$ | 棋盘上所有字母都是 `a` |
| $7$ | $9$ | 棋盘初始状态是“阶梯状”的，具体地，第 $i$ 行仅最左侧恰有 $i-1$ 个字母 |
| $8$ | $14$ | $s$ 是重复若干次的 `LURD` |
| $9$ | $11$ | 无 |


title: [ROI 2024 Day 1] 小推车

background:
翻译自 [ROI 2024 D1T3](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day1.pdf)。

航空公司提供了一种新型的商务舱，飞机上的座位沿着过道排列。假设座位总数为 $n$，座位的坐标从 $1$ 到 $n$。

每个乘客都有一个饮料偏好，饮料的种类共有 $k$ 种，编号从 $1$ 到 $k$。每个乘客只能选择一种饮料。在飞机上，饮料需要从一辆小推车上分给乘客。

饮料装在一个瓶子里，每个瓶子的饮料可以服务 $p$ 个乘客。也就是说，一个瓶子的容量为 $p$。小推车最多可以装载 $m$ 个瓶子。保证 $k\le m$。

小推车从座位前方的起点（坐标为 $0$）开始移动，并最终到达终点（坐标为 $n + 1$）。在小推车服务乘客的过程中，它可能需要去往储藏室中装载新的饮料。储藏室可能位于飞机前部的起点处，也可能位于后部的终点处，也有可能两侧都有。

如果小推车在座位 $i$ 的位置，它需要移动到起点处的储藏室的距离是 $i$，而到达终点处的储藏室的距离是 $n + 1 - i$。小推车在行进过程中可能需要补充饮料，如果小推车到达储藏室，它可以卸下空的瓶子，并装载新的饮料。不可以卸下还装有饮料的瓶子。在补充饮料后，小推车应该回到第一个未提供饮料的乘客的位置，再继续向后为乘客提供服务。

description: 你需要计算小推车从 $0$ 移动到 $n + 1$ 的最小总移动距离，以便为所有乘客提供所需的饮料。

inputFormat:
第一行包含四个整数 $n$，$m$，$k$ 和 $p$，分别表示座位数量、小推车所装瓶子的容量、饮料种类数量和每个瓶子所装饮料的容量。

第二行包含一个整数 $c$，表示储藏室的位置，$c$ 的取值范围是 $1$ 到 $3$。$c=1$ 表示储藏室只在终点位置；$c=2$ 表示储藏室只在起点位置；$c=3$ 表示储藏室在起点和终点都有。

第三行包含 $n$ 个整数 $a_i$，表示第 $i$ 个座位的乘客需要的饮料的类型。

outputFormat: 输出一个整数，表示小推车在服务所有乘客的过程中所需的最小移动距离。

hint:
在第一个样例中，小推车可以装载 $m = 2$ 个瓶子，每瓶含 $p = 1$ 份饮料。储藏室位于客舱的尽头。
- 首先，小推车需要装上饮料 $1$ 和 $2$，这些饮料将分发给座位 $1$ 和 $2$ 的乘客，小推车需要行驶 $2$ 的距离从起点 $0$ 到点 $2$，即 $d_1=2$。
- 接着，小推车需要前往客舱尽头的储藏室（距离为 $4$），装上饮料 $1$ 和 $2$，然后返回到座位 $3$（小推车需要移动 $3$ 的距离）。$d_2=4+3=7$。
- 然后，小推车要为座位 $3$ 和 $4$ 的乘客提供饮料 $1$ 和 $2$（小推车在座位 $3$ 和 $4$ 之间移动 $1$ 的距离）。$d_3=1$。
- 最后，小推车需要再次前往储藏室（从座位 $4$ 到储藏室的距离为 $2$），装上饮料 $1$，从储藏室返回到座位 $5$（距离为 $1$），服务完该乘客后再移动 $1$ 的距离到客舱尽头。$d_4=2+1+1=4$。

总距离为 $d_1+d_2+d_3+d_4=2+7+1+4=14$。

在第二个样例中，小推车可以装载 $m = 3$ 个瓶子，每瓶含 $p = 2$ 份饮料。储藏室位于客舱的前端。小推车需要装满 $3$ 瓶饮料 $1$，服务座位 $1$ 到 $4$ 的乘客。之后，$2$ 瓶饮料 $1$ 将被用完，需要立刻前往储藏室装满 $2$ 瓶饮料 $2$，然后服务座位 $5$ 到 $8$ 的乘客（如果在服务完乘客 $5$ 后再回储藏室补充饮料，则要移动更长的距离）。

在第三个样例中，小推车可以装载 $m = 3$ 个瓶子，每瓶含 $p = 2$ 份饮料，储藏室分别位于客舱的两端。为了服务乘客，需要 $2$ 瓶饮料 $2$，以及饮料 $1$ 和 $3$ 各 $1$ 瓶，因此需要去储藏室更换空瓶。最好的方案是在服务完座位 $3$ 的乘客后，再去客舱前端的储藏室换取饮料 $2$。

在第四个样例中，小推车需要装载每种饮料各 $1$ 瓶，并且由于每瓶含 $2$ 份饮料，这样可以在不额外补充的情况下服务所有乘客。

在第五个样例中，需要进行两次补充，小推车在服务完乘客 $3$ 后需要第一次返回客舱开头的储藏室，第二次则是在服务完乘客 $6$ 后去到客舱尽头的储藏室。

原题目有十二个子任务，由于洛谷限制这里不能全部上传。

对于 $100\%$ 的数据，$3\le n\le 10^6,1\le p\le 10^6,1\le a_i\le k\le m\le 10^6,1\le c\le3$。


title: [ROI 2024 Day 1] 白菜

background:
翻译自 [ROI 2024 D1T4](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day1.pdf)。

拉马赞决定从事一个重要的业务——种植白菜。种植白菜的场地是一个无限大的网格场地。每个网格单元可以种植一个白菜。拉马赞只种植了场地的一部分。他计划利用其中的几个矩形区域，这些矩形可能会相交。如果一个网格单元位于至少一个矩形内，则该单元被认为种植了白菜。

具体地，拉马赞选择了 $n$ 个矩形区域，矩形的坐标为 $(x_{L_i}, y_{L_i}, x_{R_i}, y_{R_i})$ (其中 $x_{L_i} \le x_{R_i}$，$y_{L_i} \le y_{R_i}$，$1 \le i \le n$)。如果存在至少一个矩形 $i$ ($1 \le i \le n$)，使得 $x_{L_i} \le x \le x_{R_i}$ 且 $y_{L_i} \le y \le y_{R_i}$，则认为网格单元 $(x, y)$ 被种植了白菜。

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

拉马赞曾经是一个程序员（并且还是一个获奖者），因此他决定使用人工智能机器人定期处理种植。一个机器人可以服务于任意的水平区域 $(x_{\text{robot}_1}, x_{\text{robot}_2}, y_{\text{robot}})$，即所有满足 $x_{\text{robot}_1} \le x \le x_{\text{robot}_2}$ 且 $y = y_{\text{robot}}$ 的网格单元 $(x, y)$。

重要的是，机器人只能在种植的区域内移动。他明白，为了最小化机器人的数量，需要使用那些不能进一步扩展的水平区域。如果满足以下条件，拉马赞将使用机器人在网格单元 $(x_{\text{robot}_1}, x_{\text{robot}_2}, y_{\text{robot}})$ 上工作：

- 所有满足 $x_{\text{robot}_1} \le x \le x_{\text{robot}_2}$ 且 $y = y_{\text{robot}}$ 的网格单元 $(x, y)$ 都属于种植区域；
- 网格单元 $(x_{\text{robot}_1} - 1, y_{\text{robot}})$ 不属于种植区域；
- 网格单元 $(x_{\text{robot}_2} + 1, y_{\text{robot}})$ 不属于种植区域。

description:
你需要收集有关机器人在种植区域工作的统计信息。如果存在一个机器人恰好在网格段 $(x_1, x_2, y)$ 上工作，我们说 $(x_1, x_2)$ 在行 $y$ 上被服务。具体地，你需要：

- 找出所有在某一行中被服务的 $(x_1, x_2)$ 对。
- 对于每一对这样的 $(x_1, x_2)$，找出它被服务的行数。
- 对于每一对这样的 $(x_1, x_2)$，找出它被服务的最大连续行数。换句话说，找出最大值 $k$，使得存在一个长度为 $k$ 的连续行区间 $[y_1, y_2]$（其中 $y_2 - y_1 + 1 = k$），使得在任意行 $y_1 \le y \le y_2$ 中，该对 $(x_1, x_2)$ 都被服务。

inputFormat:
输入包含多组数据。第一行给出一个整数 $t$（$1 \le t \le 200000$），表示测试数据的组数。

每组数据的第一行给出一个整数 $n$（$1 \le n \le 200000$），表示矩形区域的数量。

接下来的 $n$ 行中，每行包含四个整数 $x_{L_i}$，$y_{L_i}$，$x_{R_i}$，$y_{R_i}$（$1 \le x_{L_i} \le x_{R_i} \le 10^9$，$1 \le y_{L_i} \le y_{R_i} \le 10^9$），表示一个矩形区域。

令 $N$ 表示所有数据集中的 $n$ 总和，保证 $N \le 200000$。

outputFormat:
对于每组数据，首先输出一个整数 $p$（$p \ge 1$），表示在某一行中被服务的 $(x_1, x_2)$ 对的数量。接下来 $p$ 行中，每行输出四个整数 $x_1$，$x_2$，$cnt$，$k$（$1 \le x_1 \le x_2 \le 10^9$，$0 \le cnt, k \le 10^9$）。其中，$cnt$ 是该对 $(x_1, x_2)$ 被服务的行数，$k$ 是它被服务的最大连续行数。

每一对 $(x_1, x_2)$ 必须是不同的。每一对在某一行中被服务的 $(x_1,x_2)$ 对，必须输出且只能输出一次。输出顺序可以是任意的。

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

在第一组数据中，机器人在以下区段进行服务：$(2, 3, 2)$，$(2, 4, 3)$ 和 $(3, 4, 4)$。因此，对 $(2, 3)$，$(2, 4)$ 和 $(3, 4)$ 在某一行中得到服务，并且每对都只在一行中被服务。

在第二组数据中，机器人在以下区段进行服务：$(2, 2, 1)$，$(2, 4, 2)$ 和 $(2, 2, 3)$。因此，对 $(2, 2)$ 和 $(2, 4)$ 在某一行中得到服务。对 $(2, 2)$ 在第 $1$ 行和第 $3$ 行中得到服务，而对 $(2, 4)$ 在第 $2$ 行中被服务。

下面是第三和第四组数据的图片。

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

- 如果你的程序错误地找出了在某一行中被服务的对 $(x_1, x_2)$ 的集合，该测试点将获得零分。
- 如果你的程序：
  - 能够正确找出该集合，但不是所有的 $cnt$ 都正确，该测试点将获得 $50\%$ 的分数。
  - 能够正确找出该集合和所有 $cnt$，但不是所有的 $k$ 都正确，该测试点将获得 $75\%$ 的分数。
  - 能够正确找出该集合、所有 $cnt$ 和所有 $k$，该测试点将获得 $100\%$ 的分数。

请注意，如果你想获得获得部分分，仍需为每对配对 $(x_1, x_2)$ 输出一些 $cnt$ 和 $k$ 值，但不必全部正确。


title: [ROI 2024 Day 2] 割草

background:
翻译自 [ROI 2024 D2T1](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day2.pdf)。

草坪需要由电动割草机器人割草。我们认为草坪是一个数轴上的线段，其中在某些点上有割草机器人。机器人的大小可以忽略不计。一个机器人位于草坪的起点（起点左侧没有草坪），另一个机器人位于终点（终点右侧没有草坪）。每个机器人最初朝一个方向行驶：要么向右，要么向左。

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

第 $i$ 个机器人的电量足够处理 $p_i$ 米的草坪。所有机器人在夜间充电后同时启动，并以相同的速度移动。每个机器人沿直线朝其方向移动。机器人在以下三种情况下停止：
1. 如果机器人的电量耗尽。换句话说，若第 $i$ 个机器人从起点行驶了 $p_i$ 米。
2. 如果机器人到达了草坪的起始点或终点。
3. 如果机器人在某处遇到了另一个朝相反方向行驶或停在此处的机器人。

description: 在启动机器人之前，可以将某些机器人的方向更改为相反方向。为了割光整个草坪，你需要确定最少需要改变方向的机器人数量，使得最终整个草坪都能被割光。如果无论如何都无法使得整个草坪被割完，输出 `-1`。

inputFormat:
第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示机器人的数量。

接下来的 $n$ 行，每行描述一个机器人，按从左到右的顺序给出。每个机器人由三个整数 $x_i$, $p_i$, $d_i$ 描述，它们分别是机器人的初始位置、它可以行驶的距离以及行驶方向（$0 = x_1 < x_2 < \cdots < x_n \leq 10^9$，$1 \leq p_i \leq 10^9$，$d_i = -1$ 表示向左行驶，$d_i = 1$ 表示向右行驶）。草坪的起始点和终点分别位于点 $x_1 = 0$ 和 $x_n$。

outputFormat: 无法割光整个草坪，输出 `-1`。否则，输出一个数字，表示需要更改方向的机器人的数量，使得草坪能被割光。


title: [ROI 2024 Day 2] 交互式通道

background:
翻译自 [ROI 2024 D2T2](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day2.pdf)。

ROI 的举办地 Innopolis 大学由 $n$ 个建筑物和 $m$ 条通道组成。每条通道连接两个不同的建筑物，任何两个建筑物之间不会有多于一条通道。

已知每个建筑物都有一个可以打开或关闭的灯光。最初，所有建筑物的灯光都是关闭的。校园管理员可以在一个操作中打开或关闭任何一个建筑物的灯光。管理员还可以在灯光已经打开的情况下按下开灯按钮，或在灯光已经关闭的情况下按下关灯按钮。这些操作不会改变建筑物的灯光状态。

类似地，每条通道也有一个可以打开或关闭的灯光。最初，所有通道的灯光也都是关闭的。但与建筑物的灯光不同，通道的灯光会自动变化：如果在管理员的操作后，该通道连接的两所建筑物的灯光状态相同，那么通道的灯光也会变为相同的状态，否则它不会改变。

换句话说，如果在管理员的操作后，连接的两个建筑物的灯光都关闭，则通道的灯光也会关闭。如果连接的两个建筑物的灯光都打开，则通道的灯光也会打开。如果一个建筑物的灯光打开而另一个关闭，则通道的灯光状态不变。

description: 在 ROI 开始之前，校园主任为每个建筑物和每条通道确定了它们是否应该被照亮。请你检查管理员是否可以通过任意数量的操作来实现主任的要求。如果可以，请找到任何一种满足要求的操作序列。能够正确判断是否可以得到期望的灯光状态，即使未提供操作序列的解决方案，也能获得该测试点一半的分数。

inputFormat:
输入包含多组数据。第一行包含一个整数 $t$，表示测试数据的组数（$1 \leq t \leq 50000$）。

在每组数据中：

第一行输入两个整数 $n$ 和 $m$，分别表示建筑物的数量和通道的数量（$1 \leq n \leq 10^5$, $0 \leq m \leq 2 \times 10^5$）。

接下来的 $m$ 行是通道的描述。在第 $i$ 行中有三个整数 $a_i$, $b_i$, $c_i$ ，分别是由第 $i$ 个通道连接的两个建筑物编号，以及第 $i$ 个通道要求的灯光状态（$1 \leq a_i, b_i \leq n$, $a_i \ne b_i$, $0 \leq c_i \leq 1$）。如果 $c_i = 0$，则第 $i$ 个通道的灯光状态最终应该是关闭的，如果 $c_i = 1$，则应该是开启的。

最后一行给出 $n$ 个整数 $d_1, d_2, \dots, d_n$，表示各建筑物要求的灯光状态（$0 \leq d_i \leq 1$）。如果 $d_v = 0$，则建筑物 $v$ 的灯光状态最终应该是关闭的，如果 $d_v = 1$，则应该是开启的。

所有 $n$ 值的总和不超过 $10^5$，$m$ 值的总和不超过 $2 \times 10^5$。

outputFormat:
对于每组输入：
- 如果不存在一种操作序列能使得建筑物和通道的灯光状态达到要求，则输出 `NO`。
- 如果存在操作序列，则输出 `YES`。如果不展示具体的操作序列（只拿部分分），则在下一行输出数字 $-1$ 并继续输出下一组数据（如果有的话）。如果展示操作序列，则在下一行输出整数 $s$，表示操作的数量（$0 \leq s \leq 10^6$，所有 $s$ 值的总和不超过 $10^6$），然后在接下来的 $s$ 行中输出下列具体操作：
  - 在第 $i$ 行（$1 \leq i \leq s$）中，输出两个整数 $v_i,x_i$，分别是改变灯光状态的建筑物编号，以及新的灯光状态（$1 \leq v_i \leq n$，$0 \leq x_i \leq 1$；如果 $x_i = 0$，则表示需要关闭建筑物 $v_i$ 的灯光，如果 $x_i = 1$，则表示需要打开建筑物 $v_i$ 的灯光）。

hint:
样例解释：

第一组数据包含 $4$ 个建筑物（用圆圈表示）和 $4$ 条通道（用线表示）。机房或通道的灯光状态通过加粗的线表示（如果加粗则表示开灯）。要达到所需的灯光状态，需要 $5$ 步操作。下图展示了初始灯光状态及每一步操作后的状态：

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

第二组数据需要达到下列机房和通道的配置，但这是不可能的：

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

第三组数据中有一个建筑物需要开启灯光。这可以通过一步操作完成。

第四组数据中有一个建筑物需要关闭灯光。一个可行的操作序列是一步操作，关闭该机房的灯光。尽管灯光已经是关闭状态，这样的操作依然是有效的。

第五组数据中有两个建筑物和一条通道，所有的灯光都需要关闭。空的操作序列也是一种可行的解决方案。

数据范围见输入格式。


title: [ROI 2024 Day 2] 无人机比赛

background:
翻译自 [ROI 2024 D2T3](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day2.pdf)。

有 $n$ 架无人机报名参加一个无人机比赛，第 $i$ 架无人机飞过一单位距离需要 $t_i$ 秒。

比赛在一条直线上进行，该直线上有 $m$ 个门，编号从 $1$ 到 $m$，第 $i$ 个门位于距离比赛起点 $s_i$ 的位置。

因为赛道大小的限制，第一场比赛只会有前 $k$ 架无人机参与，编号从 $1$ 到 $k$。$k$ 的值由裁判在比赛开始前宣布，因此此时你需要对 $k$ 从 $1$ 到 $n$ 的比赛情况进行分析。

比赛的进行方式如下：

无人机从 $0$ 号点开始向门移动，每架无人机的速度不同。每架无人机都有一个存档点，即最后一个它进行了存档操作的门。最初，每架无人机的存档点都是 $0$ 号点。

在比赛中，所有无人机从其存档点开始移动，直到有一架或多架无人机到达一个门（有可能是不同无人机同时到达不同的门）。此时，在所有到达门的无人机中，选择编号最小的无人机，对该无人机进行存档操作，将其存档点设置为当前的位置。其他无人机立即传送到其存档点。然后，比赛继续进行。

如果一架无人机在最后一个编号为 $m$ 的门上进行存档操作，那么它就完成了比赛。尚未完成的无人机将传送到其存档点继续比赛。当所有无人机都完赛时，比赛结束。

description: 传送是一个非常耗能的过程。为了准备比赛，你需要了解所有无人机在比赛结束之前一共将进行多少次传送。设 $c_k$ 表示当前 $k$ 架无人机参与比赛时，所有无人机的总传送次数，则你需要求出 $c_1, c_2, \dots, c_n$ 的值。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，分别表示无人机的数量和门的数量（$2 \leq n \leq 150000$，$1 \leq m \leq 150000$）。

第二行包含 $n$ 个正整数 $t_1, t_2, \dots, t_n$，$t_i$ 表示第 $i$ 架无人机飞过一单位距离所需的秒数（$1 \leq t_i \leq 10^9$）。

第三行包含 $m$ 个正整数 $s_1, s_2, \dots, s_m$，$s_i$ 表示第 $i$ 个门的位置（$1 \leq s_1 < s_2 < \dots < s_m \leq 150000$）。

outputFormat: 输出 $n$ 个整数 $c_1, c_2, \dots, c_n$，意义见题目描述。


title: [ROI 2024 Day 2] 保持连接

background:
翻译自 [ROI 2024 D2T4](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day2.pdf)。

在一条进行无人驾驶卡车测试的直路上，有 $n$ 个城市，第 $i$ 个城市位于坐标为 $i$ 的位置。第 $i$ 个城市安装了一个功率为 $a_i$ 的天线，覆盖从 $L_i = \max(1, i - a_i)$ 到 $R_i = \min(n, i + a_i)$ 的所有城市。

无人驾驶卡车沿着这条路从城市 $s$ 移动到城市 $t$，其中 $s < t$。卡车在经过的每个城市都会连接到覆盖该城市的某个天线。连接天线的规则如下：
1. 在起始城市，卡车连接到覆盖该城市的天线中 $R_i$ 最大的一个。如果有多个这样的天线，可以选择其中任何一个。
2. 当卡车从城市 $v$ 移动到城市 $v + 1$ 时，如果之前连接的天线仍覆盖城市 $v + 1$，卡车将继续连接到该天线。否则，如果之前连接的天线不再覆盖城市 $v + 1$，卡车将重新连接到覆盖城市 $v + 1$ 的天线中 $R_i$ 最大的一个。如果有多个这样的天线，可以选择其中任何一个。

我们用 $f(s, t)$ 表示从城市 $s$ 到城市 $t$ 的卡车在途中进行的天线重新连接的次数（$s < t$）。在城市 $s$ 进行的初次连接不算作重新连接。

description:
定义天线覆盖道路的不稳定性 $F$ 为 $f(s, t)$ 的总和，即：

$$F = \sum_{s=1}^{n-1} \sum_{t=s+1}^{n} f(s, t)$$

道路运营商有一个备用天线，功率为 $x$。为了降低天线覆盖的不稳定性，可以用备用天线替换任意一个现有天线。你需要确定，如果最多替换一个天线为功率 $x$ 的备用天线，不稳定性 $F$ 值最小可能是多少。

inputFormat:
第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 10^6$，$0 \leq x \leq n$），分别为城市的数量和备用天线的功率。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq n$），即每个城市天线的功率。

outputFormat: 输出在最多用一个备用天线替换现有天线后，$F$ 的最小可能值。


title: [ROIR 2024 Day 1] 登机

background:
翻译自 [ROIR 2024 D1T1](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day1.pdf)。

飞机上一共有 $n$ 排座位，每排有六个位置，其中第三和第四个位置之间有过道。一些乘客在线上已经提前订好位置，其他乘客则在机场的登记台购买机票。在线上购买机票时，乘客可以选择任何座位，且不能更改。例如，当 $n = 6$ 时，在线上已经订好的座位可能如下（用叉号标记已占用的座位）：

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

有 $m$ 名乘客在登记台购买机票。根据航空公司的规定，在工作人员帮他们选好位置后，最终的座位安排相对于过道应该是对称的。即，如果某一排的第一个座位有乘客，那么同一排的第六个座位也必须有乘客。同样，第二和第五、第三和第四个座位也必须相应对称。同时，在线上购买的乘客的座位不能改变。在上图的初始座位中，可以添加七名乘客以满足对称性，如下图：

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

description: 给定在线购买的乘客选定的座位，你需要安排 $m$ 名乘客，使得最终的座位安排相对于过道是对称的。如果不可能做到，输出 `Impossible`。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，分别表示飞机座位的排数和在机场登记台购买机票的乘客数量（$1 \leq n \leq 1000$，$0 \leq m \leq 6000$）。

接下来的 $n$ 行描述了在线购买的乘客选定好的座位。每行包含六个字符，其中第 $j$ 行的第 $i$ 个字符表示第 $j$ 排的第 $i$ 个座位的状态，如果第 $i$ 个座位被占用，则为 `X`，否则为 `.`。

outputFormat:
如果无法找到满足要求的座位安排，输出 `Impossible`。

否则，输出 $n$ 行，每行六个字符，即飞机的最终座位安排，其中第 $j$ 行的第 $i$ 个字符表示第 $j$ 排的第 $i$ 个座位的状态。如果座位被占用则为 `X`，否则为 `.`。如果存在多个方案，可以输出其中任意一个。


title: [ROIR 2024 Day 1] 双调序列

background:
翻译自 [ROIR 2024 D1T2](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day1.pdf)。

称一个序列 $[b_1, b_2, \dots, b_k]$ 为双调序列（Bitonic Sequence），当且仅当存在一个 $1 \leq i \leq k$ 使得 $ b_1 < b_2 < \dots < b_i > \dots > b_k $。

例如，序列 $[1]$，$[2,4,5,7,5,4]$，$[1, 4, 10]$，$[3, 2]$ 都是双调序列，而序列 $[1, 1]$，$[5,4,2,4,5,7]$，$[1,1,4,5,1,4]$ 都不是。

description: 给定一个序列 $[a_1, a_2, \dots, a_n]$。要求计算满足条件的 $(l, r)$ 对的数量，其中 $1 \leq l \leq r \leq n$ 并且序列 $[a_l, a_{l+1}, \dots, a_r]$ 是双调序列。

inputFormat:
第一行输入一个整数 $n$（$1 \leq n \leq 300000$）。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。

outputFormat: 输出一个整数，即满足 $1 \leq l \leq r \leq n$ 且序列 $[a_l, a_{l+1}, \dots, a_r]$ 是双调序列的 $(l, r)$ 对的数量。


title: [ROIR 2024 Day 1] 表格游戏

background:
翻译自 [ROIR 2024 D1T3](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day1.pdf)。

给定一个有 $h$ 行和 $w$ 列的表格 $A$，每个单元格内含有一个整数。行从上到下编号为 $1$ 到 $h$，列从左到右编号为 $1$ 到 $w$。允许对这个表格进行以下操作：

- 选择一列并删除它（删除的列左边和右边的列变为相邻的列）；
- 选择一行并删除它（删除的行上边和下边的行变为相邻的行）。

这些操作可以按任意顺序执行任意多次。

description: 你需要确定是否可以通过这些操作将表格变为一个数字之和为 $s$ 的表格。如果可以，请给出具体的操作。

inputFormat:
第一行包含两个数字 $h$ 和 $w$，表示表格的大小（$1 \leq h, w \leq 15$）。

接下来 $h$ 行，每行包含 $w$ 个整数，其中第 $i$ 行第 $j$ 列为 $A_{i,j}$（$0 \leq A_{i,j} \leq 10^9$）。

最后一行输入数字 $s$，即需要通过操作达到的和（$1 \leq s \leq 10^{18}$）。

outputFormat:
如果从原始表格中无法得到一个数字之和为 $s$ 的表格，输出 `NO`。

否则：
- 第一行输出 `YES`。
- 第二行输出一个数字 $k$ ，表示需要进行的操作次数。
- 接下来的 $k$ 行，每行输出两个整数 $t_j$，$i_j$，其中 $t_j = 1$ 表示操作是对行进行的，$t_j = 2$ 表示操作是对列进行的。数字 $i_j$ 应为操作所针对的行或列的初始编号。


title: [ROIR 2024 Day 1] 树根

background:
翻译自 [ROIR 2024 D1T4](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day1.pdf)。

给定一棵由 $n$ 个节点构成的树和一个数 $k$。固定树中的某个节点 $s$，并令其为根。

将树的边定向从树根出发。换句话说，将边 $(u, v)$ 定向为 $u \to v$，如果在以 $s$ 为根时，节点 $u$ 是节点 $v$ 的父节点。在这种定向下，每个节点都可以从根到达。

定义节点 $v$ 到节点 $s$ 的距离为从 $s$ 到 $v$ 的最短路径上边的数量。定义节点 $s$ 的可达性为所有节点到节点 $s$ 的距离中的最大值。

description:
允许在树中增加不超过 $k$ 条额外的有向边。对于树中的每个节点 $s$，确定如果选择节点 $s$ 作为树根，能够达到的最小可达性是多少。

注意，在某些子任务中，只需要输出顶点编号为 $1$ 的答案。

inputFormat:
第一行包含三个整数 $n$，$k$ 和 $t$ （$2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq n - 1$，$n \times k \leq 2 \times 10^5$，$0 \leq t \leq 1$），分别表示树的顶点数量、额外添加的有向边的最大数量限制和一个整数 $t$，如果 $t$ 为 $0$，则只需输出顶点编号为 $1$ 的答案；如果 $t$ 为 $1$，则输出所有顶点的答案。

接下来的 $n - 1$ 行每行包含两个整数 $u_i$ 和 $v_i$ （$1 \leq u_i, v_i \leq n$），表示树的一条边。

保证所给的边构成一棵树。

outputFormat:
如果 $t = 0$，输出一个整数，即选择顶点编号为 $1$ 作为树根，并且增加不超过 $k$ 条额外的有向边时，可以达到的最小可达性。

如果 $t = 1$，输出 $n$ 个数，第 $i$ 个数表示选择顶点 $i$ 作为树根，并且增加不超过 $k$ 条额外的有向边时，可以达到的最小可达性。


title: [ROIR 2024 Day 2] 数组划分

background: 翻译自 [ROIR 2024 D2T1](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day2.pdf)。

description:
给定一个数组 $A = [a_1, a_2, \dots, a_n]$，其中包含 $n$ 个正整数。

需要将数组元素涂成两种颜色，使得任意两个同一颜色的元素 $x$ 和 $y$ 不满足以下条件：
- $x=p\times y$，其中 $p$ 是一个素数。

保证存在这样的涂色方案。

inputFormat:
第一行包含一个整数 $n$（$1 \leq n \leq 100000$），表示数组的元素个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$），即数组中的元素。

outputFormat:
输出数组的划分方案。具体地，输出一行 $n$ 个整数，如果第 $i$ 个数字为 $1$，表示第 $i$ 个元素应涂成第一种颜色；如果为 $2$，则表示第 $i$ 个元素应涂成第二种颜色。

如果存在多个合适的划分方案，可以输出其中任何一个。


title: [ROIR 2024 Day 2] 细菌

background:
翻译自 [ROIR 2024 D2T2](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day2.pdf)。

生物实验室中正在进行实验。开始时，有 $n$ 个冷冻的细菌，编号从 $1$ 到 $n$。根据实验计划，编号为 $i$ 的细菌将在实验开始后的 $a_i$ 秒进入培养皿。如果有多个细菌的 $a$ 相等，它们会同时进入。

一旦冷冻的细菌进入培养皿，它们会被解冻并开始成熟。编号为 $i$ 的细菌成熟需要 $t_i$ 秒。一旦细菌成熟，它们会开始繁殖：立即分裂成两个成熟的细菌，然后在接下来的每一秒钟，每个成熟细菌都会再次分裂成两个成熟的细菌。

description: 培养菌落的规模指的是培养皿中细菌的总数。实验的目标是确定多长时间后，培养菌落的规模首次恰好等于 $m$。请帮助科学家确定这个时间秒数，或者判断培养群体的规模是否永远不会恰好等于 $m$。

inputFormat:
第一行给出两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 10^9$），分别表示细菌的数量和期望的培养菌落规模。

第二行给出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示细菌进入培养皿的时间。

第三行给出 $n$ 个整数 $t_1, t_2, \dots, t_n$（$1 \leq t_i \leq 10^9$），表示冷冻的细菌成熟所需的时间。

outputFormat: 如果培养菌落的规模永远不会等于 $m$，则输出 `-1`。否则，输出在实验开始后多少秒，培养群体的规模首次恰好等于 $m$。


title: [ROIR 2024 Day 2] 三等分的数组

background:
翻译自 [ROIR 2024 D2T3](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day2.pdf)。

在生日那天，玛莎像往常一样收到了一个由 $n$ 个数组成的数组 $a$，其中每个数字都在 $1$ 到 $m$ 之间。玛莎非常喜欢数字 $3$，因此数组的长度能被 $3$ 整除。

玛莎决定将这些数字分组为三元组：每个三元组要么由三个相同的数字组成，要么由三个连续的数字组成。换句话说，每个三元组的形式要么是 $(x, x, x)$，要么是 $(x, x + 1, x + 2)$，其中 $x$ 是一个正整数。

玛莎想要研究这个礼物中的数组，她想知道将数组中的数字分成这样的三元组的方式有多少种。如果不能为第一个分组中的每个三元组与第二个分组中的每个三元组建立一一对应关系，使得对应三元组中的数字相等，则两个分组方式被认为是不同的。由于分组方式可能非常多，玛莎只需知道其模 $10^9 + 7$ 的余数。

description: 帮助玛莎计算将数组中的数字分成三元组的方式的数量，对 $10^9 + 7$ 取模。

inputFormat:
第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 5000$，$1 \leq m \leq 5000$，$n$ 是 $3$ 的倍数）。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数组中的数字（$1 \leq a_i \leq m$）。

outputFormat: 输出一行一个整数，即将数组中的数字分成三元组的方式的数量，对 $10^9 + 7$ 取模。


title: [ROIR 2024 Day 2] 二叉树的遍历

background:
翻译自 [ROIR 2024 D2T4](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day2.pdf)。

二叉树有三种基本遍历方式：前序遍历（pre-order）、中序遍历（in-order）和后序遍历（post-order）。我们可以将这三种遍历方式进行概括：假设每个节点上记录一个整数 $x$（取值范围为 $-1$ 到 $1$），表示在遍历中输出该节点的时机，具体如下：
- $x = -1$：在遍历其左右子树之前；
- $x = 0$：在遍历其左子树之后，遍历其右子树之前；
- $x = 1$：在遍历其左右子树之后。

因此，如果所有节点的 $x$ 值都是 $-1$，则遍历为前序遍历；如果都是 $0$，则为中序遍历；如果都是 $1$，则为后序遍历。

description:
考虑一棵有 $n$ 个节点的二叉树，节点编号从 $1$ 到 $n$。树的根节点为 $1$。最初，所有节点上的值都是 $-1$。

你需要处理 $q$ 个操作，操作类型如下：
1. 将节点 $l, l + 1, \dots, r$ 上的值更改为 $x$（$x$ 取值为 $-1$，$0$ 或 $1$）。
2. 查询节点 $i$ 在当前遍历方式中的位置。

需要输出所有第二种类型的操作的结果。

inputFormat:
第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 100000$）。

接下来 $n$ 行，每行包含两个整数 $L_i$ 和 $R_i$（$0 \leq L_i, R_i \leq n$），分别表示节点 $i$ 的左子树和右子树的编号，若某个子树不存在则为 $0$。

保证 $L_i$ 和 $R_i$ 描述了一个有效的二叉树。

接下来的 $q$ 行中包含操作。每行的第一个整数 $t$（$t \in \{1, 2\}$）表示操作类型。
- 对于第一种类型的操作，后面有三个整数 $l$，$r$ 和 $x$（$1 \leq l \leq r \leq n$，$x$ 为 $-1$，$0$ 或 $1$），表示节点范围和新的值。
- 对于第二种类型的操作，后面有一个整数 $i$（$1 \leq i \leq n$），表示询问其在遍历中的位置的节点编号。

outputFormat: 对于每个第二种类型的操作，输出一个整数，表示对应节点在遍历中的位置。

hint:
样例中的树是这样的：

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

刚开始，所有节点的 $x$ 值都是 $-1$，因此第一次查询时遍历得到的数组为 $[1,3,5,2,4]$，$2$ 在第四个位置。

在将节点 $1,2,3$ 的遍历方式 $x$ 改为 $1$ 后，再次查询时遍历得到的数组为 $[5,2,3,4,1]$，$5$ 在第一个位置。

接着把节点 $3$ 的遍历方式 $x$ 改为 $0$，此时再进行查询，遍历得到的数组为 $[5,3,2,4,1]$，$3$ 在第二个位置。

设 $q_1$ 为操作 $1$ 的数量。

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $0$ | $0$ | 同样例 |
|$1$ | $10$ | $n, q \leq 5000$ |
|$2$ | $5$ | $q_1 \leq 10$ |
|$3$ | $10$ | 所有操作一在所有操作二之前 |
|$4$ | $10$ | 所有叶子节点都与根节点距离相同，没有具有一个子节点的节点 |
|$5$ | $10$ | 对于所有操作一，$l = r$ |
|$6$ | $20$ | 对于所有操作一，$x \in \{-1, 1\}$，每个节点最多有一个子节点 |
|$7$ | $10$ | 对于所有操作一，$x \in \{-1, 1\}$ |
|$8$ | $10$ | 每个节点最多有一个子节点 |
|$9$ | $15$ | 无 |

对于 $100\%$ 的数据，$1 \leq n, q \leq 100000$。


title: 带余除法

background:
**注意：提交至洛谷时，请使用标准输入输出，而非文件输入输出。**

**NOTICE: When submitting your code on Luogu site, please use standard IO instead of file IO.**

[点我（或在本题底部）下载中文试题 PDF。](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/asjh3my3?contestId=200686)

[Click here (or at the bottom  of this page) to download the English version of statements (PDF).](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/lkux3617?contestId=200686)

**注意：本次比赛所有题目的大样例均为 Linux 换行符格式，在 Windows 系统内可能无法正常显示换行。**

description:
我们已经学过带余除法。对于两个正整数 $n,q$，如果 $n$ 除以 $q$ 的商为 $k$，余数为 $r$，我们可以写出带余除法算式 $n\div q = k \cdots\cdots r$，或被记为 $n\div q = k (\text{r. } r)$。本题中，为了简化，哪怕 $r=0$，我们也要写出这个余数。

现在有一个带余除法，然而你只知道被除数 $n$ 和商 $k$，而并不知道除数 $q$ 和余数 $r$。你想知道余数有多少种可能。

inputFormat:
**本题有多组测试数据**。输入的第一行有一个正整数 $T$，表示数据组数。

之后 $T$ 行，每行有一个正整数 $n$ 和自然数 $k$，分别表示带余除法的被除数和商。

outputFormat: 对于每组测试数据，输出一行一个自然数，表示余数的不同可能性数量。

samples:
参见 division/division2.in
参见 division/division2.ans

hint:
【样例 1 解释】

对于第一组数据，被除数为 $10$，商为 $2$。

- 如果除数是 $1,2,3$，那么商分别是 $k=10,5,3$，不符合题意。
- 如果除数是 $4$，那么商为 $2$，余数为 $r=2$。
- 如果除数是 $5$，那么商为 $2$，余数为 $r=0$。
- 如果除数是 $6,7,8,9,10$，那么商都是 $1$，不符合题意。
- 如果除数 $>10$，那么商为 $0$，不符合题意。

对于第二组数据，被除数为 $1$，商为 $0$。

只要除数 $q>1$，那么 $1\div q = 0 \cdots\cdots 1$ 一定是正确的带余除法算式。余数只有 $1$ 这一种可能。

【数据范围】

对于前 $30\%$ 的数据，保证 $1\le n\le 1000$，$0\le k\le 1000$。

另有 $20\%$ 的数据，保证 $k\le 10^5$。

另有 $20\%$ 的数据，保证 $k\ge 10^9$。

对于全体数据，保证 $1\le T\le 10$，$1\le n\le 10^{14}$，$0\le k\le 10^{14}$。


title: 奖牌排序

description:
有 $n$ 个小朋友参加了若干场比赛，其中第 $i$ 个小朋友获得了 $g_i$ 枚金牌、$s_i$ 枚银牌和 $b_i$ 枚铜牌。老师希望**每个小朋友**制作一张**所有小朋友**的排行榜。

然而小朋友们为了让自己的排名尽量靠前，自然是可以动一些小心思的，体现在排序标准上——每个小朋友可以选择按照金牌数从大到小排序，也可以选择按照银牌数从大到小排序，也可以选择按照铜牌数从大到小排序。在小朋友自制的排行榜里，如果自己和别的小朋友并列，那么他可以把自己写在最前面。

给出每个小朋友获得的金牌数、银牌数和铜牌数，请对于每个小朋友 $i$，计算他在他自己的排行榜里最好能排第几名。

inputFormat:
输入的第一行有一个正整数 $n$，表示小朋友的个数。

之后 $n$ 行，每行有三个自然数 $g_i,s_i,b_i$ 表示一个小朋友的金牌、银牌和铜牌数量。

outputFormat: 输出 $n$ 行，每行一个正整数，其中第 $i$ 行的正整数表示第 $i$ 个小朋友的最好排名。

samples:
参见 medal/medal2.in
参见 medal/medal2.ans

samples:
参见 medal/medal3.in
参见 medal/medal3.ans


title: 三目运算

description:
三目运算是一种比较特殊的运算，功能类似于 `if` 语句，其语法格式如下：

`条件?数值1:数值2`，三目运算得到的结果也是数值。当条件成立时得到的结果是数值 1，不成立时得到的结果为数值 2。

例如，`x>5?8:6` 就是一种三目运算表达式（也是分段常数表达式，见下文）。当 $x=7$ 时，该表达式的结果为 $8$，而 $x=3$ 时，该表达式的结果为 $6$。

---

本题中，称满足下列条件中**至少一条**的字符串 $S$ 是**分段常数表达式**：

- 十进制正整数 $a$，如 `243`，是分段常数表达式。
- 如果 $a$ 为一个十进制正整数，$p,q$ 为两个分段常数表达式，则 $\texttt{x>}a\texttt{?}p\texttt{:}q$ 是分段常数表达式。
- 如果 $a$ 为一个十进制正整数，$p,q$ 为两个分段常数表达式，则 $\texttt{x<}a\texttt{?}p\texttt{:}q$ 是分段常数表达式。

（后两条条件中， $x>a$ 和 $x<a$ 是条件，$p,q$ 为数值，该表达式是三目运算表达式。）

例如，`x>154?220:x<37?16:10` 是一个分段常数表达式，因为 `220` 和 `x<37?16:10` 都是分段常数表达式，从而整个表达式由第 2 条规则也是分段常数表达式。

---

给出一个分段常数表达式 $S$，保证出现的正整数均不超过 $m$。

yummy 有 $q$ 个询问，每次给出一个自然数 $x$ 的值，希望你求出分段常数表达式的值。

inputFormat:
输入的第一行有两个正整数 $m,q$，分别表示表达式出现数字的最大可能值和询问个数。

第二行有一个字符串 $S$，表示这个分段常数表达式。

之后有 $q$ 行，每行有一个自然数 $x$，表示一次询问。

outputFormat: 对于每个询问输出一行一个正整数，表示表达式的结果。

samples:
参见 expr/expr2.in
参见 expr/expr2.ans

samples:
参见 expr/expr3.in
参见 expr/expr3.ans

samples:
参见 expr/expr4.in
参见 expr/expr4.ans


title: 配对序列

description:
一个序列 $s_1,\ldots s_{2k}$ 是**配对的**，当且仅当：

- 对于任意 $1\le i \le k$，$s_{2i}=s_{2i-1}$。
- 对于任意 $1\le i<k$，$s_{2i}\ne s_{2i+1}$。

注意，配对的序列长度必然为偶数。

例如，$3,3,5,5,2,2$ 是配对的，而 $2,2,2,2,5,5$（$s_2=s_3$ 不满足第二条要求）或者 $1,2,3,3,1,1$（$s_1\ne s_2$ 不满足第一条要求）都不是配对的。

给出一个数列 $a_1,\ldots, a_n$，求所有配对的子序列长度的最大值。

inputFormat:
输入的第一行有一个正整数 $n$，表示序列的长度。

第二行有 $n$ 个正整数 $a_1,\ldots,a_n$，表示这个序列。

outputFormat: 输出一行一个自然数，表示最长的配对子序列长度。特别地，如果不存在非空的配对子序列，那么输出 $0$。

samples:
参见 pairing3.in
参见 pairing3.out

samples:
参见 pairing4.in
参见 pairing4.out


title: 【MX-X5-T3】「GFOI Round 1」Cthugha

background: > [Cthugha - USAO](https://music.163.com/#/song?id=1833853372)

description:
给定一张 $n \times m$ 的网格图，行编号为 $1,2,\dots ,n$，列编号为 $1,2,\dots ,m$。我们用 $(i, j)$ 来描述第 $i$ 行第 $j$ 列的格子。每个格子有一个整数权值 $a_{i,j}$，**注意格子的权值可以是负数**。

给定 $q$ 个人位于网格图上，第 $i$ 个人的初始位置在 $(x_i, y_i)$，**注意不保证每个人初始位置互不相同**。

定义某人**走一步**为：若这个人当前坐标在 $(x,y)$，则将该人移动至 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ 其中之一。设移动后到达 $(x^{\prime},y^{\prime})$，此时需要满足 $1\leq x^{\prime}\leq n,1\leq y^{\prime}\leq m$。

在任意时刻，允许任意两个人位于同一个格子。

定义一个人的**权值**为其走若干步后所有经过的格子的权值和（包括起点和终点），注意若一个格子被经过 $k$ 次则其权值需要被累加 $k$ 次。

特别地，若一个人没有走，则其**权值**为其初始位置格子的权值。

定义**总权值**为每个人走若干步数，所有人权值的最大值。

求最终所有人都走到同一个格子的最小**总权值**，或报告不存在最小**总权值**（即最小总权值为负无穷）。

inputFormat:
第一行包含三个正整数 $n, m, q$。

接下来 $n$ 行的第 $i$ 行包含 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$。

接下来 $q$ 行的第 $i$ 行包含两个正整数 $x_i, y_i$，表示第 $i$ 个人的初始位置在 $(x _ i, y _ i)$。

outputFormat: 若最小总权值不存在（即最小总权值为负无穷），输出 `No`；否则输出一行一个整数表示最小总权值。


title: [THUWC 2018] 零食

background:
来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。

2018 清华大学信息学冬季体验营（THUWC 2018）D1T1。$\texttt{1s,1G}$。

description:
Yazid 是一名清华大学的学生，他非常喜欢吃零食。

Yazid 共有 $n$ 包**薯片**，（由于它们的口味各不相同）Yazid 把他们从 $1$ 至 $n$ 编号；Yazid 还有 $m$ 包**果干**，Yazid 也把他们从 $1$ 至 $m$ 编号。

为了不引起歧义，我们规定：两包零食**类型**相同当且仅当它们同为薯片或果干。

Yazid 打算按一定顺序吃掉所有的零食。在开始吃一包零食后，直到这包零食被吃完前， Yazid 都不会吃其他零食。也就是说， Yazid 的吃零食顺序可以用一个**待吃零食的排列**来表示。

连续吃同一种食物可能会有别样的体验，所以，每包零食都有一个**妙值**。编号为 $i$（$1\leq i\leq n$）的薯片的妙值为 $a_i$，编号为 $i$（$1\leq i\leq m$）的果干的妙值为 $b_i$。

我们保证所有零食的妙值是整数，但需要注意的是，它们有可能为负。

在吃每包零食时，如果 Yazid 在其之前吃的零食与其类型相同，则 Yazid 会增加当前零食妙值的**快乐度**（吃第一包零食时不会获得快乐度）。初始时， Yazid 的快乐度为 $0$。

Yazid 希望获得最大的快乐度（需要提醒你的是，这个值可能是负的）。

饥肠辘辘的 Yazid 还要吃遍清华大学 $19$ 座食堂，所以请你帮他计算他能获得的最大快乐度。

inputFormat:
从标准输入读入数据。

**本题包含多组数据**。输入的第一行为一个非负整数 $T$ ，表示数据组数。接下来依次描述每组数据，对于每组数据：

第一行 $1$ 个正整数 $n$ ，表示薯片的数量。

第二行 $n$ 个用空格隔开的整数 $a_1,\dots,a_n$ ，表示所有薯片的妙值。

第三行 $1$ 个正整数 $m$ ，表示果干的数量。

第二行 $m$ 个用空格隔开的整数 $b_1,\dots,b_n$ ，表示所有果干的妙值。

outputFormat:
输出到标准输出。

对于每组数据，输出一行一个整数，表示 Yazid 能获得的最大快乐度。

hint:
#### 解释

为了方便起见，我们约定用 $A_i$ 表示编号为 $i$ 的薯片，用 $B_i$ 表示编号为 $i$ 的果干。

对于第 $1$ 组数据：无论以何种顺序吃这些零食， Yazid 都不会获得任何快乐度，因此答案为 $0$ 。

对于第 $2$ 组数据：最优方案可以是 $B_2\rightarrow B_1\rightarrow A_1$ ，可以在吃 $B_1$ 时获得  $20$ 的快乐度。可以证明不存在更优的解。

对于第 $3$ 组数据：按 $B_1\rightarrow B_2\rightarrow A_2\rightarrow A_3\rightarrow A_1$ 的顺序吃零食即可获得 $3$ 的快乐度。可以证明不存在更优的解。

#### 子任务

| 测试点编号 | $\sum(n+m)\le $ | $n,m\le $ | $\vert a_i\vert ,\vert b_i\vert \le $ | 其他约束 | 分值 |
| :--: | :--: | :--: | :--: | :--: | :--: |
| $1$ | $300$ | $4$ | $1,000$ | 无 | $7$ |
| $2$ | $2\times 10^6$ | $10^5$ | $1$ | 无 | $8$ |
| $3$ | $2\times 10^6$ | $10^5$ | $2$ | 无 | $11$ |
| $4$ | $2\times 10^6$ | $10^5$ | $10^9$ | 所有 $a_i,b_i$ 均为负数 | $9$ |
| $5$ | $10^4$ | $10^3$ | $10^9$ | 无 | $23$ |
| $6$ | $2\times 10^6$ | $10^5$ | $10^9$ | 无 | $42$ |

其中， $\sum (n+m)$ 表示该测试点中所有数据的 $n,m$ 之和。例如，样例1中的 $\sum (n+m)$ 即为 $1+1+1+2+3+2+5+5=20$ 。

对于所有测试点，保证 $T\leq 5,000$ ， $\sum (n+m)\leq 2\times {10}^{6}$。

对于每个测试点的所有数据，保证 $n,m\leq 100,000$ ，$1\leq \left|a_i \right|,\left|b_i \right|\leq 10^9$。

对于所有测试点，保证：所有数据中 $n,m$ 的最大值、所有数据中 $\left| a_i\right|,\left| b_i\right|$ 的最大值分别不会小于该测试点 $n,m$ 、 $\left|a_i \right|,\left|b_i \right|$ 上界的 $\frac{2}{3}$ ； $\sum (n+m)$ 也不会小于对应上界的**一半**。


title: [THUWC 2018] 城市规划

background:
来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。

2018 清华大学信息学冬季体验营（THUWC 2018）D1T2。$\texttt{1.5s,2G}$。

description:
access_globe 最近在玩一款城市规划的游戏。在游戏中，有 $n$ 个城市，$n-1$ 条可以双向通行的道路连接着这些城市，任意两个城市都可以通过这些道路互相到达。

最近，游戏中的“世界杯”比赛开始了。每一个城市都恰好支持一支球队，设第 $i$ 个城市支持的球队为 $a_i$。游戏给 access_globe 一个新的任务：选择一些城市，在这些城市建立可以承办世界杯的足球场。

access_globe 不希望建立足球场的城市所喜欢的球队的差异太大，因此他要求建立了足球场的这些城市中，不能存在 $3$ 个城市，使得它们支持的球队互不相同。同时为了减少球员花费在路上的时间，access_globe 希望任意两个建立了足球场的城市，都可以只经过其他建立了足球场的城市互相到达。

access_globe 是一个喜欢不同的同学，因此他希望你帮他求出，有多少种不同的建立足球场的方案。两种方案被认为是不同的，当且存在一个城市，使得该城市在恰好一种方案中被建立了足球场。

但你并不想帮他解决这个问题，你只想告诉他答案在 $998,244,353$ 进制下的个位（即答案除以 $998,244,353$ 的余数）。

inputFormat:
从标准输入读入数据。

第 $1$ 行包含一个整数 $n$，表示城市的个数。

第 $2$ 行包含 $n$ 个用空格隔开的整数 $a_1,…,a_n$ ，表示每个城市支持的球队。

第 $3$ 到第 $n+1$ 行，每行包含 $2$ 个用空格隔开的整数 $x_i,y_i$ ，表示一条连接城市 $x_i$ 和城市 $y_i$ 的双向道路。保证任意两个城市都可以通过这些道路互相到达。

outputFormat:
输出到标准输出。

输出一行一个数，表示不同的建立足球场的方案数除以 $998,244,353$ 的余数。

hint:
#### 解释

城市的道路情况和支持的球队情况如下图，其中颜色相同的城市支持相同的球队。

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

任何只建立一个足球场或将足球场建立在两个有道路直接相连的方案都是合法的，这样共有 $5+6=11$ 种方案。其余方案为在城市 $2$、$3$ 和其它任意一个城市建立足球场，共 $4$ 种方案，因此总共有 $15$ 种方案。

#### 子任务

| 测试点 | 分值 | $n=$ | 特殊性质 |
| :--: | :--: | :--: | :--: |
| $1$ |  $3$ |  $500$  | 无 |
| $2$ |  $7$ |  $5,000$  |  无 |
| $3$ |  $9$ |  $2\times 10^5$  |  A |
| $4$ |  $13$ |  $5\times 10^5$  |  A |
| $5$ |  $7$ |  $2\times 10^5$  |  B |
| $6$ |  $11$ |  $5\times 10^5$  |  B |
| $7$ |  $12$ |  $5\times 10^4$  |  无 |
| $8$ |  $14$ |  $2\times 10^5$  |  无 |
| $9$ |  $12$ |  $5\times 10^5$  |  无 |
| $10$ |  $12$ |  $5\times 10^5$  |  无 |

特殊性质 A：每条道路连接的两个城市支持的球队不同；每个城市最多连出 $10$ 条道路。

特殊性质 B：每条道路连接的两个城市支持的球队不同。

对于所有数据，保证 $1\le a_i\le n\le 5 \times 10^{5}$。

#### 提示

请注意本题的**空间限制**是 2 GB，请计算好程序的内存使用，不要超出限制。超出空间限制可能导致**整道题目得 0 分**。


title: [THUWC 2018] 字胡串

background:
来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。

2018 清华大学信息学冬季体验营（THUWC 2018）D1T3。$\texttt{2s,0.5G}$。

----

我希望你明白，优秀的出题人是懒得写题目背景的。但是优秀的题目也可能需要让选手了解一些基本定义， 例如以下这些内容， 而熟练的算法竞赛选手几乎可以无视。

对于一个字符串 $S$， 我们定义 $\left|S\right|$ 表示 $S$ 的长度。接着，我们定义 $S_i$ 表示 $S$ 中第 $i$ 个字符，$S_{L,R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。特别的，如果 $L>R$，或者 $L \notin \left[1,\left|S\right|\right]$，或者$R \notin \left[1,\left|S\right|\right]$，则我们可以认为 $S_{L,R}$ 为空串。

我们再定义两个字符串 $A$ 和 $B$ 的加法， $A+B$ 为将 $B$ 字符串整体连接在 $A$ 的最后一个字符后面得到的大字符串。

例如，我们可以认为 `aaaa` $+$ `bbbb` $=$ `aaaabbbb`。

我们不难发现，上述定义的加法满足结合律，但不满足交换律。

最后，我希望你还能明白，字典序是什么。

为了让你明白字典序是什么，你还需要明白前缀是什么。我们说一个字符串 $A$ 是另一个字符串 $B$ 的前缀，当且仅当存在一个整数 $len$，使得 $A$ 与 $B_{1,len}$ 是完全相同的字符串。

对于两个不同的字符串 $A$ 和 $B$，如果 $A$ 是 $B$ 的一个前缀，则我们认为在字典序下， $A < B$； 如果 $B$ 是 $A$ 的前缀，则我们认为在字典序下，$B < A$。 否则，我们总能找到一个最小的 $i$， 使得 $A_i \neq B_i$， 如果 $A_i < B_i$， 则我们认为在字典序下，$A < B$，否则 $B > A$。

description:
现在给出一个长度为 $n$ 的字符串 $A$。 在此基础上，我会进行 $Q$ 次询问。

对于第 $i$（$1 \leq i \leq Q$）次的询问，我们会给出一个非空字符串 $B^{(i)}$， 并希望你找出一个最小的 $j$（$0 \leq j \leq n$）， 使得 $A_{1,j} + B^{(i)} + A_{j+1,n}$ 的字典序最小。 对于每个询问，你只需要输出你找到的这个 $j$ 即可。

inputFormat:
从标准输入读入数据。

第一行有两个用空格隔开的整数 $n, Q$， 分别代表字符串 $A$ 的长度，以及询问次数。

第二行给出一个长度为 $n$ 的字符串，表示字符串 $A$。

第三行到第 $Q+2$ 行， 每行会给出一个非空字符串， 第 $i$ 行所给出的字符串表示 $B^{(i-2)}$。

outputFormat:
输出到标准输出。

对于每个询问，请输出一行一个整数表示你所找到的最小的 $j$（$0 \leq j \leq n$）。


title: [THUWC 2018] 明天的太阳会照常升起

background:
来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。

2018 清华大学信息学冬季体验营（THUWC 2018）D2T1。$\texttt{7s,0.5G}$。

description:
小 R 为了看日出，来到了 C 国的东海岸。

东海岸的海岸线上从北到南依次排列着 $n$ 座城市，编号为 $1$ 到 $n$。其中编号小的城市在编号大的城市的北边。相邻编号之间的城市由海滨公路连接，连接城市 $i$ 和 $i+1$ 的公路长度为 $l_i$ 公里。

小 R 有一辆汽车，这辆汽车每行驶一公里需要消耗一单位的汽油。在城市之间的道路上没有加油站，因此小R只能选择在路途中的城市里加油。城市 $i$ 每单位汽油的价格是 $p_i$。小R的汽车在消耗完所有的汽油之后就会立刻熄火，无法前进，且小R的汽车油箱最多能装 $V$ 单位汽油。

小 R 一共规划了 $m$ 次看日出的行程，在第 $i$ 次行程中，小 R 晚上住在 $s_i$ 号城市，第二天凌晨要开车赶往 $t_i$ 号城市看日出。由于某些原因，小 R 总是会从**编号较小**的城市赶往**编号较大**的城市，即满足 $s_i<t_i$ 。因为行程的时间非常紧张，所以每次行程小 R 都会选择距离最短的路线。在选择最短路线的基础上，小 R 希望合理安排加油的地点，使得每次行程的花费最小。在第 $i$ 次行程刚开始时，小 R 的汽车油箱的油量为 $v_i$（$0\le v_i\le V$）。

注意，每次行程都是相互独立的，第 $i$ 次行程刚开始的油箱的油量总是 $v_i$，不会受到上一次行程结束时油箱中剩余油量的影响。

inputFormat:
从标准输入读入数据。

第一行三个用空格隔开的正整数$n，m，V$，分别表示城市的数量，行程的数量和油箱容量。

第二行 $n$ 个用空格隔开的正整数，第 $i$ 个正整数表示 $p_i$。

第三行 $n-1$ 个用空格隔开的正整数，第 $i$ 个正整数表示 $l_i$。

接下来 $m$ 行，每行三个用空格隔开的整数 $s_i$，$t_i$，$v_i$，表示第 $i$ 次行程小 R 要从 $s_i$ 出发赶往 $t_i$，出发时油箱里有 $v_i$ 单位汽油。

outputFormat:
输出到标准输出。

输出 $m$ 行，第 $i$ 行表示第 $i$ 次行程的最小花费。

samples:
见附件中的 ex_2.in。
见附件中的 ex_2.ans。


title: [THUWC 2018] 角点检测（未配置 SPJ）

background:
来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。

2018 清华大学信息学冬季体验营（THUWC 2018）D2T3。$\texttt{3s,0.5G}$。

---

计算机视觉（Computer Vision）中，一个局部特征（local feature）被定义为“一个与其直接邻域有显著不同的小区域”，其中“显著不同”可以是许多可能，如亮度、颜色、纹理等等。足够好的特征可以让我们进一步获取图片中除颜色以外的更多（语义）信息。例如，在卷积神经网络（Convolutional Neural Network）中，特征是通过卷积核来提取的，而其层级结构使得高层的信息能通过低层信息结合来生成。一个用于人脸识别的网络中可以存在感知诸如眼、嘴、耳、发、皮肤的不同神经元，并通过卷积连接来激励感知人脸的单元。

description:
在本问题中，我们将会研究一种最基本的局部特征——"角点"。从数学上说，角点可以被认为是两条边相交的点；边在图片中，可以认为是其梯度（导数）图像上的光滑连续段（如果你拿黑笔在白纸上画一条直线，由于黑线是一个有宽度的区域，所以实际上是会有两条非常接近的边）。基于这种考虑，学术界已经提出了若干基于 SUSAN、Harris、CSS 等，并有一定表现的角点算法。我们提供了描述 SUSAN、Harris、CSS 算法的一些阅读材料，而你的任务是则是基于我们给出的资料，选取适合自己的算法并完成对应的实现和优化。

注意在实际图片中，由于存在像素离散、色彩渐变、噪声、失真等等因素，很少会有遵循良定义的边存在，因此按某种数学方法找到的这些特征点，从人的角度而言并不一定是角点，或者说会有一定的偏差。但在具体运用上，虽然这些检测点并非角点，但它们在局部上通常依然有足够的特征，所以依然被广泛应用。

inputFormat:
从标准输入读入数据。

输入的第一行包含两个正整数 $w$、$h$，表示图片的宽度和高度。保证 $w \le 1280$，$h \le 1280$。

接下来 $h\times w$ 行，每行包含 $3$ 个非负整数，描述一个像素。其中这些行中的第 $(i-1) \times w + j$ 行的三个数表示图片第 $i$ 行，第 $j$ 列的像素的 **RGB**，即红（red）、绿（green）、蓝（blue）三通道的数值。整数的范围在 $[0, 255]$ 中。

outputFormat:
输出到标准输出。

第一行一个整数 $k$，表示检测到的角点数量。

接下来 $k$ 行，每行两个非负整数 $x$、$y$，描述一个角点的坐标。**注意：坐标中 $x$ 是横坐标，即宽度方向；$y$ 是纵坐标，即高度方向。图像左上角的像素 （第 $1$ 行第 $1$ 列）的坐标规定为 $(0, 0)$**。

samples:
见附件压缩包中的 1~10.in。
见附件压缩包中的 1~10.ans。

hint:
#### 样例 $1$ 解释

这组样例的图片和其参考的检测结果如下左图和右图。

![](https://cdn.luogu.com.cn/upload/image_hosting/3vdmk3ar.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/ht9npydk.png)
#### 数据和评分方法

测试数据一共 $20$ 张图片，每张图片就是一个测试点。**另外**有 $10$ 张图片已经作为你的参考用例和预测试数据。注意：本题的预测试数据与样例**完全相同**，且预测试数据的评测结果与最终评测结果**没有关系**。

我们使用 CSS + Harris(refine) 的结果作为参考算法，并将在参考算法上人工标注的结果作为参考答案。

在评价你的角点是否正确输出时，我们会对你输出的角点和答案的角点进行二分图最大匹配。其中如果一对点对 $a$，$b$ 满足 $a$ 在以 $b$ 为中心的 $5 \times 5$ 范围以内，那么我们认为这个角点对是可匹配的。如果一个你输出的角点在最大匹配中，那么我们就认为这个角点是正确的。

每个测试点的得分比例用 $F_1$ 表示，它的具体定义为

$$
F_1 = \frac{2\mathit{TP}}{2\mathit{TP}+\mathit{FP}+\mathit{FN}}
$$

其中 $\mathit{TP}$（true positive）表示是正确输出的角点数量（即最大匹配数），$\mathit{FP}$（false positive）表示你输出的点中错误的角点数量，$\mathit{FN}$（false negative）表示正确的角点中没有被你的角点匹配的数量。

对 $F_1$ 的更进一步解释为：你输出的点中，正确的比例 $\frac{\mathit{TP}}{\mathit{TP}+\mathit{FP}}$ 叫做“准确率”；应该输出的点中，被你输出的比例 $\frac{\mathit{TP}}{\mathit{TP}+\mathit{FN}}$ 叫做“召回率”。$F_1$ 是准确率和召回率的调和平均数。

我们选取的图片会保证提供材料中的算法**在特定的优化下**都会有较好的表现。在给定的测试图片下，参考算法对角点的 $F_1$ 检测率为 $90\%\sim 100\%$ 左右。

#### 如何完成本题

下发文件除参考用例外，还有两类文件：描述参考算法的文档和其中一部分实现、一些工具。这些材料你可以任意使用，包括阅读并实现、直接使用部分代码、使用它们辅助你实现或调试等。你也可以不使用它们，完全自己完成本题。

我们推荐你实现我们给出材料中三个算法中的一个或者两个，并在此基础上尝试进行自己的调整~~或魔改~~。三种算法的实现难度和效果从低到高分别为：SUSAN（或它的一种实现方式FAST），Harris，CSS。

工具中包括：输入和PNG格式图片的转换工具，输出结果的可视化工具。

下发文件的具体使用方法，以及**文档的导读**请阅读文件中的 `README.pdf`。

最后请注意：如果你需要用到下发文件中的代码，你应当将其直接复制到你提交的代码中，而不应该使用诸如 `#include` 的方法尝试包含它。你只能提交一个文件，且测试时无法读取到给你的这些文件。


title: [THUWC 2018] 七彩序列

background:
来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。

2018 清华大学信息学冬季体验营（THUWC 2018）D2T2。$\texttt{5s,0.5G}$。

description:
给出 $n$ 种颜色的小球若干，颜色的编号从 $1$ 至 $n$ ，第 $i$ 种颜色的小球共有 $a_i$ 个。小 $L$ 要把这些小球排成一个序列，使得**不**存在一个非空前缀或非空后缀是“整齐的”。这里我们称一个前缀或后缀是“整齐的”，当且仅当其中**所有 $n$ 个颜色**小球的出现次数相同。你的任务是计算本质不同的序列数目。

善良的 temporaryDO 给大家指出了一些必要的说明：

1. 一个序列长度为 $len$ 的**前缀**（后缀）指的是序列中最靠**左**（右）的 $len$ 个小球。而非空前缀或后缀指的即是 $len\neq 0$ 的前缀或后缀。

2. 对于一个小球的序列 $S$，令 $S_i$ 表示从左到右数的第 $i$ 个小球的颜色。我们认为两个小球序列 $S, T$ 本质不同，当且仅当存在一个位置 $i$ 使得 $S_i$ 不同于 $T_i$。

为了避免高精度，你只需要计算答案对 $998,244,353$ 取模的结果即可。

inputFormat:
从标准输入读入数据。

输入的第一行包含一个整数 $n$ ，表示颜色的种类数。

接下来一行包含 $n$ 个用空格隔开的整数，第 $i$ 个正整数为 $a_i$ ，表示第 $i$ 种颜色小球的数量。

outputFormat:
输出到标准输出。

输出包含一行一个整数，表示本质不同的小球序列数目对 $998,244,353$ 取模的结果。


title: [GESP202409 二级] 数位之和

description:
小杨有 $n$ 个正整数，他认为一个正整数是美丽数字当且仅当该正整数每一位数字的总和是 $7$ 的倍数。

小杨想请你编写一个程序判断 $n$ 个正整数哪些是美丽数字。

inputFormat:
第一行包含一个正整数 $n$，表示正整数个数。
之后 $n$ 行，每行一个包含一个正整数 $a_i$。

outputFormat: 对于每个正整数输出一行一个字符串，如果是美丽数字则输出 `Yes`，否则输出 `No`。

hint:
### 数据规模与约定

对全部的测试数据，保证 $1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^5$。


title: [GESP202409 二级] 小杨的 N 字矩阵

description:
小杨想要构造一个 $m \times m$ 的 $N$ 字矩阵（$m$ 为奇数），这个矩阵的从左上角到右下角的对角线、第 $1$ 列和第 $m$ 列都是半角加号 `+` ，其余都是半角减号 `-` 。例如，一个 $5 \times 5$ 的 N 字矩阵如下：

```plain
+---+
++--+
+-+-+
+--++
+---+
```

请你帮小杨根据给定的 $m$ 打印出对应的 N 字矩阵。

inputFormat: 输入只有一行包含一个正整数 $m$。

outputFormat: 输出对应的 $N$ 字矩阵。

hint:
### 数据规模与约定

对全部的测试数据，保证 $3 \leq m \leq 49$ 且 $m$ 是奇数。


title: 「BalkanOI 2023 Day1」Car Race

description:
**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day1 T1「[Car Race](https://boi2023.zotks.si/wp-content/uploads/day_1/d1_car_race/en_EN.pdf)」**

为了吸引更多的游客和资金到曾经骄傲但现在几乎被废弃的马里博尔工业区，这座城市在前 Metalna 工厂的地点建了一条赛道（Metalna 工厂是 1990 年代初被迫关闭的多家马里博尔大型企业之一）。赛道的形状是一棵有 $n$ 个顶点的有根树。树的顶点用整数 $0,1, \ldots, n-1$ 编号，根的编号是 $0$。

比赛开始了！最初，有些顶点上有赛车。每秒，每辆赛车都向着根的方向移动到相邻的顶点。在任何时刻，如果两辆或更多的赛车同时在一个编号大于 $0$ 的顶点上，它们就会相撞，不能再参加比赛。根上可以在任何时刻容纳任意数量的赛车。

对于每个顶点 $v$，输出一个整数 $c_{v}$，它的定义如下：

- 如果在比赛开始时顶点 $v$ 上没有赛车，$c_{v}$ 是 $-1$。
- 否则，如果从顶点 $v$ 出发的赛车在到达根的途中相撞，那么 $c_{v}$ 是 $-1$。
- 否则，$c_{v}$ 是从顶点 $v$ 出发的赛车到达根的时间。

inputFormat:
第一行包含一个整数 $n$，表示树的顶点数。

第二行包含 $n-1$ 个整数 $p_{1}, p_{2}, \ldots, p_{n-1}$。$p_{i}\ (1\leq i\leq n-1)$ 表示顶点 $i$ 的父亲，满足 $0 \leq p_{i}<i$。

第三行包含 $n$ 个整数 $a_{0}, a_{1}, \ldots, a_{n-1}$。如果在比赛开始时顶点 $i$ 上有赛车 $a_{i}=1$；否则 $a_{i}=0$。

outputFormat: 输出一行包含 $n$ 个整数 $c_{0}, c_{1}, \ldots, c_{n-1}$，整数之间用一个空格分隔。