title: [COCI2016-2017#5] Poklon

description:
给定一个包含 $N$ 个自然数的数组。

接着需要回答 $Q$ 次询问，每次询问输出区间 $[L,R]$ 内恰好出现两次的自然数的数量。

inputFormat:
第一行，两个整数 $N,Q$，分别表示数组元素数量和询问次数。

第二行，$N$ 个整数，表示数组中的元素。

接下来的 $Q$ 行，每行两个整数 $L,R$，表示询问的区间。

outputFormat: 共 $Q$ 行，依次对应每次询问的结果。

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

区间 $[1,3]$ 中只有 $1$ 恰好出现了两次。

**【数据规模与约定】**

对于 $40\%$ 的数据，$N,Q \le 5000$。

对于 $100\%$ 的数据，$1 \le N,Q \le 5 \times 10^5$，$1 \le L \le R \le N$，数组中的元素都是小于 $10^9$ 的自然数。

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T5 Poklon_。**

**本题分值按 COCI 原题设置，满分 $140$。**


title: [Kubic] Division

type: P

background: 建议先看 F 题题目背景。

description:
你有一个**可重集**，初始其中只有一个正整数 $n$。

你每次可以选择当前在集合中的一个正整数 $x$ 并删去，再指定一个正整数 $y$（不要求在集合中）满足 $x>y$，并往集合中加入 $y$ 和 $x-y$。

你需要保证在**任意时刻**，集合中的最大值**严格小于**集合中的最小值的 $2$ 倍。

求出你**最多**能进行多少次操作，并**输出构造方案**。

**输入数据保证最多能进行的操作次数不超过 $10^6$**。

inputFormat: 共一行，一个整数 $n$。

outputFormat:
第一行，一个整数 $m$，表示你所构造的方案的操作次数。

接下来 $m$ 行，每行两个整数 $x,y$，表示一次操作（$x,y$ 的意义与题面中一致）。

你需要保证 $x>y$ 且 $x$ 在当前集合中出现过。

hint:
对于 $100\%$ 的数据，$1\le n\le 10^9$。

||分值|$n$|
|:-:|:-:|:-:|
|$\operatorname{Subtask}1$|$10$|$\le 10$|
|$\operatorname{Subtask}2$|$20$|$\le 100$|
|$\operatorname{Subtask}3$|$30$|$\le 10^6$|
|$\operatorname{Subtask}4$|$40$|无特殊限制|

### 评分方法

以下情况将会使你在该测试点获得 $0$ 分：

- 输出格式不满足要求。

- 输出多余信息（包括空格和换行符）

- 构造的方案操作次数与标准答案不同。

- 构造的方案不符合题目要求。

- 时间超限。

如果没有上述情况，你在该测试点获得满分。

**保证 SPJ 占用不超过 $100\operatorname{ms},10\operatorname{MB}$**

### 样例解释 1

一种操作过程如下：

`8`

`3 5`

`2 3 3`

可以证明没有更优的方案。

### 样例解释 2

一种操作过程如下：

`30`

`12 18`

`8 10 12`

`6 6 8 10`

`5 5 6 6 8`

`4 4 5 5 6 6`

可以证明没有更优的方案。


title: [BalticOI 2006 Day 1] BITWISE EXPRESSIONS

background: 在信号处理中，当变量是在一定范围内的整数时，人们有时会对包含按位 AND 和 OR 运算符的某个表达式的最大值感兴趣。你要编写一个程序，以这样的表达式和每个变量的范围作为输入，并确定表达式可以接受的最大值。

description:
为简单起见，该表达式具有特定的形式，即由按位 AND 操作符（表示 $\& $）分隔的圆括号内的若干子表达式。每个子表达式由一个或多个变量组成，变量之间用按位 OR 操作符（表示为 $|$ ）分隔。使用这种约定，可以通过给出子表达式的数量以及每个子表达式中变量的数量来完全指定表达式。变量只是根据它们在表达式中的出现情况进行编号。
举例，如果子表达式的个数为 $4$，并且每个子表达式中的变量个数为 $3$，$1$，$2$，$2$，则表达式为:
$$E=(v_1|v_2|v_3) \& (v_4) \& (v_5|v_6) \& (v_7|v_8)$$
按位操作符是用普通的方式定义的。例如，要执行 $21 \& 6$ 的运算，我们首先写下数字（操作数）的二进制形式：$10101$ 和 $110$（因为 $21=2^4+2^2+2^0$ 和 $6=2^2+2^1$）。结果中的每个二进制数字现在都取决于操作数中对应的数字:如果两个操作数中都是 $1$，那么结果数字就是 $1$，否则就是 $0$。如下图最左边所示，结果值为 $4$。如果我们想计算 $21| 6$，其过程是相同的，唯一不同的是，如果对应的数字在任何一个操作数中都是 $1$，则结果是 $1$，因此只有在两个操作数中都是 $0$ 的情况下，结果才会是 $0$。如下图中央所示，结果是 $23$。推广到两个以上操作数是很简单的。下面最右边的例子说明了 $30 \& 11 \& 7=2$。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/o3cxkqdr.png)

inputFormat: 第一行给出两个正整数 $N$ 和 $P$。第二行给出 $P$ 个正整数（$K_1,K_2, \cdots ,K_P$），其中 $K_i$ 为第 $i$ 个子表达式中的变量个数。$K_i$ 都大于等于 $1$，并且它们的和等于 $N$。下面 $N$ 行中每一行包含两个整数 $A_j$ 和 $B_j$，根据 $A_j \le v_j \le B_j$ 指定表达式中第 $j$ 个变量的取值范围。

outputFormat: 一行，包含一个整数：表达式可以接受的最大值。

hint:
#### 数据规模与约定
对于 $100 \% $ 的数据，$1 \le N \le 100$，$1 \le P \le N$，$0 \le A_j \le B_j \le 2×10^9$。
#### 样例说明
样例限制上述表达式中八个变量的值，分别为：$2 \le v_1 \le 4、1 \le v_2 \le 4、v_3=0、1 \le v_4 \le 7、1 \le v_5 \le 4、1 \le v_6 \le 2、3 \le v_7 \le 4$ 和 $2 \le v_8 \le 3$。如果用二进制记数法写，最好的赋值之一给出了表达式 $(100|011|000) \& (111) \& (100|010) \& (100|011)$，从中我们可以注意到，所有子表达式可以变成等于 $7$，除了第三个。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 1:Bitwise](https://www.cs.helsinki.fi/group/boi2006/tasks/bitwise.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [BalticOI 2006 Day 1] COIN COLLECTOR

description:
在一个国家，有 $N$ 种面额的硬币在流通，包括 $1$ 分硬币。此外，还有一种面值 $K$ 分的纸币，其价值超过了任何一种硬币。有个硬币收藏家想收集每种面额的硬币标本。他家里已经有几枚硬币了，但目前他的钱包里只有一张 $K$ 分的纸币。他在一家商店里，那里的商品都以低于 $K$ 分的所有价格出售（$1$ 分，$2$ 分，$3$ 分，$\cdots$，$K-1$ 分）。在这家商店，零钱是按照以下算法找零的：
1. 让零钱的数额是 $A$ 分。
1. 找到不超过 $A$ 的最高面额(让它是 $B$ 分硬币)。
1. 给顾客一枚 $B$ 分硬币，把 $A$ 减去 $B$。
1. 如果 $A=0$ ，结束；否则返回步骤 $2$。

硬币收藏家用 $K$ 分买了一件东西。
你的任务是编写一个程序来确定:

- 有多少种不同的硬币，收藏家在他的之前的收藏中没有而可以通过此次交易获得?
- 在这个过程中，商店能卖给他的最贵的东西是什么?

inputFormat: 第一行包含整数 $N$ 和 $K$。接下来的 $N$ 行描述流通中的货币。第 $i+1$ 行包含整数 $c_i$ 和 $d_i$，$c_i$ 表示硬币的面额（分），$d_i$ 为 $1$ 表示该收藏家已有该面额硬币，为 $0$ 表示还无。硬币按价值递增的顺序排列，即：$c_1 < c_2 <  \cdots < c_N$。第一枚硬币已知是 $1$ 分硬币，即：$c_1=1$。

outputFormat: 第一行包含一个整数，即收集者尚未拥有、但可以通过一次购买获得的最多硬币面额数。第二行包含一个整数，即要购买的商品的最高价格，以便找零包括第一行的新面额的最大数量。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \le N \le 5×10^5$，$2 \le K \le 10^9$，$1 \le c_i \le K$。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 1:Coins](https://www.cs.helsinki.fi/group/boi2006/tasks/coins.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [BalticOI 2006 Day 1] COUNTRIES

background: 任何一个国家都是由弱小而拼搏斗争逐渐强大崛起的。

description:
考虑地区的二维地图，在这张地图上有 $n$ 个城市。每个城市 $i$ 在地图上都有一个独特的坐标（$x_i$,$y_i$）。每个城市在一个将军的指挥下有 $s_i$ 个士兵。
城市 $i$ 对另一个位置（$x$,$y$）的威慑为 $s_i$ 除于它和（$x$,$y$）间距离的平方。这就好像城市 $i$ 中的大量士兵对它周围所有地图位置施加了威慑。如果城市 $j$ 对（$x_i$,$y_i$）的城市 $i$ 的威慑超过其士兵数 $s_i$：城市 $j$ 可以派遣足够的士兵前去制服保卫城市 $i$ 的士兵，那么城市 $i$ 就被城市 $j$ 所威胁。如果城市 $i$ 没有受到任何其他城市 $j$ 的威胁，那么心存感激的市民将选出其无敌的将军作为他们的国王，并将他们的城市变成他的王国的首都。
另一方面，如果一些城市 $j$ 对（$x_i$,$y_i$）的城市 $i$ 的威胁比另一个城市 $k$ 对城市 $i$ 的威胁更具威慑，那么城市 $i$ 的居民别无选择：城市 $i$ 只能向城市 $j$ 投降。从今以后，城市 $i$ 必须服从城市 $j$ 所服从的首都；然而城市 $i$ 的士兵并没有加入城市 $j$ 或其首都的军队。除此之外，城市 $i$ 会因为 $j$ 和 $k$ 两个对它具有同等威胁的城市之间相互防备而得救：如果其中一个城市攻击并征服城市 $i$，那么另一个城市将会前来攻击并战胜先前刚战斗完而疲惫不堪的攻击方士兵。但这种情况下，城市 $i$ 的居民们将不再选举他们的将军为他们的国王，因为他未能履行他的职责保护城市免受威胁。因此，他们必须把他们的城市变成一个民主国家的首都。
你的任务是编写一个程序，将地图上的城市信息作为输入，并为每个城市 $i$ 输出三种结果之一:
- 它是一个王国的首都。
- 它是一个民主国家的首都。
- 它服从城市 $j$ 作为它的首都。

inputFormat: 第一行由一个整数 $n$ 组成，表示城市数。接下来的 $n$ 行给出这 $n$ 个城市的信息，每行给出一个城市的。第 $i+1$ 行以三个整数 $x_i$，$y_i$，$s_i$ 表示城市 $i$ 的信息，这三个整数由单个空格字符分隔。

outputFormat:
输出由 $n$ 行组成，其中第 $i$ 行由城市 $i$ 的结果组成:
- 字母 $\texttt{K}$ 表示城市 $i$ 是一个王国的首都。
- 字母 $\texttt{D}$ 表示城市 $i$ 是一个民主国家的首都。
- 正整数 $j$ 表示城市 $i$ 不得不投降而服从其首都的城市 $j$ 。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \le n \le 1000$，$0 \le x_i,y_i,s_i \le 1000$，$1 \le j \le n$。
#### 样例说明
考虑以下地图，其中每个点代表一个城市，上面给出了它的士兵数量：
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/gmptiqan.png)
也就是说，位置（$3$,$2$）上的城市 $3$ 是一个王国的首都，它还包括位置（$1$,$1$）上的城市 $4$ 和位置（$2$,$1$）上的城市 $5$。另一方面，位于位置（$2$,$5$）的城市 $1$ 自己形成了一个王国，而位于位置（$2$,$3$）的城市 $2$ 自己形成了一个民主国家。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 1:Countries](https://www.cs.helsinki.fi/group/boi2006/tasks/countries.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [BalticOI 2006 Day 2] CITY PLANNING

description:
一个星球上将建造一个空间站。这个空间站将雇用 $N$ 人。他们必须住在某个地方，为此，空间站周围将建起一座城市。空间站周围的土地被划分为等大小的方形地块，每个地块上可以建一幢最高 $K$ 层的公寓楼。每幢楼每层都应有一套公寓，每个人都应住在单独的公寓里。其空间站的坐标为（$0$,$0$），其余的编号如下所示：
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/8rtnay67.png)
由于地块之间的交通只能在街道上通行，所以地块（$x$,$y$）到空间站的距离为 $|x|+|y|-1$ 个单位。
建造一幢座房子的费用等于建每层楼的费用之和。众所周知，建造一个楼层的成本取决于楼层的高度，而不是建筑的位置。
将要建造的房子将使用 $30$ 年。住在这些房子里的人将去空间站工作，在这 $30$ 年里，将他们运送到空间站和离开空间站将花费每人 $T·d$，其中 $d$ 是一个人的建筑到空间站的距离。
我们可以假设星球足够大，待建的城市只占地表的一小部分，所以我们不需要考虑星球表面的曲率。
你的任务是写一个程序来确定 $30$ 年来建造房屋和运营运输系统的最低总成本。

inputFormat: 第一行包含整数 $N$，$T$和 $K$。接下来的 $K$ 行指定了每层楼的公寓建造成本。第 $i+1$ 行包含整数 $c_i$，表示在第 $i$ 层建造一套公寓的成本（假设所有第 $i−1$ 层以下都已经建造）。众所周知，建设一个较高的楼层总是比建设一个较低的楼层更昂贵：$c_1<c_2< \cdots <c_k$。

outputFormat: 唯一的一行包含一个整数——建设城市和运营交通系统 $30$ 年的总成本。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \le N \le 10^{12}$，$1 \le T \le 5×10^5$，$1 \le K \le 20000$，$1 \le c_i \le 2×10^9$，约定答案不超过 $8×10^{18}$（也就是说，它将适合64位带符号整数）。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 2:City](https://www.cs.helsinki.fi/group/boi2006/tasks/city.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [BalticOI 2006 Day 2] RLE COMPRESSION

description:
RLE 是一种简单的压缩算法，用于压缩包含相同字符后续重复的序列。 通过压缩特定的序列，我们获得其编码。这个想法是用一个计数器表示给定字符（例如 $\texttt{aaaaa}$）的重复，以表示有多少次重复。即，我们用包含重复标记，重复字符和代表重复次数的整数的三元组来表示它。 例如，$\texttt{aaaaa}$ 可以编码为 $\texttt{＃a5}$ （其中 $\texttt{＃}$ 表示重复标记）。
我们需要以某种方式表示字母，重复标记和计数器。让字母由 $n$ 个字符组成，这些字符由集合 $\Sigma= \lbrace 0,1, \cdots ,n-1 \rbrace$ 中的整数表示。来自 $\Sigma$ 的字符序列的编码也是来自 $\Sigma$ 的字符序列。 在任何时候，重复标记都由 $\Sigma$ 中的字符表示，用 $e$ 表示。最初 $e$ 为 $0$，但在编码过程中可能会改变。
该编码解释如下：
- 除重复标记外，编码中的任何字符 $a$ 都表示自身；
- 如果编码中出现重复标记 $e$，则以下两个字符具有特殊含义：
   $\circ$ 如果 $e$ 后面跟着 $ek$，则表示 $e$ 的 $k+1$ 个重复，
   $\circ$ 否则，如果 $e$ 后跟 $b0$（其中 $b {=}\mathllap{/\,} e$），则 $b$ 将是从该点开始的重复标记，
   $\circ$ 否则，如果 $e$ 后面跟随 $bk$（其中 $b {=}\mathllap{/\,} e$ 并且 $k>0$），则它表示 $b$ 的 $k+3$ 个重复。

使用上述方案，我们可以从 $\Sigma$ 编码任何字符序列。例如，对于 $n=4$，序列 $\texttt{1002222223333303020000}$ 可以编码为 $\texttt{10010230320100302101}$。编码 $\texttt{1}$ 的第一个字符表示简单 $\texttt{1}$。接下来的 $\texttt{001}$ 编码为 $\texttt{00}$。然后，$\texttt{023}$ 表示 $\texttt{222222}$，$\texttt{032}$ 表示 $\texttt{33333}$，而 $\texttt{010}$ 将重复标记切换为 $\texttt{1}$，然后 $\texttt{0302}$ 代表自己，最后 $\texttt{101}$ 编码 $\texttt{0000}$。
序列可以以多种方式编码，并且编码长度可以变化。给定一个已经编码的序列，您的任务是查找字符数最少的编码。
编写一个程序，该程序：
- 读取字母的大小和序列的编码。
- 查找该序列的最短编码。
- 写出结果。

inputFormat: 第一行包含一个整数 $n$：字母的大小。第二行包含一个整数 $m$：编码的长度。最后一行包含 $\lbrace 0,1, \cdots ,n−1 \rbrace$ 中的 $m$ 个整数，这些整数之间用单个空格分隔，表示序列的编码。

outputFormat: 第一行应包含一个整数 $m'$：代表给定序列的编码中最少的字符数。输出的最后一行应包含集合 $\lbrace 0,1, \cdots ,n−1 \rbrace $中的 $m'$ 个整数，以单个空格分隔：该序列的编码。如果存在几个最短的序列，则程序应输出其中的任何一个。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$2 \le n \le 10^5$，$1 \le m \le 2×10^6$。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 2:RLE](https://www.cs.helsinki.fi/group/boi2006/tasks/rle.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。
Special Judge 感谢 Jakub Pawlewicz 和  @[AzzyZhe](/user/274209)。


title: [BalticOI 2006 Day 2] JUMP THE BOARD!

description:
一个 $n×n$ 的游戏板是由整数填充的，每格一个非负整数。目标是从左上角以任何合法路径跳到右下角。任何一格中的整数表示跳离该位置的步长。如果步长将推进越出游戏板，那么在那个特定的方向上的跳步是禁止的。所有的跳步必须是向右或向下。请注意，$0$ 是一个死胡同，它阻止任何进一步的进展。
如图 $1$ 中所示的 $4×4$ 板，实圆标识起始位置，虚线圆标识目标位置。图 $2$ 展示了从起点位置到目标位置的三条合法路径，每个路径中都删除了不相关的数字。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/0ql0hhx0.png)
你的任务是编写一个程序来确定从左上角到右下角的合法路径的数量。

inputFormat: 第一行包含一个正整数 $n$，表示该板的行列数。接下来 $n$ 行数据。每行包含 $n$ 个整数，每个整数的范围是 $0 \cdots 9$。

outputFormat: 唯一的一行包含一个整数，即从左上角到右下角的合法路径数。

hint:
#### 数据规模与约定
- 对于 $100 \%$ 的数据， $4 \le n \le 100$。
- 合法路径的数量可能相当大。使用 $64$ 位整数变量（C 中的 `long long int`，Pascal 中的 `Int64`）只能获得 $70 \%$ 的分数。可以保证所有的输入导致的路径数可以用不超过 $100$ 位的数字写出。

#### 题目说明
来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 2:Jump](https://www.cs.helsinki.fi/group/boi2006/tasks/jump.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: 「CGOI-1」丑国旅游

background: 丑国风景优美，是远近闻名的旅游胜地（并不）。来丑国旅游的人很多。

description:
丑国的一角排列着编号从 $1$ 到 $n$ 的 $n$ 个城市。当一个人在第 $i$ 个城市时，能且仅能走到第 $i+1$ 个城市。

第 $i$ 个城市中的人们最讨厌丑值为 $a_i$ 的人。当一个丑值为 $x$ 的人从第 $i$ 个城市走到第 $i+1$ 个城市时，他会获得 $|x-a_i|\times|x-a_{i+1}|$ 的舒适值。

现在有 $m$ 个人要来丑国旅游，第 $i$ 个人的丑值为 $x_i$，要从城市 $l_i$ 走到 $r_i$，问他得到的舒适值之和是多少。

**由于这个数可能很大，你需要求出对 $10^9+7$ 取模后的值**。

由于你不能预知到下一次旅游，我们会强制你在线。

**简化版题意：**

给出 $n$ 及 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$。

$m$ 次在线询问，每次询问给出 $x,\,l,\,r$，求 $\sum\limits_{i=l}^{r-1}|x-a_i|\times|x-a_{i+1}|$。

inputFormat:
第一行输入两个整数 $n,m$，分别表示城市数与旅游人数。

第二行输入 $n$ 个整数，第 $i$ 个数表示 $a_i$，含义如上所述。

接下来 $m$ 行，每行输入三个整数 $X,\,L,\,R$，记上一次的旅游的总舒适值对 $10^9+7$ 取模后为 $s$（若是第一次询问，则 $s=0$），则 $x_i=X\operatorname{xor}s,\;l_i=L\operatorname{xor}s,\;r_i=R\operatorname{xor}s$，其中 $\operatorname{xor}$ 表示异或，而 $x_i,\,l_i,\,r_i$ 的含义如上所述。

outputFormat: 输出 $m$ 行，第 $i$ 行的数表示第 $i$ 个人的总舒适值对 $10^9+7$ 取模后的值。


title: 『PG1』[JDWOI-2] 猪猪大厦

description:
$ \texttt{piggy} $ 建了一个巨大无比的 $\texttt {PIG}$ 大厦，可以看做一个平面，在这个平面上有 $n$ 个无限长的不垂直或平行于地面的扶手电梯，可以看做一些一次函数，并且这些电梯方向均朝右即 $x$ 轴正方向。

两个电梯的交汇点可以花 $1 \ \texttt{ZMB}$ 换乘。

一个人想要给  $ \texttt{piggy} $ 发短信让 $ \texttt{piggy} $ 过去找他 。

但是：

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

于是只能走过去找 $ \texttt{piggy} $。

此时他站在第 $x_1$ 个电梯的横坐标为 $y_1$ 位置。

$ \texttt{piggy} $ 在第 $x_2$ 个电梯的横坐标为 $y_2$ 位置。

请问他最少花多少 $\texttt{ZMB}$ 才能过去？

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

第二行四个整数 $x_1,y_1,x_2,y_2$。

接下来 $n$ 行，第 $i$ 行两个数 $k_i,b_i$，表示电梯的解析式为 $y=k_ix+b_i$。

outputFormat: 最少花多少 $\texttt{ZMB}$？如果无法到达，输出 `-1`。

hint:
**本题采用 Subtask。**

$\sf Subtask1(20pts)$：$1 \le n \le 10$；

$\sf Subtask2(30pts)$：$1 \le n\le 1000$；

$\sf Subtask3(50pts)$：$1 \le x_1,x_2 \le n\le 10^5$，$-10^3 \le y_1,y_2,k_i,b_i \le 10^3$。

**电梯的编号从 1 开始。**


title: [RC-05] 排列

description:
给出 $1\sim n$ 的排列 $p$，下标从 $1$ 开始。

**恰好** $K$ 次任意选择 $1\le i<n$ 并交换 $p_i,p_{i+1}$。问交换完毕后，字典序最小的排列 $p$ 是什么？

inputFormat:
第一行两个非负整数 $n,K$，分别表示排列中数的个数和交换次数。

接下来一行 $n$ 个整数，描述排列 $p$。

outputFormat: 一行以空格隔开的 $n$ 个正整数，描述交换完成之后的排列。


title: [APIO2021] 封闭道路

background: 本题只支持 C++ 提交，提交时不需要包含 `roads.h` 头文件，只需要将附件中的 `roads.h` 中的内容粘贴到代码的开头即可。

description:
在泗水市，有 $N$ 个路口（编号从 $0$ 到 $N-1$）。这些路口由 $N-1$ 条双向道路连接（编号从 $0$ 到 $N-2$），因此通过这些道路，任意一对路口之间都有一条唯一的路径。$i$ 号道路（$0 \le i \le N-2$）连接着 $U[i]$ 号和 $V[i]$ 号路口。

为了提高环保意识，泗水市长 Pak Dengklek 计划举办无车日。为了鼓励该活动，Pak Dengklek 将组织封路。Pak Dengklek 将首先选择一个非负整数 $k$，然后封闭一些道路，以使每个路口只能直接连接至多 $k$ 条未封闭的道路。封闭 $i$ 号道路的成本为 $W[i]$。

请你帮助 Pak Dengklek 对每个可能的非负整数 $k$（$0 \le k \le N-1$）计算封闭道路的最低总成本。

你需要实现下列函数：

`int64[] minimum_closure_costs(int N, int[] U, int[] V, int[] W)`

- $N$：泗水市的路口数量。

- $U$ 和 $V$：大小为 $N-1$ 的数组，其中 $U[i]$ 号路口和 $V[i]$ 路口通过 $i$ 号道路直接连接。

- $W$：大小为 $N-1$ 的数组，其中封闭 $i$ 号道路的成本为 $W[i]$。

- 该函数需要返回一个大小为 $N$ 的数组。对每个 $k$（$0 \le k \le N-1$），$k$ 号元素是使得每个路口与至多 $k$ 条未封闭道路直接连接的最低总成本。

该函数将被调用恰好一次。

inputFormat:
示例测试程序按如下格式读取输入数据:

- 第 $1$ 行：$N$
- 第 $2+i$（$0 \le i \le N-2$）行：$U[i]$ $V[i]$ $W[i]$

outputFormat: 示例测试程序输出仅一行，包含一个数组，表示 `minimum_closure_costs` 的返回值。

hint:
## 例子

### 例子 $1$

考虑如下调用:

`minimum_closure_costs(5, [0, 0, 0, 2], [1, 2, 3, 4], [1, 4, 3, 2])`

这个例子中共有 $5$ 个路口和 $4$ 条道路，分别连接着路口 $(0,1),(0,2),(0,3)$ 和 $(2,4)$，封闭它们的成本依次为 $1,4,3$ 和 $2$。

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

为了得到最低的总成本：

- 如果 Pak_Dengklek 选择 $k=0$，那么所有道路都需要封闭，总成本为 $1+4+3+2=10$；
- 如果 Pak_Dengklek 选择 $k=1$，那么需要封闭 $0$ 号道路和 $1$ 号道路，总成本为 $1+4=5$；
- 如果 Pak_Dengklek 选择 $k=2$，那么需要封闭 $0$ 号道路，总成本为 $1$；
- 如果 Pak_Dengklek 选择 $k=3$ 或 $k=4$，那么没有道路需要封闭。

因此，`minimum_closure_costs` 应该返回数组 $[10,5,1,0,0]$。

### 例子 $2$

考虑如下调用：

`minimum_closure_costs(4, [0, 2, 0], [1, 0, 3], [5, 10, 5])
`

这个例子中共有 $4$ 个路口和 $3$ 条道路，分别连接着路口 $(0,1),(2,0)$ 和 $(0,3)$，封闭它们的成本依次为 $5,10$ 和 $5$。

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

为了得到最低的总成本:

- 如果 PakDengklek 选择 $k=0$，那么所有道路都需要封闭，总成本为 $5+10+5=20$；
- 如果 PakDengklek 选择 $k=1$，那么需要封闭 $0$ 号道路和 $2$ 号道路，总成本为 $5+5=10$；
- 如果 PakDengklek 选择 $k=2$，那么需要封闭 $0$ 号道路或 $2$ 号道路，总成本为 $5$；
- 如果 PakDengklek 选择 $k=3$，那么没有道路需要封闭。

因此，minimum_closure_costs 应该返回数组 $[20,10,5,0]$。

## 约束

- $2 \le N \le 10^5$
- $0 \le U[i],V[i] \le N-1$ $(0 \le i \le N-2)$
- 任意一对路口可以通过道路互相到达。
- $1 \le W[i] \le 10^9$ $(0 \le i \le N-2)$。

## 子任务
1. (5 分) $U[i]=0$ $(0 \le i \le N-2)$
2. (7 分) $U[i]=i$，$V[i]=i+1$ $(0 \le i \le N-2)$
3. (14 分) $N \le 200$
4. (10 分) $N \le 2000$
5. (17 分) $W[i]=1$ $(0 \le i \le N-2)$
6. (25 分) $W[i] \le 10$ $(0 \le i \le N-2)$
7. (22 分) 无附加限制


title: [APIO2021] 六边形领域

background: 本题只支持 C++ 提交，提交时不需要包含 `hexagon.h` 头文件，只需要将附件中的 `hexagon.h` 中的内容粘贴到代码的开头即可。

description:
对于一个用六边形无限平铺的平面，Pak Dengklek 站在其中一个格子上，并称该格子为初始格子。如果六边形平铺中的两个格子有公共边，则称它们是相邻的格子。对于一步移动，Pak Dengklek 可以从一个格子向六个可能的方向（从 $1$ 到 $6$ 编号，如下图所示）移动到与其相邻的格子上。

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

对于某个由 $N$ 次行动构成的行动序列，Pak Dengklek 可以用其产生的路径（对应一个按序访问的格子序
列）构造一个领域。其中第 $i$ 次行动由移动方向 $D[i]$ 和在该方向上的移动步数 $L[i]$ 组成，并且该路径应有如下性质：

- 路径是 _封闭_ 的，这意味着在格子序列中，起点格子与终点格子（即初始格子）相同。
- 路径是 _简单_ 的，这意味着在格子序列中，除了初始格子访问过恰好两次（起点和终点分别访问一
次），其他格子只能被访问至多一次。
- 路径是 _暴露_ 的，这意味着在格子序列中，每个格子与至少一个不在序列中出现过的非 _内部格子_ 相邻。
    - 如果一个格子不在格子序列中出现过，并且从它出发，在不经过格子序列中任何格子的情况下，（通过若干步移动） 只能访问到有限个格子，我们就称该格子是 _内部格子_ 。

下图是一个符合上述条件的路径例子。其中：

- $1$ 号格子（粉色）是初始格子。
- 被编号的格子（淡蓝色）组成格子序列，编号代表它被访问的顺序。
- 被标上叉号的格子（深蓝色）是 _内部格子_。

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

构造出的领域只包含所有路径上的格子和内部格子。领域中格子 $c$ 的距离定义为：在只经过领域中包含格子的情况下，从初始格子出发到达 $c$ 所需要的最少移动步数。领域中一个格子的分数定义为 $A+d \times B$，其中 $A$ 和 $B$ 是 Pak Dengklek 给定的常数，$d$ 是该格子在领域中的距离。下图给出了用上示路径构成的领域中每个格子的距离。

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

请帮助 Pak Dengklek 计算，用给出的行动序列构成的领域中，所有格子的分数之和。由于总分数值可能很大，最终结果对 ${10}^9+7$ 取模。

你需要实现下列函数：

`int draw_territory(int N, int A, int B, int[] D, int[] L)`

- $N$：行动序列中行动的次数。
- $A,B$：分数计算中的常数。
- $D$：大小为 $N$ 的数组，其中 $D[i]$ 表示第 $i$ 次行动的方向。
- $L$：大小为 $N$ 的数组，其中 $L[i]$ 表示第 $i$ 次行动的移动步数。
- 函数应该返回用给出的行动序列所构成的领域中，所有格子的分数总和对 ${10}^9+7$ 取模后的值。
- 该函数将被调用恰好一次。

inputFormat:
示例测试程序按如下格式读取输入数据：

- 第 $1$ 行：$N$ $A$ $B$
- 第 $2+i$（$0 \le i \le N-1$）行：$D[i]$ $L[i]$

outputFormat:
示例测试程序按如下格式输出你的答案：

- 第 $1$ 行：`draw_territory` 的返回值。


title: [APIO2021] 雨林跳跃

background:
本题只支持 C++ 提交，不支持 C++14 (GCC 9)，提交时不需要包含 jumps.h 头文件，只需要将附件中的 jumps.h 中的内容粘贴到代码的开头即可。

由于洛谷的测试点限制，本题只能评测其中的 100 组数据。

description:
在苏门答腊岛的热带雨林中，有 $N$ 棵树排成一排，从左到右依次用 $0$ 到 $N-1$ 进行编号，其中 $i$ 号树的高度为 $H[i]$，且所有树的高度**互不相同**。

Pak Dengklek 正在训练一只猩猩，让她能够从一棵树上跳到另一棵树上。对于一次跳跃，猩猩可以从一棵树，向左或向右跳到比当前这棵树高的第一棵树上。形式化地，如果猩猩当前在 $x$ 号树，那么当且仅当满足下列条件之一时，她能够跳到 $y$ 号树上：

- $y$ 是满足 $H[z]>H[x]$ 的所有 $z$ 中比 $x$ 小的最大非负整数；或者：
- $y$ 是满足 $H[z]>H[x]$ 的所有 $z$ 中比 $x$ 大的最小非负整数。

Pak Dengklek 有 $Q$ 个跳跃计划，每个计划用四个整数 $A$，$B$，$C$ 和 $D$（$A \le B<C \le D$）来描述。对于每个计划，Pak Dengklek 想知道猩猩是否能够从某棵树 $s$（$A \le s \le B$）出发，经过若干次跳跃，到达某棵树 $e$（$C \le e \le D$）。若该计划可行，Pak Dengklek 还想知道可行方案中猩猩需要的最少跳跃次数。

你需要实现下列函数：

`void init(int N, int[] H)`

- $N$：树的数量。
- $H$：大小为 $N$ 的数组，$H[i]$ 表示 $i$ 号树的高度。
- 该函数在第一次 `minimum_jumps` 的调用前，将会被调用恰好一次。

`int minimum_jumps(int A, int B, int C, int D)`

- $A,B$：可以用作起点的树的编号范围。
- $C,D$：可以用作终点的树的编号范围。
- 该函数需要返回可行方案中猩猩需要的最少跳跃次数，或者返回 $-1$ 表示该计划不可行。
- 该函数将被调用恰好 $Q$ 次。

inputFormat:
示例测试程序按如下格式读取输入数据：

- 第 $1$ 行：$N$ $Q$
- 第 $2$ 行：$H[0]$ $H[1]$ $\cdots$ $H[N-1]$
- 第 $3+i$（$0 \le i \le Q-1$）行：$A$ $B$ $C$ $D$，表示第 $i$ 次 `minimum_jumps` 调用的参数。

outputFormat:
示例测试程序按如下格式输出你的答案：

- 第 $1+i$（$0 \le i \le Q-1$）行：第 $i$ 次 `minimum_jumps` 调用的返回值。

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

考虑如下调用：

`init(7, [3, 2, 1, 6, 4, 5, 7])`

在初始化完成后，考虑如下调用：

`minimum_jumps(4, 4, 6, 6)`

该计划意味着猩猩必须从 $4$ 号树（高度为 $4$）出发，并到达 $6$ 号树（高度为 $7$）。

一种跳跃次数最少的可行方案为：先跳到 $3$ 号树（高度为 $6$），再跳到 $6$ 号树。

另一种方案为：先跳到 $5$ 号树（高度为 $5$），再跳到 $6$ 号树。

因此，`minimum_jumps` 应该返回 $2$。

考虑另一个调用：

`minimum_jumps(1, 3, 5, 6)`

该计划意味着猩猩必须从 $1$ 号树（高度为 $2$），$2$ 号树（高度为 $1$），或 $3$ 号树（高度为 $6$）之一出发，并最终到达 $5$ 号树（高度为 $5$）或者 $6$ 号树（高度为 $7$）。

唯一一种跳跃次数最少的可行方案为：从 $3$ 号树出发，直接跳到 $6$ 号树。

因此，`minimum_jumps` 应该返回 $1$。

考虑另一个调用：

`minimum jumps(0, 1, 2, 2)`

该计划意味着猩猩必须从 $0$ 号树（高度为 $3$）或者 $1$ 号树（高度为 $2$）出发，并最终到达 $2$ 号树（高度为 $1$）。

由于 $2$ 号树是高度最低的树，所以无法从其他树上跳到 $2$ 号树。

因此，`minimum_jumps` 应该返回 $-1$。

**【数据范围】**

- $2 \le N \le 2 \times {10}^5$。
- $1 \le Q \le {10}^5$。
- $1 \le H[i] \le N$（$0 \le i \le N - 1$）。
- $H[i]\ne H[j]$（$0 \le i<j \le N - 1$）。
- $0 \le A \le B<C \le D \le N - 1$。

**【子任务】**

1. （4 分）：$H[i]=i+1$（$0 \le i \le N-1$）。
2. （8 分）：$N,Q \le 200$。
3. （13 分）：$N,Q \le 2000$。
4. （12 分）：$Q \le 5$。
5. （23 分）：$A=B$，$C=D$。
6. （21 分）：$C=D$。
7. （19 分）：无附加限制。


title: [COCI2021-2022#3] Kućice

description:
圣诞集市中有 $n$ 个摊位。每个摊位可以抽象为平面直角坐标系中的一个点，其坐标为 $x_i,y_i$。

现在每个摊位均有 $50\%$ 的概率违规。所有违规的摊位会被一个栅栏圈住，其中栅栏的形状为所有违规摊位对应的点组成的凸包的边界。当然，一些没有违规的无辜摊位也有可能被圈住。当违规摊位数量小于 $3$ 时，凸包显然会退化为线段、点或空集。

求被圈住摊位的期望数量。可以证明答案可以被表示成 $\frac{m}{2^n}$，其中 $m$ 为正整数。因此只需要输出 $m$ 对 $10^9+7$ 取模后的值即可。

inputFormat:
第一行，一个正整数 $n$，表示摊位的数量。

接下来的 $n$ 行，每行两个整数 $x_i,y_i$，表示摊位的坐标。数据保证不存在坐标相同的摊位且任意三个摊位都不共线。

outputFormat: 输出 $m$ 对 $10^9+7$ 取模后的值。

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

唯一的摊位违规的概率为 $50\%$，故期望值为 $\frac{1}{2}$。

**【样例 2 解释】**

违规的情况共有 $8$ 种，而每种情况下被圈住的摊位数分别为 $0,1,1,1,2,2,2,3$。故期望值为 $\frac{1}{8}(0+1+1+1+2+2+2+3)=\frac{12}{8}$。

**【数据规模与约定】**

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：每个点都在由所有点组成的凸包的边界上，同时 $n \ge 3$。
- Subtask 2（30 pts）：除了第一个点外，每个点都在由所有点组成的凸包的边界上，同时 $n \ge 4$，$x_1=y_1=0$。
- Subtask 3（10 pts）：$1 \le n \le 15$。
- Subtask 4（30 pts）：$1 \le n \le 100$。
- Subtask 5（30 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 1000$，$|x_i|,|y_i| \le 10^6$。

**【提示与说明】**

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 5 Kućice_。**

**本题分值按 COCI 原题设置，满分 $110$。**


title: [THUPC2021] 区间本质不同逆序对

description:
给定一个长为 $n$ 的序列 $a$。

有 $m$ 次询问，每次询问给定一个区间 $[l,r]$，求 $|{(a_i,a_j) : l\le i<j\le r \wedge a_i>a_j}|$。

$1\le n\le 10^5$，$1\le m\le 5\times 10^5$。

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

第二行 $n$ 个正整数，其中第 $i$ 个数 $a_i$ 表示序列第 $i$ 个位置的值，保证 $1\leq a_i \leq n$。

第三行一个正整数 $m$。

之后 $m$ 行，每行用两个空格隔开的正整数，分别表示 $l,r$，表示一次询问，保证 $1\leq l\le r \leq n$。

outputFormat: 输出 $m$ 行，第 $i$ 行输出一行一个整数，表示第 $i$ 次询问的答案。

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

对于第一次询问，集合为 $\{(3,2)\}$。

对于第二次与第三次询问，集合为 $\{(2,1),(3,1),(3,2)\}$。

对于第四次询问，集合为空集。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_0/tree/master](https://github.com/yylidiw/thupc_0/tree/master) 查看。


title: [THUPC2021] 视频倍增期

description:
为了更好地衡量视频质量，快手的产品经理提出了视频的“倍增期”的概念。倍增期是一个以秒为单位的时间量指标，其含义是视频的累计播放量从只有目前的一半到当前总播放量所耗费的时长。低质量的视频往往高开低走，刚发布时人们出于好奇或者是被标题吸引而点击，一段时间之后口碑断崖式滑坡，所以倍增期很长；高质量的视频则往往低开高走，人们看过之后自发传播和推荐，逐渐积攒起口碑和流量，所以倍增期较短。

小张是快手的一位视频后台管理员，有 $n$ 个视频是由小张负责监控的，从 $1$ 到 $n$ 依次编号。小张的一周有 $m$ 秒钟的工作时间，在每秒钟都会有一个需要处理的请求从前台传来，请求分成两种：

- 更新请求：在这一秒钟内，编号在区间 $[l, r]$ 内的视频均获得了 $x$ 次的播放量，需要更新后台的数据；
- 查询请求：前台希望知道编号为 $i$ 的视频的倍增期。设该视频本周当前的累计播放量为 $x$，该查询请求是第 $j$ 秒传来的，该视频本周的累计播放量恰好达到 $\lceil x / 2 \rceil$ 时是在第 $j'$ 秒（$j' \ge 0$），则倍增期被定义为 $j - j'$。

面对如此高频度的信息更新和查询需求，小张感到有些棘手，他希望能得到你的帮助。

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $m$，保证 $1 \le n, m \le {10}^5$。

接下来 $m$ 行，第 $j$ 行表示第 $j$ 秒的请求（$1 \le j \le m$），其格式为以下两种之一：

 - $0 \ l \ r \ x$：表示这是一个更新请求，在第 $j$ 秒，编号在区间 $[l, r]$（$1 \le l \le r \le n$）内的视频获得了 $x$ 次播放量，保证 $1 \le x \le {10}^8$；
 - $1 \ i$：表示这是一个查询请求，查询编号为 $i$（$1 \le i \le n$）的视频在第 $j$ 秒的倍增期。

outputFormat: 对于每一个查询请求，依次输出一行，表示所查询的倍增期。

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

- 第 $2$ 秒时，$4$ 号视频的累计播放量为 $0$，在第 $0$ 秒时达到了 $\lceil 0 / 2 \rceil = 0$ 秒的累计播放量，所以此时 $4$ 号视频的倍增期为 $2$ 秒。
 - 第 $4$ 秒时，$4$ 号视频的累计播放量为 $3$，在第 $3$ 秒时达到了 $\lceil 3 / 2 \rceil = 2$ 秒的累计播放量，所以此时 $4$ 号视频的倍增期为 $1$ 秒。
 - 第 $5$ 秒时，$3$ 号视频的累计播放量为 $6$，在第 $1$ 秒时达到了 $\lceil 6 / 2 \rceil = 3$ 秒的累计播放量，所以此时 $3$ 号视频的倍增期为 $4$ 秒。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_0/tree/master](https://github.com/yylidiw/thupc_0/tree/master) 查看。


title: [THUPC2021] 鬼街

description:
那条街有“鬼街”之称,十年前是 A 市最繁华的地段之一，然而如今这里已无活人居住。

街边七零八落地排着 $n$ 座房子，每栋房子都有一个 $1$ 到 $n$ 之间的独一无二的编号，用仿佛来自地狱的黑漆涂在破瓦残砖上，在黄尘中隐隐若现。

传说，这条街上的鬼是与别处的鬼是不同的，它们喜欢研究数论，会根据数字的性质来选择自己的生活，所以它们才为每一栋房子都画上了编号。

新上任的 A 市市长并不相信魑魅魍魉的传言，为了探清真相，他决定为这条街装上灵异事件监控器。

下面有 $m$ 个事件依次发生。

- 灵异事件：在以 $x$ 的所有质因子为编号的房子里，都发生了 $y$ 次闹鬼。由于神秘的原因，次数 $y$ 可能为 $0$。
- 监控事件：有一个监控器被安装，其监控以 $x$ 的所有质因子为编号的房子，当累计的闹鬼总次数达到阈值 $y$ 时，该监控器会触发报警（若 $y = 0$，则不论被监控的房子是哪几栋，下一次灵异事件都会立即触发该监控器的报警）。不同房子发生的灵异事件次数会被分开统计，不同的监控器互不影响。所有的监控器被从 $1$ 开始依次编号。

请将所有的报警反馈给市长，即每个灵异事件之后，有哪些监控器被触发。

inputFormat:
输入的第一行依次包含两个正整数 $n$ 和 $m$，保证 $1 < n, m \le {10}^5$。

接下来 $m$ 行，每行依次包含三个非负整数 $op$，$x$ 和 $y'$。其中 $op \in \{ 0, 1 \}$，若 $op$ 为 $0$，表示这是一个灵异事件；若 $op$ 为 $1$，表示这是一个监控事件。保证 $1 < x \le n$，$0 \le y' < 2^{32}$。由于神秘的原因，你无法直接得到真实的 $y$，假设 $k'$ 为上一个灵异事件触发的监控器的数量（如果尚未有灵异事件发生，则 $k'$ 为 $0$），真实的 $y$ 为 $y' \oplus k'$。$x$ 和 $y$ 在每个事件中的具体含义如上所述。

outputFormat: 对于每一个灵异事件，依次输出一行。行首是一个非负整数 $k$，表示这个灵异事件触发的报警数量，之后是 $k$ 个从小到大排列的整数，表示触发的监控器的编号。

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

在本样例中，依次发生了以下事件：

- 安装了 $1$ 号监控器，监控编号为 $2$ 和 $5$ 的房子，报警阈值为 $2$。
- 发生了一次灵异事件，$5$ 号房子似乎有闹鬼，但次数为 $0$，没有报警被触发。
- 发生了一次灵异事件，$2$ 号和 $3$ 号房子发生了 $1$ 次闹鬼。$1$ 号监控器上的累计次数达到了 $1$，但尚未触发报警。
- 发生了一次灵异事件，$7$ 号房子发生了 $1$ 次闹鬼，没有报警被触发。
- 发生了一次灵异事件，$3$ 号和 $5$ 号房子发生了 $1$ 次闹鬼。$1$ 号监控器的累计次数达到阈值 $2$，触发报警。
- 安装了 $2$ 号监控器，监控编号为 $2$ 和 $3$ 的房子，报警阈值为 $2$。
- 发生了一次灵异事件，$2$ 号房子发生了 $1$ 次闹鬼。$2$ 号监控器的累计次数达到了 $1$，但尚未触发报警。
- 安装了 $3$ 号监控器，不过其阈值为 $0$，所以下一次灵异事件必会触发其报警。
- 发生了一次灵异事件，$2$ 号房子发生了 $2$ 次闹鬼。$2$ 号监控器的累计次数达到了 $3$，超过了其报警阈值 $2$，所以被触发了报警。同时 $3$ 号监控器的报警也被触发。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_0/tree/master](https://github.com/yylidiw/thupc_0/tree/master) 查看。


title: [THUPC2021] 形式语言与自动机

background: 《形式语言与自动机》是 T 大学 C 系开设的一门专业基础课，在这门课程中，你能学到“常用语言类及其相应的计算模型，以及计算模型之间的联系”。这门课程涉及到不少较为晦涩难懂的理论知识；但对于你的好朋友，曾经在国际比赛中捧杯的小 A 来说，它似乎有些太简单了。

description:
不知道为什么，小 A 虽然上课总在做自己的事情，但是每次布置的作业他用了十几分钟就做完了。你很好奇小 A 为什么这么熟练，但眼下，小 A 上课做的事情似乎更吸引你。

“你每周上课都不认真听，是在做什么？”

“我觉得老师上课讲得还挺水的，就随便做点东西玩玩。不过充其量也就是跟课程相关的吧，随便设计点自动机什么的，测试一下它能接受什么状态。”小 A 盯着他电脑前的草稿纸说道。

过了一会，小 A 看到他屏幕上出现了一堆圆括号。你猜想他可能是设计了一个判断括号序列是否匹配的自动机。但正当你准备和小 A 搭话时，他突然指着屏幕对你说：“你说说这合理吗，我本来输了一个测试用的括号序列，结果手一滑，把光标蹭到了奇怪的地方。我就想着怎么看半天没看出来程序哪里有问题，原来是我输错了。”

你苦笑着回复说：“这不常有的事吗，反正知道问题在哪就好了。”

没想到，这句话反而让小 A 更烦躁了。

“你说常有，那我给你这个串，你试试有多少种方法把它变回一个合法的括号序列。”

诚然，你不是不会算，但是你更想听课。可惜，你没来得及打断小 A 的下一句话。

“那就这么说定了，你要是下课前没算出来，请我吃香锅。”

inputFormat: 输入仅包括一个串 $s$，表示小 A 实际输入的串。保证 $s$ 仅包括 `(` 和 `)`，且二者数量相等。

outputFormat:
输出一个整数，表示**本质不同**的还原方案的个数。

我们定义一种方案可以还原一个括号序列 $s=s_1 s_2 \cdots s_n$，当且仅当存在一个划分 $s=uvw$ 使得 $uwv$ 是合法的括号序列。其中，$u=s_1\cdots s_l$ 可以为空串（此时 $l=0$），但 $v=s_{l+1}\cdots s_r$ 和 $w=s_{r+1}\cdots s_n$ 不是空串。我们称两种还原方案**本质不同**，当且仅当两种方案中的 $l$ 不相同或 $r$ 不相同；即使两种还原方案还原出的串相同，这两种还原方案也可能本质不同。

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

所有可能的还原方案为（其中箭头前后分别为 $s=u+v+w$ 和 $uwv$）：

1. $l=0,r=2$，对应 $\varepsilon$（空串，下同）$+$`()`$+$`()()` $\Rightarrow$ `()()()`；
2. $l=0,r=4$，对应 $\varepsilon+$`()()`$+$`()`$\Rightarrow$`()()()`；
3. $l=1,r=2$，对应 `(`$+$`)`$+$`()()`$\Rightarrow$`(()())`；
4. $l=1,r=4$，对应 `(`$+$`)()`$+$`()`$\Rightarrow$`(())()`；
5. $l=2,r=4$，对应 `()`$+$`()`$+$`()`$\Rightarrow$`()()()`；
6. $l=3,r=4$，对应 `()(`$+$`)`$+$`()`$\Rightarrow$`()(())`。

这些划分方案中，方案 $1,2,5$ 还原出的串和输入的串相同，但这并不影响它们划分的方式不同。

另外，`()()`$+$`()`$+\varepsilon$ 和 `()()`$+\varepsilon+$`()` 都不是合法的还原方案，因为在前一种划分中 $w=\varepsilon$，而在后一种划分中 $v=\varepsilon$。

**【数据范围】**

对于 $100\%$ 的数据，保证 $1\le |s| \le 10,000,000$。

**【提示】**

你不需要掌握《形式语言与自动机》这门课程的相关知识也能通过本题。

另外，《形式语言与自动机》这门课程“很简单”的说法只是本题中虚构人物小 A 的看法，不代表出题人的意见。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_0/tree/master](https://github.com/yylidiw/thupc_0/tree/master) 查看。


title: [THUPC2021] 小 E 爱消除

description:
管道中塞着 $n$ 个彩色的球。这些球的直径相同。从一端到另一端它们的颜色分别为 $c_1,c_2,\ldots,c_n$。

小 E 有一个空的杯子。杯口的直径恰好比球的直径大一些，所以小 E 可以把球放入杯子中，但一次只能放入一个，并且球在杯子中只能竖直叠放。杯子中两个相邻的同色球会一起消失。

由于管道的特殊性，小 E 每次只能选择管道的一端，将最靠外的球取出，然后马上放进杯子里。

问当管道中的球全部取出后，杯子里最少会剩下几个球，以及在此前提下至少需要多大的杯子。

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

第二行 $n$ 个正整数，第 $i$ 个表示 $c_i$。

outputFormat: 输出一行，包含两个非负整数。第一个数表示杯子里剩下球数的最小值。第二个数表示在此前提下杯子需要至少能装下多少个球。

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

一种最优的方案如下：

先将两端的 $3$ 放入杯子中消去。

然后把左端的 $5,1,4,9$ 依次放入杯子，这时杯子中有 $4$ 个球。

再把右端的 $9,4$ 依次放入杯子，每放入一个球就会和杯子里的另一个球消去。在放入 $9$ 后消去前杯子中有 $5,1,4,9,9$，所以杯子需要能够容纳 $5$ 个球。

接着把左端的 $3,3$ 放入杯子，这时被杯子中有 $2$ 个球。

最后把右端的 $1,5$ 依次放入杯子。这时杯子是空的。

图片可见下发文件中的 `Sampledescription.pptx`。

**【数据范围】**

保证 $1 \le n \le 50$，$1 \le c_i \le n$。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_1/tree/master](https://github.com/yylidiw/thupc_1/tree/master) 查看。


title: [THUPC2021] 混乱邪恶

background:
出题人分为 $9$ 种阵营：守序善良、守序中立、守序邪恶、中立善良、绝对中立、中立邪恶、混乱善良、混乱中立和混乱邪恶。真正的出题人，就要能够在阵营之间不断切换，而又不迷失在境界之中。

境界是一个无限大的三角形网格。网格如下图，每个交叉点都有 $6$ 个相邻的交叉点。你从某一个交叉点出发，每次给一个出题 idea 设定风格都会使你在境界中移动一步。

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

description:
每个出题人都有一个守序指数 $L$ 和善良指数 $G$。对于一个 idea，从题面、样例或数据范围的角度，可以从 $6$ 个方向中选择恰好一个作为这个 idea 对应的题目的特有风格，同时会在境界中沿着所选的箭头方向移动一步：

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

你现在一共有 $n$ 个 idea，你知道你给每个 idea 设定某一个风格时你的 $L$ 指数和 $G$ 指数的变化。具体地，对于第 $i$ 个idea有 $12$ 个参数 $tl_{i,l},tl_{i,g},l_{i,l},l_{i,g},bl_{i,l},bl_{i,g},br_{i,l},br_{i,g},r_{i,l},r_{i,g},tr_{i,l},tr_{i,g}$：

如果选择“简洁的题面”，那么 $L$ 变成 $L+tl_{i,l}$，$G$ 变成 $G+tl_{i,g}$；

如果选择“平凡无用的样例”，那么 $L$ 变成 $L+l_{i,l}$，$G$ 变成 $G+l_{i,g}$；

如果选择“宽松的数据范围”，那么 $L$ 变成 $L+bl_{i,l}$，$G$ 变成 $G+bl_{i,g}$；

如果选择“复杂的题面”，那么 $L$ 变成 $L+br_{i,l}$，$G$ 变成 $G+br_{i,g}$；

如果选择“无私馈赠的样例”，那么 $L$ 变成 $L+r_{i,l}$，$G$ 变成 $G+r_{i,g}$；

如果选择“松松松的数据范围”，那么 $L$ 变成 $L+tr_{i,l}$，$G$ 变成 $G+tr_{i,g}$。

这里所有的加法都在模 $p$ 意义下进行。

进入混乱邪恶阵营的要求很苛刻，需要 $L$ 恰好等于 $L^*$ 且 $G$ 恰好等于 $G^*$。

你的 $L$ 指数和 $G$ 指数开始时都为 $0$。请问是否存在一种设定风格的方式使得设定完全部 $n$ 个 idea 的风格后你仍在境界中原来的位置，但是能够进入混乱邪恶阵营。

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

接下来 $n$ 行，每行 $12$ 个非负整数 $tl_{i,l},tl_{i,g},l_{i,l},l_{i,g},bl_{i,l},bl_{i,g},br_{i,l},br_{i,g},r_{i,l},r_{i,g},tr_{i,l},tr_{i,g}$。参数的顺序与题目描述中的一致，无需额外检查。

最后一行两个非负整数 $L^*,G^*$。

outputFormat:
如果能，输出一行 `Chaotic Evil`。

如果不能，输出一行 `Not a true problem setter`。

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

给第 $1$ 个 idea 设定风格为”简洁的题面“，此时你的守序指数为 $0+3=3$，善良指数为 $0+5=5$。你往左上方移动一步。

给第 $3$ 个 idea 设定风格为”宽松的数据范围“，此时你的守序指数为 $3+9=2$，善良指数为 $5+3=8$。你往左下方移动一步。

给第 $2$ 个 idea 设定风格为”无私馈赠的样例“，此时你的守序指数为 $2+1=3$，善良指数为 $8+4=2$。你往右边移动一步。此时你回到了原点并且守序指数为 $3$，善良指数为 $2$。所以你可以进入混乱邪恶阵营。

**【数据范围】**

保证 $1 \le n \le 100$，$1 \le p \le 100$。

保证其他输入数据在 $0$ 到 $p-1$ 之间。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_1/tree/master](https://github.com/yylidiw/thupc_1/tree/master) 查看。


title: [THUPC2021] 赌徒问题

description:
国籍不明，年龄不详的赌徒 Picar 和 Roman 正在玩一个游戏。

正如一些经典的和赌博相关的问题中提到的那样，这个游戏是纯随机的。

每一轮游戏中，参加游戏的赌徒需要先选定一个要下注的号码，并将要下注的金额支付给系统（不妨记游戏中使用的货币单位为 G）。选择的号码可以是 $1$ 至 $n$ 之间的任意整数（$n$ 是固定的正整数），其中号码 $i$ 对应正整数权重 $a_i$。记 $s=\sum_{i=1}^n a_i$，那么系统在每轮游戏中选出号码 $i$ 的概率总为 $a_i/s$。所有参加游戏的赌徒下注结束之后，系统将会按照给定的概率随机挑选一个号码作为中奖号码。下注了中奖号码的赌徒可以根据其下注的金额及中奖号码对应的概率获得相应的奖金，而下注了其它号码的赌徒不会获得任何奖金。

至于返还奖金的比例，一个自然的想法是：无论一个赌徒给哪个号码下注，其期望获得的奖金应该与其下注的金额相等。也就是说，如果一个赌徒为号码 $i$ 支付了 $x$ G，那么他中奖时应获得 $sx/a_i$ 的奖金。

这个游戏的一个小缺陷是，货币 G 的最小面额是 $1$ G，也就是说系统不能返还奖金的小数部分。为了避免这一现象，规定每次下注的金额必须是 $k$ 的正整数倍（其中 $k$ 是固定的正整数）。游戏的设计者需要保证，在给定 $k$ 之后，$k s$ 是每个 $a_i$（$i = 1, \ldots , n$）的正整数倍，这样计算奖金时就不会出现非整数值。

Picar 和 Roman 觉得这游戏很有意思，他们希望在不同的参数下各玩几轮。但是他们不喜欢太大的数字，所以 $s$ 不能超过一个给定的正整数 $m$（显然，由于权重之和最多为 $m$，每个权重也最多是 $m$）。对于权重集合相同的方案，仅仅打乱权重的顺序对游戏体验的改变不大，所以 Picar 和 Roman 认为，两组权重参数本质不同当且仅当这两组参数对应的**可重集合**不同。换句话说，如果将两组权重参数 $a_1, \ldots, a_n$ 和 $b_1, \ldots, b_n$ 分别从小到大排序，得到 $1\le\alpha_1\le\alpha_2\le\cdots\le\alpha_n$ 和 $1\le\beta_1\le\beta_2\le\cdots\le\beta_n$，那么这两组参数本质不同当且仅当存在下标 $i\in\left\{1, \ldots, n\right\}$ 使得 $\alpha_i \ne \beta_i$。

Picar 和 Roman 想知道，给定 $n, m, k$，有多少种满足“要求”的**本质不同**的参数方案。需要注意的是，由于这里吝啬的 Picar 和 Roman 只给了你 $k$，你需要保证你统计的每个方案中，$ks$ 是每个权重 $a_i$（$i = 1, \ldots , n$）的正整数倍。

inputFormat: 输入仅一行，包括三个正整数 $n, m, k$，两个数之间由一个空格隔开。

outputFormat: 输出一个非负整数，表示方案数对 ${10}^9+7$ 取模的结果。

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

满足要求的方案有：

1. $3=1+1+1$；
2. $4=1+1+2$；
3. $6=1+2+3$；
4. $6=2+2+2$；
5. $8=2+2+4$；
6. $9=3+3+3$。

请特别注意，本题的方案是顺序无关的。

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

除了样例 #1 中的方案外，还有：

7. $5=1+2+2$；
8. $6=1+1+4$；
9. $7=1+1+5$；
10. $8=1+2+5$；
11. $9=1+2+6$；
12. $9=1+3+5$；
13. $9=2+2+5$。

**【数据范围】**

对于 $100\%$ 的数据，保证 $1\le n\le 10$，$1\le m \le 2000$，$1\le k \le 10^9$。

**【提示】**

赌博有风险，建议远离赌博。

请选手在提交评测之前确认自己对于数据范围的理解正确。如果你的理解不是正确的，你将有可能获得 Wrong Answer 的评测结果。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_1/tree/master](https://github.com/yylidiw/thupc_1/tree/master) 查看。


title: 「EZEC-9」暂颓恒卷

background: 一些人坐成一横排，学习知识。其中有的人卷，有的人颓。

description:
### 人的行为与定义

一个人要么处于卷态，要么处于颓态。不卷则颓，不颓则卷。

这题中我们认为一共有四种人：

1. 恒卷人。恒卷人无论何时都为卷态。

2. 恒颓人。恒颓人无论何时都为颓态。

3. 暂卷人。若在某一秒暂卷人处于卷态而左右两人都处于颓态，则其下一秒状态更新为颓态。若在某一秒暂卷人处于颓态而左右有一人处于卷态，则其下一秒状态更新为卷态。__简而言之：有卷则卷。__

4. 暂颓人。若在某一秒暂颓人处于颓态而左右两人都处于卷态，则其下一秒状态更新为卷态。若在某一秒暂颓人处于卷态而左右有一人处于颓态，则其下一秒状态更新为颓态。__简而言之：有颓则颓。__

我们称处于卷态的暂卷人为卷态暂卷人，处于颓态的暂卷人为颓态暂卷人，处于卷态的暂颓人为卷态暂颓人，处于颓态的暂颓人为颓态暂颓人。

我们称恒卷人与恒颓人为恒人，暂卷人与暂颓人为暂人。

### 定义后的题目描述

有 $n$ 个人坐成一横排。最左边为第 $1$ 个人，最右边为第 $n$ 个人。

初始时给定第 $i$ 个人为第 $a_i$ 种人。保证 $a_i\in \{1,2,3,4\}$，$a_1,a_n\in\{1,2\}$（这四个编号如上文所示），即第 $1$ 个人和第 $n$ 个人都为恒人。__保证没有两个同类型恒人之间不存在其他恒人，也就是说只看恒人，恒卷人和恒颓人交替出现。__

这排人每人有一种状态，形成一个状态组。一个状态组是稳定的，当且仅当下一秒没有人状态更新。一个状态组的卷数是处于卷态的人数（恒卷人，卷态暂颓人，卷态暂卷人处于卷态）。

这排人的最佳状态组为一个 __稳定__ 的状态组，且卷数是所有稳定的状态组中的最大值（也就是说你可以任意钦定初始状态）。这排人的优秀程度被定义为最佳状态组的卷数。

老师认为他们~~太逊了~~不够优秀。由于恒卷人不必交换，恒颓人无可救药，老师让你交换小于等于 $k$ 对暂人。问交换后优秀程度的最大值。

inputFormat:
第一行两个数 $n$ 与 $k$ 。

第二行 $n$ 个数，其中第 $i$ 个数表示第 $i$ 个人为第 $a_i$ 种人。

outputFormat: 输出一行一个数，为交换小于等于 $k$ 对暂人后优秀程度的最大值。

hint:
【样例 $1$ 说明】

交换第 $5$ 个人与第 $6$ 个人，此时优秀程度为 $7$（第 $1,2,3,5,6,7,8$ 个人处于卷态）。

【数据规模与约定】

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

-  Subtask 1（30 points）：$1\leq k\leq2$，$n=9$。
-  Subtask 2（20 points）：只有第 $1$ 个人和第 $n$ 个人是恒人， $k>0$。
-  Subtask 3（10 points）：$k = 0$。
-  Subtask 4（40 points）：无特殊限制。

对于 $100\%$ 的数据，$a_i\in \{1,2,3,4\}$，$a_1,a_n\in\{1,2\}$，$4 \le n \leq 2\times10^6$，$0\le k \le 2\times 10^6$。

### 提示

Subtask 4 的数据经过了多次加强，一共有 $62$ 个测试点。


title: [THUPC2021] 挑战图灵奖

background: 图染色问题是这样的——给定一个 $n$ 个点，$m$ 条边的图，要求将每个点染上一种颜色，满足任意有边相连的两个点颜色不同，问最少需要多少种颜色。众所周知，图染色是 NPC 问题之一，如果有人能在多项式时间内解决图染色问题，那就相当于证明了 P = NP，恭喜你，下一位图灵奖得主非你莫属！

description:
今天，你的好朋友——敏珂找到了你，宣称他证明了半个图染色问题，希望你帮他看看他的做法对不对，如果你能帮他验证，他会考虑与你分享图灵奖的奖金。敏珂宣称自己解决的问题是这样的：对于一个 $n$ 个点的无向图，图上所有节点编号为  $1,2,\ldots, n$，两点之间有连边，当且仅当两点编号在模 $n$ 意义下相差不超过 $k$，即 $(x,y)$ 之间有一条无向边，当且仅当 $x \neq y$ 且存在 $i$ 满足 $1 \le i \le k$，

$$(x+i) \equiv y \pmod n$$

或

$$(y+i) \equiv x \pmod n $$

，他能够快速求出这个图的染色数。作为评审，你只需要解决一个判定性问题——对于每组数据，敏珂会给出三个正整数 $n$，$k$ 和 $x$，表示在给定 $n$ 和 $k$ 时（$n, k$ 的意义如上文所述），他认为这个图的**染色数**是 $x$，你需要判断他的答案是否正确。

如果你认为他的答案是**正确**的，输出一行 `Correct, but it doesn't necessarily mean that you can win the Turing Award.`；如果你认为他的答案是**错误**的，在第一行输出 `Wrong, don't cheat me, you are too far away from the Turing Award.`。为了让你的答案更有信服力，你还需要在第二行输出一个字符 `0` 或 `1`，`0` 表示你认为敏珂的答案小于这个图的实际染色数，`1` 表示你认为他的答案大于这个图的实际染色数；如果你认为这个问题**以当下计算机算力无法作出准确判断**，输出一行 `The problem is unsolvable, please stop cheating me, Mr.Minke.`。

inputFormat:
输入只有一行，包含三个正整数，分别表示 $n, k, x$,  意义如题面所述。

其中 $1\le x, n \le 10^{1,000,000}$，$1 \le k \le 100$，所有输入均为正整数，且对于所有数据，$n$ 只可能满足 $n \le 10^5$ 或 $n \ge 10^{100}$。

outputFormat:
输出共 $1$ 或 $2$ 行，第一行表示你的判断结果，格式如题面所述；

如果你顺利完成判断并认为敏珂的答案是错误的，则需要在第二行输出一个字符 `0` 或 `1`，`0` 表示敏珂的答案小了，`1` 表示敏珂的答案大了。

samples:
Wrong, don't cheat me, you are too far away from the Turing Award.
1

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

很显然，给 $1 \sim 6$ 号点分别染色为 $1, 2, 3, 1, 2, 3$ 是可行的，所以 $n = 6$，$k = 2$ 情况下对应的染色数为 $3$。

**【提示】**

1. 如果没有 idea，请再次阅读题面给的数据范围，也许能对解题有一些帮助。

2. Hint 1 可能没有用。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_1/tree/master](https://github.com/yylidiw/thupc_1/tree/master) 查看。


title: 「EZEC-10」排列排序

description:
给你一个长度为 $n$ 的排列 $p_1,p_2, \cdots ,p_n$。你需要把它排序。

每次可以花区间长度，即 $r-l+1$ 的代价，选择排列中的任意一段区间 $[l,r]$，并将 $[l,r]$ 从小到大排序。

现在你可以让他进行若干次这个操作，直到 $p$ 中元素的值从 $1$ 到 $n$ 按升序排序，即对于 $1$ 到 $n$ 的每一个 $i$，都有 $p_i=i$。

求问花的代价最少为多少？

inputFormat:
本题有多组询问，第一行有一个数 $T$ 表示询问组数。

对于每组询问：

第一行给出一个整数 $n$。

第二行 $n$ 个整数，由空格隔开，代表排列 $p$ 中元素的值。

outputFormat: $T$ 行，每行一个整数表示一组询问的答案。

hint:
【样例 $1$ 说明】

对于第一组数据，可选择区间 $[2,3]$ 进行排序。

对于第二组数据，可选择区间 $[1,3]$ 进行排序。

【数据规模与约定】

对于 $20\%$ 的数据，$n\leq 4$。

对于另 $30\%$ 的数据，$\sum n\leq5000$。

对于另 $10\%$ 的数据，$p_1=n$。

对于 $100\%$ 的数据，$1\le T,\sum n\le 10^6$。


title: [COCI2011-2012#4] KINO

description:
电影院的每排有 $N$ 个座位。座位分为普通座位（$\texttt S$）和爱心座位（$\texttt L$）。其中，爱心座位总是两两出现。

每排座位的相邻两个座位之间都设有一个杯架（除了两个爱心座位之间外）。特别地，一排座位的两侧也都设有杯架。

现有 $N$ 位顾客坐满这 $N$ 个座位，求最多有多少人能够使用杯座。

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

第二行，$N$ 个字符 $\texttt{S/L}$，分别表示普通座位和爱心座位。

outputFormat: 输出能够使用杯座人数的最大值。

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

若用 $\texttt *$ 来表示杯座，那么座位情况如下：

$\texttt{* S * L L * L L * S * S * L L *}$

**【数据规模与约定】**

- 对于 $100\%$ 的数据，$1 \le N \le 50$。

**【提示与说明】**

**题目译自 [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 1 KINO_。**

**本题分值按 COCI 原题设置，满分 $50$。**


title: [THUPC2021] 星星

background:
**往寻奥之星辰** ——镜（于建安七年（A.D. 0202））

> “某年月日，有挚友二人，曰镜曰奥，求索星辰之秘。初苦无所用，次苦无所得。后逢乱，奥迁于外，亦不知所踪矣。区区之身亦可望天命耶，固其情可叹矣。余撰此文以叙之。”
> ——《荧惑记<序>》

宇宙纪元 1024 太阳年第 256 地球日，于斯特罗法斯星系，“赫希萨基”小行星矿区，“吉伽克”号高级采矿船。

库洛船长本来在阅读几千年前所书写的《荧惑记》，这被考证是人类第一次对于星空的正式的有其科学目的观察记录，可是系统里一阵急促的报警声打扰了他。

“副牵引仓隔离罩人为损坏”船员在系统损管备注里写道，“我们可爱的公主柯娜达又拉来了一块巨大的石头把隔离罩磕坏了，还说要送给马卡那小子”

柯娜达是船长的女儿，马卡是大副的公子，大概还算得上是青梅竹马吧。

库洛船长又开始头痛了，这已经是第三次了，维修科上次就警告过没有多余的当前型号的隔离罩了。

“您还是不要责怪可爱的柯娜达了，”维修科的队长表示，“不过倒可以尝试用那些不能旋转的做一个替代出来，可我算不清楚要开多大的孔。”

作为主脑数据组的一员，库洛船长请你帮助维修科计算一下至少要开多大的孔。

description:
隔离罩是用来尽量防止其他宇宙射线对于扫描仪（不是牵引器！）的损坏的重要部件。

简单的，我们可以把切割前的隔离罩看成一个单位球面如下图所示：

工作计划上要完成 $N$（$1 \le N \le {10}^6$）次观测任务。

对于第 $i$ 观测次，我们从点 $(0,0)$ 出发，扫描位于点 $(x_i,y_i,z_i)$，半径为 $r_i$（$-{10}^6 < x_i,y_i < {10}^6$，$0 < r_i < z_i < {10}^6$）的陨石。
这里我们可以简单的将陨石认为成一个圆球体。

每次观测我们都要保证我们可以通过防护罩上开的洞扫描陨石的全貌。

现在请你计算我们将要开的防护罩上的圆洞在球面上的半径（大圆弧长），即所有陨石球在上半单位球投影的并的最小覆盖圆（这里的圆是在曲面上的）。

由于是单位球，所以这个数值应该等于该圆洞直径上两点与球心连线所呈平面角角度的一半。

显然的，这个角度小于 $\frac{\pi}{2}$ 大于 $0$。若角度为 $\omega$ rad 请你输出 $\frac{\omega}{\pi/2} \times {10}^5$ 并向下取整。

inputFormat:
第一行一个整数 $N$，代表后面有 $N$ 个观测计划。

之后每行四个整数，以空格分割，依序分别为 $x_i,y_i,z_i,r_i$。

outputFormat: 输出一个范围在 $[0, 99999]$ 的整数。

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

下图是各个小行星投影至防护罩的圆和最后挖出来圆洞的示意图。

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

**【提示】**

- 这并不是一道计算机图形学题目。
- 背景故事中所有人物、时间、事件、文字均为虚构。
- 输入较大，建议使用更好的读入输出方式。
- 请尽可能地利用您的代数知识。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_2/tree/master](https://github.com/yylidiw/thupc_2/tree/master) 查看。


title: [THUPC2021] 幸运位置

description:
小 Z 是一个活泼好动的孩子。有一天，她站在数轴上 $b$ 的位置，并准备开始沿着数轴的正半轴移动。小 Z 每移动一步，就会立刻沿着数轴的正半轴前进 $a$ 个单位。奇妙的是，$a,b$ 都是正整数，所以小 Z 任意时刻所处的位置也都是正整数。

小 Z 的幸运数字是一个正整数 $c$。小 Z 认为如果她移动到的位置恰好与 $c$ 互质，那么她认为这个位置是一个幸运位置。请你帮小 Z 计算她是否可以移动到幸运位置；如果可以，请计算出能移动到幸运位置的任意一个移动步数 $n$。

简洁题意：给定三个正整数 $a,b,c$，判断是否存在非负整数 $n$ 使 $(an+b, c)=1$，若存在求任意一个解，其中 $(\cdot, \cdot)$ 表示最大公因数。

inputFormat:
第一行为一个正整数 $T$，表示数据组数。接下来依次输入每组数据。

对于每组数据，输入为一行三个正整数 $a,b,c$，含义见题目描述。

对于所有的输入数据，都有 $1\le T\le 10$，$1\le a,b,c < 10^{2000}$，所有输入数据均按照十进制给出。

outputFormat:
对于每组数据输出一行一个整数。如果找不到合法的移动步数 $n$ 输出 `-1`，否则输出一个非负整数表示一个合法的移动步数 $n$。

所有输出应按照十进制输出，每行输出的长度不得超过 $2000$，测试数据将保证存在输出长度限制内的解。另外，请不要输出多余的空格及任何多余字符，并保证文末有换行符，否则可能将影响评测程序对结果的判定。

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

对于第一组数据，$a=1,b=2,c=3$，此时 $b,c$ 已经互质，$n=0$ 是一个解；

对于第二组数据，$a=1,b=3,c=6$，取 $n=2$ 时有 $an+b=5$，与 $6$ 互质，因此是一个解；

对于第三组数据，$a=2,b=2,c=2$，于是 $an+b=2n+2$，对于任意 $n$ 都有 $(an+b,c)=2$，因此不存在这样的 $n$，故输出 `-1`。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_2/tree/master](https://github.com/yylidiw/thupc_2/tree/master) 查看。


title: [THUPC2021] 群星连结

background:
众所周知，群星和公主连结联动啦！联动的结果是一个叫做群星连结的游戏。

这是一个双人回合制竞赛游戏，双方记为 Alice 和 Bob。游戏有若干**回合**，每个回合依次由先手和后手分别行动一次。

现在聪明的你写了一个优秀的 AI 来玩这个游戏，这个 AI 会遵从游戏规则，并且按照游戏过程条目里既定的策略进行游戏。但是由于您太强了，所以世界上只有这么一个 AI，所以只能自己和自己打。

现在给定这个游戏的初始局面，让这个 AI 分别作为 Alice 和 Bob 对战，其中 Alice 先手。你需要模拟游戏过程，并且判断最终是 Alice 获胜还是 Bob 获胜。

游戏初始局面会通过输入给出。

**【提示】**

本题中，**伤害**、**真实伤害**、**生命值扣除**是三个不同的概念，请注意区分。

description:
#### 基础参数

首先，在游戏开始之前，每个玩家需要选择恰好 $n$ 个角色，并编号 $1,2,3,\dots,n$。

每个角色都有一些基础参数：

1. $HP,hp$ ：最大生命值，生命值；
2. $MP,mp$：最大能量值，能量值；
3. $atk,\Delta_{atk}$：基础攻击力，攻击力增益；
4. $def,\Delta_{def}$：基础防御力，防御力增益；

另外，为方便起见，下文中记 $A=\max(atk+\Delta_{atk},1)$，$D=\max(def+\Delta_{def},0)$。

游戏开始时，生命值 $hp$ 等于最大生命值 $HP$，能量值 $mp$、攻击力增益 $\Delta_{atk}$、防御力增益 $\Delta_{def}$ 均等于 $0$。

$HP,MP,atk,def$ 将由输入给出。

除此之外，每个角色分别拥有一个**天赋**和一个**技能**，分别见**天赋**条目和**技能**条目。

#### 死亡判定

游戏过程的任意时刻，如果某个角色生命值 $hp$ 降到 $0$ **及**以下，则判定该角色【死亡】。

一个角色一旦被判定为【死亡】，则该角色将从场上完全退出，并且生命值被恒定为 $0$，不能通过任何方式回复生命值（即不能起死回生，即使拥有【天赋 — 心胜于物】；另外，也不能通过己方其它角色技能回复生命值），不能普通攻击、发动技能，也不能被选定为优先目标，因而不能被普通攻击。

总之就是不以任何形式参与后续游戏的进程，并且本题中所有“全体”、“所有角色”等词均不包含【死亡】角色。

当某方角色全部被判定【死亡】时，游戏立刻结束，并判定另一方胜利（若此时仍有尚未完成的结算，也全部不再进行）。

#### 参数溢出

在游戏过程的任意时刻，如果某个角色的生命值 $hp>HP$，则 $hp$ 会立刻变成为 $HP$。

在游戏过程的任意时刻，如果某个角色的能量值 $mp>MP$，则 $mp$ 会立刻变成为 $MP$。

#### 优先目标

游戏开始前，每个玩家需要为每个角色选定一个攻击顺序。

具体来说，对编号为 $i$ 的角色，需要确定一个攻击顺序 $p_{i,1},\ldots,p_{i,n}$，满足 $p_{i,1},\ldots,p_{i,n}$ 是一个关于 $1,\ldots,n$ 的排列。

游戏过程的任意时刻，称编号为 $i$ 的优先目标是 $p_{i,j}$，当且仅当 $p_{i,1},\ldots,p_{i,j-1}$ 全部【死亡】，并且 $p_{i,j}$ 没有【死亡】。

#### 普通攻击

普通攻击会对优先目标造成 $A$ 点伤害。

拥有【天赋 — 超凡入圣】的角色则会对优先目标造成 $A$ 点真实伤害。详见**天赋**条目。

拥有【天赋 — 星河力量投射】的角色普通攻击会附加真实伤害。详见**天赋**条目。

#### 天赋

天赋有以下几种类型（每行前的编号为天赋类型的编号，圆括弧 `()` 内部为附加参数）：

0. 【天赋 — 我自闭了】该角色的天赋毫无作用；
1. 【天赋 — 血肉皮囊】该角色免疫一半真实伤害。详情见**生命值扣除环节**条目。
   **真实伤害见生命值扣除条目**；
2. 【天赋 — 星河力量投射】$(x)$ 该角色每次普通攻击会附加的 $x$ 点真实伤害；
3. 【天赋 — 心胜于物】$(x,y)$ 该角色每次己方行动结束后回复 $x$ 点生命值，并**额外**回复 $y$ 点能量值；
4. 【天赋 — 超凡入圣】该角色的普通攻击被视为真实伤害攻击，即该角色的普通攻击不造成伤害，但造成 $A$ 点真实伤害。
5. 【天赋 — 科技至上】$(x,y)$ 该角色每次进行普通攻击后，回复 $x$ 点生命值；该角色每次发动技能后，**额外**回复 $y$ 点能量值。注意：如果普通攻击或发动技能造成对方全部角色【死亡】，则该角色不再回复生命值或能量值。

本题保证天赋附加参数均为**正**整数（但在输入数据中可能会有 $0$，详情参见**输入格式**条目）。

#### 技能

当某个角色能量值等于其最大能量值时（并且在游戏过程中被选定为发动技能的角色），可以清零其能量值并发动一次技能。

技能有以下几种类型（每行前的编号为技能类型的编号，圆括弧` ()` 内部为附加参数）：

0. 【技能：心态崩了！】该角色的主动技能毫无作用。注意，该技能仍然可以被发动，只不过毫无效果而已。
1. 【技能：格林炸裂！】$(x)$ 对敌方**所有**角色造成 $x$ 点伤害，**然后**使敌方**所有**角色能量值减少 $\left\lfloor\frac{mp_{enemy}}{10}\right\rfloor$，其中 $mp_{enemy}$ 为敌方该角色能量值（即对于每个敌方角色，若其当前的能量值为 $mp_{enemy}$，那么受此技能影响，其能量值会变成 $mp_{enemy}-\left\lfloor\frac{mp_{enemy}}{10}\right\rfloor$）。注意，根据规则，敌方角色会先受到伤害而进入生命值扣除环节，在该环节中回复能量值，然后再被该技能扣除能量值。
2. 【技能：日 (zhou) 昇 (ji) 之 (dao) 雨 (dan)！】对敌方**所有**角色造成 $A$ 点真实伤害。
3. 【技能：天楼霸断剑！】$(x)$ 对敌方**所有**目标造成 $\min\left(\left\lfloor\frac{HP_{enemy}}{10}\right\rfloor,x\times A\right)$ 点伤害，其中 $HP_{enemy}$ 为被攻击目标的最大生命值。
4. 【技能：演出开始！】$(x,y)$ 设当前为第 $t$ 回合，则从发动技能开始，到第 $t+x-1$ 回合结束期间，在己方行动结束时，己方全体角色**额外**回复 $y$ 点能量值。
5. 【技能：天狼噬斩！】$(x)$ 将优先目标的防御力增益减小 $x$，**然后**对优先目标造成 $A$ 点真实伤害。
6. 【技能：地 (太) 球 (虚) 蓝 (苍) 色 (蓝) 闪 (闪) 电！】$(x,y)$ 对优先目标造成 $A$ 点真实伤害。另外，设当前为第 $t$ 回合，则从发动技能开始，到第 $t+x-1$ 回合结束期间，敌方所有角色攻击力增益减小 $y$。
7. 【技能：极光绽放！】$(x,y,z)$ 使己方未【死亡】角色生命值最低（如有多个，则编号最小）的恰好一名角色回复 $z$ 点生命值。另外，设当前为第 $t$ 回合，则从发动技能开始到第 $t+x-1$ 回合结束期间，己方所有角色攻击力增益增大 $y$。
8. 【技能：流星！】$(x,y)$ 对敌方所有角色造成 $A$ 点伤害。设当前为第 $t$ 回合，则**从该技能造成伤害后**，到第 $t+x-1$ 回合结束期间，使敌方所有角色防御力增益减小 $y$。注意，本技能先造成伤害，再产生减益。
9. 【技能：精灵庇护！】$(x,y,z)$ 己方全体角色回复 $z$ 点生命值。设当前为第 $t$ 回合，则从发动技能开始，到第 $t+x-1$ 回合结束期间，己方所有角色防御力增益增大 $y$。
10. 【技能：全力超全开！轮回之终末！】$(x)$ 己方所有角色基础攻击力 $atk$、基础防御力 $def$ 变为原先的两倍 $2\times atk, 2\times def$；未【死亡】角色生命值 $hp$ 变为 $\max\left(\left\lfloor\frac{HP}2\right\rfloor,hp\right)$，能量值 $mp$ 变为 $\max\left(\left\lfloor\frac{MP}2\right\rfloor,mp\right)$；设当前为第 $t$ 回合，则从发动技能开始，到第 $t+x-1$ 回合结束期间，己方行动结束时，己方所有角色**额外**回复 $1$ 点能量值。在第 $t+x-1$ 回合结束时，若敌方仍有角色未【死亡】，则己方全体角色强制生命值清零，并被判定为【死亡】。另外，在发动该技能时，场上所有拥有这个技能的角色（包括自己）的技能将被强制替换为 0 号【技能：心态崩了！】（因此该技能最多在游戏中被发动一次）。

本题保证技能附加参数均为**正**整数（但在输入数据中可能会有 $0$，详情参见**输入**条目）。

注意：上述形如“设当前为第 $t$ 回合，则从发动技能开始到第 $t+x-1$ 回合结束期间，……”产生的效果是**可以叠加**的。

#### 生命回复与能量回复

生命值仅可通过天赋和技能回复。

己方行动结束时，己方全体角色能量值增加 $1$。拥有【天赋 — 心胜于物】的角色，以及受【技能：演出开始！】和【技能：全力超全开！轮回之终末！】影响的角色可以额外回复能量值。

当己方角色进行普通攻击或者发动技能后，该角色能量值增加 $1$。拥有【天赋 — 科技至上】的角色发动技能后会回复额外的能量值。

注意，发动技能时，先扣除全部能量值，再发动技能，然后再增加能量值。

特别的，若该技能为【技能：全力超全开！轮回之终末！】，则使发动该技能的角色 $mp=\max\left(mp,\left\lfloor\frac{MP}2\right\rfloor\right)$ 后再增加能量值。

当己方角色因受到伤害而进入生命值扣除环节时，该角色能量值增加 $1$（无论其是否实际扣除生命值）。

**生命值扣除见生命值扣除环节。**

#### 生命值扣除环节

当角色受到伤害或者真实伤害时，该角色立即进入生命值扣除环节（注意，即使受到了 $0$ 点伤害，也会进入生命值扣除环节）。

进入生命值扣除环节后，由能量回复条目，该角色能量值增加 $1$。

假设其受到 $x$ 点伤害和 $y$ 点真实伤害，那么：

- 若该角色因拥有【天赋—血肉皮囊】而免疫一半真实伤害，则其生命值扣除 $\max(x-D,0)+y-\left\lfloor\frac y2\right\rfloor$。
- 否则，其生命值扣除 $\max(x-D,0)+y$。

#### 游戏过程

游戏开始后，可视为若干回合，编号从 $1$ 开始。

每个回合，可以划分为如下 $5$ 个阶段：Alice 行动（期间）、Alice 行动结束、Bob 行动（期间）、Bob 行动结束、当前回合结束。

己方行动期间，

1. 如果己方存在至少一个角色可以发动技能时，则按照技能编号从大到小的顺序选择其中一位发动技能。如果有多个角色满足可以发动相同编号的技能，则选择这些角色中角色编号最大的角色发动技能。
2. 如果己方没有角色可以发动技能，则选择一个优先目标生命值最高的角色发动普通攻击。如果有多个角色的优先目标生命值最高，则选择能对优先目标扣除更多生命值（而不是造成更多伤害！）的角色发动攻击。如果仍然有多个角色可以选择，则选择其中编号最大的角色发动普通攻击。

己方行动结束。

注意，己方行动期间，仅能选择一位角色发动技能，或者选择一位角色进行普通攻击。

inputFormat:
第一行一个正整数 $n$，表示 `Alice` 和 `Bob` 分别有 $n$ 个角色。

接下来 $4 n$ 行，第 $4 i - 3$ 到第 $4 i$ 行描述 `Alice` 的编号为 $i$ 的角色。

在这四行中：

- 第一行，四个非负整数 $HP,MP,atk,def$ 分别表示该角色的最大生命值、最大能量值、基础攻击力、基础防御力，保证 $HP,MP>0$。
- 第二行，$n$ 个正整数 $p_{i,1},p_{i,2}, \ldots ,p_{i,n}$，表示该角色攻击顺序，保证这是一个关于 $1$ 到 $n$ 的排列。
- 第三行，三个非负整数 $tf,x,y$ 表示天赋编号以及附加参数。如果该天赋附加参数不足两个，那么你可以忽略多余的部分（保证此时多余的部分在输入数据中是 $0$）。
- 第四行，四个非负整数 $jn,x,y,z$ 表示技能编号及附加参数。如果该技能附加参数不足三个，那么你可以忽略多余的部分（保证此时多余的部分在输入数据中是 $0$）。

接下来 $4n$ 行描述 `Bob` 的 $n$ 个角色，形式同上。

outputFormat:
如果游戏能够以某一方胜利而结束，那么：

- 第一行，输出一个正整数 $x$，表示游戏在第 $x$ 个回合结束的。
- 第二行，输出一个字符串（`Alice` 或 `Bob`）表示胜者。
- 第三行，输出 $n$ 个非负整数，依次表示胜者的每一个角色在游戏结束时的 $hp$，若该角色已死亡则输出 $0$。

如果游戏永远不会结束或者双方平局，请输出任意卖萌表情。

hint:
**【数据范围】**

$n \le 10$，$HP, MP, atk \gt 0$，$def \ge 0$。

保证在游戏中的任意时刻，所有题面中提及到的参数及表达式的绝对值均不超过 ${10}^9$。

保证游戏在 $23333$ 回合内结束。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_2/tree/master](https://github.com/yylidiw/thupc_2/tree/master) 查看。


title: [THUPC2021] 游戏

description:
小 C 和小 W 两个人打算玩一局双人博弈游戏。

现在小 C 手里有 $n$ 颗相同的石子，小 W 打算把它们分为有顺序的 $m$ 堆，其中第 $i$ 堆石子的数量不能超过 $a_i$，但允许为 $0$。

随后，由小 C 先手，两人轮流进行操作，每次可以选择一堆非空的石子并拿走其中若干个（至少 $1$ 个），无法操作者输。

作为算法竞赛界的老司机，小 C 和小 W 早已对各种游戏的策略摸得门儿清，于是这次他们打算玩点不一样的：他们想要知道，有多少种分石子的方法能使得小 C 有必胜策略。

inputFormat:
第一行，两个正整数 $n, m$（$1 \le n \le {10}^{18}$，$1 \le m \le 10$）。

第二行，$m$ 个非负整数 $a_i$（$0 \le a_i \le {10}^{18}$）。

outputFormat: 一个非负整数，表示方案数对 $998244353$ 取模的结果。

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

以下 $4$ 种方案是符合题意的：$(0,2,4)$、$(1,1,4)$、$(2,0,4)$、$(2,2,2)$。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 [https://github.com/yylidiw/thupc_2/tree/master](https://github.com/yylidiw/thupc_2/tree/master) 查看。


title: 「Wdoi-3」夜雀 treating

background:
经历了一整天的磨难，米斯蒂娅终于迎来了这一天最后一位客人——蓬莱山辉夜。

作为永远亭的大小姐、月之都的公主，辉夜对于经营着平凡小吃摊的米斯蒂娅，向来是一个巨大的挑战。辉夜的口味极其挑剔，以至于米斯蒂娅常常难以满足她的需求。更棘手的是，如果辉夜认为米斯蒂娅招待不周，那么夜雀食堂的后果可能并不会比被幽幽子摧毁好多少。

于是可怜的小夜雀只能向你求助了。

description:
为了伺候这位主客，米斯蒂娅事先准备好了 $2n+1$ 种食材，并排成了一排，第 $i$ 种食材在左起第 $i$ 位，作为**预选食材**。

接着，辉夜对所有食材进行了打分，每个食材被给予了一个在 $[1,2n+1]$ 当中的**互不相等**的分数。其中第 $i$ 种食材的评分为 $A_i$。

由于月之民的奇怪癖好，辉夜喜欢一组连续的数字。因此，她对最终选出来的食材（不妨称为**最终食材**）的满意度，定义为将这些食材**按照其评分从小到大排序后**，其中**最长**的**评分连续**的食材的**长度**。评分连续，也就是这些食材的评分形成了公差为 $1$ 的等差数列。例如，$\{1,4,5,6,8,10,11\}$ 当中，能挑选出来的最长的评分连续的序列是 $\{4,5,6\}$，因此对于这套方案，辉夜的满意度是 $3$。

然而喜欢看乐子的辉夜，决定使用一种诡异的选择方式来折磨米斯蒂娅——

1. 设当前一共有 $2k+1$ 种食材。这些食材被依次排开，米斯蒂娅将这些食材从左到右依次编号为 $1,2,3\cdots (2k+1)$。
2. 米斯蒂娅选择当前处于**中间位置**的材料（也就是编号为 $k+1$ 的材料），并加入最终食材。注意，加入最终食材的食材会被**移出**候选食材。
3. 米斯蒂娅**任选**候选食材中的一种食材，**并移除**。保持剩余食材的相对位置不变。特别的，如果候选食材已空，那么米斯蒂娅不做任何操作。

米斯蒂娅将会不断进行 $1\sim3$ 操作，直到最终食材当中已经有了恰好 $n+1$ 种食材。她想知道，如果按照最优的操作方案，辉夜能获得的最大的满意度是多少。

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

第二行 $2n + 1$ 个整数，表示每种食材的评分。

outputFormat: 一行一个整数，表示按照最优操作方案能得到的最大满意度。

hint:
#### 样例 1 解释

$$
\def{\arraystretch}{1.7}
\begin{array}{|c|c|c|c|}\hline
\textbf{候选食材} & \textbf{选择} & \textbf{删除} & \textbf{最终食材} \cr\hline
4,7,3,6,1,2,5 & 6 & 1 & 6\cr \hline
4,7,3,2,5 & 3 & 7 & 3,6\cr \hline
4,2,5 & 2 & 5 & 2,3,6\cr \hline
4 & 4 & - & 2,3,4,6\cr \hline
\end{array}$$

此时最终食材中最长连续食材编号为 $\{2,3,4\}$ ，长度为 $3$ 。可以证明，没有更优方案。

---

#### 数据范围及约定

$$
\def{\arraystretch}{1.7}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值} \cr\hline
1 & 5 & - & 10\cr\hline
2 & 200 & - & 15\cr\hline
3 & 800 & - & 15\cr\hline
4 & 5\times 10^3& - & 20\cr\hline
5 & 2\times 10^5& \text{A} & 5\cr\hline
6 & 2\times 10^5& - & 35\cr\hline
\end{array}
$$

- 特殊性质 A ：保证 $\forall i\in[1,2n+1]$ 有 $A_i=i$ 。样例 3 即满足该性质。
- 对于 $100\%$ 的数据，有 $1 \leq n \leq 2 \times 10^5$，并且 $A$ 是一个 $1 \sim 2n+1$ 的排列。


title: [BalticOI 2004 Day 1] SCALES

description: 给您一个平衡的臂秤，一组砝码和一个物体。这些砝码的重量为 $1,3,9,27,81, \cdots$，即每个砝码的重量为 $3$ 的幂，对于每个整数 $k≥0$ 正好有一块砝码重量 $3^k$。物体的重量是 $m$，其中 $m$ 是正整数。你的任务是把物体放在左边的秤盘上，然后把一些砝码放在左右一个或两个秤盘上，使得秤平衡。

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

outputFormat: 第一行包含有关放在左秤盘上砝码的信息，第一个数字必须为非负整数――放在左秤盘上的砝码个数，然后是各砝码重量且按递增顺序，数字必须用单个空格分隔。第二行包含与第一行相同格式的有关放置在右秤盘上的砝码的信息。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \le m \le 10^{100}$。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2004](http://www.boi2004.lv/) 的 [Day 1:SCALES](http://www.boi2004.lv/Uzd_diena1.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [Ynoi2007] rvrewsus

description:
给定一个数组 $a_1,a_2,\dots,a_n$ 以及正整数 $b$，请回答 $q$ 组 $[l,r,L,R]$ 形式的询问。

$\land$ 符号表示逻辑与。

在这询问里，你需要：

  1. 创建**无重**集合 $S=\{a_i:l\le i\le r\land L\le a_i\le R\}$；
  2. 定义函数 $r(k)=\begin{cases}\min (x:x\in S)&k=0\\\min(x:x\in S\land r(k-1)<x)&k\neq0\end{cases}$；

  3. 求以下表达式值：

$$\sum_{k=0}^{|S|-1}r(k)b^k$$

所有答案对 $333333333333333397$（一个质数）取模。

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

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_N$。

接下来 $q$ 行每行四个正整数 $l,r,L,R$，表示一组询问。

outputFormat: 输出 $q$ 行，代表对应询问答案。

hint:
Idea：nzhtl1477，Solution：ccz181078，Code：w33z，Data：w33z

 - Subtask 1（2 pts）：$n,q\le5000$；
 - Subtask 2（3 pts）：$n,q\le5\times10^4$；
 - Subtask 3（3 pts）：$R-L\le 300$；
 - Subtask 4（7 pts）：$b=1$；
 - Subtask 5（7 pts）：所有 $a_i$ 互不相同；
 - Subtask 6（11 pts）：$L=0,R=333333333333333396$；
 - Subtask 7（67 pts）：无额外限制。

对于所有数据，$1\le n,q\le2\times10^5$，$1\le L\le R\le n$，$0\le b,a_i,L,R<333333333333333397$。


title: 「dWoi R2」Arcade hall / 街机厅

background:
众所周知，才囚学院地下有一个街机厅，~~百田被星龙马打败了 114514 次~~。

百田不服气，于是他打开了一个单人游戏 —— 先辈的城市。

---

114514 年，火星，幺舅幺舅巴以灵国。

因为有小可爱提出题面过于冗长，所以下方有 **简要题面**。

description:
幺舅幺舅巴以灵国一共有 $n$ 个城市，他们之间用一种神奇的通讯工具 —— 先辈符，第 $i$ 个城市的先辈符上刻有一个正整数 $w_i$。这 $n$ 个城市之前有 $n-1$ 条道路，第 $j$ 条道路连接第 $u_j$ 个城市和第 $v_j$ 个城市，有一个属性 $t_j$，这一条道路就表示为 $(u_j,v_j,t_j)$，其中 $t_j \in \{0,1,2\}$，意为：

- $t_j=0$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是敌对关系；
- $t_j=1$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是平等关系；
- $t_j=2$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是友好关系。

每一条道路都是双向的，并且保证任意两个城市 $u,v$ 之间都是可以互相到达的。

最近火星发生了 MARS-514 病毒疫情，先辈符系统的修建要加快脚步。我们规定：

- $w_i \in [1,R]$，且是一个正整数；
- 对于一条道路 $(p,q,r)$，有如下要求：
	- 当 $r=0$ 时，即第 $p$ 个城市与第 $q$ 个城市处于敌对关系时，需要保证 $w_p \ne w_q$；
    - 当 $r=2$ 时，即第 $p$ 个城市与第 $q$ 个城市处于友好关系时，需要保证 $w_p=w_q$；
    - 当 $r=1$ 时，即第 $p$ 个城市与第 $q$ 个城市处于平等关系时，不需要保证 $w_p$ 与 $w_q$ 的大小关系。

求这样分配 $w_i$ 后，将 $w_i$ 作为一个序列，会形成多少个本质不同的序列 $w_i$。

额外地，幺舅幺舅巴以灵国的统治者浩二结节在建造先辈符发现 $w_i$ 越大，用墨就会越多，建造起来也会越困难，所以浩二结节想知道 $w_i$ 的和的最小值是多少。

注意，本题的序列 $A_i$ 与 $B_i$ 本质相同当且仅当对于所有 $i$ 都有 $A_i=B_i$。

本质不同即为不满足本质相同的两个序列。

---

**简要题面**：

- 有一棵 $n$ 个点的树，第 $i$ 个点有点权 $w_i$，第 $j$ 条边有边权 $t_j$；
- 每一条边 $(u_j,v_j,t_j)$ 两边点的点权有如下要求：
	- $t_j=0$，$w_{u_j} \ne w_{v_j}$；
    - $t_j=1$，没有要求；
    - $t_j=2$，$w_{u_j}=w_{v_j}$；
    - 对任意点权都要有 $w_i \in [1,R]$；
- 求当 $w_i$ 作为序列时，一共有多少种本质不同的序列 $w_i$ 以及 $w_i$ 的和的最小值。

inputFormat:
第一行两个整数 $n,R$ 代表城市数与值域。

接下来 $n-1$ 行每行三个整数 $u_j,v_j,t_j$ 描述一条道路。

outputFormat:
一行两个整数分别代表满足要求的本质不同的序列 $w_i$ 的个数和 $w_i$ 的和的最小值。

如果不存在本质不同的序列（即第一问答案为 $0$），第二问也请输出一个 $0$。

**只有第一问答案对 $10^9+7$ 取模。**

hint:
#### 样例 1 解释

样例中的道路分布如下：

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

一共有 $12$ 种赋值方式：

1. $w_i=\{1,2,2\}$；
2. $w_i=\{1,2,3\}$；
3. $w_i=\{1,3,2\}$；
4. $w_i=\{1,3,3\}$；
5. $w_i= \bf \{2,1,1\}$，这是最优情况；
6. $w_i=\{2,1,3\}$；
7. $w_i=\{2,3,1\}$；
8. $w_i=\{2,3,3\}$；
9. $w_i=\{3,1,1\}$；
10. $w_i=\{3,1,2\}$；
11. $w_i=\{3,2,1\}$；
12. $w_i=\{3,2,2\}$。

#### 样例 2 解释

样例中的道路分布如下：

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

对于第二问，其中一种最优的赋值方式是：$w_i=\{2,1,1,1,1,1,2,1,2\}$。

#### 数据规模与约定

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

- Subtask 1（5 pts）：$t_j=1$ 或 $t_j=2$；
- Subtask 2（5 pts）：$R=1$；
- Subtask 3（10 pts）：$u_j=j$，$v_j=j+1$；
- Subtask 4（20 pts）：$t_j=0$；
- Subtask 5（10 pts）：$n \le 10$，$R \le 5$；
- Subtask 6（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le R \le 100$。

对于 Subtask 1 ~ 5，$R \le 40$。

上面描述 Subtask 时 $t_j=P$ 即为对于所有 $j \in [1,n)$ 都有 $t_j=P$。

其中对于 Subtask 1，“或” 意为 Subtask
1 的一部分测试点满足 $t_j=1$，另一部分测试点满足 $t_j=2$。


title: [COCI2011-2012#4] ZIMA

description:
给定 $N$ 天的气温情况。规定：

- 当一天的温度小于 $0$ 时，则称之为冰冻日。
- 当连续 $T$ 天都是冰冻日时，则称之为一个持续时间为 $T$ 的冰期。

冰期来临之前的若干天都会被标为警示状态。若一个冰期的持续时间为 $T$ 天，则规定：

- 若一段冰期不是所有冰期中最长的，那么冰期来临之前的 $2T$ 天都被标记为警示状态。
- 若一段冰期是所有冰期中最长的，那么冰期来临之前的 $3T$ 天都被标记为警示状态。特别地，如果有多个最长的冰期，则只有一个被标记 $3T$ 天，其它的都为 $2T$ 天。
- 若当前正处于冰期，则不允许对当前冰期进行警示，但若条件允许，可以对未来的冰期进行警示。

你可以任意选择一个最长的冰期使得其来临之前需要被标记 $3T$ 天。求在所有选择的情况中，处于警示状态天数的最大值。

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

第二行，$N$ 个整数 $T_i$，表示这 $N$ 天的温度。

outputFormat: 输出处于警示状态天数的最大值。


title: [BalticOI 2007 Day 1] Ranklist Sorting

description:
在一场比赛中，你会得到几名选手的分数。你的任务是创建一个按分数递减排序的选手的排名表。
不幸的是，用于选手排名表的数据结构仅支持一种操作，即在不改变其他玩家的相对顺序的情况下将玩家从位置 $i$ 移动到位置 $j$。如果 $i > j$，则 $j$ 和 $i-1$ 之间位置的玩家位置增加 $1$，否则如果 $i < j$，则 $i+1$ 和 $j$ 之间位置的玩家位置减少 $1$。
这个操作需要 $i$ 步来定位要移动的玩家，$j$ 步来定位他或她移动到的位置，所以将一个玩家从位置 $i$ 移动到位置 $j$ 的总成本是 $i+j$。规定，位置从 $1$ 开始编号。
确定一个步法序列来创建排名表，使步法的代价之和最小化。

inputFormat:
第一行包含整数 $n$，即玩家数量。
接下来的 $n$ 行中的每一行都包含一个非负整数 $s_i$，即当前顺序中玩家的分数。您可以假设所有分数都是不同的。

outputFormat: 第一行输出用于创建排名表的移动次数。以下几行应按应用顺序指定移动，每次移动都应该用一行包含两个整数 $i$ 和 $j$ 来描述，表示位置 $i$ 的玩家被移动到位置 $j$。数字 $i$ 和 $j$ 必须用一个空格分隔。

hint:
#### 数据规模与约定
对于 $30 \% $ 的数据，$n \le 10$，$0  \le s_i \le 10^6$。
对于 $100 \%$ 的数据，$2 \le n \le 10^3$，$0  \le s_i \le 10^6$。
 #### 题目说明
来源于 [Baltic Olympiad in Informatics 2007](https://www.boi2007.de/en/welcome) 的 [Day 1:sorting](https://www.boi2007.de/tasks/sorting.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [BalticOI 2007 Day 2] Connected Points

description:
考虑一个有 $3×N$ 点的规则网格，网格中的每个点最多有八个相邻点（见图 $1$）。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/4j322bxt.png)
我们有兴趣计算连接网格点以形成满足以下条件的多边形的不同方式的数量：
1. 多边形的顶点集由所有 $3×N$ 个点组成。
1. 多边形的相邻顶点是网格中的相邻点。
1. 每个多边形都很简单，即不能有任何自相交。

当 $N=6$ 时的两个可能的多边形如图 $2$。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/e2yye0px.png)
请编写一个程序，为给定的 $N$ 计算连接点的可能方法数，答案对 $10^9$ 取模。

inputFormat: 唯一的一行包含一个正整数 $N$。

outputFormat: 唯一的一行包含一个整数，为对 $10^9$ 取模的连接这些点的方法数。

hint:
#### 数据规模与约定
对于 $30 \% $ 的数据，$0 < N \le 200$。
对于 $70 \% $ 的数据，$0 <N \le 10^5$。
对于 $100 \%$ 的数据，$0 <N \le 10^9$。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2007](https://www.boi2007.de/en/welcome) 的 [Day 2:points](https://www.boi2007.de/tasks/points.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [COCI2011-2012#4] KEKS

description: 给定正整数 $N,K$ 和一个 $N$ 位数，求在 $N$ 位数中删除 $K$ 位后剩下的数的最大值。

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

第二行，一个 $N$ 位整数。保证没有前导 $0$。

outputFormat: 输出剩下的数的最大值。

hint:
**【数据规模与约定】**

- 对于 $50\%$ 的数据，$N \le 1000$。
- 对于 $100\%$ 的数据，$1 \le K \lt N \le 5 \times 10^5$。

**【提示与说明】**

**题目译自 [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 3 KEKS_。**

**本题分值按 COCI 原题设置，满分 $100$。**


title: [GDOI2016] 疯狂动物城

background:
原题空间限制 512MB。

---

Nick 是只在动物城以坑蒙拐骗为生的狐狸，儿时受到偏见的伤害，放弃了自己的理想。他被兔子 Judy 设下圈套，被迫与她合作查案，而卷入意想不到的阴谋，历尽艰险后成为搭档。他们识破了绵羊副市长 Bellwether 的计划，发现是 Bellwether 陷害食肉动物，用毒药让食肉动物发狂。Bellwether 被抓到了监狱里面， Nick 和 Judy 过上了一段平静的日子。

然而，故事并没有这样结束，之前在车管所帮他们查车牌号的憨厚的树懒 Flash，才是陷害食肉动物事件的幕后主使。Flash 批量制作了大量让食肉动物发狂的药剂，投放到了食肉动物群中。现在，大量的食肉动物被感染，动物城陷入了一片混乱。警察局的牛局长 Bogo 找到了 Nick，希望他能帮忙。幸运的是，动物城联邦安全局非常有先见之明，他们在每个州都秘密放置了一台机器，机器能生产能量石，这些能量石能让食肉动物恢复正常。现在 Nick 和 Judy 需要去启动这些机器。

description:
   动物城是一个有 $N$ 个州的联邦，该联邦是一个树的形状，即 $N$ 个州共有 $N-1$ 条双向道路连接它们，且 $N$ 个州是相互连通的。$N$ 个州的编号依次为 $1,2,3...N$。每个州都有且仅有一台机器。一台机器启动后的下一个时刻，就会开始生产能量石，每个单位时间生产一个。能量石从被生产的时刻开始即生效，每一个单位时间能救一定数量的食肉动物。每个州的解毒机器制造出的能量石的品种可能是不同，第 $i$ 个州的机器生产的能量石每个单位时间能救 $a_i$ 只食肉动物。

   Nick 和 Judy 剩下的时间不多了，他们决定分工合作。 Nick 从 $X$ 州出发，目的地为 $Y$ 州，路径为 $X$ 到 $Y$ 的最短路径。 Nick 从 $X$ 州出发的时刻为 $0$，每隔一个单位时间移动一个州。每到一个州，Nick 就会启动这个州的机器。 Nick 想知道他从 $X$ 州出发到达 $Y$ 州的这段时间里，一共有多少食肉动物被拯救。Nick 在纠结他的路线选择，因此，他会给你若干的询问，希望比他更聪明的你能帮助他。

   在他给你询问的过程中，动物城的局势也在发生着一些变化。动物城联邦安全局可以执行一个修改操作 "$X,Y,delta$" ，会对 $X$ 州到 $Y$ 州的最短路径上的州（包括 $X,Y$ 州）的机器进行升级，这样，这些机器生产出来的能量石，每个单位时间能救的食肉动物的数量会增加 $delta$。树懒 Flash 当然也不会坐以待毙，他有一台监控仪，会监控每个州的机器的情况，每当有机器被升级，监控仪就会保存下当前所有州的机器的属性 $a_i$。Flash可以用一种神秘的武器执行一个读取操作 "$X$" ,把当前各个州的机器恢复到第 $X$ 次保存的状态（$X=0$ 表示未进行过升级时的初始状态）。注意，只有修改操作执行的时后会进行保存。

   现在，依次给出 $M$ 个操作，若该操作为一个询问，请你输出 Nick 在当前局面下，他从 $X$ 州出发到达 $Y$ 州的这段时间里，一共有多少食肉动物被拯救，由于这个答案可能很大，你只需要输出答案模 $20160501$ 后的值。请注意，$M$ 个操作都是被加密过的。

简要题意：
给一棵树，有三种操作：
- 1. 将 $x$ 到 $y$ 的路径上的所有点的点权加上 $delta$。
- 2. 询问 $x$ 到 $y$ 的答案。答案的计算为：对于路径上的点 $i$，设它到 $y$ 的距离为 $s$，则 $i$ 的贡献为 $a_i+a_i\times 2+a_i\times 3+...+a_i\times s$。
- 3. 将这棵树恢复到第 $x$ 次 $1$ 操作之后的版本。

强制在线。

inputFormat:
第一行 $2$ 个整数 $N,M$ 表示节点个数和操作次数。

接下来 $N−1$ 每行 $2$ 个整数 $u,v$ 表示了这棵树中 $u$ 和 $v$ 这 $2$ 个州间有边相连。

接下来一行 $N$ 个整数, 表示这 $N$ 个州的机器制造的能量 $a_i$ 的初始值。

接下来 $M$ 行每行先有一个数字表示了操作的类型：

- 类型 1，代表一个修改操作，接下来有 $3$ 个整数 $X',Y',delta$。
- 类型 2，代表一个询问操作，接下来有 $2$ 个整数 $X',Y'$。
- 类型 3，代表一次读取操作，接下来 $1$ 个整数 $X'$。

$X',Y'$ 是加密后的数字。正确的 $X=X' \text{xor lastans} ,Y=Y' \text{xor lastans}$。$\text{lastans}$ 为上次输出的的答案，如果之前没有输出过那么当成 $0$。

outputFormat: 对于每个操作 $2$，输出一行，每行一个数，为所询问的答案模 $20160501$ 后的值。

hint:
对于 $20\%$ 的数据，$n,m\le 2000$。\
对于另外 $20\%$ 的数据，保证树为一条链，且操作中不含有操作 $3$。\
对于另外 $40\%$ 的数据，保证树为一条链。\
对于 $100\%$ 的数据，$1\le n,m,a_i,delta\le 10^5$。


title: [BalticOI 2000 Day 2] MUTEXES

description:
现代编程语言允许编写由多个执行线程组成的程序。这就好像有几个程序在同一个地址空间并行运行，访问相同的变量。通常，线程需要彼此同步。例如，一个线程可能需要等待另一个线程完成某些计算并将结果存储到某个变量中。
最简单的线程同步工具是互斥锁。互斥锁是一种特殊的对象，可以处于锁定或解锁状态。锁定的互斥锁始终由一个线程拥有。线程可以对互斥锁应用两种操作：LOCK 和 UNLOCK。
当线程对当前未锁定的互斥锁应用 LOCK 时，该互斥锁将被锁定并且该线程获得该互斥锁的所有权。如果一个线程尝试将 LOCK 应用于已被其他线程锁定的互斥锁，则该线程将被阻塞，直到该互斥锁被解锁。
当线程对其拥有的互斥锁应用 UNLOCK 时，该互斥锁将变为未锁定状态。如果有其他线程等待锁定互斥锁，则其中一个线程被授予互斥锁的所有权。如果有多个线程在等待，则任意选择一个。
多线程程序中的常见问题之一是死锁。当两个或多个线程正在等待彼此释放互斥锁并且它们都不能继续时，就会发生死锁。当一个线程正在等待被另一个线程锁定的互斥锁时，也会发生死锁，该线程已终止而没有释放互斥锁。
现为您提供一些线程的描述，您的任务是确定是否会发生死锁。
每个线程都是以下形式的指令序列：
``LOCK <mutex>``
``UNLOCK <mutex> ``
您可以假设以下有关命令：
- 互斥锁的名称是大写字母 A$\cdots$Z；
- 没有线程试图锁定它已经拥有的互斥锁；
- 没有线程试图解锁不属于它的互斥锁。

inputFormat: 第一行包含一个整数为线程数 $M$，后跟描述每个线程的 $M$ 个块。描述线程 $i$ 的块的第一行包含一个整数为该线程中的指令数  $N_i$，然后是 $N$ 行指令。指令不包含多余的空格。

outputFormat:
第一行必须包含一个整数：$D$。如果可能出现死锁，$D$ 必须为 $1$，否则为 $0$。
如果可能出现死锁，则第二行必须描述发生死锁的程序状态。如果存在多个死锁状态，则输出其中任何一个。在这种情况下，我们寻找的是完全死锁，即没有一个线程可以继续执行——线程必须被互斥锁终止或阻塞。如果不可能出现死锁，则该行必须为空。
程序状态通过按照线程在输入中出现的顺序为每个线程指定当前指令的从零开始的索引来描述。对于终止的线程，输出 $-1$ 作为索引。 索引必须在一行上并用空格分隔。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \le M \le 5$，$1 \le N_i \le 10$。
#### 分值说明
本题分值按 BOI 原题设置，**满分** $60$ 。
#### 题目说明
来源于 [Baltic Olympiad in Informatics 2000](http://ingforum.haninge.kth.se/BOI00/boi00.html) 的 [Day 2:Mutexes](http://ingforum.haninge.kth.se/BOI00/BOI007.html#anchor84989)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: 「PMOI-4」猜排列

background:
**这是一道 IO 交互题。**

**请各位选手确认好再提交，防止评测机爆炸。**

description:
小 A 有一个长度为 $n$ 的**排列** $a$，他想请你猜一猜这个排列。你仅能给出以下两种询问：

- `! x y`，他将会告诉你 $a_x \bmod a_y$ 的值，其中你询问的数应当满足 $a_x\gt a_y$ 且 $x\ne y$；否则，他会不高兴并直接判定询问不合法，从而导致 `WA`。
- `? l S p`，你需要给小 A 一个大小为 $l$ 的集合 $S$ 与一个整数 $p$，其中 $S=\{x_1,x_2,x_3,\ldots,x_l\}$，其中对于任意 $1\le i\le l$，$1\le x_i\le n$，且 $x_i$ 互不相同，还要满足 $1\le p\le n$，$1\le l\le n$，小 A 将会告诉你这个集合中 $a_{x_k} \ge p$ 的所有的 $x_k$，返回形式如下：首先会返回一个整数 $L$，接着会返回 $L$ 个整数，表示有 $L$ 个满足条件的 $k$（注意返回的是集合 $S$ 中的元素，而不是下标！）。

你最多只能向小 A 询问 $m_1$ 个问题 $1$，$m_2$ 个问题 $2$，其中问题二中询问的集合大小之和应不超过 $m_3$ 来猜出这个序列。

inputFormat:
输入排列的长度 $n$ 和 $m_1,m_2,m_3$ 以开始交互。

交互过程中，您可以进行题目描述中的两种询问。无论是第一种询问还是第二种询问，交互库都会返回一个整数。

在您确定答案后，请以 `A a[1] a[2] ... a[n-1] a[n]` 的形式输出一行，停止交互。

在您输出一行后，请清空缓冲区：

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 其它语言请自行查阅文档。

outputFormat: 见「交互方式」。


title: 「MCOI-09」Dream and Strings REMATCH

description:
给定 $N$ 以及非负整数序列 $a_1,a_2,\dots,a_N$。

请找到 **任何** 一个整数序列 $b_1,b_2,\dots,b_N$ 满足 $\sum |b_i|\neq 0$，$|b_i|\le 1$，和 $\sum a_ib_i=0$。

inputFormat:
第一行一个正整数 $T$。接下来 $T$ 组数据。

每一组数据两行，第一行一个正整数 $N$，接下来一行 $N$ 个正整数 $a_1,a_2,\dots,a_N$。

outputFormat:
输出 $T$ 行，第 $T$ 行输出对应组数据的 $b$ 序列。

如果无解，输出 $-1$。

hint:
本样例不符合题意 $5000\le N$ 的限制。

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

 - Subtask 1（50 pts）：$10^5\le N$
 - Subtask 2（50 pts）：无特殊限制。

对于 $100\%$ 的数据：$1\le T\le 20$，$5000\le N\le\frac{10^5}{T}$，$0\le a_i\le 10^{18}$。**数据保证随机生成。**


title: 『JROI-2 / Stoi2039』等你下课

description:
给定正整数 $d$，定义

$$S_v=\{(x,y):x,y \in \mathbb{Z_{\ge 0}},x^2-dy^2=v\}$$

求：

$$\sum_{v=1}^{\lfloor\sqrt{d}\rfloor}v[S_v \neq \varnothing]$$

多组询问。

inputFormat:
第一行一个正整数 $t$ 表示询问次数。

接下来 $t$ 行，每行一个正整数 $d$ 表示一次询问。

outputFormat: 对于每次询问输出一行一个整数表示答案。

hint:
#### 样例解释

- 对于 $d=10$，只有 $v=1$ 满足 $S_v \neq \varnothing$。
- 对于 $d=13$，有 $v=1,3$ 满足 $S_v \neq \varnothing$。
- 对于 $d=16$，有 $v=1,4$ 满足 $S_v \neq \varnothing$。
- 对于 $d=19$，有 $v=1,4$ 满足 $S_v \neq \varnothing$。

#### 数据范围

- 对于 $30\%$ 的数据，$t=1$，$1 \le d \le 70$。
- 对于 $60\%$ 的数据，$t=1$。
- 对于 $100\%$ 的数据，$1 \le t \le 4 \times 10^3$，$1 \le d \le 2 \times 10^6$。

-----
Source：[JROI-2 Summer Fun Round](https://www.luogu.com.cn/contest/30241) - T4

Idea&Sol&Std&Data：[VinstaG173](/user/59388)

Retest：None


title: 「Wdoi-6」另一侧的月

background:
[![](https://cdn.luogu.com.cn/upload/image_hosting/ikxrpn7c.png)](https://thwiki.cc/%E5%A4%A7%E7%A9%BA%E9%AD%94%E6%9C%AF_%EF%BD%9E_Magical_Astronomy.)

「人类的梦想之一，月面旅行对一般人也终于成为可能！」
「从下个月起日本各个旅行公司将开始展开旅行」

然而，月球的表面，有着将月之都与荒凉的无生命星球隔开的一道结界。只要这道结界存在，人们只能看到石头罢了。

而月面旅行的费用，也绝不是身为大学生的莲子与梅莉二人所能承担的。但是，她们想要探寻的是，被结界所包裹的，有着高度发达文明的月之都。

这，便是另一侧的月。梅莉她看见了。兔子在捣药，身着华美的服装，优雅地在天空中起舞的天女。

「我说莲子啊。如果月面旅行太贵实在不行的话，我们要不要试着想点别的办法去月球呢？」

description:
### 简要题意

给定 $n$ 个节点的树（保证 $n\ge 2$），Hifuu 和 Luna 交替操作，前者先手。每回合操作者选择一个节点，将「该节点」和「所有与该节点相连的边」删除，形成若干个连通块，操作者再从中保留一个连通块。如果该回合结束后只剩下一个节点，则该回合的操作者失败，另一个人胜利。问谁存在必胜策略。

-----
### 原始题意

但是，月之都是有结界保护的，也就是说莲子与梅莉若是想要用一些方式完成月球旅行，势必要突破这层结界。

月之都的结界是由 $n$ 个节点，$n-1$ 条灵能输送渠道构成的连通的结构，其中节点编号为 $1 \sim n$。结界有一个中枢控制系统，以提防外界的人闯入结界，抵达月之都。莲子和梅莉便需要与这个控制系统进行一些交互，才能进入月之都。

具体而言，莲子梅莉，和中枢控制系统是交替进行操作的，其中莲子梅莉是**先手**。操作方可以任意选择结界上的一个节点，将连向这个节点的**所有**灵能输送渠道全部断绝，同时废弃这个节点。这也就意味着，这会把结界分为若干**组**节点，每一组节点之间没有灵能输送渠道，而组内的节点由灵能输送渠道相连。在这些节点组中，操作者可以任意保留**一组**节点，将另外所有节点**全部废弃**，即，之后再也无法操作这些被废弃的节点了。

在这样的规则之下，若操作结束后，最后只剩下一个节点，那么操作者失败，另一个人取得胜利。现在莲子和梅莉希望知道，在这样的规则之下，她们是否存在一种必定能够抵达月之都的策略？

inputFormat:
本题多组数据。第一行输入一个正整数 $T$，表示数据组数。对于每一组数据：

- 第一行有一个正整数 $n$。
- 接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$。表示一条连接节点 $u_i$ 和 $v_i$ 的双向的灵能输送渠道。

outputFormat: 对于每一组数据，输出莲子和梅莉是否能够到达月之都。具体而言，若她们存在必定能到达月之都的策略，则输出 $\texttt{Hifuu}$，否则输出 $\texttt{Luna}$。

hint:
### 样例解释

#### 样例 \#1

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

图 $1$ 是结界。图 $2$、图 $3$ 展示了一种莲子和梅莉可能的一种必胜策略：选择节点 $2$，然后保留 $\{1,3\}$ 所处的连通块，那么中枢控制系统无论是选择节点 $1$ 还是 $3$ 都必输。

#### 样例 \#2

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

---

### 数据范围

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

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \textbf{\textsf{特殊性质}} & \textbf{Subtask \textsf{依赖}}\cr\hline
1 & 15 & 8 & - & - \cr\hline
2 & 20 & 10^5 & \mathbf{A} & -\cr\hline
3 & 20 & 10^5 & \mathbf{B} & - \cr\hline
4 & 15 & 10^3 & - & 1 \cr\hline
5 & 30 & 10^5 & - & 2,3,4 \cr\hline
\end{array}
$$

- 特殊性质 $\mathbf{A}$：保证存在一个点度数为 $n-1$。
- 特殊性质 $\mathbf{B}$：保证 $n=2^k-1,k \in \N^*$。且树的形态是完全二叉树。

对于 $100\%$ 的数据：$1 \leq T \leq 5$，$2 \le n \le 10^5$，输入数据构成一棵树。


title: 「Stoi2033」世界未末日 加强版

background:
注意：**利用提交反馈以套取数据的行为属于作弊**。

> 就算是世界要崩溃
> 亲爱的我也绝不会落泪
> 不放弃爱过的那种感觉
> 珍惜着有你记忆的一切
> 就算是世界要倾斜
> 亲爱的我也绝不说离别
> 尽管末日威胁再强烈
> 有爱就不累
> ——《世界未末日》

description:
Vinsta 和 Stella 有 $n$ 堆石子，第 $i$ 堆有 $s_i$ 个。

她们约定从 Vinsta 开始轮流操作，每次操作可以选择不少于 $1$ 堆且不超过 $k$ 堆的石子。对于第 $i$ 堆石子，可以选取两个实数 $a,b$ 满足：

- $a \times b=s_i$
- $a+b=c,c\in[1,s_i]\cap\Z$

并丢掉第 $i$ 堆的 $c$ 个石子，即 $s_i\leftarrow s_i-c$。不能操作者败，她们想要知道 Vinsta 是否有必胜策略。

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

接下来 $T$ 组数据，每组数据第一行共三个正整数： $n,k,S$，其中 $S=\max\{s_i\}$。

第二行共 $n$ 个正整数： $s_i$，表示初始时第 $i$ 堆的石子个数。

outputFormat: 对于每组数据输出一行。有必胜策略输出 `YES`，否则输出 `NO`。


title: 「PMOI-4」生成树

background:
> 题目正解不会很难，反正很难的也必不会做，所以宁愿相信题目都是善良的。

——command_block 《考前小贴士》

djy 出了一道生成树的题，然后发现做法假了，就把这个题改了一下，作为这场比赛的 B。

description:
给定 $n$ 个数，第 $i$ 个数的原始权值是 $w_i$，你要按照某种顺序将这些数依次选择。

若当前是第 $i$ 次选数，选择的**原始权值**为 $k$，则其他所有**未被选过**的数的权值均加上 $(-1)^{i+k+1} \times k$。

你需要求出一种选数方案，使得选出的 $n$ 个数**最终**的**权值**和**最大**。

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

第二行 $n$ 个整数 $w_i$，表示第 $i$ 个数的权值。

outputFormat: 一行一个整数，表示最大权值和。

hint:
【样例解释】

依次选择**编号**为 $\{7,6,5,3,4,1,2\}$ 的数即可。

【数据范围】

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

- Subtask 1（20pts）：$n \le 7$。
- Subtask 2（30pts）：$n \le  10^3$。
- Subtask 3（30pts）：保证所有的 $w_i \ge 0$ 或所有的 $w_i \le 0$。
- Subtask 4（20pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1 \le n \le 10^5,-10^9 \le w \le 10^9$。


title: 入门测试题目

type: B

description: 求两个整数的和。

inputFormat: 一行，两个用空格隔开的整数。

outputFormat: 两个整数的和。


title: Hello,World!

description:
编写一个能够输出 `Hello,World!` 的程序。

提示：
- 使用英文标点符号；
- `Hello,World!` 逗号后面**没有**空格。
- `H` 和 `W` 为**大写**字母。

samples: 无 Hello,World!


title: 输出第二个整数

description: 输入三个整数，整数之间由一个空格分隔。把第二个输入的整数输出。

inputFormat: 只有一行，共三个整数，整数之间由一个空格分隔。

outputFormat: 只有一行，一个整数，即输入的第二个整数。


title: 对齐输出

description: 读入三个整数，按每个整数占 $8$ 个字符的宽度，右对齐输出它们，按照格式要求依次输出三个整数，之间以一个空格分开。

inputFormat: 只有一行，包含三个整数 $a,b,c$。整数之间以一个空格分开。

outputFormat: 只有一行，按照格式要求依次输出三个整数，之间以一个空格分开。


title: 字符三角形

description: 给定一个字符，用它构造一个底边长 $5$ 个字符，高 $3$ 个字符的等腰字符三角形。

inputFormat: 输入只有一行，包含一个字符。

outputFormat: 该字符构成的等腰三角形，底边长 $5$ 个字符，高 $3$ 个字符。

hint: 对于 $100 \%$ 的数据，输入的字符是 ASCII 中的可见字符。


title: 地球人口承载力估计

description:
假设地球上的新生资源按恒定速度增长。照此测算，地球上现有资源加上新生资源可供 $x$ 亿人生活 $a$ 年，或供 $y$ 亿人生活 $b$ 年。

为了能够实现可持续发展，避免资源枯竭，地球最多能够养活多少亿人？

inputFormat: 一行，包括四个正整数 $x, a, y, b$，两个整数之间用单个空格隔开。

outputFormat: 一个实数 $z$，表示地球最多养活 $z$ 亿人，舍入到小数点后两位。


title: A + B 问题

description:
在大部分的在线题库中，都会将 A + B 问题作为第一题，以帮助新手熟悉平台的使用方法。

A + B 问题的题目描述如下：给定两个整数 $A$ 和 $B$，输出 $A + B$ 的值。保证 $A, B$ 及结果均在 $32$ 位整型范围内。

现在请你解决这一问题。

inputFormat: 一行，包含两个整数 $A, B$，中间用单个空格隔开。$A$ 和 $B$ 均在 $32$ 位整型范围内。

outputFormat: 一个整数，即 $A + B$ 的值。保证结果在 $32$ 位整型范围内。保证答案非负。

hint: 对于 $100 \%$ 的数据，$A, B, A + B$ 均在 $32$ 位整型范围内，且 $A + B \ge 0$。


title: 计算 (a+b)×c 的值

description: 给定 $3$ 个整数 $a,b,c$，计算表达式 $(a+b) \times c$ 的值。

inputFormat: 输入仅一行，包括三个整数 $a,b,c$，数与数之间以一个空格分开。

outputFormat: 输出一行，即表达式的值。


title: 计算 (a+b)/c 的值

description: 给定 $3$ 个整数 $a,b,c$，计算表达式 $(a+b)/c$ 的值，`/` 是整除运算。

inputFormat: 输入仅一行，包括三个整数 $a,b,c$，数与数之间以一个空格分开。

outputFormat: 输出一行，即表达式的值。


title: 带余除法

description: 给定被除数和除数，求整数商及余数。此题中请使用默认的整除和取余运算，无需对结果进行任何特殊处理。

inputFormat: 一行，包含两个整数，依次为被除数和除数（除数非零），中间用一个空格隔开。

outputFormat: 一行，包含两个整数，依次为整数商和余数，中间用一个空格隔开。


title: 计算分数的浮点数值

description: 两个整数 $a$ 和 $b$ 分别作为分子和分母，即分数 $\dfrac{a}{b}$，求它的浮点数值（双精度浮点数，保留小数点后 $9$ 位）。

inputFormat: 输入仅一行，包括两个整数 $a$ 和 $b$。

outputFormat: 输出也仅一行，分数 $\dfrac{a}{b}$ 的浮点数值（双精度浮点数，保留小数点后 $9$ 位）。


title: 甲流疫情死亡率

description: 甲流并不可怕，在中国，它的死亡率并不是很高。请根据截止 $2009$ 年 $12$ 月 $22$ 日各省报告的甲流确诊数 $a$ 和死亡数 $b$，计算甲流在各省的死亡率。

inputFormat: 输入共两行，第一行一个整数为确诊数 $a$，第二行一个整数为死亡数 $b$。

outputFormat: 输出仅一行，甲流死亡率，以百分数形式输出，精确到小数点后 $3$ 位。

hint:
### 数据规模与约定

对于全部的测试点，保证 $1 \leq a, b \leq 10^4$。

### 提示

在 C 风格输入输出中，百分号 `%` 可以这样输出：`printf("%%");`。


title: 温度表达转化

description: 利用公式 $C=5 \times (F - 32)/9$ ( 其中 $C$ 表示摄氏温度，$F$ 表示华氏温度）进行计算转化，输入华氏温度 $F$，输出摄氏温度 $C$，要求精确到小数点后 $5$ 位。

inputFormat: 输入一行，包含一个实数 $F$，表示华氏温度。（$F \ge - 459.67$）

outputFormat: 输出一行，包含一个实数，表示对应的摄氏温度，要求精确到小数点后 $5$ 位。


title: [COCI2011-2012#1] JABUKE

description:
Mirko 最近迷上了一款电子游戏。

这款游戏的屏幕被分成 $N$ 列。在屏幕的底部，有一艘 $M$ 列宽的船。游戏中，玩家可以将这艘船左右移动，但船必须**时刻保持完全在屏幕内**。初始时船占据屏幕最左边的 $M$ 列。

有苹果会从屏幕顶部掉落。每个苹果都从顶部的 $N$ 列的其中一列开始以直线掉落。当当前的苹果掉落到屏幕底部时，下一个苹果开始掉落。

如果当一个苹果掉落到底部时，船覆盖了苹果所在的列，那么我们说**这个苹果是被捡起的**。你的任务是在捡起所有苹果的前提下，最小化船移动的距离。

inputFormat:
第一行包含两个以空格分隔的整数 $N,M$。

第二行包含一个整数 $J$，表示将要掉落的苹果的个数。

接下来 $J$ 行的第 $i$ 行包含一个整数，表示第 $i$ 个苹果将要从哪一列开始掉落。

outputFormat: 输出一行一个整数，表示最小的船移动的距离。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，$1 \le M < N \le 10$，$1 \le J \le 20$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $50$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T1 JABUKE___。


title: 「EZEC-9」进位

background: 规定 $\text{popcount}(x)$ 表示 $x$ 在二进制表示下所含 $1$ 的个数。

description:
您有一个二进制数 $B$（以一个长为 $n$ 的 $01$ 字符串形式给出）和长为 $m$ 的序列 $a$。

同时，您还需要对 $B$ 进行 $m$ 次操作。

其中，第 $i$ 个操作为 $B \gets B + 2^{a_i}$，其价值 $v_i$ 为 $B$ 在操作前后变化的位置数量，即 $v_i = \operatorname{popcount}(B \mathbin{\mathrm{xor}} (B + 2^{a_i}))$。

您需要解决两个问题：

- 您可以**任意**安排操作顺序，问在执行**所有**操作后，$\displaystyle \sum_{i=1}^mv_i$ 最大为多少？

- 您可以**任意**安排操作顺序，问在执行**所有**操作后，$\displaystyle \max_{i=1}^mv_i$ 最大为多少？

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

第二行一个长为 $n$ 的 $01$ 字符串，表示二进制数 $B$，**从低位到高位依次给出**。

第三行 $m$ 个整数 $a_1,a_2,\dots,a_m$。

outputFormat:
第一行一个整数，表示第一问的答案。

第二行一个整数，表示第二问的答案。

**本题使用 Special Judge，若您的第一问答案正确，可以获得该测试点 $30\%$ 的分数，若您的第二问答案正确，可以获得该测试点另外 $70\%$ 的分数。**

**若您只回答了两问中的一问，请在另一个位置输出一个非负整数。**

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

对于第一问，依次执行第 $1,2,6,5,4,3$ 个操作可得到 $\displaystyle \sum\limits_{i=1}^mv_i=14$。

对于第二问，依次执行第 $6,5,4,3,1,2$ 个操作可得到 $\displaystyle \max\limits_{i=1}^mv_i=6$。

[详细过程](https://www.luogu.com.cn/paste/ycx4xov7)

**【数据范围】**

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

- Subtask 1（20 points）：$n,m\leq 10$。
- Subtask 2（30 points）：$n,m\leq 1000$。
- Subtask 3（20 points）：$B$ 中全为 $0$，且 $a_1=0$，$\forall i>1, a_{i-1}\leq a_i\leq a_{i-1}+1$。
- Subtask 4（20 points）：$n,m\leq 10^5$。
- Subtask 5（10 points）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$，$0\leq a_i< n$。


title: [COCI2014-2015#5] FUNGHI

description:
Hansel 和 Gretel 得到了一块分成 $8$ 片的披萨，每片上面有不同数量的蘑菇，表示为 $S_1,S_2,...,S_8$。Gretel 很喜欢蘑菇，她想要找到连续的四片披萨使得上面的蘑菇最多。

请注意，因为披萨是一个圆，因此编号为 $1$ 的披萨片与编号为 $8$ 的披萨片是相邻的。

inputFormat: 一共 $8$ 行，每行一个正整数 $S_i$（$i$ 为行数），表示披萨片上的蘑菇数。

outputFormat: 一行一个正整数，表示连续的四片披萨上最多有几个蘑菇。

hint:
对于 $100\%$ 的数据，$0 \leq S_i \leq 50$。

译自 [COCI 2014/2015 CONTEST #5](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)。


title: [COCI2014-2015#5] ZMIJA

background: Mirko 在玩魔改的贪吃蛇。

description:
给你一个 $n\times m$ 的矩阵，其中：

- 蛇在左下角，用 `Z` 表示；
- 其他格子苹果用 `J` 表示，空白用 `.` 表示；
- 操作 A 让蛇向它面对的方向走一步（不能走出矩阵）；
- 操作 B 让蛇向上走一步，并且方向转 $180\degree$；
- 当蛇所在格子有苹果时，蛇会把这个苹果吃掉。

现在蛇面向右，求最少操作数使蛇吃掉所有苹果。

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

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只含 `.`, `J`, `Z` ，表示该矩阵。

outputFormat: 一个正整数，表示蛇吃掉所有苹果的最少操作数。

hint:
对于 $100\%$ 的数据，$2 \leq n,m \leq 1000$，矩阵的左下角一定是 `Z`。

**样例 1 解释：** 依次执行操作 $BBAAABB$ 可吃掉所有苹果。

译自 [COCI 2014/2015 CONTEST #5](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)。


title: [COCI2014-2015#5] TRAKTOR

background: Mirko 用拖拉机采蘑菇。

description: 已知一个平面上 $n$ 个点，每个点的坐标可以用正整数 $X_i,Y_i$ 表示，求最小的 $ans$ 使前 $ans$ 个点中有至少 $k$ 个点处于同一行或同一列或同一与对角线平行的斜线。

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

接下来 $n$ 行，每行两个正整数 $X_i,Y_i$。

outputFormat: 一个正整数 $ans$。如无解输出 $-1$。

hint:
对于 $50\%$ 的数据，$1 \leq X_i,Y_i \leq 300$。

对于 $100\%$ 的数据，$2 \leq k \leq n \leq 10^6$，$1 \leq X_i,Y_i \leq 10^5$。

**样例 1 解释：**

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

译自 [COCI 2014/2015 CONTEST #5](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)


title: [COCI2014-2015#5] ZGODAN

description:
定义 Handsome 数：这个正整数中任意两个相邻的数位的奇偶性不同。

给你一个正整数 $n$，求与 $n$ 最近的 Handsome 数。如果有多个按从小到大的顺序输出。

inputFormat: 一个正整数 $n$。

outputFormat: 与 $n$ 最近的 Handsome 数。

hint:
对于 $100\%$ 的数据，$1 \leq n \leq 10^{1000}$。

译自 [COCI 2014/2015 CONTEST #5](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)。


title: [COCI2014-2015#5] JABUKE

description:
给你一个 $n \times m$ 的矩阵，其中苹果树用 `x` 表示，空地用 `.` 表示。

有 $g$ 年，每年都会从天而降一个苹果，落在坐标 $(x_i,y_i)$ 上，要求出**这个苹果离最近一棵苹果树的距离的平方**。当然，一年后这个苹果会长成新的一颗苹果树，并参与一年后落下的那个苹果的计算。

inputFormat:
第一行两个正整数 $n,m$，表示矩阵的长，宽。

接下来 $n$ 行，每行 $m$ 个字符，字符仅含 `x` 和 `.`，表示该矩阵。

接下来一个正整数 $g$，表示年份。

接下来 $g$ 行每行两个正整数 $x_i,y_i$，表示每年苹果下落的位置。

outputFormat: 一共 $g$ 行，每行一个整数，表示每个苹果下落时离最近一棵苹果树的距离的平方。

hint:
对于 $30\%$ 的数据，$1 \leq g \leq 500$。

对于 $100\%$ 的数据，$1\leq n,m \leq 500,1 \leq g \leq 10^5$，保证初始矩阵至少包含一棵苹果树。

距离计算公式：$d((x_1,y_1),(x_2,y_2))=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

译自 [COCI 2014/2015 CONTEST #5](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)。


title: [COCI2011-2012#1] MATRIX

description:
有一个 $N \times N$ 的矩阵，找出它的美丽值最大的子矩阵，要求这个子矩阵是正方形，即长和宽相等。

定义一个矩阵的**美丽值**为：将这个矩阵**主对角线**上的数的和定义为 $A$，另一条对角线上的数的和定义为 $B$，则这个矩阵的美丽值为 $A - B$。

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

接下来 $N$ 行每行包含 $N$ 个整数，表示这个矩阵。

outputFormat: 输出一行一个整数，表示最大的美丽值。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 400$，矩阵元素 $\in [-10^3,10^3]$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $80$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T2 MATRIX___。


title: [COCI2011-2012#1] X3

description: 给定一个长度为 $N$ 的序列 $A_1,A_2,...,A_N$，求序列元素两两异或的总和。

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

接下来 $N$ 行每行包含一个正整数 $A_i$。

outputFormat: 输出一行一个整数，表示两两异或后的总和。


title: [COCI2011-2012#1] PLES

description:
舞会上有 $N$ 个男孩和 $N$ 个女孩，我们知道他们的身高。规定每个人最多只能和一个舞伴跳舞。

每个男孩要么想和比他高的女孩跳舞，要么想和比他矮的女孩跳舞。类似地，每个女孩要么想和比她高的男孩跳舞，要么想和比她矮的男孩跳舞。没有同样高的男孩和女孩想和对方跳舞。

求如果遵照每个人的意愿，最大的舞伴对数是多少。

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

接下来 $N$ 行，每行包含一个整数 $A_i$。$A_i$ 的绝对值表示第 $i$ 个男孩的身高。如果 $A_i$ 为正数，表示第 $i$ 个男孩想和比他高的女孩跳舞；如果 $A_i$ 为负数，表示第 $i$ 个男孩想和比他矮的女孩跳舞。

接下来 $N$ 行，每行包含一个整数 $B_j$。$B_j$ 的绝对值表示第 $j$ 个女孩的身高。如果 $B_j$ 为正数，表示第 $j$ 个女孩想和比他高的男孩跳舞；如果 $B_j$ 为负数，表示第 $j$ 个女孩想和比他矮的男孩跳舞。

outputFormat: 输出一行一个整数，表示最大的舞伴对数。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1500 \le |A_i,B_j| \le 2500$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $110$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T4 PLES___。


title: CF1431J Zero-XOR Array

background: 这是一道来自 Kotlin Heroes 的题目。但是这里允许其他语言提交。

description:
You are given an array of integers $a$ of size $n$. This array is non-decreasing, i. e. $a_1\leq a_2\leq \ldots \leq a_n$.

You have to find arrays of integers $b$ of size $2n−1$, such that:

* $b_{2i−1}=a_i$ ($1\leq i\leq n$);

* array $b$ is non-decreasing;

* $b1\oplus b2\oplus \ldots \oplus b_{2n−1}=0$ ($\oplus$ denotes bitwise XOR operation: [https://en.wikipedia.org/wiki/Exclusive_or](https://en.wikipedia.org/wiki/Exclusive_or). In Kotlin, it is `xor` function).

Calculate the number of arrays that meet all the above conditions, modulo $998244353$.

inputFormat:
第一行两个整数 $n, m$，表示 $a_i, b_i < 2 ^ m$。

第二行 $n$ 个整数 $b_1, b_3,\ldots , b_{2n−1}$。

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

translation:
给定一个包含 $n$ 个整数的序列 $a$，其中第 $i$ 个整数为 $a_i$。这个序列满足单调不递减性质，即 $a_1 \le a_2 \le \ldots \le a_n$。

你需要找出所有包含 $2n-1$ 个整数的序列 $b$，使其满足以下条件：

* $b_{2i−1}=a_i$ ($1\leq i\leq n$)；

* $b$ 满足单调不递减性质；

* $b1\oplus b2\oplus \ldots \oplus b_{2n−1}=0$（$\oplus$ 表示按位异或运算。在 Kotlin 语言中，用函数 `xor` 表示）。

请计算出不同的序列 $b$ 的个数对 $998244353$ 取模的结果。


title: [Ynoi2078] 《A Path Towards Autonomous Machine Intelligence》阅读报告（更新中...）

description:
你需要支持 $m$ 次操作，第 $i$ 次操作给出 $L_i,R_i,a_i,b_i,l_i,r_i,X_i,x_i$,

相应的答案定义为：

$(\texttt{ans}_{i,0},\texttt{ans}_{i,1}):=F_{i,r_i}(F_{i,r_i-1}(\dots F_{i,l_i}(x_i,0)\dots))$，

其中

若 $L_j\le X_i\le R_j$ 则 $F_{i,j}(x,y)=((a_jx+b_j)\bmod 2677114440,\max(b_j,y))$，

其余情况 $F_{i,j}(x,y)=(x,y)$。

你需要输出 $\texttt{ans}_{i,0}$ 与 $\texttt{ans}_{i,1}$ 的异或和。

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

接下来 $m$ 行，第 $i$ 行为 $L_i,R_i,a_i,b_i,l_i,r_i,X_i,x_i$ 表示第 $i$ 次操作。

本题强制在线，对 $2\le i\le m$，第 $i$ 次操作的输入的每个数需要与第 $i-1$次操作的答案异或。

outputFormat: 共 $m$ 行，每行一个整数，表示每个操作的答案。


title: String Rearrangement in Phantom

description: 有一字符串 $S$，每次询问两串 $S[l_1,r_1]$，$S[l_2,r_2]$，问有多少划分方式使得 $S[l_1,r_1]=A+B+C$，$C+B^R+A=S[l_2,r_2]$。其中 $B^R$ 表示 $B$ 串的翻转，$+$ 表示字符串的拼接，$S[l,r]$ 表示提取串 $S$ 的第 $l$ 到第 $r$ 个字符。$A,B,C$ 可以为空。

inputFormat:
第一行两个正整数 $n$ 和 $m$ 表示 $S$ 的长度和询问数。

第二行一个长度为 $n$ 的小写字母组成的字符串表示 $S$。

接下来 $m$ 行，每行四个正整数 $l_1,r_1,l_2,r_2$ 表示询问区间，保证 $r_1-l_1=r_2-l_2$。

outputFormat: $m$ 行，每行一个正整数表示答案。


title: [BalticOI 1996 Day 1] A SQUARE AND A CIRCLE

description: 一个平面上有一个正方形和一个圆，给定正方形的两个相对顶点的坐标和圆的圆心坐标和半径，求这个正方形和这个圆的公共面积。

inputFormat: 前两行包含正方形的两个相对顶点的坐标 （$x_1,y_1$）和（$x_2,y_2$），第三行包含圆心坐标（$x_3,y_3$）和半径 $r$，为实数。

outputFormat: 输出两个图形的公共面积，小数点后两位。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$-1200.00 \le x_i,y_i \le 1200.00$，$0 < r \le 200.00$。
#### 分值说明
本题分值按 BOI 原题设置，**满分** $30$ 。
#### 题目说明
来源于 Baltic Olympiad in Informatics 1996 的 [Day 1:A SQUARE AND A CIRCLE](https://boi.cses.fi/files/boi1996_day1.pdf) 。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [JOI Open 2021] Crossing

background: # 警告：滥用本题评测将被封号！

description:
你的资源库里有 $3$ 个长度为 $N$ 的只由 `J`，`O`，`I` 组成的序列 $S_A,S_B,S_C$，你可以进行 C 操作（全名为 Croos 操作，简写为 C 操作），每一次 C 操作你可以在资源库里选择两个字符串 $C_1,C_2$，C 操作后产生的字符串为 $C_3$，则对于任意 $i \in [1,N]$，设这三个字符串第 $i$ 个位置上的字符分别为 $c_1,c_2,c_3$，有：

|$c_1$|$c_2$|$c_3$|
|:-:|:-:|:-:|
|J|J|J|
|J|O|I|
|J|I|O|
|O|J|I|
|O|O|O|
|O|I|J|
|I|J|O|
|I|O|J|
|I|I|I|

上面这个表格的意思是 $c_1,c_2$ 为对应字符时，$c_3$ 也应该是对应的字符。

进行 C 操作后将会把产生的字符串放入资源库。

你被给定了一个长度为 $N$ 的只由 `J`，`O`，`I` 组成的字符串 $T_0$，和 $Q$ 个整数 $L_j,R_j$ 和 $Q$ 个字符 $C_j$，由这些形成 $Q$ 个长度为 $N$ 的字符串 $T_j$，规则为：

> $T_j$ 是由 $T_{j-1}$ 的第 $L_j$ 个字符到第 $R_j$ 个字符都替换成 $C_j$ 得到的。

求对于每一个字符串（包括 $T_0$），是否能由给定的资源库进行一次或多次 C 操作得来。如果该字符串与资源库的其中一个字符串一模一样，也可以称“进行 C 操作得来”，详细内容请看样例 1 的 $T_2$。

第 $j$ 个字符串进行 C 操作时放入资源库的字符串将会在对第 $j+1$ 个字符串判断时清空。

inputFormat:
第一行一个整数 $N$ 代表字符串的长度。

接下来 $3$ 行 $S_A,S_B,S_C$ 代表给定的资源库里的字符串。

第五行一个整数 $Q$ 代表给定的字符串个数。

第六行一个字符串 $T_0$，意义如题面所述。

接下来 $Q$ 行每行两个整数和一个字符 $L_j,R_j,C_j$，意义如题面所述。

outputFormat: $Q+1$ 行每行一个字符串 `Yes` 或 `No`，第 $j$ 行代表第 $T_{j-1}$ 个字符串是否可以由初始资源库得来。

samples:
4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I

hint:
#### 样例 1 解释

- $T_0$ 可以由 `JJOI` 和 `OJOO` 经过 C 操作而来；
- $T_1$ 为 `OOOO`，无法从资源库经过 C 操作而来；
- $T_2$ 为 `OJOO`，资源库中有 `OJOO`，故可以；
- $T_3$ 为 `OIII`：
	1. 由 `JJOI` 和 `OJOO` 经过 C 操作产生 `IJOJ`；
    2. 由 `JOJO` 和 `IJOJ` 经过 C 操作产生 `OIII`。

#### 样例 2 解释

- $T_0$ 无法从资源库经过 C 操作而来；
- $T_1$ 为 `OOI`，无法从资源库经过 C 操作而来；
- $T_2$ 为 `JOI`，资源库中有 `JOI`，故可以。

#### 数据规模与约定

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

- Subtask 1（3 pts）：$S_A=S_B=S_C$，$N \le 100$；
- Subtask 2（23 pts）：$S_A=S_B=S_C$；
- Subtask 3（23 pts）：$N \le 100$；
- Subtask 4（51 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $1 \le N \le 2 \times 10^5$；
- $S_A,S_B,S_C$ 是只包含 `J`，`O`，`I` 的长度为 $N$ 的字符串；
- $1 \le Q \le 2 \times 10^5$；
- $T_0$ 是只包含 `J`，`O`，`I` 的长度为 $N$ 的字符串；
- $1 \le L_j \le R_j \le N$；
- $C_j \in  \{$`J`，`O`，`I`$\}$。

#### 说明

翻译自 [JOI 2020 / 2021 Open Contest A Crossing](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2021/crossing/2021-open-crossing-statement-en.pdf)。


title: [BalticOI 1996 Day 1] A NICE SEQUENCE

description:
有一个由 $N$ 个整数组成的序列 $a_1,a_2, \cdots ,a_N$。序列 $b_1,b_2, \cdots ,b_L$ 是给定序列的子序列，如果
1. 对于每个 $i$ （$1 \leq i \leq L$），存在这样的 $j$ （$1 \leq j \leq N$），使得 $b_i= a_j$；
1. 对于每个 $i_1$ 和 $i_2$ 使得 $i_1 < i_2$，$b_{i1} = a_{j1}$，$b_{i2} = a_{j2}$，关系 $j_1 < j_2$ 是有效的。

序列 $b_1,b_2, \cdots,b_L$ 是非递增的，如果对于每个 $i$（$1 \le i < L$），$b_i \le b_{i+1}$。
序列 $b_1,b_2, \cdots,b_L$ 是非递减的，如果对于每个 $i$（$1 \le i < L$），$b_i \le b_{i+1}$。
给定的序列称为 **NICE**，如果我们可以选择该序列的 $K$ 个子序列使得：
1. 每个子序列至少有 $2$ 个成员，
1. 每个子序列要么不增加要么不减少，
1. 给定序列的每个成员直接属于一个子序列。

找出给定序列的最小可能 $K$。

inputFormat: 第一行包含一个整数为 $N$ 的值，接下来的 $N$ 行包含序列成员的值（每行一个整数，对于每个 $j$（$1 \le a_j \le 100$））。

outputFormat:
输出数据必须包含：
1. 第一行中 $K$ 的值，
1. 将给定序列划分为 $K$ 个子序列的一个示例（即必须有 $N$ 行，每行包含子序列的 $a_j$ 和其 $a_j$ 属于的 索引（$1 \le$ 索引 $\le K$））。

如果给定的序列不是 **NICE**，则输出文件的第一行必须仅包含 $0$。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \le N \le 25$，$0 < K \le N$。
#### 样例说明
样例一中，子序列是 $12，33，33$ 和  $97，18，15$。
#### 分值说明
本题分值按 BOI 原题设置，**满分** $40$ 。
#### 题目说明
来源于 Baltic Olympiad in Informatics 2000] 的 [Day 1:A NICE SEQUENCE](https://boi.cses.fi/files/boi1996_day1.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [BalticOI 1996 Day 1] LOGICAL EXPRESSIONS

description:
有五个逻辑表达式，称为 R1、R2、R3、R4、R5。只有逻辑变量 $a、b、c、d、e、f、g、h$，逻辑运算
`#（not）`
`&（and）`
`+（or）`
和圆括号可以在表达式中使用。操作的优先级如上所述。可以使用圆括号定义执行操作的不同顺序。
操作由这样的表定义
![Biao](https://cdn.luogu.com.cn/upload/image_hosting/ilfi8gbz.png)
假设有一些表达式可以通过带有一个或两个参数的单个逻辑运算来表达：
- $R_i = R_j$（$R_i$ 等价于 $R_j$，即对于每组变量值，$R_i$ 给出与 $R_j$ 相同的值）；
- $R_i =$ # $R_j$（$R_i$ 等价于 $R_j$ 的否定）；
- $R_i = R_j $ &  $R_k  $（结合）;
- $R_i = R_j + R_k$（分离）；其中（$i≠k，i≠j$）。

一组基本的表达式是通过它可以表示（表达）未包含在该组中的任何其他表达式，如上定义。
编写一个程序来查找：
1. 任何最不基本的表达式集；
1. 每个表达式的任何表示（表达）（不属于表达式的基本集合）。应该使用带有一个或两个参数的任何单个逻辑运算来获得表示，即来自基本集合的表达式。

inputFormat: 一行一个表达式，R1 在第一行,以此类推。表达式中没有空格。假设输入数据是正确的。每行的长度小于 $256$。

outputFormat: 应包含 $5$ 行，每个表达式一行。将基本表达式的名称写入输出的第一行。其余行应包含所有其他表达式（即不属于基本表达式集的表达式）的等式（等价）形式的表示（表达式），如下面的示例所示。

hint:
#### 分值说明
本题分值按 BOI 原题设置，**满分** $30$ 。
#### 题目说明
来源于 Baltic Olympiad in Informatics 1996 的 [Day 1:LOGICAL EXPRESSIONS](https://boi.cses.fi/files/boi1996_day1.pdf) 。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [BalticOI 1996 Day 2] THE FILLING OF BARRELS

description:
在水平面上有 $N$ 个相等的空桶。每桶容积为 $100$ 个单位。它们中的每两个都用一根管道连接。每根管道都连接到两个桶的底部，其有自己的阀门，只能“打开“ ”或“关闭”。开始时，所有阀门都是关闭的。如果一个阀门打开，那么从一个连接的桶中的液体可以快速自由地流向另一个桶，从而使这些桶中的液体量变得相等（连通器原理）。如果阀门关闭，则液体无法通过该管道。
现允许两种操作：
1. “P”（倾倒）一定量的液体倒入规定的桶中。操作说明为：“P $n$ $m$”，其中 $n$ 为桶的编号，$m$ 为要倒入该桶的液体量（单位），
1. “V”（用于阀门）一个规定的阀门转到相反位置（即该阀门原打开现关闭，如果原关闭则现打开）。操作说明为：“V $n_1$ $n_2$”，其中 $n_1$ 和 $n_2$ 为连接有该阀门的管道的桶编号。两种不同的描述 “V $n_1$ $n_2$” 和 “V $n_2$ $n_1$” 指的是同一个阀门。

您的目标是执行给定的操作序列。您必须忽略管道中的液体量。如果某些倾倒操作因液体溢出而无法执行，则必须在适当输出后停止执行该操作序列。

inputFormat: 第一行包含整数 $N$ 和 $K$（操作数），其余 $K$ 行包含操作描述（每行一个描述）。

outputFormat: 必须包含 “OK” 以及序列执行结束时所有桶中的最小和最大液体量的值或 “OVERFLOW” 和发生溢出的操作。液体量的数值必须写成实数，小数点后有两位。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 < N \le 100$。$n$ 和 $m$ 为整数，$0 < n \le N$， $0 < m \le 1000$。$n_1$ 和 $n_2$ 为整数，$0 < n_1 \le N$，$0 < n_2 \le N$，$n_1 ≠ n_2$。 $0 < K \le 1000$。
#### 分值说明
本题分值按 BOI 原题设置，**满分** $25$ 。
#### 题目说明

来源于 Baltic Olympiad in Informatics 1996 的 [Day 2:THE FILLING OF BARRELS](https://boi.cses.fi/files/boi1996_day2.pdf) 。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [COCI2011-2012#1] SORT

description:
考虑如下的排序算法：

```
reverse-sort(sequence a)
    while (a is not in nondecreasing order)
        partition a into the minimum number of slopes
        for every slope with length greater than one
            reverse(slope)
```

定义 `slope` 为 `a` 的递减子串，`reverse()` 将翻转一段序列。

给定一个 $1$ ~ $N$ 的排列，保证在第一次划分时每个 `slope` 的长度都为偶数，求如果使用这种排序算法对给定的排列进行排序，需要调用多少次 `reverse(slope)`。

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

第二行包含 $N$ 个互不相同的的正整数，代表待排序的排列。

outputFormat: 输出一行一个整数，表示 `reverse(slope)` 需要被调用的次数。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，$2 \le N \le 10^5$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $140$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T5 SORT___。


title: [COCI2011-2012#1] SKAKAC

description:
Mirko 和 Slavko 正在玩一个游戏。

Mirko 把一个骑士棋子放在一个 $N \times N$ 的棋盘上，蒙住 Slavko 的眼睛，接下来将骑士移动 $T$ 步，每秒走一步。之后，Slavko 必须猜出骑士的最终位置才能获胜。

这个游戏中的棋盘是特别的，因为每个格子都有一部分时间被禁止通行。更准确地说，每个格子上都有一个为正整数的标记，标有数字 $K$ 的正方形只有在第 $0,K,K \times 2,K \times 3,...$ 秒内才是允许通行的，在其他时间这个格子都禁止通行。当然，骑士只能在某个格子允许通行时走到该格子。

游戏从第 $0$ 秒开始。每秒钟 Mirko 必须将骑士移动一步（根据国际象棋的规则，骑士走日字，类似中国象棋中的马）。请帮助 Slavko 写一个程序来计算出所有 $T$ 秒过后骑士可能位于的格子。

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

第二行包含两个正整数 $X,Y$，代表骑士的初始坐标。

接下来 $N$ 行，每行包含 $N$ 个不超过 $10^9$ 的正整数，描述这个棋盘。

outputFormat:
输出的第一行为一个非负整数 $M$，表示 $T$ 秒过后骑士可能位于的格子的数量。

接下来 $M$ 行，每行包含一个坐标，表示 $T$ 秒过后骑士可能位于的格子。输出的坐标按行数升序排序，如果行数相同按列数升序排序。

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

棋盘的状态如下图所示。`.` 代表允许通行的格子，`#` 代表禁止通行的格子，`K` 代表骑士可能位于的格子。

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

#### 【数据范围】

对于 $40\%$ 的数据，$T \le 5 \times 10^4$。

对于 $100\%$ 的数据，$3 \le N \le 30$，$1 \le T \le 10^6$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $160$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T6 SKAKAC___。


title: [BalticOI 1996 Day 2] A FAST JOURNEY

description:
一侧的交通道路连接了许多城市。城市从 $1$ 到 $n$ 编号，其中 $n$ 是城市的数量。在奇数天，车辆按照交通指示的方向行驶，在偶数天，则沿相反的方向行驶。两个城市之间的道路长度用一个整数值来衡量——从一个城市到另一个城市的旅程的持续时间（以小时为单位），它与方向无关。

编写一个程序来查找从城市 A 到城市 B 的路线，以便尽可能快地到达城市 B。

旅程的第一天是奇数天。一天之内的旅程不能超过十二个小时。晚上必须在一个城市度过。行程可能会在第二天继续。

inputFormat: 第一行包含两个整数为 A 和 B 城市的编号，第二行包含两个整数为城市总数和道路总数 $k$。剩下的 $k$ 行中有每条道路的信息，每行包含三个整数——道路连接的两个城市的编号以及以小时表示的城市之间旅程的持续时间。道路的方向是从第一城到第二城。

outputFormat: 每条中间路径输出一行。每行应该有四个整数——出发城市标号、到达城市编号、日期和道路长度。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 < n \le 100$，$1 \le k \le 1000$。
#### 样例说明
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/onmlfj8f.png)
#### 分值说明
本题分值按 BOI 原题设置，**满分** $35$ 。
#### 题目说明
来源于 Baltic Olympiad in Informatics 1996 的 [Day 2:A FAST JOURNEY](https://boi.cses.fi/files/boi1996_day2.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [COCI2010-2011#5] GLJIVE

description:
在超级马里奥面前有 $10$ 个蘑菇，排成一排。每挑选一个蘑菇就奖励一些分数。

超级马里奥必须按蘑菇出现的顺序挑选蘑菇，但并不是要求把他们都采集出来——他的目标是得分尽可能接近 $100$。**采集的蘑菇必须从第一个开始且是连续的**。

如果存在两个同样接近 $100$ 的数字（例如 $98$ 和 $102$），马里奥会选择较大的那个（这里是 $102$）。

帮助超级马里奥，告诉他他能得到多少分。

inputFormat: 输入共 $10$ 行，每一行包含一个正整数 $A_i$，表示挑选当前蘑菇所获得的分数，按照马里奥挑选蘑菇的顺序排列。

outputFormat: 输出共 $1$ 行，一个整数，表示马里奥能得到的分数。

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

马里奥选择第 $10$ 个蘑菇，得到 $100$ 分。

**【数据范围】**

对于 $100\%$ 的数据，$1\le A_i\le 100$。

**【说明】**

本题分值按 COCI 原题设置，满分 $30$。

题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #5](https://hsin.hr/coci/archive/2010_2011/contest5_tasks.pdf)  _**T1 GLJIVE**_。


title: [BalticOI 1996 Day 2] A NUMBER GAME

description:
下面是一个游戏。首先我们赋给变量 $n$ 和变量 $m$ 整数值。玩家 A 和 B 开始轮流移动（A 先）。每次移动都会选择一个正整数 $k \le \min \lbrace m,n \rbrace$，这会将变量 $n$ 的值减少 $k$。但是，不允许使用一个或另一个玩家在之前的移动中已经使用的数字。当其中一名玩家无法移动时，游戏结束。 走最后一步的玩家是赢家。
请编写一个程序，说明哪个玩家有获胜策略。

inputFormat: 第一行包含两个整数 $n$ 和 $m$，用空格分隔。

outputFormat: 第一行：谁有获胜策略；接下来的行：A 的所有可能的第一步动作依次递增，然后是单词 “winning” 或 B 的一个获胜答案。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$0 < n \le 70$，$0 < m \le 20$。
#### 分值说明
本题分值按 BOI 原题设置，**满分** $40$ 。
#### 题目说明
来源于 Baltic Olympiad in Informatics 1996 的 [Day 2:A NUMBER GAME](https://boi.cses.fi/files/boi1996_day2.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [COCI2010-2011#5] KOŠARKA

description: Slavko 已经开始关注 NBA 了。比赛持续时间正好是 $48$ 分钟。当一场比赛最后会显示统计数据。每当一个球队得分，Slavko 都会记下。他很好奇每个队领先的持续时间。

inputFormat:
输入共 $N$ 行：

第 $1$ 行包含一个整数 $N$，表示事件个数。

下面的 $N$ 行描述了一个队得分时的情况：

每个描述由一个得分的球队（$1$ 或 $2$）和一个时间组成，

时间的格式：$MM:SS$。如果分钟数或秒数 $\le9$，则用前导 $0$ 填充。

outputFormat:
输出的第 $1$ 行为第一个团队处于领先地位的持续时间；

第 $2$ 行为第二个团队处于领先地位的持续时间。

所有的持续时间应该是 $MM:SS$ 格式，包含前导零。

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

队伍 $1$ 在 $20$ 分钟整的时候得一分，比分 $1:0$，处于领先地位。

后面 $28$ 分钟队伍 $2$ 没有进球，故队伍 $1$ 一直保持着领先地位。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 100$，$0\le$ 分钟数 $\le 47$，$0\le $ 秒数 $\le 59$。

**【说明】**

本题分值按 COCI 原题设置，满分 $50$。

题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #5](https://hsin.hr/coci/archive/2010_2011/contest5_tasks.pdf)  _**T2 KOŠARKA**_。


title: [COCI2010-2011#5] BRODOVI

description:
Mirko 住在一个难得有船经过的有港口的小镇上。然而，直到今天，Mirko 还记得那天所有造访过这个港口的船只都出现了。他用索引 $1$ 表示这一天。

许多天过去了，Mirko 记下了至少有一艘船访问港口的日子，把这些日子命名为娱乐日。

此外，Mirko 注意到每艘船都定期访问港口。例如，长度为 $3$ 的间隔表示某艘船在第 $1$ 天、第 $4$ 天、第 $7$ 天、第 $10$ 天等时间访问港口。

给出 Mirko 的娱乐日列表（包括今天，且今天也是一个娱乐日），计算访问他的港口的最小可能的船只数量。

注:所有娱乐日都出现在 Mirko 的列表上，保证永远存在答案。

inputFormat:
输入的第 $1$ 行包含一个整数 $N$，即娱乐天的个数。

下面 $N$ 行，每行一个整数 $A_i$，表示表上的娱乐天数，按升序排列。第一个和最后一个娱乐天分别是 Mirko 开始监测港口交通的日期和今天。今天将一直出现在列表上。第一个索引总是 $1$。

outputFormat: 输出共一行，一个整数，为最小的访问 Mirko 的港口的船舶的数量。

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

最少需要两条船，第一条每 $2$ 天来一次，第二条每 $3$ 天来一次。

**【数据范围】**

对于 $70\%$ 的数据，$A_i\le 5\times 10^6$

对于 $100\%$ 的数据，$2\le N\le 5000$，$1 \le A_i\le 10^9$

**【说明】**

**【说明】**

本题分值按 COCI 原题设置，满分 $70$。

题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #5](https://hsin.hr/coci/archive/2010_2011/contest5_tasks.pdf)  _**T3 BRODOVI**_。


title: [COCI2010-2011#5] HONI

description:
COCI 的出题者必须从一堆题目中选择在下一轮中出现的题目。

题目的难度用 $1$ 到 $n$ 的整数来描述，但是对于某些题目来说，这并不容易准确地确定它们的难度。COCI 的出题者认为这些题目可以被视为有两个连续难度之一。例如，某些题目可以被视为难度为 $3$ 或 $4$。

下一轮 COCI 将包含的 $N$ 个题目。每一个难度，都会有且仅有一个题目。当然，没有题目会出现两次。

找出出题者为下一轮选择题目的不同方法的数量。我们认为两种方法是不同的仅当相同的任务分配给了不同的难度。

由于预期的结果可以非常大，输出的方案数 $\% 10^9+7$。

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

第二行包含 $N$ 个整数 $A_i$，第 $i$ 个数代表困难度恰好为 $i$ 的题目的数量。

第三行输入包含 $N-1$ 个整数 $B_i$，第 $i$ 个数代表困难度为 $i$ 或 $i+1$ 的题目的数量。

outputFormat: 输出共一行，一个整数，表示方案数 $\% 10^9+7$。

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

共 $3$ 种方案：将难度为 $2$ 或 $3$ 的题目视为难度为 $2$ 的，因为难度为 $1$ 的题目有 $3$ 道，所以共 $3$ 种方案。

**【数据范围】**

对于 $100\%$ 的数据，$2\le N\le 10^5$，$0\le A_i,B_i\le 10^9$。

**【说明】**

本题分值按 COCI 原题设置，满分 $100$。

题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #5](https://hsin.hr/coci/archive/2010_2011/contest5_tasks.pdf)  _**T4 HONI**_。


title: [COCI2010-2011#5] DVONIZ

description:
当前 $K$ 个元素的和与最后 $K$ 个元素的和都不大于 $S$ 时，我们说这个 $2\times K$ 个元素的序列是有趣的。

给出一个长度为 $N$ 的序列 $A$。对于每个元素，输出从该元素开始的最长的有趣的子段。

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

下面的 $N$ 行，每行包含序列 $A$ 中的一个整数 $A_i$。这些整数都是正的且它们的和不超过 $2\times 10^9$。

outputFormat:
输出共 $N$ 行。第 $i$ 行包含一个整数，从第 $i$ 元素开始的最长的有趣的子段的长度。

如果当前位置上没有有趣的子段，输出 `0`。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$2\le N\le 10^5$，$1\le S\le 2\times 10^9$。

**【说明】**

本题分值按 COCI 原题设置，满分 $120$。

题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #5](https://hsin.hr/coci/archive/2010_2011/contest5_tasks.pdf)  _**T5 DVONIZ**_。


title: [COCI2010-2011#5] SLIKA

description:
Mirko 刚刚安装了一个全新的绘图程序。该程序支持 $K$ 种不同的颜色，用从 $1$ 到 $K$ 的整数表示。所有的绘图都是在一个尺寸为 $N\times N$ 的画布上完成的。在开始时，所有格子都是白色的(用 `1`表示)。

画布左上角的单元格为坐标 $(0,0)$。第一个坐标 $x$ 表示行，第二个坐标 $y$ 表示列。

Mirko 最喜欢的消遣是使用 `PAINT c x1 y1 x2 y2` 命令绘制矩形棋盘图案，其中 $c$ 表示所选的颜色，$(x1,y1)$ 和 $(x2,y2)$ 分别是左上的坐标和右下的坐标。

矩形左上角的单元格将被绘制为所选的颜色，而其余的则如棋盘一样涂色。没有被所选颜色覆盖的单元格将保持它们之前的颜色。

例如，一个白色的画布涂上一个红色的棋盘图案看起来就像这样的:

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

Mirko最近发现了另外两个命令。他可以随时保存他的画通过使用 `SAVE` 的命令，稍后使用 `load x` 命令再次加载它，其中 $x$ 表示保存的序列号的正整数。

不幸的是，程序崩溃了，Mirko 的画永远丢失了。幸运的是，Mirko 用了一个保存所有已使用命令的日志。你能帮 Mirko 修复那幅丢失的画吗?

inputFormat:
输入的第一行包含三个正整数 $N,K,M$，$N$ 代表画布的边长，$K$ 代表有 $K$ 种颜色，$M$ 代表命令个数。

下面的 $M$ 行每一行都包含描述的三个命令中的一个。输入将不包含任何非法的命令。

outputFormat: 输出共 $N$ 行，每一行包含 $N$ 个表示单元格颜色的整数，对应一行的画。

samples:
3 3 4
PAINT 3 0 0 1 1
SAVE
PAINT 2 1 1 2 2
LOAD 1

samples:
3 4 7
PAINT 2 0 0 1 1
SAVE
PAINT 3 1 1 2 2
SAVE
PAINT 4 0 2 0 2
LOAD 2
PAINT 4 2 0 2 0


title: [COCI2015-2016#2] MARKO

description:
老人 Marko 在他的手机上发现了一个新功能——九键输入！他的手机有一个由数字组成的键盘，看起来像这样：

|  |  |  |  |  |
| -----------: | -----------: | -----------: | -----------: | -----------: |
|  |  1      | 2 abc  | 3 def   |  |
|  | 4 ghi  | 5 jkl   | 6 mno  |  |
|  | 7 pqrs | 8 tuv  | 9 wxyz |  |
|  |  |  |  |  |

为了用这个键盘输入一个单词，Marko 需要按一个键多次来输入所需的字母。更具体地说，如果所需字母是按键上的第一个字母，则需要按一次按键，如果是第二个字母，则需要按两次按键，依此类推。

例如，如果要输入单词 `giht`，Marko 需要先按一次 `4` 来输入 `g`，再按三次 `4` 来输入 `i`，再按两次 `4` 来输入  `h`，最后按一次 `8` 来输入 `t`。

Marko 把手机里的整本字典都背下来了。这本词典由 $N$ 个单词组成，每个单词都由小写英文字母组成，单词的总长度不超过 $10^9$ 个字符。Marko 将给出一个可用按键的集合，并想知道如果使用九键输入，字典中有多少单词可以使用给定的按键集合中的按键输入。

inputFormat:
第一行一个整数 $N$，表示字典中的单词数。

接下来 $N$ 行，每行一个由小写英文字母组成的单词。

最后一行是一个由数字 `2-9` 组成的字符串 $S$，表示可用按键的集合。

outputFormat: 一行一个整数，表示如果使用九键输入，字典中有多少单词可以使用给定的按键集合中的按键输入。

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

组成 `mono` 的四个字母都在按键 `6`  上，可以打出 `mono`。

其它单词均无法打出。

**【样例 2 解释】**

`j` 在按键 `5` 上而 `a` 在按键 `2` 上，所以可以打出 `ja`。

`l` 在按键 `5` 上而 `a` 在按键 `2` 上，所以可以打出 `la`。

**【数据范围】**

对于 $100\%$ 的数据，$1 \le N \le 10^3，1 \le |S| \le 10^3$。

**【说明】**

**本题数据点得分依原题，满分 50**。

题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T1 MARKO**。


title: [COCI2015-2016#2] GEPPETTO

description:
Geppetto 开了一家披萨店，他正在努力做出全市最好的披萨。

Geppetto 用 $N$ 种原材料做比萨，每种原材料只有一个。原材料标号为 $1$ 到 $N$。做披萨很简单，只要把原材料混合好然后放进烤箱里烤一烤就行了。但 Geppetto 发现一共有 $M$ 对原材料是冲突的，如果一对冲突的原材料混合在一份披萨里，这份披萨就会变得十分难吃。这给他带来了额外的麻烦。

Geppetto 想知道他最多能做多少种不同的比萨。如果一份比萨上有编号为 $i$ 的原材料，而另一份比萨上没有，那么这两份比萨就是不同的。

inputFormat:
第一行两个整数 $N,M$，分别表示原材料总数和冲突总数。

接下来 $M$ 行，每行两个整数 $x_i,y_i$，表示一对冲突中两种原材料的编号。

outputFormat: 一行一个整数，表示 Geppetto 最多能做多少种披萨。

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

Geppetto 可以做出以下 `4` 种披萨：

`1`

`2`

`3`

`1 3`

不过因为 Geppetto 可以不放原材料，所以最多可以做出 `5` 种披萨。

**【样例 2 解释】**

没有原材料冲突，所以一共可以做出 $2^3=8$ 种披萨。

**【样例 3 解释】**

由于所有原材料都互相冲突，所以 Geppetto 只能放一种原材料或者不放原材料，一共可以做出 $1+3=4$ 种披萨。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 20，0\le M\le 400，1\le x_i,y_i\le N$，**保证 $x_i\ne y_i$**。

**【说明】**

**本题数据点得分依原题，满分 80**。

题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T2 GEPPETTO**。


title: 「Wdoi-5」模块化核熔炉

background:
为了通过使用核聚变获得能源，守矢神社在旧地狱修建了巨大的核融合控制中心。控制中心形如双层八卦炉，通过各种电路紧密地调控着核融合的精密运行。获得了八咫鸟力量的阿空会在核反应炉的中心点燃神火。

但是正八边形的八卦炉并不利于进行拓展与维护。为了方便地实现电路，河童打算对核控制中心进行模块化改造，以实现核熔炉的维护。具体而言，河童打算将核控制中心设计成由若干个正六边形组成的巨大结构。

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

被赋予了神力的阿空可以依次激发其中的一些模块，而这些被激发的模块会快速影响到一定范围内的其他的模块。通过模块间的链接实现能量的产生。

但是因为阿空脑袋空空，由于它已经激发了多次模块，它已经记不清每个模块当中产生的核融合程度了。你能帮帮它吗？

description:
核控制中心可以看作由若干个正六边形模块组成的六边形阵列。阵列当中每个模块都可以储存核融合能量（一个非负整数）。左图就是一个核控制中心示意图。

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

我们使用如下方式对控制中心中每个模块进行标号。

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

以阵列中心为原点延伸出三根射线作为三根轴，每两根轴之间的夹角为 $120\degree$。这三根轴将平面划分为了三个部分。每个模块都可以使用一个三元组 $(x,y,z)$ 描述它的坐标，表示从原点开始按如图所示的 $x,y,z$ 方向各走若干步之后到达的地方。为了防止出现多个坐标表示同一个模块的情况，做出如下规定：原点的坐标为 $(0,0,0)$；对于中心在坐标轴上的模块，它的坐标就是从原点向所在轴走过的距离；对于其他情况，我们将平面划分为了三个区域（如第二张图的红蓝绿三个区域），一个模块的坐标就是沿着它两侧的轴分别需要走的距离。例如模块 $P$ 的坐标为 $(2,4,0)$。容易发现，每个坐标唯一对应一个模块，一个模块唯一对应一个坐标。

同时定义，两个模块的**距离**为从一个模块到另一个模块需要经过模块（包括起点和终点）的最少个数。在第一张图中，红色部分的模块到其中心距离均不超过 $3$，绿色部分的模块到其中心距离均不超过 $3$，而蓝色部分的模块到其中心距离均不超过 $2$。

核控制中心可以视为到达原点距离不超过 $n$ 的模块组成的阵列。现在阿空会执行以下操作 $m$ 次：

- $\colorbox{f0f0f0}{\verb!x y z r k!}$ ：激活坐标为 $(x,y,z)$ 的模块。它会使控制中心中到它距离不超过 $r$ 的**所有**的模块的核融合能量增加 $k$。保证 $(x,y,z)$ 在控制中心当中。

现在需要求出，执行完 $m$ 个操作后，每个模块里核融合能量值。

inputFormat:
- 第一行共两个正整数 $n,m$，分别表示控制中心的大小、操作个数。
- 接下来 $m$ 行，每行有五个整数 $x_i,y_i,z_i,r_i,k_i$，表示将距离 $(x_i,y_i,z_i)$ 不超过 $r$ 的所有模块的核融合能量增加 $k_i$。

outputFormat:
- 共一行，若干个整数。按照从左往右从上往下的顺序，依次输出每个模块当中核融合能量值。每两个值之间使用空格隔开。

下图当中的红色箭头展示了「从左往右从上往下」的顺序。

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

hint:
样例 $2$ 见下发的附件 $\textbf{\textit{nuclear2.in/nuclear2.ans}}$。
样例 $3$ 见下发的附件 $\textbf{\textit{nuclear3.in/nuclear3.ans}}$。满足特殊性质 $\text{A}$（见下文）。
样例 $4$ 见下发的附件 $\textbf{\textit{nuclear4.in/nuclear4.ans}}$。满足特殊性质 $\text{B}$（见下文）。
样例 $5$ 见下发的附件 $\textbf{\textit{nuclear5.in/nuclear5.ans}}$。

#### 样例 1 解释

如图所示（所有未标出数字的模块的核融合能量值均为 $0$）：

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

按照从左往右、从上往下的顺序依次输出每个数值，即可得到答案。

#### 数据范围及约定

本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Task} & \bm{n\le } & \bm{m\le} & \textbf{特殊性质} \cr\hline
1\sim 3 & 10 & 10 & \text{A} \cr\hline
4\sim 7 & 100 & 300 & - \cr\hline
8\sim 10 & 800 & 3\times 10^5 & \text{B} \cr\hline
11\sim 14 & 800 & 3\times 10^5 & \text{A} \cr\hline
15\sim 20 & 800 & 3\times 10^5 & - \cr\hline
\end{array}
$$

**特殊性质** $\textbf{A}$：保证对于第 $i$ 次操作，被激活的模块到控制中心边缘上的模块的距离不小于 $r_i$。
**特殊性质** $\textbf{B}$：保证对于第 $i$ 次操作，被激活的模块均为 $(0,0,0)$。

对于全部数据，保证 $n\le 800$，$m\le 3\times 10^5$，$1\le k_i\le 5\times 10^3$，$1\le r_i\le 10^9$。每次激活的模块都在控制中心里。


title: [COCI2015-2016#2] VUDU

description:
年轻的 Mirko 最近一直在买 Voodoo 娃娃。因为他对最便宜的东西很感兴趣，所以他每天都在追踪 Voodoo 娃娃的价格。他已经得知了最近 $N$ 天的娃娃价格，第 $i$ 天的娃娃价格记为 $a_i$。

Mirko 认为，连续几天的娃娃平均价格与下一天的娃娃价格之间存在某种联系。他想验证自己的观点，却被一个问题难倒了：“对于一个给定的 $P$，在这 $N$ 天内有多少个不同的连续子序列令娃娃的平均价格大于或等于 $P$ ？”

两个连续子序列不同当且仅它们的开始位置或结束位置不同。

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

接下来一行有 $N$ 个整数，第 $i$ 个整数表示 $a_i$。

最后一行有一个整数 $P$。

outputFormat: 一行一个整数，表示在这 $N$ 天内有多少个不同的连续子序列令娃娃的平均价格大于或等于 $P$。

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

平均数大于等于 `3` 的子序列只有 `3`。

**【样例 2 解释】**

平均数大于等于 `2` 的子序列有 `5` 个，它们是：

`1 3`

`1 3 2`

`3`

`3 2`

`2`

**【数据范围】**

对于 $30\%$ 的数据，$1\le N\le 10^4$；

对于 $100\%$ 的数据，$1\le N\le 10^6，1\le a_i\le 10^9，1\le P\le 10^9$。

**【说明】**

**本题数据点得分依原题，满分 140**。

题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T5 VUDU**。


title: [COCI2015-2016#2] DRŽAVA

description:
一个遥远的国家刚刚举行了选举，新首相当选了。目前，这个国家没有一条公路，所以首相决定用双向公路把国内的城市连接起来，组成县，使国家现代化。

这个国家共有 $N$ 个城市，每个县由一个或多个城市组成，**两个城市将位于同一个县，当且仅当使用新建的道路可以从一个城市到达另一个城市**。这些城市在二维坐标系中用点来表示，两个城市之间的道路表示为连接两个城市所在点的线段。这条路的长度等于以公里为单位的线段的长度。

该国目前正遭受经济衰退，因此首相决定，由于缺乏预算，他们将不修建超过 $D$ 公里的道路。此外，**如果至少有一个县存在一个非空子县（可以包括该县的所有城市），使得子县内的居民总数可以被 $K$ 整除，首相就会高兴**。例如，如果 $K=4$，一个县的城市分别有 `3`、`5`、`7` 个居民，首相就会高兴，因为前两个城市的居民总数等于 `8`。

请你确定最小的 $D$ 来帮助首相降低成本，使得首相感到高兴。

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

接下来 $N$ 行，每行三个整数 $x_i,y_i,k_i$，分别表示这个城市的坐标和这个城市的人口。

outputFormat: 一行一个实数，表示最小的 $D$，**四舍五入保留三位小数**。

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

只有当所有城市都在同一个县里首相才能高兴，所以最小的 $D$ 为 $1.414$。

**【样例 2 解释】**

当前五个城市都在同一个县里首相才能高兴，且此时 $D$ 是最小的，所以最小的 $D$ 为 $5.657$。

**【数据范围】**

对于 $40\%$ 的数据，$1\le N\le10^3$；

对于 $100\%$ 的数据，$1\le N\le5\times10^4，1\le K\le30，0\le x_i,y_i,k_i\le10^8$。

**【说明】**

**本题数据点得分依原题，满分 160**。

题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T6 DRŽAVA**。


title: [图论与代数结构 101] 图的代数表示

description: 给定一张 $n$ 个点 $m$ 条边的图，**有可能存在重边和自环**。请你给出这张图所有的代数表示。

inputFormat:
第一行四个正整数 $n$，$m$，$type1$ 和 $type2$。其中 $n$ 和 $m$ 分别表示图的点数和边数。$type1 = 0$ 表示该图为无向图，$type1 = 1$ 表示该图为有向图。$type2 = 0$ 表示该图不是赋权图，$type2 = 1$ 表示该图是赋权图。

如果 $type2 = 0$，接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ 表示一条边。

如果 $type2 = 1$，接下来 $m$ 行，每行三个正整数 $u$ ， $v$ 和 $d$ 表示一条边，其中 $d$ 为这条边的边权。

outputFormat:
按顺序输出下列代数表示：

1. 邻接矩阵或权矩阵。输出 $n$ 行，每行 $n$ 个数表示矩阵。如果该图存在重边则不输出。如果 $type2 = 0$ 输出邻接矩阵，如果 $type2 = 1$ 输出权矩阵。

2. 关联矩阵。输出 $n$ 行，每行 $m$ 个数表示矩阵。如果 $type2 = 1$ 或有自环则不输出。

3. 邻接表。输出 $n$ 行。如果 $type2 = 0$ 每行输出 $d _ i$ 个数，其中 $d _ i$ 为节点 $i$ 的度数（无向图）或正度（有向图），每个数表示一条与 $i$ 相接的边。如果 $type2 = 1$ 每行输出 $2d _ i$ 个数，每两个数表示一条边。

4. 正向表。如果 $type2 = 0$ 输出两行，分别表示向量 $A$ 和向量 $B$ 。如果 $type2 = 1$ 输出三行，分别表示向量 $A$，向量 $B$ 和向量 $Z$。

5. 逆向表。如果 $type1 = 0$ 则不输出（因为此时逆向表与正向表相同）。如果 $type2 = 0$ 输出两行，分别表示向量 $A$ 和向量 $B$ 。如果 $type2 = 1$ 输出三行，分别表示向量 $A$，向量 $B$ 和向量 $Z$。

其中，邻接表、正向表、逆向表每个点对应的所有边按输入顺序输出。

**正向表与逆向表的 $A$向量是 $n + 1$ 维向量，有向图中 $A(n + 1) = m + 1$，无向图中 $A(n + 1) = 2m + 1$。**

hint:
对于所有数据，满足 $1 \le n \le 300$，$1 \le m \le 300$，$1 \le 边权 \le 32768$。

**细节提示：**

1.无向图中一些数组可能需要 $2 m$ 的长度，请仔细检查以免数组开小。

2.无向图中如果存在自环，则在邻接表和正向表中都需要将这条边输出两次，但不影响邻接矩阵或权矩阵的输出。

3.逆向表中对于连向一点的边也要按输入顺序输出而不是边权大小顺序。

4.无向带权图中每条非自环边都会修改权矩阵中两个位置。

5.无法通过时可以通过构造有向/无向、带权/不带权、有/无自环、有/无重边的小数据来检查代码。

##### 样例一解释

第 $1$ 行至第 $3$ 行是邻接矩阵；

第 $4$ 行至第 $6$ 行是关联矩阵；

第 $7$ 行至第 $9$ 行是邻接表；

第 $10$ 行至第 $11$ 行是正向表。

##### 样例二解释

第 $1$ 行至第 $2$ 行是邻接表；

第 $3$ 行至第 $5$ 行是正向表；

第 $6$ 行至第 $8$ 行是逆向表。


title: [图论与代数结构 202] 最短路问题_2

description:
给定一张 $n$ 个点、$m$ 条边的有向图，求 $1$ 号点到每个点的最短路径长度。

**注意，图可能存在重边和自环。**

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

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$。表示一条从 $u_i$ 到 $v_i$ 长度为 $w_i$ 的有向边。

outputFormat: 一行 $n$ 个整数，第 $i$ 个整数表示 $1$ 到 $i$ 的最短路径长度，如果不存在从 $1$ 到 $i$ 的路径则第 $i$ 个整数用 $-1$ 替代。

hint:
本题没有部分分。

对于所有数据，$1\leq n,m \leq 3\times 10^5$，$1\leq w_i\leq 10^9$。

请注意答案上界的大小，可能需要使用 C++ 中的 `long long int` 类型。


title: [图论与代数结构 301] 最短树问题_1

description:
在离散数学课程的学习中，大家学习了最短树相关的知识，现在来检查一下大家的学习情况。

给定一张 $n$ 个点 $m$ 条边的带权连通无向图，点的编号从 $1$ 到 $n$，可能存在重边和自环。现在，请你求出这张图总边权和最小的支撑树（最短树）的边权之和。即，找到一颗支撑树，满足选用边的边权和最小，输出这个边权和。

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

接下来 $m$ 行，每行三个非负整数 $u, v, w$ 表示一条连接 $u$ 和 $v$ 这两个点的无向边和这条边的边权 $w$。

outputFormat: 输出仅一行一个非负整数，表示最短树的边权之和。

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

选择 $(1,3)$、$(2,3)$ 和 $(3,4)$ 这三条边构成一颗支撑树。

**【数据范围】**

对于所有数据，满足 $1\leq n \leq 2000$，$1 \leq m \leq 3000$，边权均是 $[0, {10}^9]$ 中的整数，保证输入的图合法且满足题目中的限制条件。

请注意答案上界的大小，可能需要使用 C++ 中的 `long long int` 类型。


title: [图论与代数结构 201] 最短路问题_1

description:
给定一张 $n$ 个点、$m$ 条边的有向图，求 $1$ 号点到每个点的最短路径长度。

**注意，图可能存在重边和自环，保证不存在负环。**

hint:
本题没有部分分。

对于所有数据，$1\leq n,m \leq 2\times 10^3$，$-10^9\leq w_i\leq 10^9$。

请注意答案上界的大小，可能需要使用 C++ 中的 `long long int` 类型。


title: [图论与代数结构 302] 最短树问题_2

outputFormat: 输出仅一行一个非负整数，表示最短树的边权之和。

hint:
对于所有数据，满足 $1\leq n \leq 100000$，$1 \leq m \leq 300000$，边权均是 $[0, {10}^9]$ 中的整数，保证输入的图合法且满足题目中的限制条件。

请注意答案上界的大小，可能需要使用 C++ 中的 `long long int` 类型。


title: [图论与代数结构 401] 二分图匹配

description: 给定一张左侧有 $nl$ 个点、右侧有 $nr$ 个点、$m$ 条边的二分图，求一组它的最大匹配。

inputFormat:
第一行三个整数 $nl$，$nr$，$m$。

接下来 $m$ 行，每行两个整数 $u_i$，$v_i$，表示有一条左侧第 $u_i$ 个点连向右侧第 $v_i$ 个点的边。

outputFormat: 第一行一个整数表示最大匹配数。

hint: 对于所有数据，$1\leq nl,nr\leq 500$，$1\leq m\leq 2.5\times 10^5$。


title: [图论与代数结构 501] 网络流_1

description:
给定 $n$ 个点， $m$ 条边，给定每条边的容量，求点 $s$ 到点 $t$ 的最大流。

**注意，图可能存在重边。**

inputFormat:
第一行四个整数 $n$，$m$，$s$，$t$。

接下来的 $m$ 行，每行三个整数 $u$，$v$，$c$，表示从 $u$ 到 $v$，容量为 $c$ 的一条边。

outputFormat: 输出一行一个整数，表示从 $s$ 到 $t$ 的最大流。

hint: 对于所有数据，$1 \le n \le 30$，$1 \le m \le 200$，$0 \le c \le 2 ^ {31} - 1$，所有数据均为随机构造。


title: [图论与代数结构 502] 网络流_2

outputFormat: 输出一行一个整数，表示从 $s$ 到 $t$ 的最大流。


title: [图论与代数结构 601] 最小费用最大流

description:
给定 $n$ 个点，$m$  条边，给定每条边的容量和单位流量需要支付的费用，求点 $1$ 到点 $n$ 的最大流以及此时需要的最小费用。

**注意，图可能存在重边。**

inputFormat:
第一行两个整数 $n$、$m$，表示有 $n$ 个点 $m$ 条边。

从第二行开始的之后 $m$ 行，每行四个整数 $s_i$、$t_i$、$c_i$、$w_i$ 表示一条从 $s_i$ 到 $t_i$ 的边，容量为 $c_i$，单位流量需要支付的费用为 $w_i$。

outputFormat: 输出一行两个整数，表示最大流和最小费用。

hint:
对于所有数据，保证 $1 \le n \le 400$，$0 \le m \le 15000$，$0 \le w_i \le 2 ^ {31} - 1$，保证答案在 32 位有符号整数范围内。

本题数据较弱，不存在最小费用最大流的极限情况。

实现时，若使用 Bellman-Ford 算法可以考虑如下优化：若在某次迭代中所有 $\pi(i)$ 均保持不变，则不继续迭代。


title: [图论与代数结构 701] 强连通分量

description:
给定一张 $n$ 个点 $m$ 条边的有向图，求出其所有的强连通分量。

**注意，本题可能存在重边和自环。**

inputFormat:
第一行两个正整数 $n$ ， $m$ ，表示图的点数和边数。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ 表示一条边。

outputFormat:
第一行一个整数表示这张图的强连通分量数目。

接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。


title: [图论与代数结构 801] 无向图的块

description:
在离散数学课程的学习中，大家学习了无向图中”割点“和“块”的定义，现在来检查一下大家的学习情况。

给定一张 $n$ 个点 $m$ 条边的无向图，点的编号从 $1$ 到 $n$ ，可能存在重边和自环，不保证是一张连通图。现在，请你求出这张图所有的块。

注意，我们不把一个没有任何与其相连边的点看成割点；因此，一个单独的点构成的连通块不被看成是块。你可以通过样例理解这个事情。

在输出的时候，我们规定这么一个输出的顺序：首先，对于一个块，我们把该块中所有点按照编号从小到大排序；然后，对于两个块，我们规定，把点按照顺序拿出来排成一个序列，字典序较小的排在前面。这样，我们就可以对所有块规定了一个顺序。最终输出就按照这样的顺序输出。

有关字典序的定义，可以在搜索引擎上查找，或者参考[维基百科_字典序](https://en.wikipedia.org/wiki/Lexicographic_order)。

inputFormat:
第一行两个正整数 $n$ 和 $m$ ，分别表示给定无向图的点数和边数。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ 表示一条连接这两个点的无向边。

outputFormat:
第一行一个正整数 $Cnt$ 表示答案，即图中块的个数。

接下来 $Cnt$ 行，第 $i$ 行输出若干个正整数，表示第 $i$ 个块中的所有点。注意同一个块点的编号按照从小到大的顺序输出。按照题目中规定的字典序顺序输出块。

hint:
本题没有部分分。

对于所有数据，满足 $1\leq n \leq 50000$，$1 \leq m \leq 300000$，保证输入的图合法且满足题目中的限制条件。