title: Charlie的云笔记序列

background:
Charlie 是 oiinhand 的忠实粉丝。他有使用 oih 云笔记记录自己的题解的习惯。只有一点一滴的积累才能留下自己的足迹。

oih 云笔记有什么特点吗？

oih 的站长 soha 表示，目前 oih2 的云笔记功能比较简陋，但是正在开发 oih3 中的新版云笔记功能将是世界上最适合 oier 的储藏笔记的工具。

首先，新版云笔记支持 markdown 功能，并且可以实时预览，插入公式图片都不是问题。实时自动保存，不用担心突然断电啊文档消失，而且不管在哪里都可以看！

其次，可以一键生成题解模板摘要，不用各种复制粘贴了，超省事！

再者，云笔记可以给其他同学分享自己的笔记，共同进步。写完了笔记，还可以一键向洛谷投稿呢！

然而 Charlie 最喜欢的功能是 oih 的题目收藏。现在他收藏了一系列题目，但是觉得不过瘾所以正在玩弄这个功能。

description:
某天，Charlie 将收藏的题目抽象为一个序列。$a=[a_1,a_2,a_3,\cdots,a_{n-1},a_n]$。

设 $a[l:r]$ 表示序列 ${a_i}$ 第 $l$ 个数到第 $r$ 个数之间的子串，其中 $1 \le l \le r \le n$。形式化地，$a[l:r]={a_l,a_{l+1},a_{l+2},\cdots,a_{r-1},a_r}$。比如说，$a=[9,8,0,3,2,1]$，那么 $a[2:5]=[8,0,3,2]$。

Charlie 对序列 $[a_i]$ 定义了一个函数 $F(l,r)$，表示序列 $a[l:r]$ 的本质不同的子序列个数。特别地，一个空序列也被当作一个本质不同的子序列。

序列 $a[l:r]$ 的子序列定义为 $[a_{i_1},a_{i_2},a_{i_3},\cdots,a_{i_{k-1}},a_{i_k}]$，其中 $l \le i_1<i_2<i3<\cdots<i_{k-1}<i_k \le r$。比如说，$a=[9,8,0,3,2,1]$，那么 $[8,3,2]$ 是 $a[2:5]=[8,0,3,2]$ 的一个子序列。

长度为 $n$ 的序列 $a$ 和长度为 $m$ 的序列 $b$ 被称作本质不同的，当且仅当 $n\neq m$，或存在 $i$，使得 $a_i \neq b_i$。反之，则称这 $2$ 个序列是本质相同的。比如说，$[9,8]$ 和 $[9,7]$ 是本质不同的，$[9,8]$ 和 $[9,8,7]$ 也是本质不同的，而 $[9,8]$ 和 $[9,8]$ 是本质相同的。

举个例子，设 $a=[1,9,9,8,0,3,2,1]$，那么 $F(1,3)=6$，因为 $a[1:3]=[1,9,9]$ 有 $6$ 个子序列：$[],[1],[9],[1,9],[9,9],[1,9,9]$。

现在 Charlie 想知道，$\sum _{1\le l\le r\le n} F(l,r)$ 的值是多少。由于这个数可能很大，请输出它对 $998244353$（$7\times 17\times 2^23+1$，一个质数）取模后的结果。

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

第二行包括 $n$ 个整数，表示 $a_1,a_2,a_3,\cdots a_{n-1},a_n$。

outputFormat: 一行，一个整数表示 $\sum _{1\le l\le r\le n} F(l,r)$ 的值对 $998244353$ 取模后的结果。

hint:
- 对于 $10\%$ 的数据，$1\le n \le 10$；
- 对于 $30\%$ 的数据，$1 \le n \le 100$；
- 对于 $50\%$ 的数据，$1\le n \le 1000$，$0 \le a_i \le 10^5$；
- 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$|a_i| \le 10^9$。

oiinhand 3.0 正在开发中。

这将是 oiers 都需要的工具，它不仅集合了全网所有大型 OJ 的资源（题目、题解）而且针对用户还可以将自己在其他 OJ 评测过的代码储存下来，并且有超贴心的云笔记功能，帮助大家最大效率练习。

soha 借此地征求意见，有奖哦！<http://www.wenjuan.com/s/M7fqIv/>


title: [TJOI2017] DNA

type: P

description: 加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列 $S$,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 $S$，任意修改其中不超过 $3$ 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S_0$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S_0$ 上，有多少个连续子串可能是该基因，即有多少个 $S_0$ 的连续子串修改小于等于三个字母能够变成 $S$。

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

每组数据第一行一个长度不超过 $10^5$ 的碱基序列 $S_0$。

每组数据第二行一个长度不超过 $10^5$ 的吃藕基因序列 $S$。

outputFormat: 共 $T$ 行，第 $i$ 行表示第 $i$ 组数据中，在 $S_0$中有多少个与 $S$ 等长的连续子串可能是表现吃藕性状的碱基序列。

hint:
对于 $20\%$ 的数据，$S_0,S$ 的长度不超过 $10^4$。

对于 $100\%$ 的数据，$S_0,S$ 的长度不超过 $10^5$，$0\lt T\leq 10$。

注：DNA 碱基序列只有 ATCG 四种字符。


title: BBCode转换Markdown

background: BBCode和Markdown是两种常用的格式语言。所谓格式语言指，例如在某些网站评论区发表评论时，可以使用其对你的评论进行修饰，使文字可以有颜色、粗体等各种样式。

description:
#### PDF版题目: http://pan.baidu.com/s/1i3mxk4t 提取密码hayc

BBCode的语法如下所示：

```cpp
[h1]Hello World![/h1]
[h2][i]This is a BBCode[/i][/h2]
[b][i]I love[/i] Olympic [i]Informatics[/i][/b]
```

例如，在标签[h1]中，在[h1]和[/h1]之间包裹的内容属于一级标题，对于这之间的文字要按照一级标题的样式渲染。

请注意BBCode要求标签的开闭必须完整且且嵌套无误，也就是说，如下列的例子都是不合法的BBCode：

```cpp
[h1]Hello World! //标签未闭合
[h1]Hello World![/h2] //两个标签不匹配
[h1][i]Hello World![/h1][/i] //嵌套次序错误
```

另外，极其重要的一点是，BBCode有一个特殊的标签[quote][/quote]，在其中的任意文字都不应被解析为BBCode代码，而应该对其进行Markdown化处理后被原样输出。

现在介绍Markdown。其语法如下所示：

```cpp
# Hello World! #
## *This is a Markdown* ##
__*I love* Olympic *Informatics*__
```

你的任务就是将给定的一串BBCode转换成Markdown，并对不合法的输入报错。

题目数据中会出现的所有BBCode的标签与其对应Markdown对应关系如下，保证不出现除此之外的对应：

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

对于[quote]标签的附加说明：

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

inputFormat: 所需转换的BBCode。

samples:
[h1]Hello World![/h1]
[h2]How are [i]you[/i]?[/h2]

samples:
[h1]Introducing Swift.[/h1][quote]
import SpriteKit
let object = SKSpriteNode(imageNamed: “[L2/Ascention]”
[/quote]

samples:
# Introducing Swift. #
> import SpriteKit
> let object = SKSpriteNode(imageNamed: “[L2/Ascention]”

samples:
[h1]I knew you were
trouble when you walked in[/h1]
[url=http://www.example.com]By Taylor Swift[/url]

samples:
# I knew you were
trouble when you walked in #
[By Taylor Swift](http://www.example.com)

samples:
[h1]Thanks for [i]inviting[/h1] me.[/i]
Match Error

samples:
[h2]Your gift is awesome!
Unclosed Mark

samples:
Match Error
(对该数据的解释: 匹配到第一个关闭标签后即不认为后面的内容仍是代码段)

samples:
[quote][quote][/quote]
> [quote]

hint:
为保证评测顺利不被误判，请注意下列要求：

尊重原输入输出的换行，不自行添删。

对于第一条的例外是， 遇到[quote]标签不在新的一行时，Markdown中请另起一行。另外[quote]标签中的代码段头尾空行请去除，不会出现空白的quote。

请注意上表中的空格。

对于不合法的BBCode输入，你的程序必须报错：对于匹配错误的标签输出Match Error，对于未闭合的标签输出Unclosed Mark，请参考样例。两种情况同时出现的时候（即同时有匹配错误和未闭合的标签时），按照匹配错误处理，输出Match Error。由于quote标签的特殊性，为保证不出现歧义，数据保证quote标签不会出现错误。(对于出现如[i][h1]Text[/i]这样的情况，按照Match Error处理，对于[i][h1]Text[/h1]这样的情况，按照Unclosed Mark处理)

由于洛谷限制，请大家在输出Unclosed Mark的时候在close中间切开分为两段字符串输出，否则会被吞记录。

保证以下三种字符不出现在除quote标签包裹的段落中的文字中：[,],/,\*,\_,#,>，但地址中可能会出现/字符。

保证输入不会出现标签不完整的情况，例如[h1]Text[/h

对于曾经在其他地方使用过Markdown与BBCode的同学：题中的格式不是严格的BBCode与Markdown格式，请勿被经验迷惑。


title: 汽车拉力比赛

description:
博艾市将要举行一场汽车拉力比赛。

赛场凹凸不平，所以被描述为 $N*M$ 的网格来表示海拔高度 $(1 \leq M,N \leq 500)$，每个单元格的海拔范围在 $0$ 到 $10^9$ 之间。

其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数 $D$，这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于 $D$ 。也就是说这个难度系数 $D$ 指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。

inputFormat:
第 $1$ 行两个整数 $M$ 和 $N$。第 $2$ 行到第 $M+1$ 行，每行 $N$ 个整数描述海拔高度。第 $2+M$ 行到第 $1+2M$

行，每行 $N$ 个整数，每个数非 $0$ 即 $1$，$1$ 表示该单元格是一个路标。

outputFormat: 一个整数，即赛道的难度系数 $D$。


title: [CTSC2017] 吉夫特

description:
简单的题目，既是礼物，也是毒药。

B 君设计了一道简单的题目，准备作为 gift 送给大家。

输入一个长度为  $n$  的数列  $a_1, a_2, \cdots , a_n$  问有多少个长度大于等于  $2$  的不上升的子序列满足：

 $$\prod _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \binom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 > 0$$

输出这个个数对  $1000000007$  取模的结果。

G 君看到题目后，为大家解释了一些基本概念。

我们选择任意多个整数  $b_i$  满足

 $$1 \leq b_1 < b_2 < \dots < b_{k-1} < b_k \leq n$$

我们称  $a_{b_1}, a_{b_2}, \cdots, a_{b_k} $  是  $a$  的一个子序列。

如果这个子序列同时还满足

 $$a_{b_1} \geq a_{b_2} \geq \cdots \geq a_{b_{k-1}}\geq a_{b_k}$$

我们称这个子序列是不上升的。

组合数  $\binom {n} {m} $  是从  $n$  个互不相同的元素中取  $m$  个元素的方案数，具体计算方案如下：

 $$\binom {n}{m}=\frac{n!}{m!(n-m)!}=\frac{n \times (n-1) \times \cdots \times 2 \times 1}{(m \times (m-1) \cdots \times 2 \times 1)((n-m)\times(n-m-1)\times \cdots \times 2 \times 1)}$$

这里要特别注意，因为我们只考虑不上升子序列，所以在求组合数的过程中，一定满足  $n \geq m$ ，也就是 $\binom {a_{b_{i-1}}}{a_{b_i}}$ 中一定有 $a_{b_{i-1}} \geq a_{b_i}$ 。

我们在这里强调取模  $x \mod y$  的定义：

 $x \bmod y = x -\left \lfloor \frac{x}{y} \right \rfloor \times y$

其中  $\left \lfloor n \right \rfloor$  表示小于等于  $n$  的最大整数。

 $x \bmod 2 > 0$  ，就是在说  $x$  是奇数。

与此同时，经验告诉我们一个长度为  $n$  的序列，子序列个数有  $O(2^n)$  个，所以我们通过对答案取模来避免输出过大。

B 君觉得 G 君说的十分有道理，于是再次强调了这些基本概念。

最后， G 君听说这个题是作为 gift 送给大家，她有一句忠告。

“Vorsicht, Gift!”

“小心. . . . . .剧毒！ ”

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

接下来 $n$ 行，每行一个整数，这 $n$ 行中的第 $i$ 行，表示 $a_i$。

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

hint:
对于前 $10\%$ 的测试点，$n \leq 9$，$1\leq a_i\leq 13$。

对于前 $20\%$ 的测试点，$n\leq 17$，$1\leq a_i\leq 20$。

对于前 $40\%$ 的测试点，$n\leq 1911$，$1\leq a_i\leq 4000$。

对于前 $70\%$ 的测试点，$n\leq 2017$。

对于前 $85\%$ 的测试点，$n\leq 100084$。

对于 $100\%$ 的测试点，$1\leq n\leq 211985$，$1\leq a_i\leq 233333$。所有的 $a_i$ 互不相同，也就是说不存在 $i, j$ 同时满足 $1\leq i < j\leq n$ 和 $a_i = a_j$。


title: [CTSC2017] 最长上升子序列

description:
猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列 $A =(a_1, a_2,\ldots , a_k)$，定义 $A$ 的子序列为：从 $A$ 中删除若干个元素后（允许不删，也允许将所有 $k$ 个元素都删除），剩下的元素按照原来的顺序所组成的序列。如果这个子序列的元素从左到右严格递增，则称它为 $A$ 的一个上升子序列。其中包含元素数量最多的上升子序列称为 $A$ 的最长上升子序列。例如，$(2, 4, 5, 6)$ 和 $(1, 4, 5, 6)$ 都是 $(2, 1, 1, 4, 7, 5, 6)$ 的最长上升子序列，长度都为 $4$。

现在猪小侠遇到了这样一个问题：给定一个序列 $B_m = (b_1, b_2, \ldots, b_m)$，设 $C$ 是 $B_m$ 的子序列，且 $C$ 的最长上升子序列的长度不超过 $k$，则 $C$ 的长度最大能是多少？

猪小侠觉得这个问题太简单了，缺乏挑战，他决定提出一个更难的问题。于是他给了你这样一个序列 $B = (b_1, b_2,\ldots , b_n)$，以及若干次询问。每次询问会给定两个整数 $m$ 和 $k$，你需要对于 $B$ 序列的前 $m$ 个元素构成的序列 $B_m = (b_1, b_2, \ldots, b_m)$ 和 $k$ 回答上述问题。

inputFormat:
第一行两个整数 $n, q$，其中 $n$ 是序列 $B$ 的长度，$q$ 是询问次数。

第二行是空格隔开的 $n$ 个正整数 $b_1, b_2, \ldots, b_n$。

接下来 $q$ 行，其中第 $i$ 行包含两个整数 $m_i, k_i$，表示对 $m = m_i, k = k_i$ 进行询问。

outputFormat: 输出共 $q$ 行，按顺序每行一个整数作为回答。


title: yyy loves Maths VI (mode)

background:
自动上次 redbag 用加法好好的刁难过了 yyy 同学以后，yyy 十分愤怒。
他还击给了 redbag 一题，但是这题他惊讶的发现自己居然也不会，所以只好找你

description: 一共有 $n$ 个正整数 $a_i$，他让 redbag 找众数。他还特意表示，这个众数出现次数超过了一半。

inputFormat:
第一行一个整数 $n$，表示数的个数。
第二行 $n$ 个正整数 $a_i$。

outputFormat: 一行一个整数，表示众数。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 2\times 10^6$，$a_i \in [1,2^{31})$。

有人想水过,但我告诉你这空间是不够的。

//kkksc03偷偷地说：你随便输出一个数字吧，都有1/2的几率。不过这可是乐多赛，值得不值得你看着办。所以最好想一想正解。


title: yyy loves Maths VII

background: yyy 对某些数字有着情有独钟的喜爱，他叫他们为“幸运数字”；然而他作死太多，所以把自己讨厌的数字成为“厄运数字”。

description:
一群同学在和 yyy 玩一个游戏。

每次,他们会给 yyy $n$ 张卡片，卡片上有数字，所有的数字都是“幸运数字”，我们认为第 $i$ 张卡片上数字是 $a_{i}$。

每次 yyy 可以选择向前走 $a_{i}$ 步并且丢掉第 $i$ 张卡片。当他手上没有卡片的时候他就赢了。

但是呢，大家对“厄运数字”的位置布置下了陷阱，如果 yyy 停在这个格子上，那么他就输了。注意：**即使到了终点，但是这个位置是厄运数字，那么也输了。**

现在，有些同学开始问：yyy 有多大的概率会赢呢？

大家觉得这是个好问题，有人立即让 yyy 写个程序：“电脑运行速度很快！$24$ 的阶乘也不过就 $620\,448\,401\,733\,239\,439\,360\,000$，yyy 你快写个程序来算一算。”

yyy 表示很无语，他表示他不想算概率，最多算算赢的方案数，而且是对 $10^9+7$ 取模后的值。

大家都不会写程序，只好妥协。

但是这时候 yyy 为难了，$24!$ 太大了，要跑好长时间。

他时间严重不够！需要你的帮助！

某个数字可能既属于幸运数字又属于厄运数字。

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

下面一行 $n$ 个整数，第 $i$ 个整数代表第 $i$ 张卡片上的数字 $a_i$。

第三行 $m$ 表示 yyy 的厄运数字个数（最多 $2$ 个）。

若 $m>0$，第四行 $m$ 个数 $b_i$ 代表所有的厄运数字。

outputFormat: 输出胜利方案数对 $10^9+7$ 取模的结果。


title: GCD SUM

description:
求

$$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$

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

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


title: non hates math

background:
non习惯将分数化成小数，但在数学中要以分数形式写，不能化成小数

因此non找到了会编程的你，帮助他将小数化回分数

description:
给出一个小数，将它化成假分数的形式

小数的类型有2种：（不考虑无限不循环小数）

普通小数

循环小数（会给出循环节）

（循环节用( )表示）

inputFormat: 一个小数n

outputFormat: 输出这个小数n转化成最简分数的形式

hint:
输入小数的数据范围

0至1000

对于50%的数据保证没有循环节

对于20%的数据需要读入优化


title: 债务清单

description: HZGD 刚刚带领着他的 $N$ 个学生参加完第 LXX 届 NOI。但他的学生发现他们本应该报销的费用还一直拖欠着，于是纷纷找 HZGD 要他给他们报销。不过麻烦的是，学生们总是成双成对的找他，并且只报告他们的债务总和，有的人可能来报告好几次。这让 HZGD 非常难办，他不知道是不是有些人会谎报债务，于是他希望能够列出一张债务清单。

inputFormat: 输入文件第一行包括两个正整数 $N$ 和 $M$，分别表示学生人数和向 HZGD 来报告的总次数，接下来 $M$ 行每行三个整数，分别为来报告的两个学生以及他们报告的债务总和。

outputFormat: 输出文件为一张 $N$ 行的债务清单，第 $i$ 行对应第 $i$ 个学生的债务数额，所有数额保留两位小数。如果无法列出这样一张清单，则输出 `IMPOSSIBLE`。对于有解的数据保证有唯一解。


title: 让我们异或吧

description:
异或是一种神奇的运算,大部分人把它总结成不进位加法.

在生活中 xor 运算也很常见。比如，对于一个问题的回答，是为 $1$，否为 $0$，那么：

（$A$ 是否是男生）xor（$B$ 是否是男生）＝ $A$ 和 $B$ 是否能够成为情侣

好了，现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树，它很高兴自己有 $N$ 个结点。树的每条边上有一个权值。我们要进行 $M$ 次询问，对于每次询问，我们想知道某两点之间的路径上所有边权的异或值。

inputFormat: 输入文件第一行包含一个整数 $N$ ，表示这颗开心的树拥有的结点数，以下有 $N-1$ 行，描述这些边，每行有3个数，$u,v,w$，表示 $u$ 和 $v$ 之间有一条权值为 $w$ 的边。接下来一行有一个整数 $M$，表示询问数。之后的 $M$ 行，每行两个数 $u,v$，表示询问这两个点之间的路径上的权值异或值。

outputFormat: 输出 $M$ 行，每行一个整数，表示异或值

hint:
对于 $40\%$ 的数据，有 $1 \le N,M \le 3000$；
对于 $100\%$ 的数据，有 $1 \le N ,M\le 100000$。

保证边权在 `int` 范围内。


title: Dynamic Rankings

description:
给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$，需要支持两种操作：

- `Q l r k` 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
- `C x y` 表示将 $a_x$ 改为 $y$

inputFormat:
第一行两个正整数 $n,m$，表示序列长度与操作个数。
第二行 $n$ 个整数，表示 $a_1,a_2 \dots a_n$。
接下来 $m$ 行，每行表示一个操作，都为上述两种中的一个。

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

hint:
【数据范围】

对于 $10\%$ 的数据，$1\le n,m \le 100$；
对于 $20\%$ 的数据，$1\le n,m \le 1000$；
对于 $50\%$ 的数据，$1\le n,m \le 10^4$；
对于 $100\%$ 的数据，$1\le n,m \le 10^5$，$1 \le l \le r \le n$，$1 \le k \le r-l+1$，$1\le x \le n$，$0 \le a_i,y \le 10^9$。

请注意常数优化，但写法正常的整体二分和树套树都可以以大约 $1000\text{ms}$ 每个点的时间通过。

来源：bzoj1901

本题数据为洛谷自造数据，使用[CYaRon](https://github.com/luogu-dev/cyaron)耗时5分钟完成数据制作。


title: 小红帽的回文数

description: 小红帽喜欢回文数，但生活中的数常常不是回文数。现在她手上有 $t$ 个数，现在她知道这 $t$ 个数分别在 $x$ 进制下是回文数（$x \ge 2$），请你对于每个数求出最小的 $x$。

inputFormat:
第一行为一个 $t$（$1 \le t \le 1000$）。

接下来的 $t$ 行，每行为一个数 $a_i$（$0 \le a_i \le 10 ^ {10}$）。

outputFormat: 输出有 $t$ 行，每行为所求的 $x$。


title: 不等数列

description:
将 $1$ 到 $n$ 任意排列，然后在排列的每两个数之间根据他们的大小关系插入`>` 和 `<`。问在所有排列中，有多少个排列恰好有 $k$ 个 `<`。答案对 $2015$ 取模。

注：$1 \sim n$ 的排列指的是 $1 \sim n$ 这 $n$ 个数各出现且仅出现一次的数列。

inputFormat: 一行两个整数，表示 $n$ 和 $k$。

outputFormat: 一个整数表示答案。


title: 秘密文件

description:
某天，情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的xx大陆上的老朋友小刘来解密。然而若字符串太长，则需要很长的发送时间，太不安全了，因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则：若一个字符串t连续出现k次，则可以用k(t)进行说明。如ABABAB可以缩成3(AB)。当然，重复缩短是允许的，如ABABABAAAAAAABABABAAAAAA可以缩成2(3(AB)6(A))

现在，小明想知道，对于给定的字符串，最短可以缩成什么样子。

**注意：有多个最优方案时，输出其中字典序最大的。( thanks to @Dilute. )**

inputFormat: 输入仅一行，为给定的字符串。

outputFormat: 输出仅一行，为经过缩短操作后的字符串。

hint:
【数据范围】

对于l00%的数据，字符串的长度L≤100。数据存在一定梯度。


title: Wave

description: 波在不同的介质中的传播速度是不一样的。真空中波速都是 $3\times {10}^8$ m/s，而在液体介质中的波速会比真空中的波速小，并且在不同的液体介质中波速不一样。我们将一个液体表面分成 $N \times M$ 块相同大小的正方形格子，每个格子中只包含一种液体介质。现在我们想知道，从某个波源传出去的波能以不变的波速延伸到多大的以波源为中心的大正方形内。假定所有大正方形的边都是平行于坐标轴的。

inputFormat: 输入文件第一行包含三个整数 $N, M, Q$，分别表示液体表面分成的正方形格子的行数和列数，以及询问的个数。接下来是一个 $N \times M$ 的矩阵，其中每个元素包含一个小写字母表示相应各自内的介质，不同的字母表示不同的介质。接下来 $Q$ 行每行用两个数 $X$ 和 $Y$ 描述一个询问，表示询问以第 $X$ 行第 $Y$ 列为波源的波能以不变的波速延伸到的最大的以波源为中心的大正方形的边长。注意行的标号从 $0$ 到 $N-1$，列的标号从 $0$ 到 $M-1$。

outputFormat: 输出文件包括 $Q$ 行，每行包含一个整数，即相应问题的答案。

samples:
5 5 3
abbaa
abbaa
aaaaa
aaaaa
aaaaa
1 2
1 4
3 2


title: [NOI2002] 荒岛野人

description:
克里特岛以野人群居而著称。岛上有排列成环行的 $m$ 个山洞。这些山洞顺时针编号为 $1,2,\dots ,m$ 。岛上住着 $n$ 个野人，一开始依次住在山洞 $C_1,C_2,\dots ,C_n$中，以后每年，第 $i$ 个野人会沿顺时针向前走 $P_i$ 个洞住下来。

每个野人 $i$ 有一个寿命值 $L_i$，即生存的年数。

下面四幅图描述了一个有 $6$ 个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 $1,2,3$；每年要走过的洞穴数依次为 $3,7,2$；寿命值依次为 $4,3,1$。

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

奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？

inputFormat:
第 $1$ 行为一个整数 $n(1\leq n\leq 15)$，即野人的数目。

第 $2$ 行到第 $N+1$ 每行为三个整数 $C_i, P_i, L_i (1\leq C_i,P_i \leq 100, 0\leq L_i\leq 10^6 )$，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

outputFormat: 仅包含一个数 $M$，即最少可能的山洞数。输入数据保证有解，且 $M$ 不大于 $10^6$。


title: 奶牛隐藏

background: 这本是一个非常简单的问题，然而奶牛们由于下雨已经非常混乱，无法完成这一计算，于是这个任务就交给了你。(奶牛混乱的原因看题目描述)

description:
在一个农场里有 $n$ 块田地。某天下午，有一群牛在田地里吃草，他们分散在农场的诸多田地上，农场由 $m$ 条无向的路连接，每条路有不同的长度。

突然，天降大雨，奶牛们非常混乱，想要快点去躲雨。已知每个田地都建立有一个牛棚，但是每个牛棚只能容纳一定数量的牛躲雨，如果超过这个数量，那多出的牛只能去别的田地躲雨。奶牛们每移动 $1$ 的距离花费 $1$ 时间，奶牛们想知道它们全部都躲进牛棚，最少需要多少时间。(即最后一头奶牛最少要花多久才能躲进牛棚)。

inputFormat:
第一行有两个整数，分别代表田地数 $n$ 和道路数 $m$。

接下来 $n$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $s_i, p_i$ 分别表示第 $i$ 块田地的牛的数量以及该田地的牛棚最多可以容纳多少牛。

接下来 $m$ 行，每行三个整数 $u, v, w$，代表存在一条长度为 $w$ 的连接 $u$ 和 $v$ 的道路。

outputFormat: 输出一行一个整数表示所有奶牛全都躲进牛棚所用的最少时间。如果无法使全部奶牛都躲进牛棚，输出 $-1$。

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

$1$ 号点的两只牛直接躲进 $1$ 号牛棚，剩下的 $5$ 只中，$4$ 只跑去 $2$ 号点，还有一只沿 $1 \to 2 \to 3$ 躲进 $3$ 号点, $3$ 号点的 $2$ 只牛也直接躲进去，这样最慢的牛花费的时间是 $110$。

#### 数据规模与约定

对于 $100\%$ 的数据，保证：
- $1 \leq n \leq 200$，$1 \leq m \leq 1500$。
- $1 \leq u, v \leq n$，$1 \leq w \leq 10^{15}$，$1 \leq s_i, p_i \leq 10^{16}$。


title: 自然数的拆分问题

description: 任何一个大于 $1$ 的自然数 $n$，总可以拆分成若干个小于 $n$ 的自然数之和。现在给你一个自然数 $n$，要求你求出 $n$ 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

inputFormat: 输入：待拆分的自然数 $n$。

outputFormat: 输出：若干数的加法式子。

hint: 数据保证，$2\leq n\le 8$。


title: non天平

background: non 最近正在为自己的体重而苦恼，他想称量自己的体重。于是，他找来一个天平与许多砝码。

description: 砝码的重量均是 $n$ 的幂次，$n^1, n^2, n^3, n^4, n^5$ 的……non 想知道至少要多少个砝码才可以称出他的重量 $m$。注意砝码可以放左边，也可以放右边。

inputFormat:
第一行一个正整数 $m$，表示 non 的重量；

第二行一个正整数 $n$，表示砝码重量幂次的底。

outputFormat: 一个整数表示最少所需的砝码数。


title: [USACO5.3] 巨大的牛棚Big Barn

background: （USACO 5.3.4）

description:
FJ 有一个大小为 $n\times n$ 的农场（$1\le n\le 1000$），他想要在他的农场上建造一座正方形大牛棚。他的农场中有 $t$ 棵果树（$1\le t\le10000$），但他为了不破坏果树，就想找一个空旷无树的地方修建牛棚。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚的边长。当然，牛棚的边必须和水平轴和垂直轴平行。

考虑下面的农场，`.` 表示没有树的方格，`#` 表示有树的方格。
```plain
0 1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
```
最大的牛棚是边长为 $5$ 的，可以建造在农场右下角的两个位置其中一个。

inputFormat:
第 $1$ 行输入两个正整数 $n$ 和 $t$。

第 $2\cdots t+1$ 行输入两个正整数 $x,y\ (1\le x,y\le n)$。

outputFormat: 只由一行组成，约翰的牛棚的最大边长。

hint:
题目翻译来自NOCOW。

USACO Training Section 5.3


title: 最小和

background: RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。所以今天只有短的RSA钥匙才可能被强力方式解破。

description:
已知 $a$，$b$ 是正整数且 $a \leq b$。

求满足条件且 $x+y$ 的值最小的 $x$，$y$。

条件：

- $\gcd(x,y) = a$
- $\mathrm{lcm}(x,y) = b$
- $x \leq y$

inputFormat:
多组数据，EOF 判断结束

共有不超过 $10^3$ 行，每行两个数 $a$，$b$。

outputFormat: 输出和输入文件一样多的行，每行一个半角空格隔开的两个数 $x$，$y$。

hint:
$3 \leq a, b < 2^{63}$。

EOF 结束，没有代表行数的 $n$，第一行就是数据。

数据随机生成。


title: 不同子串个数

background: 因为 NOI 被虐傻了，蒟蒻的 YJQ 准备来学习一下字符串，于是它碰到了这样一道题：

description:
给你一个长为 $n$ 的字符串，求不同的子串的个数。

我们定义两个子串不同，当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。

子串的定义：原字符串中连续的一段字符组成的字符串。

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

接下来一行 $n$ 个字符表示给出的字符串。

outputFormat: 一行一个整数，表示不一样的子串个数。

hint:
### 提示

请使用64位整数来进行输出。

### 数据规模与约定
- 对于 $30\%$ 的数据，保证 $n\le 1000$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \le 10^5$，字符串中只有小写英文字母。


title: 集合求和

description: 给定一个集合 $s$（集合元素数量 $\le 30$），求出此集合所有子集元素之和。

inputFormat: 集合中的元素（元素 $\le 1000$）

outputFormat: $s$ 所有子集元素之和。


title: yyy loves OI IV

background: 某校 2015 届有两位 OI 神牛，yyy 和 c01。

description:
全校除他们以外的 $N$ 名学生，每人都会膜拜他们中的某一个人。现在老师要给他们分宿舍了。但是，问题来了：

同一间宿舍里的人要么膜拜同一位大牛，要么膜拜 yyy 和 c01 的人数的差的绝对值不超过 $M$。否则他们就会打起来。

为了方便，老师让 $N$ 名学生站成一排，只有连续地站在一起的人才能分进同一个宿舍。

假设每间宿舍能容纳任意多的人，请问最少要安排几个宿舍？

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

第 $2, 3, \cdots, N+1$ 行，每行一个整数，是 $1$ 或 $2$，第 $i$ 行的数字表示从左往右数第 $i-1$ 个人膜拜的大牛，$1$ 表示 yyy，$2$ 表示 c01。

outputFormat: 一行，一个整数，表示最少要安排几个宿舍。


title: yyy loves physics IV

background:
“颤抖吧，实验室！”

yyy再一次来到了那个惨遭蹂躏的实验室。

description:
这次，在 Round1 里几乎壮烈牺牲的电路君又被翻了出来。一共有 $N$（$1 \le N \le 26$）个元件。

物理学霸 yyy 用一堆导线将他们连了起来，串联，并联，各种联……

但由于 yyy 的操作太不规范，导致每个元件都有损坏的风险，yyy 用他那天才的脑子算出元件 $i$ 损坏而断开的概率是 $p_i$（$0 \le p_i \le 1$），因为电路太复杂，yyy 请你帮忙算出电路断路的概率。

电路连接方式：

- 一个元件是最小的电路，用 $A$ 表示元件 $1$，$B$ 表示元件 $2$，以此类推。

- $K$ 个电路组成的串联电路表示为电路 $1,2,\dots,K$。

- $K$ 个电路组成的并联电路表示为（电路 $1$）（电路 $2$）......（电路 $K$）。

inputFormat:
第 $1$ 行是一个整数 $n$，表示一共有多少个元件；

第 $2$ 行是表示电路的字符串；

最后是 $n$ 行，每行是一个实数 $p_i$，表示元件 $i$ 断路的概率。

outputFormat: 一个实数，表示整个电路断路的概率，精确到小数点后 $4$ 位。


title: [NOI2011] 阿狸的打字机

description:
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 $28$ 个按键，分别印有 $26$ 个小写英文字母和 `B`、`P` 两个字母。经阿狸研究发现，这个打字机是这样工作的：

* 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
* 按一下印有 `B` 的按键，打字机凹槽中最后一个字母会消失。
* 按一下印有 `P` 的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入 `aPaPBbP`，纸上被打印的字符如下：

```
a
aa
ab
```

我们把纸上打印出来的字符串从 $1$ 开始顺序编号，一直到 $n$。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 $(x,y)$（其中 $1\leq x,y\leq n$），打字机会显示第 $x$ 个打印的字符串在第 $y$ 个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

inputFormat:
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数 $m$，表示询问个数。

接下来 $m$ 行描述所有由小键盘输入的询问。其中第 $i$ 行包含两个整数 $x, y$，表示第 $i$ 个询问为 $(x, y)$。

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


title: [USACO07FEB] Silver Lilypad Pond S

description:
为了让奶牛们娱乐和锻炼，Famer John 建造了一个美丽的池塘。这个长方形的池子被分成了 $M \times N$ 个方格（$1 \le M,N \le 30$）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。

Bessie 正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。

Bessie 的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，Bessie 会有八个移动方向可供选择。

约翰一直在观看 Bessie 的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。

于是他想要添加几朵莲花来帮助 Bessie 完成任务。一贯节俭的 John 只想添加最少数量的莲花，当然，莲花不能放在石头上。

请帮助 John确定必须要添加的莲花的最少数量。在添加莲花最少的基础上，确定 Bessie 从起点跳到目标需要的最少步数。最后，确定满足添加的莲花数量最少时，步数最少的路径条数。

inputFormat:
第一行，输入两个用空格分开的整数：$M$ 和 $N$。

第二行到 $M + 1$ 行：第 $i + 1$ 行有 $N$ 个用空格分开的整数，描述了池塘第 $i$ 行的状态：`0` 为水，`1` 为莲花，`2` 为岩石，`3` 为 Bessie 所在的起点，`4` 为 Bessie 想去的终点。

outputFormat:
第一行，一个整数，表示需要添加的莲花的最少数目；如果无解，则输出 $-1$。

第二行，一个整数，表示在添加莲花最少的基础上，贝西从起点跳到终点需要的最少步数；如果第一行是 $-1$，不输出这行。

第三行，一个整数，表示在添加莲花最少的基础上，步数等于第二行输出的路径条数；如果第一行是 $-1$，不输出这行。


title: [USACO08JAN] Cow Contest S

description:
$ N (1 ≤ N ≤ 100) $ cows, conveniently numbered $ 1 ~ N $ , are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow $ A $ has a greater skill level than cow $ B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) $, then cow $ A $ will always beat cow $ B $ .

Farmer John is trying to rank the cows by skill level. Given a list the results of $ M (1 ≤ M ≤ 4,500) $ two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

FJ的 $N$（$1 \leq N \leq 100$）头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按 $1, 2, \cdots, N$ 依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为 $A$ 的奶牛的编程能力强于编号为 $B$ 的奶牛 （$1 \leq A, B \leq N$，$A \neq B$)，那么她们的对决中，编号为 $A$ 的奶牛总是能胜出。 FJ 想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 $M$（$1 \leq M \leq 4,500$）轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

inputFormat:
第一行两个用空格隔开的整数 $N, M$。

第 $2\sim M + 1$ 行，每行为两个用空格隔开的整数 $A, B$ ，描述了参加某一轮比赛的奶牛的编号，以及结果（每行的第一个数的奶牛为**胜者**）。

outputFormat: 输出一行一个整数，表示排名可以确定的奶牛的数目。

hint:
样例解释：

编号为 $2$ 的奶牛输给了编号为 $1, 3, 4$ 的奶牛，也就是说她的水平比这 $3$ 头奶牛都差。而编号为 $5$ 的奶牛又输在了她的手下，也就是说，她的水平比编号为 $5$ 的奶牛强一些。于是，编号为 $2$ 的奶牛的排名必然为第 $4$，编号为 $5$ 的奶牛的水平必然最差。其他 $3$ 头奶牛的排名仍无法确定。


title: 课程

description:
有 $n$ 个人与 $m$ 个教室。其中，可以在第 $i$ 个教室上课的学生有 $k_i$ 个，编号分别为 $p_{i,j}$。每个学生都有至少一个教室**可以**上课，并且每个学生**只能**在一个教室上课。

现在询问是否存在一种方案，使得每个教室里至少有一名学生。若可以满足要求，输出 `YES`，否则输出 `NO`。

inputFormat:
第一行是数据组数 $T$，满足 $T\leq 10$。

对于每一组数据，第一行是两个整数 $m,n$（注意输入顺序）。接下来 $m$ 行，第一个数是 $k_i$，后面 $k_i$ 个数 $p_{i,j}$ 表示第 $p_{i,j}$ 名学生可以在第 $i$ 个教室上课。

outputFormat: 每行一个字符串 `YES` 或 `NO`，表示是否存在一种方案满足对应的测试数据。

hint: $n\leq 2\times 10^4,m\leq 2\times 10^4,T\leq 10$。


title: [NOI2003] 木棒游戏

background: 这是一个很古老的游戏。用木棒在桌上拼出一个不成立的等式，移动且只移动一根木棒使得等式成立。现在轮到你了。

description: 你只能移动用来构成数字的木棒，不能移动构成运算符（+、-、=）的木棒，所以加号、减号、等号是不会改变的。移动前后，木棒构成的数字必须严格与图2中的0~9相符。如果移动一根木棒可以使等式成立，则输出新的等式，否则输出No。

inputFormat: 输入数据要符合逻辑。字符串的长度小于等于1000。

outputFormat:
如果有解，则输出正确的等式，格式与输入的格式相同（以“#”结尾，中间不能有分隔符，也不要加入多余字符）。此时输入数据保证解是唯一的。

如果无解，则输出“No”（N大写，o小写）。


title: [APIO2011] 方格染色

description:
Sam 和他的妹妹 Sara 有一个包含 $n \times m$ 个方格的表格。他们想要将其中的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个 $2 \times 2$ 的方形区域都包含奇数个（ $1$ 个或 $3$ 个）红色方格。例如，下面是一个合法的表格染色方案（`R` 代表红色，`B` 代表蓝色）：
```
B B R B R
R B B B B
R R B R B
```
可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在 Sam 和 Sara 非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格依然满足他们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？

inputFormat:
输入的第一行包含三个整数 $n,m,k$，分别代表表格的行数，列数和已被染色的方格数目。

之后的 $k$ 行描述已被染色的方格。其中第i行包含三个整数 $x_i,y_i,c_i$，分表代表第 $i$ 个已被染色的方格的行编号、列编号和颜色。$c_i$ 为 $1$ 表示方格被染成红色，$c_i$ 为 $0$ 表示方格被染成蓝色。

outputFormat: 输出一个整数，表示可能的染色方案数 $w$ 对于 $10^9$ 取模后得到的值。

hint:
对于 $20\%$ 的测试数据，$n,m,k \leqslant 5$。

对于 $50\%$ 的测试数据，$n,m \leqslant 5000$，$k \leqslant 25$。

对于 $100\%$ 的测试数据，$2 \leqslant n,m \leqslant 10^5$，$0 \leqslant k \leqslant 10^5$，$1 \leqslant x_i \leqslant n$，$1 \leqslant y_i \leqslant m$，$\forall c_i \in \{0,1\}$。


title: [APIO2011] 寻路

description:
TooDee 是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的 Dee。Dee 是像蜜蜂一样的小动物，它们只在二维活动，而且他们非常的 文明开化。TooDee 的蜂窝和正常世界的蜂窝也是很不一样的，他们是矩形的且它们的边平行于 TooDee 的地理坐标系，就是说矩形的边或者是东西走向， 或者是南北走向。

因为 Dees 是很高级的生物，他们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，线段只会在经纬度都是整数的点相交。Dee 在 TooDee 飞行时必须遵守以下规则（请记住 TooDee 中所有点的经纬度都是整数）：

1. 如果当前在点 $(X, Y)$，则下一步只能飞到四个邻点 $(X, Y - 1), (X, Y + 1), (X - 1, Y), (X + 1, Y)$；

2. 不可以进入蜂巢；

3. 只能在蜂巢的角上或者边上改变飞行方向；

4. 开始的时候可以向任何方向飞；

今晚是公共财政大臣 Deeficer 的女儿的生日，她想尽早回家，请帮她找到最快的回家路径。假设她每秒可以飞行一个单位的距离。

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

输入的第一行包含一个整数 $T$，表示测试数据的组数。接下来依次描述这 $T$ 组数据，相邻的两组之间使用一个空行分隔，测试数据不多于 $20$ 组。

对 于每组数据，第一行包含四个整数 $x_s,y_s,x_t,y_t$，表示 Deeficer 的办公室和家的坐标分别是 $(x_s, y_s)$ 和 $(x_t, y_t)$。第二行包含一个整数 $n$，表示蜂巢的个数。接下来的 $n$ 行描述所有的蜂巢，其中第 $i$ 行包含四个整数 $x_{i_1}, y_{i_1}, x_{i_2}, y_{i_2}$，表示第 $i$ 个蜂巢两个对角的坐标分别为 $(x_{i_1}, y_{i_1})$ 和 $(x_{i_2}, y_{i_2})$。

任何两个蜂巢不会相交，也不会接触（在角上也不会接触）。办公室和家处在不同的位置。每个蜂巢的面积为正。

outputFormat: 对于每一组数据，输出一个整数，表示 Deeficer 最快回家的时间（单位为秒），如果她无法按规则回家，则输出 `No Path`。

hint:
对于 $20\%$ 的测试数据，$n\leq 10$，所有的坐标都是小于 $100$ 的非负整数；

对于 $60\%$ 的测试数据，$n\leq 100$，所有坐标的绝对值都小于 $10^3$；

对于 $100\%$ 的测试数据，$0\leq n\leq 10^3$，所有坐标的绝对值都是不超过 $10^9$ 的整数。


title: 木材加工

background: 要保护环境

description:
木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度**均**为 $l$ 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。

木头长度的单位是 $\text{cm}$，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 $11$ 和 $21$，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$。

inputFormat:
第一行是两个正整数 $n,k$，分别表示原木的数量，需要得到的小段的数量。

接下来 $n$ 行，每行一个正整数 $L_i$，表示一根原木的长度。

outputFormat:
仅一行，即 $l$ 的最大值。

如果连 $\text{1cm}$ 长的小段都切不出来，输出 `0`。


title: [APIO2011] 猜单词

description:
“猜单词”是一个双人游戏，在伊朗的青年学生中广为流行。假设有两个游戏者A和B，A作为先手，首先在一个双方都知道的语料库中选出一个单词，并记在脑海中。随后，他在一张小纸片上划下与单词字母数相等的小横线（不妨设为n条）。

接下来，B尝试猜出这个单词。每一轮，B选择一个字母并告诉A。A按如下规则回应：

一、若B所说的字母在单词中出现，A就把它写在对应的横线上。如果整个单词已经完整（所有的字母都已经被猜出），B获胜。

二、否则，如果字母没有在单词中出现，A就把它写在最左侧的下方仍为空白的横线下。如果所有横线下的空白处都已经有字母（也就是说，在这一轮前B已经猜了n个错误字母），那么B就输了，A获胜。

例如，A从语料库中选出了单词RED，且B已经依次猜了字母A，E，C，D，B和R。每一步的结果都在下图中展现，最终B获胜。但如果B在最后一步猜了S而不是R，他就输了。

```cpp

- - - （第一步，B选A）
A

  E
- - - （第二步，B选E）
A

  E
- - - （第三步，B选C）
A C

  E D
- - - （第四步，B选D）
A C

  E D
- - - （第五步，B选B）
A C B

R E D
- - - （第六步，B选R）
A C B
```
Aidin 是猜单词游戏迷。他相信，如果给定的语料库足够大，且其中的单词相对好，那么玩家A（先手）可以采取一种不公平的行动——修改选择的单词。也就是说，既然 玩家A只将单词记在脑海中而不写下来，那他能够在游戏过程中随时变化这个单词，只要使得和当前已经给出的结果依然一致即可。例如，在上面的游戏中，如果单 词RED，BED，LED和TED都在语料库中，那么在第4步之后，A就可以确信他将胜利。他将总是把B给出的字母写在横线下（也就是认定其为错误的字 母），那么每一次他将至多在集合{RED，BED，LED，TED}中失去一个备选单词，最终他将向B宣布：“这个单词是，嗯……”，然后再他的集合中说 出一个剩下的单词。

Aidin想，如果语料库足够好，那么A甚至可能在游戏一开始就确定获胜。例如，如果选择的单词长度为2，而集合{ME，MD，DE，ED，AS，IS，AI，SI}中的单词都在语料库中，那么A总能获胜。请自己找出A获胜的策略。

给定一个语料库，Aidin想知道是否无论B如何进行游戏，玩家A一定能获胜？

请注意在任何一次游戏结束时，如果A获胜，A需要能够给出一个语料库中的单词作为被选出的单词，这个单词应当与A所有给出的回答一致。

inputFormat:
输入包含若干个语料库，每个语料库应该被独立地处理。

输入的第一行是一个整数C，代表语料库的数目。随后C个语料库以C个模块的形式出现在输入中，每两个模块之间以一个空行隔开。1<=C<=20。

对于每个输入模块，第一行包含一个正整数k，表示语料库中单词的个数。接下来的若干行中包含k个单词。相邻的单词以空格、制表符或换行符分隔。每个单词由小于7个大写英语字母组成。

每个单词都由不同的字母组成，也就是说，同一个字母在一个单词中出现的次数不会超过一次。

outputFormat: 对于每个语料库，如果玩家A有必胜策略（也就是说，不论B按什么办法猜，A总能获胜），输出一行“Yes”。否则输出一行“No”。输出不包含引号。

samples:
2
12
SI ME AND AI ARE MD AS WHEN ED IS DE HAPY
5
A B AB AC AD

hint:
对于20%的测试数据，k<=100，每个单词的长度不超过3。

对于50%的测试数据，k<=300，每个单词的长度不超过4。

对于100%的测试数据，k<=1000。输入文件小于500KB。


title: [APIO2012] 守卫

description:
APIO 王国正被忍者攻击！忍者非常厉害，因为他们在进攻的时候可以躲在 阴影里面使得其他人看不到他们。整个王国除了国王居住的 APIO 城堡以外都已 经被占领了。在城堡前，有 N 个灌木丛，从 1 到 N 编号，有 K 个忍者躲在恰好 K 个灌木丛后面。APIO 城堡里有 M 个守卫。守卫 i 监视着编号从 Ai到 Bi的连续 的一段灌木丛。每个守卫都向国王报告在他所监视范围内是否有忍者出现。作为 国王的仆人，你需要告诉国王，基于守卫的报告，哪些灌木丛后面一定躲着一个 忍者，即对于任何和守卫报告不矛盾的忍者排列方式，在这个灌木丛后面都躲着 一个忍者。

你需要写一个程序来输出所有的这些灌木丛的编号。

inputFormat:
第一行包含三个用空格分隔的整数 N, K, M，N 是灌木丛的个数，K 是忍者 的个数，M 是守卫的个数。

接下来 M 行，每行描述一个守卫的信息。其中的第 i 行包含三个整数 Ai, Bi, Ci，表示第 i 个守卫的监视范围是从 Ai到 Bi（Ai ≤ Bi）。Ci是 0 或者 1，若是 0 表 示范围内没有看到忍者，1 表示范围内有至少一个忍者。

输入数据保证至少存在一种忍者排列方式满足所有条件。

outputFormat: 若存在灌木丛，在其后面一定躲着忍者，则将这些一定躲着忍者的灌木丛按 照编号从小到大的顺序依次输出，每个一行。即若有 X 个这样的灌木丛，则需 要输出 X 行。若不存在，则输出一行一个“-1”，不包含引号。

hint:
【样例说明 1】

在这个样例中，有两种可能的安排方式：1，3，5 或者 2，3，5。即 3 和 5 后面必然躲着一个忍者。 考虑第一个灌木丛，存在一种安排方案使得它的后面躲着忍者，但也存在一 种安排方案使得它后面没有躲忍者，因此不应该输出 1。同理，不应该输出 2。

【样例说明 2】

在这个样例中，没有灌木丛后面一定躲着忍者。

灌木的数量 1 ≤ N ≤ 100,000 ；

忍者数 1 ≤ K ≤ N ；

守卫数 0 ≤ M < 100,000 。

对于 10%的数据，N ≤ 20， M ≤ 100；

对于 50%的数据，N ≤ 1000， M ≤ 1000。


title: [APIO2012] 苦无

description:
苦无(Kunai)是一种忍者使用的形状像刀的武器，忍者通过投掷苦无攻击对 手。 现在有 $N$ 名忍者聚集在一块 $H$ 行 $W$ 列的棋盘式的广场上。每个忍者都站在 其所在方块的中心处，任何两个忍者都不在同一个方块上。每个忍者都拿着一个 苦无，面朝上、下、左、右四个方向中的一个方向站着。在时刻 $0$，所有忍者同 时向其所朝向的方向投掷苦无。

每个苦无将会一直保持其初始的方向，并以单位速度飞行。如果某个时刻一 个位置上多于一个的苦无，它们将会相撞并且消失。苦无特别小，可以看成质点。 同时，由于忍者的移动速度特别快，他们不会被苦无击中。

在下面的例子中，我们用箭头来表示苦无，而箭头的方向即为苦无的方向。 在这些图中，所有的苦无都会相撞后消失。

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

在下面的图中，两个粗线箭头表示的苦无不会相撞。其中在第二个和第三个 图中，其中一个粗线表示的苦无会与细线表示的苦无相撞后消失，因此不会撞上 另一个粗线表示的苦无。

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

你的任务是计算经过足够长的时间之后，在这个 $W × H$ 的广场中有多少格 子被苦无经过。

inputFormat:
第一行包含两个被空格隔开的整数 $W$, $H$，表示广场的尺寸为 $W$ 列 $H$ 行。 第二行包含一个整数 $N$，表示忍者的数量。

接下来 $N$ 行中，第 $i$ 行有三个以空格分隔的整数 $X_i, Y_i, D_i$, 表示第 $i$ 个忍者 处在从左往右的 $X_i$ 列、从上往下的第 $Y_i$ 行，任何两个忍者不在同一个位置。第 $i$ 个忍者面向的方向由 $D_i$ 表示，分别为：

- $D_i = 0$，表示忍者向右；
- $D_i = 1$，表示忍者向上；
- $D_i = 2$，表示忍者向左；
- $D_i = 3$，表示忍者向下。

outputFormat: 输出一个整数，表示经过足够长的时间之后，在这个 $W × H$ 的广场中被苦 无经过被苦无经过的格子数量。


title: [APIO2013] 机器人

description:
VRI（Voltron 机器人学会）的工程师建造了 n 个机器人。任意两个兼容的机 器人站在同一个格子时可以合并为一个复合机器人。

我们把机器人用 1 至 n 编号（n ≤ 9）。如果两个机器人的编号是连续的，那 么它们是兼容的，可以合并成一个复合机器人。最初这 n 个机器人各自都只有唯 一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号， 分别是构成它的所有机器人中最小和最大的编号。

例如，2 号机器人只可以与 1 号或 3 号机器人合并。若 2 号机器人与 3 号机 器人合并，可构成编号为 2-3 的复合机器人。如果编号为 2-3 的复合机器人与编 号为 4-6 的复合机器人合并，可构成编号为 2-6 的复合机器人。当所有机器人合 并以后则构成 1-n 复合机器人。

工程师把这 n 个机器人放在了一个封闭的房间中，房间四周均是墙。该房间 被划分成 w × h 个方格。有些方格有障碍物，机器人不可经过或停留；其余方格 允许多个机器人停留，同时允许机器人经过。任何时候一个机器人只占用一个方 格。初始时刻，所有机器人均在不同的方格中。

这些原始的机器人不会自发地移动。它们只有被工程师沿 x 轴或 y 轴推动 后，才会沿推动的方向不断向前直线移动，直至碰到障碍物或墙停止移动。停止 移动后，它会扫描当前的格子是否存在可以与它合并的机器人，如果有，则合并 并继续检查，直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向 上、竖直向下四个方向推动机器人，并且，在机器人尚未停止移动时，不允许推 动其它机器人，因此任何时刻，房间中都只能有一个机器人移动。

为了帮助机器人转向，工程师在一些格子中放置了转向器。具体地说，转向 器分为顺时针转向器（右转器）和逆时针转向器（左转器），顺时针转向器可以 使到达该格子的机器人沿顺时针方向转向 90°；逆时针转向器可以使到达该格 子的机器人沿逆时针方向转向 90°。

现在，我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要 推动机器人多少次，才能把所有的 n 个机器人全部合并（如果可能的话）。

inputFormat:
你的程序必须从标准输入读入。

输入的第 1 行包含 3 个整数 n、w 和 h，用 空格隔开。

输入文件中接下来的 h 行描述初始时刻房间内的信息，每行包含 w 个字符。 这 w × h 个字符中每一个表示房间中的一个格子，意义如下：

‘1’至‘9’：表示该方格中有一个机器人，编号为这个数字；

‘x’：表示该方格有障碍物；

‘A’：表示该方格中有一个逆时针转向器；

‘C’：表示该方格中有一个顺时针转向器；

‘.’：表示该方格为空地。

outputFormat: 你的程序必须输出到标准输出。输出仅一个整数，表示最少需要推动的次数。 若不能使所有机器人全部合并，输出-1。

hint:
第一步：向右推动 3 号机器人，当它碰到转向器后会向上继续移动，直至碰 到墙壁停止移动。

第二步：向上推动 4 号机器人，当它碰到墙壁后停止移动，与 3 号机器人合 并，构成 3-4 号机器人

第三步：向上推动 2 号机器人，当它碰到转向器后会向左移动，由于左侧为 墙壁，故停留在原地。

第四步：向右推动 2 号机器人，由于它在一个转向器上，故它会向上移动， 直至碰到墙壁停止移动，与 1 号机器人合并，构成 1-2 号机器人。

第五步：向左推动 3-4 号机器人，当它碰到墙壁后停止移动，与 1-2 号机器 人合并，构成 1-4 号机器人。

我们将使用以下 4 类输入测例测试你的程序。

1. （10 分）测例满足 n = 2，w ≤ 10 且 h ≤ 10，没有任何转向器。

2. （20 分）测例满足 n = 2，w ≤ 10 且 h ≤ 10。

3. （30 分）测例满足 n ≤ 9，w ≤ 300 且 h ≤ 300。

4. （40 分）测例满足 n ≤ 9，w ≤ 500 且 h ≤ 500。


title: 约数和

background: Smart 最近沉迷于对约数的研究中。

description: 对于一个数 $X$，函数 $f(X)$ 表示 $X$ 所有约数的和。例如：$f(6)=1+2+3+6=12$。对于一个 $X$，Smart 可以很快的算出 $f(X)$。现在的问题是，给定两个正整数 $X,Y(X<Y)$，Smart 希望尽快地算出 $f(X)+f(X+1)+……+f(Y)$的值，你能帮助 Smart 算出这个值吗？

inputFormat: 输入文件仅一行，两个正整数 $X$ 和 $Y(X<Y)$，表示需要计算 $f(X)+f(X+1)+\dots +f(Y)$。

outputFormat: 输出只有一行，为 $f(X)+f(X+1)+\dots+f(Y)$ 的值。

hint:
对于 $20\%$ 的数据有 $1\leq X<Y\leq 10^5$。

对于 $60\%$ 的数据有 $1\leq X<Y\leq 1\times 10^7$。

对于 $100\%$ 的数据有 $1\leq X<Y\leq 2\times 10^9$。


title: 删数

description:
有 $N$ 个不同的正整数 $x_1$, $x_2$, ..., $x_N$ 排成一排，我们可以从左边或右边去掉连续的 $i$ $(1 \le i \le n)$ 个数（只能从两边删除数），剩下 $N-i$ 个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。

每次操作都有一个操作价值，比如现在要删除从 $i$ 位置到 $k$ 位置上的所有的数。操作价值为 $|x_i-x_k| \times (k-i+1)$ ，如果只去掉一个数，操作价值为这个数的值。
问如何操作可以得到最大值，求操作的最大价值。

inputFormat:
第一行为一个正整数 $N$ ;

第二行有 $N$ 个用空格隔开的 $N$ 个不同的正整数。

outputFormat: 一行，包含一个正整数，为操作的最大值

hint:
**【样例解释和说明】**

说明，经过 $3$ 次操作可以得到最大值，第一次去掉前面 $3$ 个数：$54$ 、$29$ 、$196$ ，操作价值为 $426$。第二次操作是在剩下的三个数 $(21,133,118)$ 中去掉最后一个数$118$，操作价值为 $118$。第三次操作去掉剩下的 $2$ 个数：$21$ 和 $133$ ，操作价值为 $224$。操作总价值为 $426+118+224=768$ 。

**【数据范围】**

$3≤N≤100$ ，$1 \le x_i \le 1000$


title: [HEOI2012] 朋友圈

background: 原 双塔 请做P1651

description:
在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着．

一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目．两个国家看成是 AB 两国，现在是两个国家的描述：

- A 国：每个人都有一个友善值，当两个 A 国人的友善值 $a,b$，如果 $(a\mathbin{\mathrm{xor}} b) \bmod 2=1$，那么这两个人都是朋友，否则不是；
- B 国：每个人都有一个友善值，当两个 B 国人的友善值 $a,b$，如果 $(a\mathbin{\mathrm{xor}} b) \bmod 2=0$ 或者 $(a\mathbin{\mathrm{or}} b)$ 化成二进制有奇数个 $1$，那么两个人是朋友，否则不是朋友．

A、B 两国之间的人也有可能是朋友，数据中将会给出 A、B 之间「朋友」的情况．

对于朋友的定义，关系是是双向的．

在 AB 两国，朋友圈的定义：一个朋友圈集合 $S$，满足 $S \subset A \cup B$，对于所有的 $i,j \in S$，$i$ 和 $j$ 是朋友．

inputFormat:
**本题包含多组数据．**

- 第一行一个整数 $T$，表示输入数据总数．
- 对于每组数据：
  - 第 $1$ 行 $3$ 个整数 $A,B,M$，分别表示 A 国人数，B 国人数，AB 两国之间是朋友的对数．
  - 第 $2$ 行 $A$ 个整数 $a_i$，表示 A 国第 $i$ 个人的友善值．
  - 第 $3$ 行 $B$ 个整数 $b_i$，表示 B 国第 $i$ 个人的友善值．
  - 第 $4$ 到第 $3+M$ 行，每行两个整数 $x,y$ 表示 A 国的第 $x$ 个人和 B 国第 $y$ 个人是朋友．

outputFormat: - 输出 $T$ 行，每行输出一个整数，表示最大朋友圈的数目．

hint:
### 样例解释

最大朋友圈包含 A 国第 $1,2$ 人和 B 国第 $1,2,3$ 人．

### 数据范围

对于 $100\%$ 的数据，$1 \le T \le 6$，$1 \le a_i, b_i < 2^{31}$．

本题共有两类数据，保证所有测试点均满足其中至少一类的限制：

- 第一类：$1 \le A \le 200, 1 \le B \le 200$．
- 第二类：$1 \le A \le 10, 1 \le B \le 3000$．


title: [APIO2013] 道路费用

description:
幸福国度可以用 N 个城镇（用 1 到 N 编号）构成的集合来描述，这些城镇 最开始由 M 条双向道路（用 1 到 M 编号）连接。城镇 1 是中央城镇。保证一个 人从城镇 1 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是 收费道路，道路 i 的使用者必须向道路的主人支付 ci分钱的费用。已知所有的这 些ci是互不相等的。最近有K条新道路建成，这些道路都属于亿万富豪Mr. Greedy。 Mr. Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣 布这些费用。

两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这 些道路游行并前往中央城镇。共计 pj个参与者将从城镇 j 出发前往中央城镇。这 些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一 天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就 是 Mr. Greedy。同样根据这个习俗，Mr. Greedy 选出的这个道路集合必须使所有 选出道路的费用之和最小，并且仍要保证任何人可以从城镇 j 前往城镇 1（因此， 这些选出的道路来自将费用作为相应边边权的“最小生成树”）。如果有多个这样 的道路集合，Mr. Greedy 可以选其中的任何一个，只要满足费用和是最小的。

Mr. Greedy 很明确地知道，他从 K 条新道路中获得的收入不只是与费用有 关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 p 个人经过道路 i，道路 i 产生的收入为 ci p 的积。注意 Mr. Greedy 只能从新道路 收取费用，因为原来的道路都不属于他。

Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收 入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路 （将在嘉年华的前一天公布），使得他在 K 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序 来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

inputFormat:
你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数 N，M 和 K。接下来的 M 行描述最开始的 M 条道路。这 M 行中的第 i 行包含由空格隔开 的整数 ai，bi和 ci，表示有一条在 ai 和 bi之间，费用为 ci 的双向道路。接下来的 K 行描述新建的 K 条道路。这 K 行中的第 i 行包含由空格隔开的整数 xi和 yi，表 示有一条连接城镇 xi 和 yi 新道路。最后一行包含 N 个由空格隔开的整数，其中 的第 j 个为 pj，表示从城镇 j 前往城镇 1 的人数。

输入也满足以下约束条件。 

1 ≤ N ≤ 100000； 

1 ≤ K ≤ 20； 

1 ≤ M ≤ 300000； 

对每个 i 和 j，1 ≤ ci, pj ≤ 10^6；

如果 i ≠ i'，则 ci ≠ ci'； 

在任意两个城市之间，最多只有一条道路（包括新建的道路）。

outputFormat: 你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。

hint:
在样例中，Mr. Greedy 应该将新道路(1,3)的费用设置为 5 分钱。在这个费用 下，他可以选择道路(3,5)，(1,2)，(2,4)和(1,3)来最小化总费用，这个费用为 14。 从城镇 3 出发的 30 个人和从城镇 5 出发的 50 个人将经过新道路前往城镇 1，因 此他可以获得为(30+50)×5=400 分钱的最好收入。

如果我们这样做，将新道路(1,3)的费用设置为 10 分钱。根据传统的限制， Mr. Greedy 必须选择(3,5)，(1,2)，(2,4)和(2,3)，因为这是唯一费用最小的集合。 因此，在嘉年华的过程中道路(1,3)将没有任何收入。

我们将使用以下 5 类测例测试你的程序。

1. （国际 16 分，国内 15 分）N ≤ 10，M ≤ 20 且 K = 1；

2. （国际 18 分，国内 20 分）N ≤ 30，M ≤ 50 且 K ≤ 10；

3. （国际 22 分，国内 20 分）N ≤ 1,000，M ≤ 5,000 且 K ≤ 10；

4. （国际 22 分，国内 20 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 15；

5. （国际 22 分，国内 25 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 20。

**update: 2024/07/04 删除了两个测试点，并且改为捆绑。**


title: [APIO2014] 回文串

description:
给你一个由小写拉丁字母组成的字符串 $s$。我们定义 $s$ 的一个子串的存在值为这个子串在 $s$ 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 $s$，求所有回文子串中的最大存在值。

inputFormat: 一行，一个由小写拉丁字母（a~z）组成的非空字符串 $s$。

outputFormat: 输出一个整数，表示所有回文子串中的最大存在值。

hint:
【样例解释1】

用 $\lvert s \rvert$ 表示字符串 $s$ 的长度。

一个字符串 $s_1 s_2 \dots s_{\lvert s \rvert}$ 的子串是一个非空字符串 $s_i s_{i+1} \dots s_j$，其中 $1 \leq i \leq j \leq \lvert s \rvert$。每个字符串都是自己的子串。

一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。

这个样例中，有 $7$ 个回文子串 a，b，c，aba，aca，bacab，abacaba。他们的存在值分别为 $4, 2, 1, 6, 3, 5, 7$。

所以回文子串中最大的存在值为 $7$。

第一个子任务共 8 分，满足 $1 \leq \lvert s \rvert \leq 100$。

第二个子任务共 15 分，满足 $1 \leq \lvert s \rvert \leq 1000$。

第三个子任务共 24 分，满足 $1 \leq \lvert s \rvert \leq 10000$。

第四个子任务共 26 分，满足 $1 \leq \lvert s \rvert \leq 100000$。

第五个子任务共 27 分，满足 $1 \leq \lvert s \rvert \leq 300000$。


title: [APIO2014] 序列分割

description:
你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：

选择一个有超过一个元素的块（初始时你只有一块，即整个序列）

选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

inputFormat:
第一行包含两个整数 $n$ 和 $k$。保证 $k + 1 \leq n$。

第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$ $(0 \leq a_i \leq 10^4)$，表示前文所述的序列。

outputFormat:
第一行输出你能获得的最大总得分。

第二行输出 $k$ 个介于 $1$ 到 $n - 1$ 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 $i$ 个整数 $s_i$ 表示第 $i$ 次操作将在 $s_i$ 和 $s_{i + 1}$ 之间把块分开。

如果有多种方案使得总得分最大，输出任意一种方案即可。

hint:
你可以通过下面这些操作获得 $108$ 分：

初始时你有一块 $(4, 1, 3, 4, 0, 2, 3)$。在第 $1$ 个元素后面分开，获得 $4 \times (1 + 3 + 4 + 0 + 2 + 3) = 52$ 分。

你现在有两块 $(4), (1, 3, 4, 0, 2, 3)$。在第 $3$ 个元素后面分开，获得 $(1 + 3) \times (4 + 0 + 2 + 3) = 36$ 分。

你现在有三块 $(4), (1, 3), (4, 0, 2, 3)$。在第 $5$ 个元素后面分开，获得 $(4 + 0) \times (2 + 3) = 20$ 分。

所以，经过这些操作后你可以获得四块 $(4), (1, 3), (4, 0), (2, 3)$ 并获得 $52 + 36 + 20 = 108$ 分。

限制与约定

第一个子任务共 11 分，满足 $1 \leq k < n \leq 10$。

第二个子任务共 11 分，满足 $1 \leq k < n \leq 50$。

第三个子任务共 11 分，满足 $1 \leq k < n \leq 200$。

第四个子任务共 17 分，满足 $2 \leq n \leq 1000, 1 \leq k \leq \min\{n - 1, 200\}$。

第五个子任务共 21 分，满足 $2 \leq n \leq 10000, 1 \leq k \leq \min\{n - 1, 200\}$。

第六个子任务共 29 分，满足 $2 \leq n \leq 100000, 1 \leq k \leq \min\{n - 1, 200\}$。

感谢@larryzhong  提供的加强数据


title: [SDOI2005] 区间

description:
现给定 $n$ 个闭区间 $[a_i, b_i]$（$1 \le i \le n$）。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间 $[a, b]$ 和 $[c, d]$ 是按照升序排列的，那么我们有 $a \le b < c \le d$。

请写一个程序：

读入这些区间；

计算满足给定条件的不相交闭区间；

把这些区间按照升序输出。

inputFormat:
第一行包含一个整数 $n$（$3 \le n \le 50000$）为区间的数目。
以下 $n$ 行为对区间的描述，第 $i$ 行为对第 $i$ 个区间的描述，为两个整数 $a_i, b_i$（$1 \le a _ i \leq b _ i \le 1000000$），表示一个区间 $[a_i, b_i]$。

outputFormat: 输出计算出来的不相交的区间。每一行都是对一个区间的描述，包括两个用空格分开的整数，为区间的上下界。你应该把区间按照升序排序。


title: [SDOI2005] 解环

background:
拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军（该国的统帅）作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根“拜特链”将拜特萨锁在墙边.该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。

“将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特萨大叫道。

“拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。”拜特将军回答，同时他补充说，“但是，你必须在夜里工作，一个小时之内完成，不能弄出任何声音，否则，我将按有关法律治罪。”

description:
为了帮助拜特萨！链子上的环按整数1,2,…,n进行了编号。我们可以按照以下规则解开环：

    只有一个环时可以被连接到栅栏或从栅栏上拆开。

    第1号环总能进行连接或拆开

    如果1,...,k-1 (1<=k<n)环都被拆开，第k个环被连接时, 此时我们能连接或拆开 第k+1个环.

写一个程序：

输入描述了拜特链的构成,

计算拆除拜特链上全部环的最少操作次数,

将结果输出。

inputFormat: 第1行有一个整数n, 1<=n<=1 000.在第2行有n个用一个空格分隔的整数 o1,o2,...,on (每个都是0或1)，如果 oi=1, 那么第I个环和栅栏相连，如果 oi=0, 那么第I环没有和栅栏相连。

outputFormat: 只包含一个整数，为解开拜特链的全部环的最少操作次数。


title: [SDOI2005] 阶梯教室设备利用

description:
我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，也就是说，我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

请写一个程序：

读入所有演讲的起始和终止时间，计算最大的可能演讲总时间。

inputFormat:
第一行包括一个正整数 $n$，为所有的演讲的数目。

以下的 $n$ 行每行含有两个由空格隔开的整数 $p$ 和 $k$。这样的一对整数表示一个演讲由时间 $p$ 开始到时间 $k$ 结束。

outputFormat: 输出唯一的一个整数，为最长的演讲总时间。

hint:
### 样例解释

可以选择第 $3$ 个、第 $5$ 个、第 $6$ 个、第 $11$ 个、第 $12$ 个演讲，此时有最长的演讲总时间 $16$。

### 数据范围

$1\le n\le 10^4$，$0\le p<k\le 3\times 10^4$。


title: [APIO2014] 连珠线

description:
在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 $1$ 到 $n$。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子：

`Append(w, v)`：一个新的珠子 $w$ 和一个已经添加的珠子 $v$ 用红线连接起来。

`Insert(w, u, v)`：一个新的珠子 $w$ 插入到用红线连起来的两个珠子 $u, v$ 之间。具体过程是删去 $u, v$ 之间红线，分别用蓝线连接 $u, w$ 和 $w, v$。

每条线都有一个长度。游戏结束后，你的最终得分为蓝线长度之和。

给你连珠线游戏结束后的游戏局面，只告诉了你珠子和链的连接方式以及每条线的长度，没有告诉你每条线分别是什么颜色。

你需要写一个程序来找出最大可能得分。即，在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的，然后输出最大可能得分。

inputFormat:
第一行一个正整数 $n$，表示珠子的数量。珠子从 $1$ 到 $n$ 编号。

接下来 $n - 1$ 行每行三个整数 $a_i, b_i, c_i$。保证 $1 \leq a_i < b_i \leq n$。$1 \leq c_i \leq 10000$。表示 $a_i$ 号珠子和 $b_i$ 号珠子间连了长度为 $c_i$ 的线。

outputFormat: 输出一个整数，表示最大可能得分。

hint:
【样例描述1】

可以通过如下方式获得 $60$ 分：首先从 $3$ 号珠子开始。

把 $5$ 和 $3$ 连起来。（线长度任意）

在 $3$ 和 $5$ 之间插入 $1$。（线长分别为 $40$ 和 $20$）。

把 $2$ 和 $1$ 用长度为 $10$ 的线连起来。

把 $4$ 和 $1$ 用长度为 $15$ 的线连起来。

【限制与约定】

第一个子任务共 13 分，满足 $1 \leq n \leq 10$。

第二个子任务共 15 分，满足 $1 \leq n \leq 200$。

第三个子任务共 29 分，满足 $1 \leq n \leq 10000$。

第四个子任务共 43 分，满足 $1 \leq n \leq 200000$。


title: [APIO2015] 巴厘岛的雕塑

description:
印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。

在这条主干道上一共有 $N$ 座雕塑，为方便起见，我们把这些雕塑从 $1$ 到 $N$ 连续地进行标号，其中第 $i$ 座雕塑的年龄是 $Y_i$ 年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。

下面是将雕塑分组的规则：

这些雕塑必须被分为恰好 $X$ 组，其中 $A \leq X \leq B$，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。

当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。

计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。

请问政府能得到的最小的最终优美度是多少?

备注：将两个非负数 $P$ 和 $Q$ 按位取或是这样进行计算的：

首先把 $P$ 和 $Q$ 转换成二进制。

设 $n_P$ 是 $P$ 的二进制位数，$n_Q$ 是 $Q$ 的二进制位数，$M$ 为 $n_P$ 和 $n_Q$ 中的最大值。$P$ 的二进制表示为 $p_{M-1}p_{M-2} \dots p_1p_0$，$Q$ 的二进制表示为 $q_{M-1}q_{M-2} \dots q_1 q_0$，其中 $p_i$ 和 $q_i$ 分别是 $P$ 和 $Q$ 二进制表示下的第 $i$ 位，第 $M -1$ 位是数的最高位，第 $0$ 位是数的最低位。

$P$ 与 $Q$ 按位取或后的结果是： $(p_{M-1}\mathbin{\mathrm{OR}} q_{M-1})(p_{M-2}\mathbin{\mathrm{OR}}q_{M-2})\dots (p_1\mathbin{\mathrm{OR}} q_1) (p_0\mathbin{\mathrm{OR}}q_0)$。其中：$0 \mathbin{\mathrm{OR}} 0 = 0$

$0 \mathbin{\mathrm{OR}} 1 = 1$

$1 \mathbin{\mathrm{OR}} 0 = 1$

$1 \mathbin{\mathrm{OR}} 1 = 1$

inputFormat:
输入的第一行包含三个用空格分开的整数 $N, A, B$。

第二行包含 $N$ 个用空格分开的整数 $Y_1, Y_2, \dots, Y_N$。

outputFormat: 输出一行一个数，表示最小的最终优美度。

hint:
【样例解释】

将这些雕塑分为 $2$ 组，$(8, 1, 2)$ 和 $(1, 5, 4)$，它们的和是 $(11)$ 和 $(10)$，最终优美度是 $(11 \mathbin{\mathrm{OR}} 10) = 11$。（不难验证，这也是最终优美度的最小值。）

【数据范围】

子任务 1 （9 分）$1 \leq N \leq 20$

$1 \leq A \leq B \leq N$

$0 \leq Y_i \leq 1000000000$

子任务 2 （16 分）$1 \leq N \leq 50$

$1 \leq A \leq B \leq \min\{20, N\}$

$0 \leq Y_i \leq 10$

子任务 3 （21 分）$1 ≤ N ≤ 100$

$A = 1$

$1 \leq B \leq N$

$0 \leq Y_i \leq 20$

子任务 4 （25 分）$1 \leq N \leq 100$

$1 \leq A \leq B \leq N$

$0 \leq Y_i \leq 1000000000$

子任务 5 （29 分）$1 \leq N \leq 2000$

$A = 1$

$1 \leq B \leq N$

$0 \leq Y_i \leq 1000000000$


title: [APIO2015] 雅加达的摩天楼

description:
印尼首都雅加达市有 $N$ 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 $0$ 到 $N − 1$。除了这 $N$ 座摩天楼外，雅加达市没有其他摩天楼。

有 $M$ 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 $0$ 到 $M − 1$。编号为 $i$ 的 doge 最初居住于编号为 $B_i$ 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 $i$ 的 doge 的跳跃能力为 $P_i$ （$P_i > 0$）。

在一次跳跃中，位于摩天楼 $b$ 而跳跃能力为 $p$ 的 doge 可以跳跃到编号为 $b - p$ （如果 $0 \leq b - p < N$）或 $b + p$ （如果 $0 \leq b + p < N$）的摩天楼。

编号为 $0$ 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编号为 $1$ 的 doge。任何一个收到消息的 doge 有以下两个选择:

- 跳跃到其他摩天楼上；
- 将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 $0$ 号 doge 传递到 $1$ 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 $1$ 号 doge。

inputFormat:
输入的第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $B_i$ 和 $P_i$。

outputFormat: 输出一行，表示所需要的最少步数。如果消息永远无法传递到 $1$ 号 doge，输出 $−1$。

hint:
【样例解释】

下面是一种步数为 $5$ 的解决方案：

$0$ 号 doge 跳跃到 $2$ 号摩天楼，再跳跃到 $4$ 号摩天楼（$2$ 步）。

$0$ 号 doge 将消息传递给 $2$ 号 doge。

$2$ 号 doge 跳跃到 $3$ 号摩天楼,接着跳跃到 $2$ 号摩天楼，再跳跃到 $1$ 号摩天楼（$3$ 步）。

$2$ 号 doge 将消息传递给 $1$ 号 doge。

【数据范围】

所有数据都保证 $0 \leq B_i < N$。

子任务 1 （10 分）$1 \leq N \leq 10$

$1 \leq P_i \leq 10$

$2 \leq M \leq 3$

子任务 2 （12 分）$1 \leq N \leq 100$

$1 \leq P_i \leq 100$

$2 \leq M \leq 2000$

子任务 3 （14 分）$1 \leq N \leq 2000$

$1 \leq P i ≤ 2000$

$2 \leq M \leq 2000$

子任务 4 （21 分）$1 \leq N \leq 2000$

$1 \leq P_i \leq 2000$

$2 \leq M \leq 30000$

子任务 5 （43 分）$1 \leq N \leq 30000$

$1 \leq P_i \leq 30000$

$2 \leq M \leq 30000$


title: 角色属性树

description:
绪萌同人社是一个有趣的组织，该组织结构是一个树形结构。有一个社长，直接下属一些副社长。每个副社长又直接下属一些部长……。

每个成员都有一个萌点的属性，萌点属性是由一些质数的萌元素乘积构成（例如，猫耳的值是 $2$，弱气的值是 $3$，黄毛的值是 $5$，病娇的值是 $7$，双马尾的值是 $11$ 等等）

举个例子，正妹是双份的猫耳，而且有一份弱气，她的属性值为 $2\times 2\times 3=12$。

现在组员关心一个问题，希望知道离自己最近且有相同萌元素上司是谁，例如，属性值为 $2、4、6、45$ 这样的属性值都算是和正妹有相同的属性。

然而，组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。

inputFormat:
第一行，$n,k$ 表示成员数与询问的次数

第二行，$n$ 个数，分别是 $1$ 到 $n$ 号成员的属性值

接下来 $n-1$ 行，$x_i,y_i$ 表示 $x_i$ 是 $y_i$ 的上司。

接下来来 $k$ 行，有两种情况

$1\ u_i$：询问离 $u_i$ 成员最近且有相同萌元素上司。

$2\ u_i$：$a$ 更改 $u_i$ 的属性值为 $a$。

outputFormat: 对于每个 $1$ 类型的询问，输出符合要求的编号。如果没有符合要求的编号，输出 $-1$。

hint:
对于 $20\%$ 的数据，没有修改的操作。

对于 $50\%$ 的数据，$n\le 100$，修改次数 $<10$。

对于 $100\%$ 的数据，$n\le 200000$，$k<100000$，修改次数 $\le 50,a\_i\le 2^{31}-1$

UPD：本题测试数据随机，可能是假题。


title: zxbsmk爱查错

background: zxbsmk 在暑假回了一趟老家，见到了自己的外婆。然而他遇到了一个问题。

description:
外婆很喜欢给别人写信，然而因为年纪大了，信里面充斥着各种错误。所以 zxbsmk 打算帮外婆修正每个错误的句子。

因为外婆的文化水平很高，所以她写的句子都是英文句子，并且句子内的字母都是小写字母。然而 zxbsmk 的英语水平非常低，所以他买来了一本英语词典，词典里一共有 $W (1 \leq W \leq 600)$ 个单词，每个单词的长度都不超过 $25$ 个字母，而且都是由小写字母组成的。

那么再来看一下外婆的句子都有什么错误。例如，外婆写的一个句子是 `catotail`，这并没有什么意义，因为一个多余的字母 `o` 出现了，所以正确的句子应该是 `cattail`。

已知外婆的句子是由 $L (2 \leq L \leq 300)$ 个字母组成的。其中有一些字母是多余的。现在，请你借助 zxbsmk 的词典，帮助他修正外婆的句子。而且你必须尽量少地去除多余的字母，使剩余的字母是一个合法的句子。

inputFormat:
第一行：输入两个整数 $W$ 和 $L$。

第二行：输入 $L$ 个字符，表示需要修正的句子。

之后的 $W$ 行，每行输入一个合法的单词。

outputFormat: 一个整数，表示最少需要剔除的字母数。

hint: `catotail` $\to$ `cattail`


title: [APIO2015] 巴邻旁之桥

description:
一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 $A$ 和区域 $B$。

每一块区域沿着河岸都建了恰好 $1000000001$ 栋的建筑，每条岸边的建筑都从 $0$ 编号到 $1000000000$。相邻的每对建筑相隔 $1$ 个单位距离，河的宽度也是 $1$ 个单位长度。区域 $A$ 中的 $i$ 号建筑物恰好与区域 $B$ 中的 $i$ 号建筑物隔河相对。

城市中有 $N$ 个居民。第 $i$ 个居民的房子在区域 $P_i$ 的 $S_i$ 号建筑上，同时他的办公室坐落在 $Q_i$ 区域的 $T_i$ 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过 $K$ 座横跨河流的大桥。

由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。

当政府建造最多 $K$ 座桥之后，设 $D_i$ 表示第 $i$ 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 $D_1 + D_2 + \cdots + D_N$ 最小。

inputFormat:
输入的第一行包含两个正整数 $K$ 和 $N$，分别表示桥的上限数量和居民的数量。

接下来 $N$ 行，每一行包含四个参数：$P_i, S_i, Q_i$ 和 $T_i$，表示第 $i$ 个居民的房子在区域 $P_i$ 的 $S_i$ 号建筑上，且他的办公室位于 $Q_i$ 区域的 $T_i$ 号建筑上。

outputFormat: 输出仅为一行，包含一个整数，表示 $D_1 + D_2 + \cdots + D_N$ 的最小值。

hint:
【数据范围】

所有数据都保证：$P_i$ 和 $Q_i$ 为字符 “A” 和 “B” 中的一个， $0 \leq S_i, T_i \leq 1000000000$，同一栋建筑内可能有超过 $1$ 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 $1$）。

子任务 1 （8 分）$K = 1$

$1 \leq N \leq 1000$

子任务 2 （14 分）$K = 1$

$1 \leq N \leq 100000$

子任务 3 （9 分）$K = 2$

$1 \leq N \leq 100$

子任务 4 （32 分）$K = 2$

$1 \leq N \leq 1000$

子任务 5 （37 分）$K = 2$

$1 \leq N \leq 100000$


title: [APIO2016] 划艇

description:
在首尔城中，汉江横贯东西。在汉江的北岸，从西向东星星点点地分布着 $N$ 个划艇学校，编号依次为 $1$ 到 $N$。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同，不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典，也可以选择不派出任何划艇参加。如果编号为 $i$ 的学校选择派出划艇参加庆典，那么，派出的划艇数量可以在 $a_i$ 至 $b_i$ 之间任意选择（$a_i \leq b_i$）。

值得注意的是，编号为 $i$ 的学校如果选择派出划艇参加庆典，那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。

输入所有学校的 $a_i,b_i$ 的值，求出参加庆典的划艇有多少种可能的情况，必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同。

inputFormat:
第一行包括一个整数 $N$，表示学校的数量。

接下来 $N$ 行，每行包括两个正整数，用来描述一所学校。其中第 $i$ 行包括的两个正整数分别表示 $a_i,b_i$（$1 \leq a_i \leq b_i \leq 10^9$）。

outputFormat: 输出一行，一个整数，表示所有可能的派出划艇的方案数除以 $1,000,000,007$ 得到的余数。

hint:
【样例解释】

在只有一所学校派出划艇的情况下有 $4$ 种方案，两所学校都派出划艇的情况下有 $3$ 种方案，所以答案为 $7$。

【数据范围】

子任务 $1$（$9$ 分）：$1 \leq N \leq 500$ 且对于所有的 $1 \leq i \leq N$，保证 $a_i=b_i$。

子任务 $2$（$22$ 分）：$1 \leq N \leq 500$ 且 $\sum_{i=1}^N (b_i-a_i) \leq 10^6$。

子任务 $3$（$27$ 分）：$1 \leq N \leq 100$。

子任务 $4$（$42$ 分）：$1 \leq N \leq 500$。


title: 【深基1-2】小学数学 N 合一

description:
### 问题 1

请输出 `I love Luogu!`

### 问题 2

这里有 $10$ 个苹果，小 A 拿走了 $2$ 个，Uim 拿走了 $4$ 个，小 B 拿走剩下的所有的苹果。我们想知道：

1. 小 A 和 Uim 两个人一共拿走多少苹果？
2. 小 B 能拿走多少苹果？

现在需要编写一个程序，输出两个数字作为答案，中间使用空格分开。

### 问题 3

现在有 $14$ 个苹果。要均分给 $4$ 名同学，分不掉的苹果放回冰箱。请问：

1. 每位同学能分得几个苹果？
2. 一共分出去多少苹果？
3. 把几个苹果放回冰箱？

 	现在需要编写一个程序，输出三个数字作为答案，每个数字一行。

### 问题 4

现在有 $500$ 毫升的肥宅快乐水，要均分给 $3$ 名同学，每位同学可以分到多少毫升？请输出一个数字作为输出。保留 $6$ 位有效数字，且不使用科学计数法。

### 问题 5

甲列火车长 $260$ 米，每秒行 $12$ 米；乙列火车长 $220$ 米，每秒行 $20$ 米，两车相向而行，从两车车头相遇时开始计时，多长时间后两车车尾相离？已知答案是整数。

### 问题 6

一个长方形长宽分别是 $6 \text{ cm}$、$9 \text{ cm}$，求它的对角线长度（$\text{cm}$）。直接使用 `cout` 输出。

### 问题 7

Uim 银行账户里面有 $100$ 元。经过了下面的操作：

1. 往里面存了 $10$ 元；
2. 购物花掉了 $20$ 元；
3. 把里面的钱全部取出。

 	请在每次操作后输出账户余额，并使用换行符隔开。

### 问题 8

当半径为 $r=5$，请输出圆的周长、面积和球体积。取 $\pi=3.141593$。请直接使用 `cout` 输出答案，每行一个数字。

### 问题 9

一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半，又贪嘴多吃了一个；第二天他也刚好吃了剩余桃子的一半，贪嘴多吃了一个；第三天他又刚好吃了剩下的桃子的一半，并贪嘴多吃了一个。第四天起来一看，发现桃子只剩下一个了。请问小猴买了几个桃子？

### 问题 10

洛谷的评测任务是单位时间内均匀增加的。$8$ 台评测机 $30$ 分钟可以刚好把评测队列中的程序评测完毕，$10$ 台评测机 $6$ 分钟可以刚好把评测队列中的程序评测完毕，请问几台评测机可以在 $10$ 分钟时刚好把评测队列中的程序评测完毕？

### 问题 11

小 A 跑步速度 $5 \text{ m/s}$，小 B 跑步速度 $8 \text{ m/s}$，小 B 在小 A 后面 $100 \text{ m}$，他们同时起跑，请问需要多长时间小 B 可以追上小 A？输出一个数字表示答案，使用 `cout` 直接输出。

### 问题 12

大家都知道有 $26$ 个英文字母，其中 A 是第一个字母。现在请编程求出：

1. M 是字母表中的第几个字母？
2. 第 $18$ 个字母是什么？

输出一个数字和一个字母，使用换行隔开。

### 问题 13

小 A 有两块球形橡皮泥，一个半径是 $4$，一个半径是 $10$。他想把这两块橡皮泥揉在一起，然后塑造成一个正方体，请问这个正方体的棱长是多少？如果结果不是整数，则舍去小数点之后的数字。取 $\pi = 3.141593$。

### 问题 14

根据咕咕网校的预测，当课程定价为 $110$ 元时，会有 $10$ 人报名。如果课程价格每降低 $1$ 元，就会多 $1$ 名报名者（反之亦然）。如果希望总共能收到 $3500$ 元学费的话，那么应该定价多少呢？已知本题有两个答案符合要求，则取较小的那一个。如果这个答案不是整数，则需四舍五入精确到整数。

inputFormat: 输入一个正整数，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
请解决以下小学数学题。你可以提交答案，也可以写一个程序。

对于本题来说，如果你不知道怎么输入，也可以这么抄：

```cpp
#include<iostream>
// 填上你觉得需要的其他头文件
using namespace std;
int main() {
    int T;
    cin >> T;
    if (T == 1) {
        // 粘贴问题 1 的主函数代码，除了 return 0
        cout << "I love Luogu!";
    } else if (T == 2) {
        // 粘贴问题 2 的主函数代码，除了 return 0
        cout << 2 + 4 << " " << 10 - 2 - 4;
    } else if (T == 3) {
        // 请自行完成问题 3 的代码
    } else if (T == 4) {
        // 请自行完成问题 4 的代码
    } else if (T == 5) {
        // 请自行完成问题 5 的代码
    } else if (T == 6) {
        // 请自行完成问题 6 的代码
    } else if (T == 7) {
        // 请自行完成问题 7 的代码
    } else if (T == 8) {
        // 请自行完成问题 8 的代码
    } else if (T == 9) {
        // 请自行完成问题 9 的代码
    } else if (T == 10) {
        // 请自行完成问题 10 的代码
    } else if (T == 11) {
        // 请自行完成问题 11 的代码
    } else if (T == 12) {
        // 请自行完成问题 12 的代码
    } else if (T == 13) {
        // 请自行完成问题 13 的代码
    } else if (T == 14) {
        // 请自行完成问题 14 的代码
    }
    return 0;
}
```


title: 数字工程

description:
ACM 实验室开启了一个数字工程项目，希望把正整数 $n$ 通过一些特殊方法变成 $1$。

可采用的方法有：

1. 减去 $1$
2. 除以它的任意一个素因子。

每操作一次消耗一个单位的能量。

请问把 $n$ 变成 $1$ 最少需要消耗多少能量？

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

对于每组测试，一行一个整数 $n$。

outputFormat: 一行一个整数，表示最少消耗的能量。


title: [APIO2016] 烟火表演

description:
烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全，烟花被安置在远离开关的位置上，通过一些导火索与开关相连。导火索的连接方式形成一棵树，烟花是树叶，如图所示。火花从开关出发，沿导火索移动。每当火花抵达一个分叉点时，它会扩散到与之相连的所有导火索，继续燃烧。导火索燃烧的速度是一个固定常数。图中展示了六枚烟花 $\{E_1, E_2, \dots, E_6\}$ 的连线布局，以及每根导火索的长度。图中还标注了当在时刻 $0$ 从开关点燃火花时，每一发烟花的爆炸时间。

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

Hyunmin 为烟花表演设计了导火索的连线布局。不幸的是，在他设计的布局中，烟花不一定同时爆炸。我们希望修改一些导火索的长度，让所有烟花在同一时刻爆炸。例如，为了让图中的所有烟花在时刻 $13$ 爆炸，我们可以像下图中左边那样调整导火索长度。类似地，为了让图中的所有烟花在时刻 $14$ 爆炸，我们可以像下图中右边那样调整长度。

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

修改导火索长度的代价等于修改前后长度之差的绝对值。例如，将上面那副图中布局修改为下面那副图的左边布局的总代价为 $6$，而修改为右边布局的总代价为 $5$。

导火索的长度可以被减为 $0$，同时保持连通性不变。

给定一个导火索的连线布局，你需要编写一个程序，去调整导火索长度，让所有的烟花在同一时刻爆炸，并使得代价最小。

inputFormat:
所有的输入均为正整数。令 $N$ 代表分叉点的数量，$M$ 代表烟花的数量。分叉点从 $1$ 到 $N$ 编号，编号为 $1$ 的分叉点是开关。烟花从 $N + 1$ 到 $N + M$ 编号。

输入第一行为 $N, M$。后面 $N + M - 1$ 行，第 $i$ 行两个整数 $P_{i + 1}, C_{i + 1}$。其中 $P_i$ 满足 $1 \leq P_i < i$，代表和分叉点或烟花 $i$ 相连的分叉点。$C_i$ 代表连接它们的导火索长度（$1 \leq C_i \leq 10^9$）除开关外，每个分叉点和多于 $1$ 条导火索相连，而每发烟花恰好与 $1$ 条导火索相连。

outputFormat: 输出调整导火索长度，让所有烟花同时爆炸，所需要的最小代价。

hint:
【数据规模】

子任务 1（7 分）：$N = 1$，$1 \leq M \leq 100$。

子任务 2（19 分）：$1 \leq N+M \leq 300$，且开关到任一烟花的距离不超过 $300$。

子任务 3（29 分）：$1 \leq N+M \leq 5000$。

子任务 4（45 分）：$1 \leq N+M \leq 300000$。


title: 严酷的训练

background: Lj 的朋友 WKY 是一名神奇的少年，在同龄人之中有着极高的地位。。。

description:
他的老师老王对他的程序水平赞叹不已，于是下决心培养这名小子。

老王的训练方式很奇怪，他会一口气让 WKY 做很多道题，要求他在规定的时间完成。而老王为了让自己的威信提高，自己也会把这些题都做一遍。

WKY 和老王都有一个水平值，他们水平值的比值和做这些题所用时间的比值成反比。比如如果 WKY 的水平值是 $1$，老王的水平值是 $2$，那么 WKY 做同一道题的时间就是老王的 $2$ 倍。

每个题目有他所属的知识点，这我们都知道，比如递归，动规，最短路，网络流。在这里我们不考虑这些事情，我们只知道他们分别是知识点 $1$，知识点 $2$……每一个知识点有他对应的难度，比如动态规划经常难于模拟。

而每一个同一知识点下的题目，对于 WKY 来讲，都是一样难的。而做出每一道题，老王都有其独特的奖励值。而奖励值和题目的知识点没有必然联系。

现在 WKY 同学请你帮忙，计算在老王规定的时间内，WKY 所能得到最大奖励值是多少 。

inputFormat:
输入文件包括以下内容：

第一行：

WKY 的水平值和老王的水平值。

数据保证 WKY 的水平值小于老王的水平值（哪怕它不现实），且老王的水平值是 WKY 的水平值的整数倍。

第二行：

题目的总数 $m$ 和知识点的总数 $n$。

第三行：

$n$ 个整数。第 $i$ 个整数表示老王在做第 $i$ 个知识点的题目所需的时间。

接下来有 $m$ 行数每一行包括两个整数 $p$，$q$ 。$p$ 表示该题目所属的知识点，$q$ 表示该题目对应的奖励值。

最后一行是规定的时间。

outputFormat: 输出文件只有一行，表示能到得到的最大奖励值。

hint: 对于 $100 \%$ 的数据，$1 \leq n, m \leq 100$，规定时间 $\leq 5000$。$1 \leq p \leq n$，$1 \leq q \leq 1000$。


title: [APIO2016] 最大差分

background:
## 评测方式
以下是本题评测方式，与题面不符时以这里为准。

你的代码中不应该包含 `gap.h` 库。

你的代码中需如下进行 `findGap` 和 `MinMax` 函数的声明：
```cpp
extern "C" void MinMax(long long,long long,long long*,long long*);
extern "C" long long findGap(int,int);
```

[spj 与交互库](https://www.luogu.com.cn/paste/c4olee2x)

不保证没锅，要是有锅请私信供题人然后 D 死他。

description:
有 $N$ 个严格递增的非负整数 $a_1, a_2, \dots, a_N$（$0 \leq a_1 < a_2 < \cdots < a_N \leq 10^{18}$）。你需要找出 $a_{i + 1} - a_i$（$1 \leq i \leq N - 1$）里的最大的值。

你的程序不能直接读入这个整数序列，但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节，请根据你所使用的语言，参考下面的实现细节部分。

你需要实现一个函数,该函数返回 $a_{i + 1} - a_i$（$1 \leq i \leq N - 1$）中的最大值。

## 实现细节

**本题只支持 C++（包括 cpp11，cpp14，cpp17）**。

### C/C++
你需要包含头文件 `gap.h`。

你需要实现一个函数 `findGap(T, N)`，该函数接受下面的参数，并返回一个 `long long` 类型的整数：

- $T$：子任务的编号（$1$ 或者 $2$）
- $N$：序列的长度

你的函数 `findGap` 可以调用系统提供的查询函数 `MinMax(s, t, &mn, &mx)`，该函数的前两个参数 $s$ 和 $t$ 是 `long long` 类型的整数，后两个参数 `&mn` 和 `&mx` 是 `long long` 类型的整数的指针（`mn` 和 `mx` 是 `long long` 类型的整数）。当 `MinMax(s, t, &mn, &mx)` 返回时，变量 `mn` 将会存储满足 $a_i \in [s, t]$ 中 $a_i$ 的最小值，变量 `mx` 将会存储满足 $a_i \in [s, t]$，$a_i$ 的最大值。如果区间 $[s, t]$ 中没有序列中的数，则 `mn` 和 `mx` 都将存储 $-1$。在查询时需要满足 $s \leq t$，否则程序将会终止，该测试点计为 $0$ 分。

### Pascal
你需要使用单元 `graderhelperlib`。

你需要实现一个函数 `findGap(T, N)`，该函数接受下面的参数，并返回一个 `Int64` 类型的整数：

- $T$：子任务的编号（$1$ 或者 $2$）（`Integer` 类型）
- $N$：序列的长度（`LongInt` 类型）

你的函数 `findGap` 可以调用系统提供的查询函数 `MinMax(s, t, mn, mx)`，该函数的前两个参数 $s$ 和 $t$ 是 `Int64` 类型的整数，后两个参数 `mn` 和 `mx` 是传引用方式的 `Int64` 类型的整数（过程内部对这两个变量的修改会影响到外部的对应变量的值）。当 `MinMax(s, t, mn, mx)` 执行完毕时，变量 `mn` 将会存储满足 $a_i \in [s, t]$ 中 $a_i$ 的最小值，变量 `mx` 将会存储满足 $a_i \in [s, t]$，$a_i$ 的最大值。如果区间 $[s, t]$ 中没有序列中的数，则 `mn` 和 `mx` 都将存储 $-1$。在查询时需要满足 $s \leq t$，否则程序将会终止，该测试点计为 $0$ 分。

inputFormat:
## 样例一

### C/C++

考虑 $N = 4, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 8$。

则答案应该是 $3$，可以通过下面的几组对 `MinMax` 的询问获得：

调用 `MinMax(1, 2, &mn, &mx)`，则 `mn` 和 `mx` 皆返回 $2$。

调用 `MinMax(3, 7, &mn, &mx)`，则 `mn` 返回 $3$，`mx` 返回 $6$。

调用 `MinMax(8, 9, &mn, &mx)`，则 `mn` 和 `mx` 皆返回 $8$。

### Pascal
考虑 $N = 4, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 8$。

则答案应该是 $3$，可以通过下面的几组对 `MinMax` 的询问获得：

调用 `MinMax(1, 2, mn, mx)`，则 `mn` 和 `mx` 皆返回 $2$。

调用 `MinMax(3, 7, mn, mx)`，则 `mn` 返回 $3$，`mx` 返回 $6$。

调用 `MinMax(8, 9, mn, mx)`，则 `mn` 和 `mx` 皆返回 $8$。

## 样例评测方式

样例测评系统从标准输入中读入两行。第一行包含两个整数，子任务编号 $T$，和序列长度 $N$。第二行包含 $N$ 个严格递增的非负整数。然后该程序会向标准输出中写入两行，第一行为 `findGap` 的返回值，第二行为花费 $M$ 的值。

下面的输入描述了上面的样例：

```plane
2 4
2 3 6 8
```
注意实际使用的交互库和 spj 对数据进行了加密。

hint:
## 限制与约定

对于所有的测试点，有 $2 \leq N \leq 100000$。

每一个测试点开始测试之前，$M$ 都将被初始化为 $0$。

子任务 1（$30$ 分）：每一次调用 `MinMax` 都将使 $M$ 加 $1$。为了获得所有分数，需要满足对于该子任务下的所有测试点，都有 $M \leq \frac{N + 1}{2}$。

子任务 2（$70$ 分）：定义 $k$ 为调用 `MinMax` 时，区间 $[s, t]$ 中的序列中数的数量。每次调用 `MinMax`，将使 $M$ 加上 $k + 1$。对于每一个测试点，如果 $M \leq 3N$，你将得到 70 分，否则将得到 $\dfrac{60}{\sqrt{\frac MN + 1} - 1}$ 分。你的该子任务的得分是其下所有测试点中的最低分。


title: [APIO2013] 出题人

description:
当今世界上各类程序设计竞赛层出不穷。而设计一场好比赛绝非易事，比如给题目设计测试数据就是一项挑战。一组好的测试数据需要对不同的程序有区分度：满足所有要求的程序自然应该得到满分，而那些貌似正确的程序则会在某些特殊数据上出错。

在本题中，你在比赛中的角色反转啦！作为一名久经百战的程序员，你将帮助 Happy Programmer Contest 的命题委员会设计这次比赛的测试数据。本次比赛命题委员会选择了两个图论问题，分为 $8$ 个子任务。委员会写了一些貌似可以解决这些子任务的代码。在给任务设计数据的时候，命题委员会期望其中的一些源程序能够得到满分，而另外的一些则只能得到 $0$ 分或者少许的部分分。现在你将会获得这些源程序（C, C++, Pascal 版本）。对于每个子任务，你需要去产生一组数据 $X$ 使得它能将该任务给定的 $2$ 种源程序 $A$ 和 $B$ 区分开来。更具体地说，生成的数据必须满足如下两个条件:

输入 $X$ 对于源程序 $A$ 一定不会出现超出时间限制（TLE）的问题。

输入 $X$ 一定会导致源程序 $B$ 产生超出时间限制的问题。

此外,命题委员喜欢较小规模的测试数据，希望测试数据最好能够包含不超过 $T$ 个整数。

本题中只关心源程序 $A$ 和 $B$ 是否超时，不关心是否结果正确。

命题委员会选择了单源最短路（SSSP）以及一个被称之为神秘问题（Mystery）的两个图论问题来作为比赛的题目。我们将命题委员会完成的伪代码列在了附录中，而具体的 C、C++ 和 Pascal 源程序被我们放在了下发的文件当中。

### 子任务

参见下表。表中每一行描述了一个子任务。其中前六个子任务与单源最短路相关，子任务 7,8 与神秘问题相关。每个任务所占分数见下表。

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

对于每个子任务，你的程序给出的输入 $X$ 需要能够将源程序 $A$ 和 $B$ 区分开来，这有这样你才能够得到相应的分数。具体说来，你的分数将由输入 $X$ 中数的个数决定。假设 $X$ 中包含了 $F$ 个整数，子任务的满分为 $S,T$ 是该任务的目标大小，则该测试点的分数将由下式给出:

$$S \times \min\{T / F, 1\}$$

也就是说，如果你的测试数据 $X$ 中含有不超过 $T$ 个整数，则你将得到该任务的全部得分。

你需要把你的 $8$ 个测试数据命名为 `1.txt` ~ `8.txt`。对于每个子任务 $X$，评测系统将根据如下步骤来确定你将会得到多少分:

- 如果未提交数据，则不得分；
- 若数据不满足输入格式要求，则不得分；
- 对源程序 $A$ 运行输入，若发生超时现象，则不得分；
- 对源程序 $B$ 运行输入，若发生超时现象，则按照前文所述的公式给出该测试点的分数。

题目提供的所有源代码均会维护一个计数器来统计程序的操作次数。在源程序的运行过程中，当该计数器超过了 $10^6$ 次时，那么我们认为程序运行超时。

### 问题 1：单源最短路（SSSP）

给定一个带权有向图 $G$，以及 $G$ 中的两个节点 $s$ 与 $t$，令 $p(s, t)$ 为 $G$ 中从 $s$ 至 $t$ 的最短路长度。如果 $s$ 与 $t$ 不连通，则认为 $p(s, t)=10^9$。在本题中，输入为图 $G$ 以及 $Q$ 个询问 $(s_1, t_1), (s_2, t_2), \dots, (s_Q, t_Q)$ 。输出则是对这 $Q$ 个询问的相应输出 $p(s_1, t_1), p(s_2 , t_2), \cdots, p(s_Q, t_Q)$。

### 问题 2：神秘问题

给定一个包含 $V$ 个节点 $E$ 条边的无向图 $G$，要求将所有的节点进行编号（编号范围为 $[0, X-1]$），使得所有直接相连的节点均有不同的编号。找出符合题意的最小的 $X$。

inputFormat:
### 问题 1

输入数据包含两部分，其中第一部分使用邻接表来描述带权有向图 $G$。第二部分则描述对 $G$ 的最短路径的查询。

数据第一部分的第一行包含一个整数 $V$，表示 $G$ 中点的个数，所有点的编号为 $0, 1, \cdots, V - 1$。

接下来 $V$ 行，每行描述一个点的所有边。行中的第一个整数 $n_i$ 描述了节点 $i$ 的出边数量，接下来有 $n_i$ 个整数对 $(j, w)$ 表示有一条从 $i$ 到 $j$，边权为 $w$ 的边。

数据第二部分的第一行包含一个整数 $Q$，表示询问的组数。

接下来 $Q$ 行，第 $k$ 行包含两个整数 $s_k, t_k$，为该询问对应的起点与终点位置。

同一行中任意两个相邻的整数均需要至少一个空格将他们分开。除此之外，数据还需满足如下条件:

- $0 < V \leq 300$，$n_i$ 是一个非负整数，$0 \leq j < V$，$\lvert w \rvert < 10^6$，$0 \leq \sum\limits_{i = 0}^{V-1} n_i \leq 5000$，$0 < Q \leq 10$，$0 \leq s_k < V, 0 \leq t_k < V$；
- 所有询问中的起点 $s_k$ 都不能达到任何一个负权圈。
- 对于所有的边 $(a, b)$，有 $a \neq b, 0 \leq a < V, 0 \leq b < V$，不会重复描述一条边。

### 问题 2

输入数据的第一行包含两个整数 $V$ 和 $E$。

接下来 $E$ 行,每行两个整数 $a, b$，表示 $a$ 与 $b$ 在 $G$ 中直接相连。此外,输入数据应满足如下限制条件:

- $70 < V < 1000$，$1500 < E < 10^6$；
- 对于所有的边 $(a, b)$，有 $a \neq b, 0 \leq a < V, 0 \leq b < V$，不会重复描述一条边。

outputFormat:
### 问题 1

程序将会输出 $Q$ 行，每行一个整数，表示对应的 $p(s_k , t_k)$。而在输出的最后，所有提供的程序都会给出计数器对此输入的数值。

### 问题 2

程序将在第一行输出 $X$，即最小的编号范围，接下来在第二行中给出 $V$ 个整数，依次描述节点 $0$ 至 $V - 1$ 的编号。在输出的最后，所有提供的程序都会给出计数器对此输入的数值。

hint:
**源代码见附件**。

### 附录：伪代码

接下来是我们提供的所有程序的伪代码；变量 counter 近似描述出了程序的运行时间。评测时将会使用这些伪代码的 C++ 版本来进行评测。

FloydWarshall

```cpp
// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
    for i = 0 to V-1
        for j = 0 to V-1
            increase counter by 1;
            M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
    output M[s][t];
```

OptimizedBellmanFord

```cpp
// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
    dist[s] = 0; // s is the source vertex
    loop V-1 times
        change = false;
        for each edge (u,v) in L
            increase counter by 1;
            if dist[u] + weight(u,v) < dist[v]
                dist[v] = dist[u] + weight(u,v);
                change = true;
        if change is false // this is the ’optimized’ Bellman Ford
            break from the outermost loop;
    output dist[t];
```

ModifiedDijkstra

```cpp
// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
    dist[s] = 0;
    pq.push(pair(0, s)); // pq is a priority queue
    while pq is not empty
        increase counter by 1;
        (d, u) = the top element of pq;
        remove the top element from pq;
        if (d == dist[u])
            for each edge (u,v) in L
                if (dist[u] + weight(u,v) ) < dist[v]
                    dist[v] = dist[u] + weight(u,v);
                    insert pair (dist[v], v) into the pq;
    output dist[t];
```

Gamble1

```cpp
Sets X = V;
labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE
```
Gamble2

```cpp
Sets X = V;
labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE
```

RecursiveBacktracking

```cpp
This algorithm tries X from 2 to V one by one and stops at the first valid X.
For each X, the backtracking routine label vertex 0 with 0, then for each vertex u that has been assigned a label, the backtracking routine tries to assign
the smallest possible label up to label X-1 to its neighbor v, and backtracks if necessary.
// Please check RecursiveBacktracking.cpp/pas to see
// the exact lines where the iteration counter is increased by 1
```

感谢zhouyonglong修改spj


title: 正妹吃月饼

description:
今天是中秋节。uim 带来了一堆大小不同且味道各异的月饼。

这些月饼的质量分别是 $1g,2g,4g,8g,16g$....后面一个是前面的 $2$ 倍。每种只有一个。

uim 让正妹随便吃。

正妹希望尝试尽可能多的口味，所以会吃尽可能多数量的月饼（不是重量）。而且她的确有些饿了，至少总共要吃掉 $A\text{g}$ 的月饼才能满足。

然而正妹怕长胖，所以吃月饼不能合计超过 $B\text{g}$ 。

她希望知道自己最多能吃多少个月饼

inputFormat: 共一行，包含两个数，$A,B$。

outputFormat: 正妹能吃到最多的数量。


title: [SDOI2017] 树点涂色

description:
Bob 有一棵 $n$ 个点的有根树，其中 $1$ 号点是根节点。Bob 在每个点上涂了颜色，并且每个点上的颜色不同。

定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。

Bob可能会进行这几种操作：

- `1 x` 表示把点 $x$ 到根节点的路径上所有的点染上一种没有用过的新颜色。

- `2 x y` 求 $x$ 到 $y$ 的路径的权值。

- `3 x` 在以 $x$ 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob一共会进行 $m$ 次操作

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

接下来 $n-1$ 行，每行两个数 $a,b$，表示 $a$ 与 $b$ 之间有一条边。

接下来 $m$ 行，表示操作，格式见题目描述

outputFormat:
每当出现 $2,3$ 操作，输出一行。

如果是 $2$ 操作，输出一个数表示路径的权值

如果是 $3$ 操作，输出一个数表示权值的最大值

hint:
共 $10$ 个测试点。

测试点 $1$，$1\leq n,m\leq1000$；

测试点 $2,3$，没有 $2$ 操作；

测试点 $4,5$，没有 $3$ 操作；

测试点 $6$，树的生成方式是，对于 $i(2\leq i \leq n)$，在 $1 \sim i-1$ 中随机选一个点作为 $i$ 的父节点；

测试点 $7$，$1\leq n,m\leq 5\times 10^4$；

测试点 $8$，$1\leq n \leq 5 \times 10^4$；

测试点9,10，无特殊限制

对所有数据，$1\leq n \leq 10^5$，$1\leq m \leq 10^5$。


title: 蜜蜂路线

background: 无

description:
一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房 $m$ 开始爬到蜂房 $n$，$m<n$，有多少种爬行路线？（备注：题面有误，右上角应为 $n-1$）

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

inputFormat: 输入 $m,n$ 的值

outputFormat: 爬行有多少种路线


title: [SDOI2005] 高速公路

description:
京珠高速公路目前正在建设当中。粤北地区是世界著名的“丹霞地貌”，京珠在这里必须穿过一大片复杂的山区。工程的总设计师Bonny已经规划好了公路大致的走向，而工程师们则被派往各个多山的路段，以设计这些路段的具体规划。

现在，你因为在信息学上取得的出色成就，被Bonny派往一个称为DreadfulMess的最复杂的路段，并仅仅给了你一张地图和一些数据。

地图以笛卡尔坐标系描述，其中包括这一地区的所有山峰的数据（俯视图）及两个点A、B。每座山的轮廓被假想为四边形，工程师们把这些四边形的顶点称为“测量点” ，这些四边形不会发生重叠、包含，但有可能有共用的一段边或顶点。山以外的区域被认为是平地。

你的任务是计算此路段山区的总面积，并设计一条公路，从A点起始，到B点终止。设计的原则是：公路是一条折线（即转弯点的个数是有限的）；公路可以修在平地上、沿山脚或山谷（即两座山的结合部），也可以打隧道；隧道口不能是转弯点，除非它又是测量点；修建公路的费用最小。

费用的计算：平地、沿山脚或山谷的单位修路费用为u0，各座山修隧道的单位费用为ui。

inputFormat:
第一、二行分别为A、B点坐标，整数。

第三行为u0，正整数。

第四行为山峰数n，0<=n<=50。

以下共n行，每行首先是一个正整数ui，然后是8个整数，按逆时针方向给出表示山的四边形的顶点坐标。

输入数据保证A、B两点不会在任何山的内部，四边形任意3个顶点不在同一直线上，所有的整数的绝对值不会大于1000。

坐标均以整数对的形式给出，第一个数为横坐标，第二个为纵坐标。同一行内若有多个相邻整数，则整数间以至少一个空格隔开。

outputFormat:
第一行为这个区域山的总面积。

第二行为设计公路的总长。

第三行为修建所设计公路的费用。

输出数据均保留两位小数。


title: [POI2000] 病毒

description:
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果 $\{011, 11, 00000\}$ 为病毒代码段，那么一个可能的无限长安全代码就是 $010101 \ldots$。如果 $\{01, 11, 000000\}$ 为病毒代码段，那么就不存在一个无限长的安全代码。

现在给出所有的病毒代码段，判断是否存在无限长的安全代码。

inputFormat:
第一行包括一个整数 $n$，表示病毒代码段的数目。

以下的 $n$ 行每一行都包括一个非空的 $01$ 字符串，代表一个病毒代码段。

outputFormat: 如果存在无限长的安全代码，输出 `TAK`，否则输出 `NIE`。

hint: $1 \leq n \leq 2000$，所有病毒代码段的总长度不超过 $3 \times 10^4$。


title: [SDOI2005] 动物园

description:
位于郊区的动物园很早就采用了当时先进的自动化管理设施对动物进行管理。但是由于当时的系统没有考虑 $2000$ 年问题，使得管理人员十分担心。虽然采取了很多防范措施，系统还是在世纪之交出现了一些 BUG，部分动物的笼子门自动打开了，关在里面的动物都跑出来了。

幸好动物园已经关闭，**动物不会跑出动物园**。警长 Still 接到报警后率领一支干警奔赴现场。这时动物已经跑出了笼子，所以干警们花了很多时间才控制住了局势，所有的动物都己经送到动物园的广场。但是此时有一个棘手的问题，由于系统完全崩溃，无法得知动物是从哪个笼子里面跑出来的。此时，干警们记得动物的一些行动，都是如下的形式：

第 $t$ 分钟看到某某动物在某个位置。

Still 希望通过这些零碎的信息得到动物是从哪个笼子跑出来的。

### 任务

根据给出的信息，编程求出每个动物的笼子的位置。

动物园的地形描述为一个 $n\times n$ 的网格，一个格子可以是建筑物或者平地。笼子的位置只可能在平地，动物也只在平地运动。每种动物的奔跑速度不一样，例如老虎一分钟可以跑 $5$ 个格子，猫一分钟只可以跑 $2$ 个格子等等。以下是一个例子（其中阴影部分是建筑物）：

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

**每个笼子只关一只动物，不同的笼子关不同的动物。不同的笼子可能在同一个格子里。**

inputFormat:
第一行为自然数 $n$，表示网格的边长

以下 $n$ 行为一个 $n\times n$ 的字符串矩阵，表示动物园的地形。其中 `.` 表示空地，`*` 表示建筑物。

接着一行是自然数 $p$，表示笼子的数目（同时也是动物的数目）。

以下 $p$ 行，每行两个自然数 $R,C$，表示一个笼子处于网格的第 $R$ 行，第 $C$ 列。

以下 $p$ 行，每行一个整数 $V_i$，依次表示编号为 $i$ 的动物的速度（格子/分钟），每个动物用它的编号表示。

接着一行是自然数 $r$，表示干警们提供的信息数目。

以下 $r$ 行，每行四个自然数，$t,x, y, j$，表示第 $t$ 分钟在网格的 $(x, y)$ 位置看到动物 $j$。

具体格式参照样例。

outputFormat:
输出任意一个可行解。

包括 $p$ 行，每行三个整数 $i,x,y$，表示动物 $i$ 原来在格子 $(x,y)$。

hint:
$1\leq n,p\leq 100$，$x,y\leq n$。

注：对于特定的数据可能有多解，输出任意一解即可。


title: 无尽的生命

description:
逝者如斯夫，不舍昼夜！

叶良辰认为，他的寿命是无限长的，而且每天都会进步。

叶良辰的生命的第一天，他有 $1$ 点能力值。第二天，有 $2$ 点。第 $n$ 天，就有 $n$ 点。也就是 $S_i=i$。

但是调皮的小A使用时光机，告诉他第 $x$ 天和第 $y$ 天，就可以任意交换某两天的能力值。即 $S_x\leftrightarrow S_y$。

小A玩啊玩，终于玩腻了。

叶良辰：小A你给我等着，我有 $100$ 种办法让你生不如死。除非能在 $1$ 秒钟之内告知有多少对“异常对”。也就是说，最后的能力值序列，有多少对的两天 $x,y$，其中 $x<y$，但是能力值 $S_x>S_y$？

小A：我好怕怕啊。

于是找到了你。

inputFormat:
第一行一个整数 $k$，表示小A玩了多少次时光机

接下来 $k$ 行，$x_i,y_i$，表示将 $S_{x_i}$ 与 $S_{y_i}$ 进行交换。

outputFormat: 输出共一行，表示有多少“异常对”。


title: [SDOI2005] 矩形

description:
现在我们在一个平面上画了n个矩形。每一个矩形的两边都与坐标轴相平行，且矩形定点的坐标均为整数。现我们定义满足如下性质的图形为一个块：

1.每一个矩形都是一个块；

2.如果两个块有一段公共的部分，那么这两个块就会形成一个新的块，否则这两个块就是不同的。

示例：

图1中的矩形形成了两个不同的块。图2中的矩形形成了一个块。

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

任务：

请写一个程序：

1.从文本文件PRO.IN中读入各个矩形的顶点坐标；

2.找出这些矩形中不同的块的数目；

3.把结果输出到文本文件PRO.OUT中。

inputFormat: 文本文件PRO.IN的第一行包括一个整数n，1  n  7000，为矩形的数目。以下的n行为矩形顶点的坐标。每一个矩形都是用四个整数来描述的：左下角的x坐标、左下角的y坐标、右上角的x坐标和右上角的y坐标。所有的坐标都是不大于10000的非负整数。

outputFormat: 在文本文件PRO.OUT中输出唯一的一个整数——这些矩形所形成的不同的块的数目。


title: [SDOI2005] 投递的艺术

description:
YZ住宅小区的未来规划采用了一种新方案：小区由白色的木栅栏围成，栅栏的形状将被设计为一个任意多边形，而每户的住宅就位于多边形的顶点处，多边形的内部则将建成一个优雅怡人的小区公园。

这个方案却给负责小区送报任务的投递员带来了一些麻烦，因为他希望坚持自己的送报习惯：他喜欢骑在自己的自行车上沿着一个标准的圆形路线投送报纸，每当看到自己的右手方向有一户住宅时，他就会将报纸投过去，而且最令他骄傲的是，无论距离远近，他投出的报纸总是准确地落在住户的门前。他的这种极具艺术感的服务方式也正是住户们最感欣赏的地方。

但遗憾的是，他分辨不出每户住宅之间的区别，也记不住每家订了哪些报纸，邮局按照住宅在多边形上的次序把每户的报纸交给他，他就按照这种次序把每户的报纸投送出去。所以图一中的方案是不成立的，因为住户3拿到的总是住户2的报纸，而住户2拿到的报纸却是住户3的。图二中画出了两种可行的方案。

你的任务就是找出所有满足上述要求的投递路线的圆心（这些圆心的坐标应当是整数）。

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

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

inputFormat: 输入文件名为Polygon.in。文件第1行是4个整数Xmin、Xmax、Ymin、Ymax，表示圆心坐标的范围，第2行是一个正整数n(n100)，表示多边形的顶点数，从第3行至第n+2行是每个顶点的坐标(x,y)，所有坐标值均为整数，坐标的绝对值不大于1000，顶点按顺时针排序。

outputFormat: 输出文件名为Polygon.out。文件中共m行（m为你求出的圆心的个数），每行两个整数(x,y)，表示圆心的坐标，坐标应按y递增的次序输出，如果y相等的，应按x递增的次序。


title: [SDOI2005] 遗传代码

description:
抽象的 primitivus（Primitivus 循环）的遗传代码是一系列自然数 $K=(A_1,A_2,\cdots,A_n)$。我们所说的 primitivus 的特征是一个数对 $(l,r)$，表示 $l,r$ 在 $A$ 中**连续出现**。即存在一个 $i$，使得 $A_i=l$，$A_{i+1}=r$。在 primitivus 的遗传代码中没有 $(p,p)$ 特征。

### 任务

写一个程序：

1. 从文本文件读特征列表；
2. 计算所给特征的最短遗传代码长度；
3. 输出答案。

inputFormat:
第一行有一个正整数 $n$，它是 primitivus 的不同特征的数量。

接下来 $n$ 行，每一行中有两个被空格号隔开的数字 $l$ 和 $r$。数字对 $(l,r)$ 是 primitivus 的一个特征。在输入文件中，特征并不重复。

outputFormat: 共一行一个整数，为 primitivus 最短遗传代码的长度。

hint:
### 样例解释

以下是一种符合题意的最短的遗传代码。它符合输入数据中给出的所有的特征：

$(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6) $

### 数据范围及约定

对于全部数据，满足 $0 \le l \le 1000$，$0 \le  r \le  1000$。


title: [SDOI2005] 屠龙传说-屠龙枪卷

description:
先知看到修玛取回的药草，满意地点了点头。

他对修玛说：“跟我来”。

修玛顺从地跟着先知走到了他的房间里。先知的房间很大，四周满是书架，整整齐齐地摆放着一排排书籍。房间中间的圆桌上摆放着一个巨大的水晶球，它发出的荧光照亮了整个房间。

先知走到一排书架前，从中抽出一本薄薄的书来。这本书看起来十分古老，纸张都变成了黄色，有的地方已经发黑。修玛想，这本书的历史大概有好几百年了吧。

先知示意修玛坐下，他翻开手中的书，对修玛说道：“我已经研究这本书很久了。它是用一种古老的文字写成的，记载了一个十分古老的传说。书中提到，普通的武器是无法伤害巨龙的，只有诸神合力锻造的屠龙枪才能消灭它。为了防止屠龙枪被滥用，神把它封印在卡基思山上，只有拥有超人的勇气、力量和智慧的人才能解开这个封印。千百年来，很多人都想得到屠龙枪的力量，然而从没有人成功过。我查阅了所有有关屠龙枪的记载，悉心地研究那些资料，得知屠龙枪被封印在山顶的神殿中，而要解开这道封印，就必须把神殿中的一块巨大的圆石推到神殿祭坛的中心，然后念出解开封印的咒语。”

修玛问道：“那句咒语应该已经失传了吧？”“不，恰恰相反。”先知说，“这句咒语一直记载在这本书中，并被完好地保存下来。”“那么，剩下的只是把圆石推到祭坛的中心了。”修玛自信地笑了。然而先知却摇了摇头，“不，修玛，事情没有你想象的那么简单。爬上卡基思山就不是一件容易的事。它高耸入云，四周都是光秃秃的石壁，几乎没有落脚的地方。只有真正的勇士才能爬得上去。那块圆石也不是那么容易就能推动的，非得有超常的力量不可。这些东西，修玛你都有。但如果仅仅只有这些，那么屠龙枪早已被人拿到手了。书中不是说了么，要有勇气、力量和智慧。智慧才是真正的关键。如果在固定时间内不能把那块圆石推到祭坛的中心，那么圆石便会自动滚回原处，同时推石的人将永远无法再次推动这块圆石。而且不管你用多大力气推，这块圆石都不可能滚动得像你希望的那样快，我估计只有按照最短路线去推这块圆石，才能在固定时间内把它推到祭坛中心。神殿中又有着大大小小的石柱，有些石柱与石柱之间的空隙很小，根本就推不过去。正因为这种种困难，才没有人能够从神殿中取走屠龙枪。”

修玛沉默了一会儿，说：“不管如何，我也要去试一试。如果我不能拿到屠龙枪，就没有人能够拿到它了。”

先知点了点头，说：“去吧，修玛。记住，用你的智慧。”

修玛骑马奔驰了十天十夜，终于来到了卡基思山脚下。正如先知所说的那样，这座山根本就没有路可以上去，甚至找不到可以落脚的地方。然而修玛凭着他的勇气以及熟练的技巧，爬上了山顶。

当他走进神殿，一眼就看到了那块巨大的圆石。修玛该怎么做，才能把圆石推到祭坛的中心呢？

### 任务

你的任务是计算出把圆石推到祭坛中心的最短路线长度。

所谓推到祭坛中心是指圆石的中心与祭坛中心重合。

圆石中心的初始位置以及祭坛中心的位置是已知的。圆石半径为 $R$，它可以朝着任意方向滚动。洞中所有石柱均为正四棱柱，大小不一。

在推动圆石的过程中，要求圆石中心与所有石柱的距离均不小于 $R$，否则圆石将被石柱阻挡而不能继续滚动。

inputFormat:
第一行包含了五个实数，依次表示圆石中心的初始位置的 $x$ 坐标、$y$ 坐标、圆石半径 $R$、祭坛中心的位置 $(x,y)$。

第二行包含一个整数 $n$，表示神殿中石柱的数目。

接下来 $n$ 行，每行包含三个实数 $(x_i,y_i,r_i)$，给出了一根石柱的信息，依次表示第 $i$ 根石柱左下角 $x$ 坐标、$y$ 坐标以及该石柱的边长。

数据输入所有实数均精确到 $2$ 位小数，范围在 $0$ 到 $1000$ 之内。

outputFormat:
输出仅包含一个实数，表示把圆石推到祭坛中心的最短路线长度，输出结果保留到两位小数。

若不存在一条把圆石推到祭坛中心的路，输出 `0.00`。

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

对于全部数据，满足 $0\le n\le 20$。

---

修玛思索良久，果断地走到圆石旁边，用力推动这块巨石。圆石在修玛的推动下，缓缓地滚动起来。修玛时不时地调整着推动的角度，以使巨石朝着自己希望的方向滚动。终于，“卡嗒”的一声，圆石安安稳稳地滚到了祭坛的中心。一束光从神殿顶上直射而下，笼罩了整个祭坛。修玛对着祭坛，大声地念出了解开封印的咒语。顿时，祭坛开始颤动，中间的圆石也随着摇摆不定。突然间，整块圆石完全爆裂开来，在祭坛的中心，出现了一柄长枪。枪身上闪烁着神圣的光芒，令人惊羡不已。修玛走上前去，拔起了这柄枪。他感到一股强大的力量从手上传了过来。修玛随手把枪一挥，只听得“哗啦”一声，一根巨大的石柱应声四分五裂了。修玛又惊又喜，他知道这一定就是屠龙枪。


title: [SDOI2006] 最短距离

description:
一种 EDIT 字母编辑器，它的功能是可以通过不同的变换操作可以把一个源串 $X[l\cdots m]$ 变换为新的目标串 $Y[1\cdots n]$。EDIT 提供的变换操作有：

- 删除源串首个字符（delete）；
- 替换源串首个字符放到目标串末尾（replace）。replace 操作可以替换为与原来相同的字符；
- 移动源串首个字符放到目标串末尾（copy）；
- 向目标串插入单个字符（insert）；
- 交换源串中的两个相邻字符，并移动到目标串末尾中去（twiddle）；
- 在完成其它所有操作之后，源串中余下的全部后缀就可用删至行末的操作删除（kill）。

例如，将源 `algorithm` 转换成目标串 `altruistic` 的一种方法是采取下面的操作序列：

| 操作 | 目标串 | 原串 |
| :----------: | :----------: | :----------: |
| 初始 | （空） | `algorithm` |
| `copy a` | `a` | `lgorithm` |
| `copy l` | `al` | `gorithm` |
| `replace g to t` | `alt` | `orithm` |
| `delete o` | `alt` | `rithm` |
| `copy r` | `altr` | `ithm` |
| `insert u` | `altru` | `ithm` |
| `insert i` | `altrui` | `ithm` |
| `insert s` | `altruis` | `ithm` |
| `twiddle it into ti` | `altruisti` | `hm` |
| `replace h to c` | `altruistic` | `m` |
| `kill` | `altruistic` | （空） |

要达到这个结果还可能有其它一些操作序列。

操作 delete、replace、copy、insert、twiddle 和kill中每一个都有一个相联系的代价 cost。例如：

```plain
cost(delete) =3;
cost(replace)=6;
cost(copy)   =5;
cost(insert) =4;
cost(twiddle)=4;
cost(kill) = 被删除的串长 * cost(delete) - 1;
```

一个给定的操作序列的代价为序列中各操作代价之和。
例如上述操作序列的代价为

$$\begin{aligned}&3\times \mathrm{cost}(\mathtt{copy})+2\times \mathrm{cost}(\mathtt{replace})+\mathrm{cost}(\mathtt{delete})+3\times \mathrm{cost}(\mathtt{insert}) \\ &+\mathrm{cost}(\mathtt{twiddle}) +\mathrm{cost}(\mathtt{kill}) \\
=\ & 3\times 5+2\times 6+3+3\times 4+4+1\times 3-1\\
=\ &48\end{aligned}$$

**编程任务**

给定两个序列 $X[1\cdots m],Y[1\cdots n]$ 和一些操作代价集合，$X$ 到 $Y$ 的最短距离为将 $X$ 转化为 $Y$ 的最小的转换序列的代价。请给出一个算法来找出 $X[1\cdots m]$ 至 $Y[1\cdots n]$ 的最短距离。

inputFormat:
第一行：源序列 $X[1\cdots m]$。

第二行：目标序列 $Y[1\cdots n]$。

第三行：$5$ 个正整数，分别是：delete、replace、copy、insert、twiddle 的代价。

outputFormat: 一行一个整数，表示 $X$ 到 $Y$ 的最短距离（最小代价和）。

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

对于全部数据，满足 $1\le n,m\le 200$，且所有代价均为不大于 $100$ 的非负整数。


title: [SCOI2008] 城堡 - 数据加强版

background: [原题弱化版](https://www.luogu.com.cn/problem/P2538)

description:
在一个国家里，有 $n$ 个城市（编号为 $0$ 到 $n-1$）。这些城市之间有 $n$ 条双向道路相连（编号为 $0$ 到 $n-1$），其中编号为 $i$ 的道路连接了城市 $i$ 和城市 $r_i$（一条道路可以连接一个城市和它自身），长度为 $d_i$。$n$ 个城市中有 $m$ 个拥有自己城堡，可以抵御敌人侵略。如果没有城堡的城市遭受攻击，则离它最近的城堡将派兵前往救援。

你的任务是在不超过 $k$ 个没有城堡的城市中建立城堡，使得所有城市中“离最近城堡的距离”的最大值尽量小。换句话说，若令 $dist(c)$ 表示城市 $c$ 的最近城堡离它的距离，则你的任务是让 $\max\{dist(c)\}$ 尽量小。

输入数据保证存在方案使得对于每个城市，至少有一个城堡能够到达。

inputFormat: 输入第一行为三个正整数 $n, m, k$。第二行包含 $n$ 个整数 $r_0,r_1,\ldots,r_{n-1}$。第三行包含 $n$ 个整数 $d_0,d_1,\ldots,d_{n-1}$。第四行包含 $m$ 个各不相同的 $0$ 到 $n-1$ 之间的整数，分别为 $m$ 个城堡所在的城市编号。

outputFormat: 输出仅一行，包含一个整数，即 $\max\{dist(c)\}$ 的最小值。

hint:
$100\%$ 的数据满足：$1\leq d_i\leq 10^5$，$0\leq m\leq n-k$。

- Subtask 1：$2 \leq n \leq 3000$。
- Subtask 2：$2 \leq n \leq 10^5$。


title: [SDOI2006] 线性方程组

description:
已知 $n$ 元线性一次方程组。

$$ \begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}$$

请根据输入的数据，编程输出方程组的解的情况。

inputFormat:
第一行输入未知数的个数 $n$。
接下来 $n$ 行，每行 $n + 1$ 个整数，表示每一个方程的系数及方程右边的值。

outputFormat:
如果有唯一解，则输出解。你的结果被认为正确，当且仅当对于每一个 $x_i$ 而言结果值与标准答案值的绝对误差或者相对误差不超过 $0.01$。

如果方程组无解输出 $-1$；
如果有无穷多实数解，输出 $0$；

hint:
【数据范围】
对于 $100\%$ 的数据，$1 \le n \le 50$。对于 $\forall 1\le i, j \le n$，有 $|a_{i, j}| \le 100$，$|b_i| \le 300$。


title: [SDOI2006] 二进制方程

description:
一个形如：

X1X2…Xn=Y1Y2..Ym

的等式称为二进制方程。

在二进制方程的两边：Xi和Yj （1<=i<=n；1<=j<=m）是二进制数字（0、1）或者一个变量（小写字母）。每个变量都是一个有固定长度的二进制代码，他可以在等式中取代变量的位置，称这个长度为变量的长度。为了解一个二进制方程，需要给其中的变量赋予适当的二进制代码，使得我们用他们替代等式中的相应的变量后（等式的两边都变成二进制代码），这个等式成立。

编程任务：

对于每一个给出的方程，计算一共有多少组解。已知变量最多有26个（26个英文小写字母），且等式的每一端的数字和变量的长度之和不超过10000。

inputFormat:
第一行：k（k<=26,变量的个数，规定使用小写英文字母中的前k个字母作为变量，如k=5，则变量a,b,c,d,e）。

第二行：k个正整数，中间用一个空格隔开，依次代表k个变量的长度。

第三行：等式左边的表达式。

第四行：等式右边的表达式。

outputFormat: 等式中出现的变量共有多少组解。

hint:
样例一：4组解

1 、a=1001； b=00

2、 a=1011； b=01

3、 a=1101； b=10

4、 a=1111； b=11）

样例二：K=5，变量：a,b,c,d,e。长度分别为：4 2 4 4 2。等式是：1bad1= acbe

输出16，即变量a,b,c,d,e共有16组解。


title: [SDOI2006] 仓库管理员的烦恼

description:
仓库管理员M最近一直很烦恼，因为他的上司给了他一个艰难的任务：让他尽快想出一种合理的方案，把公司的仓库整理好。

已知公司共有n个仓库和n种货物，由于公司进货时没能很好的归好类，使得大部分的仓库里面同时装有多种货物，这就给搬运工作人员搬运货物时带来了很多的麻烦。

仓库管理员M的任务就是设计一种合理的方案，把仓库里面的货物重新整理，把相同的货物放到同一个仓库，以便于日后的管理，在整理过程中肯定需要把某些货物从一个仓库搬运到另一个仓库，已知每一次搬运货物所付出的代价等于搬运该货物的重量。

编程任务：

请你帮助仓库管理员M设计搬运方案，使得把所有的货物归好类：使每种货物各自占用一个仓库，或者说每个仓库里只能放一种货物。同时要求搬运货物时所付出的所有的总的代价最小。

inputFormat:
第一行为n (1 <= n <= 150)，仓库的数量。

以下为仓库货物的情况。第i+1行依次为第i个仓库中n种货物的数量x(0 <= x <= 100)。

outputFormat: 把所有的货物按要求整理好所需的总的最小代价。

hint: 样例说明：方案是：第1种货物放到仓库2中；第2种货物放到仓库3中；第3种货物放到仓库4中；第4种货物放到仓库1中


title: [SDOI2006] 保安站岗

description:
五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。

已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。

一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。

编程任务：

请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

inputFormat:
第 $1$ 行 $n$，表示树中结点的数目。

第 $2$ 行至第 $n+1$ 行，每行描述每个通道端点的信息，依次为：该结点标号 $i$（$0<i \le n$），在该结点安置保安所需的经费 $k$（$ \le 10000$），该边的儿子数 $m$，接下来 $m$ 个数，分别是这个节点的 $m$ 个儿子的标号 $r_1,r_2,\cdots, r_m$。

对于一个 $n$（$0<n \le 1500$）个结点的树，结点标号在 $1$ 到 $n$ 之间，且标号不重复。

outputFormat: 输出一行一个整数，表示最少的经费。

hint:
### 样例解释

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

在结点 $2,3,4$ 安置 $3$ 个保安能看守所有的 $6$ 个结点，需要的经费最小：$25$。


title: [SDOI2007] 立体分割

description:
Ghy收了 $n$ 个小弟,如 Psf、Hf、Csr、Ll……也当然包括你啊。（原文如此……）

可是身为大哥的他从来不像小弟索要什么，反而经常给小弟分发礼物。

一天他得到了 $1$ 个长方体形状的蛋糕。但是Ghy并不喜欢吃蛋糕，所以他要把蛋糕全部分给小弟们。Ghy认为所有小弟是平等的，所以找来小弟你，让你把这个蛋糕分成 $n$个大小和形状都相等的长方体小蛋糕（即全等的小蛋糕）。

我们把蛋糕搬到一个三维坐标系里，以它的一个顶点 $O$ 为坐标原点 $(0,0,0)$。另一个与 $O$ 点相对的顶点(就是离 $O$ 点最远的点)的坐标 $(x,y,z)$。其实 $x,y,z$ 就表示了长方体的长、宽、高。

inputFormat: 四个正整数，$x,y,z,n$。意义如题目所述。

outputFormat: $N$ 行，每行 $6$ 个实数，表示分割成的全等长方体小蛋糕的两相对顶点坐标，先输出第一个顶点的坐标 $x_1,y_1,z_1$，然后是 $x_2,y_2,z_2$，误差不超过 $10^{-9}$。（可以任意顺序输出小蛋糕坐标，且相对顶点任取一组输出）。

hint:
### 样例解释（2023.9.29 管理员补充）

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

### 数据范围及约定

对于 $100\%$ 的数据，$1\leq x,y,z,n\leq 1000$，$x,y,z$ 为整数。


title: [SDOI2007] 科比的比赛

description:
NBA球星云集，谁是最厉害的呢？没有定论。

Nba总裁大卫\*斯特恩最近闲得无聊，决定举办一场球员单挑大赛。

比赛是这样的:首先，我们给每人都打上个分数，表示了每个人的整体能力。然后让每个参赛队员都打n场比赛，首先看谁赢得最多，然后看谁打赢的人的能力值的和最大。

本人一向支持科比(我不支持),当然希望他赢。现在让我们和科比一起去赢得这场比赛吧！！

(科比照片一张)

假设总共比赛有m+1个人参加，告诉你科比和另外m个人的比赛的胜利可能性，你的任务就是求出在科比赢了的所有比赛的可能性最大的前提下(误差不超过1e-10)，科必打赢的人的最大能力值的和是多少？当然当一个人被你打败，他就不会再参加比赛了。

这里需要注意的是，科比能打赢其他人的可能性在不同场次是不同的。比如在比赛前期科比的手感不太好，对抗在内线称霸的人因为无法发挥外线的实力，而难以得分(接奥尼儿图一张)

中期时别人手感变好，状态起来，有实力的人会给科比制造很大的麻烦(接韦德图一张)

后期时消耗太多体力，对自己的命中率下降，难以发挥正常水平，所以对抗体力好的球员时占劣势(后接纳什图一张)

现在给你每场比赛科比对每个参赛者的获胜可能性，和每个人的能力值，帮助科比赢得比赛吧。

inputFormat:
第一行n,m(1<=n<<=10,n<=m<=100000),意义如题所述

接下来一行m个整数表示其他m个人的能力值si(1<=si<=100)

接下来是1个n\*m的矩阵，描述在每场碰到每个人的获胜可能vij(0<=vij<=1)

outputFormat:
第一行输出最大获胜可能性

第二行输出最大能力值和

Special Judge


title: [SDOI2008] 递归数列

description:
一个由自然数组成的数列按下式定义：

对于 $i \le k$：$a_{i}= b_{i}$。

对于 $i > k$：$a_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}$。

其中 $b_{1\dots k}$ 和 $c_{1\dots k}$ 是给定的自然数。

写一个程序，给定自然数 $m \le n$，计算 $\left( \sum_{i=m}^{n}{a_{i}} \right) \bmod p$。

inputFormat:
第一行一个自然数 $k$。

第二行 $k$ 个自然数 $b_{1},b_{2},\dots,b_{k}$。

第三行 $k$ 个自然数 $c_{1},c_{2},\dots,c_{k}$。

第四行三个自然数 $m,n,p$。

outputFormat: 一行一个正整数，表示 $\sum_{i=m}^{n}{a_{i}} \mod p$ 的值。


title: [SDOI2007] 游戏

description:
小木木和小凳子是两个聪明的孩子，他们五岁的时候就开始学习英语了。

英语老师教他们玩一个很简单的游戏。老师给他们一张全小写并无特殊符号的英语单词表，单词表如下：

ab
arc
arco
bar
bran
carbon
carbons

cobra
crab
crayon
narc
然后让他们从单词表里找词语接龙。接龙的规则如下:

1 前一个单词拥有的所有字母，在后一个单词里必须出现，而且字母出现次数不少于前一单词。

2 后一个单词的长度比前一个单词的长度恰好多1

对于以上例子，一合法的接龙为:

ab
bar
crab
cobra
carbon
carbons

他们之中，谁接龙的长度长，谁就赢了。小木木肯定不想输，所以找到你，放肆撒娇，导致你因为不想再被打扰而帮他了。至于小凳子呢？？说不定找郭大牛去了。嘿嘿，你和郭大牛的编程比赛？？加油吧！！！

outputFormat:
第一行，输出最大长度ans

接下来的ans行，每行输出一个字符串代表你的方案。


title: [SDOI2008] Sandy 的卡片

description:
Sandy 和 Sue 都热衷于收集干脆面中的卡片。

然而，Sue 收集卡片是因为卡片上漂亮的人物形象，而 Sandy 则是为了积攒卡片兑换超炫的人物模型。

每一张卡片都由一些数字进行标记，第 $i$ 张卡片的序列长度为 $M_i$，要想兑换人物模型，首先必须要集够 $N$ 张卡片，对于这 $N$ 张卡片，如果他们都有一个相同的子串长度为 $k$，则可以兑换一个等级为 $k$ 的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。

Sandy 的卡片数远远小于要求的 $N$，于是 Sue 决定在 Sandy 的生日将自己的卡片送给 Sandy，在 Sue 的帮助下，Sandy 终于集够了 $N$ 张卡片，但是，Sandy 并不清楚他可以兑换到哪个等级的人物模型，现在，请你帮助 Sandy 和 Sue，看看他们最高能够得到哪个等级的人物模型。

inputFormat:
第一行为一个数 $N$，表示可以兑换人物模型最少需要的卡片数，即 Sandy 现在有的卡片数。

第 $i+1$ 行到第 $i+N$ 行每行第一个数为第 $i$ 张卡片序列的长度 $M_i$，之后 $j+1$ 到 $j+1+M_i$ 个数，用空格分隔，分别表示序列中的第 $j$ 个数。

outputFormat: 一个数 $k$，表示可以获得的最高等级。

hint:
$30\%$ 的数据保证 $n\le50$

$100\%$ 的数据保证 $n\le1000,M\le1000,2\le M_i\le101$

update：题面上数据范围 $M_i$ 和 $M$ 的范围其实是一个东西… 真实数据范围: $40\le n\le1000,2\le M_i\le101$,字符串中的每个数字的大小范围为 $[0,1864]$。


title: [SDOI2008] 郁闷的小 J

description:
小 J 是国家图书馆的一位图书管理员，他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳，但是由于这个书架十分巨大，所以他的工作效率总是很低，以致他面临着被解雇的危险，这也正是他所郁闷的。

具体说来，书架由 $N$ 个书位组成，编号从 $1$ 到 $N$。每个书位放着一本书，每本书有一个特定的编码。

小 J 的工作有两类：

1. 图书馆经常购置新书，而书架任意时刻都是满的，所以只得将某位置的书拿掉并换成新购的书。

2. 小 J 需要回答顾客的查询，顾客会询问某一段连续的书位中某一特定编码的书有多少本。

例如，共 $5$ 个书位，开始时书位上的书编码为 $1, 2, 3, 4, 5$。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$2$”的书共多少本，得到的回答为：$1$。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$1$”的书共多少本，得到的回答为：$1$。

此时，图书馆购进一本编码为“$1$”的书，并将它放到 $2$ 号书位。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$2$”的书共多少本，得到的回答为：$0$。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$1$”的书共多少本，得到的回答为：$2$。

……

你的任务是写一个程序来回答每个顾客的询问。

inputFormat:
第一行两个整数 $N, M$，表示一共 $N$ 个书位，$M$ 个操作。

接下来一行共 $N$ 个整数数 $A_1, A_2, \ldots , A_N$，$A_i$ 表示开始时位置 $i$ 上的书的编码。

接下来 $M$ 行，每行表示一次操作，每行开头一个字符。

若字符为 `C`，表示图书馆购进新书，后接两个整数 $A, P$（$1 \le A \le N$），表示这本书被放在位置 $A$ 上，以及这本书的编码为 $P$。

若字符为 `Q`，表示一个顾客的查询，后接三个整数 $A, B, K$（$1 \le A \le B \le N$），表示查询从第 $A$ 书位到第 $B$ 书位（包含 $A$ 和 $B$）中编码为 $K$ 的书共多少本。

outputFormat: 对每一个顾客的查询，输出一个整数，表示顾客所要查询的结果。


title: [SDOI2008] 山贼集团

description:
某山贼集团在绿荫村拥有强大的势力。整个绿荫村由 $n$ 个连通的小村落组成，并且保证对于每两个小村落有且仅有一条简单路径相连。将小村落从 $1$ 至 $n$ 编号，山贼集团的总部设在编号为 $1$ 的小村落中。

山贼集团除了老大坐镇总部以外，其他的 $p$ 个部门希望在村落的其他地方（洛谷注：其实也包括总部）建立分部。$p$ 个分部可以在同一个小村落中建设，也可以分别建设在不同的小村落中，在不同的村落建设不同的分部需要花费不同的费用。

每个分部到总部的路径称为这个部门的管辖范围，于是这 $p$ 个分部的管辖范围可能重叠，或者完全相同。当多个分部管辖同一个村落时，他们之间可能发生矛盾，从而损失一部分利益，也可能相互合作，从而获取一部分利益。

请注意，如果相同的分部同时管辖多个村落，那么对于每个村落，都会计算一次收益损失/获取。

现在请你编写一个程序，确定 $p$ 个分部的位置，使得山贼集团能够获得最大的收益。

inputFormat:
输入的第一行有两个整数，分别代表村落数 $n$ 和山贼集团部门数量 $p$。

第 $2$ 到第 $n$ 行，每行有两个整数 $x, y$，代表存在一条连接村落 $x$ 和村落 $y$ 的道路。

第 $(n + 1)$ 到第 $2n$ 行，每行 $p$ 个整数，第 $(i + n)$ 行的第 $j$ 个整数代表在第 $i$ 个村落建设第 $j$ 个部门的花费 $a_{i, j}$。

第 $(2n + 1)$ 行有一个整数，代表集团间相互影响利益的信息条数 $t$。

第 $(2n + 2)$ 行到第 $(2n + t + 1)$ 行，每行首先有一个整数 $v$，若 $v$ 为正，则表示会获得额外的收益，$v$ 为负则表示会有损失。然后有一个整数 $c$，代表涉及分部的数量。接下来有 $c$ 个整数，分别代表涉及的分部 $x_i$。本条信息的含义为若这 $c$ 个分部同时管辖某个小村落（可能同时存在其他分部管辖该村落），则会产生额外收益或损失，其数值大小为 $|v|$。

outputFormat: 输出一行一个整数代表最大的收益。

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

在 $2$ 号节点建立 $1$ 号分部，花费为 $1$，则分部集合 $\{1\}$ 可以管辖 $1, 2$ 两个节点，根据第一条信息，该集合每管辖一个节点会产生 $3$ 的收益，因此总共产生了 $2 \times 3 = 6$ 的收益，减去建立分部的花费，最大的收益为 $6 - 1 = 5$。可以证明不存在更优的方案。

#### 数据规模与约定

对于 $40\%$ 的数据，保证 $1 \leq p \leq 6$。

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

- $1 \leq p \leq 12$，$1 \leq n \leq 100$。
- $1 \leq s,t \leq n$，$1 \leq a_{i, j} \leq 10^8$。
- $1 \leq t \leq 2^p$，$1 \leq |v| \leq 10^8$，$1 \leq c \leq p$，$1 \leq x_i \leq p$ 且 $x_i$ 互不相同。
- 答案的绝对值不超过 $10^8$。


title: [SDOI2008] Sue 的小球

description:
Sue 和 Sandy 最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue 有一支轻便小巧的小船。然而，Sue 的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue 有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue 要想得到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但这并不影响 Sue 的兴趣，因为每一个彩蛋都是不同的，Sue 希望收集到所有的彩蛋。

然而 Sandy 就没有 Sue 那么浪漫了，Sandy 希望得到尽可能多的分数，为了解决这个问题，他先将这个游戏抽象成了如下模型：

将大海近似的看做 $x$ 轴，以 Sue 所在的初始位置作为坐标原点建立一个竖直的平面直角坐标系。

一开始空中有 $N$ 个彩蛋，对于第 $i$ 个彩蛋，他的初始位置用整数坐标 $(x_{i}, y_{i})$ 表示，游戏开始后，它匀速沿 $y$ 轴负方向下落,速度为 $v_{i}$ 单位距离/单位时间。Sue 的初始位置为 $(x_{0}, 0)$，Sue 可以沿 $x$ 轴的正方向或负方向移动，Sue 的移动速度是 $1$ 单位距离/单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋的 $y$ 坐标的千分之一。

现在，Sue 和 Sandy 请你来帮忙，为了满足 Sue 和 Sandy 各自的目标，你决定在收集到所有彩蛋的基础上，得到的分数最高。

inputFormat:
第一行为两个整数 $N$, $x_{0}$ 用一个空格分隔，表示彩蛋个数与 Sue 的初始位置。

第二行为 $N$ 个整数 $x_{i}$，每两个数用一个空格分隔，第 $i$ 个数表示第 $i$ 个彩蛋的初始横坐标。

第三行为 $N$ 个整数 $y_{i}$，每两个数用一个空格分隔，第 $i$ 个数表示第 $i$ 个彩蛋的初始纵坐标。

第四行为 $N$ 个整数 $v_{i}$，每两个数用一个空格分隔，第 $i$ 个数表示第 $i$ 个彩蛋匀速沿 $y$ 轴负方向下落的的速度。

outputFormat: 一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。


title: [SDOI2009] 最优图像

background: 小 E 在好友小 W 的家中发现一幅神奇的图画，对此颇有兴趣。

description:
这幅画可以被看做一个包含 $n \times m$ 个像素的黑白图像，为了方便起见，我们用 $0$ 表示白色像素，$1$ 表示黑色像素。小 E 认为这幅图画暗藏玄机，因此他记录下了这幅图像中每行、每列的黑色像素数量，以回去慢慢研究其中的奥妙。

有一天，小 W 不慎将图画打湿，原本的图像已经很难分辨。他十分着急，于是找来小 E，希望共同还原这幅图画。根据打湿后的图画，他们无法确定真正的图像，然而可以推测出每个像素原本是黑色像素的概率 $p_{i,j}\%$。那么，一个完整的图像的出现概率就可以定义为:

$$\prod\limits_{i = 1}^n \prod\limits_{j = 1}^{m} p_{i, j}\% \times [s_{i, j} = 1]$$

其中 $s_{i,j}$ 表示在还原后的图像中，像素是白色($0$)还是黑色($1$)，$[s_{i, j} = 1]$ 表示若 $s_{i, j} = 1$，则该表达式的值为 $1$，否则为 $0$。换句话说，一个完整图像出现概率就等于其所有黑色像素的出现概率之积。显然，图像的黑色像素不能包含概率为 $0$ 的像素。

然而，小 E 对此也无能为力。因此他们找到了会编程的小 F，也就是你，请你根据以上信息，告诉他们最有可能是原始图像的答案是什么。

inputFormat:
第一行是两个整数 $n, m$，表示图像大小。

第 $2$ 到第 $(n + 1)$ 行，每行 $m$ 个整数，第 $(i + 1)$ 行的第 $j$ 个整数 $p_{i, j}$ 表示第 $i$ 行第 $j$ 列的像素是黑色的概率。

接下来一行有 $n$ 个整数，第  $i$ 个整数 $a_i$ 表示第 $i$ 行中黑色像素的个数。

接下来一行有 $m$ 个整数，第 $i$ 个整数 $b_i$ 表示第 $i$ 列中黑色像素的个数。

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

输出 $n$ 行每行一个长度为 $m$ 的只含字符 `0` 和字符 `1` 的字符串，表示答案。

输入数据保证至少存在一个可能的图像。如果有多种最优图像，任意输出一种即可。

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

共有两种可能的图像：

```plain
01
10
```
```plain
10
01
```
前者的出现概率是 $0.1×0.2=0.02$，后者的出现概率是 $0.9×0.8=0.72$，故后者是最优图像。

---

#### 数据规模与约定

- 对于 $20\%$ 的数据，保证 $n, m \leq 5$。
- 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 100$，$0 \leq p_{i, j} \leq 100$，$0 \leq a_i \leq m$，$0 \leq b_i \leq n$。

---

感谢 @[test12345](https://www.luogu.com.cn/user/23118) 提供 spj。


title: [SDOI2009] 地图复原

description:
很久以前，有一个传说中的“EWF”部族，他们世代生活在一个N×M的矩形大地上。虽然，生活的地区有高山、有沼泽，但通过勤劳勇敢，渐渐地，他们在自己的地盘上修筑了一条回路。

后来，“EWF”部族神秘地消失了。不过，考古学家在那片他们曾经生活过的地方找到了一份地图。地图是N×M的矩阵，左上角的坐标为(0, 0)，右下角的坐标为(N, M)。矩阵中的每个格子，表示高山、沼泽、平地、房屋或是道路其中之一。如果一个格子表示道路，那么经过这个格子的道路要么是直走，要么是拐弯。如下图，左边2幅表示直走格子的，右边4幅表示需要拐弯的格子。一个表示道路的格子只能表示下列情况之一。

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

可是，由于地图的年代久远，考古学家虽然能分清一个格子代表的地形，可对于道路的标记，考古学家们只能分清这一格是表示直走的还是拐弯的。现在，他们求助于你，希望你能帮助他们复原这份“EWF”部族的地图。

inputFormat:
输入文件recover.in的第一行包含两个用空格分隔的正整数N和M，分别表示地图的高和长。

接下来一个N行M列的矩阵描述地图，矩阵中没有多余字符。

大写“S”表示直走的道路，大写“T”表示拐弯的道路，点“.”表示高山、沼泽、平地和房屋。

outputFormat:
输出文件recover.out包含2N-1行，每行2M-1个字符，描述了这条回路。

所有第2i+1行的2j+1个字符为小写字母o，表示了矩阵的第i行第j列的格子的中心(i, j)。

若回路包含了(i, j)到(i, j+1)或(i, j+1)到(i, j)的一条路径，则第2i+1行的第2j+2个字符为减号“-”（ASCII码为45）；

若回路包含了(i, j)到(i+1, j)或(i+1, j)到(i, j)的一条路径，则第2i+2行的第2j+1个字符为竖线“|”（ASCII码为124）。

其它以上未说明位置上的字符为空格（ASCII码为32）。

输入数据保证至少存在一个合法解，故你的输出应有且仅有一条回路。如果存在多组答案，请输出任意一组。

hint:
对于20%的数据，有N ≤ 10；

对于40%的数据，有1 ≤ N, M ≤ 80；

对于40%的数据，输入没有“.”,且N, M > 10；

对于100%的数据，满足1 ≤ N, M ≤ 800。


title: [SDOI2010] 大陆争霸

background:
在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。

幻想历 $8012$ 年 $1$ 月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。

幻想历 $8012$ 年 $3$ 月 $2$ 日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。

幻想历 $8012$ 年 $3$ 月 $7$ 日，神谕镇的起义被杰森国大军以残酷手段镇压。

幻想历 $8012$ 年 $3$ 月 $8$ 日，克里斯国对杰森国宣战。由数十万大军组成的克里斯军团开至两国边境，与杰森军团对峙。

幻想历 $8012$ 年 $4$ 月，克里斯军团攻破杰森军团防线进入神谕镇，该镇幸存的克里斯国教徒得到解放。

战争随后进入胶着状态，旷日持久。战况惨烈，一时间枪林弹雨，硝烟弥漫，民不聊生。

description:
幻想历 $8012$ 年 $5$ 月 $12$ 日深夜，斯普林·布拉泽降下神谕：“Trust me, earn eternal life.”克里斯军团士气大增。作为克里斯军团的主帅，你决定利用这一机会发动奇袭，一举击败杰森国。具体地说，杰森国有 $N$ 个城市，由 $M$ 条单向道路连接。神谕镇是城市 $1$ 而杰森国的首都是城市 $N$。你只需摧毁位于杰森国首都的曾·布拉泽大神殿，杰森国的信仰，军队还有一切就都会土崩瓦解，灰飞烟灭。

为了尽量减小己方的消耗，你决定使用自爆机器人完成这一任务。唯一的困难是，杰森国的一部分城市有结界保护，不破坏掉结界就无法进入城市。而每个城市的结界都是由分布在其他城市中的一些结界发生器维持的，如果想进入某个城市，你就必须破坏掉维持这个城市结界的所有结界发生器。

现在你有无限多的自爆机器人，一旦进入了某个城市，自爆机器人可以瞬间引爆，破坏一个目标（结界发生器，或是杰森国大神殿），当然机器人本身也会一起被破坏。你需要知道：摧毁杰森国所需的最短时间。

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

接下来 $M$ 行，每行三个正整数 $u_i,v_i,w_i$，表示有一条从城市 $u_i$ 到城市 $v_i$ 的单向道路，自爆机器人通过这条道路需要 $w_i$ 的时间。

之后 $N$ 行，每行描述一个城市。首先是一个正整数 $l_i$，维持这个城市结界所使用的结界发生器数目。之后 $l_i$ 个 $1\ldots N$ 之间的城市编号，表示每个结界发生器的位置。如果 $l_i=0$，则说明该城市没有结界保护，保证 $l_1 = 0$ 。

outputFormat: 仅包含一个正整数 ，击败杰森国所需的最短时间。

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

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

对于 $20\%$ 的数据，满足 $N\leq 15$，$M≤50$；

对于 $50\%$ 的数据，满足 $N\leq 500$，$M\leq 6\times 10^3$；

对于 $100\%$ 的数据，满足 $1\leq N\leq 3\times 10^3$，$1\leq M\leq 7\times 10^4$，$1\leq w_i\leq 10^8$。

输入数据保证一定有解，且不会存在维持某个城市结界的结界发生器在这个城市内部。

连接两个城市的道路可能不止一条，也可能存在一个城市自己到自己的道路。


title: [SDOI2010] 外星千足虫

description:
公元 $2333$ 年 $2$ 月 $3$ 日，在经历了 $17$ 年零 $3$ 个月的漫长旅行后，“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局（NASA）研制发射，行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等 $23$ 颗太阳系星球，并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下 $45.70$ 米位置发现一批珍贵的活体生命样本，并将其带回检测。

在带回的活体样本中，最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长，身体分为若干节。受到触碰时，会将身体卷曲成圆环形，间隔一段时间后才会复原活动。

有趣的还不止如此。研究人员发现，这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足，但足的总数一定是奇数条！

虽然从外观难以区分二者，但通过统计足的数目，科学家们就能根据奇偶性判断出千足虫所属的星球。

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

作为 J 国派去 NASA 的秘密间谍，你希望参加这次研究活动以掌握进一步的情报，而 NASA 选拔的研究人员都是最优秀的科学家。于是 NASA 局长 Charles Bolden 出了一道难题来检测你的实力：

现在你面前摆有 $1\ldots N$ 编号的 $N$ 只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。

Charles 每次会在这 $N$ 只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出其内所有昆虫足数之和。Charles 会将这个和数 $\bmod$ $2$ 的结果反馈给你，同时告诉你一开始放入机器中的是哪几只虫子。

他的这种统计操作总共进行 $M$ 次，而你应当尽早得出鉴定结果。

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

假如在第 $K$ 次统计结束后，现有数据就足以确定每只虫子的身份，你就还应将这个 $K$ 反馈给 Charles，此时若 $K<M$，则表明那后 $M-K$ 次统计并非必须的。

如果根据所有 $M$ 次统计数据还是无法确定每只虫子身份，你也要跟 Charles 讲明：就目前数据会存在多个解。

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

接下来 $M$ 行，按顺序给出 Charles 这 $M$ 次使用“点足机”的统计结果。每行包含一个 $01$ 串和一个数字，用一个空格隔开。$01$ 串按位依次表示每只虫子是否被放入机器：如果第 $i$ 个字符是 $0$ 则代表编号为 $i$ 的虫子未被放入，$1$ 则代表已被放入。后面跟的数字是统计的昆虫足数 $\bmod$ $2$ 的结果。

由于 NASA 的实验机器精确无误，保证前后数据不会自相矛盾。即给定数据一定有解。

outputFormat:
在给定数据存在唯一解时有 $N+1$ 行，第一行输出一个不超过 $M$ 的正整数 $K$，表明在第 $K$ 次统计结束后就可以确定唯一解；接下来N行依次回答每只千足虫的身份，若是奇数条足则输出 `?y7M#`（火星文），偶数条足输出 `Earth`。

如果输入数据存在多解，输出 `Cannot Determine`。

hint:
### 评分标准

对于每一个测试点，如果你的输出文件与答案文件完全相同，该测试点得满分。

否则，对于存在唯一解的测试点，如果你正确回答所有千足虫的身份，将得到 $50\%$ 的分数；

其他情况，该测试点得零分。

### 数据规模和约定

对于 $20\%$ 的数据，满足 $N=M\leq 20$；

对于 $40\%$ 的数据，满足 $N=M\leq 500$；

对于 $70\%$ 的数据，满足 $N\leq500$，$M\leq 10^3$；

对于 $100\%$ 的数据，满足 $1\leq N\leq 10^3$，$1\leq M\leq 2\times 10^3$。


title: [SDOI2010] 所驼门王的宝藏

description:
在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的 AlpacaL.Sotomon 是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天 Henry Curtis 故事的起点。Henry 是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状，由 $R \times C$ 间矩形宫室组成，其中有 $N$ 间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔，由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这 $N$ 间藏宝宫室每间都架设了一扇传送门，没有宝藏的宫室不设传送门，所有的宫室传送门分为三种：

1. “横天门”：由该门可以传送到同行的任一宫室；
2. “纵寰门”：由该门可以传送到同列的任一宫室；
3. “任意门”：由该门可以传送到以该门所在宫室为中心周围 $8$ 格中任一宫室（如果目标宫室存在的话）。

深谋远虑的 Henry 当然事先就搞到了所驼门王当年的宫殿招标册，书册上详细记录了每扇传送门所属宫室及类型。而且，虽然宫殿内外相隔，但他自行准备了一种便携式传送门，可将自己传送到殿内任意一间宫室开始寻宝，并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次，且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制，每间宫室也可以多次出入。

现在 Henry 已经打开了便携门，即将选择一间宫室进入。为得到尽多宝藏，他希望安排一条路线，使走过的不同藏宝宫室尽可能多。请你告诉 Henry 这条路线最多行经不同藏宝宫室的数目。

inputFormat:
第一行给出三个正整数 $N,R,C$。

以下 $N$ 行，每行给出一扇传送门的信息，包含三个正整数 $x_i,y_i,T_i$，表示该传送门设在位于第 $x_i$ 行第 $y_i$ 列的藏宝宫室，类型为 $T_i$。$T_i$ 是一个 $1 \sim 3$ 间的整数，$1$ 表示可以传送到第 $x_i$ 行任意一列的“横天门”，$2$ 表示可以传送到任意一行第 $y_i$ 列的“纵寰门”，$3$ 表示可以传送到周围 $8$ 格宫室的“任意门”。

保证 $1 \le x_i \le R$，$1 \le y_i \le C$，所有的传送门位置互不相同。

outputFormat: 输出只有一个正整数，表示你确定的路线所经过不同藏宝宫室的最大数目。


title: [SDOI2010] 地精部落

description:
传说很久以前，大地上居住着一种神秘的生物：地精。

地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为 $n$ 的山脉 $h$ 可分为从左到右的 $n$ 段，每段有一个**独一无二**的高度 $h_i$，其中 $h_i$ 是 $1$ 到 $n$ 之间的正整数。

如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。

类似地，如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。

地精们有一个共同的爱好——饮酒，酒馆可以设立在山谷之中。地精的酒馆不论白天黑夜总是人声鼎沸，地精美酒的香味可以飘到方圆数里的地方。

地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台，并轮流担当瞭望工作，以确保在第一时间得知外敌的入侵。

地精们希望这 $n$ 段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足这个条件的整座山脉才可能有地精居住。

现在你希望知道，长度为 $n$ 的可能有地精居住的山脉有多少种。两座山脉 $a$ 和 $b$ 不同当且仅当存在一个 $i$，使得 $a_i\ne b_i$。由于这个数目可能很大，你只对它除以 $p$ 的余数感兴趣。

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

outputFormat: 一个非负整数，表示你所求的答案对 $p$ 取余之后的结果。

hint:
共有 $10$ 种可能的山脉，它们是：

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

其中标记的数字表示可以设立瞭望台的山峰，其它表示可以设立酒馆的山谷。

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

对于 $20\%$ 的数据，满足 $N \le 10$；

对于 $40\%$ 的数据，满足 $N \le 18$；

对于 $70\%$ 的数据，满足 $N \le 550$；

对于 $100\%$ 的数据，满足 $3 \le N \le 4200$，$P \le 10^9$。


title: [SDOI2010] 粟粟的书架

description:
幸福幼儿园 B29 班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢 Thomas H. Cormen 的文章。粟粟家中有一个 $R$ 行 $C$ 列的巨型书架，书架的每一个位置都摆有一本书，上数第 $i$ 行、左数第 $j$ 列摆放的书有 $P_{i,j}$ 页厚。

粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头都难以摘到。不过她发现，如果在脚下放上几本书，就可以够着苹果；她同时注意到，对于第 $i$ 天指定的那个苹果，只要她脚下放置书的总页数之和不低于 $H_i$，就一定能够摘到。

由于书架内的书过多，父母担心粟粟一天内就把所有书看完而耽误了上幼儿园，于是每天只允许粟粟在一个特定区域内拿书。这个区域是一个矩形，第 $i$ 天给定区域的左上角是上数第$x1_i$ 行的左数第 $y1_i$ 本书，右下角是上数第 $x2_i$ 行的左数第 $y2_i$ 本书。换句话说，粟粟在这一天，只能在这 $(x2_i－x1_i＋1)\times(y2_i－y1_i＋1)$ 本书中挑选若干本垫在脚下，摘取苹果。

粟粟每次取书时都能及时放回原位，并且她的书架不会再撤下书目或换上新书，摘苹果的任务会一直持续 $M$ 天。给出每本书籍的页数和每天的区域限制及采摘要求，请你告诉粟粟，她每天至少拿取多少本书，就可以摘到当天指定的苹果。

inputFormat:
第一行是三个正整数 $R, C, M$。

接下来是一个 $R$ 行 $C$ 列的矩阵，从上到下、从左向右依次给出了每本书的页数 $P_{i,j}$。

接下来 $M$ 行，第 $i$ 行给出正整数 $x1_i, y1_i, x2_i, y2_i, H_i$，表示第 $i$ 天的指定区域是 $(x1_i, y1_i)$ 与 $(x2_i, y2_i)$ 间的矩形，总页数之和要求不低于Hi。

保证 $1\le x1_i\le x2_i\le R$，$1\le y1_i\le y2_i\le C$。

outputFormat: 输出共 $M$ 行，第 $i$ 行回答粟粟在第 $i$ 天时为摘到苹果至少需要拿取多少本书。如果即使取走所有书都无法摘到苹果，则在该行输出 `Poor QLW`。

hint:
对于 $10\%$ 的数据，满足 $R, C\le10$。

对于 $20\%$ 的数据，满足 $R, C\le 40$。

对于 $50\%$ 的数据，满足 $R, C\le 200$，$M\le 2\times 10^5$。

另有 $50\%$ 的数据，满足 $R＝1$，$C\le 5\times 10^5$，$M\le 2\times 10^4$。

对于 $100\%$ 的数据，满足 $1\le P_{i,j}\le 1000$，$1\le H_i\le 2\times 10^9$。


title: [SDOI2010] 星际竞速

description:
10 年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座 $\alpha$ 星的悠悠也是其中之一。

赛车大赛的赛场由 $N$ 颗行星和 $M$ 条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这 $N$ 颗行星之间没有任何航路的天体出发，访问这 $N$ 颗行星每颗恰好一次，首先完成这一目标的人获得胜利。

由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一段时间的定位之后，它能瞬间移动到任意一个行星。

天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。

尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。

inputFormat:
输入文件 starrace.in 的第一行是两个正整数 $N, M$。

第二行 $N$ 个数 $A_1,\cdots,A_N$，其中 $A_i$ 表示使用能力爆发模式到达行星 $i$ 所需的定位时间。

接下来 $M$ 行，每行 $3$ 个正整数 $u_i, v_i, w_i$，表示在编号为 $u_i$ 和 $v_i$ 的行星之间存在一条需要航行 $w_i$ 时间的星际航路。

输入数据已经按引力值排序，也就是编号小的行星引力值一定小，且不会有两颗行星引力值相同。

outputFormat: 输出文件 starrace.out 仅包含一个正整数，表示完成比赛所需的最少时间。

hint:
样例一说明：先使用能力爆发模式到行星 $1$，花费时间 $1$。

然后切换到高速航行模式，航行到行星 $2$，花费时间 $10$。

之后继续航行到行星 $3$ 完成比赛，花费时间 $1$。

虽然看起来从行星 $1$ 到行星 $3$ 再到行星 $2$ 更优，但我们却不能那样做，因为那会导致超能电驴爆炸。

【数据规模和约定】

对于 $30\%$ 的数据 $N\leq 20$，$M\leq 50$；

对于 $70\%$ 的数据 $N\leq 200$，$M\leq 4\times 10^3$；

对于 $100\%$ 的数据 $N\leq 800$，$M\leq 1.5\times 10^4$。

输入数据中的任何数都不会超过 $10^6$。

输入数据保证任意两颗行星之间至多存在一条航道，且不会存在某颗行星到自己的航道。


title: [SCOI2007] 压缩

description:
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。

`bcdcdcdcd` 可以压缩为 `bMcdRR`，下面是解压缩的过程：

已经解压的部分|解压结果|缓冲串
---|---|---
b|b|b
bM|b|.
bMc|bc|c
bMcd|bcd|cd
bMcdR|bcdcd|cdcd
bMcdRR|bcdcdcdcd|cdcdcdcd

inputFormat: 输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

outputFormat: 输出仅一行，即压缩后字符串的最短长度。

hint:
在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。

【限制】

50%的数据满足：1<=n<=20

100%的数据满足：1<=n<=50


title: [CTSC2017] 投影

background: 无

description:
换一个角度看，世界可能就不同。 —— 小强

k 维空间中有 n 个黑点与 n 个白点。我们为每一个黑点确定一个互不相同的对应的白点，这样一共有 n! 种对应方法。我们定义这 n 个黑点与 n 个白点之间的 “移动距离”为，在所有的对应方法中，对应的黑点与白点之间的 n 个欧几里德距离的和的最小值。

例如; 考虑一维中的三个黑点 {1,5,6} 与三个白点 {2,3,4}，那么它们之间的移动距离为; |1 − 2| + |5 − 3| + |6 − 4| = 4。你可以验证一下这确实是距离和最小的一种对应方法。
你得到了三维空间中的 n 个黑点与 n 个白点。你想把它们投影到一个 k(1 ≤ k ≤ 2)维子空间上。一维子空间就是三维空间中的一条直线，二维子空间则是三维空间中的一个平面。一个点在一个子空间中的投影点就是这个子空间中距离它最近的点。例如，(0, 0, 0), (1, 1, 0), (1, 0, 0), (0, 1, 0) 这四个点投影到 x − y = 0,z = 0 这条直线上之后，得到的投影点是 (0, 0, 0), (1, 1, 0), (0;5, 0;5, 0), (0;5, 0;5, 0)。

你希望这 n 个黑点和 n 个白点投影到这个 k 维子空间之后的移动距离最大。请你计算这个最大值除以 n。

inputFormat:
每个测试文件中可能有多个测试用例，每个测试用例的格式如下：

第一行两个数 n 和 k，表示点数以及降到的维度。

后面 2n 行，每行三个数，表示点的坐标。

文件最后有一行包含两个数 −1 − 1。

outputFormat:
对文件中的每个测试用例，输出一行一个数 (长度不要超过 30)，表示结果。

你的答案与参考答案的相对误差不超过 10^−7 时被认为是正确的。

只有一个文件中所有的测试用例的结果都是正确的才能获得这个测试文件所对应的分数。

hint:
对于 30% 的数据， k = 1， n ≤ 1000, 所有的点的 z 都是 0。一个文件中最多包含一个测试用例。

对于另外 40% 的数据， k = 1， n ≤ 1000，所有的点的坐标都是 [−1, 1] 之间均匀独立随机生成的，一个文件中最多包含十个测试用例。

对于另外 30% 的数据， k = 2， n ≤ 20，所有的点的坐标都是 [−1, 1] 之间均匀独立随机生成的，一个文件中最多包含十个测试用例。

对于 100% 的数据，点的坐标的范围都是 −1 到 +1 之间的，答案不小于 0.01。


title: [SCOI2007] 降雨量

description: 我们常常会说这样的话：“$X$ 年是自 $Y$ 年以来降雨量最多的”。它的含义是 $X$ 年的降雨量不超过 $Y$ 年，且对于任意 $Y < Z < X$，$Z$ 年的降雨量严格小于 $X$ 年。例如 2002、2003、2004 和 2005 年的降雨量分别为 $4920$、$5901$、$2832$ 和 $3890$，则可以说“2005 年是自 2003 年以来最多的”，但不能说“2005 年是自 2002 年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。

inputFormat: 输入仅一行包含一个正整数 $n$，为已知的数据。以下 $n$ 行每行两个整数 $y_i$ 和 $r_i$，为年份和降雨量，按照年份从小到大排列，即 $y_i<y_{i+1}$。下一行包含一个正整数 $m$，为询问的次数。以下 $m$ 行每行包含两个数 $Y$ 和 $X$，即询问“$X$ 年是自 $Y$ 年以来降雨量最多的。”这句话是“必真”、“必假”还是“有可能”。

outputFormat: 对于每一个询问，输出 `true`、`false` 或者 `maybe`。


title: [SCOI2007] 蜥蜴

description:
在一个 $r$ 行 $c$ 列的网格地图中有一些高度不同的石柱，第 $i$ 行 $j$ 列的石柱高度为 $h_{i,j}$。

一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。

每行每列中相邻石柱的距离为 $1$，蜥蜴的跳跃距离是 $d$，即蜥蜴可以跳到**平面距离**不超过 $d$ 的任何一个石柱上。

石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 $1$（如果仍然落在地图内部，则到达的石柱高度不变）。

如果该石柱原来高度为 $1$，则蜥蜴离开后消失，以后其他蜥蜴不能落脚。

任何时刻不能有两只蜥蜴在同一个石柱上。

inputFormat:
#### 输入格式
输入第一行为三个整数 $r,c,d$，即地图的规模与最大跳跃距离。

接下来 $r$ 行每行 $c$ 个数字为石柱的初始状态，$0$ 表示没有石柱，否则表示石柱的初始高度 $h_{i,j}$。

接下来 $r$ 行每行 $c$ 个字符为蜥蜴位置，`L` 表示蜥蜴，`.` 表示没有蜥蜴。

outputFormat: 输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

hint: 对于 $100\%$ 的数据满足：$1\le r,c\le20$，$1\le d\le 4$，$1\le h\le 3$。


title: [SCOI2008] 奖励关

description:
你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出 $k$ 次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。

宝物一共有 $n$ 种，系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。也就是说，即使前 $(k-1)$ 次系统都抛出宝物 $1$（这种情况是有可能出现的，尽管概率非常小），第 $k$ 次抛出各个宝物的概率依然均为 $\frac 1 n $。

获取第 $i$ 种宝物将得到 $p_i$ 分，但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $s_i$。只有当 $s_i$ 中所有宝物都至少吃过一次，才能吃第 $i$ 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，$p_i$ 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。

假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？

inputFormat:
第一行为两个整数，分别表示抛出宝物的次数 $k$ 和宝物的种类数 $n$。

第 $2$ 到第 $(n + 1)$ 行，第 $(i + 1)$ 有若干个整数表示第 $i$ 个宝物的信息。每行首先有一个整数，表示第 $i$ 个宝物的分数 $p_i$。接下来若干个互不相同的整数，表示该宝物的各个前提宝物集合 $s_i$，每行的结尾是一个整数 $0$，表示该行结束。

outputFormat: 输出一行一个实数表示答案，保留六位小数。

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

对于全部的测试点，保证 $1 \leq k \leq 100$，$1 \leq n \leq 15$，$-10^6 \leq p_i \leq 10^6$。


title: [SCOI2008] 天平

description: 你有 $n$ 个砝码，均为 $1$ 克，$2$ 克或者 $3$ 克。你并不清楚每个砝码的重量，但你知道其中一些砝码重量的大小关系。你把其中两个砝码 A 和 B 放在天平的左边，需要另外选出两个砝码放在天平的右边。问：有多少种选法使得天平的左边重($c_1$)、一样重($c_2$)、右边重($c_3$)？（只有结果保证唯一确定的选法才统计在内）

inputFormat:
第一行包含三个正整数 $n$, $A$, $B$（$1\le A,B\le n$, $A\neq B$）。

以下 $n$ 行包含重量关系矩阵，其中第 $i$ 行第 $j$ 个字符为加号 `+` 表示砝码 $i$ 比砝码 $j$ 重，减号 `-` 表示砝码 $i$ 比砝码 $j$ 轻，等号 `=` 表示砝码 $i$ 和砝码 $j$ 一样重，问号 `?` 表示二者的关系未知。

数据保证至少存在一种情况符合该矩阵。

outputFormat: 仅一行，包含三个整数，即 $c_1$，$c_2$ 和 $c_3$。


title: [SCOI2008] 斜堆

description:
斜堆(skew heap)是一种常用的数据结构。它也是二叉树，且满足与二叉堆相

同的堆性质：每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。

但斜堆不必是平衡的，每个结点的左右儿子的大小关系也没有任何规定。在本题

中，斜堆中各个元素的值均不相同。

在斜堆 H 中插入新元素X 的过程是递归进行的：当H 为空或者X 小于H

的根结点时X 变为新的树根，而原来的树根（如果有的话）变为X 的左儿子。

当X 大于H 的根结点时，H 根结点的两棵子树交换，而X（递归）插入到交换

后的左子树中。

给出一棵斜堆，包含值为0~n的结点各一次。求一个结点序列，使得该斜堆

可以通过在空树中依次插入这些结点得到。如果答案不惟一，输出字典序最小的

解。输入保证有解。

inputFormat:
第一行包含一个整数n。第二行包含n个整数d1, d2, ... , dn， di<100表示i

是di的左儿子，di>=100 表示i 是di-100 的右儿子。显然0 总是根，所以输入中

不含d0。

outputFormat: 仅一行，包含n+1整数，即字典序最小的插入序列。


title: [SCOI2008] 着色方案

description:
有 $n$ 个木块排成一行，从左到右依次编号为 $1$ 至 $n$。

你有 $k$ 种颜色的油漆，第 $i$ 种颜色的油漆足够涂 $c_i$ 个木块。

所有油漆刚好足够涂满所有木块，即 $\sum_{i=1}^kc_i=n$。

由于相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

由于答案可能很大，请输出对 $10^9+7$ 取模的结果。

inputFormat:
第一行，一个整数 $k$，表示颜色数量。

第二行 $k$ 个整数 $c_1,c_2,\dots,c_k$，表示每种颜色能够涂木块的个数。

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

hint:
- 对于 $50\%$ 的数据，$1 \leq k \leq 5$，$1 \leq c_i \leq 3$；
- 对于 $100\%$ 的数据，$1 \leq k \leq 15$，$1 \leq c_i \leq 5$。


title: [SDOI2010] 城市规划

description:
小猪iPig来到了一个叫做pigsty的城市里，pigsty是一座专门为小猪所准备的城市，城市里面一共有n个小区给小猪们居住，并且存在许多条无向边连接着许多小区。因为这里是一个和谐的城市，所以小猪iPig准备在这个城市里面度过他的余生。

若干年之后小猪iPig当上了规划局长，这件事令他非常开心。不过与此同时pigsty城市里面出现了许多反和谐主义者，他们已经厌烦了这样和谐的生活，在城市里到处闹事。小猪iPig为了更好地控制局面，他把城市改造成了另外一个样子：iPig把道路全部摧毁之后重新修建了m条无向边，并且保证每一个小区最多存在于一个由无向边组成的环中。

iPig以为这样做就让那些反和谐主义者不敢继续猖狂下去了，谁知到在新的城市道路修建好以后反和谐主义者宣言要对城市的小区进行一次洗脑！

这下可麻烦了，iPig赶紧收集了许多的情报。iPig给每个小区标记了一个和谐值HX\_i，用它来表示第i个小区的和谐程度。

通过地下消息iPig又得知那些反和谐主义者进攻时有个规律：他们会选择若干个小区下手，这些小区都派一只猪过去，把这些小区的和谐值归零。在这个过程中，每个选择的小区所直接连接着的几个小区都派了一只猪去看守——以防被警猪给干扰。这个计划看似完美但是还是存在一个漏洞：因为人员之间都是在网络上认识的，互相没有见过面，为了防止不必要的麻烦（认错猪之类），每个小区最多只会有一头猪存在。

iPig突然感到了莫大的压力，他想知道在最坏情况下会丢失多少和谐值。但是不懂计算机的他不知道应该怎样计算。你能帮帮他吗？

inputFormat:
输入第一行有两个整数n和m，表示pigsty城市里面有n个小区，在iPig修整城市后有m条无向边连接着n个小区。

接下来一行有n个正整数，第i个正整数HX\_i表示第i个小区的和谐值为HX\_i。

接下来m行，每行两个正整数a和b（1<=a,b<=n），表示存在一条连接着小区a和小区 b的无向边。

outputFormat: 输出只有一行一个整数，表示最坏情况下损失的和谐值为多少。

hint:
【样例解释】

反和谐主义者选择的小区分别是小区3（看守的小区是小区1、小区2和小区5）、小区7（看守的小区是小区4和小区6）和小区9（看守的小区是小区8），这样会损失的总和谐值为3+3+11=17。

或者选择的小区分别是小区1（看守的小区是小区2和小区3）、小区4（看守的小区是小区5和小区7）和小区9（看守的小区是小区8），这样会损失的总和谐值为2+4+11=17。

如果同时选择小区3、小区4和小区9，虽然损失的总和谐值为18，但是小区3和小区4都要派猪来看守小区5，这不符合条件，故此方案不可行。

【数据约定】

对于20%的数据，保证每个点不存在于任何一个环中；

对于另外30%的数据，保证图中只存在一个环；

对于100%的数据，有N<=1000000，M<=2000000，所有的权值不超过1000。


title: [SDOI2010] 捉迷藏

background: iPig 在大肥猪学校刚上完了无聊的猪文课，天资聪慧的 iPig 被这门对他来说无比简单的课弄得非常寂寞，为了消除寂寞感，他决定和他的好朋友 giPi（鸡皮）玩一个更加寂寞的游戏——捉迷藏。但是，他们觉得，玩普通的捉迷藏没什么意思，还是不够寂寞，于是，他们决定玩寂寞无比的螃蟹版捉迷藏。

description:
螃蟹版捉迷藏，顾名思义，就是说他们在玩游戏的时候只能沿水平或垂直方向走。

一番寂寞的剪刀石头布后，他们决定 iPig 去捉 giPi。由于他们都很熟悉大肥猪学校的地形了，所以 giPi 只会躲在大肥猪学校内 $N$ 个隐秘地点之一，显然 iPig 也只会在那 $N$ 个地点内找 giPi。

游戏一开始，他们从这 $N$ 个隐秘地点之中选定一个地点，iPig 保持不动，然后 giPi 用 $30$ 秒的时间逃离现场（显然，giPi 不会呆在原地）。然后 iPig 会随机地去找 giPi，直到找到为止。

由于 iPig 很懒，所以他总是走最短的路径，而且，他选择起始点不是随便选的，他想找一个地点，使得该地点到（除了这个地点以外的）最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。

由于 iPig 现在手上没有电脑，所以不能编程解决这个如此简单的问题，所以他马上打了个电话，要求你帮他解决这个问题。iPig 告诉了你大肥猪学校的 $N$ 个隐秘地点的坐标，请你编程求出 iPig 的问题。

inputFormat:
第 $1$ 行：一个整数 $N$；

接下来 $N$ 行：每行两个整数 $X_i,Y_i$，表示第 $i$ 个地点的坐标。

outputFormat: 一个整数，为距离差的最小值。


title: Uim的情人节礼物·其之弐

description:
前传：详见洛谷 P2525

Uim 成功地按照顺序将礼物送到了 $N$ 个妹子的手里并维持她们的和谐。

现在 Uim 现在想知道，他最终选择的顺序是所有给 $N$ 个妹子送礼顺序中，字典序第几小的。送礼顺序可以看作 $1,2,\cdots,N$ 的一个排列。

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

第二行一个整数 $X$，表示给出的排列。

outputFormat: 一个整数，表示是第几小的字典序。

hint:
$1\le N \le 9$。

请注意输入的排列没有空格。


title: 斐波那契

background: 大样例可在页面底部「附件」中下载。

description:
小 C 养了一些很可爱的兔子。 有一天，小 C 突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行 繁衍：一对兔子从出生后第二个月起，每个月刚开始的时候都会产下一对小兔子。我们假定， 在整个过程中兔子不会出现任何意外。

小 C 把兔子按出生顺序，把兔子们从 1 开始标号，并且小 C 的兔子都是 1 号兔子和 1 号兔子的后代。如果某两对兔子是同时出生的，那么小 C 会将父母标号更小的一对优先标 号。

如果我们把这种关系用图画下来，前六个月大概就是这样的：

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

其中，一个箭头 $A \to B$ 表示 $A$ 是 $B$ 的祖先，相同的颜色表示同一个月出生的兔子。

为了更细致地了解兔子们是如何繁衍的，小 C 找来了一些兔子，并且向你提出了 $m$ 个问题：她想知道关于每两对兔子 $a_i$ 和 $b_i$，他们的最近公共祖先是谁。你能帮帮小 C 吗？

一对兔子的祖先是这对兔子以及他们父母（如果有的话）的祖先，而最近公共祖先是指 两对兔子所共有的祖先中，离他们的距离之和最近的一对兔子。比如，$5$ 和 $7$ 的最近公共祖 先是 $2,1$ 和 $2$ 的最近公共祖先是 $1,6$ 和 $6$ 的最近公共祖先是 $6$。

inputFormat: 输入第一行，包含一个正整数 $m$。输入接下来 $m$ 行，每行包含 $2$ 个正整数，表示 $a_i$ 和 $b_i$。

outputFormat: 输出一共 $m$ 行，每行一个正整数，依次表示你对问题的答案。

hint:
【数据范围与约定】 子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。 每个测试点的数据规模及特点如下表：

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

特殊性质 $1$：保证 $a_i$, $b_i$ 均为某一个月出生的兔子中标号最大的一对兔子。例如，对 于前六个月，标号最大的兔子分别是 $1, 2, 3, 5, 8, 13$。

特殊性质 $2$：保证 $|a_i-b_i|\le 1$。


title: [SDOI2010] 古代猪文

background:
“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”

——选自猪王国民歌

很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王国。

猪王国虽然不大，但是土地肥沃，屋舍俨然。如果一定要拿什么与之相比的话，那就只能是东晋陶渊明笔下的大家想象中的桃花源了。猪王勤政爱民，猪民安居乐业，邻里和睦相处，国家秩序井然，经济欣欣向荣，社会和谐稳定。和谐的社会带给猪民们对工作火红的热情和对未来的粉色的憧憬。

小猪iPig是猪王国的一个很普通的公民。小猪今年10岁了，在大肥猪学校上小学三年级。和大多数猪一样，他不是很聪明，因此经常遇到很多或者稀奇古怪或者旁人看来轻而易举的事情令他大伤脑筋。小猪后来参加了全猪信息学奥林匹克竞赛(Pig Olympiad in Informatics, POI)，取得了不错的名次，最终保送进入了猪王国大学(Pig Kingdom University, PKU)深造。

现在的小猪已经能用计算机解决简单的问题了，比如能用P++语言编写程序计算出A + B的值。这个“成就”已经成为了他津津乐道的话题。当然，不明真相的同学们也开始对他刮目相看啦~

小猪的故事就将从此展开，伴随大家两天时间，希望大家能够喜欢小猪。

description:
猪王国的文明源远流长，博大精深。

iPig 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为 $n$。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。

iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的 $1/k$，其中 $k$ 是 $n$ 的一个正约数（可以是 $1$ 或 $n$）。不过具体是哪 $1/k$，以及 $k$ 是多少，由于历史过于久远，已经无从考证了。

iPig 觉得只要符合文献，每一种 $k|n$ 都是有可能的。他打算考虑到所有可能的 $k$。显然当 $k$ 等于某个定值时，该朝的猪文文字个数为 $n/k$。然而从 $n$ 个文字中保留下 $n/k$ 个的情况也是相当多的。iPig 预计，如果所有可能的 $k$ 的所有情况数加起来为 $p$ 的话，那么他研究古代文字的代价将会是 $g^p$。

现在他想知道猪王国研究古代文字的代价是多少。由于 iPig 觉得这个数字可能是天文数字，所以你只需要告诉他答案除以 $999911659$ 的余数就可以了。

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

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


title: [SDOI2010] 代码拍卖会

description:
随着 iPig 在 P++ 语言上的造诣日益提升，他形成了自己一套完整的代码库。猪王国想参加 POI 的童鞋们都争先恐后问 iPig 索要代码库。iPig 不想把代码库给所有想要的小猪，只想给其中的一部分既关系好又肯出钱的小猪，于是他决定举行了一个超大型拍卖会。

在拍卖会上，所有的 $N$ 头小猪将会按照和 iPig 的好感度从低到高，从左到右地在 iPig 面前站成一排。每个小猪身上都有 $9$ 猪币（与人民币汇率不明），从最左边开始，每个小猪依次举起一块牌子，上面写上想付出的买代码库的猪币数量（$1$ 到 $9$ 之间的一个整数）。大家都知道，如果自己付的钱比左边的猪少，肯定得不到梦寐以求的代码库，因此从第二只起，每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪（们）会得到 iPig 的代码库真传，向着保送 PKU（Pig Kingdom University）的梦想前进。

iPig 对自己想到的这个点子感到十分满意，在去现场的路上，iPig 就在想象拍卖会上会出现的场景，例如一共会出现多少种出价情况之类的问题，但这些问题都太简单了，iPig 早已不感兴趣了，他想要去研究更加困难的问题。iPig 发现如果他从台上往下看，所有小猪举的牌子从左到右将会正好构成一个 $N$ 位的整数，他现在想要挑战的问题是所有可能构成的整数中能正好被 $P$ 整除的有多少个。由于答案过大，他只想要知道答案 $\bmod\ 999911659$ 就行了。

inputFormat: 有且仅有一行两个数 $N\ (1 \le N \le 10^{18})$ 和 $P\ (1 \le P \le 500)$，用一个空格分开。

outputFormat: 有且仅有一行一个数，表示答案除以 $999911659$ 的余数。

hint:
### 样例解释

方案可以是：$12,\allowbreak 15,\allowbreak 18,\allowbreak 24,\allowbreak 27,\allowbreak 33,\allowbreak 36,\allowbreak 39,\allowbreak 45,\allowbreak 48,\allowbreak 57,\allowbreak 66,\allowbreak 69,\allowbreak 78,\allowbreak 99$，共 $15$ 种。

### 数据规模

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