title: [HNOI2003] 多项式的加法和乘法

description:
今天的数学课上，老师讲了多项式的加法和乘法。然后布置了很多计算题，小明不想花太多时间来做数学作业，于是想编写一个程序来完成这个任务。

比如计算下面两个多项式的和与积：

$xy^2z+31wx^3y^3z^{50}+s^3$
$v^2+s^3+3wx^3y^3$

假定所有变量都是单个大写字符，所有的系数和指数都是常数，且都是整数。

我们用 `X^3` 表示 $X$ 的三次方，在系数和不同的项之间用空格分隔，例如 `X Y^2` 中，$X$ 和 $Y$ 之间有空格。下面是两个多项式的例子，除此之外没有别的空格。

`X Y^2 Z + 31 W X^3 Y^3 Z^50 + S^3`
`V^2 + S^3 + 3 W X^3 Y^3`

现在，按照上面的格式给定两个多项式，请你求出这两个多项式的和与积。

inputFormat: 输入包括两行，每一行是一个多项式。每个多项式不超过 $250$ 个字符。计算过程中保证任何中间结果系数和指数均不超过长整数范围。

outputFormat: 输出也是两行，第一行是两个多项式的和，第二行是两个多项式的积。输出中要求合并同类项。输出多项式的格式和输入的格式类似，但输出时请把所有空格都去掉，并保证每一项都是 ASCII 码排在前面的变量放在前面，即输出 `X^3Y^2` 而不是 `Y^2X^3`。另外，输出的项请按变量 `A` 的指数从小到大排列，变量 `A` 指数相同的，按变量 `B` 的指数从小到大排列，依此类推。并注意输出要符合我们平常书写的习惯。


title: [HNOI2003] 历史年份

type: P

description:
明天就要考近代史了，小明决定把要背的历史事件，根据事件发生的年份，按顺序从小到大抄在一张纸上。可是他抄的时候，相邻两个年份相隔太近了。例如1894,1911,1949这三个时间，由于相隔太近，纸上写的是：189419111949。

这使小明很苦恼，于是他准备编写个程序把这些年份还原成应该的样子。那么，怎么才能够正确地还原呢？

首先，这些年份是按时间顺序严格递增排列的，所以，还原后的也必须满足这点要求。但如果仅仅是这样，那么1,89,419,111949也满足要求。显然，最后的年份不可能有这么大，所以，小明要求在这个条件下，最后一个数要最小。

加了这个限制后，18,94,1911,1949也满足条件，但因为是近代史，第一个年份也不会这么早，所以，小明还要在保证最后一个数最小的前提下，第一个数要尽量大。并在保证第一个数最大的情况下，第二个数最大……以此类推。

注意：在本题中，数字前的前导0是被允许的。

inputFormat:
输入文件名：input.txt

输入文件包含多行，每一行是一个由不超过2000个数字组成的字符串，表示一个测试例子。一个输入文件中最多包含1000个测试例子。

outputFormat:
输出文件名：output.txt

相对于输入文件的每一个测试例子，你的程序要输出对应的一行，即是分割后的数字序列，相邻两个数用一个逗号分割。


title: [HNOI2003] 多边形

inputFormat:
输入文件名：input.txt

输入文件第一行是一个自然数N，表示多边形的顶点数。N不超过1500。之后N行每行两个整数(用空格分开)，依次表示多边形的每个顶点的坐标。

outputFormat:
输出文件名：output.txt

输出文件仅1行，是阴影部分的面积，保留2位小数。


title: [HNOI2003] 密室之门

description:
最近，我国考古学家在秦陵兵马俑的新墓坑中发现了若干个密室，每个密室都可以由一个奇特的门进入。那么怎样才能进入密室呢？

第 $i$ 个密室的门上有 $a_i$ 个转盘，该密室的第 $j$ 个转盘被均匀的分成 $b_{i,j}$ 格，这 $b_{i,j}$ 个格子按顺时针方向依次编号为 $0,1,\dots,b_{i,j}-1$，并且每一个转盘上面都有一个指针（结构类似于钟表），指针大约每过 $1.53$ 秒就会从原来指向编号为 $x$ 的格子变成指向编号为 $(x+1)\mod b_{i,j}$ 的格子。当一扇门上所有的转盘上的指针都指向编号为 $0$ 的格子的时候，那么这扇门就会被开启。

但是当考古学家发现密室时，转盘上的指针都指向不同编号的格子，考古学家经过计算发现按照门被开启的原理，有些密室是永远也打不开的。你的任务就是判断那些密室的门是可能被打开的。

inputFormat: 输入文件的第一行为 $n$，表示密室的个数。接下来的数据分为 $n$ 组，每组描述一扇门。每组数据的第一行为 $a_i$，即该密室门上转盘的个数，接下来的 $a_i$ 行每行有两个数据，第一个数据表示 $b_{i,j}$，第二个数据表示发现该密室时指针所指向的格子的编号。

outputFormat: 输出文件总共有 $n$ 行。若第 $i$ 间密室的门能够被打开，则输出文件的第 $i$ 行输出 `possible`，如果不能打开则输出 `impossible`。（注意小写输出）。


title: [HNOI2004] 打鼹鼠

description:
鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 $n \times n$ 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 $i$ 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 $(i, j)$ 的网格移向 $(i-1, j), (i+1, j), (i, j-1), (i, j+1)$ 四个网格，机器人不能走出整个 $n \times n$ 的网格。游戏开始时，你可以自由选定机器人的初始位置。

现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

inputFormat: 第一行为 $n, m$（$n \le 1000$，$m \le {10}^4$），其中 $m$ 表示在这一段时间内出现的鼹鼠的个数，接下来的 $m$ 行中每行有三个数据 $\mathit{time}, x, y$ 表示在游戏开始后 $\mathit{time}$ 个时刻，在第 $x$ 行第 $y$ 个网格里出现了一只鼹鼠。$\mathit{time}$ 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。

outputFormat: 仅包含一个正整数，表示被打死鼹鼠的最大数目。


title: [HNOI2004] 宠物收养场

description:
凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。

被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。

收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

inputFormat: 第一行为一个正整数n，n<=80000，表示一年当中来到收养场的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收养场的宠物和领养者的情况。每行有两个正整数a, b，其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个）

outputFormat: 仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。

hint:
样例解释

注：abs(3-2) + abs(2-4)=3，
最后一个领养者没有宠物可以领养。


title: [HNOI2004] 最佳包裹

description:
发强公司生产了一种金属制品，是由一些笔直的金属条连接起来的，金属条和别的金属条在交点上被焊接在了一起。现在由于美观需要，在这个产品用一层特殊的材料包裹起来。公司为了节约成本，希望消耗的材料最少（不计裁剪时的边角料的损失）。

编程，输入包括该产品的顶点的个数，以及所有顶点的坐标；请计算出包裹这个产品所需要的材料的最小面积。结果要求精确到小数点后第六位（四舍五入）。

inputFormat:
输入文件由 $(n+1)$ 行组成。

第 $1$ 行是一个整数 $n$（$4 \leq n \leq 100$），表示顶点的个数；

第 $2$ 行到第 $(n+1)$ 行，第 $(i+1)$ 行有 $3$ 个实数 $x_i$，$y_i$，$z_i$，表示第 $i$ 个顶点的坐标。

保证顶点的位置各不相同。

outputFormat: 输出文件只有一个实数，四舍五入精确到小数点后六位，表示包裹一个该产品所需的材料面积的最小值。


title: [HNOI2005] 纸片覆盖

description:
喜欢几何的小付遇到了这样一个问题：一天他在一张白纸上画了 $n$ 条直线，然后剪了一张 $m$ 边形（简单多边形）的小纸片。

他想把这张小纸片放在白纸上，使它盖住的线段的总长度最长。并且这张多边形纸片不能翻转或旋转，只能平移，如果直线的某一段刚好与多边形纸片的边重合，那么，这条线段算作是被覆盖。

你能帮他解决这个问题吗？

inputFormat:
从文件 `input.txt` 中读入数据，文件第一行为两个数 $n$ 和 $m$，其中 $1\leq n,m\leq10$，分别表示直线的数目和多边形的边数。

接下来的 $n$ 行分别表示各条直线，每行有 $4$ 个实数 $x_1,y_1,x_2,y_2$，表示一条经过 $\left(x_1,y_1\right)$ 和 $\left(x_2,y_2\right)$ 的直线。

接下来的 $m$ 行按顺时针或逆时针的顺序输入多边形的各个顶点，每行有 $2$ 个实数 $x,y$，表示一个顶点的坐标。

这里假设所有输入的实数都在 $-10000$ 到 $10000$ 之间，且不会超过 $2$ 位小数，输入的多边形保证不自交，且连续的 $3$ 点不共线。

outputFormat: 输出文件 `output.txt` 中仅包含一个数 $L$，表示输入的多边形能盖住的最大的线段总长度，精确到小数点后 $3$ 位。


title: [HNOI2004] 邮递员

description:
小李在 P 市的邮政局工作，他每天的工作是从邮局出发，到自己所管辖的所有邮筒取信件，然后带回邮局。他所管辖的邮筒非常巧地排成了一个 $m\times n$ 的点阵（点阵中的间距都是相等的）。左上角的邮筒恰好在邮局的门口。

小李是一个非常标新立异的人，他希望每天都能走不同的路线，但是同时，他又不希望路线的长度增加（即选择最短的路径走，注意路径长度是指小李实际走的物理距离，并且对路过每个邮筒的次数没有限制），他想知道他有多少条不同的路线可走。他在任何两个邮筒之间走的是直线。

编程，输入包括点阵的 $m$ 和 $n$ 的值；计算出小李可选的不同路线的总条数。

inputFormat: 输入只有一行两个整数 $m$，$n$，表示了小李管辖内的邮筒排成的点阵大小。

outputFormat: 输出一行一个整数，表示小李可选的不同路线的条数。

hint:
#### 样例输入输出 1 解释
![](https://cdn.luogu.com.cn/upload/pic/1331.png)

---
#### 数据规模与约定
- 对于 $100\%$ 的数据，保证 $1\le m\le10$，$1\le n\le20$，且保证 $n\times m$ 是偶数。


title: [HNOI2004] 树的计数

description: 一个有 $n$ 个节点的树，设它的节点分别为 $v_1,v_2,\ldots,v_n$，已知第 $i$ 个节点 $v_i$ 的度数为 $d_i$，问满足这样的条件的不同的树有多少棵。

inputFormat: 输入文件第一行是一个正整数 $n$ ，表示树有 $n$ 个结点。第二行有 $n$ 个数，第 $i$ 个数表示 $d_i$，即树的第 $i$ 个结点的度数。

outputFormat: 输出满足条件的树有多少棵。

hint: $1\le n\le 150$，保证满足条件的树不超过 $10^{17}$ 个。


title: [HNOI2004] L 语言

description:
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章 $T$ 是由若干小写字母构成。一个单词 $W$ 也是由若干小写字母构成。一个字典 $D$ 是若干个单词的集合。我们称一段文章 $T$ 在某个字典 $D$ 下是可以被理解的，是指如果文章 $T$ 可以被分成若干部分，且每一个部分都是字典 $D$ 中的单词。

例如字典 $D$ 中包括单词 $\texttt{is},\texttt{name},\texttt{what},\texttt{your}$，则文章 $\texttt{whatisyourname}$ 是在字典 $D$ 下可以被理解的，因为它可以分成 $4$ 个单词：$\texttt{what},\texttt{is},\texttt{your},\texttt{name}$，且每个单词都属于字典 $D$，而文章 $\texttt{whatisyouname}$ 在字典 $D$ 下不能被理解，但可以在字典 $D'=D\cup\{\texttt{you}\}$ 下被理解。这段文章的一个前缀 $\texttt{whatis}$，也可以在字典 $D$ 下被理解，而且是在字典 $D$ 下能够被理解的最长的前缀。

给定一个字典 $D$，你的程序需要判断若干段文章在字典 $D$ 下是否能够被理解。并给出其在字典 $D$ 下能够被理解的最长前缀的位置。

inputFormat:
第一行两个整数 $n$ 和 $m$，表示字典 $D$ 中有 $n$ 个单词，且有 $m$ 段文章需要被处理。

接下来 $n$ 行，每行一个字符串 $s$，表示字典 $D$ 中的一个单词。

接下来 $m$ 行，每行一个字符串 $t$，表示一篇文章。

outputFormat: 对于输入的每一篇文章，你需要输出一行一个整数，表示这段文章在字典 $D$ 可以被理解的最长前缀的位置。

samples:
4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

hint:
#### 样例 1 解释

- 对于第一个询问，整段文章 `whatisyourname` 都能被理解。
- 对于第二个询问，前缀 `whatis` 能够被理解。
- 对于第三个询问，没有任何前缀能够被理解。

#### 数据规模与约定

- 对于 $80\%$ 的数据，保证 $m \leq 20$，$|t| \leq 10^6$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 20$，$1 \leq m \leq 50$，$1 \leq |s| \leq 20$，$1 \leq |t| \leq 2 \times 10^6$，$s$ 与 $t$ 中均只含小写英文字母。

#### 提示

- 请注意数据读入对程序效率造成的影响。
- 请注意【数据规模与约定】中标注的串长是单串长度，并不是字符串长度和。

#### 说明

本题数据有加强，其中前 $80\%$ 的数据为原测试数据。


title: [HNOI2004] 高精度开根

description:
晓华所在的工作组正在编写一套高精度科学计算的软件，一些简单的部分如高精度加减法、乘除法早已写完了，现在就剩下晓华所负责的部分：实数的高精度开m次根。

因为一个有理数开根之后可能得到一个无理数，所以这项工作是有较大难度的。现在要做的只是这项工作的第一步：只对自然数进行开整数次根，求出它的一个非负根，并且不考虑结果的小数部分，只要求把结果截断取整即可。

程序需要根据给定的输入，包括需要开根的次数，以及被开根的整数；计算出它的非负根取整后的结果。

inputFormat:
输入文件共有两行，每行都有一个整数，并且输入中没有多余的空格：

第一行有一个正整数m (1 <= m <= 50)，表示要开的根次；

第二行有一个整数n (0<=n <= 10^10000)，表示被开根的数。

outputFormat: 输出文件只有一行，包括一个数，即为开根取整后的结果。


title: [HNOI2005] 狡猾的商人

description:
刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了 $n$ 个月以来的收入情况，其中第 $i$ 个月的收入额为 $a_i$，$i=1,2,\ldots,n-1,n$。当 $a_i>0$ 时表示这个月盈利 $a_i$ 元，当 $a_i<0$ 时表示这个月亏损 $a_i$ 元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。

刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出来，每次偷看账本时她都只能看某段时间内账本上记录的收入情况，并且她只能记住这段时间内的总收入。

现在，姹总共偷看了 $m$ 次账本，当然也就记住了 $m$ 段时间内的总收入，你的任务是根据记住的这些信息来判断账本是不是假的。

inputFormat:
第一行为一个正整数 $w$，其中 $w<100$，表示有 $w$ 组数据，即 $w$ 个账本，需要你判断。

每组数据的第一行为两个正整数 $n$ 和 $m$，其中 $n<100,m<1000$，分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。

接下来的 $m$ 行表示刁姹偷看 $m$ 次账本后记住的 $m$ 条信息，每条信息占一行，有三个整数 $s,t$ 和 $v$，表示从第 $s$ 个月到第 $t$ 个月（包含第 $t$ 个月）的总收入为 $v$，这里假设 $s$ 总是小于等于 $t$。

outputFormat: 包含 $w$ 行，每行是 `true` 或 `false`，其中第 $i$ 行为 `true` 当且仅当第 $i$ 组数据，即第 $i$ 个账本不是假的；第 $i$ 行为 `false` 当且仅当第 $i$ 组数据，即第 $i$ 个账本是假的。


title: [NOI2014] 购票

description:
今年夏天，NOI 在 SZ 市迎来了她三十周岁的生日。来自全国 $n$ 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。

全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 $n$ 个城市用 $1\sim n$ 的整数编号。其中 SZ 市的编号为 $1$。对于除 SZ 市之外的任意一个城市 $v$，我们给出了它在这棵树上的父亲城市 $f_v$  以及到父亲城市道路的长度 $s_v$。

从城市 $v$ 前往 SZ 市的方法为：选择城市 $v$ 的一个祖先 $a$，支付购票的费用，乘坐交通工具到达 $a$。再选择城市 $a$ 的一个祖先 $b$，支付费用并到达 $b$。以此类推，直至到达 SZ 市。

对于任意一个城市 $v$，我们会给出一个交通工具的距离限制 $l_v$。对于城市 $v$ 的祖先 A，只有当它们之间所有道路的总长度不超过 $l_v$  时，从城市 $v$ 才可以通过一次购票到达城市 A，否则不能通过一次购票到达。

对于每个城市 $v$，我们还会给出两个非负整数 $p_v,q_v$  作为票价参数。若城市 $v$ 到城市 A 所有道路的总长度为 $d$，那么从城市 $v$ 到城市 A 购买的票价为 $dp_v+q_v$。

每个城市的 OIer 都希望自己到达 SZ 市时，用于购票的总资金最少。你的任务就是，告诉每个城市的 OIer 他们所花的最少资金是多少。

inputFormat:
第一行包含两个非负整数 $n,t$，分别表示城市的个数和数据类型（其意义将在「提示与说明」中提到）。

接下来 $2 \sim n$ 行，每行描述一个除 SZ 之外的城市。其中第 $v$ 行包含五个非负整数 $f_v,s_v,p_v,q_v,l_v$，分别表示城市 $v$ 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。

请注意：输入不包含编号为 1 的 SZ 市，第 $2\sim n$ 行分别描述的是城市 $2$ 到城市 $n$。

outputFormat:
输出包含 $n-1$ 行，每行包含一个整数。

其中第 $v$ 行表示从城市 $v+1$ 出发，到达 SZ 市最少的购票费用。

同样请注意：输出不包含编号为 1 的 SZ 市。

hint:
从每个城市出发到达 SZ 的路线如下（其中箭头表示一次直达）：

城市 $2$：只能选择 $2 \rightarrow 1$，花费为 $2 \times 20 + 0 = 40$。

城市 $3$：只能选择 $3 \rightarrow 1$，花费为 $5 \times 10 + 100 = 150$。

城 市 $4$ ： 由于 $4 + 2 =6 \leq l_4 = 10$，故可以选择 $4\rightarrow1$。若选择 $4 \rightarrow 1$，花费为 $(4 +2) \times 10 + 10 = 70$ ； 若选择 $4 \rightarrow 2 \rightarrow 1$，则花费为 $(4\times 10 + 10) + (2 \times  20 + 0) =90$；因此选择 $4 \rightarrow 1$。

城市 $5$：只能选择 $5\rightarrow 2\rightarrow 1$，花费为 $(9 \times 1 +100) + (2 \times  20 + 0) = 149$；无法选择 $5 \rightarrow 1$，因为 $l_5 =10$，而城市 $5$ 到城市 $1$ 总路程为 $9 + 2 = 11 \gt 5$，城市 $5$ 不能直达城市 $1$。

城市 $6$：若选择 $6 \rightarrow 1$，花费为 $(5 + 5) \times 20 + 100 = 300$；若选择 $6 \rightarrow 3 \rightarrow 1$，花费为 $(5 \times 20 + 100) + (5 \times 10 + 100) = 350$；因此选择 $6 \rightarrow 1$。

城市 $7$：选择 $7 \rightarrow 4 \rightarrow 1$，花费为 $(4 \times 20 + 0) + ((4 + 2) \times 10 + 10) = 150$；

其他方案均比该方案差。

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

### 数据范围

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

对于所有数据，$n\leq 2 \times 10^5, 0 \leq p_v \leq 10^6,\ 0 \leq q_v \leq 10^{12},\ 1\leq f_v<v,\ 0<s_v\leq lv \leq 2 \times 10^{11}$，且任意城市到 SZ 市的总路程长度不超过 $2 \times 10^{11}$。

输入的 $t$ 表示数据类型，$0\leq t<4$，其中：
- 当 $t=0$ 或 $2$ 时，对输入的所有城市 $v$，都有 $f_v=v-1$，即所有城市构成一个以 SZ 市为终点的链；
- 当 $t=0$ 或 $1$ 时，对输入的所有城市 $v$，都有 $l_v=2 \times 10^{11}$，即没有移动的距离限制，每个城市都能到达它的所有祖先；
- 当 $t=3$ 时，数据没有特殊性质。


title: [USACO03FALL] Cow Exhibition G

description:
奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 $N$ 头奶牛进行了面试，确定了每头奶牛的智商和情商。

贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。

inputFormat:
第一行：单个整数 $N$，$1 \le N \le 400$。

第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数：$S_i$ 和 $F_i$，表示第 $i$ 头奶牛的智商和情商，− $1000 \le S_i;F_i \le 1000$。

outputFormat: 输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 $0$。

hint:
选择第一头，第三头，第四头奶牛，智商和为−5+6+2 = 3，情商和为7−3+1 = 5。再加

入第二号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的


title: 2038年问题

description:
网络时代，机会与危机共存。“千年虫”解决之后，会不会有新的“虫”出现？回答是肯定的，“2038年”就是一个新的关卡。

也许大家都已经知道计算机的2000年问题是什么概念，但是什么时候又冒出来一个2038年问题的呢？

用C语言编制的程序不会碰到2000年问题，但是会有2038年问题。这是因为，大多数C语言程序都使用到一个叫做“标准时间库”的程序库，这个时间库用一个标准的4字节也就是32位的形式来储存时间信息。

当初设计的时候，这个4字节的时间格式把1970年1月1日凌晨0时0分0秒作为时间起点，这时的时间值为0。以后所有的时间都是从这个时间开始一秒一秒累积得来的。

比方说如果时间已经累积到了919642718这个数值，就是说这时距离1970年1月1日凌晨0时0分0已经过去了919642718秒，换算一下就应该是1999年2月21日星期天16时18分38秒。

这样计算时间的好处在于，把任意两个时间值相减之后，就可以很迅速地得到这两个时间之间相差的秒数，然后你可以利用别的程序把它换算成明白易懂的年月日时分秒的形式。

一个4字节也就是32位的存储空间的最大值是2147483647，请注意！2038年问题的关键也就在这里———当时间一秒一秒地跳完2147483647那惊心动魄的最后一秒后，它就会转为负数也就是说时间无效。那一刻的准确的时间为2038年1月19日星期二晚上03:14:07，之后所有用到这种“标准时间库”的C语言程序都会碰到时间计算上的麻烦。

你要解决的问题是，现有一台计算机，表示时间的变量长度为N位。给定一个“时间起点”，求出对于这个“时间起点”时间，最后的有效时间是什么时候。

inputFormat:
第一行为数据组数T

第2……T+1行，每行7个数字描述一组数据，分别为表示时间的变量长度（二进制位数），然后是“时间起点”的年份，月份，日期，小时，分钟，秒数。

outputFormat: T行，对于每组数据，输出1行，6个数字，分别表示最后的有效时间的年份，月份，日期，小时，分钟，秒数。


title: 迷宫

background: 无

description: 小希非常喜欢玩迷宫游戏，现在她自己设计了一个迷宫游戏。在她设计的迷宫中，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间 A 和 B，那么既可以通过它从房间 A 走到房间 B，也可以通过它从房间 B 走到房间 A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从 $5$ 到达 $8$。

inputFormat:
输入包含多组数据，每组数据是一个以 `0 0` 结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为 $1$，且不超过 $100000$。每两组数据之间有一个空行。

整个文件以两个 `-1` 结尾。

outputFormat: 对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出 `1`，否则输出 `0`。

hint: 无


title: [CERC2016] 爵士之旅 Jazz Journey

description:
Ivan正在为他的爵士乐队计划一场规模盛大的欧洲巡演。在欧洲一共有n个城市，编号依次为1到n。Ivan计划举办d场演出，分别在城市a\_1,a\_2,...,a\_d，并且严格遵循这个顺序，而且不会在同一个城市连续巡演两次（即a\_i!=a\_{i+1}），但在整个过程中，他可能在一个城市巡演多次。最终，他一定会回到开始的城市进行巡演（即a\_1=a\_d）。

Ivan每次总是选择搭乘一趟从a\_i到a\_{i+1}的直达航班。然而，他希望变得聪明一些，尽量节省机票的开支。你也知道，机票的价格取决于供给和需求，比如一张单程票可能会比相同目的地的双程票还要贵。

一共有两种可以购买的机票：

1.从a到b的单程票，每张只能从a飞到b一次，但不能从b飞到a。

2.从a到b的双程票，只需购买一张，就能从a飞到b一次，然后从b飞回a一次，但先从b飞回a是不允许的。当然，你也可以选择从a飞到b之后就再也不返回a。

给定可以购买的机票集合，每种机票都是无限量供应的。请帮助Ivan找到一种最省钱的方案。你可以认为合法方案必然存在。

inputFormat:
第一行包含两个正整数n,d(2<=n,d<=300000)，分别表示城市的个数和巡演的次数。

第二行包含d个正整数a\_1,a\_2,...,a\_d(1<=a\_i<=n,a\_i!=a\_{i+1},a\_1=a\_d)，依次表示巡演计划中每一场所在的城市。

接下来一行包含一个正整数m(3<=m<=300000)，表示机票的种类数。

接下来m行，每行首先是两个正整数s\_i,d\_i(1<=s\_i,d\_i<=n,s\_i!=d\_i)，分别表示起点与终点；接下来一个字符t\_i，表示机票的类型，其中“O”表示单程票，“R”表示双程票；最后是一个正整数p\_i(1<=p\_i<=10^9)，表示票价。

outputFormat: 输出一行一个整数，即完成巡演所需支付的最小机票总费用。


title: [CERC2016] 关键的膝盖 Key Knocking

description:
Goran正在从他的膝盖手术中恢复，并正在试验用于存储的智能卡加密密钥。在这个问题中，一个密钥是指一个长度为3n的二进制序列，其中n是正整数。序列的每一位从左往右依次被编号为1到3n。一个密钥的权值是指相邻位不同的位置个数再加上1。比如：“000”的权值是1，“011010100”的权值是7。

他发现他可以发送小型脉冲电流来修改智能卡的电路，从而修改密钥。确切地说，他可以不断进行下面的操作：选择任意两个相邻的位，然后同时取反它们。比如他可以通过一次操作把“000”修改为“110”。

给定一个长度为3n的密钥，请操作不超过n次，将其修改为一个权值不少于2n的密钥。你可以认为合法解必然存在。

inputFormat: 包含一行一个01序列，表示初始密钥，保证长度一定为3n，且1<=n<=100000。

outputFormat:
第一行包含一个整数m，表示操作的次数，你需要保证0<=m<=n。

第二行包含m个正整数a\_1,a\_2,...,a\_m(1<=a\_i<n)，依次表示每次翻转第a\_i和第(a\_i)+1位。

如果初始密钥的权值已经不小于2n，你可以仅输出一行一个整数0。


title: [CQOI2017] 小Q的棋盘

description:
小 Q 正在设计一种棋类游戏。

在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 $V$ 个格点，编号为 $0,1,2,\cdots, V- 1$，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小 Q 现在想知道，当棋子从格点 $0$ 出发，移动 $N$ 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

inputFormat:
第一行包含2个正整数 $V, N$，其中 $V$ 表示格点总数，$N$ 表示移动步数。

接下来 $V-1$ 行，每行两个数 $a_i,b_i$，表示编号为$a_i,b_i$ 的两个格点之间有连线。

outputFormat: 输出一行一个整数，表示最多经过的格点数量。

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

从格点 $0$ 出发移动 $2$ 步。经过 $0, 1, 2$ 这 $3$ 个格点。

【输入输出样例 2 说明】

一种可行的移动路径为 $0 \to 1 \to 3 \to 5 \to 3 \to 7$，经过 $0, 1, 3, 5, 7$ 这 $5$ 个格点。

【数据规模与约定】

对于 $100\%$ 的测试点，$1\le N,V ≤ 100$，$0 ≤a_i,b_i< V$。


title: [CQOI2017] 小Q的草稿

description:
Q 是个程序员。

众所周知，程序员在写程序的时候经常需要草稿纸。小 Q 现在需要一张草稿纸用来画图，但是桌上只有一张草稿纸，而且是一张被用过很多次的草稿纸。

草稿纸可以看作一个二维平面，小 Q 甚至已经给它建立了直角坐标系。以前每一次草稿使用过的区域，都可以近似的看作一个平面上的一个三角形，这个三角形区域的内部和边界都不能再使用。当然了，以前的草稿也没有出现区域重叠的情况。

小 Q 已经在草稿纸上画上了一些关键点，这些关键点都在没使用过的区域。小 Q 想把这些关键点两两之间尽可能的用线段连接起来。连接两个关键点的线段有可能会穿过已经用过的草稿区域，这样显然不允许。于是小 Q 就想知道，有多少对关键点可以被线段连接起来，而且还不会穿过已经用过的区域。为了方便，小 Q 保证任意三个关键点不会共线。

inputFormat:
第一行包含两个整数V, T，表示草稿纸上的关键点数量和三角形区域数量。

接下来V行，每行两个整数x, y，表示一个关键点的坐标 (x,y) 。

接下来T行，每行六个整数$x_1,y_1,x_2,y_2,x_3,y_3$，表示一个三角形区域的三个顶点坐标分别是 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，保证三角形的面积大于0。

outputFormat: 输出一行，一个整数，表示能够被线段连接起来的关键点有多少对。

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

整个草稿纸是全新的，任意两个关键点都可以连线。

【输入输出样例 2 说明】

如图所示，任意两个关键点的连线都被挡住了。

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

【数据规模与约定】

对于 100%的测试点，0 ≤ 所有坐标 ≤ $10^8$，且都是整数。

```cpp
NO 1  2  3   4   5   6   7    8    9   10
V 10 20 50 100 200 400 600 1000 1000 1000
T 10 20 50 100 200 400 600 1000 1000 1000
```


title: [CQOI2017] 小 Q 的表格

description:
小 Q 是个程序员。

作为一个年轻的程序员，小 Q 总是被老 C 欺负，老 C 经常把一些麻烦的任务交给小 Q 来处理。每当小 Q 不知道如何解决时，就只好向你求助。

为了完成任务，小 Q 需要列一个表格，表格有无穷多行，无穷多列，行和列都从 $1$ 开始标号。为了完成任务，表格里面每个格子都填了一个整数，为了方便描述，小 Q 把第 $a$ 行第 $b$ 列的整数记为 $f(a, b)$。为了完成任务，这个表格要满足一些条件：

1. 对任意的正整数 $a, b$，都要满足 $f(a, b) = f(b, a)$；
2. 对任意的正整数 $a, b$，都要满足 $b \times f(a, a + b) = (a + b) \times f(a, b)$。

为了完成任务，一开始表格里面的数很有规律，第 $a$ 行第 $b$ 列的数恰好等于 $a \times b$，显然一开始是满足上述两个条件的。为了完成任务，小 Q 需要不断的修改表格里面的数，每当修改了一个格子的数之后，为了让表格继续满足上述两个条件，小 Q 还需要把这次修改能够波及到的全部格子里都改为恰当的数。由于某种神奇的力量驱使，已经确保了每一轮修改之后所有格子里的数仍然都是整数。为了完成任务，小 Q 还需要随时获取前 $k$ 行前 $k$ 列这个有限区域内所有数的和是多少，答案可能比较大，只需要算出答案 ${} \bmod 1,000,000,007$ 之后的结果。

inputFormat:
输入文件第一行包含两个整数 $m, n$，表示共有 $m$ 次操作，所有操作和查询涉及到的行编号和列编号都不超过 $n$。

接下来 $m$ 行，每行四个整数 $a, b, x, k$，表示把第 $a$ 行 $b$ 列的数改成 $x$，然后把它能够波及到的所有格子全部修改，保证修改之后所有格子的数仍然都是整数，修改完成后计算前 $k$ 行前 $k$ 列里所有数的和。

outputFormat: 输出共 $m$ 行，每次操作之后输出一行，表示答案 ${} \bmod 1,000,000,007$ 之后的结果。

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

一开始，表格的前 $3$ 行前 $3$ 列如图中左边所示。前 $2$ 次操作后表格没有变化，第 $3$ 次操作之后的表格如右边所示。

```cpp
1 2 3     2  4  6
2 4 6     4  4 12
3 6 9     6 12  9
```

**【数据范围】**

对于 $100 \%$ 的测试点，$1 \le m \le {10}^4$，$1 \le a, b, k \le n \le 4 \times {10}^6$，$0 \le x \le {10}^{18}$。

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


title: [SDOI2017] 数字表格

background:
Doris 刚刚学习了 fibonacci 数列。用 $f_i$ 表示数列的第 $i$ 项，那么

$$f_0=0,f_1=1$$

$$f_n=f_{n-1}+f_{n-2},n\geq 2$$

description:
Doris 用老师的超级计算机生成了一个 $n\times m$ 的表格，

第 $i$ 行第 $j$ 列的格子中的数是 $f_{\gcd(i,j)}$，其中 $\gcd(i,j)$ 表示 $i,j$ 的最大公约数。

Doris 的表格中共有 $n\times m$ 个数，她想知道这些数的乘积是多少。

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

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

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

接下来 $T$ 行，每行两个整数 $n, m$，表示一组数据。

outputFormat: 对于每组数据，输出一行一个整数表示答案。

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

- 对于 $10\%$ 的数据，保证 $n,m\leq 10^2$。
- 对于 $30\%$ 的数据，保证 $n,m\leq 10^3$。
- 另有 $30\%$ 的数据，保证 $T\leq 3$。
- 对于 $100\%$ 的数据，保证 $1 \leq T\leq 10^3$，$1\leq n,m\leq 10^6$。


title: [HAOI2017] 新型城市化

description:
Anihc 国有 $n$ 座城市。城市之间存在一些贸易合作关系，如果城市 $x$ 与城市 $y$ 之间存在贸易协定，那么城市 $x$ 和城市 $y$ 则是一对贸易伙伴（注意： $(x,y)$ 和 $(y,x)$ 是同一对城市）。

为了实现新型城市化，实现统筹城乡一体化以及发挥城市群辐射与带动作用，国家决定规划新型城市关系。一些城市能够被称为城市群的条件是：这些城市两两都是贸易伙伴。由于Anihc 国之前也一直很重视城市关系建设，所以可以保证在目前已存在的贸易合作关系的情况下 Anihc 的 $n$ 座城市可以恰好被划分为不超过两个城市群。

为了建设新型城市关系 Anihc 国想要选出两个之前并不是贸易伙伴的城市，使这两个城市成为贸易伙伴，并且要求在这两个城市成为贸易伙伴之后，最大城市群的大小至少比他们成为贸易伙伴之前的最大城市群的大小增加 $1$。

Anihc 国需要在下一次会议上讨论扩大建设新型城市关系的问题，所以要请你求出在哪些城市之间建立贸易伙伴关系可以使得这个条件成立，即建立此关系前后的最大城市群的大小至少相差 $1$。

inputFormat:
第一行 $2$ 个整数 $n,m$，表示城市的个数，目前还没有建立贸易伙伴关系的城市的对数。

接下来 $m$ 行，每行 $2$ 个整数 $x,y$ 表示城市 $x,y$ 之间目前还没有建立贸易伙伴关系。

outputFormat:
第一行 $1$ 个整数 $\text{ans}$，表示符合条件的城市的对数。

接下来 $\text{ans}$ 行，每行两个整数，表示一对可以选择来建立贸易伙伴关系的城市。对于一对城市 $x,y$，请先输出编号更小的那一个。最后城市对与城市对之间顺序请按照字典序从小到大输出。

hint:
数据点 $1$：$n\le 16$；

数据点 $2$：$n\le 16$；

数据点 $3\sim 5$：$n\le 100$；

数据点 $6$：$n\le 500$；

数据点 $7\sim10$：$n\le 10^4$。

对于所有的数据保证： $n \le 10^4,0 \le m \le \min(1.5\times 10^5,\dfrac{n(n-1)}{2})$。保证输入的城市关系中不会出现 $(x,x)$ 这样的关系，同一对城市也不会出现两次（无重边，无自环）。


title: [NOIP2014 普及组] 珠心算测验

background: NOIP2014 普及 T1

description:
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

inputFormat:
共两行，第一行包含一个整数 $n$，表示测试题中给出的正整数个数。

第二行有 $n$ 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

outputFormat: 一个整数，表示测验题答案。

hint:
【样例说明】

由 $1+2=3,1+3=4$，故满足测试要求的答案为 $2$。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于 $100\%$ 的数据，$3 \leq n \leq 100$，测验题给出的正整数大小不超过 $10,000$。


title: [HAOI2017] 供给侧改革

description:
你调查了某个产业近来 $n$ 个时期的供求关系平衡情况，每个时期的情况都用 $0$ 或 $1$ 中的一个数字来表示。于是这就是—个长度为 $n$ 的 $\texttt{01}$ 字符串 $S$。为了更好的了解这一些数据，你需要解决一些询问，我们令 $\text{data}(L,R)$ 表示：在字符串 $S$ 中，起始位置在 $[L,R]$ 之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问 $L,R$，求：

$$ans = \sum_{L \leqslant i < R} \text{data}(i,R)$$

数据范围保证，串 $S$ 中的每一位都是在 $0$ 和 $1$ 之间随机产生的。

inputFormat:
第一行 $2$ 个整数 $n,Q$，表示字符串的长度，以及询问个数。

接下来一行长度为 $n$ 的一个 $\texttt{01}$ 串 $S$。

接下来 $Q$ 行，每行 $2$ 个整数 $L,R$，一个询问 $L,R$。

outputFormat: 共 $Q$ 行，每行一个整数，表示对应询问的答案。

hint:
【数据规模与约定】

|数据点|$n$ 的规模|$Q$ 的规模|
|:-:|:-:|:-:|
|$1,2$|$\leqslant 20$|$\leqslant 20$|
|$3,4$|$\leqslant 100$|$\leqslant 100$|
|$5,6$|$\leqslant 5 \times 10^3$|$\leqslant 5 \times 10^3$|
|$7,8,9,10$|$\leqslant 10^5$|$\leqslant 10^5$|

对于所有的数据保证：$n \leqslant 10^5$，$Q \leqslant 10^5$，$1 \leqslant L < R \leqslant n$，$\texttt{01}$ 串随机生成。


title: [NOIP2014 提高组] 解方程

background: NOIP2014 提高组 D2T3

description:
已知多项式方程：

$$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$$

求这个方程在 $[1,m]$  内的整数解（$n$  和 $m$  均为正整数）。

inputFormat:
输入共 $n + 2$  行。

第一行包含 $2$  个整数 $n, m$ ，每两个整数之间用一个空格隔开。

接下来的 $n+1$  行每行包含一个整数，依次为 $a_0,a_1,a_2\ldots a_n$ 。

outputFormat:
第一行输出方程在 $[1,m]$  内的整数解的个数。

接下来每行一个整数，按照从小到大的顺序依次输出方程在 $[1,m]$  内的一个整数解。


title: [HAOI2017] 八纵八横

description:
Anihc 国有 $n$ 个城市，这 $n$ 个城市从 $1$ 到 $n$ 编号，$1$ 号城市为首都。城市间初始时有 $m$ 条高速公路，每条高速公路都有一个非负整数的经济影响因子，每条高速公路的两端都是城市（可能两端是同一个城市），保证任意两个城市都可以通过高速公路互达。

国正在筹划“八纵八横”的高铁建设计划，计划要修建一些高速铁路，每条高速铁路两端也都是城市（可能两端是同一个城市)，也都有一个非负整数的经济影响因子。国家还计划在“八纵八横”计划建成之后，将“一带一路”扩展为“一带一路一环”，增加“内陆城市经济环”即选择一条从首都出发沿若一系列高铁与高速公路走的路径，每条高铁或高速公路可以经过多次，每座城市也可以经过多次，最后路径又在首都结束。令“内陆城市经济环”的 GDP 为依次将这条路径上所经过的高铁或高速公路的经济影响因子异或起来（一条路经过多次则会被计算多次）。

现在 Anihc 在会议上讨论“八纵八横”的建设计划方案，他们会不断地修改计划方案，希望你能实时反馈对于当前的“八纵八横”的建设计划的方案“内陆城市经济环”的最大是多少。

初始时，八纵八横计划中不包含任何一条高铁，有以下 $3$ 种操作：

`Add x y z`

在计划中给在城市 $x$ 和城市 $y$ 之间建设一条高铁，其经济影响因子为 $z$，如果这是第 $k$ 个 `Add` 操作，则将这条高铁命名为 $k$ 号高铁。

`Cancel k`

将计划中的 $k$ 号高铁取消掉，保证此时 $k$ 号高铁一定存在。

`Change k z`

表示将第 $k$ 号高铁的经济影响因子更改为 $z$，保证此时 $k$ 号高铁一定存在。

inputFormat:
第一行 $3$ 个整数 $n,m,Q$，表示城市个数，高速公路条数，操作个数。

接下来 $m$ 行，每行 $3$ 个整数表示高速公路的信息。

接下来 $Q$ 行，每行为一个操作。

注意：输入的所有经济影响因子都将以二进制的形式从高位到低位给出。

outputFormat:
第一行一个整数。表示如果不修建任何高铁，“内陆城市经济环”的 GDP 最大值。

接下 $Q$ 行每行一个整数，表示进行了对应的每一个操作之后，对于当前的计划，“内陆城市经济环”的 GDP 最大值。

注意：输出的答案也要以二进制的形式从高位到低位给出。


title: [HAOI2017] 方案数

description:
考虑定义非负整数间的“$ \subseteq $”，如果 $ a \subseteq b $，那么 $ a \land b = a $，其中 $ \land $ 表示二进制下的“与”操作。

考虑现在有一个无限大的空间，现在你在 $ (0, 0, 0) $，有三种位移操作。

一、$(x,y,z)\to(x',y,z)$ if $x\subseteq x'$
二、$(x,y,z)\to(x,y',z)$ if $y\subseteq y'$
三、$(x,y,z)\to(x,y,z')$ if $z\subseteq z'$

由于来自东方的神秘力量，有些点被屏蔽了，也就是不能经过了。现在问你到某个点 $ (n, m, r) $ 的方案数，答案对 $ 998244353 $ 取模。

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

接下来一行一个整数 $ o $，表示障碍物的数量。

接下来 $ o $ 行，每行三个整数 $ x, y, z $ 表示障碍物的坐标，$ 0 \le x \le n, 0 \le y \le m, 0 \le z \le r $，且障碍物不在 $ (0, 0, 0) $ 和 $ (n, m, r) $ 上，障碍物不会重复。

outputFormat: 一行一个整数，代表要求的答案。


title: [SDOI2005] 位图

description:
现在我们给出一个 $n\ \times m$ 的单色位图，且该图中至少含有一个白色的像素。我们用 $(i,j)$ 来代表第 $i$ 行第 $j$ 列的像素，并且定义两点 $p_1=(i_1,j_1)$ 和 $p_2=(i_2,j_2)$ 之间的距离为：

$$d(p_1,p_2)=|i_1-i_2|+|j_1-j_2|$$

### 任务

请写一个程序，读入该位图，并对于每个像素，计算出离该像素最近的白色像素与它的距离。把结果输出。

inputFormat:
第一行包括两个用空格分开的整数 $n$ 和 $m$，$1 \le n \le 150$，$1 \le m \le 150$。

以下的 $n$ 行每行包括一个长度为 $m$ 的整数为 $0$ 或 $1$，在第 $i+1$ 行的第 $j$ 个字符如果为 $1$，那么表示像素 $(i,j)$ 为白的，否则为黑的。

outputFormat: 输出一个 $n\ \times m$ 的数表，其中的第 $i$ 行的第 $j$ 个数字为 $f(i,j)$ 表示像素 $(i,j)$ 到最近的白色像素的距离。


title: [HNOI2005] 汤姆的游戏

description: 汤姆是个好动的孩子,今天他突然对圆规和直尺来了兴趣。于是他开始在一张很大很大的白纸上画很多很多的矩形和圆。画着画着,一不小心将他的爆米花弄撒了,于是白纸上就多了好多好多的爆米花。汤姆发现爆米花在白纸上看起来就像一个个点,有些点落在矩形或圆内部,而有些则在外面。于是汤姆开始数每个点在多少个矩形或圆内部。毕竟汤姆还只是个孩子,而且点、矩形和圆又非常多。所以汤姆数了好一会都数不清,于是就向聪明的你求助了。你的任务是：在给定平面上N个图形(矩形或圆)以及M个点后，请你求出每个点在多少个矩形或圆内部(这里假设矩形的边都平行于坐标轴)。

inputFormat: 从文件input.txt中读入数据，文件第一行为两个正整数N和M，其中N表示有多少个图形(矩形或圆)，M表示有多少个点。接下来的N行是对每个图形的描述，具体来说，第i+1行表示第i个图形。先是一个字母,若该字母为“r”，则表示该图形是一个矩形,这时后面将有4个实数x1,y1,x2,y2，表示该矩形的一对对角顶点的坐标分别为(x1,y1)和(x2,y2)；若该字母为“c”，则表示该图形是一个圆,这时后面将有3个实数x,y,r,表示该圆以(x,y)为圆心并以r为半径。最后M行是对每个点的描述，其中每行将有两个实数x,y,表示一个坐标为(x,y)的点。

outputFormat: 输出文件output.txt中包含M行,每行是一个整数,其中第i行的整数表示第i个点在多少个图形内部(当某点在一个图形的边界上时，我们认为该点不在这个图形的内部)。


title: [HNOI2005] 木梳

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

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

inputFormat: 从文件input.txt中读入数据，文件第一行为整数L，其中4<=L<=100000，且有50%的数据满足L<=10^4，表示木板下侧直线段的长。第二行为L个正整数A1,A2,…,AL，其中1<Ai<=10^8，表示第i段的高度。

outputFormat: 输出文件output.txt中仅包含一个整数D，表示为使梳子面积最大，需要从木板上挖掉的格子数。


title: [HNOI2005] 数三角形

outputFormat: 输出文件output.txt中仅包含一个整数T，表示有多少个三角形的边界都没有被删除。


title: [HNOI2005] 分形


title: [HNOI2005] 星际贸易

outputFormat: 如果可以找到这样的方案，那么输出文件output.txt中包含两个整数X和Y。X表示贸易额，Y表示净利润并且两个数字之间用一个空格隔开。如果不能完成这次星际贸易，那么输出文件output.txt中包含 “Poor Coke!”（不包括引号）。


title: [HNOI2005] 虚拟内存

description:
操作系统中一种重要的存储管理技术就是虚拟内存技术。操作系统中允许进程同时运行，也就是并行。每个进程都有其相对独立的数据块（进程运行的过程中将对其进行读写操作）。理想的情况下，这些数据块都应该存放在内存中，这样才能实现高效的读写操作。但事实上，内存的容量有限，每个进程只能把一部分数据放在内存中，为了解决这个矛盾，提出了虚拟内存技术。

虚拟内存技术的基本原理是：对进程而言，内存空间是无限大的，进程可以随意地读写数据，而对操作系统内部而言，利用外存来模拟扩充的内存空间，进程要求访问某个内存单元时，交由操作系统处理，操作系统首先在内存中查找该单元是否存在，如果存在，查找成功，否则转入外存查找（一定存在于外存中）。

就存储介质的物理性质而言，内存的访问速度相对于外存要快得多，因此对于每个进程来说操作系统应该把那些访问次数较多的数据存放在内存中，而把那些访问次数很少的数据放在外存中。如何选择内存中暂留的数据是一个很值得研究的问题，下面介绍一个内存管理中比较常用的算法：

内存中的数据以页为基本存储单位，进程的读写操作都针对页来进行。实际内存空间被分割成n页，虚拟内存空间的页数往往要多得多。某一时刻，进程需要访问虚存编号为P的页，该算法的执行步骤如下：

a.    首先在内存中查找，如果该页位于内存中，查找成功，转d，否则继续下面的操作；

b.    寻找内存中是否存在空页（即没有装载任何数据页的页面），若有，则从外存中读入要查找页，并将该页送至内存中的空页进行存储，然后转d，否则继续下面的操作；

c.    在内存中寻找一个访问次数最少的页面（如果存在多个页面的访问次数同时为最少，则选取最早读入数据进入内存的那个页面），从外存中读入要查找页，替换该页。

d.    结束

所谓访问次数是指从当前页面进入内存到该时刻被访问的次数，如果该页面以前进入过内存并被其它页面替换，那么前面的访问次数不应计入这个时刻的访问次数中。

你的任务是设计一个程序实现上述算法。

测试数据将会提供 $m$ 条读写内存的命令，每条命题提供要求访问的虚拟内存页的编号 $P$ 。你的程序要求能够模拟整个 $m$ 条命令的全部执行过程，所有的命令是按照输入的先后执行的，最开始的时候内存中的 $n$ 页全为空。

inputFormat: 输入共 $m + 1$ 行，第 $1$ 行为 $n (n \le 10000)$ 和 $m (m \le 1000000)$ ，分别表示内存页数和读写内存命令条数。接下来有 $m$ 行，其中第 $i+1$ 行有一个正整数 $P_i (P_i \le 10^9)$ ，表示第i条读写内存命令需要访问的虚拟内存页的编号。

outputFormat: 输出中仅包含一个正整数，表示在整个模拟过程中，在内存中直接查找成功的次数（即上面的算法只执行步骤 a 的次数）。


title: [HNOI2006] 超级英雄

description:
现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。

这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？

inputFormat:
输入的第一行是两个正整数 $n$ 和 $m$ ($0 < n < 1001, 0 < m < 1001$)表示总共有 n 种“锦囊妙计”，编号为 $0 \sim n-1$，总共有 $m$ 个问题。

以下的m行，每行两个数，分别表示第 $m$ 个问题可以使用的“锦囊妙计”的编号。

**注意**，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。

outputFormat:
输出的第一行为最多能通过的题数 $p$，接下来 $p$ 行，每行为一个整数，第 $i$ 行表示第 $i$ 题使用的“锦囊妙计的编号”。

如果有多种答案，那么任意输出一种，本题使用 Special Judge 评判答案。

hint: 感谢@zhouyonglong 提供special Judge


title: [HNOI2006] 鬼谷子的钱袋

description:
鬼谷子非常聪明，正因为这样，他非常繁忙，经常有各诸侯的特派员前来向他咨询时政。

有一天，他在咸阳游历的时候，朋友告诉他在咸阳最大的拍卖行（聚宝商行）将要举行一场拍卖会，其中有一件宝物引起了他极大的兴趣，那就是无字天书。

但是，他的行程安排得很满，他已经买好了去邯郸的长途马车票，不巧的是出发时间是在拍卖会快要结束的时候。于是，他决定事先做好准备，将自己的金币数好并用一个个的小钱袋装好，以便在他现有金币的支付能力下，任何数目的金币他都能用这些封闭好的小钱的组合来付账。

鬼谷子也是一个非常节俭的人，他想方设法使自己在满足上述要求的前提下，所用的钱袋数最少，并且不有两个钱袋装有相同的大于 $1$ 的金币数。假设他有 $m$ 个金币，你能猜到他会用多少个钱袋，并且每个钱袋装多少个金币吗？

inputFormat: 包含一个整数，表示鬼谷子现有的总的金币数目 $m$。其中，$1 \le m \le {10}^9$。

outputFormat:
两行，第一行一个整数 $h$，表示所用钱袋个数。

第二行表示每个钱袋所装的金币个数，由小到大输出，空格隔开。


title: [HNOI2006] 潘多拉的宝盒

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

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

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

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

outputFormat: 输出一行一个数$t$，表示最长升级序列的长度。


title: [HNOI2006] 最短母串问题

description: 给定  $n$ 个字符串  $(S_1,S_2,...,S_n)$，要求找到一个最短的字符串  $T$，使得这  $n$ 个字符串  $(S_1,S_2,...,S_n)$ 都是  $T$ 的子串。

inputFormat: 输入文件第一行是一个整数  $n$，表示给定的字符串个数。接下来  $n$ 行，每行有一个全由大写字母组成的字符串，。

outputFormat: 输出文件只有一行，为找到的最短的字符串  $T$。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。

hint: 对于 $100\%$ 的数据，$n\leq 12$，每个字符串的长度不超过  $50$。


title: [HNOI2006] 公路修建问题

description:
OI island 是一个非常漂亮的岛屿，自开发以来，到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association 组织成立了，旨在建立 OI island 的交通系统。

OI island 有 $n$ 个旅游景点，不妨将它们从 $1$ 到 $n$ 标号。现在，OIER Association 需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。

OIER Association 打算修 $n-1$ 条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率， OIER Association 希望在这 $n-1$ 条公路之中，至少有 $k$ 条 $(0 \le k \le n-1)$ 一级公路。OIER Association 也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。

而你的任务就是，在给定一些可能修建的公路的情况下，选择 $n-1$ 条公路，满足上面的条件。

inputFormat:
文件第一行有三个数 $n(1 \le n \le 10000)$，$k(0 \le k \le n-1),m(n-1 \le m \le 20000)$，这些数之间用空格分开。$N$ 和 $k$ 如前所述，$m$ 表示有 $m$ 对景点之间可以修公路。

以下的 $m-1$ 行，每一行有 $4$ 个正整数 $a,b,c_1,c_2$，（$1 \le a,b \le n,a \ne b,1 \le c_2 \le c_1 \le 30000$），表示在景点 $a$ 与 $b$ 之间可以修公路，如果修一级公路，则需要 $c_1$ 的花费，如果修二级公路，则需要 $c_2$ 的花费。

**在实际评测时，将只会有 $m-1$ 行公路**

outputFormat:
输出第一行有一个数据，表示花费最大的公路的花费。

接下来的 $n-1$ 行，每行有两个正整数 $t$ 和 $p$，$t$ 和 $p$ 表示在输入的第 $t$ 对（按照输入的顺序，从 $1$ 开始标号）景点之间修建 $p$ 级公路。

$n-1$ 条公路的输出必须按 $t$ 的大小递增，如果有多个方案使花费最大的公路花费最小，那么输出任意一个都可以。


title: [HAOI2017] 字符串

description:
给出一个字符串 $ s $ 和 $ n $ 个字符串 $ p_i $，求每个字符串 $ p_i $ 在 $ s $ 中出现的次数。注意这里两个字符串相等的定义稍作改变。

给定一个常数 $ k $，对于两个字符串 $ a, b $，如果 $ a = b $，那么满足：

一、$ |a| = |b| $

二、对于所有 $ a_i \neq b_i $ 以及 $ a_j \neq b_j $，满足 $ |i-j| < k $

如果 $ |a| = |b| \le k $，那么认为 $ a = b $。

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

第二行一个字符串 $ s $。

第三行一个整数 $ n $，接下来 $ n $ 行每行一个字符串表示 $ p_i $。

所有的字符 ASCII 码在 $ 33 $ 至 $ 126 $ 之间。

outputFormat: 输出 $ n $ 行，表示每个 $ p_i $ 在 $ s $ 中出现的次数。

hint:
对于 $ p_1 $，$ xz = xy, xz = yz $，因为都只有一个位置差异。

对于 $ p_2 $，$ y = x, y = y, y = z $，同理。

对于 $ p_3 $，$ xzy \neq xyz $，最大差 $ = 1 $ 不满足 $ < k = 1 $。

数据范围与提示

对于 $ 20\% $ 的数据，满足：$ |s|, \Sigma |p_i| \le 10^3 $

对于另外 $ 20\% $ 的数据，满足：$ n \le 100 $

对于另外 $ 20\% $ 的数据，满足：$ |s|, \Sigma |p_i| \le 5 \cdot 10^4 $

对于 $ 100\% $ 的数据，满足：$ |s|, \Sigma |p_i| \le 2 \cdot 10^5 $


title: [HAOI2016] 字符合并

description:
有一个长度为 $n$ 的 $01$ 串，你可以每次将相邻的 $k$ 个字符合并，得到一个新的字符并获得一定分数。

得到的新字符和分数由这 $k$ 个字符确定。你需要求出你能获得的最大分数。

inputFormat:
输入的第一行是两个整数，分别代表字符串长度 $n$ 和参数 $k$。

输入的第二行有 $n$ 个用空格隔开的非零即一的字符，第 $i$ 个字符表示初始串的第 $i$ 个字符。。

第 $3$ 到第 $(2^k + 2)$ 行，每行有一个字符和一个整数，第 $(i + 2)$ 行的字符 $c_i$ 个整数 $w_i$ 表示长度为 $k$ 的 $01$ 串连成二进制后按从小到大顺序得到的第 $i$ 种合并方案得到的新字符,  $w_i$ 表示对应的第 $i$ 种方案对应获得的分数。

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


title: [HAOI2014] 遥感监测

description:
外星人指的是地球以外的智慧生命。外星人长的是不是与地球上的人一样并不重要，但起码应该符合我们目前对生命基本形式的认识。比如，我们所知的任何生命都离不开液态水，并且都是基于化学元素碳（C）的有机分子组合成的复杂有机体。

ZDM 实验室的天文学家们已经执著地观测 ZDM-99 星球十多年了，这个被称为“战神”的红色星球让他们如此着迷。在过去的十多年中，他们经常有一些令人激动的发现。ZDM-99 星球表面有着明显的明暗变化。对这些明暗区域，天文学家们已经细致地研究了很多年，并且绘制出了较为详尽的地图，那些暗区是陆地，而亮区则是湖泊和海洋。他们一直坚信有水的地方，一定有生命的痕迹。

这天晚上的观测条件实在是空前的好，ZDM-99 星球也十分明亮，不时呈现出若干个激光点，天文学家们推定这些激光点极有可能存在地球以外的智慧生命。遗憾的是仅持续很短的一段时间，这些激光点就消失了。

ZDM 实验室的射电望远镜观测的区域有限，只可以遥感检测到一个半径为 $R$ 的圆形区域。为了能同时能检测到所有的激光点，ZDM 实验室需要要在一个水平的直线上尽快地安装多个的射电望远镜来。

不妨设，这条安放射电望远镜的水平直线为 X 轴，ZDM-99 星球激光点就处在 $P_1(x_1,y_1),P_1(x_1,y_1),\cdots,P_1(x_n,y_n)$（忽略 Z 坐标）

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

ZDM 实验室的天文学家们想知道，至少需要安装多少个射电望远镜才能检测到所有激光点。

inputFormat:
第 1 行，$N, R$ 分别表示激光点的个数和射电望远镜能检测到的半径。

第 $2$ 到 $N+1$ 行，$X_i,Y_i$ 表示 激光点的坐标位置。

outputFormat: 输出一行： 最少需要安装的射电望远镜数。


title: [HAOI2014] 穿越封锁线

description:
某敌占区是一个封闭的多边形，用相邻的顶点集合 $P_1(x_1,y_1)$，$P_2(x_2,y_2)$，$\cdots$，$P_n(x_n,y_n)$ 表示。

我方侦察员 ZDM-007 要穿越敌占区的封锁线，为了安全起见，ZDM-007 行走的路线垂直于 X 坐标轴，从南向北穿越。

现在已知侦察员 ZDM-007 所处的位置，你能算出他在穿越封锁线时，其路线在敌占区内的总长度？

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

inputFormat:
第一行：$n$ 表示多边形顶点的个数

接下来 $n$ 行：$x_i,x_i$ 表示多边形的顶点坐标。（按逆时针顺序给出）

最后一行：$X,Y$ 表示侦察员初始时所处的位置。

outputFormat: 侦察员穿越封锁线时，在敌占区内的总长度。（输出仅保留整数部分）


title: [HAOI2014] 走出金字塔

description:
在探险的过程中，考古学家 Dr. Kong 无意地被困在一个金字塔中。金字塔中的每个房间都是三角形。Dr. Kong 可以破壁走到相邻的房间去。例如，如果他目前处于三角形 $(2,2)$ 房间，那么他可以破壁走到三角形 $(2,1)$、$(2,3)$ 或 $(1,1)$ 房间。但破壁一面墙需要花费 $K$ 分钟时间，而考古学家 Dr. Kong 的体能只能支持他 $S$ 分钟。

好在 Dr. Kong 手中有这个金字塔地图，他发现金字塔有许多出口，一旦他进入一个有出口的三角形房间，他再用 $1$ 分钟就可以走出金字塔。

现在，你能否帮助 Dr. Kong 找到一个走出金字塔花费时间最少的出口？若能，输出 Dr. Kong 走出金字塔后还剩下的体能时间（应当大于或等于 $0$）；若不能，输出 $-1$。

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

inputFormat:
第一行共四个整数，$N,M,K,S$，其中，

- $N$ 表示金字塔的层数；
- $M$ 表示出口数；
- $K$ 表示破壁一面墙的时间；
- $S$ 表示考古学家 Dr. Kong 体能维持分钟数。

第二行有两个整数 $X_a,Y_a$ 表示考古学家 Dr. Kong 所在的位置；

第三行至第 $M+2$ 行，每行有两个整数 $X_i,Y_i$，表示有出口的三角形坐标位置。

outputFormat: 输出 Dr. Kong 走出金字塔后还剩下的体能时间；若不能，输出 $-1$。

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

对于全部数据，$1 \le N \le 10^6$，$0\le M\le 10^4$，$0<K\le 20$，$10\le S\le 10^4$。

所有的数据都是整数，且数据之间有一个空格。


title: [HAOI2014] 贴海报

description:
Bytetown 城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的 electoral 墙。

张贴规则如下：

1. electoral 墙是一个长度为 $N$ 个单位的长方形，每个单位记为一个格子；

2. 所有张贴的海报的高度必须与 electoral 墙的高度一致的；

3. 每张海报以 `A B` 表示，即从第 $A$ 个格子到第 $B$ 个格子张贴海报；

4. 后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断，张贴完所有海报后，在 electoral 墙上还可以看见多少张海报。

inputFormat:
第一行，两个正整数 $N,M$，分别表示 electoral 墙的长度和海报个数。

接下来 $M$ 行，每行两个正整数 $A_i,B_i$，表示每张海报张贴的位置。

outputFormat: 输出贴完所有海报后，在 electoral 墙上还可以看见的海报数。

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

**约束条件**

$10\le N \le 10000000,1\le M\le 1000,1\le A_i \le B_i \le 10000000$

所有的数据都是正整数，数据之间有一个空格。


title: [六省联考 2017] 期末考试

description:
有 $n$ 位同学，每位同学都参加了全部的 $m$ 门课程的期末考试，都在焦急的等待成绩的公布。

第 $i$ 位同学希望在第 $t_i$ 天或之前得知**所有**课程的成绩。如果在第 $t_i$ 天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生 $C$ 不愉快度。

对于第 $i$ 门课程，按照原本的计划，会在第 $b_i$ 天公布成绩。

有如下两种操作可以调整公布成绩的时间:
1. 将负责课程 $X$ 的部分老师调整到课程 $Y$，调整之后公布课程 $X$ 成绩的时间推迟一天，公布课程 $Y$ 成绩的时间提前一天；每次操作产生 $A$ 不愉快度。
2. 增加一部分老师负责学科 $Z$，这将导致学科 $Z$ 的出成绩时间提前一天；每次操作产生 $B$ 不愉快度。

上面两种操作中的参数 $X, Y, Z$ 均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。

现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。

inputFormat:
第一行三个非负整数 $A, B, C$，描述三种不愉快度，详见【题目描述】；
第二行两个正整数 $n, m$，分别表示学生的数量和课程的数量；
第三行 $n$ 个正整数 $t_i$，表示每个学生希望的公布成绩的时间；
第四行 $m$ 个正整数 $b_i$，表示按照原本的计划，每门课程公布成绩的时间。

outputFormat: 输出一行一个整数，表示最小的不愉快度之和。


title: [六省联考 2017] 相逢是问候

description:
> Informatik verbindet dich und mich.
> 信息将你我连结。

B 君希望以维护一个长度为 $n$ 的数组，这个数组的下标为从 $1$ 到 $n$ 的正整数。

一共有 $m$ 个操作，可以分为两种：

- `0 l r` 表示将第 $l$ 个到第 $r$ 个数（ $a_l,a_{l+1} ...a_r$）中的每一个数 $a_i$ 替换为 $c^{a_i}$，即 $c$ 的 $a_i$ 次方，其中 $c$ 是输入的一个常数，也就是执行赋值 $a_i = c^{a_i}$。

- `1 l r` 求第 $l$ 个到第 $r$ 个数的和，也就是输出： $\sum_{i=l}^{r}a_i$

因为这个结果可能会很大，所以你只需要输出结果 $\bmod \space p$ 的值即可。

inputFormat:
第一行有四个整数 $n, m, p, c$，所有整数含义见问题描述。
接下来一行 $n$ 个整数，表示 $a$ 数组的初始值。
接下来 $m$ 行，每行三个整数，其中第一个整数表示了操作的类型。

- 如果是 $0$ 的话，表示这是一个修改操作，操作的参数为 $l, r$。
- 如果是 $1$ 的话，表示这是一个询问操作，操作的参数为 $l, r$。

outputFormat: 对于每个询问操作，输出一行，包括一个整数表示答案 $\bmod \space p$ 的值。

hint:
【数据范围】

对于 $0\%$ 的测试点，和样例一模一样；

对于另外 $10\%$ 的测试点，没有修改；

对于另外 $20\%$ 的测试点，每次修改操作只会修改一个位置（也就是 $l = r$ ），并且每个位置至多被修改一次；

• 对于另外 $10\%$ 的测试点， $p = 2$；

对于另外 $10\%$ 的测试点， $p = 3$；

对于另外 $10\%$ 的测试点， $p = 4$；

对于另外 $20\%$ 的测试点， $1\le n,m \le 100$；

对于 $100\%$ 的测试点， $1\le n,m \le 5\times 10^4$，$1 \le p \le 10^8$，$0< c < p$，$0 \le a_i < p$。


title: [USACO03FALL / HAOI2006] 受欢迎的牛 G

background: 本题测试数据已修复。

description: 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

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

接下来 $M$ 行：每行两个用空格分开的整数：$A$ 和 $B$，表示 $A$ 喜欢 $B$。

outputFormat: 一行单独一个整数，表示明星奶牛的数量。

hint:
只有 $3$ 号奶牛可以做明星。

【数据范围】

对于 $10\%$ 的数据，$N\le20$，$M\le50$。

对于 $30\%$ 的数据，$N\le10^3$，$M\le2\times 10^4$。

对于 $70\%$ 的数据，$N\le5\times 10^3$，$M\le5\times 10^4$。

对于 $100\%$ 的数据，$1\le N\le10^4$，$1\le M\le5\times 10^4$。


title: [SCOI2005] 骑士精神

inputFormat:
第一行有一个正整数 $T$（$T \le 10$)，表示一共有 $T$ 组数据。

接下来有 $T$ 个 $5 \times 5$ 的矩阵，`0` 表示白色骑士，`1` 表示黑色骑士，`*` 表示空位。两组数据之间没有空行。

outputFormat: 对于每组数据都输出一行。如果能在 $15$ 步以内（包括 $15$ 步）到达目标状态，则输出步数，否则输出 `-1`。

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


title: [SCOI2005] 王室联邦

description:
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。

他的国家有 $N$ 个城市，编号为 $1\ldots N$。

一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。

为了防止管理太过分散，每个省至少要有 $B$ 个城市。

为了能有效的管理，每个省最多只有 $3\times B$ 个城市。

每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。

但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。

一个城市可以作为多个省的省会。

聪明的你快帮帮这个国王吧！

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

接下来 $N－1$ 行，每行描述一条边，包含两个数，即这条边连接的两个城市的编号。

outputFormat:
如果无法满足国王的要求，输出 $0$。

否则第一行输出数 $K$，表示你给出的划分方案中省的个数。

第二行输出 $N$ 个数，第 $I$ 个数表示编号为 $I$ 的城市属于的省的编号。要求城市编号在 $[1,K]$ 范围内。

第三行输出 $K$ 个数，表示这 $K$ 个省的省会的城市编号。

如果有多种方案，你可以输出任意一种。

hint:
对于 $100\%$ 的数据，$1\le B\leq N\le 10^3$。

感谢 @[FlierKing](/user/9433) 提供 spj。


title: [SCOI2005] 扫雷

description:
相信大家都玩过扫雷的游戏。那是在一个$n\times m$的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是$n\times 2$的，第一列里面某些格子是雷，而第二列没有雷，如下图：

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

由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

inputFormat: 第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

outputFormat: 一个数，即第一列中雷的摆放方案数。


title: [SCOI2005] 超级格雷码

inputFormat: 只有一行，为两个整数n和B。

outputFormat: 一共B^n个行，每行一个B进制数，表示你所求得的符合条件的排列。

hint: 感谢@Night_Aurora 提供SPJ


title: [SCOI2005] 栅栏

description:
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为 $10$ 的木板可以切成长度为 $8$ 和 $2$ 的两个木板。

你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。

inputFormat:
第一行为整数 $m(m\leq50)$ 表示木材店老板可以提供多少块木材给约翰。紧跟着 $m$ 行为老板提供的每一块木板的长度。

接下来一行（即第 $m+2$ 行）为整数 $n(n\leq1000)$，表示约翰需要多少木材。

接下来 $n$ 行表示他所需要的每一块木板的长度。木材的规格小于 $32767$。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。

outputFormat: 只有一行，为约翰最多能够得到的符合条件的木板的个数。


title: [SCOI2005] 繁忙的都市

description:
城市 C 是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的：城市中有 $n$ 个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：

1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
1. 在满足要求 1 的情况下，改造的道路尽量少。
1. 在满足要求 1、2 的情况下，改造的那些道路中分值最大的道路分值尽量小。

任务：作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建。

inputFormat:
第一行有两个整数 $n,m$ 表示城市有 $n$ 个交叉路口，$m$ 条道路。

接下来 $m$ 行是对每条道路的描述，$u, v, c$ 表示交叉路口 $u$ 和 $v$ 之间有道路相连，分值为 $c$。

outputFormat: 两个整数 $s, \mathit{max}$，表示你选出了几条道路，分值最大的那条道路的分值是多少。

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

对于全部数据，满足 $1\le n\le 300$，$1\le c\le 10^4$，$1 \le m \le 8000$。


title: [SCOI2005] 最大子矩阵

description:
这里有一个 $n \times m$ 的矩阵，请你选出其中 $k$ 个子矩阵，使得这个 $k$ 个子矩阵分值之和最大。

注意：选出的 $k$ 个子矩阵不能相互重叠。

inputFormat: 第一行为 $n,m,k$，接下来 $n$ 行描述矩阵每行中的每个元素的分值（每个元素的分值的绝对值不超过 $32767$）。

outputFormat: 只有一行为 $k$ 个子矩阵分值之和最大为多少。

hint: 对于 $100 \%$ 的数据，$1 \leq n \leq 100$，$1 \leq m \leq 2$，$1 \leq k \leq 10$。


title: [SCOI2006] 数字立方体

description: 有一个立方体被分成 $n\times n\times n$ 的单位，坐标用 $(X,Y,Z)$ 表示 $(1\le X,Y,Z\le n)$。每个单位立方体内有一个绝对值不超过 $10^9$ 的整数。统计有多少个子立方体的所有数之和是 $m$ 的倍数。子立方体即满足 $x_1\le X\le x_2$，$y_1\le Y\le y_2$，$z_1\le Z\le z_2$ 的所有单位立方体集合，其中 $1\le x_1,x_2,y_1,y_2,z_1,z_2\le n$。

inputFormat:
第一行有两个整数 $n, m$，表示立方体的边长和作除数的正整数。

以下 $n\times n$ 行，每行有 $n$ 个整数。首先是 $X=1, Y=1$ 的 $n$ 个单位立方体，然后是 $X=1, Y=2$ 的 $n$ 个…最后是 $X=n, Y=n-1$ 的 $n$ 个和 $X=n$ 和 $Y=n$ 的 $n$ 个，共 $n^3$ 个整数。

outputFormat: 输出仅包含一个数，即所有整数和为 $m$ 的倍数的子立方体的个数。

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

- $30\%$ 的数据满足 $1\le n\le 10$。
- $100\%$ 的数据满足 $1\le n\le 40$。

对于所有的数据满足 $1\le m\le 10^6$。


title: [SCOI2006] 一孔之见

description:
从一个圆孔里看一个凸多边形，为了让看到的面积至少为 $S$，孔的半径至少需要多大？
假设孔的圆心固定在 $(0,0)$，且 $(0, 0)$ 在多边形的内部（而不是外部或边界上）。

inputFormat:
第一行包含一个整数 $n$ 和一个实数 $S$（精确到小数点后两位），表示凸多边形的顶点数和需要看到的面积。保证 $S$ 不超过凸多边形的面积。

以下 $n$ 行每行包含两个实数 $x,y$（精确到小数点后 $6$ 位），表示各顶点的坐标。顶点按逆时针顺序或顺时针顺序给出。

outputFormat: 包含一个实数 $r$，保留两位小数，表示孔的最小半径。

hint:
【限制】

对于 $50\%$ 的数据：$3\le n \le 10$，输入凸多边形是正多边形，且中心在 $(0,0)$
对于 $100\%$ 的数据：$3\le n \le 50$


title: [SCOI2006] 城堡

description:
为了救出心爱的公主 Julie，Billy 来到了恶魔的城堡。经过了三天三夜的浴血奋战，魔王殿已近在咫尺。

这是一条狭长的通道，Billy 在位置 $0$，而魔王殿在位置 $n + 1$。在每个单位时间，Billy 可以往左或往右移动一个单位，或者原地不动。每个格子的上方都有石头周期性的往下砸，格子 $i$ 的周期为 $c_i$。

对于格子 $i$ 上方的石头，可以用 $c_i$ 个整数来描述：$h_1, h_2, \cdots, h_{c_i}$，表示在时间 $t = kc_i + x$（$1\leq x\leq c_i$）时处于该格子上将被砸掉 $h_x$ 格血。其中 $h_x = 0$ 表示该时刻没有石头砸下来。

计算 Billy 最少损失多少格血后可以到达魔王殿。假设 Billy 是不会死的。注意从位置 $1$ 也是可以回到位置 $0$ 的，且在位置 $0$ 不损血。

inputFormat:
第一行包括一个整数 $n$，表示通道的长度。

以下 $n$ 行，依次表示格子 $1, 2, \cdots, n$ 的情况。每行第一个整数为 $c_i$，表示石头下落周期，接下来有 $c_i$ 个整数，分别为 $h_1, h_2, \cdots, h_{c_i}$。

outputFormat: 包含一个整数 HP，表示血的最小损失。

hint:
对于 $50\%$ 的数据，$n\leq 20$；

对于 $100\%$ 的数据满足：$0\leq n\leq 1000$，$1\leq c_i\leq 10$，$0\leq h_x\leq 100$。

- 2023.4.12 添加一组 hack 数据，不计分。


title: [SCOI2012] 喵星球上的点名

description:
a180285 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。

假设课堂上有 $n$ 个喵星人，每个喵星人的名字由**姓**和**名**构成。喵星球上的老师会选择 $m$ 个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的**子串**，那么这个喵星人就必须答到。

然而，由于喵星人的字码如此古怪，以至于不能用 ASCII 码来表示。为了方便描述，a180285 决定用数串来表示喵星人的名字。

现在你能帮助 a180285 统计每次点名的时候有多少喵星人答到，以及 $m$ 次点名结束后每个喵星人答到多少次吗？

inputFormat:
首先定义喵星球上的字符串给定方法：

先给出一个正整数 $l$，表示字符串的长度，接下来 $l$ 个整数，第 $i$ 个整数 $a_i$ 表示字符串的第 $i$ 个字符。

输入的第一行有两个整数，分别表示喵星人的个数 $n$ 个点名次数 $m$。
接下来 $n$ 行，每行两个喵星球上的字符串，按照定义的方法给出，依次表示第 $i$ 只喵的姓和名。
接下来 $m$ 行，每行一个喵星球上的字符串，表示一个老师点名的串。

outputFormat:
对于每个老师点名的串，输出一行一个整数表示有多少只喵答到。
然后在最后一行输出 $n$ 个用空格隔开的整数，第 $i$ 个整数表示第 $i$ 个喵星人被点到的次数。

hint:
#### 样例 1 解释

事实上样例给出的数据如果翻译成地球上的语言可以这样来看

```plain
2 3
izayoi sakuya
orihara izaya
izay
hara
raiz
```

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n, m \le 10^3$，喵星人的名字总长不超过 $4\times10^3$，点名串的总长不超过 $2\times10^3$。
- 对于$100\%$ 的数据，保证 $1 \leq n\le 5 \times 10^4$，$1 \leq m \le 10^5$，喵星人的名字总长和点名串的总长分别不超过 $10^5$，保证喵星人的字符串中作为字符存在的数不超过 $10^4$ 。


title: [SCOI2012] 喵星人的入侵

description:
a180285 幸运地被选作了地球到喵星球的留学生，其实是作为特工去调查，喵星人是否有侵略地球的企图。喵星人果然打算入侵地球！从 a180285 口中得到确切消息之后，地球小组成员决定制定反侵略计划。

喵星到地球的一段必经之路可以看作 $n\times m$ 的格点，喵星人将会从地图上的 $S$ 位置出发，目的地是地球的入口 $T$。为了抵抗喵星人的入侵，地球防御小组打算在地图上的格点上放置一些炮塔（最多放置 $K$ 个），炮塔攻击周围的 $8$ 个方向（$8$ 个方向分别是：东、南、西、北、东北、西北、东南、西南）（如下图所示，中间格子的炮塔可以攻击周围的八个格子）。此外地球防御小组还可以在地图上放置无限多个障碍，使得喵星人无法从有障碍的格子经过。

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

右图是 $3\times 3$ 地图的一个示例，其中 $\tt X$ 表示炮塔，$\tt \#$ 表示障碍，有炮塔或者障碍的格子，喵星人都无法经过。在这张地图中喵星人从 $S$ 走到 $T$ 受到的伤害如下：

- 在 $S(1, 0)$ 处受到伤害为 $2$（炮塔 $(0,0)$ 和 $(2, 1)$ 能攻击到 $S$）；
- 在空地 $(1,1)$ 处受到伤害为 $3$（同时被炮塔 $(0,0),(0,2)$ 和 $(2, 1)$ 攻击）；
- 在 $T(1,2)$ 处受到伤害为 $2$（炮塔 $(0,2)$ 和 $(2, 1)$ 能攻击到 $T$）。

于是受到的总伤害为 $2+3+2=7$。

作为地球防御小组的成员，请你为喵星人布阵，使得喵星人受到的伤害最大。注意如果有多条从 $S$ 到 $T$ 的路径，喵星人会选择伤害最小的一条。

inputFormat:
第一行为三个整数 $n,m,K$，分别表示地图的长和宽，以及最多能放置的炮塔数量。

接下来的 $n$ 行，每行包含 $m$ 个字符，$\tt \#$ 表示地图上原有的障碍，$\tt .$ 表示该处为空地，数据保证在原地图上存在 $S$ 到 $T$ 的路径。

outputFormat:
输出在合理布阵下，喵星人采取最优策略后，会受到的最大伤害。

注意必须保证在布阵结束后喵星人仍然可以沿一条或以上的路径从起点 $S$ 到达终点 $T$，否则他们组织更大规模的侵略。

hint:
### 样例解释

样例的一种最优布局方案如下：

```plain
S#T
.X.
...
```

### 数据范围及约定

- 对于 $30\%$ 的数据，保证 $1\le n,m\leq 6$；
- 对于 $100\%$ 的数据，保证 $\min(n,m)\le 6$，$\max(n,m)\le 20$，$1\le K\le 15$ 且从 $S$ 到 $T$ 的路径必定存在。


title: 宝石管理系统

description: GY 君购买了一批宝石放进了仓库。有一天 GY 君心血来潮，想要清点他的宝石，于是把 $m$ 个宝石都取出来放进了宝石管理系统。每个宝石 $i$ 都有一个珍贵值 $v_i$，他希望你能编写程序查找到从大到小第 $n$ 珍贵的宝石。但是现在问题来了，他非常不小心的留了一些宝石在仓库里面，有可能要往现有的系统中添加宝石。这些宝石的个数比较少。他表示非常抱歉，但是还是希望你的系统能起作用。

inputFormat:
第一行两个整数 $m,q$，表示已经取出来的宝石个数以及接下来的查询或插入操作个数。

第二行 $m$ 个正整数，表示这 $m$ 个宝石的珍贵值。

以下 $q$ 行，每行两个整数 $c,n$。

若 $c=1$（即询问），则输出当前第 $n$ 珍贵的宝石。

若 $c=2$（即插入），则往系统中插入珍贵值为 $n$ 的宝石。

outputFormat: 对于每个 $c=1$（询问）,输出当前第 $n$ 珍贵的宝石的珍贵值 $v_i$。


title: [六省联考 2017] 组合数问题

description:
组合数 $C_n^m$ 表示的是从 $n$ 个互不相同的物品中选出 $m$ 个物品的方案数。举个例子， 从 $(1, 2, 3)$ 三个物品中选择两个物品可以有 $(1, 2)$，$(1, 3)$，$(2, 3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数  $C_n^m$  的一般公式：

$$ C_n^m = \frac {n!} {m! \ (n - m)!}  $$

其中 $n! = 1 \times 2 \times \cdots \times n$。（特别地，当 $n = 0$ 时，$n! = 1$；当 $m > n$ 时，$C_n^m = 0$。）

小葱在 NOIP 的时候学习了 $C_i^j$ 和 $k$ 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，$C_i^j$ 是否是 $k$ 的倍数，取决于 $C_i^j \bmod k$ 是否等于 $0$，这个神奇的性质引发了小葱对 $\mathrm{mod}$ 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 $n, p, k, r$，他希望知道

$$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p,$$

即

$$\left( C_{nk}^{r} + C_{nk}^{k + r} + C_{nk}^{2k + r} + \cdots + C_{nk}^{(n - 1)k + r}  + C_{nk}^{nk + r} + \cdots \right) \bmod p$$

的值。

inputFormat: 第一行有四个整数 $n, p, k, r$，所有整数含义见问题描述。

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

hint:
对于 $30\%$ 的测试点，$1 \leq n, k \leq 30$，$p$ 是质数；
对于另外 $5\%$ 的测试点，$p = 2$；
对于另外 $5\%$ 的测试点，$k = 1$；
对于另外 $10\%$ 的测试点，$k = 2$；
对于另外 $15\%$ 的测试点，$1 \leq n \leq 10^3, 1 \leq k \leq 50$，$p$ 是质数；
对于另外 $15\%$ 的测试点，$1 \leq n \times k \leq 10^6$，$p$ 是质数；
对于另外 $10\%$ 的测试点，$1 \leq n \leq 10^9, 1 \leq k \leq 50$，$p$ 是质数；
对于 $100\%$ 的测试点，$1 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 1$。


title: [USACO11FEB] Generic Cow Protests G

description:
Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 10^5$）排成一列，正在进行一场抗议活动。第 $i$ 头奶牛的理智度为 $a_i$（$-10^4 \leq a_i \leq 10^4$）。

FJ 希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成若干个小组，每个小组内的奶牛的理智度总和都要不小于零。

由于奶牛是按直线排列的，所以一个小组内的奶牛位置必须是连续的。请帮助 FJ 计算一下，满足条件的分组方案有多少种。

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

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 头奶牛的理智度 $a_i$。

outputFormat: 输出满足条件的分组方案对 $10^9+9$ 取模的结果。


title: [USACO04OPEN] MooFest G

background: [P5094 [USACO04OPEN] MooFest G 加强版](https://www.luogu.com.cn/problem/P5094)

description:
约翰的 $n$ 头奶牛每年都会参加“哞哞大会”。

哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。

它们参加活动时会聚在一起，第 $i$ 头奶牛的坐标为 $x_i$，没有两头奶牛的坐标是相同的。

奶牛们的叫声很大，第 $i$ 头和第 $j$ 头奶牛交流，会发出
$\max\{v_i,v_j\}\times |x_i − x_j |$
的音量，其中 $v_i$ 和 $v_j$ 分别是第 $i$ 头和第 $j$ 头奶牛的听力。

假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

inputFormat:
第一行：单个整数 $n$，$1\le n\le2\times 10^4$

第二行到第 $n + 1$ 行：第 $i + 1$ 行有两个整数 $v_i$ 和 $x_i$（$1\le v_i,x_i\le2\times 10^4$）。

outputFormat: 单个整数：表示所有奶牛产生的音量之和


title: 四子连棋

description:
在一个 $4\times 4$ 的棋盘上摆放了 $14$ 颗棋子，其中有 $7$ 颗白色棋子，$7$ 颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

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

inputFormat: 从文件中读入一个 $4\times 4$ 的初始棋局，黑棋子用 `B` 表示，白棋子用 `W` 表示，空格地带用 `O` 表示。

outputFormat: 用最少的步数移动到目标棋局的步数。

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


title: [NOI2014] 随机数生成器

description:
小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 random 和 C/C++中的 rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。

比如，下面这个二次多项式递推算法就是一个常用算法：

算法选定非负整数 $x_0,a,b,c,d$ 作为随机种子，并采用如下递推公式进行计算。

对于任意 $i ≥ 1,x_i=(a \times x_{i-1}^2+b \times x_{i-1}+c)\mod d$ 这样可以得到一个任意长度的非负整数数列$\{x_i\},i \ge 1$，一般来说，我们认为这个数列是随机的。

利用随机序列 ${xi},i≥1$，我们还可以采用如下算法来产生一个 $1$ 到 $K$ 的随机排列$ \{ Ti \},i=1 ... k$：

1. 初始设 $T$ 为 $1$ 到 $K$ 的递增序列；
2. 对 $T$ 进行 $K$ 次交换，第 $i$ 次交换，交换 $T_i$ 和 $T_{(x_i \bmod i) + 1}$ 的值。

此外，小 H 在这 $K$ 次交换的基础上，又额外进行了 $Q$ 次交换操作，对于第i 次额外交换，小 H 会选定两个下标 $u_i$ 和 $v_i$，并交换 $T_{u_i}$ 和 $T_{v_i}$ 的值。

为了检验这个随机排列生成算法的实用性，小 H 设计了如下问题：

小 H 有一个 $N$ 行 $M$ 列的棋盘，她首先按照上述过程，通过 $N \times M + Q$ 次交换操作，生成了一个 $1\sim N \times M$ 的随机排列 $\{Ti\},i=1 ... N \times M$，然后将这 $N \times M$ 个数逐行逐列依次填入这个棋盘：也就是第 $i$ 行第 $j$ 列的格子上所填入的数应为 $ T_{(i-1) \times M+j} $。

接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或者向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 $N$ 行第 $M$ 列的格子。

小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 $N + M - 1$ 的升序序列，我们称之为路径序列。

小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？

inputFormat:
第 1 行包含 $5$ 个整数，依次为 $x_0,a,b,c,d$ ，描述小H采用的随机数生成算法所需的随机种子。

第 2 行包含三个整数 $N,M,Q$ ，表示小H希望生成一个1到 $N \times M$ 的排列来填入她 $N$ 行 $M$ 列的棋盘，并且小H在初始的 $N \times M$ 次交换操作后，又进行了 $Q$ 次额外的交换操作。

接下来 $Q$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，表示第 $i$ 次额外交换操作将交换 $T_{u_i}$和 $T_{v_i}$ 的值。

outputFormat: 输出一行，包含 $N+M-1$ 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。

hint:
对于样例 1，根据输入的随机种子，小 H 所得到的前 12 个随机数xi为：

9 5 30 11 64 42 36 22 1 9 5 30

根据这 12 个随机数，小 H 在进行初始的 12 次交换操作后得到的排列为：

6 9 1 4 5 11 12 2 7 10 3 8

在进行额外的 3 次交换操作之后，小 H 得到的最终的随机排列为：

12 9 1 7 5 11 6 2 4 10 3 8

```cpp
12 9 1 7
5 11 6 2
4 10 3 8
```

最优路径依次经过的数字为 ：12-9-1-6-28。

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


title: [NOIP1996 提高组] 砝码称重

description: 设有 $1\mathrm{g}$、$2\mathrm{g}$、$3\mathrm{g}$、$5\mathrm{g}$、$10\mathrm{g}$、$20\mathrm{g}$ 的砝码各若干枚（其总重 $ \le 1000$），可以表示成多少种重量？

inputFormat:
输入方式：$a_1 , a_2  ,a_3 , a_4 , a_5 ,a_6$

（表示 $1\mathrm{g}$ 砝码有 $a_1$ 个，$2\mathrm{g}$ 砝码有 $a_2$ 个，$\dots$，$20\mathrm{g}$ 砝码有 $a_6$ 个）

outputFormat:
输出方式：`Total=N`

（$N$ 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

hint:
**【题目来源】**

NOIP 1996 提高组第四题


title: [六省联考 2017] 摧毁“树状图”

description:
自从上次神刀手帮助蚯蚓国增添了上千万人口（蚯口？），蚯蚓国发展得越来越繁荣了！最近，他们在地下发现了一些神奇的纸张，经过仔细研究，居然是 D 国 X 市的超级计算机设计图纸！

这台计算机叫做 “树状图”，由 $n$ 个计算节点与 $n - 1$ 条可以双向通信的网线连接而成，所有计算节点用不超过 $n$ 的正整数编号。顾名思义，这形成了一棵树的结构。

蚯蚓国王已在图纸上掌握了这棵树的完整信息，包括 $n$ 的值与 $n - 1$ 条网线的连接信息。于是蚯蚓国王决定，派出蚯蚓国最强大的两个黑客，小 P 和小 H，入侵 “树状图”，尽可能地摧毁它。

小 P 和小 H 精通世界上最好的编程语言，经过一番商量后，他们决定依次采取如 下的步骤：
* 小 P 选择某个计算节点，作为他入侵的起始点，并在该节点上添加一个 **P** 标记。
* 重复以下操作若干次（可以是 $0$ 次）：
    * 小 P 从他当前所在的计算节点出发，选择一条没有被标记过的网线，入侵到该网线的另一端的计算节点，并在路过的网线与目的计算节点上均添加一个 **P** 标记。
* 小 H 选择某个计算节点，作为她入侵的起始点，并在该节点上添加一个 **H** 标记。
* 重复以下操作若干次（可以是 $0$ 次）：
    * 小 H 从她当前所在的计算节点出发，选择一条没有被标记过的网线，入侵到该网线的另一端的计算节点，并在路过的网线与目的计算节点上均添加一个 **H** 标记。（注意，小 H 不能经过带有 **P** 标记的网线，但是可以经过带有 **P** 标记的计算节点）
* 删除所有被标记过的计算节点和网线。
* 对于剩下的每条网线，如果其一端或两端的计算节点在上一步被删除了，则也删除这条网线。

经过以上操作后，“树状图” 会被断开，剩下若干个（可能是 $0$ 个）连通块。为了达到摧毁的目的，蚯蚓国王希望，连通块的个数越多越好。于是他找到了你，希望你能帮他计算这个最多的个数。

小 P 和小 H 非常心急，在你计算方案之前，他们可能就已经算好了最优方案或最优方案的一部分。你能得到一个值 $x$：
* 若 $x = 0$，则说明小 P 和小 H 没有算好最优方案，你需要确定他们两个的入侵路线。
* 若 $x = 1$，则说明小 P 已经算好了某种两人合作的最优方案中，他的入侵路线。他将选择初始点 $p_0$，并沿着网线一路入侵到了目标点 $p_1$，并且他不会再沿着网线入侵；你只需要确定小 H 的入侵路线。
* 若 $x = 2$，则说明小 P 和小 H 算好了一种两人合作的最优方案，小 P 从点 $p_0$ 入侵到了 $p_1$ 并停下，小 H 从点 $h_0$ 入侵到了 $h_1$ 并停下。此时你不需要指挥他们入侵了，只需要计算最后两步删除计算节点与网线后，剩下的连通块个数即可。

inputFormat:
每个输入文件包含多个输入数据。输入文件的第一行为两个整数 $T$ 和 $x$，$T$ 表示该文件包含的输入数据个数，$x$ 的含义见上述。（同一个输入文件的所有数据的 x 都是相同的。）

接下来依次输入每个数据。

outputFormat: 对于每个数据，输出一行，表示在给定条件下，剩下连通块的最大个数。

hint:
* 若 $x = 0$，则该行只有一个整数 $n$。
* 若 $x = 1$，则该行依次有三个整数 $n, p_0, p_1$。
* 若 $x = 2$，则该行依次有五个整数 $n, p_0, p_1, h_0, h_1$。

保证 $p_0, p_1, h_0, h_1$ 均为不超过 $n$ 的正整数。

每个数据接下来有 $n - 1$ 行，每行有两个不超过 $n$ 的正整数，表示这两个编号的计算节点之间有一条网线将其相连。保证输入的是一棵树。

同一行相邻的整数之间用恰好一个空格隔开。

**数据文件可能较大，请避免使用过慢的输入输出方法。**

【样例 1 说明】

这个输入文件只有一个输入数据。一种最优的方案如下：

- 小 P 从节点 $2$ 开始入侵，节点 $2$ 被小 P 标记。

- 小 P 从节点 $2$ 入侵到节点 $4$，节点 $4$ 和经过的网线被小 P 标记。

- 小 P 从节点 $4$ 入侵到节点 $7$，节点 $7$ 和经过的网线被小 P 标记。

- 小 H 从节点 $10$ 开始入侵，节点 $10$ 被小 H 标记。

- 删除被标记的节点 $2,4,7,10$ 和被标记的网线 $(2,4)$ 和 $(4,7)$。

- 删除任意一端在上一步被删除的网线。

此时还剩下 $8$ 个连通块。其中节点 $1,3,5,6,8,9,11$ 各自形成一个连通块，节点$12,13$形成了一个连通块。

【样例 2 说明】

- 数据 1：只有 $1$ 个计算节点，唯一可行的方案是小 P 从节点 $1$ 开始入侵（并马上停止），小 H 也从节点 $1$ 入侵到节点 $1$。所有的节点都被删去，剩下 $0$ 个连通块。

- 数据 2：一种最优方案是，小 P 从节点 $1$ 入侵到节点 $1$，小 H 也从节点 $1$ 入侵到节点 $1$。在删除操作后，剩下 $1$ 个连通块（只有节点 $2$）。

- 数据 3：唯一的最优方案是，小 P 从节点 $2$ 入侵到节点 $2$，小 H 也从节点 $2$ 入侵到节点 $2$，剩下 $2$ 个连通块。

- 数据 4：一种最优方案是，小 P 从节点 $2$ 入侵到节点 $2$，小 H 也从节点 $2$ 入侵到节点 $2$，剩下 $2$ 个连通块。

- 数据 5：唯一的最优方案是，小 P 从节点 $5$ 入侵到节点 $5$，小 H 也从节点 $5$ 入侵到节点 $5$，剩下 $4$ 个连通块。

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

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

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

对于整数 $k$，设$\sum n^k$ 为某个输入文件中，其$ T$ 个输入数据的 $n^k$ 之和。

对于所有数据，$T \leq 10^5, \sum n^1 <5 \times 10^5$

请注意初始化的时间复杂度，避免输入大量小数据时超时。

每个测试点的详细数据范围见下表。如果表中 “完全二叉” 为 Yes，则该输入文件的每个数据满足：网线信息的第 $j$ 行 $(1 \leq j < n)$ 输入的两个数依次是 $\left\lfloor \frac {j + 1} {2} \right\rfloor$ 和 $j + 1$。

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


title: [六省联考 2017] 分手是祝愿

description:
> Zeit und Raum trennen dich und mich.
时空将你我分开。

B 君在玩一个游戏，这个游戏由 $n$ 个灯和 $n$ 个开关组成，给定这 $n$ 个灯的初始状态，下标为从 $1$ 到 $n$ 的正整数。

每个灯有两个状态亮和灭，我们用 $1$ 来表示这个灯是亮的，用 $0$ 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。

但是当操作第 $i$ 个开关时，所有编号为 $i$ 的约数（包括 $1$ 和 $i$）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。

B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。

这个策略需要的操作次数很多，B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 $k$ 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 $k$ 步）操作这些开关。

B 君想知道按照这个策略（也就是先随机操作，最后小于等于 $k$ 步，使用操作次数最小的操作方法）的操作次数的期望。

这个期望可能很大，但是 B 君发现这个期望乘以 $n$ 的阶乘一定是整数，所以他只需要知道这个整数对 $100003$ 取模之后的结果。

inputFormat:
第一行两个整数 $n, k$。
接下来一行 $n$ 个整数，每个整数是 $0$ 或者 $1$，其中第 $i$ 个整数表示第 $i$ 个灯的初始情况。

outputFormat: 输出一行，为操作次数的期望乘以 $n$ 的阶乘对 $100003$ 取模之后的结果。

hint:
对于 $0\%$ 的测试点，和样例一模一样；
对于另外 $30\%$ 的测试点，$n \leq 10$；
对于另外 $20\%$ 的测试点，$n \leq 100$；
对于另外 $30\%$ 的测试点，$n \leq 1000$；
对于 $100\%$ 的测试点，$1 \leq n \leq 100000, 0 \leq k \leq n$；
对于以上每部分测试点，均有一半的数据满足 $k = n$。


title: 三国杀I（洗牌&发牌）

description:
一场三国杀一共有 $n$ 个玩家，每人需要 $4$ 张牌。牌库共 $k$ 张牌，需洗牌后再发。每张牌有以下 $3$ 个属性：

一、牌的类型:

1. 基础：杀（$\texttt{K}$）、闪（$\texttt{M}$）、桃（$\texttt{P}$）、酒（$\texttt{W}$）。

2. 非延时锦囊：决斗（$\texttt{B}$）、万箭（$\texttt{A}$）、南蛮（$\texttt{S}$）、五谷（$\texttt{C}$）、桃园（$\texttt{G}$）、拆（$\texttt{D}$）、顺（$\texttt{U}$）、铁索（$\texttt{T}$）、无懈（$\texttt{N}$）、火攻（$\texttt{F}$）、无中（$\texttt{E}$）。

3. 延时锦囊：兵（$\texttt{I}$）、乐（$\texttt{K}$）、闪电（$\texttt{L}$）。

4. 马（$\texttt{+,-}$）

5. 武器：连弩（$\texttt{LN}$）、青釭（$\texttt{QG}$）、古锭（$\texttt{GD}$）、寒冰（$\texttt{HB}$）、雌雄（$\texttt{CX}$）、吴六（$\texttt{WL}$）、青龙（$\texttt{QL}$）、丈八（$\texttt{ZB}$）、贯石（$\texttt{GS}$）、方天（$\texttt{FT}$）、羽扇（$\texttt{YS}$）、麒麟（$\texttt{LG}$）。

6. 防具：仁王（$\texttt{RW}$）、八阵（$\texttt{BZ}$）、藤甲（$\texttt{TJ}$）、狮子（$\texttt{SZ}$）

二、花色：只有可能是 $\texttt{C,H,S,D}$ 中的一个。

三、点数：只有可能是 $\texttt{A,2,3,4,5,6,7,8,9,T,J,Q,K}$（T代表10，从小到大）中的一个。

洗牌方式的介绍：一次洗牌过后，从上到下依次是：$\left\lfloor\dfrac{k}{2}\right\rfloor+1,1,\left\lfloor\dfrac{k}{2}\right\rfloor+2,2,\left\lfloor\dfrac{k}{2}\right\rfloor+3,3, ... ,k,\left\lfloor\dfrac{k}{2}\right\rfloor$（可以有奇数张牌，最后一张牌直接忽略掉）。

发牌方式的介绍：从第 $1$ 张牌开始，从上到下依次将第 $i$ 张牌给第 $[(i-1)\mod n+1]$ 号玩家。

已知一共洗了 $m$ 次牌，现在问你第 $p$ 位玩家发到的 $4$ 张牌有哪些。

inputFormat:
输入一共 $k+1$ 行。

第一行 $4$ 个正整数 $n,k,m,p$。
随后 $k$ 行，每行两个字符串，其中第一个字符串第一个字符表示花色，第二个字符表示点数，第二个字符串表示牌的类型。输出玩家拥有的牌的时候亦按照此格式输出。

$n,k,m,p$ 的含义见题意所述。

outputFormat:
输出共 $4$ 行，每行一个字符串，表示第 $p$ 位玩家拥有的 $4$ 张牌（输出应包括每张牌的**花色、点数和类型**，格式同输入）。

如果牌数不够，输出 `Error:cards not enough`。

samples:
2 10 1 1
C2 K
H5 B
DT K
SA M
HQ P
D4 K
C6 P
H9 M
ST B
SK C

samples:
2 7 1 1
C2 K
H5 B
DT K
SA M
HQ P
SK C
C6 P

hint: 对于 $100\%$ 的数据，满足 $1\leqslant p\leqslant n\leqslant 1000,1\leqslant k\leqslant 100000,1\leqslant m\leqslant 80$。


title: [HAOI2012] 外星人

description: 艾莉欧在她的被子上发现了一个数字 $N$，她觉得只要找出最小的 $x$ 使得，$\varphi^x(N) = 1$。根据这个 $x$ 她就能找到曾经绑架她的外星人的线索了。当然，她是不会去算，请你帮助她算出最小的 $x$。

inputFormat:
第一行一个正整数 $\mathrm{test}$，接下来 $\mathrm{test}$ 组数据每组数据第一行一个正整数 $m$，接下来 $m$ 行每行两个正整数 $p_i, q_i$

其中 $\displaystyle \prod_{i = 1}^{m} p_i^{q_i}$ 为 $N$ 的标准分解形式。

$\prod$ 为连乘

$\varphi^x(N)$ 表示嵌套 $x$ 次，不是幂

outputFormat: 输出 $\mathrm{test}$ 行，每行一个整数，表示答案。

hint:
$30\%$ 的数据，$N \le 10^6$。

$60\%$ 的数据，$x \le 100$。

$100\%$ 的数据，$\mathrm{test} \le 50$，$1 \le p_i \le {10}^5$，$1 \le q_i \le {10}^9$，$m \le 2000$。

$\varphi$ 为欧拉函数，$\varphi(n)$ 即小于等于 $n$ 的数中与 $n$ 互质的数的个数。

提示：$\varphi(\prod_{i=1}^mp_i^{q_i})=\prod_{i=1}^m(p_i-1)*p_i^{q_i-1}$。


title: 金字塔

description: 有一盗墓者潜入一金字塔盗宝。当她（难道是 Lara Croft ?）打开一个宝箱的时候，突然冒出一阵烟（潘多拉的盒子？），她迅速意识到形势不妙，三十六计走为上计……由于她盗得了金字塔的地图，所以她希望能找出最佳逃跑路线。地图上标有 $N$ 个室，她现在就在 $1$ 室，金字塔的出口在 $N$ 室。她知道一个秘密：那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线，使得在最坏的情况下所用的时间最少。

inputFormat: 输入文件的第一行有两个正整数 $N$（$3 \le N \le 100$）和 $M$（$3 \le M \le 2000$）；下面有 $M$ 行，每行有三个数正整数 $U$ 、 $V$ 、 $W$，表示直接从 $U$ 室跑到 $V$ 室（$V$ 室跑到 $U$ 室）需要 $W$（$3 \le W \le 255$）秒。

outputFormat: 输出所求的最少时间（单位为秒）。

hint:
样例解释 Sample Explan：

基本上有三种路线：

（1）$1 \to 2 \to 3 \to 4 \to 7$。

总时间为：$10$ ＋ $12$ ＋ $20$ ＋ $8$ ＝ $50$，最坏的情况是“ $3 \to 4$ ”那一段，要多花 $20$ 秒（因为行走速度减半），所以这条路选最坏需要 $70$ 秒；

（2）$1 \to 2 \to 5 \to 6 \to 4 \to 7$。

总时间为：$10$ ＋ $10$ ＋ $12$ ＋ $13$ ＋ $8$ ＝ $53$，最坏的情况是“ $6 \to 4$ ”那一段，要多花 $13$ 秒，所以这条路选最坏需要 $66$ 秒；

（3）$1 \to 7$。

总时间为：$34$ ＝ $34$，最坏的情况是“ $1 \to 7$ ”那一段，要多花 $34$ 秒，所以这条路选最坏需要 $68$ 秒。


title: [六省联考 2017] 寿司餐厅

description:
Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。

每天晚上，这家餐厅都会按顺序提供 $n$ 种寿司，第 $i$ 种寿司有一个代号 $a_i$ 和美味度 $d_{i, i}$，不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的，Kiana 也可以无限次取寿司来吃，但每种寿司每次只能取一份，且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段，即 Kiana 可以一次取走第 $1, 2$ 种寿司各一份，也可以一次取走第 $2, 3$ 种寿司各一份，但不可以一次取走第 $1, 3$ 种寿司。

由于餐厅提供的寿司种类繁多，而不同种类的寿司之间相互会有影响：三文鱼寿司和鱿鱼寿司一起吃或许会很棒，但和水果寿司一起吃就可能会肚子痛。因此，Kiana 定义了一个综合美味度 $d_{i, j} \ (i < j)$，表示在一次取的寿司中，如果包含了餐厅提供的从第 $i$ 份到第 $j$ 份的所有寿司，吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间，所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时，不止一个综合美味度会被累加，比如若 Kiana 一次取走了第 $1, 2, 3$ 种寿司各一份，除了 $d_{1, 3}$ 以外，$d_{1, 2}, d_{2, 3}$ 也会被累加进总美味度中。

神奇的是，Kiana 的美食评判标准是有记忆性的，无论是单种寿司的美味度，还是多种寿司组合起来的综合美味度，在计入 Kiana 的总美味度时都只会被累加一次。比如，若 Kiana 某一次取走了第 $1, 2$ 种寿司各一份，另一次取走了第 $2, 3$ 种寿司各一份，那么这两次取寿司的总美味度为 $d_{1, 1} + d_{2, 2} + d_{3, 3} + d_{1, 2} + d_{2, 3}$，其中 $d_{2, 2}$ 只会计算一次。

奇怪的是，这家寿司餐厅的收费标准很不同寻常。具体来说，如果 Kiana 一共吃过了 $c \ (c > 0)$ **种**代号为 $x$ 的寿司，则她需要为这些寿司付出 $mx^2 + cx$ 元钱，其中 $m$ 是餐厅给出的一个常数。

现在 Kiana 想知道，在这家餐厅吃寿司，自己能获得的总美味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。由于她不会算，所以希望由你告诉她。

inputFormat:
第一行包含两个正整数 $n, m$，分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。
第二行包含 $n$ 个正整数，其中第 $k$ 个数 $a_k$ 表示第 $k$ 份寿司的代号。
接下来 $n$ 行，第 $i$ 行包含 $n - i + 1$ 个整数，其中第 $j$ 个数 $d_{i, i+j-1}$ 表示吃掉寿司能获得的相应的美味度，具体含义见问题描述。

outputFormat: 输出共一行包含一个正整数，表示 Kiana 能获得的总美味度减去花费的总钱数的最大值。


title: [TJOI2017] 城市

description:
从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这个地区一共有 $n$ 座城市，$n-1$ 条高速公路，保证了任意两运城市之间都可以通过高速公路相互可达，但是通过一条高速公路需要收取一定的交通费用。小明对这个地区深入研究后，觉得这个地区的交通费用太贵。

小明想彻底改造这个地区，但是由于上司给他的资源有限，因而小明现在只能对一条高速公路进行改造，改造的方式就是去掉一条高速公路，并且重新修建一条一样的高速公路（即交通费用一样），使得这个地区的两个城市之间的最大交通费用最小（即使得交通费用最大的两座城市之间的交通费用最小），并且保证修建完之后任意两座城市相互可达。如果你是小明，你怎么解决这个问题？

inputFormat:
输入数据的第一行为一个整数 $n$，代表城市个数。

接下来的 $n - 1$ 行分别代表了最初的 $n-1$ 条公路情况。每一行都有三个整数 $u,v,d$。$u,v$ 代表这条公路的两端城市标号，$d$ 代表这条公路的交通费用。

$1 \leq u,v \leq n$，$1\leq d \leq 2000$。

outputFormat: 输出数据仅有一行，一个整数，表示进行了最优的改造之后，该地区两城市 之间最大交通费用。


title: 队爷的新书

description:
队爷即将出版新书，以记录他辉煌的虐题生涯。。。

有 $n$ 家出版社对这本书表示了兴趣，并愿意给队爷支付 $p \in [Min_{pay},Max_{pay}]$ 的报酬来得到这本书的出版权，每家出版社的 $Min_{pay}$ 和 $Max_{pay}$ 是不一样的。

现在队爷希望你帮他找出一个报酬值 $p$，使得他获得的总报酬最多。（每一个 $Min_{pay} \leq p \leq Max_{pay}$ 的出版社都会付给队爷 $p$ 的报酬）。

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

接下来 $n$ 行，每行 $2$ 个整数 $Min_{payi}$ 和 $Max_{payi}$，为第 $i$ 家出版社愿支付的报酬范围。

outputFormat: 只有一个整数 ans，为最大总报酬。

hint:
【样例解释】

当 $p = 4$ 时，有 $3$ 家出版社会给出报酬，此时最大。

【数据规模与约定】

对于 $20\%$ 的数据，$1 \leq Min_{pay},Max_{pay} \leq 10000$；

对于 $40\%$ 的数据，$1 \leq n \leq 1000,1 \leq Min_{pay},Max_{pay} \leq 10^6$；

对于 $100\%$ 的数据，$1 \leq n \leq 100000,1 \leq Min_{pay},Max_{pay} \leq 10^9$。


title: [ZJOI2007] 仓库建设

description:
L 公司有 $n$ 个工厂，由高到低分布在一座山上，工厂 $1$ 在山顶，工厂 $n$ 在山脚。

由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。

由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 $i$ 个工厂目前已有成品 $p_i$ 件，在第 $i$ 个工厂位置建立仓库的费用是 $c_i$。

对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 $n$，故产品只能往山下运（即**只能运往编号更大的工厂的仓库**），当然运送产品也是需要费用的，一件产品运送一个单位距离的费用是 $1$。

假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

- 工厂 $i$ 距离工厂 $1$ 的距离 $x_i$（其中 $x_1=0$）。
- 工厂 $i$ 目前已有成品数量 $p_i$。
- 在工厂 $i$ 建立仓库的费用 $c_i$。

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用 + 运输费用）最小。

inputFormat:
输入的第一行是一个整数 $n$，代表工厂的个数。

第 $2$ 到 $(n + 1)$ 行，每行有三个用空格隔开的整数，第 $(i + 1)$ 行的整数依次代表 $x_i,~p_i,~c_i$。

outputFormat: 仅输出一行一个整数，代表最优方案的费用。

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

在工厂 $1$ 和工厂 $3$ 建立仓库，建立费用为 $10+10=20$ ，运输费用为 $(9-5) \times 3 = 12$，总费用 $32$。

#### 数据范围与约定

对于 $20\%$ 的数据，保证 $n \leq 500$。

对于 $40\%$ 的数据，保证 $n \leq 10^4$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^6$，$0 \leq x_i,p_i,c_i < 2^{31}$。

对于任意的 $1 \leq i < n$，保证 $x_i < x_{i + 1}$。

设答案为 $ans$，保证 $ans + \sum\limits_{i = 1}^{n} p_ix_i < 2^{63}$。


title: [SDOI2012] 吊灯

background: 山东省省队选拔赛第二试（第一天）

description:
Alice 家里有一盏很大的吊灯。所谓吊灯，就是由很多个灯泡组成。只有一个灯泡是挂在天花板上的，剩下的灯泡都是挂在其他的灯泡上的。也就是说，整个吊灯实际上类似于**一棵树**。其中编号为 $1$ 的灯泡是挂在天花板上的，剩下的灯泡都是挂在编号小于自己的灯泡上的。

现在，Alice 想要办一场派对，她想改造一下这盏吊灯，将灯泡换成不同的颜色。她希望相同颜色的灯泡都是相连的，并且每一种颜色的灯泡个数都是相同的。

Alice 希望你能告诉她，总共有哪些方案。

Alice 是一个贪心的孩子，如果她发现方案不够多，或者太多了，就会很不高兴，于是她会尝试调整。对于编号为 $x$（$x\neq 1$）的灯泡，如果原来是挂在编号为 $f_x$ 的灯泡上，那么 Alice 会把第 $x$ 个灯泡挂到第 $(f_x + 19940105)\bmod (x-1) + 1$ 个灯泡上。

由于九在古汉语中表示极大的数，于是，Alice 决定只调整 $9$ 次。对于原始状态和每一次调整过的状态，Alice 希望你依次告诉她每种状态下有哪些方案。

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

接下来一行，有 $n-1$ 个整数 $U_i$，第 $i$ 个数表示第 $i+1$ 个灯泡挂在了第 $U_i$ 个的下面。保证编号为 $1$ 的灯泡是挂在天花板上的。数字之间用逗号（西文标点）`,` 隔开且最后一个数字后面没有逗号。

outputFormat:
对于 $10$ 种状态下的方案，需要按照顺序依次输出。

对于每一种状态，需要先输出单独的一行，表示状态编号，如样例所示。

之后若干行，每行 $1$ 个整数，表示划分方案中每种颜色的灯泡个数。

按升序输出。

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

对于 $40\%$ 的数据，$n\leq 5\times 10^4$。

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

对于 $60\%$ 的数据，$n\leq 3\times 10^5$。

对于 $70\%$ 的数据，$n\leq 7\times 10^5$。

对于 $100\%$ 的数据，$1\leq n\leq 1.2\times 10^6$。


title: [SDOI2012] Longge 的问题

background: Longge 的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。

description: 现在问题来了：给定一个整数 $n$，你需要求出 $\sum\limits_{i=1}^n \gcd(i, n)$，其中 $\gcd(i, n)$ 表示 $i$ 和 $n$ 的最大公因数。

inputFormat: 输入只有一行一个整数，表示 $n$。

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


title: 弹珠游戏

description:
MedalPluS 和他的小伙伴 NOIRP 发掘了一个骨灰级别的游戏——超级弹珠。

游戏的内容是：在一个 $n \times n$ 的矩阵里，有若干个敌人，你的弹珠可以摧毁敌人，但只能攻击你所在的行、列里的所有敌人，然后你就可以获得他们的分数之和，现在请你选择一个你的位置，使得能击杀的敌人最多，注意，你不能和敌人在一个地方。

inputFormat: 输入有两行，第一行一个正整数 $n$，接下来 $n$ 行，每行 $n$ 列，如果有敌人则为一个正整数，否则为 $0$。

outputFormat: 输出共一行，最多分数，如果连你的容身之地都没有，请输出“Bad Game!”

hint:
【数据范围】

对于 $30\%$ 的数据，$1≤n≤10$；

对于 $100\%$ 的数据，$1≤n≤1000$，保证容身之地的数量小于 $10000$，保证每个位置敌人的数量不超过 $1000$。


title: 守墓人

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

在一个荒凉的墓地上，有一个令人尊敬的守墓人， 他看守的墓地从来没有被盗过， 所以人们很放心的把自己的先人的墓安顿在他那

守墓人能看好这片墓地是必然而不是偶然……

因为……守墓人懂风水 0.0

description:
他把墓地分为主要墓碑和次要墓碑， 主要墓碑只能有 $1$ 个， 守墓人把他记为 $1$ 号， 而次要墓碑有 $n-1$ 个，守墓人将之编号为 $2,3\dots n$，所以构成了一个有 $n$ 个墓碑的墓地。

而每个墓碑有一个初始的风水值，这些风水值决定了墓地的风水的好坏，所以守墓人需要经常来查询这些墓碑。

善于运用风水的守墓人，通过一次次逆天改命，使得自己拥有了无限寿命，没人知道他活了多久。这天，你幸运的拜访到了他，他要求你和他共同见证接下来几年他的战果，但不过他每次统计风水值之和都需要你来帮他计算，算错了他会要你命 QAQ

风水也不是不可变，除非遭遇特殊情况，已知在接下来的 $2147483647$ 年里，会有 $f$ 次灾难，守墓人会有几个操作：

1. 将 $[l,r]$ 这个区间所有的墓碑的风水值增加 $k$。

2.将主墓碑的风水值增加 $k$

3.将主墓碑的风水值减少 $k$

4.统计 $[l,r]$ 这个区间所有的墓碑的风水值之和

5.求主墓碑的风水值

上面也说了，很多人会把先人的墓安居在这里，而且守墓人活了很多世纪→\_→，墓碑的数量会多的你不敢相信= =

守墓人和善的邀请你帮他完成这些操作，要不然哪天你的旅馆爆炸了，天上下刀子.....

为了活命，还是帮他吧

inputFormat:
第一行，两个正整数 $n,f$ 表示共有 $n$ 块墓碑，并且在接下来的 $2147483647 $年里，会有 $f$ 次世界末日

第二行，$n$ 个正整数，表示第 $i$ 块墓碑的风水值

接下来 $f$ 行，每行都会有一个针对世界末日的解决方案，如题所述，标记同题

outputFormat: 输出会有若干行，对 $4$ 和 $5$ 的提问做出回答

hint:
$20\%$ 的数据满足：$1\leq n\leq 100$

$50\%$ 的数据满足：$1\leq n\leq 6000$

$100\%$ 的数据满足：$1\leq n,f\leq 2 \times 10^5$，答案不超过 64 位整数。


title: 三素数数

background: 蛟川书院的一道练习题QAQ

description: 如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。

inputFormat: 一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。

outputFormat: 一个整数，表示n位三素数的个数m，要求输出m除以10^9 + 9的余数。

hint: 区域动归QAQ


title: [SDOI2017] 新生舞会

description:
学校组织了一次新生舞会，Cathy 作为经验丰富的老学姐，负责为同学们安排舞伴。

有 $n$ 个男生和 $n$ 个女生参加舞会，一个男生和一个女生一起跳舞，互为舞伴。

Cathy 收集了这些同学之间的关系，比如两个人之前认识没，计算得出 $a_{i,j}$。

Cathy 还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 $b_{i,j}$，表示第 $i$ 个男生和第 $j$ 个女生一起跳舞时的不协调程度。

当然，还需要考虑很多其他问题。

Cathy 想先用一个程序通过 $a_{i,j}$ 和 $b_{i,j}$ 求出一种方案，再手动对方案进行微调。

Cathy 找到你，希望你帮她写那个程序。

一个方案中有 n 对舞伴，假设每对舞伴的喜悦程度分别是 $a'_1,a'_2,...,a'_n$，假设每对舞伴的不协调程度分别是 $b'_1,b'_2,...,b'_n$。令

$C=\frac {a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n}$

Cathy 希望 $C$ 值最大。

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

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数表示 $a_{i,j}$。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数表示 $b_{i,j}$。

outputFormat: 一行一个数，表示 $C$ 的最大值。四舍五入保留 $6$ 位小数，选手输出的小数需要与标准输出相等。


title: 蚂蚁搬家

description:
边长为 $1$ 的正方体（自行脑补），有一只蚂蚁要从上表面上的一点出发爬往下表面的某一点，规定蚂蚁只能沿正方体表面爬行，要求编程求出一条从起点到终点的最短距离。

起点和终点坐标从键盘输入，设定上下两个表面的坐标原点均为正方形的中心，且两个表面的坐标系的 $X$ 轴和 $Y$ 轴方向一致，输出时保留三位小数。

inputFormat: $4$ 个实数（$-0.5$ 到 $0.5$ 之间），分别表示出发点和目的点的坐标。

outputFormat: 最短距离


title: 地下城主

description:
你参加了一项秘密任务，在任务过程中你被困在了一个 3D 的地下监狱里面，任务是计时的，你现在需要在最短的时间里面从地牢里面逃出来继续你的任务。地牢由若干层组成，每一层的形状都是长宽一样的矩形，地牢被分成了若干小格，当小格没有被岩石所占据时，你可以前往所在小格的前方，后方，左方，右方，上层，下层的小格。每走一小格花费一分钟时间。

你能不能顺利的从地牢里面逃出来呢？如果可以，那所需要的最短时间又是多少呢？

~~据说出口藏有神器。~~

inputFormat:
第一行输入 $L,R,C$ （$L$ 为地牢的层数，$R$ 为每层小格的行数，$C$ 为每层小格的列数，其中 $1 \leq L,R,C \leq 30$）。

第二行开始输入 $L$ 层地牢的格局，每一层有 $R$ 行，每行有 $C$ 个小格，两层地牢中间有空行隔开。

输入的文件中，`S` 代表你的起始点，`E` 代表你所要到达的出口，`#` 为小格被岩石占据，`.` 表示没有被岩石占据。

outputFormat:
输出包含一行，当你可以顺利到达出口时请输出：`Escaped in x minute(s).`

其中，$x$ 代表你所花费的最短时间，否则请输出 `Trapped!`

hint: 来源：POJ 2251


title: [SDOI2017] 硬币游戏

description:
周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。

大家纷纷觉得这个游戏非常符合同学们的特色，但只是扔硬币实在是太单调了。

同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币，其他同学记录下正反面情况。

用 $\texttt H$ 表示正面朝上，用 $\texttt T$ 表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比如 $\texttt{HTT}$ 表示第一次正面朝上，后两次反面朝上。

但扔到什么时候停止呢？大家提议，选出 $n$ 个同学，每个同学猜一个长度为 $m$ 的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利，为了保证只有一个同学胜利，同学们猜的 $n$ 个序列两两不同。

很快，$n$ 个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。

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

接下里 $n$ 行，每行一个长度为 $m$ 的字符串，表示第 $i$ 个同学猜的序列。

outputFormat: 输出 $n$ 行，第 $i$ 行表示第 $i$ 个同学胜利的概率。选手输出与标准输出的绝对误差不超过 $10^{-6}$ 即视为正确。


title: [SDOI2017] 相关分析

description:
Frank 对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。

Frank 不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。

现在 Frank 要分析参数 $X$ 与 $Y$ 之间的关系。他有 $n$ 组观测数据，第 $i$ 组观测数据记录了 $x_i$ 和 $y_i$。他需要一下几种操作。

###  $\verb!1 L R!$

用直线拟合第 $L$ 组到第 $R$ 组观测数据。用 $\overline{x}$ 表示这些观测数据中 $x$ 的平均数，用 $\overline{y}$ 表示这些观测数据中 $y$ 的平均数，即

$$\begin{aligned}\overline{x}&={1 \over R-L+1} \sum _{i=L} ^R x_i \\\overline{y}&={1 \over R-L+1} \sum _{i=L} ^R y_i\end{aligned}$$

如果直线方程是 $y=ax+b$，那么 $a$ 应当这样计算：

$$a={\displaystyle\sum_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y}) \over \displaystyle\sum _{i=L} ^R (x_i -\overline{x})^2}$$

你需要帮助 Frank 计算 $a$。

###  $\verb!2 L R S T!$

Frank 发现测量数据第 $L$ 组到第 $R$ 组数据有误差，对每个 $i$ 满足 $L \leq i \leq R$，$x_i$ 需要加上 $S$，$y_i$ 需要加上 $T$。

###  $\verb!3 L R S T!$

Frank 发现第 $L$ 组到第 $R$ 组数据需要修改，对于每个 $i$ 满足 $L \leq i \leq R$，$x_i$ 需要修改为 $(S+i)$，$y_i$ 需要修改为 $(T+i)$。

inputFormat:
第一行两个数 $n,m$，表示观测数据组数和操作次数。

接下来一行 $n$ 个数，第 $i$ 个数是 $x_i$。

接下来一行 $n$ 个数，第 $i$ 个数是 $y_i$。

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

outputFormat: 对于每个 $1$ 操作，输出一行，表示直线斜率 $a$。选手输出与标准输出的绝对误差或相对误差不超过 $10^{-5}$ 即为正确。


title: [ZJOI2012] 旅游

description:
到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~

经过一番抉择，两人决定将 T 国作为他们的目的地。T 国的国土可以用一个凸 $n$ 边形来表示，$n$ 个顶点表示 $n$ 个入境/出境口。T 国包含 $n-2$ 个城市，每个城市都是顶点均为 $n$ 边形顶点的三角形（换而言之，**城市组成了关于 T 国的一个三角剖分**）。**两人的旅游路线可以看做是连接 $n$ 个顶点中不相邻两点的线段**。

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

为了能够买到最好的纪念品，小白希望旅游路线上经过的城市尽量多。作为小蓝的好友，你能帮帮小蓝吗？

inputFormat:
每个输入文件中仅包含一个测试数据。

第一行包含一个正整数 $n$，$n$ 的含义如题目所述。

接下来有 $n-2$ 行，每行包含三个整数 $p,q,r$，表示该城市三角形的三个顶点的编号（T 国的 $n$ 个顶点按顺时间方向从 $1$ 至 $n$ 编号）。

outputFormat: 输出文件共包含一行，表示最多经过的城市数目。（**一个城市被当做经过当且仅当其与线路有至少两个公共点**）


title: [CQOI2017] 老C的任务

description:
老 C 是个程序员。

最近老 C 从老板那里接到了一个任务——给城市中的手机基站写个管理系统。作为经验丰富的程序员，老 C 轻松地完成了系统的大部分功能，并把其中一个功能交给你来实现。

由于一个基站的面积相对于整个城市面积来说非常的小，因此每个的基站都可以看作坐标系中的一个点，其位置可以用坐标 $(x,y)$ 来表示。此外，每个基站还有很多属性，例如高度、功率等。运营商经常会划定一个区域，并查询区域中所有基站的信息。

现在你需要实现的功能就是，对于一个给定的矩形区域，回答该区域中（包括区域边界上的）所有基站的功率总和。如果区域中没有任何基站，则回答 $0$。

inputFormat:
第一行两个整数 $n,m$，表示一共有 $n$ 个基站和 $m$ 次查询。接下来一共有 $n$ 行，每行由 $x_i,y_i,p_i$ 三个空格隔开的整数构成，表示一个基站的坐标 $(x_i,y_i)$ 和功率 $p_i$。不会有两个基站位于同一坐标。

接下来一共有 $m$ 行，每行由 $x_1,y_1,x_2,y_2$ 四个空格隔开的整数构成，表示一次查询的矩形区域。该矩形对角坐标为 $(x_1,y_1)$ 和 $(x_2,y_2)$，且边与坐标轴平行。

outputFormat: 输出 $m$ 行，每行一个整数，对应每次查询的结果。


title: [CQOI2017] 老C的方块

description:
老 C 是个程序员。

作为一个懒惰的程序员，老 C 经常在电脑上玩方块游戏消磨时间。游戏被限定在一个由小方格排成的 $R$ 行 $C$ 列网格上，如果两个小方格有公共的边，就称它们是相邻的，而且有些相邻的小方格之间的公共边比较特殊。特殊的公共边排列得有很强的规律。首先规定，第 $1$ 行的前两个小方格之间的边是特殊边。然后，特殊边在水平方向上每 $4$ 个小方格为一个周期，在竖直方向上每 $2$ 个小方格为一个周期。所有的奇数列与下一列之间都有特殊边，且所在行的编号从左到右奇偶交替。

下图所示是一个 $R=C=8$ 的网格，蓝色标注的边是特殊边。首先，在第 $1$ 行，第 $1$ 列和第 $2$ 列之间有一条特殊边。因为竖直方向周期为 $2$，所以所有的奇数行，第 $1$ 列和第 $2$ 列之间都有特殊边。因为水平方向周期为 $4$，所以所有奇数行的第 $5$ 列和第 $6$ 列之间也有特殊边，如果网格足够大，所有奇数行的第 $9$ 列和第 $10$ 列、第 $13$ 列和第 $14$ 列之间都有特殊边。因为所有的奇数列和下一列之间都有特殊边，所以第 $3$ 列和第 $4$ 列、第 $7$ 列和第 $8$ 列之间也有特殊边，而所在行的编号从左到右奇偶交替，所以它们的特殊边在偶数行。如果网格的规模更大，我们可以用同样的方法找出所有的特殊边。

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

网格的每个小方格刚好可以放入一个小方块，在游戏的一开始，有些小方格已经放上了小方块，另外的小方格没有放。老 C 很讨厌下图所示的图形，如果他发现有一些小方块排列成了它讨厌的形状（特殊边的位置也要如图中所示），就很容易弃疗，即使是经过任意次旋转、翻转后排列成讨厌的形状，老 C 也同样容易弃疗。

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

为了防止弃疗，老 C 决定趁自己还没有弃疗，赶紧移除一些格子里小方块，使得剩下的小方块不能构成它讨厌的形状。但是游戏里每移除一个方块都是要花费一些金币的，每个方块需要花费的金币有多有少参差不齐。老 C 当然希望尽可能少的使用游戏里的金币，但是最少要花费多少金币呢？老 C 懒得思考，就把这个问题交给你了。

inputFormat:
第一行有 $3$ 个正整数 $C,R,n$，表示 $C$ 列 $R$ 行的网格中，有 $n$ 个小方格放了小方块。

接下来 $n$ 行，每行 $3$ 个正整数 $x,y,w$，表示在第 $x$ 列第 $y$ 行的小方格里放了小方块，移除它需要花费 $w$ 个金币。保证不会重复，且都在网格范围内。

outputFormat: 输出一行，包含一个整数，表示最少花费的金币数量。

hint:
【输入输出样例 2 说明】 如图所示。容易发现，如果不移除第 $1$ 列第 $2$ 行的小方块，则至少要移除两个小方块，才能不包含老 C 讨厌的图形，花费至少 $20$ 个金币；而删除第 $1$ 列第 $2$ 行的小方块后，原有的讨厌图形全都不存在了，只需要花费 $15$ 个金币。

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

【数据规模与约定】

对于第 $1\sim 2$ 个测试点，$1\le C, R \le 100$，$1\leq n \leq 20$。

对于第 $3\sim 6$ 个测试点，$1 \leq C, R\leq 10^5$，$2000\le n\leq 5000$，数据有梯度。

对于第 $7\sim 10$ 个测试点，$1\leq C, R\leq 10^5$，$30000 \leq n\leq 10^5$，数据有梯度。

对于所有测试点，$1 \leq C, R, n \leq 10^5$，$ 1 \leq w \leq 10^4$。


title: [CQOI2017] 老C的键盘

description:
老 C 是个程序员。

作为一个优秀的程序员，老 C 拥有一个别具一格的键盘，据说这样可以大幅提升写程序的速度，还能让写出来的程序在某种神奇力量的驱使之下跑得非常快。

小 Q 也是一个程序员。有一天他悄悄潜入了老 C 的家中，想要看看这个键盘究竟有何妙处。他发现，这个键盘共有 $n$ 个按键，这 $n$ 个按键虽然整齐的排成一列，但是每个键的高度却互不相同。聪明的小 Q 马上将每个键的高度用 $1 \sim n$ 的整数表示了出来，得到一个 $1 \sim n$ 的排列 $h_1,h_2, \cdots ,h_n$。

为了回去之后可以仿造一个新键盘（新键盘每个键的高度也是一个 $1 \sim n$ 的排列），又不要和老 C 的键盘完全一样，小 Q 决定记录下若干对按键的高度关系。作为一个程序员，小 Q 当然不会随便选几对就记下来，而是选了非常有规律的一些按键对：对于 $i=2,3, \cdots ,n$，小 Q 都记录下了一个字符 `<` 或者 `>`，表示 $h_{\frac i2}<h_i$ 或者$h_{\frac i2}>h_i$。于是，小 Q 得到了一个长度为 $n-1$ 的字符串，开开心心的回家了。

现在，小 Q 想知道满足他所记录的高度关系的键盘有多少个。虽然小 Q 不希望自己的键盘和老 C 的完全相同，但是完全相同也算一个满足要求的键盘。答案可能很大，你只需要告诉小 Q 答案 $\bmod ~ 1,000,000,007$ 之后的结果即可。

inputFormat: 输入共一行，包含一个正整数 $n$ 和一个长度为 $n - 1$ 的只包含 `<` 和 `>` 的字符串，分别表示键盘上按键的数量，和小 Q 记录的信息，整数和字符串之间有一个空格间隔。

outputFormat: 输出共一行，包含一个整数，表示答案 $\bmod      ~ 1,000,000,007$ 后的结果。


title: 围栏木桩

description: 某农场有一个由按编号排列的 $n$ 根木桩构成的首尾不相连的围栏。现要在这个围栏中选取一些木桩，按照原有的编号次序排列之后，这些木桩高度成一个升序序列。所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数 $t$ 最大，并求出选取出 $t$ 根木桩的方案总数 $c$。

inputFormat: 文件中的第一行只有一个数 $m$，表明随后有 $m$ 个问题的描述信息。每个问题的描述信息格式为 $n,h_1,h_2,h_3,…,h_n$（其中 $h_i(i=1,2,3,…,n)$ 表示第 $i$ 根木桩的高度）。

outputFormat: 依次输出每个问题中 $t$ 和 $c$ 的解。每行输出一个问题的解。

hint: $m \leq 5$，$n \leq 20$，$h_i \leq 150$。


title: 马农

description:
在观看完战马检阅之后，来自大草原的两兄弟决心成为超级“马农”，专门饲养战马。

兄弟两回到草原，将可以养马的区域分为 $N \times N$ 的单位面积的正方形，并实地进行考察，归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了。首先，两人的马场都必须是矩形区域。同时，为了方便两人互相照应，也为了防止马匹互相走散，规定两个马场的矩形区域相邻，且只有一个交点。最后，互不认输的两人希望两个马场的收益相当，这样才不会影响他们兄弟的感情。现在，兄弟俩找到你这位设计师，希望你给他们设计马场，问共有多少种设计方案。

inputFormat: 第一行一个整数 $N$，表示整个草原的大小为 $N \times N$。接下来 $N$ 行，每行 $N$ 个整数 $A_{i,j}$，表示第 $i$ 行第 $j$ 列的单位草地的收成。（注意：收益可能是负数，养马也不是包赚的，马匹也可能出现生病死亡等意外。）

outputFormat: 输出符合两人要求的草原分配方案数。

hint: 对于所有数据，$1 \leq n \leq 50$。


title: 胖男孩

description:
麦克正如我们所知的已快乐地结婚，在上个月他胖了 $70$ 磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。

每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过 $3$ 个，误打的字符可能在正确字符之前也可能在其之后。

当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发 $3$ 遍，使他容易读懂一点。

编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。

inputFormat: 输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过 $100$ 个。

outputFormat: 输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。

hint: 由 @zhouyonglong 提供 SPJ


title: 任务安排

description:
$n$ 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间为 $t_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 $f_i$。请确定一个分组方案，使得总费用最小。

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

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

outputFormat: 一个数，最小的总费用。


title: EXCEEDED WARNING A

description:
有这样一些数据，它们均为小于 $10^9$ 的非负整数，且个数为 $n$，现在请你输出其中最小的 $m$ 个数。

小心溢出，注意 Memory Limit = 4000KiB。

inputFormat:
第一行以半角空格间隔开的两个非负整数： $n, m$

接下来的 $n$ 行，随机产生的 $n$ 个数，保证 $32$ 位整型变量可以存下。

outputFormat: 共 $m$ 行，即题目描述中的 $m$ 个数，从小到大依次输出。


title: EXCEEDED WARNING B

background: SGU 107

description: 求有多少个平方后末尾为 $987654321$ 的 $n$ 位数。

inputFormat: 一个整数 $n$。

outputFormat: 答案，即 **“平方后末尾为 $\bm{987654321}$ 的 $\bm{n}$ 位数”** 的个数

hint:
$1\le n\le 1 0^6$。

不要问我暴力能过几个点，我只想说呵呵。


title: [国家集训队] 墨墨的等式

description: 墨墨突然对等式很感兴趣，他正在研究 $\sum_{i=1}^n a_ix_i=b$ 存在非负整数解的条件，他要求你编写一个程序，给定 $n, a_{1\dots n}, l, r$，求出有多少 $b\in[l,r]$ 可以使等式存在非负整数解。

inputFormat:
第一行三个整数 $n,l,r$。

第二行 $n$ 个整数 $a_{1\dots n}$。

outputFormat: 一行一个整数，表示有多少 $b\in[l,r]$ 可以使等式存在非负整数解。


title: yyy2015c01 的 IDE 之 Watches

background: 在 2020 年的某一天，我们的 yyy2015c01 同学想要开发一套 IDE。

description:
作为他开发团队中的一员，你不幸地被选入了 Debugger 的开发组。

yyy2015c01 设想的 Debugger 由几部分组成，其中的一个小组件就是 Watches——中文称之为“变量观察器”。

由于 IDE 目前还是内测版，开发组需要先编一个能观察 int 类型变量值的 Watches 来看看效果如何。这个任务交由你来完成。

开发组假想的 Watches 能实现如下 3 种语句运行后监测相应变量值的功能：
- `n=1;` 将常量赋给变量，保证这个常量的位数不大于 $9$。
- `a=b;` 变量之间赋值：若原变量（在本例中是 $b$）未被赋值则认为其初始值为 $0$。
- `m=1+2;` $A+B$ 表达式赋值，只有 `+` 且只有两个数或者变量，$A$ 和 $B$ 都介于 $1$ 至 $10^6$ 之间。

请你编写一个 Watches，并在所有语句运行完后对所有被赋值过的变量按标识符的字典序输出它们的值（保证不会有变量的值大于 int 的最大值）。

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

第一行是一个正整数 $n$，表示共有 $n$ 条赋值语句；

第二行到第 $n+1$ 行，每行是一条赋值语句（格式为“变量名=赋值式子;”），保证不会有多余的其他字符。

outputFormat: 输出共 $n$ 行：每行是一个被赋值过的变量标识符及它的值。

hint:
数据很弱，直接模拟过哟~

（别想着变量标识符只有一位哟！）

另：向本题主人公 yyy2015c01 同学致敬！


title: [BJOI2017] 机动训练

background:
> AM 4:45
>
> 又是晴朗的好天气。
>
> AM 5:00
>
> 不要嘛，再睡一会
>
> AM 5:05
>
> 呜……欺负人

description:
睡眼朦胧的菜酱 (?) 已经被二爷拉起来晨跑了。而这个时间你在做什么呢？

咳咳，言归正传，最近菜酱的训练遇到了点小麻烦。

凌晨绕格瑞赛亚岛跑一圈是基本，在那之后，菜酱还要接受严格的机动训练。所谓机动训练，就是在紧急情况 (?) 下，高速且隐蔽地从位置 $s$ 移动到位置 $t$ 的训练。一般来说，$s$ 和 $t$ 是根据二爷的心情随机决定的，但是由于菜酱已经熟悉了地形，每次总是能找到不太费劲的路径，二爷决定增大难度。所谓增大难度，其实就是指定整条路径，这样菜酱就没办法抄近道了。当然，由于是为了实战而进行的训练，二爷也不会随便乱指定路径，至少不会故意绕路。然后发生的问题就是，如何才能「随机」一整条路径出来？二爷统计了全岛所有的合法路径，打算每次在这个表格里随机抽一条出来。但是很快二爷发现，许多路径所经过的地形是完全相同的，这类路径的训练会更加有用。于是二爷修改了随机策略，地形较为常见的路径权重会变得更大。

一次偶然的机会，菜酱看到了二爷的随机策略，并发动技能「过目不忘 (?)」记了下来。现在你要帮菜酱分析数据。

为什么是你？当然是因为否则就会被菜酱爆头 (并不)。

整个岛可以看作一片 $m\times n$ 的区域，每个格子有自己的地形。

一条路径由一系列八连通的格子组成，两个格子八连通当且仅当这两个格子拥有公共的顶点。

定义一条“机动路径”如下：

1. 它是一条不自交的路径，即路径上任意两个格子都不是同一个。
2. 它的起点和终点处于不同位置，换言之这条路径至少包含 $2$ 个格子。
3. 从起点开始，任何一步只能向不远离终点的方向移动，这里不远离指的是 $x$ 和 $y$ 两个方向都不远离。

举例说明：

```plain
.....t    ......    .---.
-++...    ---...    .-s-.
-s+...    -s+..t    .-+-.
---...    ---...    ..t..
```

图中加号和减号标明了与 $s$ 八连通的所有格子，其中加号是“不远离 $t$”的方向。

因此可以看出，如下路径是机动路径：

```plain
++++++t    ......+t    .......t
+......    .....++.    ......+.
+......    ..++++..    ...+++..
s......    s++.....    s+++....
```

而如下路径不是机动路径：

```plain
\../---t    .......t    .s.
|--.....    ....../.    /..
|.......    s..../..    \..
s.......    .\--/...    .t.
```

需要注意的是，某些不合法的路径甚至比机动路径还要短，这是因为机动路径不是按照长度来定义的。

接下来定义一条机动路径的地形，岛上的地形由一个矩阵给出，如：

```plain
.**.
*..*
*..*
.**.
```

那么，一条机动路径的地形序列就是它所经过的地形排成一列，如：

```plain
s-\.
...\
...|
...t
```

地形序列就是 `.****.`。

每条机动路径的权重就是与之拥有相同地形序列的机动路径数量之和，例如与这条路径拥有相同地形序列的路径有

```plain
./-t    t...    ...s    s-\.    ./-s    s...    ...t    t-\.
/...    |...    ...|    ...\    /...    |...    ...|    ...\
|...    \...    .../    ...|    |...    \...    .../    ...|
s...    .\-s    t-/.    ...t    t...    .\-t    s-/.    ...s
```

共 $8$ 条，注意回文时正反算两条，以及自己也算一条。

所以这条机动路径的权重是 $8$，同时所有这 $8$ 条机动路径的权重都是 $8$。

现在你需要统计所有的机动路径权重之和。

如果对这种统计方式没有直观的感受，可以查看样例说明。

inputFormat:
第一行两个整数 $m,n$，表示岛的大小。

接下来 $m$ 行，每行 $n$ 个字符，表示岛的地形。

outputFormat:
仅一个数，表示所有机动路径的权重之和。

由于这个数可能很大，你只需要输出它对 $10^9+9$ 取模的结果。


title: yyy2015c01挑战算周长

background: yyy2015c01 快速的解决了问题，受到邻居们的赞许，高兴的回到家，把糖给了妈妈，吃了香喷喷的午饭，又睡了一个甜甜的午觉，感觉人生真美好。下午爸爸回到家，听说了 yyy2015c01 帮老师及邻居们解决了难题，准备带她去游乐场玩她平日最喜欢玩的跳舞机作为奖励，yyy2015c01 听了，兴奋的一蹦三尺高。

description:
游乐场里人头攒动，每台跳舞机前都围满了人，怎么办呢？人这么多，想玩上估计要等好久了，yyy2015c01 左顾右盼，突然发现一台跳舞机前面没人， “哈哈，被我发现一台没人的，赶快去……”，结果到了面前才发现这台新机器的玩法与众不同，脚下的格子随机位置显示出很多的 `X`，踩到一个格子，就要根据规则先算出它对应的周长，然后把正确周长输入机器，最后的胜利者还可以获得游乐城的免费游戏券一张，yyy2015c01 心动了，小朋友们，你们可以帮助 yyy2015c01 顺利拿到游戏券么？

游戏规则如下：

新跳舞机踏板上有许多要分析的目标，由脚踩确定一个目标。目标边界的周长是一个有用的测量参数。编程任务：确定选中目标的周长。新跳舞机的踏板是一个矩形的网格，里面点 `.`，表示空的地方；有大写字母 `X`，表示目标的一部分。

方格中的一个 `X` 是指一个完整的网格方形区域，包括其边界和目标本身。网格中心的 `X` 与其边界上 $8$ 个方向的 `X` 都是相邻的。任何两个相邻的 `X`，其网格方形区域在边界或拐角处是重叠的，所以它们的网格方形区域是相邻的。一个目标是由一系列相邻 `X` 的网格方形区域连接起来构成的。在网格 $1$ 中，一个目标填充了全部网格；在网格 $2$ 中有两个目标，其中一个目标只占左下角的一个网格方形区域，其余的 `X` 属于另一个目标。

yyy2015c01 总是能踩到一个 `X`，以选中包含该 `X` 的目标，记录脚踩时的坐标。行列号是从左上角开始，从 $1$ 开始编号的。一个有用的统计参数是目标的周长。 假定每个 `X` 的每条边上有一个方形的单元。

目标中不会包含任何完全封闭的孔。

inputFormat: 共 $M+1$ 行，第一行为四个正整数 $M,N,X,Y$（中间用空格隔开），表示网格的大小为 $M$ 行，$N$ 列，且踩中网格的第 $X$ 行第 $Y$ 列方格。后面就是 $M$ 行，由字符 `.` 和 `X` 构成。

outputFormat: 共一行，表示选中目标的周长。

hint: $1\leq M\leq 20$，$1\leq N\leq 20$，$1\leq X\leq M$，$1\leq Y\leq N$。


title: yyy2015c01 的 IDE 之 Call Stack

description:
作为他开发团队中的一员，你不幸地 yyy2015c01 被选入了 Debugger 的开发组。

yyy2015c01 设想的 Debugger 由几部分组成，其中的一个小组件就是 Call Stack——中文称之为 “调用栈”。

由于 IDE 目前还是内测版，开发组需要先编一个能识别参数表的 Call Stack 来看看效果如何。这个任务交由你来完成。

开发组假想的 Call Stack 能实现识别 `int` 和 `char` 参数表，以辨别出不同的函数，规则是：

```
int fac1(int n);
```

和

```
int fac1(char n);
```

是两个不同的函数；但

```
int Fac1(int n,int m);
```

和

```
int FAC1(int x,int y);
```

被认为是相同的函数。也就是说，这个 Call Stack 认的不是参数名，而是其类型和忽略大小写的函数名。

注意：`int main()` 可能会出现，也可能不出现；无论它有没有出现，都不能将其算入函数中。

请你编写一个 Call Stack，并在所有函数调用完后输出这个程序一共有多少个不完全相同的函数（保证程序中的每个函数至少调用一次）。

inputFormat: 输入共 $n + 1$ 行：第一行是一个正整数 $n$，表示共有 $n$ 次调用操作；第 $2 \sim n+1$ 行每行是一条函数调用信息（严格按照样例输入的格式），保证不会有多余的其他字符。

outputFormat: 输出共一行：一个正整数 $m$，表示在上述调用中共有多少个参数表不完全相同的函数。

hint:
每个函数的参数最多有 $10$ 个，每行的输入数据长度均不超过 $255$。

向本题主人公 yyy2015c01 同学致敬！


title: yyy2015c01 的 U 盘

background: 在 2020 年的某一天，我们的 yyy2015c01 买了个高端 U 盘。

description:
你找 yyy2015c01 借到了这个高端的 U 盘，拷贝一些重要资料，但是你发现这个 U 盘有一些问题：

1. 这个 U 盘的传输接口很小，只能传输大小不超过 $L$ 的文件。
2. 这个 U 盘容量很小，一共只能装不超过 $S$ 的文件。

但是你要备份的资料却有很多，你只能备份其中的一部分。

为了选择要备份哪些文件，你给所有文件设置了一个价值 $V_i$，你希望备份的文件总价值不小于 $p$。

但是很快你发现这是不可能的，因为 yyy2015c01 的传输接口太小了，你只有花钱买一个更大的接口（更大的接口意味着可以传输更大的文件，但是购买它会花费更多的钱）。

注意：你的文件不能被分割（你只能把一个文件整个的传输进去，并储存在U盘中）,

你放在 U 盘中文件的总大小不能超过 U 盘容量。

现在问题来了：你想知道，在满足 U 盘中文件价值之和**不小于** $p$ 时，最小需要多大的接口。

inputFormat:
第 $1$ 行，三个正整数 $n,p,S$ 分别表示文件总数，希望最小价值 $p$ ，U 盘大小。

接下来 $n$ 行，每行两个正整数 $W_{i},V_{i}$，表示第 $i$ 个文件的大小和价值。

outputFormat:
输出一个正整数表示最小需要的接口大小。

如果无解输出 `No Solution!`。

hint:
$1 \le n, W_i, S \le 10^3$，$1 \leq V_i \leq 10^6$，$1 \leq p \leq 10^9$。

数据较小，请勿乱搞。

样例解释 $1$：买一个大小为 $2$ 接口，把物品 $1$ 、$2$ 放进$\text{U}$盘。

样例解释 $2$：买一个大小为 $500$ 的接口。

样例解释 $3$：本来可以买大小为 $2$ 的接口，可是 U 盘容量放不下足够的文件。

如果数据出现疏漏，请联系出题人 [a710128](https://www.luogu.com.cn/user/2573)

向本题主人公 yyy2015c01 同学致敬！


title: [NOI2014] 动物园

description:
近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

某天，园长给动物们讲解 KMP 算法。

园长：“对于一个字符串 $S$，它的长度为 $L$。我们可以在 $O(L)$ 的时间内，求出一个名为 $\mathrm{next}$ 的数组。有谁预习了 $\mathrm{next}$ 数组的含义吗？”

熊猫：“对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作 $\mathrm{next}[i]$。”

园长：“非常好！那你能举个例子吗？”

熊猫：“例 $S$ 为 $\verb!abcababc!$，则 $\mathrm{next}[5]=2$。因为$S$的前$5$个字符为 $\verb!abcab!$，$\verb!ab!$ 既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出 $\mathrm{next}[1] = \mathrm{next}[2] = \mathrm{next}[3] = 0$，$\mathrm{next}[4] = \mathrm{next}[6] = 1$，$\mathrm{next}[7] = 2$，$\mathrm{next}[8] = 3$。”

园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在 $O(L)$ 的时间内求出 $\mathrm{next}$ 数组。

下课前，园长提出了一个问题：“KMP 算法只能求出 $\mathrm{next}$ 数组。我现在希望求出一个更强大 $\mathrm{num}$ 数组一一对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $\mathrm{num}[i]$。例如 $S$ 为 $\verb!aaaaa!$，则 $\mathrm{num}[4] = 2$。这是因为$S$的前 $4$ 个字符为 $\verb!aaaa!$，其中 $\verb!a!$ 和 $\verb!aa!$ 都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而 $\verb!aaa!$ 虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，$\mathrm{num}[1] = 0,\mathrm{num}[2] = \mathrm{num}[3] = 1,\mathrm{num}[5] = 2$。”

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出$\mathrm{num}$数组呢？

特别地，为了避免大量的输出，你不需要输出 $\mathrm{num}[i]$ 分别是多少，你只需要输出所有 $(\mathrm{num}[i]+1)$ 的乘积，对 $10^9 + 7$ 取模的结果即可。

inputFormat:
第 $1$ 行仅包含一个正整数 $n$，表示测试数据的组数。
随后 $n$ 行，每行描述一组测试数据。每组测试数据仅含有一个字符串 $S$，$S$ 的定义详见题目描述。数据保证 $S$ 中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。

outputFormat: 包含 $n$ 行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对 $10^9+7$ 取模的结果。输出文件中不应包含多余的空行。


title: 搬运工

background: 陈老师喜欢网购书籍，经常一次购它个百八十本，然后拿来倒卖牟取暴利。

description:
前些天，高一的新同学来了，他便像往常一样兜售他的书，经过一番口舌，同学们决定买他的书，但是陈老师桌上的书有三堆，每一堆都有厚厚的一叠，他要想个办法用最轻松的方式把书拿下来给同学们。但是你想逗一下陈老师，于是你设计一个最累的方式给他。若告诉你这三堆分别有 $i$，$j$，$k$ 本书，以及每堆从下到上书的质量，每次取书只能从任一堆的最上面取，那么请你设计一个方案，让他花最大的力气取下所有的书。

显然，每次取书陈老师的体力消耗都会加大，这里用体力系数代表，取下第一本书时，体力系数为 $1$，第二本书时体力系数为 $2$，依次类推，而每次体力消耗值则为体力系数与书的重量之积。

inputFormat:
第一行有三个整数，分别为三堆书的数量 $i$，$j$，$k$。

第二行至第四行分别为每堆由下至上的书本重量。

outputFormat: 输出最累方式的体力消耗总值。

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

+ 对于 $50\%$ 的数据有 $0\le i,j,k\lt10$。
+ 对于 $100\%$ 的数据有 $0\le i,j,k\lt100$。

最后输出的体力消耗总值在 C++ int 范围内。


title: [USACO09OCT] Allowance G

description:
作为创造产奶纪录的回报，Farmer John 决定开始每个星期给Bessie 一点零花钱。

FJ 有一些硬币，一共有 $N (1 \le N \le 20)$ 种不同的面额。每一个面额都能整除所有比它大的面额。

他想用给定的硬币的集合，每个星期至少给 Bessie 某个零花钱的数目 $C (1 \le C \le 100000000)$。请帮他计算他最多能支付多少个星期的零花钱。

inputFormat:
第 $1$ 行: 两个由空格隔开的整数: $N$ 和 $C$；

第 $2$ 到第 $N+1$ 行: 每一行有两个整数表示一个面额的硬币：硬币面额 $V (1 \le V \le 100,000,000)$ 拥有的该面额的硬币数 $B (1 \le B \le 1,000,000)$。

outputFormat: 第 $1$ 行: 一个单独的整数，表示最多能给支付多少个星期至少为 $C$ 的零用钱。


title: 放苹果

description: 把 $m$ 个同样的苹果放在 $n$ 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法。（$5,1,1$ 和 $1,1,5$ 是同一种方法）

inputFormat: 第一行是测试数据的数目 $t$，以下每行均包括二个整数 $m$ 和 $n$，以空格分开。

outputFormat: 对输入的每组数据 $m$ 和 $n$，用一行输出相应的结果。

hint: 对于所有数据，保证：$1\leq m,n\leq 10$，$0 \leq t \leq 20$。


title: 三角形图

background: 模拟赛一道难过到我的题

description:
一个三角形网格上，每个小三角形的面积都为1。你可以从某个点开始，沿着边走出一个多边形来，使得围成一定的面积。我们可以给每个点定义5个方向：

a    左转120°

b    左转60°

c    直走

d    右转60°

e    右转120°

这样的话，一个图形就能被一组字母表示出来。 ![](https://cdn.luogu.com.cn/upload/pic/1430.png)  ![](https://cdn.luogu.com.cn/upload/pic/1423.png) 比如左边的图，从A点开始顺时针走，则可以表示为dcddeaddd；从B点开始顺时针走，则可以表示ddeaddddc；……。右图显示的是左图翻折后的情况。

左图和右图是本质相同的图形。为了惟一地表示一类全等的图形，我们在这类图形的所有表示方法中找字典序最小的表示方法来代表这一类全等的图形。左图和右图的最小表示方法相同，都是addddcdde。

现在告诉你一个图形的某个表示法（不一定是最小表示方法），请你求出在这个图形的基础上加一个小三角形后合法图形的个数，以及他们的最小表示方法。

一个图形是合法的，当且仅当组成它的所有小三角形均有至少一条与其他三角形公共的边，且不存在中空。

下面的图形都是不合法的： ![](https://cdn.luogu.com.cn/upload/pic/1425.png)  ![](https://cdn.luogu.com.cn/upload/pic/1426.png)  ![](https://cdn.luogu.com.cn/upload/pic/1427.png)  ![](https://cdn.luogu.com.cn/upload/pic/1428.png)

inputFormat:
第一行1个数字T，表示数据组数。

接下来T行每行一个字符串，表示某个图形的某个表示方法。

读入数据保证一定合法，且一定是顺时针的表示方法。

outputFormat:
对于每组数据：

第一行1个整数K，表示加一个小三角形后的不全等的图形的个数。

接下来一行K个字符串，表示这K个不同图形的最小表示方法（按字典序排序），字符串两两之间用一个空格隔开，最小表示方法必须是顺时针的。

两组数据间用一个空行隔开。

samples:
5
acedccecced addebcecced adebebecced adecbedcced cceccecce

1
cddddce

hint:
样例解释

Sample 1 的解释：

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


title: 因式分解II

description:
小玉上了初中，开始学因式分解。可是她怎么都解不出来。所以她求你帮忙。

她给你看了她的作业，就是因式分解。由于刚开始学，就降低了难度。

我们假设作业里面的代数只有一个x。最高指数是2，且最高指数的系数是1。当x前的系数是1时，1省去……（反正作业题目符合我们的日常写法）

我们帮她解决下这个“简单”的问题吧！虽然听起来挺容易，但是编程需要考虑很多情况呢！

保证作业答案的数字都是整数。

// 这跟神器有什么关系么？神说，帮助他人，积累善行，神器自然出现。哈哈哈哈好牵强的解释~

//为了帮助在5月月赛ac这道题目，kkksc03偷偷地进行以下的温馨提示：

//数据可能会比较刁钻，请考虑到各种情况，包括只有输入一项的情况、中间过程会不会超maxlongint的情况等。

//lzn：喂！你这是透题行为，是要上法庭的！

//absi2011:样例输出里的"//"及以后字符只是注解,并不要你输出

/\*
absi2011:输入规范好不和谐啊...

我只是来补充一下...

如果x或者常数项的系数是0 整个省略掉

哦,x的系数是-1的话 也会把1省去...

保证输入的那玩意儿可以分解....而且分解出来都是整数...

\*/

// 原作: 2022.7.24 没想到初中时候贡的题已经~~坑害了~~这么多人ac了.  现在已经大二，时过境迁，已经完全不会了哈哈哈

inputFormat: 一个多项式，要求前面已述。各个系数<=maxlongint。

outputFormat:
几个乘积。答案也符合日常写法。为了方便老师批改，若将答案表示成(x+a)(x+b)，则a>b。

什么是日常写法？

1、(x+0)写成x

2、(x+a)(x+a)写成(x+a)^2

3、有时候可以这样写：(x-3)。但是不能出现类似于(x+-3)这样的写法

samples:
(x+1)x
//反过来是不可以的。

hint: x次数不高于2次，项数不高于3项，降幂排列。


title: [BJOI2017] 树的难题

description:
给你一棵 $n$ 个点的无根树。

树上的每条边具有颜色。一共有 $m$ 种颜色，编号为 $1$ 到 $m$，第 $i$ 种颜色的权值为 $c_i$。

对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划分成若干个相同颜色段。定义路径权值为颜色序列上每个同颜色段的颜色权值之和。

请你计算，经过边数在 $l$ 到 $r$ 之间的所有简单路径中，路径权值的最大值。

inputFormat:
第一行，四个整数 $n, m, l, r$。

第二行，$m$ 个整数 $c_1, c_2, \ldots, c_m$，由空格隔开，依次表示每个颜色的权值。

接下来 $n-1$ 行，每行三个整数 $u, v, c$，表示点 $u$ 和点 $v$ 之间有一条颜色为 $c$ 的边。

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


title: [BJOI2017] 魔法咒语

description:
Chandra 是一个魔法天才。

从一岁时接受火之教会洗礼之后，Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。

直到十四岁，开始学习威力强大的禁咒法术时，Chandra 才遇到了障碍。

根据火之魔法规则，禁咒的构成单位是 $N$ 个基本词汇。施法时只要凝聚精神力，说出一段用这些词语组成的长度恰好等于 $L$ 的语言，就能释放威力超乎想象的火法术。过去的魔法师们总结了几种表达起来最连贯的组合方式，方便施法者以最快语速完成法术。

但具有魔法和语言双重天才的 Chandra 不满足于这几种流传下来的禁咒，因为她可以毫无困难地说出普通人几乎不可能表达的禁咒语句。然而，在实际施法时，Chandra 发现有些自创禁咒念出后不但没有预期效果，反而会使自己的精神力迅速枯竭，十分难受。

这个问题令 Chandra 万分不解。她大量阅读典籍，到处走访魔法学者，并且不顾精神折磨一次又一次尝试新咒语，希望找出问题的答案。

很多年过去了，在一次远古遗迹探险中，Chandra 意外闯进了火之神艾利克斯的不知名神殿。根据岩土特征分析，神殿应该有上万年的历史，这是极其罕见的。Chandra 小心翼翼地四处探索，沿着魔力流动来到一间密室。她看见密室中央悬浮着一本书籍。在魔法保护下书籍状况完好。精通上古语言的 Chandra 读过此书，终于解开了多年的困惑。

禁咒法术之所以威力强大，是因为咒语借用了火之神艾利克斯的神力。这本书里记载了艾利克斯生平忌讳的 $M$ 个词语，比如情敌的名字、讨厌的植物等等。使用禁咒法术时，如果语言中含有任何忌讳词语，就会触怒神力而失效，施法者也一并遭受惩罚。

例如，若 `banana` 是唯一的忌讳词语，`an`、`ban`、`analysis` 是基本词汇，禁咒长度须是 $11$，则 `bananalysis` 是无效法术，`analysisban`、`anbanbanban` 是两个有效法术。注意：一个基本词汇在禁咒法术中可以出现零次、一次或多次；只要组成方式不同就认为是不同的禁咒法术，即使书写形式相同。

谜题破解，Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。

由于答案可能很大，你只需要输出答案模 $10 ^ 9 + 7$ 的结果。

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

接下来 $N$ 行，每行一个只含小写英文字母的字符串，表示一个基本词汇。

接下来 $M$ 行，每行一个只含小写英文字母的字符串，表示一个忌讳词语。

outputFormat: 仅一行，一个整数，表示答案（模 $10^9+7$）。

hint:
【样例解释 1】

有效的禁咒法术共有 $14$ 种：`boom/bang/oo`，`oo/oo/oo/oo/oo`，`oo/oo/ooh/ooh`，`oo/ooh/oo/ooh`，`oo/ooh/ooh/oo`，`ooh/oo/oo/ooh`，`ooh/oo/ooh/oo`，`
ooh/ooh/boom`，`ooh/ooh/oo/oo`，`ooh/ooh/bang`，`ooh/bang/ooh`，`bang/oo/oo/oo`，`bang/ooh/ooh`，`bang/bang/oo`。

【样例解释 2】

有效的禁咒法术有 `a/ab`，`ab/a`，`aba` 共三种。注意，`ab/a` 和 `aba` 算成两种不同的禁咒法术。

【数据规模与约定】

本题一共有 $10$ 个测试点。

下表是每个测试点的数据规模和约定：

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

对于 $100\%$ 的数据，$1 \le N, M \le 50，1 \le L \le 10^8$，基本词汇的长度之和不超过 $100$，忌讳词语的长度之和不超过 $100$。保证基本词汇不重复，忌讳词语不重复。


title: [AH2017/HNOI2017] 礼物

description:
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 $n$ 个装饰物，并且每个装饰物都有一定的亮度。

但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的非负整数 $c$。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1 \sim n$，其中 $n$ 为每个手环的装饰物个数， 第 $1$ 个手环的 $i$ 号位置装饰物亮度为 $x_i$，第 $2$ 个手环的 $i$ 号位置装饰物亮度为 $y_i$，两个手环之间的差异值为（参见输入输出样例和样例解释）：

$$\sum_{i=1}^{n} (x_i-y_i)^2$$

麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

inputFormat:
输入数据的第一行有两个数 $n,m$，代表每条手环的装饰物的数量为 $n$，每个装饰物的初始亮度小于等于 $m$。

接下来两行，每行各有 $n$ 个数，分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

outputFormat: 输出一个数，表示两个手环能产生的最小差异值。注意在将手环改造之后，装饰物的亮度可以大于 $m$。

hint:
【样例解释】

需要将第一个手环的亮度增加 $1$，第一个手环的亮度变为：$2,3,4,5,6$

旋转一下第二个手环。对于该样例，是将第二个手环的亮度 $6,3,3,4,5$ 向左循环移动一个位置，使得第二手环的最终的亮度为：$3,3,4,5,6$。

此时两个手环的亮度差异值为 $1$。

【数据范围】

对于 $30\%$ 的数据，$n \le 500$，$m \le 10$；

对于 $70\%$ 的数据，$n \le 5000$；

对于 $100\%$ 的数据，$1 \le n \le 50000$, $1 \le a_i \le m \le 100$。


title: [AHOI2017/HNOI2017] 大佬

description:
人们总是难免会碰到大佬。他们趾高气昂地谈论凡人不能理解的算法和数据结构，走到任何一个地方，大佬的气场就能让周围的人吓得瑟瑟发抖，不敢言语。你作为一个 OIer，面对这样的事情非常不开心，于是发表了对大佬不敬的言论。 大佬便对你开始了报复，你也不示弱，扬言要打倒大佬。现在给你讲解一下什么是大佬，大佬除了是神犇以外，还有着强大的自信心，自信程度可以被量化为一个正整数 $C$，想要打倒一个大佬的唯一方法是摧毁 Ta 的自信心，也就是让大佬的自信值**等于** $0$（恰好等于 $0$，不能小于 $0$）。由于你被大佬盯上了，所以你需要准备好 $n$ 天来和大佬较量，因为这 $n$ 天大佬只会嘲讽你动摇你的自信，到了第 $n+1$ 天，如果大佬发现你还不服，就会直接虐到你服，这样你就丧失斗争的能力了。

你的自信程度同样也可以被量化，我们用 $\mathrm{mc}$ 来表示你的自信值**上限**。在第 $i \ (i\ge 1)$ 天，大佬会对你发动一次嘲讽，使你的自信值减小 $a_i$，如果这个时刻你的自信值**小于** $0$ 了，那么你就丧失斗争能力，也就**失败**了（特别注意你的自信值为 $0$ 的时候还可以继续和大佬斗争）。 在这一天，大佬对你发动嘲讽之后，如果你的自信值仍大于等于 $0$，你**能且仅能**选择如下的行为**之一**：

1. 还一句嘴，大佬会有点惊讶，导致大佬的自信值 $C$ 减小 $1$。
2. 做一天的水题，使得自己的当前自信值增加 $w_i$，并将新自信值和自信值上限 $\mathrm{mc}$ 比较，若新自信值大于 $\mathrm{mc}$，则新自信值更新为 $\mathrm{mc}$。例如，$\mathrm{mc} = 50$，当前自信值为 $40$，若 $w_i = 5$，则新自信值为 $45$，若 $w_i = 11$，则新自信值为 $50$。
3. 让自己的等级值 $L$ 加 $1$。
4. 让自己的讽刺能力 $F$ 乘以自己当前等级 $L$，使讽刺能力 $F$ 更新为 $F\cdot L$。
5. 怼大佬，让大佬的自信值 $C$ 减小 $F$。并在怼完大佬之后，你自己的等级 $L$ 自动降为 $0$，讽刺能力 $F$ 降为 $1$。由于怼大佬比较掉人品，所以这个操作只能做**不超过两次**。

**特别注意**的是，在任何时候，你**不能**让大佬的自信值**为负**，因为自信值为负，对大佬来说意味着屈辱，而大佬但凡遇到屈辱就会进化为更厉害的大佬直接虐飞你。在第 $1$ 天，在你被攻击之前，你的自信是满的（初始自信值等于自信值上限 $\mathrm{mc}$），你的讽刺能力 $F$ 是 $1$，等级是 $0$。

现在由于你得罪了大佬，你需要准备和大佬正面杠，你知道世界上一共有 $m$ 个大佬，他们的嘲讽时间都是 $n$ 天，而且第 $i$ 天的嘲讽值都是 $a_i$。不管和哪个大佬较量，你在第 $i$ 天做水题的自信回涨都是 $w_i$。这 $m$ 个大佬中**只会有一个**来和你较量（$n$ 天里都是这个大佬和你较量），但是作为你，你需要知道对于任意一个大佬，你是否能摧毁他的自信，也就是让他的自信值恰好等于 $0$。和某一个大佬较量时，其他大佬不会插手。

inputFormat:
第一行三个正整数 $n,m,\mathrm{mc}$。分别表示有 $n$ 天和 $m$ 个大佬，你的自信上限为 $\mathrm{mc}$。

接下来一行是用空格隔开的 $n$ 个数，其中第 $i(1\le i\le n)$ 个表示 $a_i$。

接下来一行是用空格隔开的 $n$ 个数，其中第 $i(1\le i\le n)$ 个表示 $w_i$。

接下来 $m$ 行，每行一个正整数，其中第 $k(1\le k\le m)$ 行的正整数 $C_k$ 表示第 $k$ 个大佬的初始自信值。

outputFormat: 共 $m$ 行，如果能战胜第 $k$ 个大佬（让他的自信值恰好等于 0），那么第 $k$ 行输出 $1$，否则输出 $0$。

hint:
- 对于 $20\%$ 的数据，$1\le n\le 10$；
- 另有 $20\%$ 数据，$1\le C_i,n,\mathrm{mc}\le 30$；
- 对于 $100\%$ 的数据，$1\le n, \mathrm{mc}\le 100, 1\le m\le 20; 1\le a_i, w_i\le\mathrm{mc}, 1\le C_i\le 10^8$。


title: 整式的计算【数据有误】

background: 小明上了初中，整式计算总是出错，所以他找到了爱编程的你，让你设计一个程序帮帮他。

description: 输入几个单项式或多项式，计算结果。

inputFormat: 包括+，-,\*,字母(只包括a到z26个小写字母)单项式两边没有括号，多项式两边有( )或[ ]，保证在每一个因式中，单项式在多项式前面。（长度不超过255）

outputFormat: 输出这个表达式的结果，每个因式按字典序排列。

hint: 水题一道。


title: 狗哥采矿

background:
又是一节平静的语文课。

狗哥闲来无事，出来了这么一道题。

description: 一个 $n\times m$ 的矩阵中，每个格子内有两种矿 yeyenum 和 bloggium，并且知道它们在每个格子内的数量是多少。最北边有 bloggium 的收集站，最西边有 yeyenum 的收集站。现在要你在这些格子上面安装向北或者向西的传送带（每个格子只能装一种）。问最多能采到多少矿？

inputFormat: 第一行包含两个整数 $n,m,\ ( 1 ≤ n ≤ 500, 1 ≤ m ≤ 500)$。接下来 $n$ 行 $m$ 列，表示每个格子中可以传送到 yeyenum 的数量（小于 $1000$），再接下来 $n$ 行 $m$ 列，表示每个格子中可以传送到 bloggium 的数量。$n, m$ 同时为 $0$ 时结束。

outputFormat: 每组测试数据仅输出一个数，表示最多能采到的矿。

hint: 传输过程中不能转弯，只能走直路。


title: 狗哥玩木棒

background: 狗哥又趁着语文课干些无聊的事了...

description: 现给出一些木棒长度，那么狗哥能否用给出的木棒(木棒全用完)组成一个正方形呢？

inputFormat: 输入文件中的第一行是一个整数 $n(1\le n\le 10)$ 表示测试的组数，接下来 $n$ 行表示每组的测试数据。 每行的第一个数为 $m(4\leq m\leq 20)$,接下来 $m$ 个数 $a_i(1\leq a_i\le 1000)$ 表示木棒的长度。

outputFormat: 对于每组测试数据，如果可以组成正方形输出“yes”，否则输出“no”。

hint: 狗哥快抓狂了


title: [TJOI2017] 可乐

description: 加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市，问经过了 $t$ 秒，可乐机器人的行为方案数是多少？

inputFormat:
第一行输入两个正整数 $N$，$M$。$N$ 表示城市个数，$M$ 表示道路个数。

接下来 $M$ 行每行两个整数 $u$，$v$，表示 $u$，$v$ 之间有一条道路。保证两座城市之间只有一条路相连，且没有任何一条道路连接两个相同的城市。

最后一行是一个整数 $t$，表示经过的时间。

outputFormat: 输出可乐机器人的行为方案数，答案可能很大，请输出对 $2017$ 取模后的结果。


title: [AH2017/HNOI2017] 队长快跑

description:
众所周知，在 P 国外不远处盘踞着巨龙大 Y。传说中，在远古时代，巨龙大 Y 将 P 国的镇国之宝窃走并藏在了其巢穴中，这吸引着整个 P 国的所有冒险家前去夺回，尤其是皇家卫士队的队长小 W。在 P 国量子科技实验室的帮助下，队长小 W 通过量子传输进入了巨龙大 Y 的藏宝室，并成功夺回了镇国之宝。但此时巨龙布下的攻击性防壁启动，将小 W 困在了美杜莎的迷宫当中。

被困在迷宫 $(0,0)$ 处的队长小 W 快速观察了美杜莎的迷宫的构造，发现迷宫的出口位于 $(p,q)$ 处。巨龙大 Y 在迷宫当中布置了 $n$ 火焰吐息机关，每个机关可以用三个参数 $(x,y,\theta)$ 表示，分别指明机关位于平面的坐标 $(x,y)$，以及火焰吐息的方向相对于 $x$ 正方向的倾角 $\theta$。巨龙强大的力量使得火焰吐息有无穷长，且队长小  W 不能通过被火焰吐息覆盖的射线（注意，机关所处的坐标若没有被其他火焰吐息覆盖，则是可以通过的）。同时，迷宫在沿 $x$ 负方向无穷远的地方放置了美杜莎之眼，使得队长小 W 必须倾向于向 $x$ 正方向行动（即队长小 W 的移动方向在 $x$ 正方向上的投影必须为正，不能是负数或零），否则队长小 W 将被瞬间石化而无法逃离。

心急如焚的队长小 W 需要趁着巨龙大 Y 还没将其抓住前逃离美杜莎的迷宫，所以他立马向 P 国智囊团求助，作为智囊团团长的你，一定可以帮队长小 W 找出安全逃至迷宫出口的最短道路。

inputFormat:
第一行为三个整数 $n,p,q$ 分别表示火焰吐息机关总数以及出口坐标。

接下来 $n$ 行，每行两个整数与一个实数 $(x,y,\theta)$ 分别表示机关所处的坐标以及火焰吐息的关于 $x$ 正方向的倾角。

outputFormat: 输出文件仅包含一行一个小数，表示最短道路的长度。当你的答案和标准答案的相对误差不超过 $10^{-8}$ 时（ 即 $\frac{|a-o|}{a}\leq10^{-8}$ 时， 其中 $a$ 是标准答案，$o$ 是输出）认为你的答案正确。

hint:
【样例解释】

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

$30\%$ 的数据满足 $n\leq 300$；

$60\%$ 的数据满足 $n\leq 2000$；

$80\%$ 的数据满足 $n\leq 10^5$；

$100\%$ 的数据满足： $0 \leq n,p, |q|, |x|, |y| \leq 10^6； \theta \in [−\pi, \pi]$。
数据保证至少存在一条合法路径，且起点和终点均不会被火焰路径覆盖。


title: [AH2017/HNOI2017] 抛硬币

description:
小 A 和小 B 是一对好朋友，他们经常一起愉快的玩耍。最近小 B 沉迷于**师手游，天天刷本，根本无心搞学习。但是已经入坑了几个月，却一次都没有抽到 SSR，让他非常怀疑人生。勤勉的小 A 为了劝说小 B 早日脱坑，认真学习，决定以抛硬币的形式让小 B 明白他是一个彻彻底底的非洲人，从而对这个游戏绝望。两个人同时抛 b 次硬币，如果小 A 的正面朝上的次数大于小 B 正面朝上的次数，则小 A 获胜。

但事实上，小 A 也曾经沉迷过拉拉游戏，而且他一次 UR 也没有抽到过，所以他对于自己的运气也没有太大把握。所以他决定在小 B 没注意的时候作弊，悄悄地多抛几次硬币，当然，为了不让小 B 怀疑，他不会抛太多次。现在小 A 想问你，在多少种可能的情况下，他能够胜过小 B 呢？由于答案可能太大，所以你只需要输出答案在十进制表示下的最后 $k$ 位即可。

inputFormat: 有多组数据，对于每组数据输入三个数 $a,b,k$，分别代表小 A 抛硬币的次数，小 B 抛硬币的次数，以及最终答案保留多少位整数。

outputFormat: 对于每组数据，输出一个数，表示最终答案的最后 $k$ 位为多少，若不足 $k$ 位以 $0$ 补全。


title: [TJOI2017] 异或和

description:
在加里敦中学的小明最近爱上了数学竞赛，很多数学竞赛的题都是与序列的连续和相关的。  所以对于一个序列，求出它们所有的连续和来说，小明觉得十分的简单。

但今天小明遇到了一个序列和的难题，这个题目不仅要求你快速的求出所有的连续和（即子串和），还要快速的求出这些连续和的异或值。

小明很快的就求出了所有的连续和，但是小明要考考你，在不告诉连续和的情况下，让你快速求是序列所有连续和的异或值。

inputFormat:
第一行输入一个 $n$，表示这序列的数序列。

第二行输入 $n$ 个非负整数 $a_1,a_2 \dots a_n$ 代表这个序列。

outputFormat: 输出这个序列所有的连续和的异或值。

hint:
【样例解释】

序列 $[1,2,3]$ 有 $6$ 个连续和，它们分别是 $1,2,3,3,5,6$，而 $1 \text{ xor } 2 \text{ xor } 3 \text{ xor } 3 \text{ xor } 5 \text{ xor } 6 = 0$。

【数据范围】

- 对于 $20\%$ 的数据，$1\le n \le 100$；
- 对于 $100\%$ 的数据，$1\le n \le 10^5$，$\sum a_i \le 10^6$。


title: 化学分子式

background: 元首和元老正在共同努力学习化学，他们想让电脑帮助他模拟分子式减轻负担。请你帮他设计一个程序。

description:
你的任务是编写一个能处理在虚拟的化学里分子式的程序，在真正的化学里，每个分子式描述分子包括一个或者多个原子，但是，它可能没有真正的化学药品。

下面是原子符号和分子式的定义：

分子中一个原子由一个原子符号表示，原子符号由单个大写字母或者一个大写字母和一个小写字母组成。例如：H和He都是原子符号。

一个分子式是一个原子符号的非空序列，例如，HHHeHHHe是一个分子式，表示一个分子包括4个H和2个He。

为了方便起见，一段相同的式子，如x….x(n个X，2<=n<=99)，可以被缩写为（X）n。如果X是一个原子符号，那么括号可以省略。例如，HHHeHHHe也可以写作H2HeH2He,(HHHe)2,(H2He)2,((H)2He)2。

分子式的定义可以用一种规范的语言描述。简而言之，分子式的语法描述如下：

分子：原子|原子数量|（分子）数字|分子 分子
原子：大写字母|大写字母 小写字母

数字：2|3|4|5|……|99|
大写字母：A|B|……|Z|
小写字母：a|b|c|……|z|

在我们这个虚拟的化学里的每一个原子都有自己的原子质量，给你原子的质量，你的程序必须输出一个用分子式表示的分子质量。分子的质量定义为所有包括的原子的质量之和。例如，假设H和He的原子质量为1和4，那么（H2He）2的分子量为12。

inputFormat:
输入格式：

输入由两部分组成。第一部分是原子表，由一些行组成，每行包括一个原子符号、一个或者多个空格，以及该原子的原子质量（<=1000）。没有两行包含相同的原子符号。

第一部分最后仅包括一行字符串“END\_OF\_FIRST\_PART”。

第二部分是一些行的序列。每行是一个分子式，不多于80个字符，而且不包括空格。一个分子最多包括10^5个原子，一些分子中的原子可能没有在原子表中出现。

最后一行仅一个零，表示输入结束。

outputFormat:
输出格式：

输出时一些行的序列，和输入文件的第二部分行数相同。如果分子中的每一个原子都在原子表中出现，输出一个整数，并表示分子质量。否者输出UNKNOWN。不要输出多余的字符。

samples:
H 1
He 4
C 12
O 16
F 19
Ne 20
Cu 64
Cc 333
END_OF_FIRST_PART
H2C
(MgF)2As
Cu(OH)2
H((CO)2F)99
0


title: 圆圆舞蹈

description:
熊大妈的奶牛在时针的带领下，围成了一个圆圈，由于没有严格的教育，奶牛们之间的间隔不一致。

奶牛想知道两只最远的奶牛到底隔了多远。奶牛 $A$ 到 $B$ 的距离为 $A$ 顺时针走和逆时针走，到达 $B$ 的较短路程。告诉你相邻两个奶牛间的距离，请你求出两只最远的奶牛到底隔了多远。

inputFormat:
第一行一个整数 $N$，表示有 $N$ 只奶牛，$2\le N\le 10^5$。

接下 $2\sim N+1$ 行，第 $i$ 行有一个数，表示第 $i-1$ 头奶牛顺时针到第 $i$ 头奶牛的距离 $d_i$，$1\le d_i\le 2^{31}-1$，所有距离之和 $\le 2^{31}-1$。

第 $N+1$ 行的数表示第 $N$ 头奶牛顺时针到第 $1$ 头奶牛的距离。

outputFormat: 一行，表示最大距离。


title: [USACO07FEB] Bronze Lilypad Pond B

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

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

贝西的舞步很像象棋中的马步：每次总是先横向移动 M1 (1 ≤ M1 ≤ 30)格，再纵向移动 M2 (1 ≤ M2 ≤ 30, M1≠M2)格，或先纵向移动 M1 格，再横向移动 M2 格。最多时，贝西会有八个移动方向可供选择。

给定池塘的布局和贝西的跳跃长度，请计算贝西从起点出发，到达目的地的最小步数，我们保证输入数据中的目的地一定是可达的。

inputFormat:
第一行：四个用空格分开的整数：M，N，M1 和 M2

第二行到 M + 1 行：第 i + 1 行有 N 个用空格分开的整数，描述了池塘第

i 行的状态：0 为水，1 为莲花，2 为岩石，3 为贝西所在的起点，4 为贝西想去

的终点。

outputFormat: 第一行：从起点到终点的最少步数。


title: yyy loves Chemistry I

background:
从前，有个人叫 yyy，他特别喜欢化学，尤其是一些很危（zuo）险（si）的实验。

这一天，他开始研究起了一个神奇又有趣的方程式：

$\text{2Na + 2H}_{2}\text{O == 2NaOH + H}_2\uparrow$

description:
现在 yyy 将一块质量为 $x\ \text{g}$ 的钠投入很多（过量）的水中，然后开始收集氢气。

最终，我们知道，这块钠在水中游动着消失了。而 yyy 很厉害，把氢气全收集起来了。

**已知每投入 $\bm{23}$ 克的钠，就会生成 $\bm1$ 克的氢气。**

那么现在 yyy 收集了多少克氢气呢？

**形式化题意：输入一个实数 $\bm x$，输出 $\bm{\frac{x}{23}}$ 的前 $\bm8$ 位小数值，要求四舍五入。**

inputFormat:
一行一个实数 $x$，代表 yyy 将投入了水中的钠的质量（单位：$\text{g}$）。

输入文件行末一定**不会**有一只回车啦。

outputFormat: 一行一个实数（四舍五入精确到 $8$ 位小数），代表生成了多少克氢气。

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

对于 $100\%$ 的数据，满足 $0<x\le1$。

### 提示

你想知道 $x$ 有几位小数吗？才不给你呢>\_<
kkksc：没有数据范围怎么行！输入文件不超过 $5\text M$！
出题人：怎么能这样！差评！我不好挖坑了！

### 警告

**请注意，题目中描述的实验具有很大风险，请勿轻易尝试：活泼金属 $\bold{Na}$ 存在安全隐患、$\bold{NaOH}$ 具有强烈的腐蚀性、$\bold{NaOH}$ 溶解于水时会放出大量热量。**


title: [NOI2014] 魔法森林

background: [hack数据的提交link](https://www.luogu.com.cn/problem/U163126)

description:
为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 $n$ 个节点 $m$ 条边的无向图，节点标号为 $1,2,3,…,n$，边标号为 $1,2,3,…,m$。初始时小 E 同学在 $1$ 号节点，隐士则住在 $n$ 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 $1$ 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 $e_i$ 包含两个权值 $a_i$ 与 $b_i$ 。若身上携带的 A 型守护精灵个数不少于 $a_i$ ，且 B 型守护精灵个数不少于 $b_i$ ，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。

inputFormat: 输入文件的第 $1$ 行包含两个整数 $n,m$，表示无向图共有 $n$ 个节点，$m$ 条边。 接下来 $m$ 行，第 $i+1$ 行包含 $4$ 个正整数 $X_i,Y_i,a_i,b_i$，描述第 $i$ 条无向边。 其中 $X_i$ 与 $Y_i$ 为该边两个端点的标号，$a_i$ 与 $b_i$ 的含义如题所述。 注意数据中可能包含重边与自环。

outputFormat: 输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携 带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出 `-1`。

hint:
\* 解释1

如果小 E 走路径 $1\to 2\to 4$，需要携带 $19+15=34$ 个守护精灵； 如果小 E 走路径 $1\to 3\to 4$，需要携带 $17+17=34$ 个守护精灵； 如果小 E 走路径 $1\to 2\to 3\to 4$，需要携带 $19+17=36$ 个守护精灵； 如果小 E 走路径  $1\to 3\to 2\to 4$，需要携带 $17+15=32$ 个守护精灵。 综上所述，小 E 最少需要携带 $32$ 个守护精灵。

\* 解释2

小 E 无法从 $1$ 号节点到达 $3$ 号节点，故输出 `-1`。

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


title: yyy loves Maths II

background: 上次蒟蒻 redbag 可把 yyy 气坏了，yyy 说他只是小学生，蒟蒻 redbag 这次不坑他了。

description:
redbag 给了 yyy 很多个数，要 yyy 计算这些数的和。

必须要快，redbag 只给了 yyy $1$ 秒的时间！！！

inputFormat: 一行，很多个数。

outputFormat: 一行，一个实数(四舍五入精确到 $5$ 位小数)，表示这些数的和。

hint: 对于 $100\%$ 的数据，所有数 $ \le 233,333,333 $，保证在小数点后最多有 $6$ 位数，最多共有 $5\times 10^4$ 个数。


title: 阶乘之乘

background: 不告诉你……

description: 求出 $1!\times 2!\times 3!\times 4!\times \cdots \times n!$ 的末尾有几个零。

inputFormat: 一行，一个整数 $n(n\le 10^8)$。

outputFormat: 输出答案，表示零的个数。


title: 电脑班的裁员

background: 隔壁的新初一电脑班刚考过一场试，又到了BlingBling的裁员时间，老师把这项工作交给了ZZY来进行。而ZZY最近忙着刷题，就把这重要的任务交（tui）给了你。

description: ZZY有独特的裁员技巧：每个同学都有一个考试得分ai（-1000<=ai<=1000），在n个同学（n<=500）中选出不大于k段（k<=n）相邻的同学留下，裁掉未被选中的同学，使剩下同学的得分和最大。要特别注意的是，这次考试答错要扣分【不要问我为什么】，所以得分有可能为负。

inputFormat: 第一行为n，k，第二行为第1~n位同学的得分。

outputFormat: 一个数s，为最大得分和。

hint: 2014彭鲲志：“题目这么短一看就很水。”


title: [TJOI2017] 不勤劳的图书管理员

description:
加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。

他的任务是把书排成有序的，所以无序的书让他产生厌烦。

两本乱序的书会让小豆产生这两本书页数的和的厌烦度。

现在有 $n$ 本被打乱顺序的书，在接下来 $m$ 天中每天都会因为读者的阅览导致书籍顺序改变位置。

因为小豆被要求在接下来的 $m$ 天中至少要整理一次图书。

小豆想知道，如果他前 $i$ 天不去整理，第 $i$ 天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。

inputFormat:
第一行会有两个数，$n,m$ 分别表示有 $n$ 本书，$m$ 天。

接下来 $n$ 行，每行两个数，$a_i,v_i$，分别表示第 $i$ 本书本来应该放在 $a_i$ 的位置，这本书有 $v_i$ 页，保证不会有放置同一个位置的书。

接下来 $m$ 行，每行两个数，$x_j$ 和 $y_j$，表示在第 $j$ 天的第 $x_j$ 本书会和第 $y_j$ 本书会因为读者阅读交换位置。

outputFormat: 一共 $m$ 行，每行一个数，第 $i$ 行表示前 $i$ 天不去整理，第 $i$ 天小豆的厌烦度，因为这个数可能很大，所以将结果模 $10^9 +7$ 后输出。


title: 地标访问

background: 改编自 USACO2007Nov 铜组 Exploration

description: 贝西在一条道路上旅行，道路上有许多地标，贝西想要在日落之前访问尽可能多的路标。将道路视为一条数轴，贝西从原点出发，道路上有 $n(1 \le n \le 5\times 10^4)$ 个地标，每个地标有一个坐标 $x_i(|x_i| \le 10^5)$ 且地标的坐标各不相同，$t(1 \le T \le 10^9)$ 分钟之后将会日落。

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

第二行至第 $n+1$ 行：地标的坐标 $x_i$。

outputFormat: 一个整数，贝西能访问的最多的地标数

hint:
1、贝西日落时不用回到原点。

2、与原模拟水题不同。

3、数据较原题有所修改


title: [TJOI2017] 龙舟

description:
加里敦大学有一个龙舟队，龙舟队有 $n$ 支队伍，每只队伍有 $m$ 个划手。龙舟比赛是一个集体项目，和每个人的能力息息相关，但由于龙舟讲究配合，所以评价队伍的能力的是一个值 $C=\frac{b_1 \times b_2 \times \cdots \times b_m}{a_1 \times a_2 \times \cdots \times a_m}$，其中 $b_i$ 表示第 $i$ 个位置的标准能力值，$a_i$ 表示在队伍中第 $i$ 个位置的划手的能力值。最后通过约分，我们会得到 $C=\frac{B}{A}$，其中 $\gcd(B,A)=1$，即 $A,B$ 互质。

但是由于比赛现场的情况不一样，我们认为在现场压力为 $M$ 的情况下，队伍最后的表现情况是 $C^{-1}\mod M$。我们规定在模 $M$ 的条件下 $\frac{1}{x}=y$，其中 $y$ 满足 $xy \equiv 1\pmod M$，并且 $y$ 大于等于 $0$ 小于 $M$。如果不存在这样的 $y$ 我们就认为在压力为 $M$ 的条件下这支队伍会发挥失常（即 $y$ 是 $x$ 在模 $M$ 意义下的逆元，如果不存在逆元我们认为队伍发挥失常）。给出这个赛季的比赛安排情况，现在教练组想知道各队在比赛中的表现情况。

inputFormat:
第一行输入三个整数 $n,m,k$，表示有 $n$ 支队伍，每支队伍由 $m$ 个人组成，有 $k$ 场比赛。

第二行输入 $m$ 个整数，第 $i$ 个整数表示第 $i$ 个位置的标准能力值为 $b_i$。

第三行到第 $n+2$ 行，共 $n$ 行，每行有 $m$ 个数，第 $2+i$ 行第 $j$ 个数表示第 $i$ 支队伍第 $j$ 个位置划手的能力值。

第 $n+3$ 行到第 $n+k+2$ 行，共 $k$ 行，每行有两个数 $x,M$，分别表示第 $x$ 支队伍会在压力为 $M$ 的比赛中出战。

outputFormat: 共 $k$ 行，第 $i$ 行表示在第 $i$ 个参赛安排中队伍的现场表现情况 $C$，如果出现队伍发挥失常，输出 `-1`。


title: 白雪皑皑

background: “柴门闻犬吠，风雪夜归人”，冬天，不期而至。千里冰封，万里雪飘。空中刮起了鸭毛大雪。雪花纷纷，降落人间。 美能量星球（pty 在 spore 上的一个殖民地）上的人们被这美景所震撼。但是 pty 却不高兴，他不喜欢白色的世界，他觉得这样太单调了。所以他想对雪花进行染色，让世界变得多彩些。

description: 现在有 $n$ 片雪花排成一列。 pty 要对雪花进行 $m$ 次染色操作，第 $i$ 次染色操作中，把第 $((i\times p+q)\bmod n)+1$ 片雪花和第 $((i\times q+p)\bmod n)+1$ 片雪花之间的雪花（包括端点）染成颜色 $i$。其中 $p,q$ 是给定的两个正整数。他想知道最后 $n$ 片雪花被染成了什么颜色。没有被染色输出 $0$。

inputFormat: 输入共四行，每行一个整数，分别为 $n,m,p,q$，意义如题中所述。

outputFormat: 输出共 $n$ 行，每行一个整数，第 $i$ 行表示第 $i$ 片雪花的颜色。

hint:
- 对于 $20\%$ 的数据满足：$n,m\leq 1000$。
- 对于 $40\%$ 的数据满足：$n\leq 8000$，$m\leq 10^6$。
- 对于 $80\%$ 的数据满足：$n\leq 5\times 10^5$，$m\leq 10^7$。
- 对于 $100\%$ 的数据满足：$1\leq n\leq 10^6$，$1\leq m\leq 10^7$。

保证 $1\leq m\times p+q,m\times q+p\leq 2\times 10^9$。


title: kkksc03考前临时抱佛脚

background: kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

description:
这次期末考试，kkksc03 需要考 $4$ 科。因此要开始刷习题集，每科都有一个习题集，分别有 $s_1,s_2,s_3,s_4$ 道题目，完成每道题目需要一些时间，可能不等（$A_1,A_2,\ldots,A_{s_1}$，$B_1,B_2,\ldots,B_{s_2}$，$C_1,C_2,\ldots,C_{s_3}$，$D_1,D_2,\ldots,D_{s_4}$）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 $2$ 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

inputFormat:
本题包含 $5$ 行数据：第 $1$ 行，为四个正整数 $s_1,s_2,s_3,s_4$。

第 $2$ 行，为 $A_1,A_2,\ldots,A_{s_1}$ 共 $s_1$ 个数，表示第一科习题集每道题目所消耗的时间。

第 $3$ 行，为 $B_1,B_2,\ldots,B_{s_2}$ 共 $s_2$ 个数。

第 $4$ 行，为 $C_1,C_2,\ldots,C_{s_3}$ 共 $s_3$ 个数。

第 $5$ 行，为 $D_1,D_2,\ldots,D_{s_4}$ 共 $s_4$ 个数，意思均同上。

outputFormat: 输出一行,为复习完毕最短时间。


title: 覆盖

background: WSR 的学校有 $B$ 个男生和 $G$ 个女生都来到一个巨大的操场上扫地。

description:
操场可以看成是 $N$ 行 $M$ 列的方格矩阵，如下图 (1) 是一个 $4$ 行 $5$ 列的方格矩阵。每个男生负责打扫一些连续的行，每个女生负责打扫一些连续的列。比如有两个男生，第一个男生负责第 $1, 2$ 两行、第二个男生负责第 $4$ 行，如图 (2) 的蓝色。打扫的区域可能重复，比如，又有两个女生，第一个女生负责打扫第 $3, 4$ 两列，第二个女生负责打扫第 $4, 5$ 两列，如图 (3) 的红色。从图 (3) 可以容易看出，有颜色覆盖的方格数为 $18$，即这 $4$ 名学生总共打扫了 $18$ 个方格。

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

老师要 WSR 在学校给出打扫安排的数据后快速计算出这些学生总共打扫了多少方格。

inputFormat:
第一行 $4$ 个正整数：$N, M, B, G$。其中 $N$ 表示方阵行数，$M$ 表示方阵列数，$B$ 表示男生数，$G$ 表示女生数。

接下来 $B$ 行，每行两个整数 $x, y$。表示相应某个男生负责打扫从第 $x$ 行到第 $y$ 行（共 $y - x + 1$ 行），保证 $1 \le x \le y \le N$。

再接下来 $G$ 行，每行两个整数 $x, y$。表示相应某个女生负责打扫从第 $x$ 列到第 $y$ 列（共 $y - x + 1$ 列），保证 $1 \le x \le y \le M$。

outputFormat: 一个整数，表示所打扫的面积。（即格子的总数）

hint:
不会可以自己画图。

### 数据范围与约定

对于 $80\%$ 的数据，$1 \le N,M,B,G \le 10^2$。

对于 $100\%$ 的数据，$ 1 \le N,M,B,G \le 5 \times 10^3$。