title: [HEOI2012] 旅行问题

description:
yz 是 Z 国的领导人，他规定每个地区的名字只能为 $26$ 个小写拉丁字母的一个。由于地区数有可能超过 $26$ 个，便产生了一个问题，如何辨别名字相同的地区？于是 yz 规定，一个地区的描述必须包含它的所有上级，且上级按次序排列。于是，一个地区的描述是一个字符串。比如说，一个地区的名字为 $\tt c$，它的上级为 $\tt b$，$\tt b$ 的上级为 $\tt a$，$\tt a$ 没有上级，那么这个地区就描述为 $\tt abc$。显然，这个描述同时包含了 $\tt c$ 的上级 $\tt b$ 和 $\tt b$ 的上级 $\tt a$ 的描述，分别为 $\tt ab$ 和 $\tt a$。

值得注意的是，每个地区最多有一个上级，同一上级的地区之间名字不同，没有上级的地区之间名字不同。

现在，yz 对外公布了 $n$ 个地区的描述，这些描述中包含了 Z 国所有地区的描述，并让你处理来访者的旅行问题。

现有 $m$ 对人访问这个国家，对于每对人，第一个人喜欢第 $i$ 个描述中的第 $j$ 个地区，设这个地区描述为 $s_1$，第二个人喜欢第 $k$ 个描述中的第 $l$ 个地区，设这个地区描述为 $s_2$。他们为了统一行程，决定访问描述为 $s$ 的地区（显然他们只关心地区的名字，并非是地区本身），设 $s$ 的长度为 $t$，$s$ 需要满足以下条件：

1. $t\leq j$，$t\leq l$。
2. $s[1\cdots t]=s_1[j-t+1\cdots j]$，$s[1\cdots t]=s_2[l-t+1\cdots l]$，即 $s$ 为 $s_1$ 中 $1$ 到 $j$ 位与 $s_2$ 中 $1$ 到 $l$ 位的公共后缀。
2. $t$ 最大化。

为了不使输出过大，你只需把这个字符串按照如下生成的 $26$ 进制数转成 $10$ 进制后 $\bmod\ (10^9+7)$ 后输出：

- $a \to 0$；
- $b \to 1$；
- ……
- $z \to 25$。

比如地区 $\tt cab$ 被编码成 $2\times26^2+0\times26^1+1\times26^0=1353$。

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

第 $2\cdots n+1$ 行，每 $i+1$ 行给定一个字符串 $a_i$，表示第 $i$ 个描述。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行给定四个整数 $i,j,k,l$，字母含义与题目描述一致。

outputFormat: 共 $m$ 行，每行一个整数，表示答案字符串的编码。

hint:
### 样例解释

询问 $1$ 中的公共后有 $\tt ab$ 和 $\tt b$，但是没有 $\tt ab$ 这个地区，只有 $\tt b$ 地区，所以只能选择 $\tt b$ 这个地区；

询问 $2$ 中的公共后有 $\tt abb$，$\tt bb$ 和 $\tt b$，但是没有 $\tt abb$ 和 $\tt bb$ 这两个地区，只有 $\tt b$ 地区，所以只能选择 $\tt b$ 这个地区。

### 数据范围及约定

设这个国家地区总数数为 $tot$（注意：输入的字符串总长度可能超过 $tot$！）

- 对于 $30\%$ 的数据，满足 $1\le tot, m, n \le 100$；
- 对于 $50\%$ 的数据，满足 $1\le tot, m, n \le 1000$；
- 对于 $80\%$ 的数据，满足 $1\le tot, m, n \le 10^5$；
- 对于 $100\%$ 的数据，满足$1\le  tot, m, n \le 10^6$。

保证输入文件不超过 $20\text{MB}$。

HEOI2012 Day 2 Task 2


title: [HEOI2012] 野外探险

type: P

background: 小 H 是一位探险家。在险峻的珠穆朗玛峰，原始辽阔的非洲大草原，美丽冻人的南极大陆等地方都留下过这位探险家的足迹。这次，他来到了位于南美洲充斥着大量毒虫猛兽的以及各式各样传说的亚马逊热带雨林进行探险。为此，他花了许多时间来准备这次激动人心的探险。在准备就绪后，小 H 和他的助手在当地导游的带领下踏入了这片雨林。

description:
通过 GPS 定位系统，他们获得了雨林大致的地图。这个地图是一个 $n$ 行 $m$ 列的字符网格图，’.’表示的是空地，’*’表示的是不可通行的区域，’#’表示的是需要清理的区域，’H’表示小H所在的位置，该区域是空地。他们的移动方式有 $t$ 种，用$a[i]$,$b[i]$($1\leq i\leq t$)表示，假设他们所在的位置为第 $x$ 行第 $y$ 列，那么他们下一步的位置将是第 $x+a[i]$行第 $y+b[i]$列，也可以是反方向，即第 $x-a[i]$行第 $y-b[i]$列。小 H 一行人每天可在选择一种移动方式，朝着正方向或者反方向连续走若干步之后停下，不可以不走。在当天的行走过程中，他们不可以到达不可通行的区域，如果他们到达了一个需要清理的区域，他们会停止移动。为了以后探险的方便，他们会用该天剩下的时间来清理该区域，之后该区域将永久变成空地。

现在，为了使探险活动顺利的进行，他们将 $q$ 个询问通过网络发送给了你，询问他们在第 $d[i]$($1\leq i\leq q$)天能到达的区域个数，题目保证不会有无路可走的情况。你能帮助他解决这个问题吗？

inputFormat:
输入的第 $1$ 行包含三个正整数，分别表示 $n$、$m$、$t$。

在第 $2$ 行至第 $n+1$ 行中，每行都有 $m$ 个字符（只可能是’.’，’*’，’#’，’H’，其中’H’ 有且只有一个）。

在第 $n+2$ 行至第 $n+t+1$行中，每行有两个整数，分别表示 $a[i]$，$b[i]$（$a[i]$，$b[i]$不可能同时为 $0$）。

在第 $n+t+2$ 行包含一个正整数，表示 $q$。

在第 $n+t+3$ 行至第 $n+t+q+2$ 行共有 $q$ 个整数，表示他们所询问的时间点（即 $d[i]$）。

outputFormat: 输出共 $q$ 行，对于每一个询问，输出他们所能走到的地点的个数。

hint:
对于 20%的数据，满足 $n,m\leq4$, $q\leq100$；

对于 70%的数据，满足 $n,m\leq300$；

对于 100%的数据，满足 $n,m\leq1000$, $t\leq5$, $q\leq1000$, $0\leq d[i]\leq10^9$；

HEOI 2012 Day2 Task3


title: 偷上网

description:
Alice 和 Bob 生活在一个 $l \times l$ 的正方形房子里，由于 Bob 最近沉迷隔膜，Alice 决定要限制 Bob 上网的频率。

Alice 建造了 $n$ 个无线信号屏蔽器，第 $i$ 个位于 $(x_i, y_i)$，屏蔽范围为 $\frac{l}{n}$。

Bob 网瘾发作按捺不住上网的冲动，找到了你，帮他找到一个位置 $(x, y)$，使得没有被 Alice 的无线信号屏蔽器覆盖。

inputFormat:
第一行两个整数 $n, l(1 \leq n \leq 10, 1 \leq l \leq 10^5)$，分别表示无线信号屏蔽器的个数和房子的大小。

接下来 $n$ 行，每行 $2$ 个数，分别是 $x_i, y_i(0 \leq x_i, y_i \leq l)$，意义如上所述。

outputFormat:
如果可以找到，输出两个数 $x, y(0 \leq x, y \leq l)$，意义如上所述，如果有多组解，输出任意一组即可。如果你输出的解满足到任意一个屏蔽器的距离都不小于 $\frac{l}{n} + 10^{-6}$，则视为正确。

否则输出 "GG"。


title: 太极剑

description:
在学习太极之后，Bob 要求 Alice 教他太极剑。Alice 告诉他首先需要通过一项基本剑术测试。测试要求 Bob 尽可能快地切断 $n$ 根绳子。

所有绳子的端点两两不同，所以共有 $2n$ 个端点。这些端点被捆在一个圆上，等距离分布。我们把这些端点按顺时针方向编号为 $1$ 到 $2n$。

Bob 每次切割的轨迹是一条直线，可以将所有与这条直线相交的绳子切断，他想知道至少多少次可以切断所有的绳子。

inputFormat:
第一行一个整数 $n(1 \leq n \leq 2 \times 10^5)$，表示绳子的个数。

接下来 $n$ 行，每行两个整数 $a_i, b_i(1 \leq a_i, b_i \leq 2n, a_i \not= b_i)$，表示第 $i$ 根绳子的两个端点的编号。

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


title: 玩游戏

background: ### 警告：恶意提交评测将被封号。

description:
Alice 和 Bob 又在玩游戏。

对于一次游戏，首先 Alice 获得一个长度为 $n$ 的序列 $a$，Bob 获得一个长度为 $m$ 的序列 $b$。之后他们各从自己的序列里随机取出一个数，分别设为 $a_x, b_y$，定义这次游戏的 $k$ 次价值为 $(a_x + b_y)^k$。

由于他们发现这个游戏实在是太无聊了，所以想让你帮忙计算对于 $i = 1, 2, \cdots, t$，一次游戏 $i$ 次价值的期望是多少。

由于答案可能很大，只需要求出模 $998244353$ 下的结果即可。

inputFormat:
第一行两个整数 $n, m(1 \leq n, m \leq 10^5)$，分别表示 Alice 和 Bob 序列的长度。

接下来一行 $n$ 个数，第 $i$ 个数为 $a_i(0 \leq a_i < 998244353)$，表示 Alice 的序列。

接下来一行 $m$ 个数，第 $j$ 个数为 $b_j(0 \leq b_j < 998244353)$，表示 Bob 的序列。

接下来一行一个整数 $t(1 \leq t \leq 10^5)$，意义如上所述。

outputFormat: 共 $t$ 行，第 $i$ 行表示一次游戏 $i$ 次价值的期望。


title: [COCI2017-2018#5] Olivander

description:
Harry Potter has damaged his magic wand in a fight with Lord Voldemort. He has decided to
get a new wand in Olivander's wand shop. On the floor of the shop, he saw N wands and N
wand boxes. The lengths of the wands are, respectively, $X_1$
,$X_2$
...$X_n$
, and the box sizes are
$Y_1$
,$Y_2$
...$Y_n$
. A wand of length X can be placed in a box of size Y if X ≤ Y
. Harry wants to know
if he can place all the wands in boxes so that each box contains exactly one wand.
Help him solve this difficult problem.

inputFormat:
The first line of input contains the positive integer N
(1 ≤ N
≤ 100), the number from the task.
The second line contains N
positive integers $X_i$
(1 ≤ $X_i$
≤ $10^9$ ), the numbers from the task.
The third line contains N
positive integers $X_i$
(1 ≤ $X_i$
≤ $10^9$ ), the numbers from the task.

outputFormat:
If Harry can place all the wands in boxes, output “DA” (Croatian for yes), otherwise output
“NE” (Croatian for no).

translation:
## 题意简述
有 $n$ 个棍子和 $n$ 个盒子，要求每个盒子里放的棍子的总长度不能超过盒子的高度。求是否有方案使得各个棍子都能放到任意一个盒子里。是输出 DA，否则输出 NE。（一个盒子里只能放一根棍子）
## 输入
输入共三行。

第一行，一个整数 $n$。

第二行， $n$ 个整数 $X_1,X_2,X_3,\dots,X_n$。其中第 $i$个数 $X_i$表示第 $i$根棍子的长度。

第三行， $n$个整数 $Y_1,Y_2,Y_3,\dots,Y_n$。其中第 $i$ 个数 $Y_i$ 表示第 $i$ 个盒子的高度。
## 输出
输出仅一行。即如果有能够将各个棍子都能放进任一盒子的方案输出 DA，否则输出 NE（输出不包括引号）。

## 样例解释
样例 $1$：哈利波特能够将所有棍子放进盒子里面。例如 $X_1\Rightarrow Y_3,X_2\Rightarrow Y_2,X_3\Rightarrow Y_1$。

样例 $2$：哈利波特不能够将所有棍子放进盒子里。
因为 $Y_2=2$，不能塞下任何一根棍子。

## 数据范围
对于 $60\%$ 的数据，保证 $n\leqslant9$。

对于 $100\%$ 的数据，保证 $n\leqslant100$，并且  $\forall i$，都满足 $X_i,Y_i\leqslant10^9$。

hint:
In test cases worth 60% of total points, it will hold N
≤ 9.

**Clarification of the first test case:**

Harry can place the wands in boxes. For example, he can place the wand of length 5 in a box of size
6, wand of length 7 in a box of size 13, and wand of length 9 in a box of size 10.

**Clarification of the second test case:**

Harry can’t place the wands in boxes because the box of size 2 can’t fit any of the wands.


title: [COCI2017-2018#5] Spirale

description:
Little Stjepan often likes to go out with his friends and have fun in a popular nightclub in
Zagreb. However, Stjepan sometimes drinks too much soda and gets light headed from all
the sugar. Last night was an example of this, which is why Stjepan had the same image in
his mind the whole time. It was a scribble of number spirals of some sort. Since he can’t
quite remember what the image looked like, but can describe it, he is asking you to
reconstruct it for him.

Stjepan recalls that the image was of the shape of a table consisting of numbers written in N
rows and M columns. Also, he recalls that there were K spirals in that table. For each spiral,
the starting position is known, as well as the direction it’s moving in, which can be clockwise
and counter-clockwise. An example is shown in the images below. The spirals created
Stjepan’s image in exactly $10^{100}$ steps in the following way:
1. Initially, the table is empty, and each spiral is in its own starting position.
2. In each following step, each spiral moves to its next position. It is possible that, at
times, the spirals leave the boundaries of the table, but also to return within it.
3. After exactly $10^{100}$ steps, for each field in the table, the final value is the value of the
earliest step in which one of the spirals touched that field.

![](https://cdn.luogu.com.cn/upload/pic/19205.png)

inputFormat:
The first line of input contains positive integers N
, M
(1 ≤ N
, M
≤ 50) and K
(1 ≤ K
≤ N
*M
).
Each of the following K lines contains three positive integers $X_i$
, $Y_i$ and $T_i$ (1 ≤ X ≤ N
, 1 ≤ Y ≤
M
, 0 ≤ T ≤ 1), the starting position of the $i^{th}$
spiral and its direction (0 - clockwise, 1 -
counter-clockwise). No two spirals will begin in the same field.

outputFormat:
You must output N lines with M numbers, representing the table after each spiral makes
$10^{100}$ steps.

translation:
### 题目描述

小斯捷潘经常喜欢和朋友们一起去萨格勒布一家很受欢迎的夜总会玩。不过，斯捷潘有时会喝太多苏打水，糖分过多会让他头晕目眩。昨晚就是一个例子，所以斯捷潘脑海中一直浮现着同一个画面。那是一个潦草的数字螺旋。由于他不太记得那幅图的样子，但可以描述出来，所以他请求您为他重现那幅图。

斯捷潘回忆说，图像是一张表格，由 $N$ 行 $M$ 列数字组成。此外，他还记得表格中有 $K$ 个螺旋。每个螺旋的起始位置和移动方向都是已知的，有顺时针和逆时针两种。下面的图片就是一个例子。这些螺旋以如下方式创建了斯捷潘的图像，步数正好为 $10^{100}$ ：

1. 一开始，表格是空的，每个螺旋都在自己的起始位置。
2. 在接下来的每一步中，每个螺旋都会移动到下一个位置。有时，螺旋可能会离开表格，但也可能会返回到表格内。
3. 经过整整 $10^{100}$ 步后，对于表格中的每个格子，格子中的数值就是其中一个螺旋最少经过该格子的步数。

![](https://cdn.luogu.com.cn/upload/pic/19205.png)

### 输入格式

第一行输入包含正整数 $N$ , $M$ （ $1 ≤ N , M ≤ 50$ ）和 $K$ （ $1 ≤ K ≤ N \times M$ ）。下面 $K$ 行中的每一行都包含三个正整数 $X_i,Y_i,T_i$ （ $1 ≤ X_i ≤ N , 1 ≤ Y_i ≤ M , 0 ≤ T_i ≤ 1$ ），第 $i$ 个螺旋的起始位置和方向（ $0$ 表示顺时针，$1$ 表示逆时针）。没有螺旋的起始位置在同一格子上。

### 输出格式

您必须输出一个 $N$ 行 $M$ 列的表格，表示在每个螺旋移动 $10^{100}$ 步之后的表格。

### 说明/提示

对于 $50\%$ 的数据来说，保证 $N=M,K=1$ 并且 $X_i=Y_i=\lfloor\frac{N+1}{2}\rfloor$ （也就是说， $X_i$ 和 $Y_i$ 会等于 $N+1$ 除以 $2$ 再下取整的结果。）

![](https://cdn.luogu.com.cn/upload/pic/19206.png)

为简单起见，在第一个螺旋的数字后面加上字母 `A` ，在第二个螺旋的数字后面加上字母 `B` 。只显示了第一个螺旋的前 $20$ 步和第二个螺旋的前 $21$ 步。灰色格子是表格中的格子，其他格子都超出了表格的范围，但显示出来是为了说明螺旋在表格外移动的方式。

hint:
In test cases worth 50% of total points, it will hold: N
=M
i K
=1 and $X_i$
=$Y_i$
=$\lfloor\frac{N+1}{2}\rfloor$, i.e. $X_i$
and $Y_i$
will be equal to the integer division of N
+1 with 2.

![](https://cdn.luogu.com.cn/upload/pic/19206.png)

For simplicity’s sake, the letter A was added to the numbers from the first spiral, and the letter B to the
numbers from the second spiral. Only the first 20 steps of the first spiral are shown, and 21 steps of
the second spiral. The fields in gray are the fields from the table we’re interested in, all other fields are
out of the table’s bounds, but are shown to illustrate the way the spirals move outside of the table.


title: [COCI2017-2018#5] Birokracija

description:
Mirko has become CEO of a huge corporation. This corporation consists of N people,
labeled from 1 to N
, and Mirko is labeled 1. The corporation is structured so that each
employee (except Mirko) has a boss, and we say that employee is an assistant to that boss.
Each boss can have multiple assistants, but still reports to their boss. This holds for
everyone except Mirko, who is at the top of the pyramid and doesn’t have a boss, but has his
assistants.

When Mirko gets a task from the investors, he then delegates that task to his assistant with
the minimal number. This assistant then delegates the task to their assistant with the
minimal number, and this process repeats until the task is given to an unlucky person
without an assistant, who then must do the task.

This is when the real problems begin. The person that did the task gets paid 1 coin, the boss
of that person gets 2 coins, the boss of that person gets 3 coins, and so on, all the way to
Mirko, who gets as many coins as there are people in this sequence. After that, the
employee that really did the job realizes how unfair the system is and quits their job out of
principle.

When it comes to doing the next task in the corporation, there is a person less, so maybe the
paychecks are less, but the work must continue. Tasks are piling up, so the whole procedure
(assigning a new task, doing it, dividing paychecks and the person doing the task quitting)
repeats until Mirko is left alone in the corporation and does his first (also his last) task.

Of course, Mirko will have amassed quite a fortune until then, but he also wants to know how
much money each of the employees earned.

inputFormat:
The first line of input contains the positive integer N (2 ≤ N ≤ 2·$10^5$ ), the number of
employees (including Mirko).

The following line contains N- 1 positive integers $a_2$ , $a_3$ , $a_4$ , …, $a_n$
(1 ≤ $a_i$
< i
), where $a_i$
denotes the boss of employee i
.

outputFormat:
You must output a single line consisting of N numbers, the $i^{th}$ number corresponding to the
amount of money earned by the $i^{th}$ employee.

translation:
Mirko是一家大公司的CEO。该公司由$N$人组成，编号为1到N，Mirko编号为$1$。公司的结构像一棵树一样，每个员工（Mirko除外）都有老板，我们说这个员工是该老板的助手。每个老板都可以有多名助手。Mirko没有老板，但有他的助手。

之后会有一些任务，Mirko会将该任务委托给他编号最小的助手。然后，该助手也将任务委托给他编号最小的助手，并且这个过程重复进行，直到任务被发送给没有助手的人，然后他必须亲自完成任务。

执行任务的人获得1个硬币，那个人的老板获得2个硬币，那个人的老板获得3个硬币，依此类推，一直到Mirko。之后，真正完成工作的员工意识到系统的不公平并感到伤心，并且不会再执行任务（也就是辞职）。

当公司收到的下一个任务时，因为少了一个人，所以薪水可能更少，但工作必须继续。任务是无限多的（直到公司倒闭），因此整个过程（分配新任务，执行任务，划分薪水和执行任务人员的退出）重复进行，最后Mirko独自留在公司并完成他的第一个（也是他的最后一个）任务。

当然，在此之前，Mirko将积累相当多的财富，但他也想知道每个员工赚了多少钱。

输入输出格式

输入格式：
第一行有一个整数$N(2 ≤ N ≤ 2e5)$，既包括Mirko在内的员工的个数。
紧接着第二行有$n-1$个整数，分别为$a2,a3,\cdots ,an(1 ≤ a_i < i )$，$ai$表示$ai$的上级。

输出格式

输出一行$N$个整数，第$i$个整数表示编号为$i$的人
能得到的金币数。

说明

$50\%$的数据满足$2≤N≤5000$。

hint:
In test cases worth 50% of total points, it will hold 2 ≤ N
≤ 5000.

**Clarification of the second test case:**

Mirko assigns the first task to employee 2, who then assigns it to employee 3, who then does it. For
this, employee 3 gets 1 coin, employee 2 gets 2 coins, and employee 1 (Mirko) gets 3 coins.
Employee 3 then quits.

Mirko assigns the second task to employee 2, who then assigns it to employee 4 (because employee
3 quit), who then assigns it to employee 5, who then does it. For this, employee 5 gets 1 coin,
employee 4 gets 2 coins, employee 2 gets 3 coins, and employee 1 gets 4 coins. Employee 5 then quits.

The procedure is repeated for a total of 5 tasks.

In total, Mirko gets 13 coins, employee 2 gets 8, employee 4 gets 3, and employee 3 and 5 each get 1
coin.


title: [COCI2017-2018#5] Pictionary

description:
There is a planet, in a yet undiscovered part of the universe, with a country inhabited solely
by mathematicians. In this country, there are a total of N mathematicians, and the interesting
fact is that each mathematician lives in their own city. Is it also interesting that no two cities
are connected with a road, because mathematicians can communicate online or by
reviewing academic papers. Naturally, the cities are labeled with numbers from 1 to N.

Life was perfect until one mathematician decided to write an academic paper on their
smartphone. The smartphone auto-corrected the word “self-evident” to “Pictionary” and the
paper was published as such. Soon after, the entire country discovered pictionary and
wanted to meet up and play, so construction work on roads between cities began shortly.
.
The road construction will last a total of M days, according to the following schedule: on the
first day, construction is done on roads between all pairs of cities that have M as their
greatest common divisor. On the second day, construction is done on roads between all
pairs of cities that have M-1 as their greatest common divisor, and so on until the $M^{th}$ day
when construction is done on roads between all pairs of cities that are co-prime. More
formally, on the $i^{th}$ day, construction is done on roads between cities a and b if gcd(a, b) = $M-i+1$.

Since the mathematicians are busy with construction work, they’ve asked you to help them
determine the minimal number of days before a given pair of mathematicians can play
pictionary together.

inputFormat:
The first line of input contains three positive integers N, M
and Q
(1 ≤ N
, Q ≤ 100 000, 1 ≤ M
≤ N
), the number of cities, the number of days it takes to build the roads, and the number of
queries.

Each of the following Q lines contains two distinct positive integers A and B
(1 ≤ A
, B ≤ N
)
that denote the cities of the mathematicians who want to find out the minimal number of days
before they can play pictionary together.

outputFormat: The $i^{th}$ line must contain the minimal number of days before the mathematicians from the $i^{th}$ query can play pictionary together.

translation:
## 题目描述
在宇宙一个不为人知的地方，有一个星球，上面有一个国家，只有数学家居住。
在这个国家有$n$个数学家，有趣的是，每个数学家都住在自己的城市，且城市间无道路相连，因为他们可以在线交流。当然，城市有从$1$到$n$的编号。

一位数学家决定用手机发论文，而手机将“不言而喻”自动更正成了“猜谜游戏”。
不久之后，这个国家就发现了猜谜游戏。他们想要见面一起玩，于是这个国家就开始了修路工程。
道路修建会持续$m$天。对于第$i$天，若$\gcd(a,b)=m-i+1$，则$a$和$b$城市间会修一条路。

由于数学家们忙于建筑工作，请你来确定一对数学家最早什么时候能凑到一起玩。

## 输入输出格式
### 输入格式
第一行有三个正整数$n,m,q$，表示城市数量、修路持续天数、询问数量。
接下来$q$行，每行有两个正整数$a,b$，表示询问$a$和$b$两个城市的数学家最早什么时候能在一起玩。

### 输出格式
输出$q$行，第$i$行有一个正整数，表示第$i$次询问的结果

## 说明
**数据范围：**
对于$40\%$的数据：
$n≤4000,q≤10^5$
对于全部数据：
$1≤n,q≤10^5$
$1≤m≤n$

样例1解释：
在第一天，$(3,6)$之间修了一条路，因此第二次询问输出`1`
在第二天，$(2,4),(2,6),(2,8),(4,6),(6,8)$之间都修了一条路，此时$4$和$8$号城市连通，第三次询问输出`2`
在第三天，所有编号互质的城市之间都修了路，$2$和$5$号城市在此时连通，第一次询问输出`1`

样例2解释：
在第二天，$(20,15)$之间修了一条路
第四天，$(15,9)$之间修了一条路
所以$20$和$9$号城市在第四天连通，输出`4`

hint:
In test cases worth 40% of total points, it will hold N
≤ 1000, Q
≤ 100 000.

**Clarification of the first test case:**

On the first day, road (3, 6) is built. Therefore the answer to the second query is 1.

On the second day, roads (2, 4), (2, 6), (2, 8), (4, 6) and (6, 8) are built. Cities 4 and 8 are now
connected (it is possible to get from the first to the second using city 6).

On the third day, roads between relatively prime cities are built, so cities 2 and 5 are connected.

**Clarification of the second test case:**

On the second day, road (20, 15) is built, whereas on the fourth day, road (15, 9) is built. After the
fourth day, cities 20 and 9 are connected via city 15.


title: [COCI2017-2018#5] Planinarenje

description:
Mirko and Slavko like to hike together. Mirko likes mountain peaks, and Slavko likes valleys.
Because of this, every time they climb to a peak, Slavko decides which valley they are going
to descend to, given that a trail exists to it. Similarly, in each valley, Mirko decides which
peak they are going to climb up to. It will never be possible to directly climb from one peak to
another, or to get from one valley to another valley. In order to make the hiking as fun as
possible, they never visit the same spot twice (whether it’s a peak or a valley). Once they
reach a spot that only leads to spots they’ve visited before, they call the mountain rangers to
pick them up. If the final spot is a peak, Mirko wins, and if it is a valley, Slavko wins.

Naturally, you must already know what your task is: If we assume that both of them play
optimally, who wins? Answer this question for all initial peaks.

inputFormat:
The first line contains two positive integers, N and M (1 ≤ N ≤ 5000, 1 ≤ M ≤ min(5000, N
·N
)).
Here N denotes the number of peaks and valleys (therefore, there are N peaks and N
valleys), and M
denotes the number of hiking trails.

Each of the following M lines contains two positive integers: $v_i$ and $d_i$ (1 ≤ $v_i$ , $d_i$ ≤ N) that
denote there is a trail between peak $v_i$ and valley $d_i$.
Between each peak and valley, there will exist at most one trail.

outputFormat:
You must output N
lines. The $i^{th}$ line denotes the winner if the starting point is peak i
.

translation:
米尔科$(Mirko)$和斯拉夫科$(Slavko)$喜欢一起远足。米尔科喜欢山峰，斯拉夫科喜欢山谷。正因为如此，每当他们爬上一个山峰，若有连向山谷的路，则斯拉夫科就决定他们要去哪一个山谷。同样地，在每个山谷中，若有连向山峰的路，米尔科就决定他们将爬到哪一个山峰。不可能出现从一个山峰直接攀登到另一个山峰的情况，也不可能出现从一个山谷到另一个山谷的情况。为了使徒步旅行尽可能有趣，他们从不去同一地点两次（无论是一个山峰或一个山谷）。一旦他们到达一个地点，没有其它的地方可去，他们会叫登山者来接他们。如果最后一个点是一个山峰，则米尔科获胜，如果是一个山谷，则斯拉夫科获胜。

现在你的任务是，对于每一个山峰，如果他们从这里出发，并且都采用最优策略，谁会赢？

第一行两个正整数 $N,M$ $(1 ≤ N ≤ 5000, 1 ≤ M ≤ min(5000, N^2))$。$N$ 表示共有 $N$ 个山峰和 $N$ 个山谷。$M$ 表示共有 $M$ 条双向道路。

接下来 $M$ 行，每行两个正整数$v_i,d_i$ $(1 ≤ v_i,d_i≤ N)$ 表示第 $v_i$ 个山峰与第 $d_i$ 个山谷有路相连。

共 $N$ 行，每行一个字符串，第 $i$ 行表示从第 $i$ 个山峰出发的胜利者。

$30\%$的数据 $1 ≤ N≤ 10$

另有$20\%$的数据是森林。

hint:
In test cases worth 30% of total points, it will hold 1 ≤ N
≤ 10 and 1 ≤ M
≤ N
·N
.

In test cases worth an additional 20% of total points, for each two connected spots, there will
exist a unique path between them. In other words, the graph will be a forest.

**Clarification of the second test case:**

Starting from the first peak, Slavko can choose to go to the first valley, so Slavko wins.

Starting from the second peak, Slavko can choose to go to the second valley, after which Mirko wins
by choosing to go to the fourth peak.

Starting from the third peak, there are no trails, so Mirko wins.

Starting from the fourth peak, Slavko must choose to go to the second valley, after which Mirko wins
by choosing the second peak.


title: [SDOI2018] 物理实验

description:
小 T 这学期有物理实验课，为了顺利完成下一节课的实验，他打算在课前对实验内容进行预习。

这次实验在一个二维平面上进行，平面上放置了一条无限长的直线导轨，导轨上放置了一个长为$L$的激光发射器，激光发射器会向导轨两侧沿导轨垂直方向发射宽度为$L$的激光束。

平面上还放置了 $n$ 个挡板，每个挡板可以看作是一条线段，现在每个挡板都不和直线导轨接触，且
和直线导轨的夹角不超过 $85	\degree$，任意两个挡板也不会相互接触，激光束不能穿透这些挡板，并且会被挡板吸收掉，不会被挡板反射出去。

小 T 想确定一个激光发射器的位置使得被激光束照射到的挡板长度之和最大，你需要帮小 T 算出这
个最大值。

inputFormat:
第一行包含一个正整数 T，表示测试数据的组数。

对于每组测试数据，第一行是一个整数 $n$，表示挡板个数；
接下来 n 行，每行包含四个整数 $x1, y1, x2, y2$，表示挡板的两端点分别是 $(x1, y1)$ 和 $(x2, y2)$，保证$(x1, y1){=}\mathllap{/\,}(x2, y2)$。
第 $n + 2$ 行是五个整数 $x1, y1, x2, y2, L$，表示直线导轨经过了点 $(x1, y1)$ 和 $(x2, y2)$，且激光发射器的长度为 $L$，同样保证 $(x1, y1)\mathrlap{\,/}{=}(x2, y2)$。

outputFormat: 对于每组测试数据，输出一行，包含一个实数，表示激光束能照射到的挡板长度之和的最大值，要求相对误差不超过 $10^{-6}$，也就是说，令输出结果为 $a$，标准答案为 $b$，若满足 $\dfrac{|a-b|}{max(1,b)}$ $≤$ $10^{-6}$，则输出结果会被认为是正确答案。

hint:
- $T ≤ 100$
- $1 ≤ n ≤ 10^4$，
- $1 ≤ L ≤ 2 × 10^9$，
- 所有坐标的绝对值不超过 $10^9$。

## SubTasks

- 子任务 1 (40 分)：满足 $1 ≤ n ≤ 100$ 且所有坐标的绝对值不超过 $10^4$。
- 子任务 2 (40 分)：所有坐标的绝对值不超过 $10^6$。
- 子任务 3 (20 分)：没有任何附加的限制。


title: [SDOI2018] 战略游戏

description:
省选临近，放飞自我的小 Q 无心刷题，于是怂恿小 C 和他一起颓废，玩起了一款战略游戏。

这款战略游戏的地图由 $n$ 个城市以及 $m$ 条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到任意其他城市。

现在小 C 已经占领了其中至少两个城市，小 Q 可以摧毁一个小 C 没占领的城市，同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小 C 占领的城市 $u$ 和 $v$，使得从 $u$ 出发沿着道路无论如何都不能走到 $v$，那么小 Q 就能赢下这一局游戏。

小 Q 和小 C 一共进行了 $q$ 局游戏，每一局游戏会给出小 C 占领的城市集合 $S$，你需要帮小 Q 数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。

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

对于每组测试数据：

第一行是两个整数 $n$ 和 $m$ ，表示地图的城市数和道路数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v (1 \le u < v \le n)$，表示第 $u$ 个城市和第 $v$ 个城市之间有一条道路，同一对城市之间可能有多条道路连接。

第 $m + 1$ 是一个整数 $q$，表示游戏的局数，

接下来 $q$ 行，每行先给出一个整数 $|S| (2 \le |S| \le n)$，表示小 C 占领的城市数量，然后给出 $|S|$ 个整数 $(1 \le S_1 < S_2 < \cdots < S_{|S|} ≤ n)$，表示小 C 占领的城市。

outputFormat: 对于每一局游戏，输出一行，包含一个整数，表示这一局游戏中有多少个城市在小 Q 摧毁之后能够让他赢下这一局游戏。

hint:
- $1 \le T \le 10$；
- $2 \le n \le 10^5$ 且 $n - 1 \le m \le 2\times 10 ^ 5$；
- $1 \le q \le 10^5$；
- 对于每组测试数据，有 $\sum|S| \le 2 \times 10^5$。

### Subtasks

- 子任务 1 (30 分)：对于每组测试数据，满足 $\sum|S| \le 20$；
- 子任务 2 (45 分)：对于每一次询问，满足 $|S| = 2$；
- 子任务 3 (25 分)：没有任何附加的限制。


title: [SDOI2018] 反回文串

description:
“回文串什么的最讨厌了……”

小 $Q$ 讨厌任何形式的回文串：

- 如果一个字符串从左往右读和从右往左读是一样的，那么小 $Q$ 讨厌它；例如 $aa$ 和 $aba$。

- 对于一个字符串来说，若将某个前缀子串移除并拼接到字符串的尾部，能得到一个小 $Q$ 讨厌的字符串，那么小 $Q$ 也会讨厌原来的这个字符串；例如 $aab$ 和 $baa$。

那么问题来了，如果任意字符串只可以由 $k$ 种已知的字符组成，那么长度为 $n$ 的所有字符串里，有多少字符串是小 $Q$ 讨厌的？

答案可能很大，你只需要给出答案对 $p$ 取模的值。

inputFormat:
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来 $T$ 行，每行描述一组测试数据，包含三个正整数 $n, k$ 和 $p$。

outputFormat: 对于每组测试数据，输出一行，包含一个整数，表示答案对 $p$ 取模的值。


title: [WC2017] 挑战

background:
## 滥用本题评测将被封号。洛谷不保证此类毒瘤题的评测结果准确性。

你和同学们找了三道题目用来练习。

这次练习的目标是写出能在时间限制里通过尽量大规模数据的代码。

同学们纷纷写出了优秀的代码。现在，他们向你发起了挑战，他们对每个问题都设置了若干个测试数据，这是他们能通过的最大规模的测试数据。现在，他们想看一看你写的代码究竟能超过多少同学的代码，通过多大规模的测试数据。

本题分为 $3$ 个任务，每个任务对应一道题和相应的若干个测试点，你需要对于每个任务，设计一个能通过尽量多测试点的程序。

description:
## 任务一

给定 $n$ 个 $32$ 位无符号整数，将它们从小到大排序。

## 任务二

有 $2n$ 个人在玩 「石头剪刀布」 游戏。他们排成两排，每排 $n$ 个人。每个人在每一局游戏都使用固定策略，即对于第 $i (i \in 1, 2)$ 排的第 $j (0 \leq j < n)$ 个人，用一个整数 $a_{ij}$ 表示他的策略，其中 $0$ 表示只出石头，$1$ 表示只出剪刀，$2$ 表示只出布。

现在有 $q$ 个询问，每个询问给定三个整数 $x,y,l(0\leq x,y<n,1\leq l\leq n-max(x,y))$， 问将第一排的第 $x∼x+l-1$ 个人和第二排的第 $y∼y+l-1$ 个人比赛之后，第一排有多少个人会赢。

上文中 「比赛」 的意思是，对于所有整数 $i$ 满足 $0\leq i<l$,让第一排的第 $x+i$ 个人和 第二排的第 $y+i$ 个人进行 「石头剪刀布」 游戏。

## 任务三

我们称一个合法的括号串为：只由左括号和右括号构成，两种括号的数量相等， 且任意一个前缀的左括号数量不少于右括号数量的串。现在给定一个由 ```(```，```)``` 和```?``` 构成的串，问有多少种不同的方案，使得将每个 ```?``` 都替换成一个括号之后，该串变成一 个合法的括号串。两种方案不同，当且仅当至少有一个位置的 ```?``` 被替换成了不同的括号。

inputFormat:
此题提供了模板程序。选手可以在此基础上编写自己的程序，模板程序详见下文数据范围与提示。

第一行一个整数$ task\_id(1\leq task\_id\leq3)$，表示任务编号。接下来是每个具体任务的输入内容。

在输入的同一行中，相邻的两个整数会被一个空格隔开。

对于任务一：一行，两个整数 $n,s$。令 $a_0=next\_integer(s),a_i=next\_integer(a_{i-1}),1\leq i<n$，则 $a_0,a_1,…,a_{n-1}$ 即为需要排序的 $n$ 个整数。

对于任务二：第一行两个整数 $n,q$。第二行一个仅包含 $0, 1, 2$ 的长度为 $n$ 的字符串，第 $i$ 个字符所代表的整数表示第一排第 $i$ 个人的策略（即 $a_{1i}$）。第三行格式同第二行，表示第二排各个人的策略。

对于任务三：第一行一个整数 $n$，表示给定的串的长度。第二行一个字符串，即为给定的串。

outputFormat:
对于任务1：令 $b$ 为已经排好序的数组，调用 ```output_arr(b, n * 4)``` 即可。

对于任务2：将每个询问的答案依次存入 $32$ 位无符号整数数组 $b$ 中（即，存入 $b_0,b_1,⋯,b_{q-1}$ 中），然后调用 ```output_arr(b, q * 4)``` 即可。

对于任务3：输出一个整数，表示不同的方案数除以 $2^{32}$ 得到的余数。

hint:
## 数据范围与提示

| 任务编号 | 分值 | 测试点编号 | 数据范围与约定 | 时间限制 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| 1 | 5 | 1 | $n=100000$ | 3s |
| 1 | 19 | 2 | $n=10^8$ | 4s |
| 1 | 11 | 3 | $n=2\times10^8$ | 6s |
| 2 | 7 | 4 | $n=q=1000$ | 3s |
| 2 | 23 | 5 | $n=q=300000$ | 3s |
| 3 | 9 | 6 | $n=1000$ | 3s |
| 3 | 5 | 7 | $n=120000$ | 3s |
| 3 | 7 | 8 | $n=225000$ | 3s |
| 3 | 14 | 9 | $n=266666$ | 3s |

## 模板程序

### C++模板

```
#include <stdio.h>
#include <string.h>
#include <algorithm>

typedef unsigned int u32;
typedef unsigned long long u64;

inline u32 next_integer(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

bool output_arr(void *a, u32 size) {
    if (size % 4) {
        return puts("-1"), 0;
    }

    u32 blocks = size / 4;
    u32 *A = (u32 *)a;
    u32 ret = size;
    u32 x = 23333333;
    for (u32 i = 0; i < blocks; i++) {
        ret = ret ^ (A[i] + x);
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
    }

    return printf("%u\n", ret), 1;
}

// ===== header ======

namespace Sorting {
void init_data(u32 *a, int n, u32 seed) {
    for (int i = 0; i < n; i++) {
        seed = next_integer(seed);
        a[i] = seed;
    }
}

void main() {
    int n;
    u32 seed;
    scanf("%d%u", &n, &seed);

    u32 *a = new u32[n];
    init_data(a, n, seed);

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
}
}

namespace Game {
void main() {
    int n, q;
    scanf("%d%d", &n, &q);

    char *s1 = new char[n + 1];
    char *s2 = new char[n + 1];
    scanf("%s%s", s1, s2);

    u32 *anss = new u32[q];
    int *q_x = new int[q];
    int *q_y = new int[q];
    int *q_len = new int[q];

    for (int i = 0; i < q; i++) {
        scanf("%d%d%d", q_x + i, q_y + i, q_len + i);
    }

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
}
}

namespace Parentheses {
void main() {
    int n;
    scanf("%d", &n);

    char *s = new char[n + 1];
    scanf("%s", s);

    u32 ans;
    // ans = solve(n, s);

    printf("%u\n", ans);
}
}

int main() {
    int task_id;
    scanf("%d", &task_id);

    switch (task_id) {
        case 1:
            Sorting::main();
            break;
        case 2:
            Game::main();
            break;
        case 3:
            Parentheses::main();
            break;
    }

    return 0;
}
```

### C模板

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define bool int
#define true 1
#define false 0

typedef unsigned int u32;
typedef unsigned long long u64;

inline u32 next_integer(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

bool output_arr(void *a, u32 size) {
    if (size % 4) {
        return puts("-1"), 0;
    }

    u32 blocks = size / 4;
    u32 *A = (u32 *)a;
    u32 ret = size;
    u32 x = 23333333;
    u32 i;
    for (i = 0; i < blocks; i++) {
        ret = ret ^ (A[i] + x);
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
    }

    return printf("%u\n", ret), 1;
}

// ===== header ======

void Sorting_main() {
    int n;
    u32 seed;
    scanf("%d%u", &n, &seed);

    u32 *a = malloc(n * sizeof(u32));
    int i;
    for (i = 0; i < n; i++) {
        seed = next_integer(seed);
        a[i] = seed;
    }

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
}

void Game_main() {
    int n, q;
    scanf("%d%d", &n, &q);

    char *s1 = malloc((n + 1) * sizeof(char));
    char *s2 = malloc((n + 1) * sizeof(char));
    scanf("%s%s", s1, s2);

    u32 *anss = malloc(q * sizeof(u32));
    int *q_x = malloc(q * sizeof(int));
    int *q_y = malloc(q * sizeof(int));
    int *q_len = malloc(q * sizeof(int));

    int i;

    for (i = 0; i < q; i++) {
        scanf("%d%d%d", q_x + i, q_y + i, q_len + i);
    }

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
}

void Parentheses_main() {
    int n;
    scanf("%d", &n);

    char *s = malloc((n + 1) * sizeof(char));
    scanf("%s", s);

    u32 ans;
    // ans = solve(n, s);

    printf("%u\n", ans);
}

int main() {
    int task_id;
    scanf("%d", &task_id);

    switch (task_id) {
        case 1:
            Sorting_main();
            break;
        case 2:
            Game_main();
            break;
        case 3:
            Parentheses_main();
            break;
    }

    return 0;
}
```

### Pascal模板

```
type
    u32 = dword;
    u64 = qword;
    u32_p = ^u32;
    u64_p = ^u64;
    longint_p = ^longint;

function next_integer(x : u32) : u32; inline;
begin
    x := x xor (x << 13);
    x := x xor (x >> 17);
    x := x xor (x << 5);
    exit(x);
end;

function output_arr(a_in : pointer; size : u32) : boolean;
var
    blocks : u32;
    a, a_ed : u32_p;
    ret, x : u32;
begin
    if size mod 4 <> 0 then begin
        writeln(-1);
        exit(false);
    end;

    blocks := size div 4;
    ret := size;
    a := a_in;
    a_ed := a + blocks;
    x := 23333333;

    while a < a_ed do begin
        ret := ret xor (a[0] + x);
        x := x xor (x << 13);
        x := x xor (x >> 17);
        x := x xor (x << 5);
        inc(a);
    end;

    writeln(ret);
    exit(true);
end;

// ====== header ======

procedure init_data(a : u32_p; n : longint; seed : u32);
var
    a_ed : u32_p;
begin
    a_ed := a + n;
    while a < a_ed do begin
        seed := next_integer(seed);
        a[0] := seed;
        inc(a);
    end;
end;

procedure Sorting_main();
var
    n : longint;
    seed : u32;
    a : u32_p;
    i : u32;
begin
    read(n, seed);

    a := Getmem(n * sizeof(u32));
    init_data(a, n, seed);

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
end;

procedure Game_main();
var
    n, q : longint;
    s1, s2 : ansistring;
    anss : u32_p;
    q_x, q_y, q_len : longint_p;
    i : longint;
begin
    readln(n, q);
    readln(s1);
    readln(s2);

    anss := Getmem(q * sizeof(u32));
    q_x := Getmem(q * sizeof(longint));
    q_y := Getmem(q * sizeof(longint));
    q_len := Getmem(q * sizeof(longint));

    for i := 0 to q - 1 do begin
        read(q_x[i], q_y[i], q_len[i]);
    end;

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
end;

procedure Parentheses_main();
var
    n : longint;
    s : ansistring;
    ans : u32;
begin
    read(n);
    read(s);

    // ans := solve(n, s);

    writeln(ans);
end;

var
    task_id : longint;

begin
    read(task_id);

    if task_id = 1 then begin
        Sorting_main();
    end else if task_id = 2 then begin
        Game_main();
    end else if task_id = 3 then begin
        Parentheses_main();
    end;
    close(input); close(output);
end.
```


title: [COI2012] KAMPANJA

background: 临近选举，总统要在城市$1$和城市$2$举行演讲。他乘汽车完成巡回演讲，从$1$出发，途中要经过城市$2$，最后必须回到城市$1$.特勤局对总统要经过的所有城市监控。为了使得费用最小，必须使得监控的城市最少。求最少要监控的城市。

description:
一共有$N$个城市，有$M$条有向边。$(0<=N,M<=200)$
有N从1出发途中要经过$2$，最后要回到1的路线中最少要经过的点的数目。

inputFormat:
第一行包含$2$个整数$N,M$。$N$表示城市的数目，$M$表示有向边的数目。
接下来$M$行，每行两个数$A,B$，表示从$A$到$B$有一条有向边。

outputFormat: 最少要监控的城市的数量。

hint:
$0<=N,M<=200$

本题数据加强by Imagine


title: [COI2012] TRAMPOLIN

background: 有很多超级英雄：蝙蝠侠，蜘蛛侠，超人等。其中，有一位叫牛。今天他想模仿蜘蛛侠，所以他选择了一排高大的摩天楼来跳。

description:
具体而言，他选择了一个由 N 个摩天大楼构成的序
列，从左到右编号从 1 到 N.他最初位于第 K 座摩天大厦。不幸的是，这样的他的能力有限，所以只能向左或向右跳到相邻的摩天楼，只有那些摩天大楼的高度不大于他目前的摩天大楼
的高度的楼房才行。然而，他使蹦床上一些摩天大楼，从这些摩天大厦，他可以跳到任何其
他的摩天大楼，无论多么高以及位置在何处。
找出从第 K 座楼房开始，他能跳到的最多的不同的楼房数。如果一个楼房被多次访问，我
们只计算一次。楼房 K 也被计算在内，不管我们是否回到过楼房 K。

inputFormat:
第一行，包含两个数Ｎ和 K (3 ≤ N ≤ 300 000, 1 ≤ K ≤ N)，表示楼房总数和开始的楼
房。
第二行Ｎ个数，均小于 10^6，从左到右依次表示楼房的高度。
第三行Ｎ个字符'.' 或'T'.如果第 i 个字符是'T'，表示这里有一个蹦床在第 i 个楼房。

outputFormat: 一个数，有示最多能到的楼房数。


title: [COI2012] SETNJA

background: Mirko 要给朋友们送音乐会门票。

description:
朋友的家可表示为二维平面的网格。Mirko 在行走时，可以朝 $8$ 个方向移动，每次都是整数坐标。他每一步朝上、下、左、右以及 $4$ 个对角方向走一格。

每个朋友的家可表示为平面上的点 $(x,y)$。当 Mirko 到某朋友家送票时，朋友也可以走出来迎接他，也可以向 $8$ 个方向行走。因此，Mirko 和这个朋友最多可以在距离他家 $P$ 步远的位置相遇。$P$ 随每个朋友不同。

Mirko 的起始位置与终点位置都未知。

请求出 Mirko 送完所有票的最少移动步数。

inputFormat:
第一行一个整数，表示 Mirko 的朋友数 $N (2 ≤ N ≤ 200{,}000)$；

接下来 $N$ 行，每行 $3$ 个数，分别表示 $x,y,P\ (0 ≤ x, y, P ≤ 200{,}000)$。朋友按 Mirko 送票的顺序给出。

outputFormat: 共一行一个整数，表示 Mirko 必须走的最少移动步数。


title: [SDOI2018] 原题识别

background:
 - Input file: old.in
 - Output file: old.out
 - Time limit: 10 seconds
 - Memory limit: 512 megabytes

description:
“人肉题库” 小 $Q$ 刷题非常勤奋，题量破万。每当有人拿题目请教他时，小 $Q$ 总能在 $1$ 秒内报出这
是哪个 $OJ$ 的哪道题。因此，小 $Q$ 是被当作 “原题搜索机” 一样的存在。

有一天，小 $Q$ 来到了一棵 $n$ 个节点的有根树下，这棵树的根节点为 $1$ 号点，且每个节点都印着一道
题目。凭借超大的题量，小 $Q$ 迅速识别出了每道题的来源，并发现有些题目被搬运了好多次。他把每个
节点的题目都做了一个分类，第 $i$ 个节点的题目对应的题目种类为 $a_i$，当且仅当 $a_i=a_j$ 时，$i$ 点和 $j$ 点的题目来源是相同的。

同一道题目做多次除了增加 $AC$ 数以外，对本身的水平没有任何提高。为了调查这棵树的题目质量，
小 $Q$ 会不断提出以下两种询问共 $m$ 次：

- $1$ $x$ $y$：如果将 $x$ 点到 $y$ 点的最短路径上的所有点 (包括 $x$ 和 $y$) 对应的题目都做一遍，那么一共可
以做到多少道本质不同的题目？

- $2$ $A$ $B$：如果在 $A$ 点到根的最短路径上 (包括 $A$ 点和根) 等概率随机选择一个点 $x$，在 $B$ 点到根的最短路径上 (包括 $B$ 点和根) 等概率随机选择一个点 $y$，那么询问 $1$ $x$ $y$ 的答案期望是多少？

定义 $cnt_x$ 表示 $x$ 点到根最短路径上的节点个数，因为小 $Q$ 不喜欢分数，而且第 $2$ 类询问的答案一
定可以表示成$\frac{ans}{{cnt_A}*{cnt_B}}$的形式，你只需要告诉他 $ans$ 的值就可以了。

识别这些题目消耗了小 $Q$ 太大的精力，他没有办法自己去计算这些简单的询问的答案。请写一个程序回答小 $Q$ 的所有 $m$ 个问题。

inputFormat:
第一行包含一个正整数 $T$，表示测试数据的组数。
每组数据第一行包含 $5$ 个正整数 $n, p, SA, SB, SC$，其中 $n$ 表示树的节点个数。

为了在某种程度上减少输入量，树边和每个点的题目种类 $a[]$ 将由以下代码生成：
```
unsigned int SA, SB, SC;
unsigned int rng61(){
	SA ^= SA << 16;
	SA ^= SA >> 5;
	SA ^= SA << 1;
	unsigned int t = SA;
	SA = SB;
	SB = SC;
	SC ^= t ^ SA;
	return SC;
}
void gen(){
	scanf("%d%d%u%u%u", &n, &p, &SA, &SB, &SC);
	for(int i = 2; i <= p; i++)
	addedge(i - 1, i);
	for(int i = p + 1; i <= n; i++)
	addedge(rng61() % (i - 1) + 1, i);
	for(int i = 1; i <= n; i++)
	a[i] = rng61() % n + 1;
}
```
第二行包含一个正整数 $m$，表示询问次数。

接下来 $m$ 行，每行 $3$ 个正整数，形式为 $1$ $x$ $y$ 或者 $2$ $A$ $B$，依次表示每个询问。

outputFormat: 对于每组数据，输出 $m$ 行，每行一个整数，依次回答每个询问。


title: [SDOI2018] 旧试题

background:
 - Input file: divsum.in
 - Output file: divsum.out
 - Time limit: 5 seconds
 - Memory limit: 512 megabytes

 （注：此处文件输入输出为比赛时要求，在洛谷提交时采用标准输入输出即可。）

description:
时光匆匆，转眼间又是一年省选季……

这是小 $Q$ 同学第二次参加省队选拔赛。今年，小 $Q$ 痛定思痛，不再冒险偷取试题，而是通过练习旧试题提升个人实力。可是旧试题太多了，小 $Q$ 没日没夜地做题，却看不到前方的光明在哪里。

一天，因做题过度而疲惫入睡的小 $Q$ 梦到自己在考场上遇到了一道好像做过的题目，却怎么也想不起曾经自己是怎么解决它的，直到醒来还心有余悸。

小 $Q$ 眉头一皱，感觉事情不妙，于是他找到了你，希望你能教他解决这道题目。小 $Q$ 依稀记得题目要计算如下表达式的值。

$$
(\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}d(ijk))\bmod (10^9+7)
$$

其中 $d(ijk)$ 表示 $i × j × k$ 的约数个数。

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

接下来 $T$ 行，每行描述一组测试数据，包含三个整数 $A, B$ 和 $C$，含义见题目描述。

outputFormat: 对于每组测试数据，输出一行，包含一个整数，表示所求表达式的值。


title: [SDOI2018] 荣誉称号

background:
 - Input file: title.in
 - Output file: title.out
 - Time limit: 10 seconds
 - Memory limit: 512 megabytes

description:
休闲游戏玩家小 $Q$ 不仅在算法竞赛方面取得了优异的成绩，还在一款收集钻石的游戏中排名很高。

这款游戏一共有 $n$ 种不同类别的钻石，编号依次为 $1$ 到 $n$。小 $Q$ 已经玩了这款游戏很久了，对于第
$i$ 种钻石，他已经收集到了 $a_i$ 个。这款游戏最大的亮点就是，钻石只有一种获得途径，那就是从商城中购买。具体来说，第 $i$ 种钻石的单价为 $b_i$ 点券。为了鼓励玩家充值，每种钻石都没有数量上限，只要肯充钱，就可以拥有任意多的钻石。但是这款游戏并没有开发 “丢弃道具” 功能，因此小 $Q$ 不能通过丢弃钻石去完成任务。

最近这款游戏推出了一个限时成就任务，完成任务的玩家可以获得荣誉称号，而完成任务条件则是：
给定正整数 $k$ 和 $m$，对于任意一个整数 $x (x\ge 2^k)$，$a_{x}+a_{\lfloor\frac{x}{2}\rfloor}+a_{\lfloor\frac{x}{4}\rfloor}+a_{\lfloor\frac{x}{8}\rfloor}+...+a_{\lfloor\frac{x}{2^k}\rfloor}$ 都要是 $m$的倍数。

高玩小 $Q$ 当然想完成这个限时成就任务，但是在充钱之前他想知道他究竟需要多少点券才能完成这个任务。请写一个程序帮助小 $Q$ 计算最少需要的点券数量。

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

每组数据第一行包含 $9$ 个正整数 $n, k, m, p, SA, SB, SC, A, B$，其中 $n$ 表示钻石种类数，$k, m$ 表示任
务条件。

为了在某种程度上减少输入量，$a[]$ 和 $b[]$ 由以下代码生成：
```
unsigned int SA, SB, SC;int p, A, B;
unsigned int rng61(){
	SA ^= SA << 16;
	SA ^= SA >> 5;
	SA ^= SA << 1;
	unsigned int t = SA;
	SA = SB;
	SB = SC;
	SC ^= t ^ SA;
	return SC;
}
void gen(){
	scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);
	for(int i = 1; i <= p; i++)scanf("%d%d", &a[i], &b[i]);
	for(int i = p + 1; i <= n; i++){
		a[i] = rng61() % A + 1;
		b[i] = rng61() % B + 1;
	}
}
```

outputFormat: 对于每组数据，输出一行一个整数，即最少需要的点券数量。


title: [BJWC2008] 王之财宝

description:
《基尔伽美修》是人类历史上第一部英雄史诗，两河流域最杰出的文学作品之一。作品讲述了基尔伽美修一生的传奇故事。在动画Fate/stay night中，基尔伽美修与亚瑟王等传说中的英雄人物一起出现在了现实世界，展开了一场惊天地、泣鬼神的战斗。在记载于12块泥板的史诗中，基尔伽美修与同伴安吉杜一起降伏了森林的守护者——神兽洪芭芭，成为地上最强的王者，同时将世间所有财宝收归手中。王之财宝(Gate of Babylon)成为Fate中金皮卡（基尔伽美修的外号…）炫耀的资本……

一天金皮卡突发奇想：如果从自己无尽的财宝里面，随便抽不超过M件宝具出来砸死敌人的话。一共有多少种搭配方法呢？假设金皮卡一共有N种不同类型的宝具，大部分类型的宝具都有无限多，但其中T种超级神器的数量是有限的。设第i种超级神器的数量不超过$B_i$件。若相同类型的宝具数量相同，则认为是相同的搭配方案。

金皮卡知道方案数会很大，从小数学成绩就好的他挑选了一个质数P，请你帮他计算一下方案数模P后的余数。注意，一件也不选也是一种方案。

inputFormat:
第一行包含4个整数，分别为N，T，M，P

之后T行，每行一个整数，代表$B_i$

$N,M≤10^9$，$P≤10^5$，$B_i≤10^9$

$0≤T≤N$，$M>0$，$B_i>0$，$T≤15$

outputFormat: 仅包含一个整数，即方案数模P后的余数。

hint:
只有一种超级神器，数量不超过3

当不选择超级神器时，另一种宝具可以挑选0到10件，共11种方案

当选择1件神器出来时，另一种宝具可以挑选0到9件，共10种方案

当挑选2件神器时，共9种方案

挑选3件神器时，共8种方案

一共有11+10+9+8=38种方案，$38\bmod13=12$，于是答案等于12


title: [COCI2012-2013#6] BUREK

background: COCI

description:
给定 $N$ 个三角形，和 $M$ 条直线，直线要么平行于 $x$ 轴，要么平行于 $y$ 轴，问这 $M$ 条直线分别穿过多少个三角形。

**（一条直线穿过一个三角形，当且仅当这条直线可以将这个三角形分成两个面积均大于零的多边形）。**

inputFormat:
输入的第一行包含一个正整数 $N$，表示三角形的个数。

接下来 $N$ 行，每行三个坐标 $(x_1,y_1)$，$(x_2,y_2)$，$(x_3,y_3)$ 表示三个点，且这三点不共线，描述一个三角形。所有坐标均为非负整数，三角形可以重叠。

接下来一行包含一个正整数 $M$，表示直线的条数。

接下来 $M$ 行，每行一个字符串 `x = c` 或 `y = c`（注意等号两边的空格），描述一条直线。其中 `c` 为非负整数。

outputFormat: 对于每一条直线输出一个整数，表示它穿过的三角形的个数。


title: [COCI2012-2013#6] JEDAN

background: COCI

description:
有$N$个数排成一行(数值代表高度)，最初所有的数都为零，你可以选择连续的一段等高的数，将它们都增加$1$(除了开头和结尾那个数)如下图表示了两次操作:

![](https://cdn.luogu.com.cn/upload/pic/19412.png)

现在有一些数字看不清了，我们用$-1$表示，请你根据留下的数字，推出有多少
种可能的方案。使得留下的数字正好满足上面的操作方法。

inputFormat:
第一行一个正整数$N$表示数的个数。
接下来一行$N$个数，依次表示每一个数的大小，$-1$表示看不清楚，你可以用任
意满足条件的数代替。第$i$个数用$h_i$表示

outputFormat: 一个数，表示所有可能的方案对$1000000007$ 求余的值。


title: [COCI2012-2013#6] BAKTERIJE

description:
一个 $N$ 行，$M$ 列的矩形区域，行从上到下从 $1$ 到 $N$ 编号，列从左到右从 $1$ 到 $M$ 编号，有 $K$ 个细菌被放在这些单元格内，每个细菌都有自己的方向和运动规则。规则如下：读取自己在这个单元格的数字 $X$，顺时针转 $90^{\circ}$ $X$ 次，如果它面对矩形边界，则转 $180^{\circ}$，最后进入自己面向的单元格。我们放置一个陷阱在某一单元格，当所有细菌同时进入陷阱时，陷阱被激活，细菌会在一秒内被消灭。

给定所有信息，求什么时候所有细菌被消灭。

inputFormat:
第一行三个正整数 $N, M, K$。

接下来一行，两个数 $x, y$ 表示在 $x$ 行 $y$ 列处有一个陷阱。

接下来依次描述每一个细菌：
- 首先是一行两个数 $X,Y$ 和一个字母 $C$，分别表示行列坐标和它的方向，`U` 表示上，`D` 表示下，`L` 表示左，`R` 表示右。
- 接下来一个矩阵，表示这个细菌在这个每一个单元格上的$X$，$0\leq X\leq 9$。

outputFormat: 一行一个数，表示细菌被杀死的最后时间，如果无法全部消灭则输出 $-1$。

hint: $3\leq N\leq 50$，$3\leq M \leq 50$，$1\leq K\leq 5$。


title: 【模板】扩展中国剩余定理（EXCRT）

description:
给定 $n$ 组非负整数 $a_i, b_i$ ，求解关于 $x$ 的方程组的最小非负整数解。
$$\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}$$

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

接下来 $n$ 行，每行两个非负整数 $a_i, b_i$。

outputFormat: 输出一行，为满足条件的最小非负整数 $x$。

hint:
对于 $100 \%$ 的数据，$1 \le n \le {10}^5$，$1 \le b_i,a_i \le {10}^{12}$，保证所有 $a_i$ 的最小公倍数不超过 ${10}^{18}$。

**请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。**

数据保证有解。


title: [PA2017] Banany

description:
Bajtazar 是一名商人，他每天会从自己所在的城市出发，到另一个城市去贩卖香蕉。每条道路都会有一定的过路费，而作为终点的城市能获得一定收益（注意：途经点没有收益）。而每过一天，就会有一条道路的费用发生变化，或者某个城市的收益发生变化。Bajtazar 想知道当他每一天醒来后，以哪个城市作为终点获得的利润最大，而次日他会从该城市继续出发。

有 $n$ 个城市，由 $n - 1$ 条道路连接，且互相都能到达。第 $i$ 个城市有一个收益 $z_i$ ，每条边有一个费用 $w$ 。

如果从 $s$ 到 $t$ 做生意，获得的利润是

$$ z_t - \sum_{e \in \mathrm{Path}(s, t)} w(e) $$

一共有 $q$ 天。

最初 Bajtazar 在 $1$ 号城市。他每天经历了费用的变动后会前往下一个城市。他会选择获得利润最大的，如有多个相同则选择编号最小的，但他不能呆在原来的城市不走。

inputFormat:
第一行输入两个整数 $n$ ，$q$ 。

第二行输入 $n$ 个整数表示受益 $z_1,z_2,…,z_n$ 。

接下来 $n - 1$ 行输入边权与费用 $u\ v\ w$ 。

接下来 $q$ 行，有两种输入。

-    输入 $1\ i\ z_i$ 表示将原本 $i$ 城市的费用替换。
+    输入 $2\ u\ v\ w$ 表示将原本连接 $(u,v)$ 两城市的边上的费用替换。

outputFormat: 对于每行变化，总共输出 $q$ 组答案。表示经历变化之后， Bajtazar 的下一个目标。


title: [BJWC2008] 序列

description:
对一个长度为$N$的序列$\{a_n\}(a_i\in[0,2^{16}-1])$，进行如下两种，共计$M$个操作：

1. `A x`$(x\ge0)$：$a_i=a_i+x\mod2^{16}$

2. `Q i`：询问$Card\{k\mid(a_k\;\&\;2^i)>0,1\le k\le N,k\in\mathbb{Z}\}$的结果

其中$\&$运算符为相当于C/C++中的`&`或Pascal中的`and`

给定初始序列和操作序列，请你模拟操作过程，并计算所有$Q$操作的相应的结果的和。

inputFormat:
输入文件的第一行包含两个以空格分隔的整数，分别代表$N,M$

接下来的$N$行每行包含一个整数，代表初始序列

接下来的$M$行，每行描述一个操作，格式如题目中所述

outputFormat: 输出文件包含一个整数，表示所有$Q$操作的结果的和


title: [BJWC2008] 方程

description:
给定$3\times N$个正整数

$A_1,A_2...A_n$

$B_1,B_2...B_n$

$C_1,C_2...C_n$

另给定$M$对正整数$S_i,T_i$对于每一对$S_i,T_i$

求下列方程组的一组非负实数解

$A_1X_1+A_2X_2+...+A_nX_n=S_i$

$B_1X_1+B_2X_2+...+B_nX_n=T_i$

使得$C_1X_1+C_2X_2+...+C_nX_n$最大

inputFormat:
第一行两个整数代表$N,M$

接下来$N$行每行三个正整数$A_i,B_i,C_i$

$N\leq 10^5$, $M \leq 10^4$

$1\le A_i,B_i,C_i,S_i,T_i\le1000000$

outputFormat:
输出为$M$行，第$i$行代表$S_i,T_i$

如果方程无解输出`IMPOSSIBLE`

否则输出一个实数保留五位小数，代表对应的最大值。


title: [COCI2011-2012#5] RAZBIBRIGA

description:
四个长度相同的单词可以拼成一个正方形，如下图，`"HLAD","NIVA","HSIN","DEDA"` 拼成了一个 $4\times 4$ 的正方形。

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

现在给你 $N$ 个等长的单词，求这些单词的子集可以拼成多少个不同的正方形，输出方案数。

注意，**同一方格内不能有重复的单词**，如果两个单词至少有一个字符不同，那这两个单词就是不同的。

inputFormat:
第一行，一个整数 $N$，表示单词数。

接着 $N$ 行，每行一个单词，由大写字母组成，如题所示。

outputFormat:
一行，一个整数，表示方案数。

方案数可能很大，你需要开 `long long` 或 `int64`。

hint:
$4\le N\le 10^{5}$。

每个单词至多有 $10$ 个字符。

单词由大写字母构成。

题目译自 [COCI 2011/2012 #5 T4](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。


title: [COCI2011-2012#5] POPLOČAVANJE

background: 注意：本题相对于原题缩小了空间限制，需要一些小技巧才能通过。

description:
有一条由 $N$ 个英文小写字母组成的街道，市政府偶尔会更换街道上的瓷砖。但是，字母瓷砖的需求量很大，所以政府只有 $M$ 种字母瓷砖可供选择。

第 $i$ 个瓦片图案由 $L_{i}$ 个字母组成。瓷砖不能旋转，也不能打碎，而且只能放置在瓷砖字母与街道上连续的字母子序列重合的地方。

瓷砖可以重叠，且可以使用相同图案的多块瓷砖。如果一个街道不能被任何瓷砖覆盖，那么他就是不好的。

求有多少个不好的街道。

inputFormat:
第一行，一个整数 $N$，表示街道上的字母数。

第二行有 $N$ 个小写字母，表示街道上的序列，由小写字母组成。

第三行，一个整数 $M$，表示瓷砖数量。

接着 $M$ 行，每行 $L_{i}$ 个小写字母，表示该瓷砖的图案。

outputFormat: 一行，一个整数，表示方案数。

hint:
$1\le N\le 3\times 10^{5}$，$1\le M\le 5\times 10^{3}$，$1\le L_{i}\le 5\times 10^{3}$。

题目译自 [COCI 2011/2012 #5 T6](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。


title: [SHOI2009] 巴士路线

description:
OItown周围有n个小村庄。村庄与村庄之间有公路，每一条公路连接两个村庄。因为这些村庄并不富裕，所以，当初建公路时，这些公路只是恰好将这些村庄连通，也就是说任意从一个村庄沿着公路走到另一个村庄的方式都是唯一的。于是，有时两个很近的村庄之间要走很长的路。所以，村民们就希望能开通这些公路上的公共交通路线，方便大家的出行。

巴士运营公司采纳了这个意见。同时，巴士公司认为这些巴士线路必须满足下述条件：

1.每条巴士线路的起点和终点都在村庄内，巴士开行的线路都沿着公路；

2.每条公路都要有巴士线路覆盖，这样村民们的出行就只需要换成巴士车就行了；

3.每条公路只被一条巴士线路覆盖，且只被覆盖一次，否则巴士公司觉得在成本上不划算；

4.巴士线路的总数应当最少，这样才能方便管理。

例如，如果6个村庄之间的5条公路是这样的：

![](https://cdn.luogu.com.cn/upload/pic/19772.png)

那么这样的3条巴士线路就能满足上面的条件：1-2-3，2-4，5-4-6。

不过，居民们自然认为“巴士换乘”是不方便的，因此他们希望从一个村庄乘车去另一个村庄的路上换乘次数的最大值尽可能少。例如上面这个线路安排中，从村庄1到村庄6需要换成2次，是最大的换乘次数。

另一方面，巴士公司认为，一条公交线路越长意味着，一旦巴士车发生故障，受影响耽误时间的乘客就越多。所以巴士公司希望，最长的一条线路尽可能短。所谓短，就是途经的村庄少。

现在，这个巴士线路设计的任务交给了参加SHTSC的你，你当然要同时考虑上面两方面的因素，所以，你必须计算出：(1)换乘次数的最大值最小可能值(2)最长的线路途经村庄数的最小可能值。

inputFormat:
输入数据的第一行是一个整数n，表示村庄的数目。

接下去每行有两个整数x、y，分别描述一条公路，表示村庄x、y之间有一条公路。

输入文件保证，每条公路只会被描述一次。

outputFormat:
输出文件有三行：

第一行是一个整数，表示公交线路安排中包含的路线数。

第二行是一个整数，表示换乘次数的最大值的最小可能值。

第三行是一个整数，表示最长的线路途经村庄数的最小可能值。

hint:
如果你的输出的第一行与标准答案相等，你能得2分。

如果你的输出的第二行与标准答案相等，你能得4分。

如果你的输出的第三行与标准答案相等，你能得4分。

对于70%的数据：n<=300
对于100%的数据：n<=$10^5$


title: 一道水题 II

description:
一天，szb 在上学的路上遇到了灰太狼。

灰太狼：帮我们做出这道题就放了你。
szb：什么题？
灰太狼：求一个能被 $[1,n]$ 内所有数整除的最小数字，并对 $100000007$ 取模。
szb：这题太水了，就让我小弟来做好了。

然后你就光荣的接受了这个任务。

inputFormat: 一行一个数 $n$。

outputFormat: 一行一个数 $ans$。


title: [COCI2011-2012#5] BLOKOVI

description:
平面直角坐标系种有 $N$ 个质量为 $m_{i}$ ，长为 $2$，高为 $h$ 的矩形，使得：

* 矩形的边缘与坐标轴平行；
* 矩形的下层与 $y$坐标不重合，且为以下值：$0,h,2h,3h,\dots,(N-1)h$；
* 最低的矩形左下角的坐标为 $(-2,0)$，右下角与原点重合。

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

定义一个矩阵的 X 中心是其下边的中点的 X 坐标。一个或多个矩形的 X 中心是其 X 中心的加权平均值。它的计算方法为：

$$
Xbarycetre=\frac{\sum_{i}m_{i}\times Xcentre(i)}{\sum_{i}m_{i}}
$$

其中 `Xbarycetre` 表示一个或多个矩形的 X 中心，`Xcentre` 表示一个矩阵的 X 中心。

换句话说，其值为每个矩形的质量乘以它的 X 中心之积除以矩形的总质量。

对于每一个矩形，如果它**上面的矩形**的 X 中心与其的 X 中心的距离小于等于 $1$，则称这些矩形组成的排列是稳定的。

例如，左图的排列是不稳定的，因为上面两个矩形的 X 中心到下面的矩形的X中心的距离大于 $1$。而右图的排列是稳定的。

给出所有矩形的质量，求其可以组成的稳定排列中的矩形的最大 X 坐标。

你不能改变矩形的顺序，它们从**基本**低到高给出。

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

接着 $N$ 行，每行一个整数 $m_{i}$，表示第 $i$ 个矩形的质量。

outputFormat: 一行，一个小数，表示答案，答案在 $0.000001$ 的误差内均为正确。

hint:
有 $30\%$ 的数据，矩形的质量从大到小给出。

$2\le N\le 3\times 10^{5}$，$1\le m_{i}\le 10^{4}$。

题目译自 [COCI 2011/2012 #5 T5](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。


title: [SHOI2010] 滚动的正四面体

description:
正四面体总共有4个面，每个面都是一个正三角形。现在把它的一个面标记上字母A，如图 3中所示，A标记在底面上：

![](https://cdn.luogu.com.cn/upload/pic/19848.png)

一个正四面体的一次滚动显然有3个方向可以选择：向左（L）、向右（R）、向后（B）。如图 4所示：

![](https://cdn.luogu.com.cn/upload/pic/19850.png)

于是，这个正四面体的滚动过程就可以用一个只包含“L”“R”“B”的字符串来描述。

初始时，正四面体的A面朝下，现在SECSA将给这个正四面体一串滚动指令——当然就是一个这样的字符串——让这个正四面体每秒滚动一下。也就是说，第1秒内正四面体A面朝下，第1秒末执行第一条指令，第2秒末执行第2条指令，依次类推，直至将整个指令串执行完毕。

你的任务就是当SECSA询问你的时候告诉他：这个正四面体在第L秒到第R秒内A面有多少秒朝着地面。

当然，SECSA可能因为对这个正四面体的滚动路径不满意，他随时会修改他的某一条指令。因此你的程序应该能执行下面两个操作：

(1)接受SECSA修个第i条指令的信息

(2)回答SECSA的“在第L秒到第R秒内A面有多少秒朝着地面”的询问

例如，假如原指令串为“LLLLB”，那么第1、4、6秒内A面是朝下的。此时，如果SECSA向你询问第3秒到第6秒的情况，你就应该回答“2”。而SECSA将第3条指令修改为“R”的话，指令串就变成了“LLRLB”，那么正四面体就只有在第1、5秒内A面朝下了。如图 5所示：

![](https://cdn.luogu.com.cn/upload/pic/19851.png)

inputFormat:
输入文件的第一行是一个整数n，表示指令串中包含的指令条数。

输入文件的第二行是一个字符串，共包含n个字符，每个字符是“L”“R”“B”之一，表示初始的指令串。

输入文件的第三行是一个整数m，表示你的程序需要处理的操作总数。

接下去m行，每行描述一个操作，为以下两种格式之一：

(1)0 i c：表示把第i个操作改成c，c为“L”“R”“B”之一

(2)1 L R：表示询问第L秒到第R秒内，A面有多少秒朝下

输入文件保证：1<=i<=n，1<=L<=R<=n+1。

outputFormat: 输出文件对于每一个询问操作依次输出你的程序给出的回答，每个回答为一个整数，占一行。

hint:
第1个样例就是问题描述中的例子

在第2个样例中，按照原指令“LLLLBRRR”，则第1、4、6、9秒内A面向下；按照第一次修改后的指令“LRLLBRRR”，则只有第1秒内A面向下；按照第二次修改后的指令“LRLLBRBR”，则第1、9秒内A面向下。

1<=n<=60000

1<=m<=150000


title: [SHOI2010] 电脑网络

description:
SHOI 的领队为了方便大家交流，决定在大家集训的机房里建立起一个局域网络。现在的机房里一共有 $n$ 台电脑终端，SHOI 的领队使用了 $m$ 条网线去建立这个局域网，每条网线都把某两台电脑连接起来使得它们可以双向通信。现在这个网络是连通的，也就是说，任意两台电脑之间都可以直接的或间接的通信。

为了在整个备战过程中，确保所有学生之间通过这个电脑网络的交流，SHOI 的领队想要知道：“如果某台电脑 $\texttt{A}
$ 因故障关机的同时某一条网线 $\texttt{L}$（并非连接在 $\texttt{A}$ 上的）被切断，那么，除了 $\texttt{A}$ 以外的其他电脑能否保持相互通信？”

于是，SHOI 的领队需要你计算这个局域网络的“不稳定程度”。不稳定程度是指：通过从网络中移除一台电脑且切断一条网线（这条网线不连接在这台电脑上）使得整个网络中的其他电脑之间通讯不完全连通的不同方案的总数。

inputFormat:
输入文件的第一行有两个正整数 $n$、$m$，分别表示网络中的电脑终端的数量以及用来连接电脑的网线数量。

接下来 $m$ 行每行有两个整数 $x$、$y$ 来描述一条网线，表示这条网线连接了编号为 $x$、$y$ 的电脑，且 $x$ 不等于 $y$。

输入文件保证，这个电脑网络初始时是连通的。

outputFormat: 输出文件只有一行，这行只有一个整数，即为通过从网络中移除一台电脑且切断一条网线使得整个网络不连通的不同方案总数。

hint:
- $1 \leq n \leq 2 \times 10^3$；
- $1 \leq m \leq 2 \times 10^5$。


title: [SHOI2011] 改进代码

description:
 PP 写了两段对数组进行操作的代码。

对于 Pascal 选手，两段代码分别如下：

```
procedure operate1(l, r, c : longint);
var
    i : longint;
begin
    for i := l to r do
        a[i] := (a[i] + c) mod p;
end;

procedure operate2(l, r : longint);
var
    i, cnt : longint;
begin
    cnt := 0;
    for i := l to r - 1 do
        if a[i] > a[i + 1]
            then cnt := cnt + 1;
    writeln(cnt);
end;
```

对于 C / C++ 选手，两段代码分别如下：

```cpp
void operate1(int l, int r, int c)
{
    int i;
    for (i = l; i <= r; ++i)
        a[i] = (a[i] + c) % p;
}

void operate2(int l, int r)
{
    int i, cnt = 0;
    for (i = l; i < r; ++i)
        if (a[i] > a[i + 1])
            ++ cnt;
    printf("%d\n", cnt);
}
```

于是，主程序就可以通过调用这两个子程序对数组 $a_i$ 进行操作，下面是示例代码。

对于 Pascal 选手，代码如下：

```
begin
    operate1(1, 4, 3);
    operate1(4, 7, 4);
    operate2(1, 7);
end.
```

对于 C / C++ 选手，代码如下：

```
int main()
{
    operate1(1, 4, 3);
    operate1(4, 7, 4);
    operate2(1, 7);
}
```

但是 QQ 觉得 PP 的程序效率太低了，他想请你优化 PP 的代码。即，对于一段只包含 ``operate1`` 、 ``operate2`` 两种语句的主程序以及运行之前数组 $a_i$ 的初始值，请你计算出他的输出。

inputFormat:
输入的第一行包含 $3$ 个整数 $n,m,p$ 。其中 $n$ 是操作中 $l,r$ 的上界， $m$ 是主程序中的语句数， $p$ 是程序中的常数 $p$ 的值。

接下去 $n$ 行每行一个整数，依次是 $a_1,a_2,…,a_n$ 的初始化的值。输入保证这些值都在 $0,1,…,p-1$ 之中。

接下去 $m$ 行每行依次描述主程序的一行代码。每一行的格式为下面两者之一：

-    ``1 l r c`` : 表示代码 ``operate1(l, r, c);`` 。

-    ``2 l r`` : 表示代码 ``operate2(l, r);`` 。

outputFormat: 输出即为输入对应的程序的输出。


title: [SHOI2011] 直线拟合

description: 平面上有 $n$ 个点 $v_i(x_i,y_i)$ 。求 $D(l)=\max_{1\le i\le n} dis(v_i,l)$ 的最小可能值，其中变量 $l$ 是平面上的一条直线，函数 $dis(v_i,l)$ 表示直线 $l$ 与点 $v_i$ 之间的距离。

inputFormat: 输入的第一行为一个正整数 $n$ 。接下来 $n$ 行，每行一对整数 $x_i , y_i$ ，用一个空格分隔，依次表示这 $n$ 个点的坐标，其中 $|x_i|,|y_i| \le 10^8$ ，且不同的点不会重合。

outputFormat: 输出只有一行，包含一个实数，即 $D(l)$ 的最小值，四舍五入到小数点后两位。

hint:
**样例解释 1**

样例 $1$ 中， 取到最小值时的直线 $l$ 为 $y=1$ 。

**样例解释 2**

样例 $2$ 中的 $6$ 个点，以及 $D(l)$ 取到最小值时的直线 $l$ 如图所示。

![1](https://cdn.luogu.com.cn/upload/pic/20067.png)

**数据范围与提示**

测试点 $1$：$n=3$。

测试点 $2 \sim 4$：$3 \le n \le 100$。

测试点 $5 \sim 7$：$100 < n \le 100000$ ，且输入文件如下生成：选定一条线段，每次先在该线段上等概率随机选择一个点，再取离该点最近的整点。

测试点 $8 \sim 10$：$3 < n \le 100000$。


title: 文理分科

description:
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）

小 P 所在的班级要进行文理分科。他的班级可以用一个 $n\times m$ 的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：

- 如果第 $i$ 行第 $j$ 列的同学选择了文科，则他将获得 $art_{i,j}$ 的满意值，如果选择理科，将得到 $science_{i,j}$ 的满意值。

- 如果第 $i$ 行第 $j$ 列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加 $same\text{\underline{ }}art_{i,j}$ 的满意值。

- 如果第 $i$ 行第 $j$ 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 $same\text{\underline{ }}science_{i,j}$ 的满意值。

小 P 想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。

inputFormat:
输入第一行为两个正整数 $n,m$。
接下来 $n$ 行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $art_{i,j}$；
接下来 $n$ 行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $science_{i,j}$；
接下来 $n$ 行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $same\text{\underline{ }}art_{i,j}$；
接下来 $n$ 行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $same\text{\underline{ }}science_{i,j}$。

outputFormat: 输出为一个整数，表示最大的满意值之和。

hint:
### 样例说明

1 表示选择文科，0 表示选择理科，方案如下：

1  0  0  1

0  1  0  0

1  0  0  0

### 数据范围

$n,m\leq 100$，读入数据均 $\leq 500$。


title: 取石子

description:
现在 Yopilla 和 yww 要开始玩游戏！

他们在一条直线上标记了 $n$ 个点，从左往右依次标号为 $1, 2, ..., n$ 。然后在每个点上放置一些棋子，其中第 $i$ 个点放置了 $a_i$ 个棋子。接下来，从 Yopilla 开始操作，双方轮流操作，谁不能操作谁输。每次的操作是：当前操作方选定一个有棋子的点 $x$ ，然后选择至少一个点 $x$ 上的棋子，然后把这些棋子全都移动到点 $x / prime$ 上，其中 $prime$ 是一个质数，且 $prime \mid x$ 。

Yopilla 最初一次操作的策略是随机的：随机找到一个有棋子的点 $x$ ，随机选择正整数个棋子 $y$ ，随机转移到一个能转移到的点 $z$ 。所有棋子可以看作是一样的，换句话说：两种操作不同，当且仅当三元组 $(x, y, z)$ 不同。之后双方都按照最优策略来操作。

Yopilla 想要预测，他能够获胜的概率是多少，答案对 $998244353$ 取模。

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

第二行 $n$ 个数 $a_1, a_2, ..., a_n$ 。

outputFormat: 输出 $m$ 行，表示 Yopilla 能够获胜的概率对 $998244353$ 取模。

hint:
样例解释：

$1$ 号点有 $3$ 个棋子，$2$ 号点有 $1$ 个棋子，$3$ 号点有 $2$ 个棋子。第一次操作的时候，能进行的有三种可能：将 $2$ 号点的 $1$ 个棋子移到 $1$ 号点，将 $3$ 号点的 $1$ 个棋子移到 $1$ 号点，将 $3$ 号点的 $2$ 个棋子移到一号点。而其中只有一种情况能使得 Yopilla 有必胜策略。所以答案为
$$\frac{1}{3} \equiv 332748118 \pmod {998244353}$$

对于 $20 \%$ 的数据，只有一个石子。

对于 $100 \%$ 的数据，$1 \le n \le {10} ^ 6, 0 \le a_i \le {10} ^ 9$ ，保证至少有一个不在一号点的石子。


title: 重返现世

description:
为了打开返回现世的大门，Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 $n$ 种原料，只需要集齐任意 $k$ 种，就可以开始制作。

Yopilla 来到了迷失大陆的核心地域。每个单位时间，这片地域就会随机生成一种原料。每种原料被生成的概率是不同的，第 $i$ 种原料被生成的概率是 $\frac{p_i}{m}$ 。如果 Yopilla 没有这种原料，那么就可以进行收集。

Yopilla 急于知道，他收集到任意 $k$ 种原料的期望时间，答案对 $998244353$ 取模。

inputFormat:
第一行三个数 $n, k, m$ 。

第二行 $n$ 个数 $p_1, p_2, ..., p_n$ 。

outputFormat: 输出一行。


title: 画画

description:
yww 要开始画画了！

地上有一张纸，纸上有 $n$ 个点。

yww 要在结点之间连边。yww 的连边是非常有规律的。每次他会拿好笔，选定一个点，从这个点 $x$ 向其他点 $y$ 连边，再从 $y$ 向其他点 $z$ 连边，依次类推，直到连回点 $x$ 。yww 会进行若干次这样的连边。并且，自始至终，yww 都不会在两个结点之间连超过一条边。

yww 想知道，他一共能画出多少种本质不同的图。两个图本质相同，当且仅当存在一个点到点的置换，使得对于原图和在置换作用下的新图，任意两点之间要么都没有连边，要么都有连边。你只需要将答案对 $998244353$ 取模。

一句话题意，n 个点的无标号的每个连通块有欧拉回路的图的个数。

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

outputFormat: 输出一个数。


title: [语言月赛202302] 惊蛰

type: B

description:
给定一个正整数，规定一次操作为选定 $l,r$，删去所有从后往前数第 $l\sim r$ 位的数字，并且将剩下的数字组成一个新的正整数。如 $123456$ 删去从后往前数的第 $2\sim 3$ 位就会变成 $1236$。

现在有 $T$ 组询问，每次询问给定一个正整数 $n$，你需要回答：对于这个正整数，能否通过**最多一次操作**（不操作也算）将其变为 $4$ 的倍数。

但是请注意，不能把所有的数位全都删完。

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

输入的第一行，一个正整数 $T$。

接下来 $T$ 行，每行一个正整数 $n$。保证 $n$ 不包含前导零。

outputFormat:
输出共 $T$ 行。

对于 $T$ 组数据，每组数据需要输出 $1$ 行，表示问题的答案。若可以，输出 `Yes`，不可以，输出 `No`。

hint:
### 样例 1 解释

对第一组数据：删去从后往前数第 $2\sim 3$ 位，剩下的数是 $4$，是 $4$ 的倍数。

对第二组数据：可以证明没有任何一种方案能够达成目标。

对第三组数据：删去从后往前数第 $1$ 位，剩下的数是 $28$，是 $4$ 的倍数。

### 数据范围

对于前 $10\%$ 的数据，保证 $1\le n\le 9$。\
对于前 $30\%$ 的数据，保证 $1\le T\le 10,1\le n\le 100$。\
对于另外 $10\%$ 的数据，保证 $T=1$。\
对于前 $60\%$ 的数据，保证 $1\le T\le 10,1\le n\le 10^9$。\
对于 $100\%$ 的数据，$1\le T\le 10^2,1\le n\le 10^{18}$。


title: [USACO22DEC] Palindromes P

description:
农夫约翰合牛国（The United Cows of Farmer John，UCFJ）正在参加一年一度的蹄球锦标赛！UCFJ 队的 $N(1 \le N \le 7500)$ 头奶牛以微弱优势击败了 Farmer Nhoj 的队伍，赢得了蹄球比赛的金牌。

奶牛们已经为颁奖典礼排好了队。她们希望 FJ 拍摄 $\dfrac{N(N+1)}{2}$ 张合影，为队伍的每个连续子段拍摄一张。

然而，FJ，作为球队的主帅，对于奶牛们应该如何列队十分讲究。具体地说，他拒绝为一个子段拍照，除非它形成一个**回文串**，即对于所有不超过子段长度的正整数 $i$，从子段左端开始的第 $i$ 头奶牛的品种必须与从子段右端开始的第 $i$
头奶牛的品种相同。每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

对于队伍的 $\dfrac{N(N+1)}{2}$ 个连续子段的每一个，计算将该子段重新排列成回文串所需的最小换位次数（如果不可能这样做则为 $−1$）。单次换位是在子序列中取两头相邻的奶牛并交换。输出所有这些次数之和。

注意对每个连续子段所需的换位次数是独立计算的（奶牛们会在照片拍摄之间返回她们的起始位置）。

inputFormat: 输入队伍，用一个长为 $N$ 的字符 $\texttt{G}$ 和 $\texttt{H}$ 组成的字符串表示。

outputFormat: 输出队伍的所有 $\dfrac{N(N+1)}{2}$ 个连续子段的前述数量之和。

hint:
### 样例 1 解释

前四个连续子段是 $\texttt{G}$，$\texttt{GH}$，$\texttt{GHH}$ 和 $\texttt{GHHG}$。$\texttt{G}$ 和 $\texttt{GHHG}$ 都已经是回文串，因此它们对总和的贡献为 $0$。$\texttt{GHH}$ 可以使用一次换位重新排列成回文串，因此它对总和的贡献为 $1$。$\texttt{GH}$ 不能使用任意次数的换位重新排列成回文串，因此它对总和的贡献为 $−1$。

$\texttt{HHGG}$ 是另一个对总和有贡献的连续子段。这个子段可以使用两次换位重新排列成回文串。

### 测试点性质

除样例外有十五个测试点，满足 $N \in \{ 100,200,500,1000,2000,5000,5000,5000,5000,5000,7500,7500,7500,7500,7500\}$ 各一。


title: [USACO22DEC] Making Friends P

description: FJ 的 $N(2 \le N \le 2 \times 10^5)$ 头编号为 $1 \cdots N$ 的奶牛之中初始时有 $M(1 \le M \le 2 \times 10^5)$ 对朋友。奶牛们一头一头地离开农场去度假。第 $i$ 天，第 $i$ 头奶牛离开了农场，同时第 $i$ 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系？

inputFormat:
输入的第一行包含 $N$ 和 $M$。

以下 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 和 $v_i$ 是朋友（$1 \le u_i,v_i \le N,u_i \neq v_i$）。每个奶牛无序对至多出现一次。

outputFormat: 输出一行，包含形成的新的朋友关系的总数。不要计入初始时已经是朋友的奶牛对。


title: [SHOI2011] 扫雷机器人

description:
扫雷是陆军战场上一项重要的而危险的任务。为此， AL 军工厂专门研制了一种扫雷机器人。这种机器人是专门针对直线形雷阵设计的。所谓直线形雷阵，就是所有的地雷都埋在同一条直线上。例如图中黑点表示的雷阵就是直线形雷阵。

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

AL 军工厂生产的扫雷机器人的排雷方法只有一种，那就是安全引爆。每次，机器人在所有探测到的地雷中选择一颗引爆。被引爆的地雷会接连引爆不超过他的爆炸威力范围的其它地雷，这些被间接引爆的地雷还能引起进一步的连锁爆炸。例如图中，用一个圆的半径表示地雷的爆炸威力。如果引爆 $2$ 号雷， $1$ 、 $2$ 号雷都会爆炸；如果引爆 $3$ 号雷， $4$ 颗地雷全都会爆炸；而如果引爆 $4$ 号雷，那就只有它一颗爆炸。

虽然是机器人，但引爆也是危险的。所以，扫雷机器人的订购人希望机器人能在实战中采取引爆次数尽可能少的炸毁所有地雷的排雷方案。于是 AL 军工厂想就此方面对机器人进行测试。为了评估机器人的表现， AL 军工厂打算事先计算出：在一个直线形雷阵（即输入的雷阵）中，如果随机进行引爆，完成排雷工作所需要引爆次数的期望；并将这个值与机器人的实际排雷方案相比较，来评估他的表现。

所谓“随机进行引爆”是指，每次在所有没有被引爆的地雷中等概率的随机选择一个进行引爆。当这一次引爆引发的连环爆炸结束后，如果还有地雷没有被引爆，则重复上面的操作，直到所有地雷都被引爆为止。

inputFormat:
输入的第一行是一个正整数 $n$ ，表示地雷的个数。

接下去 $n$ 行，按照地雷的位置顺序，每行描述一颗地雷。其中，第 $i+1$ 行有两个整数 $x_i$ 和 $d_i$ ，分别是地雷的坐标和地雷的爆炸威力。也就是说，第 $i$ 号地雷的爆炸能直接进一步引爆第 $j$ 号地雷的条件是 $|x_i-x_j| \le d$ 。 输入保证： $|x_i| \le 10^8$ ， $1 \le d_i \le 10^8$ 。

outputFormat: 输出只有一行，包含一个实数，即为答案。四舍五入到小数点后四位。

hint:
**提示**

本题的试题目录下有 $10$ 个额外的输入样例文件 ``robot20111.in~robot201110.in`` ，以及它们对应的输出样例文件 ``robot20111.out~robot201110.out`` 。这些数据符合本题中关于数据规模的全部约定，但它们不是最终的测试数据。

**[下载地址](https://pan.baidu.com/s/1Q5X52FMH38UYvmrEsVsEkA)**，密码：ypbv。

**评分方式**

在每个测试点，如果您的输出是 $YourAns$ ，而标准答案是 $StdAns$ ，那么：

-    当 $ |YourAns-StdAns| \le 0.0001$ 时，该测试点得 $10$ 分。

-    当 $0.01 \ge |YourAns-StdAns| > 0.0001$ 时，该测试点得 $6$ 分。

-    当 $0.5 \ge |YourAns-StdAns| > 0.01$ 时，该测试点得 $2$ 分。

-    否则得 $0$ 分。

**数据范围**

测试点 $1$：$n \le 20$。

测试点 $2$：$n \le 200$ ，且任意方案都保证引爆次数不超过 $20$。

测试点 $3$：$n \le 200$。

测试点 $4 \sim 5$：$n \le 4000$ ，且任意方案都保证引爆次数不超过 $20$。

测试点 $6 \sim 10$：$n \le 4000$。


title: [SHOI2011] 银行家

description:
你在一家银行工作，任务是帮助客户取出他们存放在保险箱里的金币。

银行里有 $m$ 个保险箱，你没有办法打开这些保险箱，因为钥匙都在客户的手里。一个客户可能有很多个保险箱的钥匙，一个保险箱的钥匙也可能被多个客户拥有。今天早上，经理已经告知，你需要按照顺序接待 $n$ 个客户（任何客户都不会同时到场），你也知道，第 $i$ 个客户会要求取走 $c_i$ 枚金币。每个客户来到银行的时候，会打开所有他能打开的保险箱，然后从中取走 $c_i$ 枚金币（任何金币都没有区别），如果这些保险箱里的金币数量不足 ，他会感到不高兴，在取走尽量多的金币之后，到你的经理那里去投诉你们银行的服务质量太差了。

你当然不希望“上帝”的投诉让你丢了工作，于是想到了个补救的办法：虽然每个客户走的时候都会把保险箱重新关上，但是你可以在他取金币的时候，偷偷地调整被打开的保险箱里的金币数量，譬如说把 $1$ 号保险里多余的 $5$ 枚放到 $2$ 号里，这样说不定下个客户来的时候，就能取到更多的金币了。

尽管有这样的方法，还是可能没法完成所有客户的要求。然而，你希望，尽量帮助客户取走更多的金币，这样才能消除他们的怒气，保住这份来之不易的工作和薪水。

inputFormat:
第一行有两个正整数： $m$ 和 $n$ ， $m$ 表示保险柜的数量， $n$ 表示客户的数量。

第二行有 $m$ 个非负正数，表示银行在开始营业前，第 $1$ 号保险柜到第 $m$ 号保险柜的金币数量。 接下来有 $n$ 行，按照前来银行的顺序，依次描述了每个客户的情况。每行的开始都是一个非负整数 $k$ ，接着有 $k$ 个 $1$ 到 $m$ 之间的整数 $a_1,a_2,…,a_k$ ，表示这个客户拥有 $a_1$ 号、 $a_2$ 号，直到 $a_k$ 号保险箱的钥匙。最后还有一个非负整数 $c_i$ ，表示他需要的金币数量。 输入保证所有出现在输入数据中的整数都不超过 $10000$ 。

outputFormat:
输出只需要一个整数，表示所有客户可以取走的金币总数的最大值。
输入保证答案不会超过 $100000$ 。


title: [APIO2018] 新家

background: **警告！滥用本题者封号！请勿多次重复提交！**

description:
五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 $n$个商店出现。第 $i$个商店可以使用四个整数 $x_i, t_i, a_i, b_i$描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 $q$个询问，每个询问用二元组 （坐标，时间）表示。第 $i$对二元组用两个整数 $l_i, y_i$描述，分别表示选择的地点 $l_i$和年份 $y_i$。

现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离居住点最远的商店类型到居住点的距离。类型 $t$的商店到居住点的距离定义为：在指定的年份，类型 $t$的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 $i$的商店在第 $y$年在营业当且仅当 $a_i ≤ y ≤ b_i$ 。注意，在某些年份中，可能在五福街上并非所有 $k$种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 $-1$。

你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。

inputFormat:
第一行包含三个整数 $n, k$和 $q$ ，分别表示商店的数量、商店类型的数量和（坐标，时间）二元组的数量。$(1 \leq n, q \leq 3×10^5, 1 ≤ k ≤ n)$。

接下来 $n$行，每行包含四个整数 $x_i, t_i, a_i$ 和 $b_i$用于描述一家商店，意义如题面所述$(1 ≤ x_i, a_i, b_i ≤ 10^8, 1 ≤ t_i ≤ k, a_i ≤ b_i)$。

接下来 $q$行，每行包含两个整数 $l_i$和 $y_i$ ，表示一组（坐标，时间）查询$(1 ≤ l_i, y_i ≤ 10^8)$。

outputFormat: 输出一行，包含 $q$个整数，依次表示对于 $q$组（坐标，时间）询问求出的结果。

hint:
**提示**

在第一个样例中，有 4 家商店，共 2 种类型，还有 4 个询问。

- 对于第一个询问：小明在第 3 年住在坐标为 5 的地方。这一年中，编号为 1 和 2 的商店在营业，到编号为 1 的商店的距离为 2 ，到编号为 2 的商店距离为 4 ，所以最大距离为$4$。
- 对于第二个询问：小明在第 6 年住在坐标为 5 的地方。这一年中，编号为 1 和 3 的商店在营业，到编号为 1 的商店的距离为 2 ，到编号为 3 的商店距离为 2 ，所以最大距离为$2$。
- 对于第三个询问：小明在第 9 年住在坐标为 5 的地方。这一年中，编号为 1 和 4 的商店在营业，它们的类型都为 1，没有类型为 2 的商店在营业，所以答案为 $-1$。
- 同样的情况出现在第四个询问中。

在第二个样例中，有 2 家商店，共 1 种类型，还有三个询问。 两家商店的类型都是 1 。在所有的询问中，小明均住在坐标为 1 的地方。 在前两个询问中，至少有一个商店在营业，所以答案为 $0$ ，在第三个询问中，两个商店都不在营业，所以答案为 $-1$ 。

在第三个样例中，有 1 家商店和 1 个询问，两者之间的距离是 $99999999$ 。

**子任务（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）**

- Subtask 1(points: $5$): $n, q \leq 400$
- Subtask 2(points: $7$): $n, q \leq 6 × 10^4, k \leq 400$
- Subtask 3(points: $10$): $n, q \leq 3 × 10^5$，对于所有的商店 $a_i = 1, b_i = 10^8$
- Subtask 4(points: $23$): $n, q \leq 3 × 10^5$，对于所有的商店 $a_i = 1$
- Subtask 5(points: $35$): $n, q \leq 6 × 10^4$
- Subtask 6(points: $20$): $n, q \leq 3 × 10^5$


title: [APIO2018] 选圆圈

description:
在平面上，有 $n$ 个圆，记为 $c_1, c_2,...,c_n$ 。我们尝试对这些圆运行这个算法：

1. 找到这些圆中半径最大的。如果有多个半径最大的圆，选择编号最小的。记为 $c_i$。
2. 删除 $c_i$ 及与其有交集的所有圆。两个圆有交集当且仅当平面上存在一个点，这个点同时在这两个圆的圆周上或圆内。（原文直译：如果平面上存在一个点被这两个圆所包含，我们称这两个圆有交集。一个点被一个圆包含，当且仅当它位于圆内或圆周上。）
3. 重复上面两个步骤直到所有的圆都被删除。

![QQ20180525194902.png](https://cdn.luogu.com.cn/upload/pic/19974.png)

当 $c_i$ 被删除时，若循环中第 $1$ 步选择的圆是 $c_j$，我们说 $c_i$ 被 $c_j$ 删除。对于每个圆，求出它是被哪一个圆删除的。

inputFormat:
第一行包含一个整数 $n$，表示开始时平面上圆的数量。

接下来 $n$ 行，每行包含三个整数 $x_i, y_i, r_i$ 依次描述圆 $c_i$ 圆心的 $x$ 坐标、$y$ 坐标和它的半径。

outputFormat: 输出一行，包含 $n$ 个整数 $a_1, a_2, ..., a_n$，其中 $a_i$ 表示圆 $c_i$ 是被圆 $c_{a_i}$ 删除的。

hint:
**提示**

题目描述中的图片对应了样例一中的情形。

**子任务（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）**

- Subtask 1(points: $7$): $n \leq 5000$
- Subtask 2(points: $12$): $n \leq 3 × 10^5$，对于所有的圆 $y_i = 0$
- Subtask 3(points: $15$): $n \leq 3 × 10^5$，每个圆最多和一个其他圆有交集
- Subtask 4(points: $23$): $n \leq 3 × 10^5$，所有的圆半径相同
- Subtask 5(points: $30$): $n \leq 10^5$
- Subtask 6(points: $13$): $n \leq 3 × 10^5$

所有数据均满足：$-10^9 ≤ x_i, y_i ≤ 10^9, 1 ≤ r_i ≤ 10^9$。


title: [APIO2018] 铁人两项

description:
比特镇的路网由 $m$ 条双向道路连接的 $n$ 个交叉路口组成。

最近，比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程：选手先完成一段长跑赛程，然后骑自行车完成第二段赛程。

比赛的路线要按照如下方法规划：

1. 先选择三个两两互不相同的路口 $s$、$c$ 和 $f$，分别作为比赛的起点、切换点（运动员在长跑到达这个点后，骑自行车前往终点）、终点。
2. 选择一条从 $s$ 出发，经过 $c$ 最终到达 $f$ 的路径。考虑到安全因素，选择的路径经过同一个点至多一次。

在规划路径之前，镇长想请你帮忙计算，总共有多少种不同的选取 $s$、$c$ 和 $f$ 的方案，使得在第 $2$ 步中至少能设计出一条满足要求的路径。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，分别表示交叉路口和双向道路的数量。

接下来 $m$ 行，每行两个整数 $v_i, u_i$。表示存在一条双向道路连接交叉路口 $v_i, u_i$（$1 \le v_i, u_i \le n$，$v_i \neq u_i$）。

保证任意两个交叉路口之间，至多被一条双向道路直接连接。

outputFormat: 输出一行，包括一个整数，表示能满足要求的不同的选取 $s$、$c$ 和 $f$ 的方案数。

hint:
**提示**

在第一个样例中，有以下 $8$ 种不同的选择 $(s, c, f)$ 的方案：

- $(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (3, 2, 1)$；
- $(4, 2, 1), (4, 3, 1), (4, 3, 2)$。

在第二个样例中，有以下 $14$ 种不同的选择 $(s, c, f)$ 的方案：

- $(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 4, 3), (2, 3, 4)$；
- $(2, 4, 3), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2)$；
- $(4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)$。

**子任务（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）**

- Subtask 1（points: $5$）：$n \leq 10$，$m \leq 100$。
- Subtask 2（points: $11$）：$n \leq 50$，$m \leq 100$。
- Subtask 3（points: $8$）：$n \leq 100000$，每个交叉路口至多作为两条双向道路的端点。
- Subtask 4（points: $10$）：$n \leq 1000$，在路网中不存在环（存在环是指存在一个长度为 $k$（$k \ge 3$）的交叉路口序列 $v_1, v_2, \ldots, v_k$，序列中的路口编号两两不同，且对于 $i$ 从 $1$ 到 $k - 1$，有一条双向道路直接连接路口 $v_i$ 和 $v_{i+1}$，且有一条双向道路直接连接路口 $v_k$ 和 $v_1$）。
- Subtask 5（points: $13$）：$n \leq 100000$，在路网中不存在环。
- Subtask 6（points: $15$）：$n \leq 1000$，对于每个交叉路口，至多被一个环包含。
- Subtask 7（points: $20$）：$n \leq 100000$，对于每个交叉路口，至多被一个环包含。
- Subtask 8（points: $8$）：$n \leq 1000$，$m \leq 2000$。
- Subtask 9（points: $10$）：$n \leq 100000$，$m \leq 200000$。


title: [POI2004] WYS

background: 虽然题目名比较毒瘤，但这确实是一个简单题。

description: 给 $n$ 个互不相交的多边形，这些多边形的边均平行或垂直于坐标轴。定义多边形 $i$ 的深度 $d_i$ 为 $\max\{d_j\}+1$，其中多边形 $j$ 包含多边形 $i$。特别的，若一个多边形不被任何多边形包含，则其深度为 $1$。求深度最大的多边形的深度。

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

接下来每行描述一个多边形。首先给出一个偶数 $k$ $(4 \leqslant k \leqslant 10000)$，接下来包含 $k$ 个整数: $x_1,x_2,\cdots,x_k$ $(0 \leqslant x_i \leqslant 10^8)$。这些点的坐标分别为 $(x_1, x_2), (x_3, x2), (x_3, x4), (x_5, x_4),\cdots,(x_{k-1}, x_k), (x_1, x_k)$。他们按照逆时针顺序构成多边形。

outputFormat: 输出一个整数表示最大深度。

hint: 对于 $100\%$ 的数据，$n \leqslant 40000, \sum k \leqslant 200000$。


title: [SHOI2011] 编译优化

description:
就像 PASCAL 语言和 C/C++ 语言一样， SH 语言也是一种编程语言。 SH 语言共有 $26$ 个寄存器，用大写拉丁字母 A, B, … , Z 表示。 SH 语言的程序中，第一行依次是这 $26$ 个寄存器的初始值，用空格分隔。程序的第二行起，每一行都是一条命令。 SH 语言有三种命令，如下表所示（在格式这一列中，用下划线代替实际语言中的一个空格）。

-    ``ADD``命令 格式：``ADD_R1_R2``  功能：将寄存器 R2 的值加到寄存器 R1 上。 限制：无。

-    ``GOTO`` 命令 格式：``IF _R_ < _I1_ GOTO _LINE_ I2`` 功能：如果寄存器 R 的值小于立即数 I1 ，则跳转至第 I2 （ $\ge 2$ ）行，否则继续执行下一行。限制：至多出现一次，且只可能出现在第 I2 行之后。

-    ``PRINT`` 命令 格式：``PRINT_R`` 功能：打印寄存器 R 的值。限制：出现且仅出现在最后一行。

现给定一个 SH 语言的程序，请输出 ``PRINT`` 命令打印的值。

inputFormat: 每个输入文件都是一个 SH 语言的程序。输入文件保证：所有寄存器的初始值以及 ``GOTO`` 命令中出现的立即数，均为不超过 $2^{63}-1$ 的非负整数，但程序执行过程中寄存器的值不限于此。

outputFormat: 每个输出文件只有一行，包含一个整数，即 ``PRINT`` 命令所打印的值。

hint:
在每个测试点，如果您的输出与标准答案完全一致，您将能得到该测试点的全部分数；否则，您将在该测试点得 $0$ 分。

本题为提交答案题，所有的 $10$ 个输入文件 ``compiler1.in ~ compiler10.in`` 都已存放在题目背景的下载链接中。对于每个输入文件，您需要分别给出相应的输出文件 ``compiler1.out ~ compiler10.out``。

注意：您只需提交输出文件而无需提交任何程序。


title: [COCI2017-2018#5] Karte

description:
有$N$ 张牌叠在一起，第 $i$ 张牌上，有一个数字 $a_i$ 表示它下面**至少**有 $a_i$ 张牌上的信息是错误的，若它下面确实有至少 $a_i$ 张牌的信息是错误的，那这张牌的信息就是正确的，否则这张牌的信息就是错误的。（我们认为最下面的牌的后面有 $0$ 张错误的）

现在需要你重新调整牌的顺序，使得正好有 $K$ 张牌上的信息是错误的。

inputFormat:
第一行两个正整数 $N$ 和 $K$ $( 1 ≤ N≤ 5×10^5,0 ≤ K≤ N )$表示牌的张数和要求的错误信息的个数。
接下来 $N$ 行，每行一个数，表示对应的 $a_i$ $(0 ≤ a_i≤ 5×10^5 )$

outputFormat: 如果调整方案不存在，输出$-1$。否则输出由顶部到底部 $N$ 张牌对应的 $a_i$，若有多种方案，输出任意一种即可。

hint:
$30\%$的数据 $N≤ 16$。

另有$40\%$的数据 $N≤ 2000$。

**样例 2 说明：**

第 $5$ 张牌上写的是$2$，但是其后面只有 $0$ 张错误，所以它是错误的。

第 $4$ 张牌上写的是$1$，其后面有 $1$ 张错误（第五张），所以它是正确的。

第 $3$ 张牌上写的是$0$，其后面有 $1$ 张错误（第五张），所以它是正确的。

第 $2$ 张牌上写的是$3$，但是其后面只有 $1$ 张错误（第五张），所以它是错误的。

第 $1$ 张牌上写的是$3$，但是其后面只有 $2$ 张错误（第五张，第二张），所以它是错误的。

因此总共有 $3$ 张是错误的。


title: [CEOI2017] One-Way Streets

description:
给定一张 $n$ 个点 $m$ 条边的无向图，现在想要把这张图定向。

有 $p$ 个限制条件，每个条件形如 $(x_i,y_i)$，表示在新的有向图当中，$x_i$ 要能够沿着一些边走到 $y_i$。

现在请你求出，每条边的方向是否能够唯一确定。同时请给出这些能够唯一确定的边的方向。

数据保证有解。

inputFormat:
第一行两个空格隔开的正整数 $n,m$ 。

接下来 $m$ 行，每行两个空格隔开的正整数 $a_i,b_i$，表示 $a_i,b_i$ 之间有一条边。

接下来一行一个整数 $p$，表示限制条件的个数。

接下来 $p$ 行，每行两个空格隔开的正整数 $x_i,y_i$，描述一个 $(x_i,y_i)$ 的限制条件。

outputFormat:
输出一行一个长度为 $m$ 的字符串，表示每条边的答案：

-    若第 $i$ 条边必须得要是 $a_i$ 指向 $b_i$ 的，那么这个字符串的第 $i$ 个字符应当为 ``R``；

-    若第 $i$ 条边必须得要是 $b_i$ 指向 $a_i$ 的，那么这个字符串的第 $i$ 个字符应当为 ``L``；

-    否则，若第 $i$ 条边的方向无法唯一确定，那么这个字符串的第 $i$ 个字符应当为 ``B``。

hint: 对于所有测试点，有 $1\le n,m,p\le 100\ 000;1\le a_i,b_i,x_i,y_i\le n$。


title: [CEOI2017] Sure Bet

description:
现在有 $n$ 个A类灯泡和 $n$ 个B类灯泡，每个灯泡都有各自的权值。

我们将这些灯泡分为 $n$ 组，每组包含一个来自A类的灯泡和一个来自B类的灯泡。

你可以从中选取任意个灯泡，每选取一个灯泡需要花费 $1$ 的代价。

在你选取完之后，系统会随机在A类和B类中选择一个类型，并点亮那一类的所有灯泡。你选取的每个点亮的灯泡会给你带来等于它权值的收益。

现在请你合理选取灯泡，以最大化可能的最小收益。你只需要求出来这个收益即可。

inputFormat:
第一行一个正整数 $n$ ，表示灯泡的组数。

接下来 $n$ 行每行两个空格隔开的实数 $A_i,B_i$。分别表示属于这组的A灯泡和B灯泡的权值。输入的实数不会超过四位小数。

outputFormat: 输出最大化的最小可能收益，请输出到小数点后恰好四位。

hint:
**样例解释**

最优策略是选择第一组的B灯泡和第三组的A灯泡和第四组的A灯泡：

-    如果B类灯泡被点亮，收益是 $3.7-3=0.7$。
-    如果A类灯泡被点亮，收益是 $1.6+1.9-3=0.5$ 。

最小可能收益是 $0.5$。

**数据范围**

对于所有测试点，有 $1.0\le A_i,B_i\le 1000.0$，$0\le n\le 10^5$。


title: [CEOI2017] Mousetrap

description:
有一个有 $n$ 个房间和 $n-1$ 条走廊的迷宫，保证任意两个房间可以通过走廊互相到达，换句话说，这个迷宫的结构是一棵树。

一个老鼠被放进了迷宫，迷宫的管理者决定和老鼠做个游戏。

一开始，有一个房间被放置了陷阱，老鼠出现在另一个房间。老鼠可以通过走廊到达别的房间，但是会弄脏它经过的走廊。老鼠不愿意通过脏的走廊。

每个时刻，管理者可以进行一次操作：堵住一条走廊使得老鼠不能通过，或者擦干净一条走廊使得老鼠可以通过。然后老鼠会通过一条干净的并且没被堵住的走廊到达另一个房间。只有在没有这样的走廊的情况下，老鼠才不会动。一开始所有走廊都是干净的。管理者不能疏通已经被堵住的走廊。

现在管理者希望通过尽量少的操作将老鼠赶到有陷阱的房间，而老鼠则希望管理者的操作数尽量多。请计算双方都采取最优策略的情况下管理者需要的操作数量。

注意：管理者可以选择在一些时刻不操作。

inputFormat:
第一行三个空格隔开的正整数数 $n,t,m$。分别代表房间的个数，陷阱房的编号和老鼠起始房间的编号。

接下来 $n-1$ 行，每行两个空格隔开的整数 $a_i,b_i$，表示有一条走廊连接编号为 $a_i$ 和 $b_i$ 的房间。

outputFormat: 输出一行包含一个整数，表示双方都采取最优策略的情况下，管理者需要的操作数量。

hint:
**样例解释**

-    管理者先堵住房间 $4$ 和 $7$ 之间的走廊。
-    老鼠走到房间 $6$。房间 $4$ 和 $6$ 之间的走廊现在是脏的。
-    管理者堵住房间 $6$ 和 $8$ 之间的走廊。
-    老鼠不能动。
-    管理者清理房间 $4$ 和 $6$ 之间的走廊，房间 $4$ 和 $6$ 之间的走廊现在是干净的。
-    老鼠走到房间 $4$，房间 $4$ 和 $6$ 之间的走廊现在是脏的。
-    管理者堵住房间 $2$ 和 $3$ 之间的走廊。
-    老鼠走到房间 $2$，房间 $2$ 和 $4$ 之间的走廊现在是脏的。
-    管理者不进行操作。
-    老鼠走到房间 $1$。

这个过程中管理者总共进行了 $4$ 次操作。

**数据范围**

对于所有的数据，$1 \le n \le 10^6$。


title: [CEOI2017] Building Bridges

description:
有 $n$ 根柱子依次排列，每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$。

现在想要建造若干座桥，如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间，那么需要 $(h_i-h_j)^2$ 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$，注意 $w_i$ 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

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

第二行 $n$ 个空格隔开的整数，依次表示 $h_1,h_2,\cdots,h_n$。

第三行 $n$ 个空格隔开的整数，依次表示 $w_1,w_2,\cdots,w_n$。

outputFormat: 输出一行一个整数表示最小代价，注意最小代价不一定是正数。

hint: 对于 $100\%$ 的数据，有 $2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6$。


title: [CEOI2017] Palindromic Partitions

description:
给出一个只包含小写字母字符串，要求你将它划分成尽可能多的小块，使得这些小块构成回文串。

例如：对于字符串 ``abcab``，将他分成 ``ab`` ``c`` ``ab`` 或者 ``abcab`` 就是构成回文串的划分方法，``abc`` ``ab`` 则不是。

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

接下来的 $T$ 行，每行输入一个字符串，代表你需要处理的字符串，保证该字符串只包含小写字母。

outputFormat: 输出 $T$ 行，对于每个输入的字符串，输出一行包含一个整数 $x$，表示该字符串最多能分解成 $x$ 个小块，使得这些小块构成回文串。

hint: 对于 $100\%$ 的数据，有 $1\le T\le 10$。设 $L$ 为单个字符串的长度，则 $1\le L\le 10^6$。


title: [CEOI2017] Chase

description:
在逃亡者的面前有一个迷宫，这个迷宫由 $n$ 个房间和 $n-1$ 条双向走廊构成，每条走廊会链接不同的两个房间，所有的房间都可以通过走廊互相到达。换句话说，这是一棵树。

逃亡者会选择一个房间进入迷宫，走过若干条走廊并走出迷宫，但他永远不会走重复的走廊。

在第 $i$ 个房间里，有 $F_i$ 个铁球，每当一个人经过这个房间时，他就会受到铁球的阻挡。逃亡者手里有 $V$ 个磁铁，当他到达一个房间时，他可以选择丢下一个磁铁（也可以不丢），将与这个房间相邻的所有房间里的铁球吸引到这个房间。这个过程如下：

1.    逃亡者进入房间。
2.    逃亡者丢下磁铁。
3.    逃亡者走出房间。
4.    铁球被吸引到这个房间。

注意逃亡者只会受到这个房间原有的铁球的阻拦，而不会受到被吸引的铁球的阻挡。

在逃亡者走出迷宫后，追逐者将会沿着逃亡者走过的路径穿过迷宫，他会碰到这条路径上所有的铁球。

请帮助逃亡者选择一条路径，使得追逐者遇到的铁球数量减去逃亡者遇到的铁球数量最大化。

inputFormat:
第一行两个空格隔开的整数整数 $n$ 和 $V$。
第二行 $n$ 个空格隔开的整数表示 $F_i$。
之后的 $n-1$ 行，每行两个空格隔开的整数 $x$ 和 $y$，表示有一条走廊连接编号为 $x$ 和编号为 $y$ 的房间。

outputFormat: 输出一个整数表示最优情况下追逐者遇到的铁球数量减去逃亡者遇到的铁球数量。

hint:
**样例解释**

有一个最优方案如下：

-    从 $6$ 号房间进入迷宫并丢下第一个磁铁，他遇到了 $5$ 个铁球，这个时候 $6$ 号房间会有 $27$ 个铁球，而 $5$ 号，$7$ 号，$8$ 号，$9$ 号房间都没有铁球。
-    走到 $7$ 号房间丢下第二个磁铁并走出迷宫，他遇到了 $0$ 个铁球，这个时候 $7$ 号房间会有 $41$ 个铁球，而 $2$ 号，$4$ 号，$6$ 号，$10$ 号房间会没有铁球。

在这个过程中，逃亡者会遇到 $5$ 个铁球而追逐者会遇到 $41$ 个铁球。

**数据范围**

对于 $100\%$ 的数据，有 $1\le n\le 10^5;0\le V\le 100;0\le F_i\le 10^9$。


title: 信息传递

description:
给定置换
$$
f = \begin{pmatrix} 1 & 2 & ... & n \\\ a_1 & a_2 & ... & a_n \end{pmatrix}
$$
求有多少个置换 $g$ ，满足
$$
g ^ n = f
$$
答案对 $998244353$ 取模。

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

第二行 $n$ 个数 $a_1, a_2, ..., a_n$ 。

outputFormat: 输出答案。


title: 【模板】"动态 DP"&动态树分治

description:
给定一棵 $n$ 个点的树，点带点权。

有 $m$ 次操作，每次操作给定 $x,y$，表示修改点 $x$ 的权值为 $y$。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

inputFormat:
第一行有两个整数，分别表示结点个数 $n$ 和操作个数 $m$。

第二行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的权值  $a_i$。

接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示存在一条连接 $u$ 与 $v$ 的边。

接下来 $m$ 行，每行两个整数 $x,y$，表示一次操作，修改点 $x$ 的权值为 $y$。

outputFormat: 对于每次操作，输出一行一个整数表示答案。


title: [BalticOI 2008] 游戏

description:
玩家 $\text{A}$ 和玩家 $\text{B}$，在一个 $n\times n$ 的正方形方格板上玩游戏。方格板上的方格要么是白的，要么是黑的。游戏只在白色区域上进行，黑色区域是禁区。初始时，每位玩家的起点上，会放置一个棋子。保证两人起点不同。

玩家交替移动，玩家 $\text{A}$ 先移动。每次移动，玩家会将他的棋子移动到相邻的白色方格中。如果玩家将棋子移动到对方现在的位置，玩家可以再移动一步，以越过对手。注意在这种情况下，第二步移动的方向可以与第一步移动的不同。

这个游戏的目标是玩家的棋子首先到达对方的起点，先到者为胜。即使玩家的最后一步包含两次移动，并且他只是越过了对手的起点（如果对手现在在起点），这个玩家也获得胜利。

给出方格板的布局和两个玩家的起点，判定哪个玩家有必胜策略（如果对手不管怎样移动，一个玩家能获得胜利，就称一个玩家有必胜策略）。

inputFormat:
标准输入的第一行包含一个正整数 $t$，表示测试数据的组数（$1\le t \le 10$）。在此之后为 $t$ 组测试数据。每一组测试数据格式如下：

在这组数据的第一行是一个正整数 $n$，表示方格的边长（$2\le n\le 300$），之后的每一行包含 $n$ 个字符（字符之间无空格）。每个字符是 ``.``（一个白色方格），``#``（一个黑色方格），``A``（$\text{A}$ 的起点）和 ``B``（$\text{B}$ 的起点）其中之一。

保证在两人的起点间存在一条白色方格的通路。

outputFormat: 对于每组数据，输出一行到标准输出，包含一个字符 ``A`` 或 ``B``，表示有着必胜策略的玩家。

hint:
**样例解释**

对于第一组数据：

![0](https://i.loli.net/2018/02/19/5a8ab4a17e247.gif)

如果 $\text{A}$ 在前三次移动中移动到方格最右边，$\text{B}$ 将在前三次移动中向上移动。因此，在第三次移动中玩家 $\text{B}$ 将会到达 $\text{A}$ 的方块所在方格，并且给 $\text{B}$ 一次额外的移动机会。因此，$\text{B}$ 会首先到达 $\text{A}$ 的起点并且赢得游戏。

对于第二组数据：

![1](https://i.loli.net/2018/02/19/5a8ab4a17e132.gif)

$\text{A}$ 可以先向右移动一次，再向下移动一次。然后，$\text{A}$ 可以由 $\text{B}$ 的前两次移动决定他向下或向右移动来回避 $\text{B}$。这样的话 $\text{A}$ 会首先到达 $\text{B}$ 的起点，因此赢得比赛。事实上我们已经证明了 $\text{A}$ 有必胜策略。

**数据范围**

对于 $40\%$ 的数据， $n \le 40$。

对于 $60\%$ 的数据， $n \le 150$。

对于所有数据，$2\le n\le 300$。


title: [BalticOI 2008] 阀门

description:
成为码农多年的你，已经厌倦了码农生活。你决定跳槽，去做一些不一样的事情。

正在寻找下一份工作的你，被一份水产养殖的工作吸引住了。“太酷了！”并且，鱼是很好的生物 嗯切绘也是这么想的 。所以你毫不犹豫地去应聘了。幸运的是，你成功拿到了 Offer。今天是你工作的第一天。

你的老板已经给你分配了任务：分隔两个蓄水池。你手上的操作指南告诉了你如下信息：

这两个蓄水池之间有一些管道连通，每个管道有两个阀门。当两个阀门同时开启时，这个管道就处于开启状态，反之处于关闭状态。阀门用开关控制。同一个开关会控制一些阀门，但是每一个阀门都只被一个开关控制。有可能一个管道上的两个阀门被同一个开关控制，也可能有开关不控制任何阀门。

![0](https://i.loli.net/2018/02/19/5a8ac86221c4b.png)

开关以以下两种方式控制阀门：

-    当开关闭合时阀门打开，当开关断开时阀门关闭
-    当开关闭合时阀门关闭，当开关断开时阀门打开

玩了一会儿开关之后你突然意识到你的编程经历会十分有用。给出每个阀门被哪个开关所控制，判断是否可能关闭所有管道，如果可以，找出这种合法配置下每一个开关的状态。

inputFormat:
标准输入的第一行包含两个整数 $n$ 和 $m$，分别表示管道数和开关数。开关被从 $1$ 到 $m$ 标号。

接下来的 $n$ 行描述管道，一行用四个整数 $a,s_a,b,s_b$ 描述一个管道，$a,b$ 代表控制该管道的开关（$1\le a,b\le m$）。$s_a$ 和 $s_b$ 为 $0$ 或 $1$，并与描述中的操作模式相符，$s_i=0$ 表示当且仅当开关 $i$ 断开时阀门关闭，$s_i=1$ 表示当且仅当开关 $i$ 闭合时阀门关闭。

outputFormat:
如果有可能关闭所有管道，标准输出应包含 $m$ 行，如果开关 $i$ 断开，第 $i$ 行应输出 $0$，如果开关 $i$ 闭合，第 $i$ 行应输出 $1$。如果有很多可能的答案，你的程序可以输出任意一种。

如果不可能关闭所有管道，你的程序应输出一行，包含一个单词 ``IMPOSSIBLE``。

hint:
**数据范围**

对于 $30\%$ 的数据，$n\le 40, m\le 20$。

对于所有数据，$1\le n\le 2.5\times 10^5, 1\le m\le 5\times 10^5$。


title: [BalticOI 2008] 手套

description:
化学教授名曰“酸雨”。在他家黑暗的地下室，有两个装有手套的抽屉，一个抽屉装左手手套，另一个装右手手套。每个抽屉中有 $n$ 种不同颜色的手套。教授知道在每个抽屉中，每种颜色的手套数目（在不同抽屉中，相同颜色的手套数目可能不同）。保证他能够找到同色的一副手套。

只有教授带相同颜色的一副手套时试验才可能会成功（与哪种颜色无关），所以在每次试验开始之前他都要去地下室从抽屉中拿手套，并且希望至少有一副一样颜色的手套。但是地下室太黑了，不出地下室就不可能分辨出任何手套的颜色。教授讨厌去地下室超过一次，同时也讨厌拿一堆手套回实验室（以防没有相同颜色的手套）。

#任务

写一个程序能够：

-    从标准输入中读取颜色种数和每种颜色手套的数目
-    计算在确保拿出的手套中有一副颜色相同的手套的情况下需要取出手套的最小数目（需要明确指出从每个抽屉中取出手套的确切数目）
-    将结果写到标准输出

inputFormat:
标准输入的第一行包含一个正整数 $n$ （$1\le n\le 20$）描述不同的颜色种数。颜色从 $1$ 到 $n$ 编号；

输入第二行包含 $n$ 个非负整数 $0\le a_1,a_2,\cdots ,a_n\le 10^8$，$a_i$ 表示在装左手手套的抽屉中第 $i$ 种颜色手套的数目；

输入第三行包含 $n$ 个非负整数 $0\le b_1,b_2,\cdots ,b_n\le 10^8$，$b_i$ 表示在装右手手套的抽屉中第 $i$ 种颜色手套的数目。

outputFormat:
标准输出第一行包含单独一个整数，表示从装左手手套抽屉中取出的手套数。第二行包含单独一个整数，表示从装右手手套抽屉中取出的手套数。这两个数的总和应尽量小。

如果有多种正确答案，你的程序可以输出任意一组。

hint:
有 $40$ 分 $n\le 4$ 且 $a_i,b_i\le 10$。

对于所有数据，$1\le n\le 20$。


title: [BalticOI 2008] 网格

description:
Byteland 国的地图是一个大小为 $n\times m$ 的网格（$n$ 是垂直方向长度，$m$ 是水平方向长度）。标记分隔的水平线被叫做平行线，并编号为 $0$ 到 $n$，标记分隔的垂直线被叫做子午线，并编号为 $0$ 到 $m$。

在 Byteland 国，天气预报是一个十分严肃的话题，对于每个单元格，准备天气预报需要一定时间来计算。由于地形条件和其他因素，不同的单元格有着不同的计算时间。直到目前为止，预报系统还是会依次处理每一个单元格，所以完成预报天气需要花费的时间为计算所有单元的时间。

你被要求设计一个可以在多进程处理器上运行的新系统，为了共享处理器的计算能力，Byteland 国要被 $r$ 条平行线和 $s$ 条子午线划分为 $(r+1)(s+1)$ 个矩形。每个线程会依次处理一个矩形内部的单元格，这样的话对于一个矩形区域的计算时间，就为矩形区域内单元格计算时间之和。完成预报的计算时间是一个处理器上计算时间的最大值。

你的任务是找到对于选择 $r$ 条平行线和 $s$ 条子午线分隔后最小的计算时间。

#任务

写一个程序能够：

-    从标准输入读取 Byteland 的地图，要求的平行线和子午线条数以及每个单元格的处理时间；
-    找到完成预报的最小计算时间；
-    输出这个值到标准输出。

inputFormat:
第一行包含四个正整数 $n,m,r,s$，由一个空格隔开。

接下来 $n$ 行包含每一个单元格的计算时间 $c_{i,j}$。第 $i+1$ 行的第 $j$ 个数表示位于第 $i-1$ 和第 $i$ 条平行线，第 $j-1$ 和第 $j$ 条子午线之间的单元格需要的计算时间。

outputFormat: 输出一行一个整数，表示最优的计算时间。

hint:
**样例解释**

![0](https://i.loli.net/2018/02/19/5a8ae8ca02cbb.png)

第二条和第四条平行线，第四条子午线把整个国家分为六个矩形，计算时间为 $21, 13, 27, 27, 17, 31$，所以完成预报的计算时间为 $31$。

**数据范围**

对于 $40\%$ 的数据，$n\le 10,m\le 10$；

对于全部数据，$1\le r<n\le 18,1\le s<m\le 18$，$1\le i\le n,1\le j\le m,0\le c_{i,j}\le 2\times 10^6$。


title: [BalticOI 2008] 黑手党

description:
Byteland 国警方收到了一条匿名举报，其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。

高速公路网包含双向的高速公路段，每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知，黑帮会距港口边最近的收费站进入高速公路，从距仓库最近的收费站离开（不会在出高速后重新进入）。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时，它就会被警察抓住。

从这个角度看，最简单的办法就是在每个收费站处都安排特警班。然而，控制一个收费站需要特定的费用，每个收费站费用不同。警方想要让花费最小，所以他们需要制定一个收费站的最小控制集，这个集合满足两个条件：

-    所有从港口到仓库的交通必须至少经过集合中的一个收费站
-    监控这些收费站的费用（即监控每一个收费站费用之和）最小

你可以假设使用高速公路可以从港口到仓库。

#任务

写一个程序能够：

-    从标准输入中读取高速公路网，监控代价和运输的起点和终点
-    找到收费站的最小控制集
-    输出这个集合到标准输出

inputFormat:
标准输入的第一行包含两个整数 $n$ 和 $m$，表示收费站的总数和公路段的总数。收费站按 $1$ 到 $n$ 标号；

第二行包含两个整数 $a$ 和 $b$，分别表示距港口和仓库最近的两个收费站编号；

接下来 $n$ 行表示控制费用，第 $i$ 行包含一个整数，表示第 $i$ 个收费站的控制费用 $c$；

接下来 $m$ 行表示高速公路网，第 $j$ 行包含两个整数 $x$ 和 $y$，表示在 $x$ 和 $y$ 收费站之间有一条公路段相连。每一条高速公路段只出现一次。

outputFormat:
唯一的一行输出应包含最小控制集中收费站的编号，以递增顺序输出，用一个空格分隔。

如果有多于一个最小控制集，你的程序可以输出任意一个。

hint:
**样例解释**

![0](https://i.loli.net/2018/02/19/5a8af2c2ef8d7.gif)

这张图片显示了高速公路网中收费站的编号（在左上角）和控制费用。$1$ 号和 $4$ 号收费站组成了最小控制集，总控制费用为 $5$。

**数据范围**

对于 $40\%$ 的测试数据，$n\le 20$；

对于全部数据，$1\le n\le 200,1\le m \le 2\times 10^4$，$1 \le a,b \le n,a≠b$，$1\le c\le 10^7$，$1\le x<y\le n$。


title: [BalticOI 2008] 魔法石

description:
知名的石头 $\text{Xi-n-k}$ 只能在 Wonderland 中找到，这样的石头只是一种碑文只有字母 ``X`` 和 ``I`` 的花岗岩板。每个石板包含 $n$ 个字母。每个石板上有不超过 $k$ 个位置 ``X`` 和 ``I`` 相邻。

石板的顶部和底部不是固定的，所以石头可以旋转，变为倒立状态。例如下面这两个图片描述的是一样的石头。

![0](https://i.loli.net/2018/02/20/5a8ba0ad731f2.png)

(看同样石头的两种方式。这种石头的种类是 $\text{Xi-8-3}$，也是 $\text{Xi-8-4}$（当然也可以是 $\text{Xi-8-}k$，$k \ge 3$））。

现在 Wonderland 中任意两块魔法石都不是一样的，即两块石头都没有相同的碑文（注意旋转 $180^\circ$ 是允许的）。

如果可以以两种不同方式（用旋转 $180^\circ$ 的方式）读一块石头的碑文，那么对于这块石头，碑文的正规阅读方式被定义为两种阅读方式字典序小的那种。

如果一块石头的碑文是对称的，即旋转 $180^\circ$ 并不改变碑文，那么对于这块石头，碑文的的正规阅读方式被定义为这种独一无二的阅读方式。

例如：有六种 $\text{Xi-3-2}$ 魔法石，它们的正规阅读方式以字典序写出为：``III``，``IIX``，``IXI``，``IXX``，``XIX`` 和 ``XXX``。

Alice 是一个研究 Wonderland 的魔法石的专家。她想要创建一个 $\text{Xi-n-k}$ 魔法石的正规阅读方式字典（对于一些特定的 $n$ 和 $k$）。对于给出的 $i$，在字典中第 $i$ 个位置应该是什么碑文呢？

#任务

写一个程序能够：

-    从标准输入中读取数字 $n$，$k$，$i$
-    判定对于 $\text{Xi-n-k}$ 魔法石，第 $i$ 个正规阅读方式（按字典序）
-    输出结果到标准输出

inputFormat: 标准输入只有一行，包含三个数 $n$，$k$，$i$，用一个空格分开。

outputFormat:
标准输出只有一行，应该包含 $\text{Xi-n-k}$ 魔法石，第 $i$ 个正规阅读方式（按字典序）。

如果 $\text{Xi-n-k}$ 魔法石的数量比 $i$ 小，那么只输出一行一个短语 ``NO SUCH STONE``。

samples:
3 2 5
XIX

samples:
3 2 7
NO SUCH STONE

hint:
**数据范围与提示**

对于全部数据，$0\le k<n\le 60,0<i<10^{18}$。

注：我们说 $\text{A}$ 的碑文字典序比 $\text{B}$ 小（假设 $\text{A}$ 和 $\text{B}$ 的碑文长度相同），当且仅当在第一个碑文不同的位置 $\text{A}$ 包含 ``I`` 且 $\text{B}$ 包含 ``X`` 。


title: [BalticOI 2008] 选举

description:
The citizens of Byteland have recently been voting in the parliamentary elections. Now, when the results
have been published, the parties have to decide on a coalition to form the government.

Each party received a certain number of seats in the parliament. The coalition must be a subset of the
parties such that together they have strictly more than half of all the seats in the parliament. It is desirable for
the coalition to have as many seats as possible, to ensure they can still pass their proposed laws even if a few
of their members are absent from a parliament session.
A coalition is called redundant if one of its parties can be removed with the remaining ones still having
more than half of the seats in the parliament. Of course, such a removable party would effectively have no
power — the other members of the coalition would be able to force the laws regardless of its opinion.

Write a program that:

- reads the election results from the standard input,
- finds a non-redundant coalition that has the maximal possible number of seats in the parliament,
- writes the description of this coalition to the standard output.

### Input

The first line of the standard input contains one integer $n\ (1\le n\le 300)$ — the number of parties that participated in the elections. The parties are numbered from $1$ to $n$.

The second line contains n nonnegative integers $a_1,\dots,a_n$, separated by single spaces, where $a_i$
is the
number of seats received by the $i$-th party. You may assume that the total number of seats in the parliament
will be positive and lower or equal to $100000$.

Additionally, in test cases worth $40\%$ of points, the number of parties will not exceed $20$.

### Output

The first line of the standard output should contain one integer $k$ — the number of parties in a non-redundant
coalition which has the maximal number of seats.
The second line should contain $k$ distinct integers separated by single spaces — the numbers of parties
that form the coalition.

If there are several non-redundant coalitions with the maximal number of seats, you may output any of
them. The member parties can be listed in any order.

### 题目翻译

Byteland 国的居民最近一直为议会选举投票。现在，当结果公布的时候，党派不得不决定联合组建政府。

每个党派都会获得议会中的一定席位。联合政府由这些党派中的一部分组成，他们在议会中的席位数之和**严格大于**总席位数的一半。对于联合政府来说，席位越多越好。

一个**过剩**的联合政府是指联合政府中的一个党派被移出后，剩余的联合政府在国会中仍有过半数的席位。

请写一个程序能够：

-    读取选举结果；
-    找到一个在议会中有着**最大可能席位数**且**不过剩**的联合政府；
-    输出这个联合政府的描述。

inputFormat:
标准输出的第一行包含一个整数 $n$，表示参加选举的党派数。党派被从 $1$ 到 $n$ 编号。

第二行包含 $n$ 个非负整数 $a_1,\dots ,a_n$，被一个空格隔开，$a_i$ 是第 $i$ 个党派获得的席位数。你可以假设国会中的中的总席位数为小于等于 $10^5$ 的正整数。

outputFormat:
标准输出第一行应该包含一个整数 $k$，表示无过剩且在议会中有着最大可能席位数的联合政府中含有的党派数。

第二行应该包含 $k$ 个被单个空格隔开的不同整数，表示组成联合政府的党派编号。

如果有不止一个联合政府可以满足要求，你可以输出任意一个。党派的编号可以以任意顺序输出。

hint:
对于 $40\%$ 的数据，$n\le 20$；

对于全部数据，$1\le n\le 300$。


title: [BalticOI 2015] Network

description:
The government of Byteland has decided that it is time to connect their little country to the Internet, so that all citizens can participate in programming competitions and watch videos of cute cats. When it was time to build the network backbone of the country, they assigned the company Internet Optimists Inc. with connecting all the $N$ computers of Byteland. The connections were made as direct links between pairs of computers in such a way that any pair of computers are connected by a sequence of links.

Byteland is not a rich country by any means, so to minimize costs the network topology was built in the form of a tree (i.e. there are exactly $N-1$ direct links between computers). Far too late, it was realised that this solution suffers from a serious drawback. If just a single link is broken, the computers of Byteland will be partitioned so that some computers cannot communicate with each other! To improve the reliability of Byteland's network, it was decided that it should at least tolerate if a single link is broken. Your task is to help Internet Optimists Inc. to improve the network in a cheapest way. Given the network topology of Byteland (i.e. which $N-1$ pairs of computers are connected by direct links), find the minimum number of links that need to be added so that the network will still be connected if any single link is broken.

inputFormat: The first line of input contains a positive integer $N$ ( $N \geq 3$ ) , the number of computers in Byteland. For simplicity, all computers are numbered from $1$ to $N$. Each of the following $N-1$ lines contains a pair of integers $a$ and $b$ ( $1\leq a,b \leq n,a \ne b$ ) that describes a direct link between computers $a$ and $b$.

outputFormat: In the first line of output your program should write an integer $k$, the minimal number of links that should be added to the network. In each of the following $k$ lines your program should write a pair of integers $a$ and $b$ ( $1\leq a,b \leq n,a \ne b$ ) that denote the numbers of computers that should be connected by a link. The links can be written in any order. If there is more than one solution, your program should output any one of them.

translation:
### 题目描述###
拜特朗政府已经决定，现在是时候将他们的小国家与互联网连接起来，以便所有公民都能参加节目比赛，观看可爱猫的视频。当是时候建设这个国家的网络骨干时，他们给互联网乐观主义者公司分配了连接所有N个拜特兰德的电脑。这些连接是作为计算机对之间的直接连接，使任何一对计算机都通过一系列的链接连接起来。

拜特朗是一个发展中国家，因此，为了将成本降到最低，网络拓扑是以树的形式构建的(即有N−1个计算机之间的直接连接)。为时已晚，人们意识到这一解决方案存在严重缺陷。如果只有一个链接断了，那么拜特兰德的计算机就会被分割，这样一些计算机就不能互相通信了！为了提高拜特朗网络的可靠性，人们决定至少要容忍单个链路中断。你的任务是帮助互联网乐观主义者公司以最便宜的方式改进网络。给出了拜特朗的网络拓扑(即N−1个计算机对是通过直接链接连接的)，找到需要添加的最少数量的链接，以便如果任何单个链接中断，网络仍将被连接。

### 输入输出格式
#### 输入格式：
输入的第一行包含一个正整数N(N≥3)，表示拜特兰德的计算机数量。为了简单起见，所有的计算机都是从1到N。以下N−1行包含一对整数。a和b(1≤a, b≤n, a≠b)，它描述计算机之间的直接链接a和b.
#### 输出格式：
在输出的第一行只有一个整数k，表示应该添加到网络中的最少链接数量。在下列每一项中都有对整数。a和b(1≤a ,b≤n ,a≠b)表示应该通过链接连接的计算机数量。链接可以按任何顺序写入。如果有一个以上的解决方案，您的程序应该输出其中的任何一个。

感谢@找寻 提供翻译


title: [USACO05DEC] Cleaning Shifts S

description:
约翰的奶牛们从小娇生惯养，她们无法容忍牛棚里的任何脏东西。约翰发现，如果要使这群有洁癖的奶牛满意，他不得不雇佣她们中的一些来清扫牛棚，约翰的奶牛中有 $ N(1 \leq N \leq 10000) $ 头愿意通过清扫牛棚来挣一些零花钱。

由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾，自然地，她们要求在这段时间里，无论什么时候至少要有一头奶牛正在打扫。需要打扫的时段从某一天的第 $ M $ 秒开始，到第 $ E $ 秒结束 $ (0 \leq M \leq E \leq 86399) $。注意这里的秒是指时间段而不是时间点，也就是说，每天需要打扫的总时间是 $ E-M+1 $ 秒。

约翰已经从每头牛那里得到了她们愿意接受的工作计划：对于某一头牛，她每天都愿意在笫 $ T_1 \ldots T_2 $ 秒的时间段内工作 $ (M \leq T_1 \leq T_2 \leq E) $ ，所要求的报酬是 $ S $ 美元 $ (0 \leq S \leq 500000) $。与需打扫时段的描述一样，如果一头奶牛愿意工作的时段是每天的第 $ 10 \ldots 20 $ 秒，那她总共工作的时间是 $ 11 $ 秒，而不是 $ 10 $ 秒。

约翰一旦决定雇佣某一头奶牛，就必须付给她全额的工资，而不能只让她工作一段时间，然后再按这段时间在她愿意工作的总时间中所占的百分比来决定她的工资。现在请你帮约翰决定该雇佣哪些奶牛以保持牛棚的清洁，当然，在能让奶牛们满意的前提下，约翰希望使总花费尽量小。

inputFormat:
第 $ 1 $ 行： $ 3 $ 个正整数 $ N,M,E $ 。

第 $ 2 $ 到 $ N+1 $ 行：第 $ i+1 $ 行给出了编号为 $ i $ 的奶牛的工作计划，即 $ 3 $ 个正整数 $ T_1,T_2,S $ 。

outputFormat: 输出一个整数，表示约翰需要为牛棚清理工作支付的最少费用。如果清理工作不可能完成，那么输出 $ -1 $ 。

hint: 约翰有 $ 3 $ 头牛，牛棚在第 $ 0 $ 秒到第 $ 4 $ 秒之间需要打扫。 约翰雇佣前两头牛清扫牛棚，可以只花 $ 5 $ 美元就完成一整天的清扫。


title: P哥旋转

background: P哥开始学字符串了！

description:
P 哥学会了字符串处理的新方法——旋转。

“旋转”是这样一种操作：将原字符串最后面的字符抹去，然后把它加到最前面，得到一个新串。

P 哥可以进行无数次“旋转”操作，**让得到的新串中本质不同的回文子串尽可能多**。

两个回文串本质不同，当且仅当它们长度不同，或至少有一个相同位置的字符不同。

现在 P 哥得到了一个串 $S$，请你通过“旋转”操作帮 P 哥达成他的目标（即上面的加粗字体部分），并输出新串中不同的回文子串的个数。

inputFormat: 输入共一行，代表串 $S$，保证只有小写英文字母。

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

hint:
设 $n$ 为串 $S$ 的长度。

- 对于前 $20\%$ 的数据，$n \le 100$。
- 对于前 $40\%$ 的数据，$n \le 2000$。
- 对于另 $10\%$ 的数据，保证得出正确答案不用进行旋转。
- 对于 $100\%$ 的数据，$n \le 1.5\times 10^6$。

此外，对于后 $50\%$ 的数据，保证串 $S$ 的非随机部分长度不超过 $5000$。

**注意**：本题采用 subtask 方式计分。前 $50\%$ 的数据是 $subtask#1$，该 subtask 采用加和的方式计分（你可以认为是传统计分方式）。后 $50\%$ 的数据是 $subtask#2$，该 subtask 采用取 $\min$ 的方式计分（即只要错一个点，后 $50$ 分全部没有）。


title: Divided Prime

description:
给定一个数字$A$，这个$A$由$a_1,a_2,\cdots,a_N$相乘得到。

给定一个数字$B$，这个$B$由$b_1,b_2,\cdots,b_M$相乘得到。

如果$\frac{A}{B}$是一个质数，请输出`YES`，否则输出`NO`。

inputFormat:
每个测试点包含多组数据，第一行读入一个整数 $T$ 表示数据组数，对于每组数据：

第一行输入两个整数 $N,M$，分别表示 $A$ 由 $N$ 个数字相乘得到，$B$ 由 $M$ 个数字相乘得到。

第二行输入 $N$ 个整数，分别表示组成 $A$ 的 $N$ 个数字。

第三行输入 $M$ 个整数，分别表示组成 $B$ 的 $M$ 个数字。

保证对于一个数字，其在 ${b_i}$ 中出现的次数不多于在 ${a_i}$ 中出现的次数。

outputFormat:
对于每组数据：
如果 $\frac{A}{B}$ 是一个质数，请输出 `YES`，否则输出 `NO`。
在输出 `YES` 或 `NO` 后输出一个换行符。


title: River Jumping

description: 有一条宽度为 $N$ 的河上，小 D 位于坐标为 $0$ 的河岸上，他想到达坐标为 $N$ 的河岸上后再回到坐标为 $0$ 的位置。在到达坐标为 $N$ 的河岸之前小 D 只能向坐标更大的位置跳跃，在到达坐标为 $N$ 的河岸之后小 D 只能向坐标更小的位置跳跃。在河的中间有 $M$ 个岩石，小 D 希望能跳到每个岩石上恰好一次。由于小 D 的跳跃能力太强，小 D 的跳跃长度有个下限 $S$，但没有上限。现在请你判断他是否能够完成他的目标。

inputFormat:
第一行输入两个整数 $N,M,S$，分别表示河的宽度，岩石的数量和跳跃长度的下限。

第二行输入 $M$ 个整数，分别表示 $M$ 个岩石的坐标 $w_1,w_2,\cdots,w_N$。保证 $\{w_i\}$ 为递增序列。

outputFormat:
如果小D可以完成他的目标，第一行输出 `YES`，第二行输出 $M+2$ 个数，依次表示小D跳到的石头编号。特殊的，坐标为 $0$ 的河岸编号为 $0$，坐标为$N$的河岸标号为 $M+1$ 。如果有多种解法，允许输出任意一种。

如果小 D 不能完成他的目标，第一行输出 `NO`。

hint: 对于全部数据，保证 $1 \le N,S \le 100000$，$0 \le M < N$，$1 \le w_i < N$。


title: True Vegetable

description: 小A现在有$N$道题，编号为$1,2,\cdots,N$。每道题的起始毒瘤程度为$0$或$1$。在每回合，小A可以将编号连续的$K$道题的毒瘤程度+1。但小B因为本身比较菜，不是很愿意小A出毒瘤题，所以在$w_i$回合开始时可以向第$x_i$题传播$v_i$点的菜气，使得第$x_i$的毒瘤程度减少$v_i$点（减后可以为负）。这里我们假定菜是有限的，在释放了$v_i$点的菜气后，小B需要至少$r_{v_i}$个回合不能释放菜气。现在小A知道了小B释放菜气的计划，他想知道他至少需要多少个回合可以使得每道题的毒瘤程度至少为$1$。

inputFormat:
第一行输入四个整数，$N,M,K,L$，分别为题目的数量，小B的操作数量，每次连续增加毒瘤程度题目的数量和释放菜气的最大值。

第二行输入$N$个整数$a_1,a_2,\cdots,a_N$，分别为$N$个题目的毒瘤程度。

第三行输入$L$个整数$r_1,r_2,\cdots,r_L$，分别为释放$1$到$L$点菜气的冷却回合数。

接下来有$M$行，每行输入三个整数$w_i,x_i,v_i$，表示小B在第$w_i$回合开始时向第$x_i$题释放了$v_i$点的菜气。保证$\{w_i\}$为递增序列。

outputFormat: 请输出小A将每道题的毒瘤程度加到至少为$1$最少需要的回合数。


title: [BalticOI 2011 Day1] Growing Trees

description:
For fertilizing the trees he has several bottles of MegaBoostFertilizer, which, when treated on trees, causes them to grow one centimeter up instantly. Every bottle has a limited capacity $c_i$ , which determines the number of trees it can be applied to. Moreover, for each bottle there is a minimal height $h_i$ of trees, which can be treated with it. Since Egon wants to have all his trees as big as possible, he always applies the fertilizer to the $c_i$ smallest trees chosen from the trees that are at least $h_i$ centimeters high.

When Egon computes statistics about trees he has to determine the number of trees whose height is in some given interval. Egon is quite busy working in the garden, so he asked you to write a program, that given the list of his tasks, computes the statistics for him.

inputFormat:
The first line of the standard input contains two integers $N$ and $M$ denoting the number of trees in Egon’s garden and the number of his tasks. The second line contains a sequence of $N$ integers fromthe range $[1,N]$ describing the initial heights of the trees in centimeters. The following $M$ lines describe the tasks in chronological order. Each of those lines begins with a character $t_i$ $(t_i=F \ or \ C)$, which describes the type of the task.

If $t_i=F$ then two integers $c_i$ and $h_i$ follow. Such a line means that Egon applies a bottle of MegaBoostFertilizer to the $c_i$ smallest trees among those trees that are at least $h_i$ centimeters high. When there are less than $c_i$ trees of sufficient height, he applies the fertilizer to all such trees and discards the bottle with some fertilizer remaining.

If $t_i=C$ then two integers $\min_i$ and $\max_i$ follow. They denote that Egon has to compute the number of trees whose height $H$ is between $\min_i$ and $\max_i$ centimeters $(\min_i \le H \le \max_i)$.

outputFormat: For every task of type C, output one line containing the number of apple trees that have the required height. The order of the results should conform to the order of type C tasks in the input.

translation:
给出一个长度为 $N$ 的数组 $a$，数组中每个数的取值范围均为 $[1,N]$（没说互不相同）。
接下来有 $M$ 组操作，操作分为两种：
1. $\texttt{F}\:\:c\:\:h$
将满足 $a[i] \ge h$ 的所有 $a[i]$ 中最小的 $c$ 个数都 $+1$；
2. $\texttt{C}\:\:max\:\:min$
输出满足 $min \le a[i] \le max$ 的 $a[i]$ 的个数。

### 输入格式

第一行有两个整数 $N$ 和 $M$。
第二行有 $N$ 个整数，表示数组 $a$。
在接下来的 $M$ 行中，每行有一组操作。

### 输出格式

对于每组 $\texttt{C}\:\:max\:\:min$ 操作输出一行，每行一个整数，表示满足 $min \le a[i] \le max$ 的 $a[i]$ 的个数。

翻译提供者：Planet6174


title: [BalticOI 2011 Day1] Switch the Lamp On 电路维修

description:
Casper is designing an electronic circuit on a $N \times M$ rectangular grid plate. There are $N \times M$ square tiles that are aligned to the grid on the plate. Two (out of four) opposite corners of each tile are connected by a wire.

A power source is connected to the top left corner of the plate. A lamp is connected to the bottom right corner of the plate. The lamp is on only if there is a path of wires connecting power source to lamp. In order to switch the lamp on, any number of tiles can be turned by 90° (in both directions).

![0](http://ruanx.pw/bzojch/file/2346_0.jpg)

In the picture above the lamp is off. If any one of the tiles in the second column from the right is turned by 90° , power source and lamp get connected, and the lamp is on.

Write a program to find out the minimal number of tiles that have to be turned by 90° to switch the lamp on.

inputFormat: The first line of input contains two integer numbers $N$ and $M$, the dimensions of the plate. In each of the following $N$ lines there are $M$ symbols – either \ or / – which indicate the direction of the wire connecting the opposite vertices of the corresponding tile.

outputFormat: There must be exactly one line of output. If it is possible to switch the lamp on, this line must contain only one integer number: the minimal number of tiles that have to be turned to switch on the lamp. If it is not possible, output the string: ``NO SOLUTION``

translation:
### 题目描述
Casper 正在设计电路。有一种正方形的电路元件，在它的两组相对顶点中，有一组会用导线连接起来，另一组则不会。有 $N\times M$ 个这样的元件，你想将其排列成 $N$ 行，每行 $M$ 个。 电源连接到板的左上角。灯连接到板的右下角。只有在电源和灯之间有一条电线连接的情况下，灯才会亮着。为了打开灯，任何数量的电路元件都可以转动 90°（两个方向）。

![](https://cdn.luogu.com.cn/upload/pic/1286.png)

![](https://cdn.luogu.com.cn/upload/pic/1285.png)

在上面的图片中，灯是关着的。如果右边的第二列的任何一个电路元件被旋转 90°，电源和灯都会连接，灯被打开。现在请你编写一个程序，求出最小需要多少旋转多少电路元件。

### 输入输出格式

#### 输入格式
输入的第一行包含两个整数 $N$ 和 $M$，表示盘子的尺寸。 在以下 $N$ 行中，每一行有 $M$ 个符号 `\` 或 `/`，表示连接对应电路元件对角线的导线的方向。
#### 输出格式：
如果可以打开灯，那么输出只包含一个整数，表示最少转动电路元件的数量。

如果不可能打开灯，输出 `NO SOLUTION`。

hint:
对于 $40\%$ 的数据，$1 \le N \le 4$，$1 \le M \le 5$。

对于所有数据，$1 \le N,M \le 500$。


title: [BalticOI 2011 Day1] Treasures and Vikings

description:
You have a treasure map that is arranged into a $N \times M$ grid. A grid square may be either sea or part of an island. In addition, the map shows the treasure and an enemy Viking ship that occupies one (sea) square. Finally, for convenience you have also drawn your own position.

Now you must set up a fixed route to get the treasure. The route must start at your position, end at the treasure, and consist of a sequence of moves. In each move, you can go only to an (horizontally or vertically) adjacent square that is not part of an island. But beware: The Viking ship might follow you, using the same kind of moves! After each of your moves according to your route, the Viking ship may move or not. Your move and the Vikings’ reaction together is called a round.

After every round, the following checks are made:

-    If you are in line with the Viking ship (you are in the same vertical or horizontal line as the Viking ship with only sea between the Viking ship and you), you are dead.
-    If you aren’t dead and at the treasure-spot, you get the treasure.

Write a program that decides whether it is possible to set up a fixed route in advance such that you can get the treasure by following this route and will not get killed by the Vikings – no matter how the Viking ship moves.

inputFormat: The first line of input contains two integers $N$ and $M$, the dimensions of the map. Each of the following $N$ lines contain $M$ characters. Each character describes a square in the map, and is either ``.`` (sea), ``I`` (part of an island), ``V`` (the Viking ship), ``Y`` (your position), or ``T`` (the treasure). Each of ``V``, ``Y``, and ``T`` will occur exactly once.

outputFormat: The only line of the output must contain the string ``YES``, if it is possible to set up a route to get the treasure, or ``NO`` otherwise.

translation:
你有一张藏宝图，藏宝图可视为 $N×M$ 的网格。每个格子可能是你的船、贼船、海、陆地或藏宝点。你只有一条船，整张图只有一条贼船。你和贼船都只能在海域移动。藏宝点在海中。

你与贼船交替移动，每一回合，你移动一次，接着贼船移动一次。每次移动，你可以移动到上下左右四个相邻格子中的一格，也可以不移动。贼船的移动同理，贼船也可以不移动。你先移动。

每一回合结束后，如果你和贼船在同一行或同一列，**并且你和贼船之间没有陆地**，你就挂了；在你没挂的情况下，如果你位于藏宝点，你就拿到了宝藏。
请问：是否有一条安全的路径，使得无论贼船怎么跑你都能或者拿到宝藏。

Translated by @Planet6174

hint:
**Sample Explanation 1**

The route is:go down for three times,go right for three times too,go down at last.

**数据范围**

对于 $50\%$ 的数据，$1 \le N,M \le 200$。

对于所有数据，$1 \le N,M \le 700$。


title: [BalticOI 2011 Day2] Meetings

description:
The Society for Saving the World has called their $N$ members to an emergency congress to finally agree on a plan for saving the world. To reach a common decision in any meeting at the congress, the meeting participants proceed as follows:

1.    Each of them has a proposal and takes $P$ minutes to present it to the others.

2.    After all participants have made their presentations, they vote for the best proposal, which takes $V$ minutes.

For example, if each proposal takes one minute $(P = 1)$ and voting also takes one minute $(V = 1)$, a meeting with $100$ participants would reach a decision in $101$ minutes. To speed up the overall decision-making process, the participants of the congress have decided to split into groups and work in parallel. Each group selects the best proposal among themselves using the procedure described above. Then the representatives of the groups meet and pick the final plan among the proposals voted best in each group. For example, if the $100$ participants would split into two groups of $40$ and $60$, respectively, the process could work as follows (again, $P = V = 1$):

-    the larger group takes $61$ minutes to select their best proposal;
-    the smaller group takes $41$ minutes to do the same and then has to wait for the larger group to finish;
-    then the two representatives of the groups meet and spend $2$ minutes presenting to each other and $1$ minute to vote.

The total time spent is thus $61 + 2 + 1 = 64$ minutes. But the groups might further divide themselves into subgroups and sometimes it could be useful to split into more than two groups. As a special case, a subgroup of $1$ member can decide in no time, as there is no need to present one’s own proposal to oneself. Write a program that, given presentation and voting times $P$ and $V$ , computes the minimal time needed for the $N$ participants of the congress to reach a common decision, assuming they organize their meetings and groups optimally.

inputFormat: The first and only line of input contains the three integers $N, P,$ and $V$ : $N$ is the number of participants of the congress, $P$ is the presentation time (in minutes), and $V$ is the voting time (in minutes).

outputFormat: The first and only line of output should contain the integer $M$, the minimal number of minutes needed for the congress to reach a decision.

translation:
** 译自 BalticOI 2011 Day2 T1「Meetings」**

有 $N$ 人需达成一项计划。每人都花 $P\min$ 陈述自己的提案，所有人陈述完毕后再花 $V\min$ 表决出最佳提案。例如，如果有 $100$ 人，$P=V=1\min$，总共需要 $1\times 100 + 1=101\min$ 来达成计划。
为了加快进度，他们想分成小组，每个小组表决出一份最佳议案，再由全部人一起表决各小组选出的议案。注意小组内可以再分组。小组内表决的方式类似，也是每人陈述自己的提案后再表决。例如，$100$ 人分成两组，一组 $60$ 人，一组 $40$ 人，那么过程如下（与前面相同，$P=V=1\min$）：
* $60$ 人组花 $61\min$ 选出最佳议案，同时 $40$ 人组花 $41\min$ 选出最佳议案（自然，他们要等待 $60$ 人组）；
* 两组再花 $2\min$ 陈述，然后花 $1\min$ 表决。

总用时 $61 + 2 + 1 = 64\min$。
试求：他们至少要多久才能达成计划。

Translated by @Planet6174

hint:
**Sample Explanation 1**

In sample 1,the nine people should be divided into 3 groups.There should be 3 people in each group.

**数据范围**

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

对于 $70\%$ 的数据，$1 \le N \le 5 \times 10^4$。

对于所有数据，$1 \le N \le 10^{15},1 \le P,V \le 1000$。


title: [BalticOI 2011 Day2] Plagiarism

description:
The participants of the World Programming Competition submitted $N$ solution files $f_1 ,...,f_N$ to the grading system. Before accepting the results as final, the jury would like to rule out any possibility of plagiarism. They have a program that takes two files and compares them to decide if they are too similar to each other.

However, the number of files is rather big and it would take too much time to compare all pairs. On the other hand, many pairs could be quickly eliminated based on the fact that the file sizes are too different.

More precisely, the jury decided to fully skip comparing every pair where the size of the smaller file is less than 90% of the size of the larger one. So, the comparison program has to examine only those distinct pairs of files $(f_i, f_j)$ where $i≠j, size(f_i) \le size(f_j)$ and $size(f_i) \ge 0.9 \times size(f_j)$.

Write a program that computes the number of pairs of files that will have to be examined.

inputFormat: The first line of input contains the integer $N$, the number of solution files submitted. The second line contains $N$ integers $size(f_1),\cdots,size(f_N)$, each showing the size of one file.

outputFormat: The first and only line of output must contain one integer, the number of pairs of files that will have to be examined.

translation:
Description

世界编程大赛的选手们提交N份程序文件f1, …, fN给评测系统。在将评测结果正式公布之前，评委会想要排除一切可能的剽窃现象。他们已有一个对比程序，用来比较两份程序文件，并判断它们是否太过相似了。 然而程序文件的数目相当大，把每两份（一对，pair）文件都进行比较的话将花太多的时间。另一方面，许多对(pair)可以直接被排除，如果文件的大小相差太大的话。 更准确地说，评委会决定，如果每两份文件（一对，pair）中，较小文件的体积小于较大文件的体积的90%，那将直接不比较这样的一对(pair)。所以，对比程序只比较这样的一对(fi, fj)： i≠j, size(fi )≤ size(fj )且size(fi )≥0.9∙size(fj )。 编写程序计算有多少对(pair)文件需要被比较。

Input:

第1行包含一个整数N，即提交的程序文件总数。 第2行包含N个整数size(f1), …, size(fN)，每个整数代表文件的体积大小。

Output:

第1行，也是唯一的一行，给出一个整数，即需要被比较的文件的对(pair)的数目。

感谢@谦谦君子 提供翻译


title: [BalticOI 2011 Day2] Polygon

description:
A simple polygon with $N$ vertices is drawn on an infinite rectangular grid. For such a polygon, only neighboring edges touch at their common vertex; no other of its edges intersect or touch. All vertices of the polygon lie on grid points, i.e., vertices have integer coordinates.

Your task is to find the total length of grid line segments which lie strictly inside the given polygon (these line segments are highlighted in the drawings below).

inputFormat: The first line of input contains a single integer $N$, the number of vertices of the polygon. Each of the following $N$ lines contains two integers $x$ and $y$, the coordinates of one vertex. The vertices are given either in clockwise or counterclockwise order. All vertices are distinct, but more than two consecutive vertices may lie on a line.

outputFormat: The only line of output must contain a decimal number: the total length of grid line segments which lie strictly inside the given polygon.

translation:
在平面直角网格图中有一个简单多边形，它有 $N$ 个顶点，每个顶点都在格点上（格点=整点）。
试求：严格在多边形内部的网格线有多长。在「样例解释」中， 严格在多边形内部的网格线将会加粗显示。
请注意精度。设你的答案为 $L$，标准答案为 $R$，则只需满足 $|L - R| \le R \times 10^{-6}$ 和 $|L - R| <= 10^{-6}$ 两个条件中的其中一个即可得分。

### 样例输入
第一行有一个整数 $N$。
在接下来的 $N$ 行中，每行两个整数 $x$ 和 $y$，表示一个顶点的坐标。

### 样例输出
输出仅一行，一个数，表示严格在多边形内部的网格线的长度。

#### 样例解释 1
![](https://cdn.luogu.org/upload/pic/42607.png)

符合要求的横线之长为 $\frac{4}{3} + \frac{8}{3} =4$，竖线之长为 $3+2+1=6$。总长 $4+6=10$。

#### 样例解释 2
![](https://cdn.luogu.org/upload/pic/42608.png)

符合要求的横线之长为 $1+2+4=7$，竖线之长为 $\frac{9}{4}+\frac{3}{2}+\frac{7}{4}=5.5$。总长 $7+5.5=12.5$。

翻译提供者：Planet6174

hint:
**Sample Explanation 1**

The length of horizontal lines is $\frac{4}{3} + \frac{8}{3} = 4$. The length of vertical lines is $3 + 2 + 1 = 6$. The total length is $4 + 6 = 10$.

**Sample Explanation 2**

The length of horizontal lines is $1+2+4 = 7$. The length of vertical lines is $\frac{9}{4}+\frac{3}{2}+\frac{7}{4} = 5.5$. The total length is $7 + 5.5 = 12.5$.

**数据范围**

对于 $50\%$ 的数据，多边形所有的边均在网格线上。

对于所有数据，$3 \le N \le 10^5,-5 \times 10^8 \le x,y \le 5 \times 10^8$。


title: [BalticOI 2011 Day2] Tree Mirroring

description: Let $T$ be a rooted tree (a connected undirected acylic graph), and let $S$ be a perfect copy of $T$. Construct a new graph by taking the union of $T$ and $S$, and merging the corresponding leaf nodes (but never the root). We call such a graph a tree-mirrored graph.

inputFormat: The first line of input contains two integers $N$ and $M$, the number of vertices and edges of a graph $G$. The vertices in $G$ are labeled from $1$ to $N$. The following $M$ lines describe the edges. Each such line contains two integers $x$ and $y(x≠y;1 \le x,y \le N)$, describing one edge. There will be at most one edge between any pair of vertices.

outputFormat: The first and only line of output should contain the string ``YES`` if the graph $G$ is a tree-mirrored graph, and ``NO`` otherwise.

translation:
题目描述

T是一棵树(一个连通的无向图)，并且S是一个完美的复制品(与T完全相同)。构造一个新的图T和S，并合并相应的叶节点(但绝不合并根)。我们称这样的图为树之镜像图.

输入输出格式

输入格式：

输入的第一行包含两个整数。N和M，表示图G的顶点和边数。

接下来有M行，每一行包含两个正整数：x和y (x≠y且 1≤x,y≤N)表示顶点X和Y之间有一条边。且在任意一对顶点之间最多有一条边。

输出格式：

输出只有一行，判断图G是否是一个树之镜像图，是输出yes，否则输出no。

Translated by @找寻


title: [COCI2006-2007#3] BICIKLI

background: 一场自行车比赛将要在一个遥远的地方上举行。

description:
这个地方有 $n$ 个城镇，从 $1\sim n$ 编号，其中有 $m$ 条**单向**道路连接它们。比赛将在 $1$ 号城镇开始并在 $2$ 号城镇结束。

主办方想知道，一共有多少条不同的路线？

inputFormat:
输入第一行为两个整数 $n,m$，意义如题目描述所示。

接下来的 $m$ 行，每行两个整数 $a,b$，描述一条从 $a$ 到 $b$ 的道路。

两个城镇间可以有多条道路。

outputFormat:
输出不同的路线的数量。

如果有无数条不同的路线，则输出 `inf`。

否则输出路线数对 $10^9$ 取模的结果。

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

对于 $100\%$ 的数据，$1\le n\leq 5\times 10 ^ 4$，$1\leq m\le 10^5$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T5 BICIKLI***

感谢 @[ShineEternal](https://www.luogu.com.cn/user/45475) 提供的翻译。