title: [USACO4.4] 棋盘游戏Shuttle Puzzle

description:
大小为3的棋盘游戏里有3个白色棋子，3个黑色棋子，和一个有7个格子一线排开的木盒子。3个白棋子被放在一头，3个黑棋子被放在另一头，中间的格子空着。

初始状态: WWW\_BBB

目标状态: BBB\_WWW

在这个游戏里有两种移动方法是允许的：

你可以把一个棋子移到与它相邻的空格；

你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。

大小为N的棋盘游戏包括N个白棋子，N个黑棋子，还有有2N+1个格子的木盒子。

这里是3-棋盘游戏的解，包括初始状态，中间状态和目标状态：

WWW BBB

WW WBBB

WWBW BB

WWBWB B

WWB BWB

W BWBWB

WBWBWB
BW WBWB

BWBW WB

BWBWBW
BWBWB W

BWB BWW

B BWBWW

BB WBWW

BBBW WW

BBB WWW

请编一个程序解大小为N的棋盘游戏(1 <= N <= 12)。要求用最少的移动步数实现。

inputFormat: 一个整数N。

outputFormat:
输出用移动的棋子在棋盘的位置(位置从左到右依次为1, 2, ..., 2N+1)表示的变换序列，每个数字之间以空格分隔，每行20个数(除了最后一行)。

输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；...)。


title: 小岛

type: P

background: 西伯利亚北部的寒地，坐落着由 $N$ 个小岛组成的岛屿群，我们把这些小岛依次编号为 $1$ 到 $N$。

description:
起初，岛屿之间没有任何的航线。后来随着交通的发展，逐渐出现了一些连通两座小岛的航线。例如增加一条在 $u$ 号小岛与 $v$ 号小岛之间的航线，这条航线的用时为 $e$。那么沿着这条航线，$u$ 号小岛上的人可以前往 $v$ 号小岛，同样的 $v$ 号小岛上的人也可以前往 $u$ 号小岛，其中沿着这一条航线花费的时间为 $e$。

同时，随着旅游业的发展，越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。

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

第一行有两个整数 $N$ 和 $M$，分别表示小岛的数与总操作数。

接下来的 $M$ 行，每行表示一个操作，格式如下：

`0 s t`：表示询问从 $s$ 号小岛到 $t$ 号小岛的最短用时（$1\le s\le n,~ 1\le t\le n,~ s\neq t$）。

`1 u v e`：表示新增了一条从 $u$ 号小岛到 $v$ 号小岛，用时为 $e$ 的双向航线（$1\le u\le n, ~1\le v\le n,~ u ≠ v,~ 1\le e\le 10^6$）。

outputFormat:
输出针对每一次询问，单独输出一行。

对于每一组询问来说，如果不存在可行的道路，则输出 `-1`，否则输出最短用时。


title: 飞行员配对方案问题

background: 第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

description: 一共有 $n$ 个飞行员，其中有 $m$ 个外籍飞行员和 $(n - m)$ 个英国飞行员，**外籍飞行员从 $1$ 到 $m$ 编号**，**英国飞行员从 $m + 1$ 到 $n$ 编号**。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

inputFormat:
输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 $m$ 和飞行员总数 $n$。
从第二行起到倒数第二行，每行有两个整数 $u, v$，代表外籍飞行员 $u$ 可以和英国飞行员 $v$ 配合。
输入的最后一行保证为 `-1 -1`，代表输入结束。

outputFormat:
**本题存在 Special Judge**。
请输出能派出最多的飞机数量，并给出一种可行的方案。
输出的第一行是一个整数，代表一次能派出的最多飞机数量，设这个整数是 $k$。
第 $2$ 行到第 $k + 1$ 行，每行输出两个整数 $u, v$，代表在你给出的方案中，外籍飞行员 $u$ 和英国飞行员 $v$ 配合。这 $k$ 行的 $u$ 与 $v$ 应该互不相同。

hint:
**【数据范围与约定】**

- 对于 $100\%$ 的数据，保证 $1 \leq m \leq n < 100$，$1 \leq u \leq m < v \leq n$，同一组配对关系只会给出一次。

**【提示】**

- 请注意输入的第一行先读入 $m$，再读入 $n$。

tags: 网络流与线性规划 24 题


title: 寻找平面上的极大点

description:
在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x>=a,y>=b;

用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。

给定n个点的集合，一定存在若干个点，它们不会被集合中的任何一点所支配，这些点叫做极大值点。

编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。

inputFormat: 输入包括两行，第一行是正整数n，表示是点数，第二行包含n个点的坐标，坐标值都是整数，坐标范围从0到100，输入数据中不存在坐标相同的点。

outputFormat:
按x轴坐标最小到大的顺序输出所有极大点。

输出格式为:(x1,y1),(x2,y2),...(xk,yk)

注意：输出的每个点之间有","分隔,最后一个点之后没有",",少输出和多输出都会被判错


title: 编辑距离

description:
设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

$A, B$ 均只包含小写字母。

inputFormat: 第一行为字符串 $A$；第二行为字符串 $B$；字符串 $A, B$ 的长度均小于 $2000$。

outputFormat: 只有一个正整数，为最少字符操作次数。


title: 科技庄园

background:
Life种了一块田，里面种了有一些桃树。

Life对PFT说：“我给你一定的时间去摘桃，你必须在规定的时间之内回到我面前，否则你摘的桃都要归我吃！”

PFT思考了一会，最终答应了！

由于PFT的数学不好！它并不知道怎样才能在规定的时间获得最大的价值，

由于PFT不是机器人，所以他的体力并不是无限的，他不想摘很多的桃以至体力为0，而白白把桃给Life。同时PFT每次只能摘一棵桃树，，每棵桃树都可以摘K次（对于同一棵桃每次摘的桃数相同）。每次摘完后都要返回出发点（PFT一次拿不了很多）即Life的所在地（0，0）{试验田左上角的桃坐标是（1，1）}。

PFT每秒只能移动一个单位，每移动一个单位耗费体力1(摘取不花费时间和体力,但只限上下左右移动)。

inputFormat:
第一行：四个数为N，M，TI，A 分别表示试验田的长和宽，Life给PFT的时间，和PFT的体力。

下面一个N行M列的矩阵桃田。表示每次每棵桃树上能摘的桃数。

接下来N行M列的矩阵，表示每棵桃最多可以采摘的次数K。

outputFormat: 一个数：PFT可以获得的最大的桃个数。

hint:
样例说明：

可以摘到1次（1，1）和1次（2，3），体力和时间不满足再摘桃了。

范围：

对于M，N，TI，A   10<=30%<=50  10<=100%<=100

对于K  10<=100%<=100

保证结果在long int范围内


title: 太空飞行计划问题

description:
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $ E = \{ E_1, E_2, \cdots, E_m \} $，和进行这些实验需要使用的全部仪器的集合 $ I = \{ I_1, I_2, \cdots, I_n \} $。实验 $ E_j $ 需要用到的仪器是 $ I $ 的子集 $ R_j \subseteq I $。

配置仪器 $ I_k $ 的费用为 $ c_k $ 美元。实验 $ E_j $ 的赞助商已同意为该实验结果支付 $ p_j $ 美元。W 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

inputFormat: 第 $ 1 $ 行有 $ 2 $ 个正整数 $ m $ 和 $ n $。$ m $ 是实验数，$ n $ 是仪器数。接下来的 $ m $ 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的 $ n $ 个数是配置每个仪器的费用。

outputFormat: 第 $ 1 $ 行是实验编号，第 $ 2 $ 行是仪器编号，最后一行是净收益。

hint:
感谢 @FlierKing 提供 spj

$1 \leq n, m \leq 50 $

这道题数据是在 Windows 生成的，输入数据中所有的换行都是 `\r\n` 而不是 `\n`
读入某实验需要用到的仪器编号的时候，可以这么读入。(感谢@zhouyonglong的提供)
```cpp
char tools[10000];
memset(tools,0,sizeof tools);
cin.getline(tools,10000);
int ulen=0,tool;
while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
{//tool是该实验所需仪器的其中一个
    //这一行，你可以将读进来的编号进行储存、处理，如连边。
    if (tool==0)
        ulen++;
    else {
        while (tool) {
            tool/=10;
            ulen++;
        }
    }
    ulen++;
}
```

tags: 网络流与线性规划 24 题


title: 试题库问题

description:
问题描述：

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

编程任务：

对于给定的组卷要求，计算满足要求的组卷方案。

inputFormat:
第一行有两个正整数 $k$ 和 $n$。$k$ 表示题库中试题类型总数，$n$ 表示题库中试题总数。

第二行有 $k$ 个正整数，第 $i$ 个正整数表示要选出的类型 $i$ 的题数。这 $k$ 个数相加就是要选出的总题数 $m$。

接下来的 $n$ 行给出了题库中每个试题的类型信息。每行的第一个正整数 $p$ 表明该题可以属于 $p$ 类，接着的 $p$ 个数是该题所属的类型号。

outputFormat:
输出共 $k$ 行，第 $i$ 行输出 `i: ` 后接类型 $i$ 的题号。
如果有多个满足要求的方案，只要输出一个方案。
如果问题无解，则输出`No Solution!`。

hint:
$2\leq k \leq 20$，$k \leq n \leq 10^3$。

---

感谢 @PhoenixEclipse 提供 spj

tags: 网络流与线性规划 24 题


title: 最小路径覆盖问题

description: 给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $V$ 中每个定点恰好在 $P$ 的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。$P$ 中路径可以从 $V$ 的任何一个定点开始，长度也是任意的，特别地，可以为 $0$。$G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖。设计一个有效算法求一个 DAG（有向无环图）$G$ 的最小路径覆盖。

inputFormat: 第一行有两个正整数 $n$ 和 $m$。$n$ 是给定 DAG（有向无环图）$G$ 的顶点数，$m$ 是 $G$ 的边数。接下来的 $m$ 行，每行有两个正整数 $i$ 和 $j$ 表示一条有向边 $(i,j)$。

outputFormat: 从第一行开始，每行输出一条路径。文件的最后一行是最少路径数。

hint:
对于 $100\%$ 的数据，$1\leq n\leq 150$，$1\leq m\leq 6000$。

由 @FlierKing 提供 SPJ

tags: 网络流与线性规划 24 题


title: 魔术球问题

description:
假设有 $n$ 根柱子，现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1$，$2$，$3$，...的球“

1. 每次只能在某根柱子的最上面放球。

2. 同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球。例如，在 $4$ 根柱子上最多可放 $11$ 个球。

对于给定的 $n$，计算在 $n$ 根柱子上最多能放多少个球。

inputFormat: 只有一行一个整数 $n$，代表柱子数。

outputFormat:
**本题存在 Special Judge**。

请将 $n$ 根柱子上最多能放的球数以及相应的放置方案输出。

输出的第一行是球数。

接下来的 $n$ 行，每行若干个整数，代表一根柱子上的球的编号，数字间用单个空格隔开。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 55$。

tags: 网络流与线性规划 24 题


title: 最长不下降子序列问题

description:
给定正整数序列 $x_1 \ldots, x_n$。

1. 计算其最长不下降子序列的长度 $s$。
2. 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。
3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个**不同的**长度为 $s$ 的不下降子序列。

令 $a_1, a_2, \ldots, a_s$ 为构造 $S$ 时所使用的下标，$b_1, b_2, \ldots, b_s$ 为构造 $T$ 时所使用的下标。且 $\forall i \in [1,s-1]$，都有 $a_i \lt a_{i+1}$，$b_i \lt b_{i+1}$。则 $S$ 和 $T$ **不同**，当且仅当 $\exists i \in [1,s]$，使得 $a_i \neq b_i$。

inputFormat: 第一行有一个正整数 $n$，表示给定序列的长度。接下来的一行有 $n$ 个正整数$x_1, ..., x_n$。

outputFormat:
- 第 1 行是最长不下降子序列的长度 $s$。
- 第 2 行是可取出的长度为 $s$ 的不下降子序列个数。
- 第 3 行是允许在取出的序列中多次使用 $x_1$ 和 $x_n$ 时可取出的长度为 $s$ 的**不同的**不下降子序列个数。

tags: 网络流与线性规划 24 题


title: 猴子上树

description:
在猴村有一条笔直的山路，这条山路很窄，宽度忽略不计。有 $n$ 只猴子正站在山路上静静地观望今天来参加比赛的各位同学。用一个正整数 $X_i$ 表示第 $i$ 只猴子所站位置，任意两只猴子的所站位置互不相同。在这条山路的 $m$ 个位置上种着一些高大的树木，正整数 $Y_j$ 表示第 $j$ 棵树木所在的位置，任意两棵树的位置互不相同。

正当猴子们聚精会神的欣赏各位高超编程技能 聚精会神的欣赏各位高超编程技能时，一只老虎大摇摆的走了过来。猴子们吓得直冒冷汗，第一反应就是找棵大树爬上去这样能避免被老虎咬死或者吃掉（不考虑老虎上树问题）。

在位置 $a$ 的猴子跑到在位置 $b$ 的大树上，需要消耗能量为 $|a-b|$（即 $a-b$ 的绝对值）。为了尽可能有效利用这些大树避难，每棵上至少要一只猴子。
请编程计算 $n$ 只猴子全部上树最少需要消耗多少能量？

inputFormat:
输入共 4 行。

第 1 行一个整数 $n$，表示猴子的数量。

第 2 行 $n$ 个整数，第 $i$ 个整数 $X_i$ 表示第 $i$ 只猴子所在的位置。

第 3 行一个整数 $m$，表示大树的数量。

第 4 行 $m$ 个整数，第 $j$ 个整数表示第 $j$ 棵大树所在的位置。

outputFormat: 输出一行，一个整数表示 $n$ 只猴子全部上树最少需要消耗的能量。


title: 函数

background: Alice 和 Bob 玩游戏。

description:
Alice 给出一个 $1$~$n$ 的排列表示一个函数 $y=f(x)$，即给出的第 $i$ 个数字即为 $f(i)$。

现在 Bob 需要给出一个字典序尽可能小的函数 $y=g(x)$，使得对于任意 $i$，$f(g(i))=g(f(i))$。

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

第二行 $n$ 个整数，依次表示 $f(1),f(2) \cdots f(n)$。

outputFormat: 共一行，$n$ 个整数，依次表示 $g(1),g(2) \cdots g(n)$。


title: 漂亮字串

description: Caima认为O和X是最优美的两个字母，由O、X组成的串是最优美的串。在这些最优美的串中，如果任意只包含X的字串，长度不超过maxX，任意只包含O的子串，长度不超过maxO，且整个串最多有countO个O，countX个X。那么这个就是超级优美无敌串。现在Caima想知道最长的超级优美无敌串有多长，希望你告诉他。

inputFormat:
输入包含多行，至文件结束为止；

每行四个数，依次是CountO、CountX、maxO、maxX.

CountO、CountX、maxO、maxX均大于等于0小于等于1000000

outputFormat: 每组数据输出一行，一个数表示最长的超级优美无敌串的长度


title: 【数学1】小浩的幂次运算

description:
幂次运算让小浩觉得有些烦，最近他碰到了一些问题。
他需要求出所有 $w^i$ 使得 $l \le w^i \le r$ ，于是他找到了你。

inputFormat: 输入为一行，有三个整数 $l,r,w$。

outputFormat:
输出为一行，输出所有满足条件的数字，用空格分开。
如果没有满足条件的数字，则输出 $-1$。


title: [USACO16JAN] Build Gates S

description:
FarmerJohn 打算在他农场的一部分，建设一个围栏。但是因为没有认真做事，建造完成后，围栏变成一个很奇怪的形状。

具体来说，FJ 从 $(0,0)$ 出发，走了 $N$ 步，每步移动一单位（向东、向南、向西或向北）。

他走过的每一步，都会留下一段单位长度的围栏。例如，如果他的第一步向北，他建造一单位从 $(0,0)$ 到 $(0,1)$ 的围栏。

FJ 可能重复到达点多次，他也可能重复建造一段围栏多次。如果他的路径穿过一段已经建成的围栏，他的围栏也有可能会有交叉。

不用说，FJ 看到完成的围栏时，一定很沮丧。特别的，他发现一些区域被围栏封闭起来，从而无法到达。FJ 想在围栏上，安装一些门来解决这个问题。

门可以安装在任意一段单位长度（注：必须是之前走过的某一步）的围栏上，从而可以穿越这段围栏的两侧。

请计算 FJ 最少需要安装多少个门，才能保证农场上任意区域到任意区域都可到达。

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

第二行包含一个长度为 $N$ 的字符串，描述 FJ 的路径。每个字符为 $\tt N$（北），$\tt E$（东），$\tt S$（南），或 $\tt W$（西）。

outputFormat: 输出一个整数，表示为了保证农场所有区域的连通性，FJ 最少需要安装多少个门。

hint:
注意，如果农场初始连通，答案就是 $0$。

### 数据范围

$1\le n\le 1000$。


title: 众数

background: Alice 和 Bob 玩游戏。

description:
Alice 现在有一个序列 $a_1,a_2,...a_n$。

现在她需要 Bob 支持询问一个区间内的众数,还要支持修改一个位置的 $a_i$。

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

第二行 $n$ 个整数，表示 $a_1,...,a_n$。

接下来 $m$ 行，每行三个整数 $flag,x,y$。

如果 $flag=0$，表示询问 $\big[x,y\big]$ 区间内的众数，如果有多个输出较小的。

如果 $flag=1$，表示将 $a_x$ 改为 $y$。

outputFormat: 对于每个 $flag=0$ 的询问，每行输出一个整数表示答案。

hint:
对于 $100\%$ 的数据 $n,m \le 1000$。

对于查询操作满足 $x\le y$。

任意时刻 $0<a_i\le 10^9$。


title: 机器人路径规划问题

background:
**通过套取数据而直接“打表”过题者，是作弊行为，发现即棕名。**

本题**不保证**存在**可以通过满足本题数据范围的任意数据**做法。由于测试数据过水，可以通过此题的程序不一定完全正确（算法时间复杂度错误、或不保证正确性）。本题题目和数据仅供参考。本题不接受添加 hack 数据。

本题为错题。**不建议尝试或提交本题。**[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

description: 机器人 Rob 可在一个树状路径上自由移动。给定树状路径 $T$ 上的起点 $s$ 和终点 $t$，机器人 Rob 要从 $s$ 运动到 $t$。树状路径 $T$ 上有若干可移动的障碍物。由于路径狭窄，任何时刻在路径的任何位置不能同时容纳 $2$ 个物体。每一步可以将障碍物或机器人移到相邻的空顶点上。设计一个有效算法用最少移动次数使机器人从 $s$ 运动到 $t$。对于给定的树 $T$，以及障碍物在树 $T$ 中的分布情况。计算机器人从起点 $s$ 到终点 $t$ 的最少移动次数。

inputFormat:
第 $1$ 行有 $3$ 个正整数 $n$，$s$ 和 $t$，分别表示树 $T$ 的顶点数，起点 $s$ 的编号和终点 $t$ 的编号。

接下来的 $n$ 行分别对应于树 $T$ 中编号为 $0,1,\cdots,n-1$ 的顶点。每行的第 $1$ 个整数 $h$ 表示顶点的初始状态，当 $h=1$ 时表示该顶点为空顶点，当 $h=0$ 时表示该顶点为满顶点，其中已有 $1$ 个障碍物。第 $2$ 个数 $k$ 表示有 $k$ 个顶点与该顶点相连。接下来的 $k$ 个数是与该顶点相连的顶点编号。

outputFormat: 程序运行结束时，将计算出的机器人最少移动次数输出。如果无法将机器人从起点移动到终点，输出 `No solution!`。

hint: 题目中出现的数字均小于 $1000$。

tags: 启发式迭代加深搜索,IDA*

tags: 网络流与线性规划 24 题


title: 方格取数问题

description: 有一个 $m$ 行 $n$ 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

inputFormat:
第一行是两个用空格隔开的整数，分别代表方格图的行数 $m$ 和列数 $n$。

第 $2$ 到第 $(m + 1)$ 行，每行 $n$ 个整数，第 $(i + 1)$ 行的第 $j$ 个整数代表方格图第 $i$ 行第 $j$ 列的的方格中的数字 $a_{i, j}$。

outputFormat: 输出一行一个整数，代表和最大是多少。

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

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 100$，$1 \leq a_{i, j} \leq 10^5$。

**提示**

请注意输入的第一行先读入 $m$ 再读入 $n$。

tags: 网络流与线性规划 24 题


title: 航空路线问题

description:
给定一张航空图，图中顶点代表城市，边代表两城市间的直通航线，并且不存在任何两个城市在同一条经线上。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

1. 从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。

2. 除起点城市外，任何城市只能访问一次。

对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

inputFormat:
输入的第一行是用空格隔开的两个整数，分别代表航空图的点数 $n$ 和边数 $v$。

第 $2$ 到第 $(n + 1)$ 行，每行一个字符串，第 $(i + 1)$ 行的字符串代表从西向东第 $i$ 座城市的名字 $s_i$。

第 $(n + 2)$ 到第 $(n + v + 1)$ 行，每行两个字符串 $x, y$，代表城市 $x$ 和城市 $y$ 之间存在一条直通航线。

outputFormat:
**本题存在 Special Judge**。

请首先判断是否存在满足要求的路线，若存在，请给出一种旅行的方案。

如果存在路线，输出格式为：

- 请在第一行输出一个整数 $m$，代表途径最多的城市数。
- 在第 $2$ 到第 $(m + 2)$ 行，每行一个字符串，第 $(i + 1)$ 行的字符串代表旅行路线第 $i$ 个经过的城市的名字。请注意第 $1$ 和第 $m$ 个城市必然是出发城市名。

否则请输出一行一个字符串 ``No Solution!``。

samples:
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

samples:
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

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

对于 $100\%$ 的数据，保证 $1 \leq n < 100$，$1 \leq v \leq \frac{n \times (n - 1)}{2}$，$s_i$ 的长度不超过 $15$，且仅可能包含大小写字母与数字，$x, y$ 一定是输入中给出的城市名，且不会有同一组 $x, y$ 被给出两次。

tags: 网络流与线性规划 24 题


title: 软件补丁问题

description:
T 公司发现其研制的一个软件中有 $n$ 个错误，随即为该软件发放了 $m$ 个补丁程序。

每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。

换句话说，对于任意一个补丁 $i$，都有四个与之相应的集合 $B1_i,B2_i,F1_i$ 和 $F2_i$。仅当软件包含 $B1_i$ 中的所有错误，而不包含 $B2_i$ 中的任何错误时，才可以使用补丁 $i$。补丁 $i$ 将修复软件中的某些错误集合 $F1_i$，而同时加入另一些错误 $F2_i$。另外，运行每个补丁都耗费一定的时间。

试设计一个算法，利用 T 公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 $n$ 个错误和 $m$ 个补丁程序，找到总耗时最少的软件修复方案。

inputFormat:
第一行有两个正整数 $n$ 和 $m$。$n$ 表示错误总数，$m$表示补丁总数。

接下来 $m$ 行给出了 $m$ 个补丁的信息。每行包括一个正整数，表示运行补丁程序 $i$ 所需时间，以及两个长度为 $n$ 的字符串。中间用一个空格符隔开。

第一个字符串中，如果第 $k$ 个字符为 ```+```，则表示第 $k$ 个错误属于 $B1_i$。若为 ```-```，则表示第 $k$ 个错误属于 $B2_i$。若为 ```0```，则第 $k$ 个错误既不属于 $B1_i$ 也不属于 $B2_i$，即软件中是否包含第 $k$ 个错误并不影响补丁 $i$ 的可用性。

第二个字符串中，如果第 $k$ 个字符为 ```-```，则表示第 $k$ 个错误属于 $F1_i$。若为 ```+```，则表示第 $k$ 个错误属于 $F2_i$。若为 ```0```，则第 $k$ 个错误既不属于 $F1_i$ 也不属于 $F2_i$，即软件中是否包含第 $k$ 个错误不会因使用补丁 $i$ 而改变。

outputFormat: 程序运行结束时，将总耗时数输出。如果问题无解，则输出 `0`。

tags: 网络流与线性规划 24 题


title: [CTSC1999] 家园 / 星际转移问题

description:
由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。

现有 $n$ 个太空站位于地球与月球之间，且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而太空船的容量是有限的，第 $i$ 艘太空船只可容纳  $h_i$ 个人。每艘太空船将周期性地停靠一系列的太空站，例如 $(1,3,4)$ 表示该太空船将周期性地停靠太空站 $134134134\dots$。每一艘太空船从一个太空站驶往任一太空站耗时均为 $1$。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

inputFormat:
输入的第一行是三个用空格隔开的整数，分别代表太空站个数 $n$，太空船个数 $m$ 和地球上的人数 $k$。

第 $2$ 到第 $(m + 1)$ 行，每行给出一艘太空船的信息，第 $(i + 1)$ 行的第一个整数 $h_i$ 代表第 $i$ 艘太空船可容纳的人数。随后有一个整数 $r_i$，代表第 $i$ 艘太空船停靠的站点数。之后有 $r_i$ 个整数，依次代表该太空船停靠站点的编号 $S_{i, j}$，其中太空站自 $1$ 至 $n$ 编号，地球编号为 $0$，月球编号为 $-1$。

outputFormat: 输出一行一个整数，代表将所有人转移到月球上的最短用时。若无解则输出 $0$。

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

对于 $100\%$ 的数据，保证：

- $1 \leq n \leq 13$。
- $1 \leq m \leq 20$。
- $1 \leq k \leq 50$。
- $1 \leq r_i \leq n + 2$。
- $-1 \leq S_{i, j}\leq n$。

tags: 网络流与线性规划 24 题


title: [AHOI2016初中组] 自行车比赛

description:
小雪非常关注自行车比赛，尤其是环滨湖自行车赛。一年一度的环滨湖自行车赛，需要选手们连续比赛数日，最终按照累计得分决出冠军。今年一共有 $N$ 位参赛选手。每一天的比赛总会决出当日的排名，第一名的选手会获得 $N$ 点得分，第二名会获得 $N-1$ 点得分，第三名会获得 $N-2$ 点得分，依次类推，最后一名会获得 $1$ 点得分。保证没有选手会排名相同。

在之前的数日较量中，$N$ 位选手已经分别累计了一些分数。现在即将开始的是最后一天的比赛。小雪希望知道有多少位选手还有可能获得最终的冠军，也就是说还有多少选手有可能通过最后一天的比赛获得累计总分第一名。

inputFormat:
第一行输入一个整数 $N$，表示参赛选手总数，保证 $3\le N\le 3\times 10^5$。

之后 $N$ 行，其中第 $i$ 行输入一个整数 $B_i$ 表示第 $i$ 位选手已经获得的累计分数，满足 $0\le B_i\le 2\times 10^6%$。

outputFormat: 输出只有一行，只输出一个整数，表示有多少位选手有可能获得最终的冠军。


title: [AHOI2016初中组] 游戏

description:
小雪与小可可正在玩一种数字游戏。他们准备了 $n$ 张卡片，每一张卡片上都有一个整数。游戏开始后，小雪会先选择一个不小于 $a$ 且不大于 $b$ 的整数 $t$，并告诉小可可这个数字 $t$ 是多少。之后小可可会挑出恰好 $k$ 张卡片，并将这 $k$ 张卡片上的数字相加，得到的和数记为 $m$。

小雪希望 $t$ 和 $m$ 差的绝对值尽可能大，而小可可却希望 $t$ 和 $m$ 差的绝对值尽可能小。在游戏开始前，他们二人都知道 $n$， $a$， $b$ 和 $k$ 是多少，也知道每一张卡片上的数字是多少。在小雪决定了 $t$ 的大小后，不能再修改，之后才由小可可挑选纸牌。

小雪希望知道，在二人都尝试最优策略的情况下， $t$ 和 $m$ 差的绝对值最大可以有多大？

inputFormat:
输入有两行。

第一行有 4 个整数 $n$， $k$， $a$ 和 $b$，分别满足 $1 \le k \le n \le 250$ 且 $0 \le a \le b \le 75000$。

第二行有 $n$ 个整数，依次为 $x_1$ 到 $x_n$，给出了每一张卡片上的数字。

每一张卡片上的数字 $x_i$ 都满足 $0\le x_i \le 300$。

outputFormat: 输出一行，只有一个整数，表示 $t$ 和 $m$ 差的绝对值最大可以有多大。

hint:
对于 30% 的数据， $1\le k\le n\le 20$ 且 $0\le a\le b\le   6000$。

对于 80% 的数据， $1\le k\le n\le 65$ 且 $0\le a\le b\le   19650$。

对于 100% 的数据， $1\le k\le n\le 250$ 且 $0\le a\le b\le 75000$。


title: [AHOI2016初中组] 迷宫

description:
小雪和小可可被困在了一个无限大的迷宫中。

已经知道这个迷宫有 $N$ 堵环状的墙，如果把整个迷宫看作是一个二维平面，那么每一堵墙都是平面上一个圆。**任意两个圆不相交，不重合，也不会相切，但有可能相互包含**。小雪和小可可分别被困在了 $2$ 个不同的位置，且保证他们的位置与这些圆不重合。

他们只有破坏墙面才能穿过去。

小雪希望知道，如果他们要相见，至少要破坏掉多少堵墙？他们可以在任何位置相见。

inputFormat:
第一行有一个整数 $N$，表示有多少堵墙。

之后 $N$ 行，每一行有 $3$ 个整数 $x, y, r$，表示有一堵环状的墙是以 $(x,y)$ 为圆心，$r$ 为半径的。

再下一行有一个整数 $Q$，表示有多少组询问。

之后 $Q$ 行，每一行有 $4$ 个整数 $a, b, c, d$，给出了一组询问，表示小雪所在的位置为 $(a,b)$，小可可所在的位置为 $(c,d)$。

outputFormat: 输出 $Q$ 行，对应 $Q$ 次询问，每一行输出一个整数，表示最少需要破坏掉多少堵墙才能相见。


title: [AHOI2016初中组] 黑白序列

background: 小可可知道小雪喜欢什么样子的黑白序列。

description:
首先，对于任何正整数 $n$，如果一个黑白序列是由连续 $n$ 个黑接上连续 $n$ 个白，那一定是小雪喜欢的黑白序列。

其次，如果有两个黑白序列小雪都喜欢，那么把这两个序列接起来得到的新序列，小雪也一定喜欢。小雪不会喜欢更多别的黑白序列。

例如，如果用字符 `B` 和 `W` 分别表示黑色，`W` 表示白色，那么 `BW`，`BBWW`，`BBBWWW` 以及 `BWBW`，`BWBBWW`，`BWBBWWBW` 都是小雪喜欢的黑白序列。而 `W`，`WW`，`WB`，`WBBW` 以及 `BBBWW` 都不是小雪喜欢的黑白序列。

现在小可可准备了一个未完成的黑白序列，用 `B` 和 `W` 表示黑色和白色，用 `?` 表示尚未确定，他希望知道一共有多少种不同的方法，在决定了每一个 `?` 位置的颜色后可以得到一个小雪喜欢的黑白序列。

两个方案若有至少一位不同才能算是不同的，不是 `?` 的位置是不允许修改的。

答案对 $10^9 + 9$（一个素数）取模。

inputFormat: 第一行输入一个长度大于零的字符串，由 `B`，`W` 和 `?` 组成。

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

hint:
#### 样例输入输出 1 解释
有六种合法方案，依次得到的最终黑白序列为：

- `BBBBWWWW`，
- `BBBWWWBW`，
- `BWBBBWWW`，
- `BWBBWWBW`，
- `BWBWBBWW`，
- `BWBWBWBW`。

#### 数据规模与约定

- 对于 $20\%$ 的数据，输入长度不超过 $22$。
- 对于 $60\%$ 的数据，输入长度不超过 $5000$。
- 对于 $100\%$ 的数据，输入长度不超过 $500000$，保证序列中只含 `W`，`B`，`?` 三种字符，其中 `?` 是英文字符。


title: 钦定

description:
小 S 拿到了复赛参赛表，表上的选手是由 $A$ 位神犇与 $B$ 位蒟蒻间隔、循环构成的。

比如 $A=2$，$B=3$ 时，选手 $1,2,6,7,11,12\dots$ 是神犇，选手 $3,4,5,8,9,10,13,14,15\dots$是蒟蒻。

现在小 S 钦定了一些选手是神犇，蒟蒻，但她不能构造出这样的 $A,B$，你能帮帮她吗？

inputFormat:
每个测试点多组数据。

每组数据第一行两个整数 $N,M$。

第二行为 N 名选手编号 $a_1,a_2,\dots,a_N$。即小 S 把他们钦定为神犇。

第三行为 M 名选手编号 $b_1,b_2,\dots,b_M$。即小 S 把他们钦定为蒟蒻。

outputFormat: 对于每组数据，输出满足题意的两个整数 $A,B$（用空格隔开），并且使得 $A$ 最小的情况下 $B$ 最小。 如果没有符合条件的 $A,B$，请输出 `NO`。


title: 制杖题

description: 求不大于 $m$ 的、质因数集与给定质数集有交集的自然数之和。

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

第二行，$n$ 个整数，表示质数集内的元素 $p_i$。

outputFormat: 一个整数，表示答案，对 $376544743$ 取模。


title: 小A的礼物

background: ** 数据已更新（2018-3-2） **

description:
小 A 去学校参加活动辣，学校会发礼物哦，学校有很多礼物点。

每一个礼物点都有去别的礼物点的道路和各种种类的礼物。

为了防止多次领礼物，这些道路都是单向的道路，并且没有环。

而且对于每条边连接 $a$，$b$ 点，如果删去这条边之后，存在点 $c$ 可以到达 $a$，也能到达 $b$，那么这条边就不会存在于路径中。

并且除了点 $1$ 之外，所有点有且只有一条入边。

小 A 想知道，对于点 $S$ 能到达的所有点（包括本身），有多少种不同的礼物？

inputFormat:
第一行是礼物点的数量$n$ ($n \le 100000$)

接下来 1 行 $n-1$ 个数，分别代表点 $2,\cdots, n$ 的入点

接下来 1 行 $n$ 个数，代表每个节点的礼物编号

接下来一行是 $m$，代表询问数量

接下来 $m$ 行，每行一个节点编号，代表询问的节点编号

outputFormat: 对于每个询问，输出礼物总数


title: 染色

background:
此题时限2s

此题时限2s

此题时限2s

description: 有一个 $n$ 行 $m$ 列的格点图，你需要给每个点上染上 $k$ 种颜色中的一种，要求没有两个相邻点颜色相同。给定第一行与最后一行的染色，试求总染色方案数。

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

第二行 $m$ 个整数，第一行的染色方案，用 $0\sim k-1$ 表示每种颜色。

第三行 $m$ 个整数，最后一行的染色方案，用 $0\sim k-1$ 表示每种颜色。

outputFormat: 一个整数，表示答案，对 $376544743$ 取模。


title: 泡芙

background: 此题空间限制 $256$ MB，保证系统栈空间与内存限制大小相同。

description: 火星猫经过一番努力终于到达了冥王星。他发现冥王星有 $N$ 座城市，$M$ 条无向边。火星猫准备出发去找冥王兔，他听说有若干泡芙掉落在一些边上，他准备采集一些去送给冥王兔。但是火星猫的火星光环和冥王星相生相克，当火星猫走过一条路之后，这条路就不能再走了。如果冥王兔吃不到泡芙，他们就不能嘿嘿嘿了。所以告诉你火星猫和冥王兔的位置，请问冥王兔能不能吃到泡芙。

inputFormat:
第一行 $N,M$ 表示点数和边数。

接下来 $M$ 行每行 $X,Y,Z$ 表示 $X$ 到 $Y$ 有一条无向边，$Z=1$ 表示有泡芙，$Z=0$ 表示没有

接下来一行是 $Q$，表示有 $Q$ 组询问。

每行 $S,T$ 表示火星猫和冥王兔的位置。

outputFormat: 对于每组询问输出 `YES` 或 `NO`。


title: [USACO15DEC] Switching on the Lights S

background:
来源：usaco-2015-dec

Farm John 最近新建了一批巨大的牛棚。这些牛棚构成了一个 $N \times N$ 的矩形网络 $(1 < N < 100)$。

然而 Bessie 十分怕黑，他想计算可以把多少个牛棚的灯打开。

description:
有 $N \times N$ 个房间，组成了一张 $N \times N$ 的网格图，Bessie 一开始位于左上角 $(1,1)$，并且只能上下左右行走。

一开始，只有 $(1,1)$ 这个房间的灯是亮着的，Bessie 只能在亮着灯的房间里活动。

有另外 $M$ 条信息，每条信息包含四个数 $a,b,c,d$，表示房间 $(a,b)$ 里有房间 $(c,d)$ 的灯的开关。

请计算出最多有多少个房间的灯可以被打开。

outputFormat: 一个数，最多可以点亮的房间数。

hint:
Bessie 可以使用 $(1,1)$ 的开关打开 $(1,2),(1,3)$ 的灯，然后走到 $(1,3)$ 并打开 $(2,1)$ 的灯，走到 $(2,1)$ 并打开 $(2,2)$ 的灯。$(2,3)$ 的开关无法到达。因此可以点亮 $5$ 个房间。

Here, Bessie can use the switch in (1,1) to turn on lights in (1,2) and (1,3). She can then walk to (1,3) and turn on the lights in (2,1)，from which she can turn on the lights in (2,2). The switch in (2,3) is inaccessible to her, being in an unlit room. She can therefore illuminate at most 5 rooms.


title: 小B的询问

description:
小B 有一个长为 $n$ 的整数序列 $a$，值域为 $[1,k]$。
他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$，求：
$$\sum\limits_{i=1}^k c_i^2$$

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。
小B请你帮助他回答询问。

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

第二行 $n$ 个整数，表示 小B 的序列。

接下来的 $m$ 行，每行两个整数 $l,r$。

outputFormat: 输出 $m$ 行，每行一个整数，对应一个询问的答案。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n,m,k \le 5\times 10^4$。


title: Facer的程序

description:
Facer 是一个萌萌哒的码农

他写了N个程序

程序之间是有 有机的联系的

任意两个程序恰好由一条联系链连在一起

具体来说，对于程序 a,b ， 存在且仅存在一个序列a,x1,x2....xn,b

使得a,x1有联系,x1,x2有联系.....

符合这样的一组程序称为程序块

现在已知一个程序块的程序之间的联系

询问它有多少个子程序块

即取出一个程序子集S，使得S也满足上述条件

inputFormat:
第一行N

接下来N-1行，每行两个数，代表有联系的两个程序

outputFormat:
输出有多少个子程序块

对1000000007取模


title: Facer 帮父亲

background: Facer 可是一个孝顺的孩纸呦

description:
Facer 的父亲是一名经理，现在总是垂头丧气的。

Facer 问父亲，怎么啦？父亲说，公司出了点问题啊。

公司管理着 $n$ 个风景点，每个风景点都有不少人来参观。

可是现在！人民投诉票价太高了，他不得不调整票价。

具体来说，第 $i$ 个景点如果票价是 $x$，来的人数就是 $\max( (a_i - b_i\times x),0 )$。

你需要分配每个景点的门票，使得所有景点的门票总价之和不超过 $k$，求最大的收益。

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

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

outputFormat: 一行，表示最大的收益。


title: Facer的魔法

background: Facer 误闯入禁地，学会了魔法。

description:
Facer 闯入禁地之后，遇到了对手。

具体来说，Facer 魔法是一串数字。

但是 Facer 能力有限，这串数字只能从给定的 $n$ 个数中选择，能产生的魔法值为选择出的这些数字的平均数。

他的对手不会像 Facer 这样的强大的魔法，但是他会克制招数，即从 Facer 选出的数字中找出中位数，便是他的魔法值。

求 Facer 最多能克制对方多少点魔法。

一句话题意：给你 $n$ 个数，你可以选若干个数，使得平均数减中位数最大。

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

第二行 $n$ 个数如题。

outputFormat: Facer 能克制对方多少魔法值，精确到两位小数。


title: 巧克力

background: 王 7 的生日到了，他的弟弟准备送他巧克力。

description: 有一个被分成 $n\times m$ 格的巧克力盒，在 $(i,j)$ 的位置上有 $a_{i,j}$ 块巧克力。就在送出它的前一天晚上，有老鼠夜袭巧克力盒，某些位置上被洗劫并且穿了洞。所以，你——王 7 的弟弟王 9，必须从这个满目苍夷的盒子中切割出一个矩形巧克力盒，其中不能有被老鼠洗劫过的格子且使这个盒子里的巧克力尽量多。

inputFormat: 第一行有两个整数 $n,m$。第 $i+1$ 行的第 $j$ 个数表示 $a_{i,j}$。如果这个数为 $0$，则表示这个位置的格子被洗劫过。

outputFormat: 输出最大巧克力数。

hint:
**样例解释**

第三行前三列 `10 3 4` 组成的矩形的巧克力数最大。

**数据范围**

对于全部的数据，$1\le n,m\le 300$，$0\le a_{i,j} \le 255$。


title: [APIO/CTSC2007] 数据备份

description:
你在一家 IT 公司为大型写字楼或办公楼的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。

然而，网络电缆的费用很高。当地电信公司仅能为你提供 $K$ 条网络电缆，这意味着你仅能为 $K$ 对办公楼（或总计 $2K$ 个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 $2K$ 个办公楼一定是相异的）。

此外，电信公司需按网络电缆的长度（公里数）收费。因而，你需要选择这 $K$ 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 $K$ 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。

下面给出一个示例，假定你有 $5$ 个客户，其办公楼都在一条街上，如下图所示。这 $5$ 个办公楼分别位于距离大街起点 $1\rm km$, $3\rm km$, $4\rm km$, $6\rm km$ 和 $12\rm km$ 处。电信公司仅为你提供 $K=2$ 条电缆。

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

上例中最好的配对方案是将第 $1$ 个和第 $2$ 个办公楼相连，第 $3$ 个和第 $4$ 个办公楼相连。这样可按要求使用 $K=2$ 条电缆。第 $1$ 条电缆的长度是 $\rm 3km-1km = 2km$，第 2 条电缆的长度是 $\rm 6km―4km = 2 km$。这种配对方案需要总长 $4\rm km$ 的网络电缆，满足距离之和最小的要求。

inputFormat:
输入文件的第一行包含整数 $N$ 和 $K$，其中 $N$（$1\leq N \leq 10^5$）表示办公楼的数目，$K$（$\displaystyle 1\leq K \leq \frac{N}{2}$）表示可利用的网络电缆的数目。

接下来的 $N$ 行每行仅包含一个整数 $s$（$0\leq s \leq 10^9$）, 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

outputFormat: 输出文件应当由一个正整数组成，给出将 $2K$ 个相异的办公楼连成 $K$ 对所需的网络电缆的最小总长度。

hint:
$30\%$ 的输入数据满足 $N\leq 20$。

$60\%$ 的输入数据满足 $N\leq 10^4$。


title: [APIO2007] 风铃

description:
你准备给弟弟 Ike 买一件礼物，但是，Ike 挑选礼物的方式很特别：他只喜欢那些能被他排成有序形状的东西。

你准备给 Ike 买一个风铃。风铃是一种多层的装饰品，一般挂在天花板上。

每个风铃都包含一些由竖直线连起来的水平杆。每根杆的两头都有线连接，下面或者挂着另一根水平杆，或者挂着一个玩具。下面是一个风铃的例子：

为了满足弟弟，你需要选一个满足下面两个条件的风铃：

1. 所有的玩具都在同一层(也就是说，每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。
2. 对于两个相差一层的玩具，左边的玩具比右边的玩具要更靠下一点。

风铃可以按照下面的规则重新排列：任选一根杆，将杆两头的线“交换”。也就是解开一根杆左右两头的线，然后将它们绑到杆的另一头。这个操作不会改变更下面的杆上线的排列顺序。

正在训练信息学奥林匹克的你，决定设计一个算法，判断能否通过重新排列，将一个给定的风铃变为 Ike 喜欢的样子。

考虑上面的例子，上图中的风铃满足条件 $1$，却不满足条件 $2$ ——最左边的那个玩具比它右边的要高。

但是，我们可以通过下面的步骤把这个风铃变成一个 Ike 喜欢的：

 1.   第一步，将杆 $1$ 的左右两边交换，这使得杆 $2$ 和杆 $3$ 的位置互换，交换的结果如下图所示：

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

 2.   第二步，也是最后一步，将杆 $2$ 的左右两边交换，这使得杆 $4$ 到了左边，原来在左边的玩具到了右边，交换的结果发下图所示：

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

现在的这个风铃就满足 Ike 的条件了。

你的任务是：给定一个风铃的描述，求出最少需要多少次交换才能使这风铃满足 Ike 的条件(如果可能)。

inputFormat:
输入的第一行包含一个整数 $n$，表示风铃中有多少根杆。

接下来的 $n$ 行描述杆的连接信息。这部分的第 $i$ 行包含两个由空格分隔的整数 $l_i$ 和 $r_i$，描述杆 $i$ 的左右两边悬挂的东西。如果挂的是一个玩具，则对应的值为``-1``，否则为挂在下面的杆的编号。

outputFormat: 输出仅包含一个整数。表示最少需要多少次交换能使风铃满足 Ike 的条件。如果不可能满足，输出``-1``。

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

- 对于 $100\%$ 的数据，满足 $1 \le n \le 10^5$，$-1 \leq l_i, r_i \leq n$，$l_i, r_i \neq 0$。


title: [APIO2007] 动物园

description:
新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，包含一大圈围栏，每个围栏里有一
种动物。如下图所示：

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

你是动物园的公共主管。你要做的是，让每个来动物园的人都尽可能高兴。今天有一群小朋友来动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有的动物有一些小朋友喜欢，有的动物有一些小朋友害怕。如，Alex 喜欢可爱的猴子和考拉，而害怕拥牙齿锋利的狮子。而 Polly 会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你不能移走太多动物，否则小朋友们就没有动物可看了。每个小朋友站在大围栏圈的外面，可以看到连续的 $5$ 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当下面两处情况之一发生时，小朋友就会高兴：
- 至少有一个他害怕的动物被移走
- 至少有一个他喜欢的动物没被移走

例如，考虑下图中的小朋友和动物：

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

- 假如你将围栏 $4$ 和 $12$ 的动物移走。Alex 和 Ka-Shu 将很高兴，因为至少有一个他们害怕的动物被移走了。这也会使 Chaitanya 高兴，因为他喜欢的围栏  $6$ 和 $8$ 中的动物都保留了。但是，Polly 和 Hwan 将不高兴，因为他们看不到任何他们喜欢的动物，而他们害怕的动物都还在。这种安排方式使得三个小朋友高兴。
- 现在，换一种方法，如果你将围栏 $4$ 和 $6$ 中的动物移走，Alex 和 Polly 将很高兴，因为他们害怕的动物被移走了。Chaitanya 也会高兴，虽然他喜欢的动物 $6$ 被移走了，他仍可以看到围栏 $8$ 里面他喜欢的动物。同样的 Hwan 也会因可以看到自己喜欢的动物 $12$ 而高兴。唯一不高兴的只有 Ka-Shu。
- 如果你只移走围栏 $13$ 中的动物，Ka-Shu 将高兴，因为有一个他害怕的动物被移走了，Alex, Polly, Chaitanya 和 Hwan 也会高兴，因为他们都可以看到至少一个他们喜欢的动物。所以有 $5$ 个小朋友会高兴。这种方法使得了最多的小朋友高兴。

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

$N$ 是围栏数（$10 \le N \le 10^4$），$C$ 是小朋友的个数（$1 \le C \le 5\times 10^4$）。

围栏按照顺时针的方向编号为 $1,2,3,\cdots,N$。

接下来的 $C$ 行，每行描述一个小朋友的信息，以下面的形式给出： $E, F, L ,X_1, X_2 ,\cdots ,X_F ,Y_1 ,Y_2 ,\cdots ,Y_L$。

其中： $E$ 表示这个小朋友可以看到的第一个围栏的编号（$1 \le E \le N$），换句话说，该小朋友可以看到的围栏为 $E$， $E+1$， $E+2$， $E+3$， $E+4$。

注意，如果编号超过 $N$ 将继续从 $1$ 开始算。

如：当 $N=14$，$ E=13$ 时，这个小朋友可以看到的围栏为 $13,14,1, 2$ 和 $3$。

$F$ 表示该小朋友害怕的动物数。

$L$ 表示该小朋友喜欢的动物数。

围栏 $X_1, X_2, \cdots, X_F$ 中包含该小朋友害怕的动物。

围栏 $Y_1, Y_2, \cdots, Y_L$ 中包含该小朋友喜欢的动物。

$X_1, X_2, \cdots, X_F, Y_1, Y_2, \cdots, Y_L$ 是两两不同的整数，而且所表示的围栏都是该小朋友可以看到的。

小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了（这样最小的 $E$ 对应的小朋友排在第一个，最大的 $E$ 对应的小朋友排在最后一个）。

注意可能有多于一个小朋友对应的 $E$ 是相同的。

outputFormat: 仅输出一个数，表示最多可以让多少个小朋友高兴。

hint:
**数据范围**
对于 $100\%$ 的数据，$10 \le N \le 10^4$，$1 \le C \le 5\times 10^4$，$1 \le E \le N$。

**样例说明**
- 第一个样例是题目描述中的例子，所有的 $C=5$ 个小朋友都能高兴。
- 第二个样例是一个不能使得所有 $C=7$ 个小朋友都高兴的例子。


title: [APIO2008] 免费道路

description:
新亚（New Asia）王国有 N 个村庄，由 M 条道路连接。其中一些道路是鹅卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去 王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。

国王已决定保持尽可能少的道路免费，但是两个不同的村庄之间都应该一条且仅由一条 且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需 要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好 K 条鹅卵石路免费。

举例来说，假定新亚王国的村庄和道路如图 3(a)所示。如果国王希望保持两 条鹅卵石路免费，那么可以如图 3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5) 免费。该方案满足了国王的要求，因为：(1)两个村庄之间都有一条由免费道 路组成的路径；(2)免费的道路已尽可能少；(3)方案中刚好有两条鹅卵石道路 (2, 3)和(3, 4)

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

图 3: (a)新亚王国中村庄和道路的一个示例。实线标注的是水泥路，虚线标注 的是鹅卵石路。(b)一个保持两条鹅卵石路免费的维护方案。图中仅标出了免 费道路。

给定一个关于新亚王国村庄和道路的述以及国王决定保持免费的鹅卵石 道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果 存在则任意输出一个方案。

inputFormat:
输入第一行包含三个由空格隔开的整数：

N，村庄的数目(1≤N≤20,000)；

M，道路的数目(1≤M≤100,000)；

K，国王希望保持免费的鹅卵石道路数目(0≤K≤N - 1)。

此后 M 行述了新亚王国的道路，编号分别为 1 到 M。第(i+1)行述了第 i 条 道路的情况。用 3 个由空格隔开的整数述：

ui 和 vi，为第 i 条道路连接的两个村庄的编号，村庄编号为 1 到 N；

ci，表示第 i 条道路的类型。ci = 0 表示第 i 条道路是鹅卵石路，ci = 1 表 示第 i 条道路是水泥路。

输入数据保证一对村庄之间至多有一条道路连接

outputFormat: 如果满足国王要求的道路维护方案不存在，你的程序应该在输出第一行打印 no solution。 否则，你的程序应该输出一个符合要求的道路维护方案，也就是保持免费的 道路列表。按照输入中给定的那样输出免费的道路。如果有多种合法方案，你可 以任意输出一种。


title: [APIO2008] DNA

description:
分析如DNA序列这样的生命科学数据是计算机的一个有趣应用。从生物学的角度上说，DNA是一种由腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶这四种核苷酸组成的链式结构。这四种核苷酸分别用大写字母A、C、G、T表示。这样，一条DNA单链可以被表示为一个只含以上四种字符的字符串。我们将这样的字符串称作一个DNA序列。

有时生物学家可能无法确定一条DNA单链中的某些核苷酸。在这种情况下，字符N将被用来表示一个不确定的核苷酸。换句话说，N可以用来表示A、C、G、T中的任何一个字符。我们称包含一个或者多个N的DNA序列为未完成序列；反之，就称作完成序列。如果一个完成序列可以通过将一个未完成序列中的个N任意替换成A、C、G、T得到的话，就称完成序列适合这个未完成序列。举例来说，ACCCT适合ACNNT，但是AGGAT不适合。

研究者们常按照如下方式排序四种核苷酸：A优先于C，C优先于G，G优先于T。如果一个DNA序列中的个核苷酸都与其右边的相同或者优先，就将其归类为范式-1。举例来说，AACCGT是范式-1，但是AACGTC不是。

一般来说，一个DNA序列属于范式-j(j>1)，只要它属于范式-(j-1)或者是一个范式-(j-1)和一个范式-1的连接。举例来说，AACCC、ACACC和ACACA都是范式-3，但GCACAC和ACACACA不是。

同样，研究者们按照字典序对DNA序列进行排序。按照这个定义，最小的属于范式-3的DNA序列是AAAAA，最大的是TTTTT。这里是另外一个例子，考虑未完成序列ACANNCNNG。那么前7个适合这个未完成序列的DNA序列是：
```
ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG
```

inputFormat:
输入第一行包含三个由空格隔开的整数：M(1≤M≤50,000)，K(1≤K≤10)和 R(1≤R≤2×$10^{12}$)。

第二行包含一个长度为 M 的字符串，表示未完成序列。

保证适 合该未完成序列的范式-K 的总数不超过 4×10^18，因此该数可以用 C 和 C++中的 long long 类型或者 Pascal 中的 Int64 类型表示。同时，R 不会超过适合给定未完 成序列的范式-K 的总数。

outputFormat: 在第一行中输出第R个适合输入中的未完成序列的范式-K。


title: [APIO2009] 采油区域

description:
Siruseri 政府决定将石油资源丰富的 Navalur 省的土地拍卖给私人承包商以 建立油井。被拍卖的整块土地为一个矩形区域，被划分为 $M \times N$ 个小块。 Siruseri 地质调查局有关于 Navalur 土地石油储量的估测数据。这些数据表示 为 $M \times N$ 个正整数，即对每一小块土地石油储量的估计值。 为了避免出现垄断，政府规定每一个承包商只能承包一个由 $K\times K$ 块相连的土地构成的正方形区域。 AoE 石油联合公司由三个承包商组成，他们想选择三块互不相交的 $K\times K$ 的 区域使得总的收益最大。 例如，假设石油储量的估计值如下：

```
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9
```

- 如果 $K = 2$，AoE 公司可以承包的区域的石油储量总和为 $100$；
- 如果 $K = 3$，AoE 公司可以承包的区域的石油储量总和为 $208$。

AoE 公司雇佣你来写一个程序，帮助计算出他们可以承包的区域的石油储量之和的最大值。

inputFormat: 输入第一行包含三个正整数 $M, N, K$，其中 $M$ 和 $N$ 是矩形区域的行数和列数，$K$ 是每一个承包商承包的正方形的大小（边长的块数）。接下来 $M$ 行，每行有 $N$ 个正整数表示这一行每一小块土地的石油储量的估计值。

outputFormat: 输出只包含一个正整数，表示 AoE 公司可以承包的区域的石油储量之和的最大值。

hint:
数据保证 $K\le M$ 且 $K\le N$ 并且至少有三个 $K\times K$ 的互不相交的正方形区域。

其中 $30\%$ 的输入数据，$M, N \le 12$。所有的输入数据, $M, N\le 1500$。每一小块土地的石油储量的估计值是非负整数且小于等于 $500$。


title: [APIO2009] 会议中心

description:
Siruseri 政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很 感兴趣，他们希望能够在里面举行会议。

对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。 会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。

显 然，有可能存在不止一种满足要求的策略。 例如下面的例子。总共有 4 个公司。他们对租借会堂发出了请求，并提出了 他们所需占用会堂的起止日期（如下表所示）。

```cpp
       开始日期 结束日期
 公司1    4        9
 公司2    9        11
 公司3    13       19
 公司4    10       17
```
上例中，最多将会堂租借给两家公司。租借策略分别是租给公司 1 和公司 3， 或是公司 2 和公司 3，也可以是公司 1 和公司 4。注意会议中心一天最多租借给 一个公司，所以公司 1 和公司 2 不能同时租借会议中心，因为他们在第九天重合 了。

销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首 先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的 顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出 其中字典序最小1的候选策略作为最终的策略。

例中，会堂最终将被租借给公司 1 和公司 3：3 个候选策略是 {(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。 你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

inputFormat: 输入的第一行有一个整数 N，表示发出租借会堂申请的公司的个数。第 2 到 第 N+1 行每行有 2 个整数。第 i+1 行的整数表示第 i 家公司申请租借的起始和终 止日期。对于每个公司的申请，起始日期为不小于 1 的整数，终止日期为不大于 10^9 的整数。

outputFormat: 输出的第一行应有一个整数 M，表示最多可以租借给多少家公司。第二行应列出 M 个数，表示最终将会堂租借给哪些公司。

hint:
对于 50%的输入，N≤3000。

在所有输入中，N≤200000。


title: [APIO2009] 抢掠计划

description:
Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。

Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆祝他的胜利。

使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机里面就不会再有钱了。 例如，假设该城中有 $6$ 个路口，道路的连接情况如下图所示：

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

市中心在路口 $1$，由一个入口符号 → 来标识，那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢劫的现金总数为 $47$，实施的抢劫路线是：$1-2-4-1-2-3-5$。

inputFormat:
第一行包含两个整数 $N,M$。$N$ 表示路口的个数，$M$ 表示道路条数。

接下来 $M$ 行，每行两个整数，这两个整数都在 $1$ 到 $N$ 之间，第 $i+1$ 行的两个整数表示第 $i$ 条道路的起点和终点的路口编号。

接下来 $N$ 行，每行一个整数，按顺序表示每个路口处的 ATM 机中的钱数 $a_i$。

接下来一行包含两个整数 $S,P$，$S$ 表示市中心的编号，也就是出发的路口。$P$ 表示酒吧数目。

接下来的一行中有 $P$ 个整数，表示 $P$ 个有酒吧的路口的编号。

outputFormat: 输出一个整数，表示 Banditji 从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

hint:
对于 $50\%$ 的数据，保证 $N, M \le 3000$。

对于 $100\%$ 的数据，保证 $N, M \le 5\times 10^5$，$0 \le a_i \le 4000$。保证可以从市中心沿着 Siruseri 的单向的道路到达其中的至少一个酒吧。


title: [APIO2010] 特别行动队

description:
你有一支由 $n$ 名预备役士兵组成的部队，士兵从 $1$ 到 $n$ 编号，你要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号**应该连续**，即为形如 $(i, i + 1, \cdots i + k)$的序列。所有的队员都应该属于且仅属于一支特别行动队。

编号为 $i$ 的士兵的初始战斗力为 $x_i$ ，一支特别行动队的初始战斗力 $X$ 为队内士兵初始战斗力之和，即 $X = x_i + x_{i+1} + \cdots + x_{i+k}$。

通过长期的观察，你总结出对于一支初始战斗力为 $X$ 的特别行动队，其修正战斗力 $X'= aX^2+bX+c$，其中 $a,~b,~c$ 是已知的系数（$a < 0$）。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队的修正战斗力之和最大。试求出这个最大和。

inputFormat:
输入的第一行是一个整数 $n$，代表士兵的人数。

输入的第二行有三个用空格隔开的整数，依次代表 $a,~b,~c$，即修正战斗力的系数。

输入的第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表编号为 $i$ 的士兵的初始战斗力 $x_i$。

outputFormat: 输出一行一个整数，代表最大的所有特别行动队战斗力之和。

hint:
#### 样例输入输出 $1$ 解释

你有 $4$ 名士兵，$x_1 = 2,~x_2 = 2,~x_3 = 3,~x_4=4$。修正战斗力公式中的参数为  $a = -1,~b = 10,~c = -20$。

此时，最佳方案是将士兵组成 $3$ 个特别行动队：第一队包含士兵 $1$ 和士兵 $2$，第二队包含士兵 $3$，第三队包含士兵 $4$。特别行动队的初始战斗力分别为 $4,~3,~4$，修正后的战斗力分别为 $-4^2 + 10 \times 4 -20 = 4$，$-3^2 + 10 \times 3 - 20 = 1$，$-4^2 + 10 \times 4 -20 = 4$。修正后的战斗力和为 $4 + 1 + 4 = 9$，没有其它方案能使修正后的战斗力和更大。

#### 数据范围与约定

对于 $20\%$ 的数据，$n \leq 10^3$。

对于 $50\%$ 的数据，$n \leq 10^4$

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$-5 \leq a \leq -1$，$-10^7 \leq b \leq 10^7$，$-10^7 \leq c \leq 10^7$，$1 \leq x_i \leq 100$。


title: [APIO2010] 巡逻

description:
在一个地区中有 $n$ 个村庄，编号为 $1, 2, \dots, n$。有 $n-1$ 条道路连接着这些村庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其他任何一个村庄。每条道路的长度均为 $1$ 个单位。为保证该地区的安全，巡警车每天要到所有的道路上巡逻。警察局设在编号为 $1$ 的村庄里，每天巡警车总是从警察局出发，最终又回到警察局。下图表示一个有 $8$ 个村庄的地区，其中村庄用圆表示（其中村庄 $1$ 用黑色的圆表示），道路是连接这些圆的线段。为了遍历所有的道路，巡警车需要走的距离为 $14$ 个单位，每条道路都需要经过两次。

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

为了减少总的巡逻距离，该地区准备在这些村庄之间建立 $K$ 条新的道路，每条新道路可以连接任意两个村庄。两条新道路可以在同一个村庄会合或结束，如下面的图例 (c)。一条新道路甚至可以是一个环，即其两端连接到同一个村庄。由于资金有限，$K$ 只能是 $1$ 或 $2$。同时，为了不浪费资金，每天巡警车必须经过新建的道路正好一次。下图给出了一些建立新道路的例子：

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

在 (a) 中，新建了一条道路，总的距离是 $11$。在 (b) 中，新建了两条道路，总的巡逻距离是 $10$。在 (c) 中，新建了两条道路，但由于巡警车要经过每条新道路正好一次，总的距离变为了 $15$。试编写一个程序，读取村庄间道路的信息和需要新建的道路数，计算出最佳的新建道路的方案使得总的巡逻距离最小，并输出这个最小的巡逻距离。

inputFormat: 第一行包含两个整数 $n, K(1 ≤ K ≤ 2)$。接下来 $n-1$ 行，每行两个整数 $a,b$，表示村庄 $a$ 与 $b$ 之间有一条道路 $(1 ≤ a, b ≤ n)$。

outputFormat: 输出一个整数，表示新建了 $K$ 条道路后能达到的最小巡逻距离。


title: 慈善的约瑟夫

description: 你一定听说过约瑟夫问题吧？即从 $N$ 个人中找出唯一的幸存者。现在老约瑟夫将组织一个皆大欢喜的新游戏，假设 $N$ 个人站成一圈，从第 $1$ 人开始交替的去掉游戏者，但只是暂时去掉，直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人得到 $1$ 个金币，永久性离开。其余剩下的将重复以上的游戏过程，比幸存者号码大的人每人得到 $1$ 个金币后离开。经过若干轮这样的过程后，一旦人数不再减少，则最后剩下的那些人将得到 $2$ 个金币。请你计算一下老约瑟夫一共要付出多少钱？

inputFormat: 一行一个正整数N表示人数。

outputFormat: 一行一个正整数表示共需支付的钱数。


title: [APIO2010] 信号覆盖

description:
一家电信公司正在北京城搭建一个 GSM 网络。城市里共有 n 个房子需要被 信号覆盖。由于经费的限制，电信公司只能安装一个天线。 这里将每个房子用一个点坐标来表示。为了简化天线的放置，电信公司将会 选择其中的 3 个房子作一个外接圆，然后将天线放在圆的中心，所有位于这个圆 内或者圆的边界上的房子都将被天线的信号所覆盖。 电信公司将会随机选择城市中的 3 个房子来搭建天线，他们想知道在所有可 能放置天线的方案中平均会有多少个房子被信号覆盖。 例如，假设共有 4 个房子 A, B, C, D，它们的位置如下图：

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

如果我们选择ABC或者BCD三个点搭建的外接圆，所有的房子都会被覆盖。 如果我们选择 ACD 或者 ABD，剩下的房子将不会在天线的信号覆盖范围内。因 此平均有(4 + 4 + 3 + 3) / 4 = 3.50 个房子被信号覆盖。 给定所有房子的位置，你的任务是计算平均有多少个房子被信号覆盖。假定 每一个房子都有一个二维的整数坐标，并且保证任何三个房子都不在同一条直线 上，任何四个房子都不在同一个圆上。

inputFormat: 输入第一行包含一个正整数 n, 表示房子的总数。接下来有 n 行，分别表示 每一个房子的位置。对于 i = 1, 2, .., n, 第 i 个房子的坐标用一对整数 xi和 yi来表 示，中间用空格隔开。

outputFormat: 输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，需保证输出 结果与精确值的绝对误差不超过 0.01。

hint:
【样例说明】

3.5, 3.50, 3.500, … 中的任何一个输出均为正确。此外，3.49, 3.51, 3.499999，…等也都是可被接受的输出。

【数据范围】

100%的数据保证，对于 i = 1, 2, .., n, 第 i 个房子的坐标(xi, yi)为整数且 –1,000,000 ≤ xi, yi ≤ 1,000,000. 任何三个房子不在同一条直线上，任何四个房子不 在同一个圆上；

40%的数据，n ≤ 100；

70%的数据，n ≤ 500；

100%的数据，3 ≤ n ≤ 1,500。


title: Facer和教官

background:
Facer和教官关系很好（py交易）

被教官任命为副教官

description:
Facer训练一个N个人的队伍

每个人有一个智力值ai和体力值bi

Facer希望两个人组队，组队的两个人要尽量相似

具体来说，两个人的相似度cmp(i,j) =| ai - aj + bj - bi | + | ai - aj |
cmp(i,j)越小表示越相似

现在本来有N个人，但是Facer想要再加入一个人

有M个候选人

Facer需要对每一个候选人找到组队的对象（即找到和他cmp最低的的本来就在队伍中的人），你需要输出每个人和队伍中的人最低的cmp，并输出它

inputFormat:
第一行N，M

接下来N行，每行两个数，表示本来就在队伍中的人的智力值ai,体力值bi

接下来M行

如果是 1 a b 表示队伍中新加入了一个人 ,智力a , 体力b

如果是2  a b表示有一个候选人，请找出和候选人最相似的队伍中的人

outputFormat: 对于每个候选人，输出他和本来就在队伍中的人的最低的cmp


title: Facer的工厂

description:
Facer 是一个工厂里的兼职工人，这回他碰到了一个问题。

有 $N$ 根钢管，每根长度是 $a_i$。

有一个钢管加工器，每秒钟可以加工 $k$ 长度的钢管。

Facer 需要按顺序加工这些钢管。

不过呢，机器的最大等待长度是 $h$，即等待加工（已经塞入机器却还没有加工的钢管）的钢管长度不能超过 $h$（保证 $a_i \le h$）。

Facer 只能在整数秒的时候塞入钢管。

求 Facer 处理完这些钢管最少要多久呢？

inputFormat:
第一行 $N,H,K$，代表钢管条数，最大等待长度和每秒处理速度。

接下来 $N$ 行，每行一个数，代表钢管的长度。

钢管需要按顺序处理。

outputFormat: 最短时间

hint:
样例 1 解释：只有 $1$ 根钢管，加工时间为 $\lfloor 5/3\rfloor = 2$。

样例 2 解释：

第一秒塞入 $5$，等待长度 $5$，机器处理了 $3$，等待长度 $2$。

第二秒塞入 $4$，等待长度 $6$，机器处理了 $3$，等待长度 $3$。

第三秒塞入 $3$，等待长度 $6$，机器处理了 $3$，等待长度 $3$。

第四秒塞入了 $1,2$，等待长度 $6$，机器处理了 $3$，等待长度 $3$。

第五秒无塞入，等待长度 $3$，机器处理了 $3$，处理完毕。

$N \le 100000$，$h,a_i \le 10^9$。

本题 by zhouyonglong


title: [NOIP2017 提高组] 奶酪

background: NOIP2017 提高组 D2T1

description:
现有一块大奶酪，它的高度为 $h$，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 $z = 0$，奶酪的上表面为 $z = h$。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑 到奶酪的上表面去?

空间内两点 $P_1(x_1,y_1,z_1)$、$P2(x_2,y_2,z_2)$ 的距离公式如下：

$$\mathrm{dist}(P_1,P_2)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$$

inputFormat:
每个输入文件包含多组数据。

第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下： 第一行包含三个正整数 $n,h,r$，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。

接下来的 $n$ 行，每行包含三个整数 $x,y,z$，两个数之间以一个空格分开，表示空洞球心坐标为 $(x,y,z)$。

outputFormat: $T$ 行，分别对应 $T$ 组数据的答案，如果在第 $i$ 组数据中，Jerry 能从下表面跑到上表面，则输出 `Yes`，如果不能，则输出 `No`。

hint:
【输入输出样例 $1$ 说明】

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

第一组数据,由奶酪的剖面图可见：

第一个空洞在 $(0,0,0)$ 与下表面相切；

第二个空洞在 $(0,0,4)$ 与上表面相切；

两个空洞在 $(0,0,2)$ 相切。

输出 `Yes`。

第二组数据,由奶酪的剖面图可见：

两个空洞既不相交也不相切。

输出 `No`。

第三组数据,由奶酪的剖面图可见：

两个空洞相交，且与上下表面相切或相交。

输出 `Yes`。

【数据规模与约定】

对于 $20\%$ 的数据，$n = 1$，$1 \le h$，$r \le  10^4$，坐标的绝对值不超过 $10^4$。

对于 $40\%$ 的数据，$1 \le n \le 8$，$1 \le h$，$r \le 10^4$，坐标的绝对值不超过 $10^4$。

对于 $80\%$ 的数据，$1 \le n \le 10^3$，$1 \le h , r \le 10^4$，坐标的绝对值不超过 $10^4$。

对于 $100\%$ 的数据，$1 \le n \le 1\times 10^3$，$1 \le h , r \le 10^9$，$T \le 20$，坐标的绝对值不超过 $10^9$。


title: 数学1（math1）- 加减算式

background: 蒟蒻HansBug 在数学考场上，挠了无数次的头，可脑子里还是一片空白。

description: 好不容易啊，HansBug 终于熬到了做到数学最后一题的时刻了，眼前是一堆杂乱的加减算式。显然成功就在眼前了。可是他脑细胞和RP已经消耗殆尽，所以这个重要的任务就交给你们啦。

inputFormat: 一行，包含一个字符串形式的加减法多项式（每一项数字范围为$0\sim 32767$）。

outputFormat: 一个整数，为计算所得的结果（保证计算结果不会超过长整型范围）。

hint: 数据保证字符串长度不超过 $60000$。


title: 物理1（phsic1）- 磁通量

background: 蒟蒻 HansBug 在物理考场上，挠了无数次的头，可脑子里还是一片空白。

description: 眼下出现在 HansBug 蒟蒻面前的是一个奇怪的磁场，形状为多边形，可以描述为 $N$ 个点构成的序列，这些点即依次为该磁场的各个顶点。于是现在蒟蒻 HansBug 想要知道该磁场的磁通量为多少。可是他脑细胞和 RP 已经消耗殆尽，所以这个高端的任务就交给你们啦。

inputFormat:
第一行为一个整数 $N$ 和一个实数 $B$，$B$ 为磁感应强度。

第 $2\sim N+1$ 行，每行包含两个实数，表示该点的横纵坐标。

outputFormat: 一行，包含一个实数，即为磁通量（输出四舍五入保留四位小数）。

hint:
磁通量 $=$ 磁感应强度 $\times$ 磁场区域面积。

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

$0\lt B\le 10$。


title: 化学1（chem1）- 化学合成

background: 蒟蒻 HansBug 在化学考场上，挠了无数次的头，可脑子里还是一片空白。

description:
眼下出现在蒟蒻 HansBug 面前的是一个化学合成题，据他所知，一般答案如下面这样的格式：

![](https://cdn.luogu.com.cn/upload/pic/2223.png) （接下一行）

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

简单解释下：每种化合物可以通过一步反应生成另一个化合物（将这称作一步反应，设为 $A\rightarrow B$），现在假设每个 $A\rightarrow B$ 中，理论上 $1$ 个单位的 $A$ 都仅可以生成 $1$ 个单位的 $B$。然而实际实验表明，并不存在绝对完全的化学转化，设转化率为 $C$（即 $1$ 个单位 $A$ 实际可以生成 $C$ 个单位的 $B$，$0<C<1$）。

现在蒟蒻 HansBug 的知识体系中有 $N$ 个这样 $A\rightarrow B$ 的转化。然而题目中蒟蒻 HansBug 要由 $1$ 个单位的化合物 $S$ 生成化合物 $T$，可是他脑细胞和 RP 已经消耗殆尽，所以找到最终产量最高的合成路线的艰巨任务就交给你啦！

inputFormat:
第一行为四个整数：$N,M,S,T$，分别表示总共出现的化合物个数、HansBug 所知道的反应个数、起始的化合物序号、终末的化合物序号（$1\le S,T\le N$）。

第 $2 \sim M+1$ 行每行为两个整数和一个实数：$A_i,B_i,C_i$，分别表示第 $i$ 个反应为由 $1$ 个单位的 $A_i$ 化合物生成 $C_i$ 单位的 $B_i$ 化合物。

outputFormat: 一行，包含一个实数，为最佳路线下最终的产量（四舍五入保留 $4$ 位小数），如果没有可行路线的话，输出 `orz`。

hint:
样例 1 和样例 2 中，两条合成路线分别为 $1\rightarrow3$、$1\rightarrow2$、$2\rightarrow3$，产率分别为 $0.8$、$0.9$、$0.9$。

在样例 1 中，有两种可行的路线 $1\rightarrow3$ 和 $1\rightarrow2\rightarrow3$ ，最终产量分别为 $0.8$、$0.9\times0.9=0.81$，故第二条路线更优，产量为 $0.8100$。

样例 2 中，$2$ 只能生成 $3$，$3$ 无法生成别的化合物，故无法生成，蒟蒻 HansBug 只好选择 `orz`。

**【数据范围】**

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


title: ccj与zrz之积木问题

background: ccj和zrz无聊到了玩起了搭积木...(本题选自uva101，翻译来自《算法竞赛入门经典2》)

description:
从左到右有 $n$ 个木块，编号从 $0$ 到 $n-1$，要求模拟以下 $4$ 种操作（下面的 $a$ 和 $b$ 都是木块编号，归位表示比如 $1$ 号木块归到 $1$ 号位去）。

- $\texttt{move }a\texttt{ onto }b$：把 $a$ 和 $b$ 上方的木块全部归位，然后把 $a$ 摞在 $b$ 上面；
- $\texttt{move }a\texttt{ over }b$：把 $a$ 上方的全部归位，然后把 $a$ 放在 $b$ 所在木块堆的顶部；
- $\texttt{pile }a\texttt{ onto }b$：把 $b$ 上方的木块全部归位，然后把 $a$ 及上面的木块整体摞在 $b$ 上面；
- $\texttt{pile }a\texttt{ over }b$：把 $a$ 及上面的木块整体摞在 $b$ 所在木块堆的顶部；
- 遇到 $\texttt{quit}$ 停止。$a$ 和 $b$ 在同一堆的指令时非法指令，应当忽略。

最后输出每个位置的木块列表，按照从底部到顶部的顺序排列。

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

接下来若干行：每行一个指令（语法不会错），遇到 $\texttt{quit}$ 停止。

outputFormat: 输出共 $n$ 行，第 $i$ 行输出一个 $i$ 和冒号，然后一个空格，输出，它位置上的所有积木。

samples:
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

hint:
### 数据范围及约定

对于全部数据，$0<n<25$。


title: ccj与zrz之在回家的路上

background: zrz走在回家了路上，突然很想上厕所，然后就冲到厕所门口，惊讶的发现门上有个算式。。。

description: 给出一个算式（a\*b=c或a/b=c或a+b=c或a-b=c）其中a，b，c是三个数字，但是其中有一个是问号，表示未知，请你求出未知的那一个量。

inputFormat: 只有一行，一个算式（a\*b=c或a/b=c或a+b=c或a-b=c），可能会有多余的空格

outputFormat: “?”代表的数字，保留2位小数。

hint: 总长度小于200，所有数字和要求的数字均不会超过1000000000，也不会是负数。读入的数不会是小数，但答案有可能是


title: 英语1（eng1）- 英语作文

background: 蒟蒻 HansBug 在英语考场上，挠了无数次的头，可脑子里还是一片空白。

description: 眼下出现在 HansBug 蒟蒻面前的是一篇英语作文，然而智商捉急的 HansBug 已经草草写完了，此时他发现离考试结束还有 $40$ 分钟，于是他打算估计一下这篇共有 $M$ 个单词的英语作文的含金量如何。众所周知的是，在中高考英语作文中使用高级词汇可以有效提高文章的含金量，从而获得更好的分数。已知蒟蒻HansBug知道 $N$ 个高级词汇，该词汇为 $A_i$（词汇长度为 $L_i$ ，包含数字、大小写字母），该高级词汇的含金量为 $B_i$，则该高级词汇每出现一次便可增加 $B_i$ 的含金量。可是他脑细胞和 RP 已经消耗殆尽，所以这个伟大的任务就交给你啦！

inputFormat:
第一行包含两个整数 $N$ 和 $P$ ， $N$ 表示HansBug共知道的高级词汇个数， $P$ 为模数

第 $2-N+1$行，每行包含一个单词 $A_i$ （长度为Li）和一个整数 $B_i$ ，其中 $B_i(0<B_i\le 10^5)$ 表示该单词的含金量

接下来直到输入结束的若干行为一篇英语作文，其中包含共计 $M$ 个单词，以及若干的分隔符（分隔符包含且仅包含`,`、`.`、`!`、`?`）

outputFormat: 一行，包含一个整数，为该文章的总含金量对 $P$ 的模。

samples:
5 99
hansbug 1
kkksc03 2
yyy 3
absi2011 4
lzn 100
hansbug is a juruo!but absi2011 not.!?!
one day absi2011 laughed at yyy and hansbug.
then kkksc03 and lzn blamed him for that.

samples:
5 99
yyyy 1
kkksc03 2
yyy 3
absi2011 4
lzn 100
yyyy is a juruo!but absi2011 not.!?!
one day absi2011 laughed at yyy and yyyy.
then kkksc03 and lzn blamed him for that.

hint:
样例 $1$ 中，共计出现了 $2$ 次`hansbug`、 $2$ 次`absi2011` 、 $1$ 次 `yyy` 、 $1$ 次`kkksc03`、 $1$ 次  `lzn` ，所以总含金量为 $1\times2+2\times4+3\times1+4\times1+100\times1=115$，对 $99$ 取模就是 $16$ 。

样例 $2$ 中，和样例 $1$ 基本一样，值得注意的是整体的 `yyyy` 不可以被认为是 `yyy` 出现 $2$ 次，请注意这是一篇英语作文，一切以单词为最小单位。

此题目中大小写敏感。

数据范围（设所有单词的最大长度为 $Lmax$ ）：

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


title: 语文1（chin1）- 理理思维

background: 蒟蒻 HansBug 在语文考场上，挠了无数次的头，可脑子里还是一片空白。

description:
考试开始了，可是蒟蒻 HansBug 脑中还是一片空白。哦不！准确的说是乱七八糟的。现在首要任务就是帮蒟蒻 HansBug 理理思维。假设 HansBug 的思维是一长串字符串（字符串中包含且仅包含 $26$ 个字母），现在的你，有一张神奇的药方，上面依次包含了三种操作：

1、 获取第 $x$ 到第 $y$ 个字符中字母 $k$ 出现了多少次

2、将第 $x$ 到第 $y$ 个字符全部赋值为字母 $k$

3、将第 $x$ 到第 $y$ 个字符按照 $\text{a} \sim \text{z}$ 的顺序排序

你欣喜若狂之时，可是他脑细胞和 RP 已经因为之前过度紧张消耗殆尽，眼看试卷最后还有一篇八百字的作文呢，所以这个关键的任务就交给你啦！

inputFormat:
第一行包含两个整数 $n,m$，分别表示 HansBug 的思维所包含的字母个数和药方上操作个数。
第二行包含一个长度为 $n$ 的字符串，表示 HansBug 的思维。

接下来 $m$ 行，每行表示一个操作，格式如下：

- `1 x y k` 表示将第 $x$ 到第 $y$ 个字符中 $k$ 出现的次数输出

- `2 x y k` 表示将第 $x$ 到第 $y$ 个字符全部替换为 $k$

- `3 x y` 表示将第 $x$ 到第 $y$ 个字符按照 $\text{a} \sim \text{z}$ 的顺序排序

outputFormat: 输出为若干行，每行包含一个整数，依次为所有操作 $1$ 所得的结果。

hint:
样例说明：

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

数据规模：

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

### 此题目中大小写不敏感。

### 新加了三组 hack 数据，不在上面的表格中，但保证 $1\le n,m \le 50000$。


title: 友好城市

description: 有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的 $N$ 个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量多。

inputFormat:
第一行，一个整数 $N$，表示城市数。

第二行到第 $N+1$ 行，每行两个整数，中间用一个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

outputFormat: 仅一行，输出一个整数，表示政府所能批准的最多申请数。


title: 【模板】最小生成树

description: 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 `orz`。

inputFormat:
第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

outputFormat: 如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 `orz`。

hint:
数据规模：

对于 $20\%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40\%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70\%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100\%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

样例解释：

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

所以最小生成树的总边权为 $2+2+3=7$。


title: 【模板】并查集

description: 如题，现在有一个并查集，你需要完成合并和查询操作。

inputFormat:
第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
 `Y` ；否则输出 `N` 。

outputFormat: 对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 `Y` 或者 `N` 。


title: Facer爱游泳

background: Facer 是一个爱游泳的孩子。

description:
一天他来到了一个 $n \times m$ 的游泳池中，其中第一行是水面，第 $n$ 行是游泳池底。

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

Facer 想要从 $(1,1)$ 游到 $(1,m)$。他初始速度为 $0$ m/s。

Facer 可以按照以下方式游泳：假设当前 Facer 位于 $(x,y)$，速度为 $v$，那么它可以游到 $(x+v,y+1)$，如果 $x+v>n$，那么就会游到 $(n,y+1)$。

到了每一个格子，Facer 可以选择将自己的速度 $+1$，$-1$ 或者不变，也就是说每次 Facer 有三种选择：

- 游到 $(x+v-1,y+1)$，速度变为 $v-1$。
- 游到 $(x+v,y+1)$，速度变为 $v$。
- 游到 $(x+v+1,y+1)$，速度变为 $v+1$。

游泳池的每个格子上会放有以下两种物品中的一种：

- 变速器，每个变速器有一个属性 $w$，到了这个格子速度会变为 $v+w$（当然原来的 $+1$，$-1$，不变照样存在）。
- 金币盒，每个金币盒中有一定数量的钱 $a$，到了这个位置你可以得到 $a$ 个金币。

除此之外，有以下两点需要注意的：

1. 当 Facer 到达水面，即位于 $(1,x)$ 时，Facer的速度会变成 $0$（当然他仍然可以选择将速度 $+1$，$-1$ 或不变）。
2. Facer 不能在水下待太长时间，相邻两次到水面换气的时间不能超过 $k$ 秒。

求 Facer 能够得到最大金币的数量。

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

第二行到第 $n+1$ 行，每行 $m$ 个字符串，表示每个格子物品的情况：

- 首字母为 ```v```，后面接一个整数 $w$，表示该格子中有一个变速器，属性为 $w$。
- 首字母为 ```s```，后面接一个整数 $a$，表示该格子中有一个金币盒，钱数为 $a$。

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


title: 【模板】单源最短路径（弱化版）

background: 本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 [P4779](https://www.luogu.org/problemnew/show/P4779)。

description: 如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

inputFormat:
第一行包含三个整数 $n,m,s$，分别表示点的个数、有向边的个数、出发点的编号。

接下来 $m$ 行每行包含三个整数 $u,v,w$，表示一条 $u \to v$ 的，长度为 $w$ 的边。

outputFormat: 输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$。

hint:
【数据范围】
对于 $20\%$ 的数据：$1\le n \le 5$，$1\le m \le 15$；
对于 $40\%$ 的数据：$1\le n \le 100$，$1\le m \le 10^4$；
对于 $70\%$ 的数据：$1\le n \le 1000$，$1\le m \le 10^5$；
对于 $100\%$ 的数据：$1 \le n \le 10^4$，$1\le m \le 5\times 10^5$，$1\le u,v\le n$，$w\ge 0$，$\sum w< 2^{31}$，保证数据随机。

**Update 2022/07/29：两个点之间可能有多条边，敬请注意。**

对于真正 $100\%$ 的数据，请移步 [P4779](https://www.luogu.org/problemnew/show/P4779)。请注意，该题与本题数据范围略有不同。

样例说明：

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

图片1到3和1到4的文字位置调换


title: 【模板】线段树 1

description:
如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

inputFormat:
第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1. `1 x y k`：将区间 $[x, y]$ 内每个数加上 $k$。
2. `2 x y`：输出区间 $[x, y]$ 内每个数的和。

outputFormat: 输出包含若干行整数，即为所有操作 2 的结果。

hint:
对于 $30\%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70\%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100\%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

**【样例解释】**

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


title: 【模板】线段树 2

description:
如题，已知一个数列，你需要进行下面三种操作：

- 将某区间每一个数乘上 $x$；
- 将某区间每一个数加上 $x$；
- 求出某区间每一个数的和。

inputFormat:
第一行包含三个整数 $n,q,m$，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $q$ 行每行包含若干个整数，表示一个操作，具体如下：

操作 $1$： 格式：`1 x y k`  含义：将区间 $[x,y]$ 内每个数乘上 $k$

操作 $2$： 格式：`2 x y k`  含义：将区间 $[x,y]$ 内每个数加上 $k$

操作 $3$： 格式：`3 x y`  含义：输出区间 $[x,y]$ 内每个数的和对 $m$ 取模所得的结果

outputFormat: 输出包含若干行整数，即为所有操作 $3$ 的结果。

hint:
【数据范围】

对于 $30\%$ 的数据：$n \le 8$，$q \le 10$。
对于 $70\%$ 的数据：$n \le 10^3 $，$q \le 10^4$。
对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le q \le 10^5$。

除样例外，$m = 571373$。

（数据已经过加强 ^\_^）

样例说明：

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

故输出应为 $17$、$2$（$40 \bmod 38 = 2$）。


title: 【模板】树状数组 1

description:
如题，已知一个数列，你需要进行下面两种操作：

- 将某一个数加上 $x$

- 求出某区间每一个数的和

inputFormat:
第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

- `1 x k`  含义：将第 $x$ 个数加上 $k$

- `2 x y`  含义：输出区间 $[x,y]$ 内每个数的和

outputFormat: 输出包含若干行整数，即为所有操作 $2$ 的结果。

hint:
【数据范围】

对于 $30\%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；
对于 $70\%$ 的数据，$1\le n,m \le 10^4$；
对于 $100\%$ 的数据，$1\le n,m \le 5\times 10^5$。

数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31}, 2^{31})$ 范围内。

样例说明：

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

故输出结果14、16


title: 【模板】KMP

description:
给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l, r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 border 为 $s$ 的一个**非 $s$ 本身**的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$，你还需要求出对于其每个前缀 $s'$ 的最长 border $t'$ 的长度。

inputFormat:
第一行为一个字符串，即为 $s_1$。
第二行为一个字符串，即为 $s_2$。

outputFormat:
首先输出若干行，每行一个整数，**按从小到大的顺序**输出 $s_2$ 在 $s_1$ 中出现的位置。
最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。

hint:
### 样例 1 解释

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

对于 $s_2$ 长度为 $3$ 的前缀 `ABA`，字符串 `A` 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$。

### 数据规模与约定

**本题采用多测试点捆绑测试，共有 3 个子任务**。

- Subtask 1（30 points）：$|s_1| \leq 15$，$|s_2| \leq 5$。
- Subtask 2（40 points）：$|s_1| \leq 10^4$，$|s_2| \leq 10^2$。
- Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 $1 \leq |s_1|,|s_2| \leq 10^6$，$s_1, s_2$ 中均只含大写英文字母。


title: 【模板】树状数组 2

description:
如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $x$；

2. 求出某一个数的值。

inputFormat:
第一行包含两个整数 $N$、$M$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i $ 项的初始值。

接下来 $M$ 行每行包含 $2$ 或 $4$个整数，表示一个操作，具体如下：

操作 $1$： 格式：`1 x y k` 含义：将区间 $[x,y]$ 内每个数加上 $k$；

操作 $2$： 格式：`2 x` 含义：输出第 $x$ 个数的值。

outputFormat: 输出包含若干行整数，即为所有操作 $2$ 的结果。

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

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

故输出结果为 6、10。

---

#### 数据规模与约定

对于 $30\%$ 的数据：$N\le8$，$M\le10$；

对于 $70\%$ 的数据：$N\le 10000$，$M\le10000$；

对于 $100\%$ 的数据：$1 \leq N, M\le 500000$，$1 \leq x, y \leq n$，保证任意时刻序列中任意元素的绝对值都不大于 $2^{30}$。


title: 【模板】普通平衡树

description:
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入一个数 $x$。
2. 删除一个数 $x$（若有多个相同的数，应只删除一个）。
3. 定义**排名**为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
4. 查询数据结构中排名为 $x$ 的数。
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

对于操作 3,5,6，**不保证**当前数据结构中存在数 $x$。

inputFormat: 第一行为 $n$，表示操作的个数,下面 $n$ 行每行有两个数 $\text{opt}$ 和 $x$，$\text{opt}$ 表示操作的序号（$ 1 \leq \text{opt} \leq 6 $）

outputFormat: 对于操作 $3,4,5,6$ 每行输出一个数，表示对应答案。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^5$，$|x| \le 10^7$

来源：Tyvj1728 原名：普通平衡树

在此鸣谢


title: 【模板】字符串哈希

description:
如题，给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串。

**友情提醒：如果真的想好好练习哈希的话，请自觉。**

inputFormat:
第一行包含一个整数 $N$，为字符串的个数。

接下来 $N$ 行每行包含一个字符串，为所提供的字符串。

outputFormat: 输出包含一行，包含一个整数，为不同的字符串个数。

hint:
对于 $30\%$ 的数据：$N\leq 10$，$M_i≈6$，$Mmax\leq 15$。

对于 $70\%$ 的数据：$N\leq 1000$，$M_i≈100$，$Mmax\leq 150$。

对于 $100\%$ 的数据：$N\leq 10000$，$M_i≈1000$，$Mmax\leq 1500$。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

Tip：
感兴趣的话，你们可以先看一看以下三题：

BZOJ3097：http://www.lydsy.com/JudgeOnline/problem.php?id=3097

BZOJ3098：http://www.lydsy.com/JudgeOnline/problem.php?id=3098

BZOJ3099：http://www.lydsy.com/JudgeOnline/problem.php?id=3099

如果你仔细研究过了（或者至少仔细看过AC人数的话），我想你一定会明白字符串哈希的正确姿势的^\_^


title: 方差

background: 滚粗了的 HansBug 在收拾旧数学书，然而他发现了什么奇妙的东西。

description: 蒟蒻 HansBug 在一本数学书里面发现了一个神奇的数列，包含 $N$ 个实数。他想算算这个数列的平均数和方差。

inputFormat:
第一行包含两个正整数 $N,M$，分别表示数列中实数的个数和操作的个数。

第二行包含 $N$ 个实数，其中第 $i$ 个实数表示数列的第 $i$ 项。

接下来 $M$ 行，每行为一条操作，格式为以下三种之一：

操作 $1$：`1 x y k` ，表示将第 $x$ 到第 $y$ 项每项加上 $k$，$k$ 为一实数。
操作 $2$：`2 x y` ，表示求出第 $x$ 到第 $y$ 项这一子数列的平均数。
操作 $3$：`3 x y` ，表示求出第 $x$ 到第 $y$ 项这一子数列的方差。

outputFormat: 输出包含若干行，每行为一个实数，即依次为每一次操作 $2$ 或操作 $3$ 所得的结果（所有结果四舍五入保留 $4$ 位小数）。


title: 硬币翻转

description:
有很多个硬币摆在一行，有正面朝上的，也有背面朝上的。正面朝上的用 $1$ 表示，背面朝上的用 $0$ 表示。

现在要求从这行的第一个硬币开始，将**从第一个硬币开始的前若干个硬币**同时翻面，求如果要将所有硬币翻到正面朝上，最少要进行这样的操作多少次？

inputFormat: 一个字符串，由 $0$ 和 $1$ 组成，表示硬币的初始状态。

outputFormat: 一个整数，表示要翻转的最少次数。

hint:
### 样例解释

- 第 $1$ 次翻转：把第一个硬币翻到反面，字符串为 $00$；
- 第 $2$ 次翻转：把第一、二个硬币一起翻到正面，字符串为 $11$，翻转完成，输出 $2$。

### 数据范围

记 $n$ 表示硬币的总个数，

- 对于 $20\%$ 的数据，$1\le n\leq10$；
- 对于 $50\%$ 的数据，$1\le n\leq10^4$；
- 对于 $100\%$ 的数据，$1\le n\leq10^6$。


title: 【模板】网络最大流

description: 如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。

inputFormat:
第一行包含四个正整数 $n,m,s,t$，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来 $m$ 行每行包含三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，边权为 $w_i$（即该边最大流量为 $w_i$）。

outputFormat: 一行，包含一个正整数，即为该网络的最大流。

hint:
#### 样例输入输出 1 解释

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

题目中存在 $3$ 条路径：

- $4\to 2\to 3$，该路线可通过 $20$ 的流量。
- $4\to 3$，可通过 $20$ 的流量。
- $4\to 2\to 1\to 3$，可通过 $10$ 的流量（边 $4\to 2$ 之前已经耗费了 $20$ 的流量）。

故流量总计 $20+20+10=50$。输出 $50$。

---

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n\leq10$，$m\leq25$。
- 对于 $100\%$ 的数据，保证 $1 \leq n\leq200$，$1 \leq m\leq 5000$，$0 \leq w\lt 2^{31}$。


title: 【模板】左偏树/可并堆

description:
如题，一开始有 $n$ 个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

1. `1 x y`：将第 $x$ 个数和第 $y$ 个数所在的小根堆合并（若第 $x$ 或第 $y$ 个数已经被删除或第 $x$ 和第 $y$ 个数在同一个堆内，则无视此操作）。

2. `2 x`：输出第 $x$ 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 $x$ 个数已经被删除，则输出 $-1$ 并无视删除操作）。

inputFormat:
第一行包含两个正整数 $n, m$，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含 $n$ 个正整数，其中第 $i$ 个正整数表示第 $i$ 个小根堆初始时包含且仅包含的数。

接下来 $m$ 行每行 $2$ 个或 $3$ 个正整数，表示一条操作，格式如下：

操作 $1$：`1 x y`

操作 $2$：`2 x`

outputFormat: 输出包含若干行整数，分别依次对应每一个操作 $2$ 所得的结果。

hint:
**【数据规模】**

对于 $30\%$ 的数据：$n\le 10$，$m\le 10$。
对于 $70\%$ 的数据：$n\le 10^3$，$m\le 10^3$。
对于 $100\%$ 的数据：$n\le 10^5$，$m\le 10^5$，初始时小根堆中的所有数都在 `int` 范围内。

**【样例解释】**

初始状态下，五个小根堆分别为：$\{1\}$、$\{5\}$、$\{4\}$、$\{2\}$、$\{3\}$。

第一次操作，将第 $1$ 个数所在的小根堆与第 $5$ 个数所在的小根堆合并，故变为四个小根堆：$\{1,3\}$、$\{5\}$、$\{4\}$、$\{2\}$。

第二次操作，将第 $2$ 个数所在的小根堆与第 $5$ 个数所在的小根堆合并，故变为三个小根堆：$\{1,3,5\}$、$\{4\}$、$\{2\}$。

第三次操作，将第 $2$ 个数所在的小根堆的最小值输出并删除，故输出 $1$，第一个数被删除，三个小根堆为：$\{3,5\}$、$\{4\}$、$\{2\}$。

第四次操作，将第 $4$ 个数所在的小根堆与第 $2$ 个数所在的小根堆合并，故变为两个小根堆：$\{2,3,5\}$、$\{4\}$。

第五次操作，将第 $2$ 个数所在的小根堆的最小值输出并删除，故输出 $2$，第四个数被删除，两个小根堆为：$\{3,5\}$、$\{4\}$。

故输出依次为 $1$、$2$。


title: 【模板】堆

description:
给定一个数列，初始为空，请支持下面三种操作：

1. 给定一个整数 $x$，请将 $x$ 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）。

inputFormat:
第一行是一个整数，表示操作的次数 $n$。
接下来 $n$ 行，每行表示一次操作。每行首先有一个整数 $op$ 表示操作类型。
- 若 $op = 1$，则后面有一个整数 $x$，表示要将 $x$ 加入数列。
- 若 $op = 2$，则表示要求输出数列中的最小数。
- 若 $op = 3$，则表示删除数列中的最小数。如果有多个数最小，只删除 $1$ 个。

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


title: 教辅的组成

background: 滚粗了的 HansBug 在收拾旧语文书，然而他发现了什么奇妙的东西。

description: 蒟蒻 HansBug 在一本语文书里面发现了一本答案，然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数，其中有书，有答案，有练习册。已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份答案，然而现在全都乱做了一团。许多书上面的字迹都已经模糊了，然而 HansBug 还是可以大致判断这是一本书还是练习册或答案，并且能够大致知道一本书和答案以及一本书和练习册的对应关系（即仅仅知道某书和某答案、某书和某练习册有可能相对应，除此以外的均不可能对应）。既然如此，HansBug 想知道在这样的情况下，最多可能同时组合成多少个完整的书册。

inputFormat:
第一行包含三个正整数 $N_1,N_2,N_3$，分别表示书的个数、练习册的个数和答案的个数。

第二行包含一个正整数 $M_1$，表示书和练习册可能的对应关系个数。

接下来 $M_1$ 行每行包含两个正整数 $x,y$，表示第 $x$ 本书和第 $y$ 本练习册可能对应。（$1\leq x \leq N_1$，$1 \leq y \leq N_2$）

第 $M_{1}+3$ 行包含一个正整数 $M_2$，表述书和答案可能的对应关系个数。

接下来 $M_2$ 行每行包含两个正整数 $x,y$，表示第 $x$ 本书和第 $y$ 本答案可能对应。（$1 \leq x \leq N_1$，$1 \leq y \leq N_3$）

outputFormat: 输出包含一个正整数，表示最多可能组成完整书册的数目。

hint:
样例说明：

如题，$N_1=5$，$N_2=3$，$N_3=4$，表示书有 $5$ 本、练习册有 $3$ 本、答案有 $4$ 本。

$M_1=5$，表示书和练习册共有 $5$ 个可能的对应关系，分别为：书 $4$ 和练习册 $3$ 、书 $2$ 和练习册 $2$ 、书 $5$ 和练习册 $2$ 、书 $5$ 和练习册 $1$ 以及书 $5$ 和练习册 $3$。

$M_2=5$，表示数和答案共有 $5$ 个可能的对应关系，分别为：书 $1$ 和答案 $3$、书 $3$ 和答案 $1$、书 $2$ 和答案 $2$、书 $3$ 和答案 $3$ 以及书 $4$ 和答案 $3$。

所以，以上情况的话最多可以同时配成两个书册，分别为：书 $2$ 练习册 $2$ 答案 $2$、书 $4$ 练习册 $3$ 答案 $3$。

数据规模：

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

对于数据点 $1,2,3$，$1\le M_1,M_2\leq 20$。

对于数据点 $4\sim 10$，$1\le M_1,M_2 \leq 20000$。


title: 查单词

background: 滚粗了的 HansBug 在收拾旧英语书，然而他发现了什么奇妙的东西。

description: 蒟蒻 HansBug 在一本英语书里面找到了一个单词表，包含 $N$ 个单词（每个单词内包含大小写字母）。现在他想要找出某一段连续的单词内字典序最大的单词。

inputFormat:
第一行包含两个正整数 $N, M$，分别表示单词个数和询问个数。

接下来 $N$ 行每行包含一个字符串，仅包含大小写字母，长度不超过 $15$，表示一个单词。单词**大小写不敏感**。

再接下来 $M$ 行每行包含两个整数 $x, y$，表示查询求从第 $x$ 到第 $y$ 个单词中字典序最大的单词。如果有两个单词忽略大小写情况下字典序相同，**输出靠后的那个**。

outputFormat: 输出包含 $M$ 行，每行为一个字符串，分别依次对应 $M$ 个询问的结果。

samples:
5 5
absi
hansbug
lzn
kkk
yyy
1 5
1 1
1 2
2 3
4 4

hint:
### 样例说明

第一次操作：在{absi,hansbug,lzn,kkk,yyy}中找出字典序最大的，故为yyy

第二次操作：在{absi}中找出字典序最大的，故为absi

第三次操作：在{absi,hansbug}中找出字典序最大的，故为hansbug

第四次操作：在{hansbug,lzn}中找出字典序最大的，故为lzn

第五次操作：在{kkk}中找出字典序最大的，故为kkk

### 数据规模

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


title: 直线交点数

description: 假设平面上有 $N$ 条直线，且无三线共点，那么这些直线有多少种可能的交点数？

inputFormat: 一行，一个整数 $N$，代表有 $N$ 条直线。

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

hint: 对于所有数据，满足 $1 \le N \le 25$。


title: 国王的魔镜

description: 国王有一个魔镜，可以把任何接触镜面的东西变成原来的两倍——只是，因为是镜子嘛，增加的那部分是反的。比如一条项链，我们用AB来表示，不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话，魔镜会把这条项链变为ABBA。如果再用一端接触的话，则会变成ABBAABBA（假定国王只用项链的某一端接触魔镜）。给定最终的项链，请编写程序输出国王没使用魔镜之前，最初的项链可能的最小长度。

inputFormat: 只有一个字符串，由大写英文字母组成（字母数<=100000），表示最终的项链。

outputFormat: 只有一个整数，表示国王没使用魔镜前，最初的项链可能的最小长度。


title: 又上锁妖塔

description:
小 A 在玩《剑仙》，他遇到了一个锁妖塔，想从外面爬上去。

锁妖塔共有 $n$ 层，第 $i$ 层的高度为 $h_i$。小 A 会用仙术，每用一次可以让他向上跳一层或两层，但是每次跳跃后小 A 都将用完力气，必须爬过至少一层才能再次跳跃（你可以认为小 A 需要跳两次一层才休息）。

现在小 A 想让你帮他算出爬上塔顶的最短时间。

inputFormat:
第一行一个整数 $n \in [1, 10 ^ 6]$。

第二行 $n$ 个整数 $h_i \in [1, 100]$，表示从下往上第 $i$ 层的高度。

outputFormat: 一个数 $t$，表示最短时间。


title: 【模板】最近公共祖先（LCA）

description: 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

inputFormat:
第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

outputFormat: 输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

hint:
对于 $30\%$ 的数据，$N\leq 10$，$M\leq 10$。

对于 $70\%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100\%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，**不保证** $a \neq b$。

样例说明：

该树结构如下：

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

第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。

第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。

第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。

第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。

第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4, 4, 1, 4, 4$。

2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。


title: 【模板】最小费用最大流

description:
给出一个包含 $n$ 个点和 $m$ 条边的有向图（下面称其为网络） $G=(V,E)$，该网络上所有点分别编号为 $1 \sim n$，所有边分别编号为 $1\sim m$，其中该网络的源点为 $s$，汇点为 $t$，网络上的每条边 $(u,v)$ 都有一个流量限制 $w(u,v)$ 和单位流量的费用 $c(u,v)$。

你需要给每条边 $(u,v)$ 确定一个流量 $f(u,v)$，要求：

1.  $0 \leq f(u,v) \leq w(u,v)$（每条边的流量不超过其流量限制）；
2. $\forall p \in \{V \setminus \{s,t\}\}$，$\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)$（除了源点和汇点外，其他各点流入的流量和流出的流量相等）；
3. $\sum_{(s,i)\in E}f(s,i)=\sum_{(i,t)\in E}f(i,t)$（源点流出的流量等于汇点流入的流量）。

定义网络 $G$ 的流量 $F(G)=\sum_{(s,i)\in E}f(s,i)$，网络 $G$ 的费用 $C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)$。

你需要求出该网络的**最小费用最大流**，即在 $F(G)$ 最大的前提下，使 $C(G)$ 最小。

inputFormat:
输入第一行包含四个整数 $n,m,s,t$，分别代表该网络的点数 $n$，网络的边数 $m$，源点编号 $s$，汇点编号 $t$。

接下来 $m$ 行，每行四个整数 $u_i,v_i,w_i,c_i$，分别代表第 $i$ 条边的起点，终点，流量限制，单位流量费用。

outputFormat: 输出两个整数，分别为该网络的最大流 $F(G)$，以及在 $F(G)$ 最大的前提下，该网络的最小费用 $C(G)$。

hint:
对于 $100\%$ 的数据，$1 \leq n \leq 5\times 10^3$，$1 \leq m \leq 5 \times 10^4$，$1 \leq s,t \leq n$，$u_i \neq v_i$，$0 \leq w_i,c_i \leq 10^3$，且该网络的最大流和最小费用 $\leq 2^{31}-1$。

输入数据随机生成。


title: 传教

background: 写完暑假作业后，bx2k去找pear玩。pear表示他要去汉中传教，于是bx2k准备跟着去围观。

description:
pear把即将接受传教的人排成一行，每个人从左到右的编号为1-n。每个人有一个信仰值，一开始所有人的信仰值为0。接着pear会做以下两件事之一：

1.pear向连续的一段人群传教。具体来说，pear会使第l个人到第r个人之间的所有人的信仰值增加k。

2.pear想知道某一段人的信仰值之和来得知泉岭精神是否深入人心。具体来说，pear会问bx2k第l个人到第r个人之间所有人的信仰值之和。

身为一个泉岭精神的信徒，bx2k自然会帮pear来算。但是bx2k太笨了，根本不会算。于是他想找你来帮忙。

inputFormat:
第一行包含两个整数n,m。分别表示接受传教的人数以及pear的操作数。

接下来m行，每行包含若干个整数。若第一个整数为1，则代表pear在进行传教，这一行接下来会包含l,r,k三个整数。否则第一个整数为2，代表pear的一个询问，这一行接下来会包含l,r两个整数。

outputFormat: 输出若干行，每行包含1个整数，表示pear询问的答案。行数为pear的询问数量。

hint:
【样例说明】

一开始所有人的信仰值都为0，所以答案为0。到第五个操作时，五个人的信仰值分别为0,7,7,15,6。则答案为7+15=22

【数据范围与约定】

对于1-3测试点，n,m<=10

对于4-5测试点，n,m<=10^3

对于6-8测试点，没有传教操作。

对于所有测试点，n<=10^9,m<=10^3,0<l<=n,0<r<=n,k<=10


title: 回家

description:
[](https://paste.ubuntu.com/p/DSg5bzrrjs/)

小 H 在一个划分成了 $n \times m$ 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小 H 不可以静止不动）， 但不能离开封锁线，否则就被打死了。 刚开始时他有满血 $6$ 点，每移动一格他要消耗 $1$ 点血量。一旦小 H 的血量降到 $0$， 他将死去。 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去， 他也不能通过拾取鼠标补满 HP。 即使在家门口死去， 他也不能算完成任务回到家中。

地图上有五种格子：

`0`：障碍物。

`1`：空地， 小 H 可以自由行走。

`2`：小 H 出发点， 也是一片空地。

`3`：小 H 的家。

`4`：有鼠标在上面的空地。

小 H 能否安全回家？如果能， 最短需要多长时间呢？

inputFormat:
第一行两个整数 $n,m$， 表示地图的大小为 $n \times m$。

下面 $n$ 行， 每行 $m$ 个数字来描述地图。

outputFormat: 一行， 若小 H 不能回家， 输出 `-1`，否则输出他回家所需最短时间。

hint:
对于所有数据，$1 \le n,m \le 9$。

2021.9.2 增添一组 hack 数据 by @囧仙


title: 三分

background: 本题可能存在严重精度问题，部分数据下难以通过。本题数据较水，仅供参考。

description: 如题，给出一个 $N$ 次函数，保证在范围 $[l, r]$ 内存在一点 $x$，使得 $[l, x]$ 上单调增，$[x, r]$ 上单调减。试求出 $x$ 的值。

inputFormat:
第一行一次包含一个正整数 $N$ 和两个实数 $l, r$，含义如题目描述所示。

第二行包含 $N + 1$ 个实数，从高到低依次表示该 $N$ 次函数各项的系数。

outputFormat:
输出为一行，包含一个实数，即为 $x$ 的值。若你的答案满足以下二者之一，则算正确：
- 你的答案 $x'$ 与标准答案 $x$ 的相对或绝对误差不超过 $10^{-5}$。
- 你的答案 $x'$ 与标准答案 $x$ 对应的函数值，即 $f(x') $ 和 $f(x)$ 的相对或绝对误差不超过 $10^{-5}$。

hint:
对于 $100\%$ 的数据，$6 \le N \le 13$，函数系数均在 $[-100,100]$ 内且至多 $15$ 位小数，$|l|,|r|\leq 10$ 且至多 $15$ 位小数。$l\leq r$。

**【样例解释】**

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

如图所示，红色段即为该函数 $f(x) = x^3 - 3 x^2 - 3x + 1$ 在区间 $[-0.9981, 0.5]$ 上的图像。

当 $x = -0.41421$ 时图像位于最高点，故此时函数在 $[l, x]$ 上单调增，$[x, r]$ 上单调减，故 $x = -0.41421$，输出 $-0.41421$。


title: 【模板】线性筛素数

background:
本题已更新，从判断素数改为了查询第 $k$ 小的素数
提示：如果你使用  `cin` 来读入，建议使用 `std::ios::sync_with_stdio(0)` 来加速。

description: 如题，给定一个范围 $n$，有 $q$ 个询问，每次输出第 $k$ 小的素数。

inputFormat:
第一行包含两个正整数 $n,q$，分别表示查询的范围和查询的个数。

接下来 $q$ 行每行一个正整数 $k$，表示查询第 $k$ 小的素数。

outputFormat: 输出 $q$ 行，每行一个正整数表示答案。

hint:
【数据范围】
对于 $100\%$ 的数据，$n = 10^8$，$1 \le q \le 10^6$，保证查询的素数不大于 $n$。

Data by NaCly\_Fish.


title: 爆弹虐场

description:
某年某月某日，Kiana 结识了一名爆弹虐场的少年。

Kiana 仗着自己多学了几年OI，所以还可以勉勉强强给这位少年 讲一些自己擅长的题。具体来说，Kiana 先给这位少年灌输了n 个毫不相干的知识点，然后再通过自己的[数据删除]技术把这些知识点强行联系在一起。

由于这位少年有着爆弹虐场的实力，所以对于每个Kiana 准备强行构造的联系，他都能够自己想出来，不过会花费更多的时间。具体来说，Kiana 一共有m 个联系，每个联系可以把两个不相干的知识点连在一起，如果由Kiana 直接来讲第i 个联系，需要花费ti 的时间， 而如果由少年自己想出来，则需要花费Ti 的时间。

为了偷懒，Kiana 只需要自己讲的或少年想出来的联系能刚好把知识点全部直接或间接串在一起就可以了。但为了保证教学质量， Kiana 觉得至少有k 个联系需要少年自己想出来。由于Kiana 耐心有限，她希望无论是自己讲或是少年自己想，构造的联系中花费时间最长的一个用时最短。

现在Kiana 想知道，满足这些条件的情况下，构造的联系中耗时最长的一个的最短用时是多少。由于她不会算，所以希望由你告诉她。

inputFormat:
输入文件包括m+1 行。

第一行包含三个正整数n,k 和m，分别表示知识点的数量，Kiana 希望少年自己想出来的联系的数量和联系的总数量。

接下来m 行，每行包含四个正整数a,b,Ti 和ti，表示在知识点a 和b 之间可以构造出一个联系，这个联系由少年自己想出来需要花费 Ti 的时间，而Kiana 直接讲出来需要花费ti 的时间。

outputFormat:
输出文件包括一行。

第一行包含一个正整数，表示构造的联系中耗时最长的一个的最短用时。


title: 学校选址 II

description: 在一条大路一旁有许多栋楼，每栋楼里有许多小学生（哈哈哈一波小学生来袭！）。但是这条路上没有小学！！！！所以唯恐世界不乱的牛A打算在路上（汽车什么的都不敢来这个小学生云集的地方咯，所以不用担心安全问题）任选几点（可以和楼重合，当然也可以不重合）建立小学，且使所有小学生上学走的路程之和最短。牛A发现修建一所小学根本无法满足他唯恐世界不乱的（变态）心理，所以他准备建立K所小学。

inputFormat:
第一行2个整数，表示楼数n，学校数k（1<=n,k<=100）

第二行n个整数，表示每栋楼的学生数（0＜每栋楼学生数≤100 )

第三行n-1个数，分别表示楼i到楼i+1之间距离（1≤距离≤100，1≤i≤n-1）

outputFormat: 即学生走的距离和的最小值


title: 三角形计数

background: 三角形计数(triangle) 递推

description: 把大三角形的每条边 $n$ 等分，将对应的等分点连接起来（连接线分别平行于三条边），这样一共会有多少三角形呢？编程来解决这个问题。

inputFormat: 第一行为整数 $t(t≤100)$，表示测试数据组数；接下来 $t$ 行，每行一个正整数 $n(n≤500)$。

outputFormat: 对于每个 $n$，输出一个正整数，表示三角形个数。


title: 【模板】树套树

description:
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

1. 查询 $k$ 在区间内的排名

2. 查询区间内排名为 $k$ 的值

3. 修改某一位置上的数值

4. 查询 $k$ 在区间内的前驱（前驱定义为严格小于 $x$，且最大的数，**若不存在输出 `-2147483647`**）

5. 查询 $k$ 在区间内的后继（后继定义为严格大于 $x$，且最小的数，**若不存在输出 `2147483647`**）

inputFormat:
第一行两个数 $n,m$，表示长度为 $n$ 的有序序列和 $m$ 个操作。

第二行有 $n$ 个数，表示有序序列。

下面有 $m$ 行，$opt$ 表示操作标号。

若 $opt=1$，则为操作 $1$，之后有三个数 $l~r~k$，表示查询 $k$ 在区间 $[l,r]$ 的排名。

若 $opt=2$，则为操作 $2$，之后有三个数 $l~r~k$，表示查询区间 $[l,r]$ 内排名为    $k$ 的数。

若 $opt=3$，则为操作 $3$，之后有两个数 $pos~k$，表示将 $pos$ 位置的数修改为 $k$。

若 $opt=4$，则为操作 $4$，之后有三个数 $l~r~k$，表示查询区间 $[l,r]$ 内 $k$ 的前驱。

若 $opt=5$，则为操作 $5$，之后有三个数 $l~r~k$，表示查询区间 $[l,r]$ 内 $k$ 的后继。

outputFormat: 对于操作 $1,2,4,5$，各输出一行，表示查询结果。

hint:
$1\le n,m\le5\times 10^4$，序列中的值在任何时刻 $\in[0,10^8]$。

题目来源：bzoj3196 / Tyvj1730，在此鸣谢。

此数据为洛谷原创。**（特别提醒：此数据不保证操作 4、5 一定存在，故请务必考虑不存在的情况。）**


title: 神秘数字

background: 在公元XXXX年，侦探小明收到了组织的神秘信息，在Y市的某个地方有一道神秘的门。小明到达了那个门后，发现门上有一行字：“这个门需要密码才能解锁。”小明左找右找，终于找到了一张字条：“现在给你n个数，请你求出这n个数里面，有多少个连续的数的平均数大于某个给定的数M？注意：这个数可能会很大，请输出这个数对92084931取模的结果。最终的结果即是这个门的密码。”小明苦思冥想了半天，但始终找不到答案。于是他来求助于你。请你帮他解决这个问题。由于小明十分着急，他最多只能等1秒。

description: 给定n个数，请你帮助小明求出里面有多少个连续的数的平均数大于给定的某个数M.并将这个方案数输出。注意：这个数可能会很大，所以请输出这个数对92084931取模的结果。

inputFormat: 两行。第一行为两个数n和M。第二行为n个数。

outputFormat: 一行一个数，即问题的解对92084931取模的结果


title: 【模板】重链剖分/树链剖分

description:
如题，已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

- `1 x y z`，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。

- `2 x y`，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。

- `3 x z`，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。

- `4 x` 表示求以 $x$ 为根节点的子树内所有节点值之和

inputFormat:
第一行包含 $4$ 个正整数 $N,M,R,P$，分别表示树的结点个数、操作个数、根节点序号和取模数（**即所有的输出结果均对此取模**）。

接下来一行包含 $N$ 个非负整数，分别依次表示各个节点上初始的数值。

接下来 $N-1$ 行每行包含两个整数 $x,y$，表示点 $x$ 和点 $y$ 之间连有一条边（保证无环且连通）。

接下来 $M$ 行每行包含若干个正整数，每行表示一个操作。

outputFormat: 输出包含若干行，分别依次表示每个操作 $2$ 或操作 $4$ 所得的结果（**对 $P$ 取模**）。

hint:
**【数据规模】**

对于 $30\%$ 的数据： $1 \leq N \leq 10$，$1 \leq M \leq 10$；

对于 $70\%$ 的数据： $1 \leq N \leq {10}^3$，$1 \leq M \leq {10}^3$；

对于 $100\%$ 的数据： $1\le N \leq {10}^5$，$1\le M \leq {10}^5$，$1\le R\le N$，$1\le P \le 2^{30}$。所有输入的数均在 `int` 范围内。

**【样例说明】**

树的结构如下：

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

各个操作如下：

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

故输出应依次为 $2$ 和 $21$。


title: [NOI2009] 植物大战僵尸

background: Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。Plants（植物）和 Zombies（僵尸）是游戏的主角，其中 Plants 防守，而 Zombies 进攻。该款游戏包含多种不同的挑战系列，比如 Protect Your Brain、Bowling 等等。其中最为经典的，莫过于玩家通过控制 Plants 来防守 Zombies 的进攻，或者相反地由玩家通过控制 Zombies 对 Plants 发起进攻。

description:
现在，我们将要考虑的问题是游戏中 Zombies 对 Plants 的进攻，请注意，本题中规则与实际游戏**有所不同**。游戏中有两种角色，Plants 和 Zombies，每个 Plant 有一个攻击位置集合，它可以对这些位置进行保护；而 Zombie 进攻植物的方式是走到植物所在的位置上并将其吃掉。

游戏的地图可以抽象为一个 $N$ 行 $M$ 列的矩阵，行从上到下用 $0$ 到 $N–1$ 编号，列从左到右用 $0$ 到 $M–1$ 编号；在地图的每个位置上都放有一个 $Plant$，为简单起见，我们把位于第 $r$ 行第 $c$ 列的植物记为 $P_{r, c}$。

Plants 分很多种，有「攻击类」「防守类」和「经济类」等等。为了简单的描述每个 Plant，定义 $\operatorname{Score}$ 和 $\operatorname{Attack}$ 如下：

* $\operatorname{Score}(P_{r, c})$ — Zombie 击溃植物 $P_{r, c}$ 可获得的能源。
若 $\operatorname{Score}(P_{r, c})$ 为非负整数，则表示击溃植物 $P_{r, c}$ 可获得能源 $\operatorname{Score}(P_{r, c})$，若为负数表示击溃 $P_{r, c}$ 需要付出能源 $-\operatorname{Score}(P_{r, c})$。

* $\operatorname{Attack}(P_{r, c})$ — 植物 $P_{r, c}$ 能够对 Zombie 进行攻击的位置集合。

Zombies 必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies 攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此 Zombies 的进攻总是从地图的右侧开始。也就是说，对于第 $r$ 行的进攻，Zombies 必须首先攻击 $P_{r, M-1}$；若需要对 $P_{r, c}$（$0 \le c < m - 1$）攻击，必须将 $P_{r,M-1}, P_{r, M-2} \cdots P_{r, c+1}$ 先击溃，并移动到位置 $(r, c)$ 才可进行攻击。

在本题的设定中，Plants 的攻击力是无穷大的，一旦 Zombie 进入某个 Plant 的攻击位置，该 Zombie 会被瞬间消灭，而该 Zombie 没有时间进行任何攻击操作。因此，即便 Zombie 进入了一个 Plant 所在的位置，但该位置属于其他植物的攻击位置集合，则 Zombie 会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，Plant 的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。

Zombies 的目标是对 Plants 的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套 Zombies 的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

inputFormat:
第一行包含两个正整数 $N$ 和 $M$，分别表示地图的行数和列数。

接下来 $N \times M$ 行描述每个位置上植物的信息。第 $r \times M + c + 1$ 行按照如下格式给出植物 $P_{r, c}$ 的信息：

第一个整数为 $\operatorname{Score}(P_{r,c})$，第二个整数为集合 $\operatorname{Attack}(P_{r,c})$ 中的位置个数 $w$，接下来 $w$ 个位置信息 $(r', c')$，表示 $P_{r, c}$ 可以攻击位置第 $r'$ 行第 $c'$ 列。

outputFormat: 仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为 $0$。

hint:
#### 数据规模与约定
- 对于 $20\%$ 的数据，保证 $ N, M \le 5$。
- 对于 $40\%$ 的数据，保证 $ N, M \le 10$。
- 对于 $100\%$ 的数据，保证 $1 \le N \le 20$，$1 \le M \le 30$，$-10^4 ≤ \operatorname{Score} \le 10^4$。

#### 说明
题面由 @syksykCCC 修改。


title: 小笼包

background: JOI同学的午饭，是在中华料理店买的小笼包。这是一种用小麦粉制成的皮包着馅和热汤的料理，吃的时候，热汤会飞溅出来。

description:
JOI 同学点的小笼包套餐，由馅料不同的 $N$ 个小笼包组成。$N$ 个小笼包等间隔排成一列，编号为 $1$ 到 $N$。第 $i$ 个小笼包与第 $j$ 个小笼包之间的距离是绝对值 $\vert i - j \vert$。
JOI 同学按照顺序吃小笼包。最初，所有的小笼包的美味度都是 $0$。吃第 $i$ 个小笼包时，汤汁向周围飞散，与第 $i$ 个小笼包距离 $D_i$ 以下的小笼包都淋上了汤汁，而被淋上汤汁的小笼包的美味度会增加 $A_i$。也就是说，吃第 $i$ 个小笼包的时候，第 $j$ 个小笼包 $(1 \leq j \leq N $ 并且 $ i - D_i \leq j \leq i + D_i)$ 还没有吃到的话，第 $j$ 个小笼包的美味度就增加 $A_i$。

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

JOI 同学要在吃小笼包的顺序上下功夫，让吃的小笼包的美味度的合计最大化。

inputFormat:
输入共 $3$ 行。

第 $1$ 行是 $1$ 个整数 $N$。

第 $2$ 行是 $N$ 个整数 $D_1,D_2,...,D_N (0 \leq D_i \leq 7) $，以空格分隔。

第 $3$ 行是 $N$ 个整数 $A_1,A_2,...,A_N (0 \leq A_i \leq 1000) $，以空格分隔。

outputFormat: 共 $1$ 行，输出 JOI 同学吃的小笼包的美味度的合计最大值。

hint:
样例 $1$ 的说明：以第 $5 \rightarrow$ 第 $3 \rightarrow$ 第 $1 \rightarrow$ 第 $2 \rightarrow$ 第 $4$ 的顺序吃的话，美味度合计为 $20$，因为美味度超过 $20$ 的吃法是不存在的，所以这是最好的。

本题是 2014 年日本信息学奥林匹克（JOI）预选第 6 题。


title: hzwer 爱折纸

description:
hzwer 买到了一张神奇的小纸条，初始时它由 $N$ 个格子组成，每个格子上面有一个整数 $N_i$，显然每两个相邻的格子之间有一条分界线，hzwer 可以选择任意一条分界线，将整张纸条进行向左翻折，如果翻折后有两个格子重叠，那么翻折后的格子上数字为原两个格子数字之和，否则数字保持不变。hzwer 也可以将整张纸条进行向左翻转，翻转之后第 $i$ 个格子的数字变成第 $N - i + 1$ 个格子的数字。

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

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

inputFormat:
多组数据，最多 $5$ 组，每组数据由四行组成：

第一行包含一个整数 $N$，代表了初始纸条的格子数。

第二行包含 $N$ 个整数，代表了初始时每个格子的值 $N_i$。

第三行包含一个整数 $M$（$M \le N$），代表了理想纸条的格子数。

第四行包含 $M$ 个整数，代表了理想纸条上每个格子的值 $M_i$。

outputFormat: 每组数据包含一个字母，`S` 代表可行，`N` 代表不可行。


title: 时间表

background: 小 A 是一个电话服务中心的主管，他的团队有一大批人。他们团队中的每个人都会花费他们的时间参加会议和通过电话与客户通话，当然还有研究团队的项目也是要花费他们的时间的。

description:
他们中的每个人在每个小时只能在参加会议、和客户通话、研究项目三者中选择一个来进行。为了提高效率，每个小时必须完整地奉献到这一项工作中，不能中途改变。

小 A 所在的地方很奇怪，他们一个星期有 $D$ 天，从 $1$ 到 $D$ 标号。为了照顾员工的嗓子，第 $i$ 个人在每个星期最多能够与客户通话 $L_i$ 小时。

开会是已经计划好的事情，对于每个人他们需要在什么时间参加会议是确定的。这个电话服务中心每天要有 $H$ 个小时的时间是可以回复客户的电话的，为了简便，这 $H$ 个小时被从 $1$ 到 $H$ 标号。

对于每周的每个小时，有多少客户会连接到电话服务中心是已知的。因此，小 A 知道他在第 $i$ 天的第 $j$ 个小时必须安排 $R_{i,j}$ 个员工来和客户通话。如果第 $k$ 个人在第 $i$ 天的第 $j$ 个小时没有会议可以和客户通话，那么 $F_{k,i,j}$ 的值为 $1$，如果有会议则为 $0$。

再次说明，小  A的世界十分奇怪，他们除了每周可能不是 $7$ 天以外，每天也可能不是 $24$ 个小时。

小 A 需要为每个员工创建一个时间表。由于员工也需要吃饭和休息，每天都会有一个午休时间，这段时间是从 $L_{\text{T}_\text{begin}}$ 开始到 $L_{\text{T}_\text{end}}$ 结束（$L_{\text{T}_\text{begin}}$ 和 $L_{\text{T}_\text{end}}$ 也包含在内）。小 A 需要确保每个员工在这段时间内至少有一个小时是没有参加会议或与客户通话的，以便他们可以吃饭和休息，或者做自己想做的事情。

如果某个人在某个小时内没有会议也没有和客户通话，那他在这个小时就可以去研究公司项目，研究公司项目也算在工作时间之内。另外，他们有可能会去研究自己的项目，然而这是不算在工作时间内的。

小 A 想要知道，他是否有可能安排出这样一个时间表，并且满足：

- 每个人每天最多花费 $N$ 个小时在参加会议和客户通话上；
- 每个人每周最多花费 $L_i$ 个小时和客户通话；
- 每个人在午休时间至少有一个小时没有参加会议或和客户通话；
- 对于第 $i$ 天第 $j$ 个小时，恰好有 $R_{i,j}$ 个人可以与客户通话。

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

每组数据第一行包含四个整数 $P, D, H, N$，分别表示团队的人数，每周需要工作的天数，每天电话服务中心可以响应客户电话的小时数，以及每天每个人的工作时长；

接下来一行包含 $P$ 个整数，第 $i$ 个表示 $L_i$；

再接下来一行包含两个整数$L_{\text{T}_\text{begin}}$ 和 $L_{\text{T}_\text{end}}$，表示午休时间段；

接下来 $D$ 行每行包含 $H$ 个整数，第 $i$ 行第 $j$ 个整数表示 $R_{i,j}$；

再接下来 $P$ 个块，每个块有 $D$ 行，每行包含 $H$ 个整数。第 $k$ 个块的第$i$ 行的第 $j$ 个数表示 $F_{k,i,j}$。

outputFormat: 共 $T$ 行，如果第 $i$ 组数据存在可行方案则输出 `Yes`，否则输出 `No`。

hint:
对于 $100\%$ 的数据满足有

$1 \leq T \leq 5,1 \leq N \leq H \leq 70$

$1 \leq D, P\leq 70,1 \leq L_i \leq N\times D, 0 \leq R_{i, j} \leq 15$

$0 \leq F_{k, i, j} \leq 1,1 \leq L_{\text{T}_\text{begin}} \leq L_{\text{T}_\text{end}} \leq N$。


title: 大逃离

background: zrz走进了一个奇葩的迷宫，他发现自己迷路了，想逃出来，他好不容易数完了所有的路，累的快晕了，只好叫你帮忙咯。

description: 这是一棵有n个节点的图，有m条双向边，每一条路有w个单位距离，zrz在1的位置，出口在n的位置，不过zrz脑子出了点bug，于是不想走最短的路，想走第2短的路，第2短路径允许与最短路径有重边，然后也可以重复通过一些节点和路，注意如果有多条路径都是最短路径，那么他们都不能叫第2短路径。但是zrz觉得如果接下来进入的一个节点所直接连接的地方小于k个（起点和终点除外），那么他就不敢进去。

inputFormat:
第一行3个数：n,m,k

接下来m行：每行3个数，u，v，w。表示从u到v有一条权值为w的边。（u,v<=n，w<=10000）

outputFormat: 一个数：表示从s走到t的第2短路的值，如果不存在，输出-1

hint:
对于50%的数据：n<=10,m<=10

对于90%的数据：n<=1000,m<=20000

对于100%的数据：n<=5000，m<=100000

另外，k比较小

样例2最短路径是300（1-2-4）。因为从2无法走到3（3连接到的节点只有2个），所以可以1-2-1-2-4，第二短路为500。


title: 写程序

background: zrz在写程序，他叫你帮他看看他的程序有没有问题。

description:
有一个若干行的程序，每一行只有一个命令，可能出现的命令有一下几种

int a[maxn]    声明一个数组，开头一定是int，不会是别的什么longlong之类的，a是指一个数组的名称（不一定是a，也有可能是别的字母或者多个字母，总之长度不超过10），后面是一个中括号和一个数字或一个变量，表示数组大小（从0到maxn-1，maxn<=100），数组声明之后里面的数均为0。

a[i] h  把h赋给a[i]（也就是a[i]=h），同样h可能是一个数字或者是一个变量，i代表一个数字或者是一个变量。

cout h 输出h，h一定是个变量。

inputFormat: 若干行：每行一个命令

outputFormat: 对于每一个输出的命令（即cout），输出一行。如果在某一行发现有数组下标越界（切记，只可能出现这种错误，不会出现别的比如重定义之类的问题），不管是哪个命令，都要立即停止，无论下面有多少行命令都忽略，并输出-1。

hint: 行数不会太多的，变量可能嵌套，如 a[a[b[0]]]等等，也有可能出现大写字母，所有的出现的数字不会超过10^9，也不会是负数，更不会是小数。


title: Cool loves maids

background: Cool 非常喜欢妹子，以至于 Cool 在百度上有一个非常神奇的 ID 【雾】。

description:
Cool 现在搞清楚了女生宿舍的地形。女生宿舍是由很多栋楼构成的，它们可以被抽象成 $20\times 20$ 的方格。

Cool 的妹子们所处的地方可以被表示为实数类型的坐标。当一个妹子 $(x,y)$ 在楼 $(i,j)$ 中，当且仅当 $i \le x<i+1$，$j \le y<j+1$，$i,j\in \Z$。两个妹子之间有距离，当且仅当一个妹子所在的楼的横纵坐标均小于另一个妹子所在的楼，此时她们之间的距离为她们自身坐标的曼哈顿距离。

现在 Cool 要搞一个大统计：求 $n$ 个妹子之间所有距离之和。

inputFormat:
为了避免输入文件过大无法上传在读入方面消耗过多时间，本题采取数据生成方案。

输入包含两行：

- 第一行，一个整数 $n$；
- 第二行，包含 $6$ 个整数 $\mathrm{rxa},\mathrm{rxc},\mathrm{rya},\mathrm{ryc},\mathrm{rza},\mathrm{rzc}$。

所有的实数都采用如下方式生成：

1. 初始化 $x=y=z=0$；
2. 重复以下过程：
   - $x=(y\times \mathrm{rxa}+\mathrm{rxc})\bmod \mathrm{rp}$；
   - $y=(z\times \mathrm{rya}+\mathrm{ryc})\bmod \mathrm{rp}$；
   - $z=(x\times \mathrm{rza}+\mathrm{rzc})\bmod \mathrm{rp}$。

每次得到的实数即为 $(x\bmod 20)+(y\bmod 10)\div 10+(z\bmod 10)\div 100$。$\mathrm{rp}=2333333$。

第 $i$ 个妹子将以第 $2i-1$ 个生成实数为横坐标，第 $2i$ 个生成实数为纵坐标。

outputFormat: 输出包含一行一个实数，表示 $n$ 个妹子之间所有距离之和的平均值，保留 $5$ 位小数。

hint:
### 数据范围及约定

对于全部数据，保证 $1\le n\le 5\times 10^6$。


title: Cool loves shaxian

background: Cool 非常非常喜欢吃沙县,确切地说,他非常非常把各种无辜群众拉到沙县去吃饭(╯‵□′)╯(┻━┻。大家都非常非常想知道沙县到底给了 Cool 多少钱带盐沙县小吃,以便未来威逼利诱 Cool 来请客吃隔壁的 KFC。经过多方追踪,大家发现了带盐费发放的某一些规律ヾ(o◕∀◕)ノヾ。

description:
沙县发放带盐费以壕著称。这家沙县发放带盐费时有个指数 $d$。他会发放 $n$ 轮带盐费，在第 $i$ 轮中，都会发放 $f(i) = \sum_{k|i} k^d (i \leq n)$ 这么多的钱。

现在大家有了 $Q$ 个问题，每个问题都形如 Cool 参加从第 $L_i$ 轮到第 $R_i$ 轮的带盐活动，将能获得多少钱。（保证 $1 \leq L_i \leq R_i \leq n$）

由于开在南大街的沙县小吃不是一般的有钱啊，所以呢，我们要计算的是 Cool 收到的钱对 $10^ 9 + 7$ 取模得到的答案。

inputFormat:
输入包含若干行。

第一行，三个整数，$n, d, Q$。（$n\leq 10^7$，$d\leq 10^{18}$，$q\leq 5\times 10^4$。

接下来的 $Q$ 行,每行两个整数 $L_i, R_i$。

outputFormat:
输出包含 $Q$ 行。

每行一个整数，表示 Cool 得到的带盐费。


title: Cool loves jiaoyi

background: Cool 交易得十分熟练。现在 Cool 即将参加一场 NOIP 普及组模拟赛。Cool 什么都不会，他将通过交易来获得每一题的题解 / 标程。

description:
Cool 的交易对象构成了一个树形结构。

对于每一场轰轰烈烈的交易，都会有一个交易起点和交易终点。在树上从交易起点到交易终点的路径称作交易链，交易链上的所有交易对象都将加入这场交易，交易的代价即为交易对象数。

现在 Cool 面临着 $m$ 场交易，现在 Cool 要钦点 $k$ 场交易，使得存在某个神秘交易对象参与了所有 $k$ 场交易，并且最小化这 $k$ 场交易中代价之差的最大值。

inputFormat:
输入包含若干行。

第一行三个整数 $,n,m,k$ 代表交易对象数、交易场数和 Cool 钦定的 $k$。接下来的 $n-1$ 行，每行两个整数 $u,v$ 代表交易对象 $u,v$ 在交易树上相连。

接下来的 $m$ 行，每行两个整数 $s,t$，表示每场交易的交易起点和交易终点（起点终点可以重合）。

outputFormat: 输出包含一个整数，表示 Cool 钦点的最小的最大代价之差，若不存在这样的 $k$ 场交易，输出 $-1$。

hint: 选择第 $1,2,3$ 三场交易，则交易对象 $3,4,5$ 被同时交易了 $3$ 次，且三场交易的代价分别为 $3,4,4$。他们交易代价之差最大为 $4-3$。此时最优。


title: Cool loves touli

background: Cool 一直都很崇拜 touli。

description:
有一天 Cool 和 touli 在打多校，突然开始讨论怎么样的阵容比较厉害。Cool 觉得一个阵容，将他们的等级从低到高排序后，攻击力应该是递增的。Cool 就问 touli 这个阵容最多有几个人。

不过 touli 觉得这个问题实在太 SB，就改变了条件，他认为等级从低到高排序后，对于任意两个排序后相邻的英雄，等级低的英雄的攻击力应该不大于等级高的英雄的力量，等级高的英雄的攻击力应当不小于等级低的英雄的智力。

现在 Cool 想知道若干个英雄中，最多能选出多少个英雄加入阵容。

inputFormat:
第一行 $n$ 表示有 $n$ 个英雄。

接下来 $n$ 行，每行 $4$ 个整数 $l,s,w,a$，分别表示该英雄的等级、力量、智力、攻击力。

outputFormat: 一个数,表示最多能选出的英雄个数。

hint:
选择第 $1$ 个和第 $3$ 个英雄，符合条件。对于第 $1$ 个和第 $2$ 个英雄，第 $2$ 个英雄的攻击力小于第 $1$ 个英雄的智力，所以不能同时存在。

$n\leq 10^5$，$l,s,w,a\le10^8$，$l$ 互不相同。


title: Catch the theives

background: 你们懂的，浙江某高中的保安是非常敬（sui）职（bian）的，但是有一天，一群奶牛（不要问我怎么想的），溜进了校园走进了二食堂，偷吃了可口的饭菜（没尝过）。现在 headmaster 非常生气，让保安严查此事。这时 \*\*\* 走过，勤劳而又严谨的保安求助 \*\*\*，\*\*\* 很忙所以把任务交给了你。要不要来杯咖啡先。

description: karlven 听说保安在打游戏值班时看到有 $4$ 只奶牛滚出校门（吃太饱了？），而且这个品种的奶牛非常贪心，而且有秩序。怎么体现？偷吃的时候他们会排队，且后一只偷吃的量是前一只的**整数倍（设为 $k,k>1$）**，按照他的经验估计这些奶牛**最多能吃 $m$ 吨**的食物，一旦**超过就会暴毙**化为灰烬，所以一只奶牛**不会**吃超过 $m$ 吨的食物并且只能**一吨一吨**吃。一旦有一只奶牛无法吃东西，他就会攻击同伴然后自尽。现在 karlven 不告诉你 $m$ 的值，只告诉你奶牛**能够一起偷吃并且一起安全滚出校门**的方案数量 $n$（$n\le10^{15}$，不要方），请你算出 $m$ 的值，若有多种解，输出**最小的可能值**。如果你怎么算都算不出，就输出 $-1$，然后投诉保安。

inputFormat: 一个数 $n$。

outputFormat: 你算出的答案，一个整数。


title: Protect the school

background: 话说上回保安因为奶牛事件而搞得地位岌岌可危，所以他们决定好好看守这个学校，他们有一个计划。但是由于学校太大了，他们计划不好，所以找到上次帮他的你，请你解决他的苦难。然后他又可以开始了手机游戏之旅。

description: 学校有 $n$ 个检查点，由于保安懒得动脑筋，他们决定在这 $n$ 个检查点之间建立 $m$ 条通道，由于学校的懒政以及军事化管理，这些路是单向的，逆向通过会被处分。保安们人手不够（游戏任务太多），他们决定只挑选一些点来站岗，由于保安身怀绝技，可以瞬间通过任何他站岗点可以走到的路（瞬移到到任何连通的点）。每一个检查点有一个值表示这个点的困难程度。为了保护学校，请你帮他们出个主意，保证一旦有一个检查点发生事件，都能有保安瞬间抵达。但是为了舒服和管理便利，请你告诉他们在使用最少的保安数量的情况下最小的困难总和。

inputFormat:
第一行一个整数 $n$，代表检查点数量。

接下来一行 $n$ 个整数，代表困难程度。

接下来一行一个数 $m$，表示道路的数量。

接下来 $m$ 行每行两个整数 $u,v$ 代表 $u$ 到 $v$ 有一条单向通道。

outputFormat:
两个整数。

第一个整数表示最小困难和。第二个整数表示在保证最小困难和以及最少保安数量的条件下，可选的方案总数。

hint: $1 \le n \le 10 ^ 4,1 \le m \le 5 \times 10 ^ 4$，保证答案在 `int` 范围内。


title: 校园网络【[USACO]Network of Schools加强版】

background: 浙江省的几所 OI 强校的神犇发明了一种人工智能，可以 AC 任何题目，所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空，他们来找你帮助他们。

description: 共有 $n$ 所学校 $(1 \leq n \leq 10000)$ 已知他们实现设计好的网络共 $m$ 条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

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

接下来 $n$ 行每行有若干个整数，用空格隔开。

第 $i+1$ 行，每行输入若干个非零整数 $x$，表示从 $i$ 到 $x$ 有一条线路。以 $0$ 作为结束标志。

outputFormat:
第一行一个整数，表示至少选几所学校作为共享软件的母机，能使每所学校都可以用上。

第二行一个整数，表示至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。


title: 母舰

background:
广东汕头聿怀初中 Train#3 Problem 1

（有没有红警既视感~）

description:
在小 A 的星际大战游戏中，一艘强力的母舰往往决定了一场战争的胜负。一艘母舰的攻击力是普通的 MA（Mobile Armor）无法比较的。

对于一艘母舰而言，它是由若干个攻击系统和若干个防御系统组成的。两艘母舰对决时，一艘母舰会选择用不同的攻击系统去攻击对面母舰的防御系统。当这个攻击系统的攻击力大于防御系统的防御力时，那个防御系统会被破坏掉。当一艘母舰的防御系统全部被破坏掉之后，所有的攻击都会攻击到敌方母舰本身上去造成伤害。

这样说，一艘母舰对对面的伤害在一定程度上是取决于选择的攻击对象的。

在瞬息万变的战场中，选择一个最优的攻击对象是非常重要的。所以需要写出一个战斗系统出来，判断出你的母舰最多能对对手造成多少伤害并加以实现。

inputFormat:
输入第一行两个整数 $M$ 和 $N$，表示对方母舰的防御系统数量和你的母舰的攻击系统数量。

接着 $M$ 行每行一个整数每一个表示对方防御系统的防御力是多少。

接着 $N$ 行每行一个整数每一个表示己方攻击系统的攻击力是多少。

outputFormat: 输出仅有一行，表示可以造成的最大伤害。


title: 家谱

background: 现代的人对于本家族血统越来越感兴趣。

description: 给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

inputFormat: 输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用 `#name` 的形式描写一组父子关系中的父亲的名字，用 `+name` 的形式描写一组父子关系中的儿子的名字；接下来用 `?name` 的形式表示要求该人的最早的祖先；最后用单独的一个 `$` 表示文件结束。

outputFormat: 按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式为：本人的名字 $+$ 一个空格 $+$ 祖先的名字 $+$ 回车。

samples:
#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

samples:
Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

hint: 规定每个人的名字都有且只有 $6$ 个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有 $10^3$ 组父子关系，总人数最多可能达到 $5 \times 10^4$ 人，家谱中的记载不超过 $30$ 代。


title: [NOIP2016 提高组] 愤怒的小鸟

background: NOIP2016 提高组 D2T3

description:
Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于 $(0,0)$ 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 $y=ax^2+bx$ 的曲线，其中 $a,b$ 是 Kiana 指定的参数，且必须满足 $a < 0$，$a,b$ 都是实数。

当小鸟落回地面（即 $x$ 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 $n$ 只绿色的小猪，其中第 $i$ 只小猪所在的坐标为 $\left(x_i,y_i \right)$。

如果某只小鸟的飞行轨迹经过了 $\left( x_i, y_i \right)$，那么第 $i$ 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；

如果一只小鸟的飞行轨迹没有经过 $\left( x_i, y_i \right)$，那么这只小鸟飞行的全过程就不会对第 $i$ 只小猪产生任何影响。

例如，若两只小猪分别位于 $(1,3)$ 和 $(3,3)$，Kiana 可以选择发射一只飞行轨迹为 $y=-x^2+4x$ 的小鸟，这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有 $T$ 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。

inputFormat:
第一行包含一个正整数 $T$，表示游戏的关卡总数。

下面依次输入这 $T$ 个关卡的信息。每个关卡第一行包含两个非负整数 $n,m$，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 $n$ 行中，第 $i$ 行包含两个正实数 $x_i,y_i$，表示第 $i$ 只小猪坐标为 $(x_i,y_i)$。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 $m=0$，表示 Kiana 输入了一个没有任何作用的指令。

如果 $m=1$，则这个关卡将会满足：至多用 $\lceil n/3 + 1 \rceil$ 只小鸟即可消灭所有小猪。

如果 $m=2$，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 $\lfloor n/3 \rfloor$ 只小猪。

保证 $1\leq n \leq 18$，$0\leq m \leq 2$，$0 < x_i,y_i < 10$，输入中的实数均保留到小数点后两位。

上文中，符号 $\lceil c \rceil$ 和 $\lfloor c \rfloor$ 分别表示对 $c$ 向上取整和向下取整，例如：$\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。

outputFormat:
对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。


title: 天使的起誓

description:
Tenshi 非常幸运地被选为掌管智慧之匙的天使。在正式任职之前，她必须和其他新当选的天使一样要宣誓。

宣誓仪式是每位天使各自表述自己的使命，他们的发言稿放在 $n$ 个呈圆形排列的宝盒中。这些宝盒按顺时针方向被编上号码 $1, 2, \cdots, n - 1, n$。

一开始天使们站在编号为 $n$ 的宝盒旁。她们各自手上都有一个数字，代表她们自己的发言稿所在的盒子是从 $1$ 号盒子开始按顺时针方向的第几个。例如：有  $7$ 个盒子，如果 Tenshi 手上的数字为 $9$，那么她的发言稿所在的盒子就是 $2$ 个。现在天使们开始按照自己手上的数字来找发言稿，先找到的就可以先发言。

Tenshi 一下子就找到了，于是她最先上台宣誓：“我将带领大家开启 NOI 之门……” Tenshi 宣誓结束后，陆续有天使上台宣誓。可是有一位天使找了好久都找不到她的发言稿，原来她手上的数字 $m$ 非常大，她转了好久都找不到她想找的宝盒。

请帮助这位天使找到她想找的宝盒编号。

inputFormat: 第一行为正整数 $n$，第二行为正整数 $m$。

outputFormat: 只有一行（包括换行符），即天使想找的宝盒的编号。


title: IPv6地址压缩

background:
（友情提示：IPv6 基础知识曾多次出现在 NOIP 初赛中）Internet Protocol，互联网协议，即为我们常说的 IP。我们目前常说的 IP 主要指它的第四版，即 IPv4，它由 IETF 于 1981 年发布。它的地址长度是 $32$ 个二进制位，因此也就有 $2^{32}$ 个 IP 地址可供使用，约为 $43$ 亿，在当时，谁也没有料想到 IPv4 如此庞大的地址长度会有用完的一天。

在 21 世纪的今天，互联网的蓬勃发展早就了我们如今便利的生活。当下，世界人口已超过 70 亿，计算机和各种联网设备已经走入千家万户，而不再仅是上个世纪 80 年代科学家们的工具。此时便出现了人们日益增长的联网设备需要同落后 IPv4 地址长度之间的矛盾。尽管可以通过网络地址翻译能技术来共享 IP 地址，临时解决枯竭的问题，但显然不是长久之计。

IETF 也有先见之明，早早地于 1998 年发布了 IPv6 协议，从微软 2006 年发布的 Windows Vista 开始成为默认安装的网络协议。作为 IPv4 的继任者，它的地址长度为 $128$ 个二进制位，也就是 $2^{128}$ 个IP地址可供使用。然而面对这冗长的地址，一位记忆力不好的网络工程师小明在配置路由表时遇到了许许多多多的困难，现在他找到了你，希望你帮忙编写一个程序来按照 IPv6 地址标准的格式压缩规则来压缩 IPv6 地址。

description:
**【IPv6 格式】**

IPv6 二进位制下为 $128$ 位长度，以 $16$ 位为一组，每组以冒号“`:`”隔开，可以分为 $8$ 组，每组以 $4$ 位十六进制方式表示。

比如 `2001:0db8:0000:0000:0123:4567:89ab:cdef` 是一个合法的 IPv6 地址。

同时 IPv6 地址在某些条件下可以压缩：

1. 每组数字代表的独立十六进制数可以省略前位的 `0`。

比如上面的 IPv6 地址可被压缩为 `2001:db8:0:0:123:4567:89ab:cdef`。

2. 可以用双冒号 `::` 表示一组 `0` 或多组连续的 `0`，但只能出现一次。

比如上面的 IPv6 地址可被压缩为 `2001:db8::123:4567:89ab:cdef`。

请你帮助记忆力不好的网络工程师小明解决他遇到的问题。

**【规则补充】**

1. 输入数据为完全展开的 IPv6 地址，确保输入的 IPv6 地址不含双冒号，每组地址省略的 `0` 都会被补充上去。

2. 双冒号只能使用一次，因此我们压缩最长的全 `0` 组。

比如 `2001:0db8:0000:0000:1:0000:0000:0000`，压缩为 `2001:db8:0:0:1::`，而非 `2001:db8::1:0:0:0`。

3. 双冒号只能使用一次，因此我们在我们遇到地址中多个连续全 `0` 组长度相同时，我们压缩最前面的一个。

比如 `2001:0db8:0000:0000:ffff:0000:0000:1`，压缩为 `2001:db8::ffff:0:0:1`，而非 `2001:db8:0:0:ffff::1`。

4. 输入的 IPv6 地址可能无法被压缩，此时请照原样输出。

提示：本题所示的压缩规则与 macOS (Darwin) 默认的 IPv6 地址显示方式相同，而 Windows 和 Linux 只遇到一组全 `0` 时不会使用 `::` 进行压缩。但用此方法压缩过的 IPv6 地址一样可以被 Windows 和 Linux 正确识别。

比如 `2001:0db8:ffff:0000:0123:4567:89ab:cdef`，Darwin 压缩为 `2001:db8:ffff::123:4567:89ab:cdef`，而 Linux 和 Windows 压缩为 `2001:db8:ffff:0:123:4567:89ab:cdef`。

inputFormat: 一串 $39$ 个字符的字符串，代表一个完全展开的 IPv6 地址。

outputFormat: 一串压缩后的 IPv6 地址。


title: 图的 m 着色问题

background: 给定无向连通图 $G$ 和 $m$ 种不同的颜色。用这些颜色为图 $G$ 的各顶点着色，每个顶点着一种颜色。如果有一种着色法使 $G$ 中每条边的 $2$ 个顶点着不同颜色，则称这个图是 $m$ 可着色的。图的 $m$ 着色问题是对于给定图 $G$ 和 $m$ 种颜色，找出所有不同的着色法。

description: 对于给定的无向连通图 $G$ 和 $m$ 种不同的颜色，编程计算图的所有不同的着色法。

inputFormat: 第 $1$ 行有 $3$ 个正整数 $n,k,m$，表示给定的图 $G$ 有 $n$ 个顶点和 $k$ 条边，$m$ 种颜色。顶点编号为 $1,2,\dots,m$。接下来的 $k$ 行中，每行有 $2$ 个正整数 $u,v$，表示图 $G$ 的一条边 $(u,v)$。

outputFormat: 程序运行结束时，将计算出的不同的着色方案数输出。

hint:
数据保证，$1\leq n\leq 100$，$1 \leq k\leq 2500$。

在 $n$ 很大时保证 $k$ 足够大。

保证答案不超过 $20000$。

数据为在满足上述条件的合法数据中随机采样得到。


title: 局域网

background: 某个局域网内有 $n$ 台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用 $f(i,j)$ 表示 $i,j$ 之间连接的畅通程度，$f(i,j)$ 值越小表示 $i,j$ 之间连接越通畅，$f(i,j)$ 为 $0$ 表示 $i,j$ 之间无网线连接。

description: 现在需要解决回路问题，我们将除去一些连线，使得网络中没有回路，**不改变原图节点的连通性**，并且被除去网线的 $\sum f(i,j)$ 最大，请求出这个最大值。

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

接下来的 $k$ 行每行三个正整数 $i,j,m$ 表示 $i,j$ 两台计算机之间有网线联通，通畅程度为 $m$。

outputFormat: 一个正整数， $\sum f(i,j)$ 的最大值。

hint: 对于全部数据，保证 $1\le n \le 100$，$1\le f(i,j)\le 1000$。


title: 变幻数

description:
给定一个十进制正整数 $n$，它的递归变幻数定义如下：

- 如果 $n$ 的位数多于 $1$ 位（忽略前置的 $0$），将 $n$ 的各个位上的数相乘，乘积为 $m$。称 $m$ 为 $n$ 的子变幻数，$n$ 称为 $m$ 的父变幻数。求一个数的变幻数等于求其子变幻数。即求 $n$ 的变幻数等于求 $m$ 的变幻数。

- 如果 $n$ 的位数只有一位，$n$ 的变幻数即为它本身。 如求 $679$ 的变幻数过程为：$679 \to 378(6 \times 7 \times 9) \to 168(3 \times 7 \times 8) \to 48(1 \times 6 \times 8) \to 32(4 \times 8) \to 6(2 \times 3)$，所以 $679$ 的变幻数为 $2$。

现在的问题是给定一个子变幻数 $k$，问 $k$ 的父变幻数最小是多少？ 如：$k=18$，则 $k$ 的父变幻数可以是 $29$，也可以是 $92$。但最小为 $29$。

inputFormat: 一个子变幻数 $k$（位数 $\le 1000$）。

outputFormat: $k$ 的最小父变幻数。 当不存在父变幻数时请输出 `There is no such number!`。


title: [USACO08FEB] Dining Cows B

description:
为了避免餐厅过分拥挤，FJ 要求奶牛们分 $2$ 批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按 FJ 的设想，所有第 $2$ 批就餐的奶牛排在队尾，队伍的前半部分则由设定为第 $1$ 批就餐的奶牛占据。

由于奶牛们不理解 FJ 的安排，晚饭前的排队成了一个大麻烦。 第 $i$ 头奶牛有一张标明她用餐批次 $D_i$ 的卡片。虽然所有 $N$ 头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，FJ 找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如 $112222$ 或 $111122$。有的时候，FJ 会把整个队列弄得只有 $1$ 组奶牛（比方说，$1111$ 或 $222$）。

你也晓得，FJ 是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在 FJ 改卡片编号的时候，都不会挪位置。

inputFormat:
第一行输入一个整数 $N$（$1 \le N \le 3 \times 10 ^ 4$）。

第 $2 \sim N + 1$ 行，每行 $1$ 个整数，表示第 $i$ 头牛的用餐批次 $D_i$（$1 \le D_i \le 2$）。

outputFormat: 输出 $1$ 个整数，为 FJ 最少要改几头奶牛卡片上的编号，才能让编号变成他设想中的样子。


title: 良好的感觉

description: kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 $A_i$，$A_i$ 越大，表示人感觉越舒适。在一段时间 $\left[i, j\right]$ 内，人的舒适程度定义为 $\left[i, j\right]$ 中最不舒服的那一天的感受值 $\times$ $\left[i, j\right]$中每一天感受值的和。现在给出 kkk 在连续 $N$ 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

inputFormat:
第一行为 $N$，代表数据记录的天数。

第二行 $N$ 个整数，代表每一天的感受值。

outputFormat: 一行，表示在最舒适的一段时间中的感受值。


title: [NOIP2016 提高组] 组合数问题

background: NOIP2016 提高组 D2T1

description:
组合数 $\binom{n}{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $\binom{n}{m}$ 的一般公式：

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

其中 $n!=1\times2\times\cdots\times n$；特别地，定义 $0!=1$。

小葱想知道如果给定 $n,m$ 和 $k$，对于所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 $(i,j)$ 满足 $k\mid\binom{i}{j}$。

inputFormat:
第一行有两个整数 $t,k$，其中 $t$ 代表该测试点总共有多少组测试数据，$k$ 的意义见问题描述。

接下来 $t$ 行每行两个整数 $n,m$，其中 $n,m$ 的意义见问题描述。

outputFormat: 共 $t$ 行，每行一个整数代表所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 中有多少对 $(i,j)$ 满足 $k\mid\binom{i}{j}$。

hint:
【样例1说明】

在所有可能的情况中，只有 $\binom{2}{1} = 2$ 一种情况是 $2$ 的倍数。

【子任务】

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

- 对于全部的测试点，保证 $0 \leq n, m \leq 2 \times 10^3$，$1 \leq t \leq 10^4$。


title: 加油问题

description:
一个美国旅行代理商经常被要求去估计开车从一个城市旅行至另一个城市的最小费用。他有一个在通常路线上的大多数加油站的列表。列表包括了所有加油站的位置及当前每加仑汽油的价格。

为了简化估计费用的过程，代理商使用了以下的简化汽车驾驶员行为的规则：

- 除非汽车无法用油箱里的汽油达到下一个加油站（如果有的话）或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来。
- 在每一个停下的加油站，驾驶员总是将油加满。
- 在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上花去 $2.00$ 元。
- 在驶向加油站或目的地时，驾驶员不需要超过必须量的汽油。不需要“安全余量”。
- 驾驶员开始旅行时油箱总是满的
- 每个加油站付款时四舍五入到分（ $1$ 元等于 $100$ 分）。

你必须写一个程序以估计驾驶员在旅程上至少要为汽油和食品付多少钱。

inputFormat:
开始的 $2$ 行给出了出发地和目的地的信息。数据项的后继行代表了路线上的加油站，每个加油站用一行表示。下面是输入数据中数据项的精确格式及其含义。

第一行：一个实数——从出发地到目的地的距离（英里）

第二行：三个实数及一个整数

- 第一个实数是汽车油箱的最大的容量（加仑）
- 第二个实数是汽车每加仑汽油可以行驶的英里数
- 第三个实数是汽车在出发地城市加满油箱的费用（单位：元）
- 最后一个整数，是路线上加油站的数目 $n$。

接下来的每一行有两个实数。

- 第一个实数是从出发地到加油站的距离（单位：英里）
- 第二个实数是该加油站出售的汽油每加仑的价格（单位：分）

数据项中的所有数据都是正数。一条路线上的加油站根据其到出发地的距离递增排列。路线上不存在这样的加油站，它到出发点的距离大于从出发点到目的地的距离。每条路线上的加油站都被适当的安排以使得任何汽车都能从出发地开到目的地。

outputFormat: 仅一行，一个实数（保留两位小数），表示最小的花费（单位：元）。

hint:
### 数据范围及约定

对于全部数据，$n \le 51$。


title: [USACO08NOV] Light Switching G

description:
Farmer John tries to keep the cows sharp by letting them play with intellectual toys. One of the larger toys is the lights in the barn. Each of the $N (2 \le N \le 10^5)$ cow stalls conveniently numbered $1\ldots N$ has a colorful light above it.

At the beginning of the evening, all the lights are off. The cows control the lights with a set of N pushbutton switches that toggle the lights; pushing switch i changes the state of light i from off to on or from on to off.

The cows read and execute a list of $M(1\le M \le 10^5)$ operations expressed as one of two integers ( $0 \le$ operation $\le 1$ ).

The first kind of operation (denoted by a $0$ command) includes two subsequent integers $S_i$ and $E_i (1 \le S_i \le E_i \le N)$ that indicate a starting switch and ending switch. They execute the operation by pushing each pushbutton from $S_i$ through $E_i$ inclusive exactly once.

The second kind of operation (denoted by a $1$ command) asks the cows to count how many lights are on in the range given by two integers $S_i$ and $E_i (1 \le S_i \le E_i \le N)$ which specify the inclusive range in which the cows should count the number of lights that are on.

Help FJ ensure the cows are getting the correct answer by processing the list and producing the proper counts.

农夫约翰试图让奶牛玩智力玩具来保持它们的敏锐。谷仓里的灯是较大的玩具之一。$N (2 \le N \le 10^5)$ 个牛栏编号为 $1 \ldots N$，每个牛栏上面都有一盏灯。起初所有的灯都关着。

共有 $M$ 次操作，分为两种。
1. 指定一个区间 $[S_i,E_i]$，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
2. 指定一个区间 $[S_i,E_i]$，要求你输出这个区间内有多少盏灯是打开的。

inputFormat:
第 $1$ 行: 用空格隔开的两个整数 $N$ 和 $M$，$N$ 是灯数。

第 $2\ldots M+1$ 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, $S_i$ 和 $E_i$。

若指令号为 $0$，则表示改变 $[S_i,E_i]$ 区间内的灯的状态（把开着的灯关上，关着的灯打开）。

若指令号为 $1$，则表示输出 $[S_i,E_i]$ 这个区间内有多少盏灯是打开的。


title: [HEOI2016/TJOI2016] 排序

description:
在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。

这个难题是这样子的：给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种：

- `0 l r` 表示将区间 $[l,r]$ 的数字升序排序
- `1 l r` 表示将区间 $[l,r]$ 的数字降序排序

注意，这里是对**下标**在区间 $[l,r]$ 内的数排序。
最后询问第 $q$ 位置上的数字。

inputFormat:
输入数据的第一行为两个整数 $n$ 和 $m$，$n$ 表示序列的长度，$m$ 表示局部排序的次数。

第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个排列。

接下来输入 $m$ 行，每一行有三个整数 $\text{op},l,r$，$\text{op}$ 为 $0$ 代表升序排序，$\text{op}$ 为 $1$ 代表降序排序, $l,r$ 表示排序的区间。

最后输入一个整数 $q$，表示排序完之后询问的位置

outputFormat: 输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 $q$ 位置上的数字。

hint:
河北省选2016第一天第二题。

对于 $30\%$ 的数据，$n,m\leq 1000$

对于 $100\%$ 的数据，$n,m\leq 10^5$，$1\leq q\leq n$


title: [HEOI2016/TJOI2016] 游戏

description:
在 2016 年，佳媛姐姐喜欢上了一款游戏，叫做泡泡堂。

简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者躲开对手的炸弹。在玩游戏的过程中，小 H 想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。

给定一张 $ n \times m $ 的网格地图:其中 ``*`` 代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。 ``x`` 代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。``#`` 代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。例如：给出 $ 1 \times 4 $ 的网格地图 `` *xx*``，这个地图上最多只能放置一个炸弹。给出另一个$ 1 \times 4 $ 的网格地图 ``*x#*``，这个地图最多能放置两个炸弹。

现在小 H 任意给出一张 $ n \times m $ 的网格地图，问你最多能放置多少炸弹。

inputFormat:
第一行输入两个正整数 $ n, m $，$ n $ 表示地图的行数，$ m $ 表示地图的列数。

接下来输入 $ n $ 行 $ m $ 列个字符，代表网格地图。``*``的个数不超过 $ n \times m $ 个。

outputFormat: 输出一个整数 $ a $，表示最多能放置炸弹的个数。

hint: $1 \leq n,m \leq 50$


title: 瓶子国的故事

background:
这是一道非传统题。

传说有一个国家叫瓶子国，里面有大大小小的瓶子。

现在瓶子国想要学习邻居跳蚤国发展计算机，可是瓶子国没有计算机只有瓶子。

于是瓶子国国王就给了你一些瓶子，让你实现一些计算任务。

description:
我们用水的量来描述一个数。

- 一个瓶子的容量为它最多可以装的水的数量。

瓶子国国王认为瓶子可以干这些事：

- $\verb!I!$：制造一个新瓶子，它的容量和里面装的水量都为输入的数，这个瓶子的编号为 $\textbf{当前最大编号} +1$。
- $\verb!F !s$；把编号为 $s$ 的瓶子里的水倒满。
- $\verb!E !s$：把编号为 $s$ 的瓶子里的水倒空。
- $\verb!C !s$：制作一个新瓶子，它的容量为 $s$，里面没装水，这个瓶子的编号为 $\textbf{当前最大编号} +1$。注意由于瓶子容积有限，$0\le s\le 10^9$。
- $\verb!M !s$：制作一个新瓶子，它的容量为 $\textbf{s 号瓶子里装的水的数量}$，里面没装水，这个瓶子的编号为 $\textbf{当前最大编号}+1$。
- $\verb!T !a\ b$：把 $a$ 瓶往 $b$ 瓶倒水，直到 $a$ 瓶空或者 $b$ 瓶满为止。（注意 $a\neq b$）。
- $\verb!O !s$：把 $s$ 号瓶子里的水输出。

还有一种昂贵的操作：

- $\verb!K !a\ b$：制作一个新瓶子，它的容量为 $\textbf{a 号瓶子的容量} \times \textbf{b 号瓶子的容量}$，这个瓶子的编号为 $\textbf{当前最大编号}+1$。注意由于瓶子容积有限，$\textbf{a 号瓶子的容量}\times\textbf{b 号瓶子的容量}$，不能超过 $10^9$。（使用这种操作要扣分，评分规则详见下方提示）

现在瓶子国国王把这些操作给了你，你只要输出这些操作，瓶子国的瓶子们就会为你执行！

瓶子国国王给了你一些计算任务，你只需要实现这些任务就行啦！

左边是数据点编号，右边是计算任务。

1. 输入 $a$ 和 $b$，计算 $a+b$。（$0\le a,b\le 10^5$）
2. 输入 $a$ 和 $b$，计算 $|a-b|$。（$0\le a,b\le 10^5$）
3. 输入 $a$ 和 $b$，计算 $\max(a,b)$。（$0\le a,b\le 10^5$）
4. 输入 $a$ 和 $b$，输出 $\gcd(a,b)$。（$1\le a,b\le 1000$）
5. 输入 $a$，输出 $a$ 的 $32$ 位二进制表示。（$0\le a\le 10^5$，例如 $5$ 输出 $\verb!0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1!$）
6. 输入 $a$ 和 $b$，输出 $a\times b$。（$0\le a,b\le 1000$）
7. 输入 $a$ 和 $b$，输出 $a\oplus b$。（$0\le a,b\le 10^5$，$\oplus$ 表示异或）
8. 输入 $a$，输出 $a\div 10$ 下取整。（$1\le a\le 10000$）
9. 输入 $a$ 和 $b$，输出 $a\times b \bmod 262144$。（$0\le a,b\le 10^5$）
10. 输入 $a$ 和 $b$，输出 $a$ 的 $b$ 次方。（$1\le a,b\le 1000$，$a$ 的 $b$ 次方不超过 $10^6$）

瓶子国国王会生成 $30$ 组**左右**的数据对你的程序进行测试，并根据你使用的操作个数进行评分，评分规则详见下方提示。

（**UPD**：如果你没有看懂题目这里有一段补充说明）

你**提交到洛谷的程序**（C/C++/Pascal）需要输出一段操作，格式类似样例输出。

例如第一个点，提交后洛谷上的 checker 会随机生成 $a$ 和 $b$ 作为 $\verb!I!$ **操作的输入**来测试你的操作。

对于本地 checker（下载见提示区），你可以把输出的操作保存成 `a.txt`，然后第一行输入 `a.txt`，第二行如果手玩就输 $0$，如果测试指定点就输编号。

inputFormat: 输入共一行一个整数，表示数据点编号。

outputFormat: 输出可以满足计算任务的操作。

samples:
233
// 仅作为参考，这里应该填数据编号

samples:
I
C 1
F 2
C 233333
T 1 3
T 2 3
O 3
（这个程序可以进行x+1！是不是很厉害啊！不过程序中并不能附加任何注释）

hint:
请注意提交的是一段**输出操作的程序**！（如果你生成答案之后把生成它的程序删了直接打表输出，可能会输出超限）

灵感来自 NOI2016 旷野大计算（其实我不说你们肯定也知道啊）

为了方便选手本地测试，下面是一个 C++ 的本地checker（需要注意的是，它的测试结果与洛谷上的测试结果不一定一样，洛谷上可能更严格）：

- http://paste.ubuntu.com/23070332/

如果需要下载 exe 的话可戳度盘：

- http://pan.baidu.com/s/1o7HZ1GY 密码为 `kqhl`。

### 评分规则

如果你的算法输出了错误结果（多输出也算）或者发生运行错误（操作不符合要求等）或者行数超过 $5\times 10^6$ 行或者行数太长了 checker 没能在 $1s$ 内测试完 $30$ 组数据，你将获得 $0$ 分。

否则，假设 std 的步数为 $s$，你的步数为 $x$。

- 如果 $x\le s$，你的基准分为 $10$ 分。
- 如果 $s<x\le s+5$，你的基准分为 $9$ 分。
- 如果 $s+5<x\le 3s$，你的基准分为 $8$ 分。
- 如果 $3s<x\le 10s$，你的基准分为 $7$ 分。
- 如果 $10s<x\le 50s$，你的基准分为 $6$ 分。
- 如果 $x>50s$，你的基准分为 $5$ 分。

如果你使用了昂贵的 $\verb!K!$ 操作，你会得到（基准分 $-4$）分。

否则你会得到基准分。

（说人话：步数越少分越高，用K操作扣4分）

（**UPD2：洛谷上的checker常见错误信息**）

```cpp
too many lines：超过500w行（这个似乎还没有触发过）
WTF：就是操作的第一个字符串（I/T/K/F/E/C/M/O）长度大于1
（可能是由于上一个操作多跟了一个操作数？）
wrong operation：操作的第一个字符串长度为1但不是I/T/K/F/E/C/M/O。
expected *****：希望输入一个数/字符串却没有（可能是操作数多打/少打）
nothing to input：I操作数量大于输入的数数量
F/E/C/M/T/O/K wrong bottle：操作的瓶子编号不在[1,当前最大编号]范围内
C exceed [0,10^9]：字面意思
K exceed 10^9：字面意思
wa on test xxx：你在第xxx组随机数据狗带了
wa on extratest xxx：你在第xxx组人工数据（手打的）狗带了
```


title: [国家集训队] middle

description:
一个长度为 $n$ 的序列 $a$，设其排过序之后为 $b$，其中位数定义为 $b_{n/2}$，其中 $a,b$ 从 $0$ 开始标号，除法下取整。

给你一个长度为 $n$ 的序列 $s$。

回答 $Q$ 个这样的询问：$s$ 的左端点在 $[a,b]$ 之间，右端点在 $[c,d]$ 之间的子区间中，最大的中位数。

其中 $a<b<c<d$。

位置也从 $0$ 开始标号。

我会使用一些方式强制你在线。

inputFormat:
第一行序列长度 $n$。

接下来 $n$ 行按顺序给出 $a$ 中的数。

接下来一行 $Q$。

然后 $Q$ 行每行 $a,b,c,d$，我们令上个询问的答案是 $x$（如果这是第一个询问则 $x=0$）。

令数组 $q=\{(a+x)\bmod n,(b+x)\bmod n,(c+x)\bmod n,(d+x)\bmod n\}$。

将 $q$ 从小到大排序之后，令真正的要询问的 $a=q_0$，$b=q_1$，$c=q_2$，$d=q_3$。

输入保证满足条件。

outputFormat: $Q$ 行依次给出询问的答案。


title: [NOIP2016 提高组] 蚯蚓

background: NOIP2016 提高组 D2T2

description:
本题中，我们将用符号 $\lfloor c \rfloor$ 表示对 $c$ 向下取整，例如：$\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。

蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 $n$ 只蚯蚓（$n$ 为正整数）。每只蚯蚓拥有长度，我们设第 $i$ 只蚯蚓的长度为 $a_i\,(i=1,2,\dots,n)$，并保证所有的长度都是非负整数（即：可能存在长度为 $0$ 的蚯蚓）。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 $p$（是满足 $0 < p < 1$ 的有理数）决定，设这只蚯蚓长度为 $x$，神刀手会将其切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓。特殊地，如果这两个数的其中一个等于 $0$，则这个长度为 $0$ 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 $q$（是一个非负整常数）。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 $m$ 秒才能到来……（$m$ 为非负整数）

蛐蛐国王希望知道这 $m$ 秒内的战况。具体来说，他希望知道：

- $m$ 秒内，每一秒被切断的蚯蚓被切断前的长度（有 $m$ 个数）；
- $m$ 秒后，所有蚯蚓的长度（有 $n + m$ 个数）。

蛐蛐国王当然知道怎么做啦！但是他想考考你……

inputFormat:
第一行包含六个整数 $n,m,q,u,v,t$，其中：$n,m,q$ 的意义见【问题描述】；$u,v,t$ 均为正整数；你需要自己计算 $p=u / v$（保证 $0 < u < v$）；$t$ 是输出参数，其含义将会在【输出格式】中解释。

第二行包含 $n$ 个非负整数，为 $a_1, a_2, \dots, a_n$，即初始时 $n$ 只蚯蚓的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

保证 $1 \leq n \leq 10^5$，$0 \leq m \leq 7 \times 10^6$，$0 < u < v \leq 10^9$，$0 \leq q \leq 200$，$1 \leq t \leq 71$，$0 \leq a_i \leq 10^8$。

outputFormat:
第一行输出 $\left \lfloor \frac{m}{t} \right \rfloor$ 个整数，按时间顺序，依次输出第 $t$ 秒，第 $2t$ 秒，第 $3t$ 秒，……被切断蚯蚓（在被切断前）的长度。

第二行输出 $\left \lfloor \frac{n+m}{t} \right \rfloor$ 个整数，输出 $m$ 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 $t$，第 $2t$，第 $3t$，……的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。

请阅读样例来更好地理解这个格式。

hint:
**样例解释 1**

在神刀手到来前：$3$ 只蚯蚓的长度为 $3,3,2$。

$1$ 秒后：一只长度为 $3$ 的蚯蚓被切成了两只长度分别为$1$ 和 $2$ 的蚯蚓，其余蚯蚓的长度增加了 $1$。最终 $4$ 只蚯蚓的长度分别为 $(1,2),4,3$。括号表示这个位置刚刚有一只蚯蚓被切断。

$2$ 秒后：一只长度为 $4$ 的蚯蚓被切成了 $1$ 和 $3$。$5$ 只蚯蚓的长度分别为：$2,3,(1,3),4$。

$3$ 秒后：一只长度为 $4$ 的蚯蚓被切断。$6$ 只蚯蚓的长度分别为：$3,4,2,4,(1,3)$。

$4$ 秒后：一只长度为 $4$ 的蚯蚓被切断。$7$ 只蚯蚓的长度分别为：$4,(1,3),3,5,2,4$。

$5$ 秒后：一只长度为 $5$ 的蚯蚓被切断。$8$ 只蚯蚓的长度分别为：$5,2,4,4,(1,4),3,5$。

$6$ 秒后：一只长度为 $5$ 的蚯蚓被切断。$9$ 只蚯蚓的长度分别为：$(1,4),3,5,5,2,5,4,6$。

$7$ 秒后：一只长度为 $6$ 的蚯蚓被切断。$10$ 只蚯蚓的长度分别为：$2,5,4,6,6,3,6,5,(2,4)$。所以，$7$ 秒内被切断的蚯蚓的长度依次为 $3,4,4,4,5,5,6$。$7$ 秒后，所有蚯蚓长度从大到小排序为 $6,6,6,5,5,4,4,3,2,2$。

**样例解释 2**

这个数据中只有 $t=2$ 与上个数据不同。只需在每行都改为每两个数输出一个数即可。

虽然第一行最后有一个 $6$ 没有被输出，但是第二行仍然要重新从第二个数再开始输出。

**样例解释 3**

这个数据中只有 $t=9$ 与上个数据不同。

注意第一行没有数要输出，但也要输出一个空行。

**数据范围**

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


title: 刻录光盘

description:
在JSOI2005夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？！

组委会把这个难题交给了LHC，LHC分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！

可是，LHC调查后发现，由于种种原因，有些营员并不是那么的合作，他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们JSOI宣扬的团队合作精神格格不入！！！

现在假设总共有N个营员（2<=N<=200），每个营员的编号为1~N。LHC给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料。

现在，请你编写一个程序，根据回收上来的调查表，帮助LHC计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

inputFormat: 先是一个数N，接下来的N行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号，以一个0结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有1个0，一行中的若干数之间用一个空格隔开。

outputFormat: 一个正整数，表示最少要刻录的光盘数。


title: 行路难【疑似 std 复杂度有误】

background: 小X来到了山区，领略山林之乐。在他乐以忘忧之时，他突然发现，开学迫在眉睫

description:
山区有 $n$ 座山。山之间有 $m$ 条羊肠小道，每条连接两座山，只能单向通过，并会耗费小 X 一定时间。

小 X 现在在 $1$ 号山，他的目的是 $n$ 号山，因为那里有火车站。

然而小 X 的体力是有限的。他每通过一条羊肠小道，就会变得更疲劳，导致他通过任意一条羊肠小道的时间都增加 $1$。

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

第 $2$ 行到第 $m+1$ 行，每行 $3$ 个数 $A, B, C$，表示 $A$ 、 $B$ 之间有一条羊肠小道，可以让小 X 花费 $C$ 的时间从 $A$ 移动到 $B$。

outputFormat:
第一行一个数 $T$，表示小 X 需要的最短时间。

第二行若干个数，用空格隔开，表示小 X 的移动路线。例如，$[1, 4, 2, 5]$ 表示小 $X$ 从 $1$ 号山开始，移动到 $4$ 号山，再到 $2$ 号山，最后到 $5$ 号山。

hint:
### 数据范围及约定

对于全部数据，$n \le 10^4$，$m \le 2\times 10^5$。

数据保证没有多条最短路径。


title: [USACO14DEC] Marathon S

description:
Unhappy with the poor health of his cows, Farmer John enrolls them in an assortment of different physical fitness activities. His prize cow Bessie is enrolled in a running class, where she is eventually expected to run a marathon through the downtown area of the city near Farmer John's farm!

The marathon course consists of N checkpoints (3 <= N <= 500) to be visited in sequence, where checkpoint 1 is the starting location and checkpoint N is the finish. Bessie is supposed to visit all of these checkpoints one by one, but being the lazy cow she is, she decides that she will skip up to K checkpoints (K < N) in order to shorten her total journey. She cannot skip checkpoints 1 or N, however, since that would be too noticeable.

Please help Bessie find the minimum distance that she has to run if she can skip up to K checkpoints.

Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2|.

Bessie 参加城市马拉松比赛，要顺序经过 $N (3 \leq N \leq 500)$ 个检查点，其中检查点 $1$ 是起点，检查点 $N$ 是终点。 Bessie尝试略过 $K(K < N)$ 个检查点，以减少总路程，检查点 $1$ 和检查点 $N$ 不能被略过。两个检查点的距离是 $|x_1-x_2| + |y_1-y_2|$。

输入输出格式

inputFormat:
The first line gives the values of N and K.

The next N lines each contain two space-separated integers, x and y,representing a checkpoint (-1000 <= x <= 1000, -1000 <= y <= 1000).

The checkpoints are given in the order that they must be visited.

Note that the course might cross over itself several times, with several checkpoints occurring at the same physical location. When Bessie skips such a checkpoint, she only skips one instance of the checkpoint -- she does not skip every checkpoint occurring at the same location.

outputFormat: Output the minimum distance that Bessie can run by skipping up to K checkpoints. In the sample case shown here, skipping the checkpoints at (8, 3) and (10, -5) leads to the minimum total distance of 4.

translation:
【题目描述】

由于对他的奶牛的健康状况不佳而感到不满，牧场主约翰让它们参加各种各样的体育健身活动。最让他感到自豪的奶牛是 Bessie，她将参加约翰牧场附近城市里的马拉松比赛！

马拉松比赛有 $N$ 个检查点 $(3\leq N\leq 500)$ ，需要按顺序访问。检查点 $1$ 是起点，检查点 $N$ 是终点。Bessie 应该按顺序一一访问所有的这些检查点，但由于她是一头懒惰的牛（懒惰竟然还选择跑马拉松！），于是她决定跳过 $K(K<N)$ 个检查点以缩小她的赛程。但她不能跳过第 $1$ 个和第 $N$ 个检查点，因为这样太明显了。

请你帮助 Bessie 计算出跳过中间的 $K$ 个检查点后她最少要跑多少距离。

注意：由于街道是网格状的，我们用坐标来表示点的位置。但是 $(x_1,y_1),(x_2,y_2)$ 两点间的距离应为 $|x_1-x_2|+|y_1-y_2|$，这种测量距离的方法被称为“曼哈顿”距离，这是因为在市中心的网格路中，你可以沿平行于 $x$ 轴或 $y$ 轴的方向走，但不能沿直线到达。

【输入格式】

第一行：两个正整数 $N$ 和 $K$。

第 $2$ 行到第 $N+1$ 行，每行两个整数$x,y (-1000\leq x\leq 1000,-1000\leq y\leq 1000)$。

这里给出了检查点的顺序，她必须按顺序访问。注意：可能会有几个检查点出现在同一位置，Bessie 跳过这样的检查点时，相当于只跳过其中的一个检查点。

【输出格式】

输出跳过某一个检查点后 Bessie 可以跑的最短距离。

感谢@彭骐飞 提供的翻译


title: 暗杀

description:
敌方的高级将领都是有很多相同之处的。为了方便找到每名敌将的弱点，我军情报部已经找到了他们的不同点，并将其归纳为 $k$ 种特性。比如 $1$ 号特性就代表一个敌将喜欢打人，$2$ 号特性就代表一个敌将喜欢吃饭，等等。

为了方便存储，我军使用特性值来描述一个敌将的特点。特性值是一个位数为 $k$ 的二进制整数，每一位都可以表示一名敌将的一个特性。$1$ 代表具有此特性，$0$ 代表没有。

我军间谍打听到，不久有 $n$ 个敌方将领会举行一场宴会，而且入场时他们会排成一路纵队入场。如果有连续的 $m$ 个人的每种特性出现的次数之和是一样的，那么我军间谍就很容易暗杀这 $m$ 个人。你需要帮助我军算出，间谍最多可以暗杀多少人？

因为间谍开始攻击后就可能被敌人击毙，所以间谍只能进行一次攻击。

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

第二行 $n$ 个整数，第 $i$ 个数 $a_i$ 表示第 $i$ 个敌将的特性值（以十进制的形式输入）。

outputFormat: 最多可以暗杀多少个敌将。


title: A*B Problem

description: 给出一个数 $A$ ，你需要给出一个最小的数 $B$ ，使得 $A\times B$ 的结果只含有 $0$ 和 $1$ 。

inputFormat: 一个正整数 $A$。

outputFormat: 正整数 $B$ 和 $A\times B$ 的结果，两数之间用一个空格隔开。