title: [TJOI2013] 数字根

description:
一个数字的数字根定义为:这个数字每一位的数字加起来求和,反复这个过程直到和小于10。例如,64357的数字跟为7,因为6+4+3+5+7=25,2+5=7个区间的数字根定义为这个区间所有数字和的数字根。

给定一个序列A1,A2,A3,…,An,你需要回答一些询问。每一个询问给定个区间[L,R],求出这个区间所有连续子区间里最大的前5个不同的数字根，不够5个的用-1补全

inputFormat: 第一行一个整数N,表示序列的长度。第二行是N个整数Ai(0≤Ai<10^9)。第三行是一个整数Q表示询问次数。接下来Q行,每一行两个正整数1,r,表示询问区间。(1≤l≤r≤N)

outputFormat: Q行,表示每一个查询区间所有连续子区间里最大的前5个不同的数字根,按降序输出,输出用空格隔开。


title: [TJOI2013] 奖学金

type: P

background: 小张最近发表了一篇论文，有一个神秘人物要给小张学院发奖学金。

description:
小张学院有 $c$ 名学生，第 $i$ 名学生的成绩为 $a_i$，要获得的奖学金金额为 $b_i$。
要从这 $c$ 名学生中挑出 $n$ 名学生发奖学金。这个神秘人物爱好奇特，他希望得到奖学金的同学的**成绩**的**中位数**尽可能大，但同时，他们的**奖学金总额**不能超过 $f$。

inputFormat:
第一行有三个整数，分别表示要挑出的学生人数 $n$，学生总人数 $c$ 和奖学金总额的最大值 $f$，**保证 $n$ 为奇数**。

第 $2$ 到第 $(c + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数依次表示第 $i$ 名学生的成绩 $a_i$ 和如果要给他发奖学金，则需要发的金额数 $b_i$。

outputFormat: 输出一行一个整数表示答案。如果无法满足神秘人的条件，请输出 $-1$。

hint:
### 样例 1 解释

选择成绩为 $5$，$35$，$50$ 的三名同学，奖金总额为 $18 + 30 + 21 = 69$。

### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n \leq 10^3$，$c \leq 2 \times 10^3$。
- 对于 $100\%$ 的数据，保证 $3 \leq n  \leq 10^5$，$n \leq c \leq 2 \times 10^5$，$0 \leq f \leq 2\times 10^9$，$0 \leq a_i \leq 2 \times 10^9$，$0 \leq b_i \leq 10^5$。


title: [TJOI2014] 匹配

description:
有 $N$ 个单身的男孩和 $N$ 个单身女孩，男孩 $i$ 和女孩 $j$ 在一起得到的幸福值为 $H_{i,j}$。

一个匹配即对这 $N$ 个男孩女孩的安排：每个男孩恰好有一个女朋友，每个女孩恰好有一个男朋友。

一个匹配的幸福值即这 $N$ 对男女朋友的幸福值的和。

经典的问题是计算幸福值最大的匹配，即完美匹配。然而完美匹配有时候并不唯一，你需要计算对于所有的完美匹配，其交集是什么。

inputFormat:
输入的第一行是一个正整数 $N$ 。

接下来是一个 $N\times N$ 大小的矩阵 $H$，$H_{i,j}$ 表示男孩 $i$ 和女孩 $j$ 在一起的幸福值。

outputFormat: 第一行输出完美匹配的幸福值，接下来是若干行，每一行是一对整数 $i$ 和 $j$，表示男孩 $i$ 和女孩 $j$ 在所有完美匹配的交集中，以 $i$ 的递增顺序输出。


title: [TJOI2014] 电源插排

description:
小 M 的实验室有很多电源插排。这些插排的编号从 $1$ 到 $n$，由左向右排成一排。

每天早晨，这些插排都是没有被使用的。每当一个学生来到实验室，他就将自己的笔记本电源插到某一个未被使用的插排上。

实验室的同学们都很奇怪，他们完成这个过程是这样的：首先，他们找到还没有被使用的插排的最长区间。

如果有多个区间长度相同，他们就选择最靠右的那个。然后将自己的电源插到该区间的中间。

如果区间长度是偶数，他们同样选择靠右的那个。当一个同学离开实验室时,他会将自己的电源拔出来。

数据保证每一个同学来到实验室时，至少有一个空的插排。

需要计算在区间 $[l,r]$ 已经有多少个插排被使用了。

inputFormat:
第一行是两个整数 $n$ 和 $q$，表示插排数量和询问数量。

接下来 $q$ 行，每一行以一个整数 $k$ 开头。

> 如果 $k$ 为 $0$，接下来就是两个整数 $l$ 和 $r$，表示一个询问。
>
> 否则 $k$ 表示表示编号为 $k$ 的学生到来或离开。$k$ 的奇数次出现表示到来，偶数次出现表示离开。每个学生的编号都是唯一的。

outputFormat: 对于每一个询问，输出一个整数，表示询问区间内有多少个插排已经被使用。


title: [TJOI2014] 拼图

description:
小Z最近迷上了拼图游戏,然而智商有限,他总是无法拼出完整图案。游戏是这样的：首先小Z会得到一些拼图碎片,然后他试着重新排列这些碎片使得它们组成一个大小为4\*4的正方形。如下图。注意小Z不能旋转或者翻转这些碎片。

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

小Z得到如图1的碎片,然后经过重新排列得到图2的正方形。

由于小Z实在太笨了,聪明的你请写一个程序帮助他来解决这个问题吧。

inputFormat:
输入包含多组数据,请使用EOF

每组数据的的第一行包含一个正整数N，表示碎片的个数。接下来输入N个碎片。每个碎片的第一行是两个正整数r和c,表示这个碎片的行数和列数。接下来是r行,每一行包含c个字符'0'或'1'，'1'表示碎片占据这个位置,'0'表示该位置为空。数据保证每个碎片都是完整的一片(即'1'是相互连通的),并且没有行或者列全部为'0'。

outputFormat: 如果无法组成一个正方形,输出”No solution”;如果有多组解,输出”Yes, many!”。否则,输出”Yes, only one!”,接下来输出一个4\*4的矩阵H,Hij表示位置i,j的碎片编号。碎片编号从1开始。

samples:
Yes, only one!
1112
1412
3422
3442
Yes, many!
No solution

hint:
### 数据范围

对于 30% 的数据，N < 5

对于 100% 的数据，N ≤ 16


title: [TJOI2015] 线性代数

description:
为了提高智商，ZJY 开始学习线性代数。

她的小伙伴菠萝给她出了这样一个问题：给定一个 $n \times n$ 的矩阵 $B$ 和一个 $1 \times n$ 的矩阵 $C$。求出一个 $1×n$ 的 01 矩阵 $A$，使得 $D=(A×B-C)×A^{\sf T}$ 最大，其中$A^{\sf T}$为$A$的转置，输出$D$。

inputFormat: 第一行输入一个整数 $n$。接下来 $n$ 行输入 $B$ 矩阵，第 $i$ 行第 $j$ 个数代表 $B$ 接下来一行输入 $n$ 个整数，代表矩阵 $C$。矩阵 $B$ 和矩阵 $C$ 中每个数字都是不过 $1000$ 的非负整数。

outputFormat: 输出一个整数，表示最大的 $D$。

hint:
- 对于 $30\%$ 的数据，$n \leq 15$；
- 对于 $100\%$ 的数据，$1 \leq n \leq 500$；
- 另外还有两组不计分的 hack 数据，放在 subtask 2 中，数据范围与上面一致。


title: [TJOI2015] 组合数学

description:
为了提高智商，ZJY 开始学习组合数学。某一天她解决了这样一个问题：给一个网格图，其中某些格子有财宝。每次从左上角出发，只能往右或下走。问至少要走几次才可能把财宝全捡完。

但是她还不知足，想到了这个问题的一个变形：假设每个格子中有好多块财宝，而每一次经过一个格子至多只能捡走一块财宝，其他条件不变，至少要走几次才可能把财宝全捡完？

这次她不会做了，你能帮帮她吗？

inputFormat:
第一行为一个正整数 $t$，表示数据组数。

每组数据的第一行是两个正整数 $n$ 和 $m$，表示这个网格图有 $n$ 行 $m$ 列。

接下来 $n$ 行，每行 $m$ 个非负整数，表示这个格子中的财宝数量（$0$ 表示没有财宝）。

outputFormat: 对于每组数据，输出一个整数，表示至少走的次数。

hint:
### 数据范围

对于 $30\%$ 的数据，$n \le 5$，$m \le 5$，每个格子中的财宝数不超过 $5$ 块。

对于 $50\%$ 的数据，$n \le 100$，$m \le 100$，每个格子中的财宝数不超过 $1000$ 块。

对于 $100\%$ 的数据，$1\le t\le 2$，$1\le n \le 1000$，$1\le m \le 1000$，每个格子中的财宝不超过 $10^6$ 块。


title: [TJOI2014] 上升子序列

description:
给定一个只包含整数的序列(序列元素的绝对值大小不超过10^9),你需要计算上升子序列的个数,满足如下条件的称之为一个上升子序列:

1. 是原序列的一个子序列

2. 长度至少为2

3. 所有元素都严格递增

如果两个上升子序列相同,那么只需要计算一次。例如:序列{1,2,3,3}有4个上升子序列,分别为{1,2}{1,3},{1,2,3},{2,3}

inputFormat: 输入的第一行是一个整数n,表示序列长度。接下来一行是n个整数,表示序列。

outputFormat: 输出仅包含一行,即原序列有多少个上升子序列。由于答案可能非常大,你只需要输出答案模10^9+7的余数。

hint:
### 数据范围

对于 30% 的数据，N ≤ 5000

对于 100% 的数据，N ≤ 10^5


title: [TJOI2014] Alice and Bob

description: Alice 和 Bob 发明了一个新的游戏。给定一个序列 $\{x_0,x_1,\cdots,x_{n-1}\}$，Alice 得到一个序列 $\{a_0,a_1,\cdots,a_{n-1}\}$，其中 $a_i$ 表示以 $x_i$ 结尾的最长上升子序列的长度；Bob 得到一个序列$\{b_0,b_1,\cdots,b_{n-1}\}$，其中 $b_i$ 表示以 $x_i$ 开头的最长下降子序列的长度。Alice 的得分是序列 $\{a_i\}$ 的和，Bob的得分是序列 $\{b_i\}$ 的和。

inputFormat: 输入的第一行是 $n$，第二行是序列 $\{a_0,a_1,\cdots,a_{n-1}\}$。数据保证序列 $\{a_i\}$ 可以由至少一个 $1$ 到 $n$ 的排列得到。

outputFormat: 输出包含一行,表示在序列 $\{a_i\}$ 给定的情况下 Bob 能得到的最高分数。


title: [TJOI2015] 弦论

description: 为了提高智商，ZJY 开始学习弦论。这一天，她在《String theory》中看到了这样一道问题：对于一个给定的长度为 $n$ 的字符串，求出它的第 $k$ 小子串是什么。你能帮帮她吗?

inputFormat:
第一行是一个仅由小写英文字母构成的字符串 $s$。

第二行为两个整数 $t$ 和 $k$，$t$ 为 $0$ 则表示不同位置的相同子串算作一个，$t$ 为 $1$ 则表示不同位置的相同子串算作多个。$k$ 的意义见题目描述。

outputFormat: 输出数据仅有一行,该行有一个字符串，为第 $k$ 小的子串。若子串数目不足 $k$ 个，则输出 $-1$。


title: [TJOI2014] 电影评分

description: 小Z发明了一套新的电影评分系统。这套系统有三种操作:发布新电影、对电影评分、以及询问电影评分的排名。具体是这样运作的:如果是发布新电影,并且这部电影的有所主演之前均没有出现过,那么这部新电影的评分为0,否则这部电影的评分为**最近一部**与该电影**至少有一个共同主演**的电影的评分;如果是对电影进行评分,那么这部电影的评分就变成之前评分与新的评分的平均数;如果是查询排名,则根据评分输出相应排名。评分最高的为第一名。如果有多部电影分数相同,那么输出最早的一部。电影的评分在0到5之间。

inputFormat:
输入的第一行是n,表示操作次数。接下来n行,每一行是以下三种操作之一：

1. Q x:查询当前排名为x的电影ID

2. R ID x actor1 actor2 …· actorx:发布新电影ID,该电影有x个主演分别为 actor1, actor2,…’

3. C ID score:评分操作,表示对电影ID的评分为 score

数据保证每个电影的ID不相同,且每部电影至多不超过5名主演。

1≤ actor1, actor2,··≤10^5

1≤ID≤10^5

outputFormat: 对于每一个查询操作,输出相应排名的电影的ID。


title: [TJOI2015] 旅游

description:
为了提高智商，ZJY 准备去往一个新世界去旅游。这个世界的城市布局像一棵树，每两座城市之间只有一条路径可以互达。

每座城市都有一种宝石,有一定的价格。ZJY 为了赚取最高利益,她会选择从 A 城市买入再转手卖到 B 城市。

由于ZJY买宝石时经常卖萌，因而凡是 ZJY 路过的城市，这座城市的宝石价格会上涨。让我们来算算 ZJY 旅游完之后能够赚取的最大利润。(如 A 城市宝石价格为 $v$，则ZJY出售价格也为 $v$)

inputFormat:
第一行输入一个正整数 $n$ 表示城市个数

接下来一行输入 $n$ 个正整数表示每座城市宝石的最初价格 $p$,每个宝石的初始价格不超过 $100$。

第三行开始连续输入 $n-1$ 行,每行有两个数字 $x$ 和 $y$。表示 $x$ 城市和 $y$ 城市有一条路径。城市编号从$1$开始。

下一行输入一个正整数 $q$ 表示询问次数。

接下来 $q$ 行每行输入三个正整数 $a,b,v$，表示 ZJY 从 $a$ 旅游到 $b$，城市宝石上涨 $v$。

outputFormat: 对于每次询问，输出 ZJY 可能获得的最大利润，如果亏本了则输出 $0$。

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

- 对于 $30\%$ 的数据，保证 $n \le 100$，$q \le 10^4$。
- 对于 $100\%$ 的数据，保证 $1\le n,q \le 5\times 10^4$，在任何时刻任何城市的宝石价格都不超过 $10^9$。


title: [TJOI2015] 棋盘

description:
为了提高智商，ZJY 去新世界旅游了。可是旅游过后的 ZJY 杯具地发现要打开通往原来世界的门，必须要解开门上面画的谜题。谜题是这样的：

有个 $n$ 行 $m$ 列的棋盘，棋盘上可以放许多特殊的棋子。每个棋子的攻击范围是 $3$ 行 $p$ 列。输入数据用一个 $3\times p$ 的矩阵给出了棋子攻击范围的模板，棋子被默认为模板中的第 $1$ 行，第 $k$ 列，则棋子能攻击到的位置是 $1$，不能攻击到的位置是 $0$。输入数据保证第 $1$ 行第 $k$ 列的位置是 $1$。打开门的密码就是，在要求棋子互相不能攻击到的前提下，摆放棋子的方案数。注意什么棋子都不摆放也算作一种可行方案。由于方案数可能很大,而密码为 $32$ 位的二进制密码,所以 ZJY 仅需要知道方案数对 $2^{32}$ 次方取余数的结果即可。

注意：编号从 $0$ 开始，即第 $1$ 行指的是中间那行。

inputFormat:
输入数据的第一行为两个整数 $n$ 和 $m$，表示棋盘的大小。

第二行为两个整数 $p$ 和 $k$，表示接下来的攻击范围模板的大小，以及棋子在模板中的位置。

接下来三行,每行有 $p$ 个数,表示攻击范围的模版。每个数字后有一个空格。

outputFormat: 输出数据仅有一行，一个整数，表示可行的方案数模 $2^{32}$ 的余数。

hint:
### 数据范围

对于 $10\%$ 的数据，$1 \leq n \leq 5$，$1 \leq m \leq5$。

对于 $50\%$ 的数据，$1 \leq n \leq 1000$，$1 \leq m \leq 6$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^{6}$，$1 \leq m \leq 6$。


title: [TJOI2015] 概率论

description:
为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 $n$ 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？

判断两棵树是否同构的伪代码如下：

$$
\def\arraystretch{1.2}
    \begin{array}{ll}
    \hline
    \textbf{算法 1}&\text{Check}(T1,T2) \\
    \hline
    1&\textbf{Require: }\text{ 两棵树的节点}T1,T2\\
    2&\qquad\textbf{if}\ \ T1=\text{null}\textbf{ or }T2=\text{null}\textbf{ then }\\
    3&\qquad\qquad\textbf{return}\ \ T1=\text{null}\textbf{ and }T2=\text{null}\\
    4&\qquad\textbf{else}\\
    5&\qquad\qquad\textbf{return}\ \text{Check}(T1\to\mathit{leftson},T2\to\mathit{leftson}) \\
    & \qquad\qquad\qquad \textbf{ and }\text{Check}(T1\to\mathit{rightson},T2\to\mathit{rightson})\\
    6&\qquad\textbf{endif}\\
    \hline
    \end{array}
    $$

inputFormat: 输入一个正整数 $n$，表示有根树的结点数。

outputFormat: 输出这棵树期望的叶子节点数，要求误差小于 $10^{-9}$。


title: MloVtry的idea

background: 点击～

description:
MloVtry是一个脑洞很大的人，它总会想出一些奇奇怪怪的idea。

可问题是，MloVtry作为一个蒟蒻，很多时候都没办法解决自己提出的问题，所以MloVtry想出一套题的梦想一直被搁置。

不过好在MloVtry有一些神犇朋友，他们强的没边，所以MloVtry一有机会就会向这些dalao们请教。

现在MloVtry有n个idea，这n个idea在MloVtry二维的大脑里排成一列，每一个idea都有一个难度值，用a[i]表示，当然难度值越大越困难。

MloVtry准备与q个神犇进行交♂易，但是MloVtry不想问一些过于简单的idea来降自己的B格，又不好意思用太难的、无法解决的idea来伤害自己与神犇之间的感情，所以它每次都会挑idea序列中的第k简单的idea来向神犇询问（也就是难度值第k小的那个idea）。

MloVtry的脑子有坑，但是没关系，这个坑会反而会帮助MloVtry思考，不过这样数列的a[i]就会更新，具体的，设坑在第j个idea上，那么a[i]=a[i]-zz(i<=j);a[i]=i+a[i]-j(i>j)。

如果仅仅如此MloVtry也不会感到迷茫，但关键的是这个坑还会不定时的跳跃，这就让MloVtry手足无措了---它不知道这个时候要问哪个问题了。

现在MloVtry会给出你---它最好的朋友一些询问---一些二元组（at，k），表示脑洞位于at，且它想询问第k简单的idea，请你告诉MloVtry这个idea难度是多少。

inputFormat:
第一行三个整数n,q,zz，含义见题面

第二行n个整数a[1],a[2].....a[n]

随后q行，每行两个整数表示at与k

特别的，MloVtry是一个三维生物，所以它无法想象有人可以在时间轴上翻滚，所以at与k与上一个询问的答案的绝对值的异或值并对n取膜后再+1的值为本次的at和k。

（也就是设lastans为上次询问答案，每一次at=(at^abs(lastans))%n+1,k=(k^abs(lastans))%n+1,并将lastans更新，初始lastans=0）

outputFormat: q行q个整数，表示对每个询问的回答

hint:
各个值保证在int范围内。

对于100%的数据，n,q<=6w。

对于40%的数据，n,q<=1000。

PS.可能有重复，例如

1 1 1 1 1 0

此时第1大、第2大....第5大的值都是1，第6大的值是0


title: 多边形染色

background:
Flokirie有一个美丽的凸n边形，顶点编号为1~n，每条边长都不相等。

他想把每个顶点都染成1~c中某一颜色，且相邻顶点颜色不能相同。

description:
他想知道所有可行方案共有多少。于是他在纸上算了算，5分钟就解决了这题。

于是他觉得太low了，便定义了以下骚操作。

① 1 x p：表示第x个顶点必须染颜色p。

② 2 x p：表示第x个顶点必须不染颜色p。

③ 3 x y：表示更改第x个顶点与第y个顶点之间边的属性（保证y=x±1，且x,y≠1,n），第x个顶点必须与第y个顶点颜色相同。

现在，他想知道所有可行的方案共有多少种。由于结果可能过大，你只需输出它对987654321取模的结果即可。

inputFormat:
第一行，三个正整数n，m，c，表示多边形边数、操作个数、颜色个数。

第2~(m+1)行，每行三个正整数表示一个操作，具体意义见题目描述。

outputFormat: 一行一个整数，为所有可行操作和模上987654321的结果。


title: Roy&October之取石子

background: Roy 和 October 两人在玩一个取石子的游戏。

description:
游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取 $p^k$ 个（ $p$ 为质数，$k$ 为自然数，且 $p^k$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。

现在 October 先取，问她有没有必胜策略。

若她有必胜策略，输出一行 `October wins!`；否则输出一行 `Roy wins!`。

inputFormat:
第一行一个正整数 $T$，表示测试点组数。

第 $2$ 行$\sim$ 第 $T+1$ 行，一行一个正整数 $n$，表示石子个数。

outputFormat: $T$ 行，每行分别为 `October wins!` 或 `Roy wins!`。

samples:
October wins!
October wins!
October wins!

hint:
对于 $30\%$ 的数据，$1\leq n\leq 30$；

对于 $60\%$ 的数据，$1\leq n\leq 10^6$；

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^7$, $1\leq T\leq 10^5$。

（改编题）


title: 遥远的国度

description:
`zcwwzdjn` 在追杀 `zhx` ，而 `zhx` 逃入了一个遥远的国度。当 `zcwwzdjn` 准备进入遥远的国度继续追杀时，守护神 `RapiD` 阻拦了 `zcwwzdjn` 的去路，他需要 `zcwwzdjn` 完成任务后才能进入遥远的国度继续追杀。

问题是这样的：遥远的国度有 $n$ 个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，第 $i$ 个的防御值为 $val_i$，有些时候 `RapiD` 会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。

`RapiD` 想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。

由于 `RapiD` 无法解决这个问题，所以他拦住了 `zcwwzdjn` 希望他能帮忙。但 `zcwwzdjn` 还要追杀 `zhx`，所以这个重大的问题就被转交到了你的手上。

inputFormat:
第 $1$ 行两个整数 $n\ m$，代表城市个数和操作数。

第 $2$ 行至第 $n$ 行，每行两个整数 $u\ v$，代表城市 $u$ 和城市 $v$ 之间有一条路。

第 $n+1$ 行，有 $n$ 个整数，第 $i$ 个代表第 $i$ 个点的初始防御值 $val_i$。

第 $n+2$ 行一个整数 $id$，代表初始的首都为 $id$。

第 $n+3$ 行至第 $n+m+2$ 行，首先有一个整数 $opt$。

如果 $opt=1$，接下来有一个整数 $id$，代表把首都修改为 $id$；

如果 $opt=2$，接下来有三个整数 $x\ y\ v$，代表将 $x\ y$ 路径上的所有城市的防御值修改为 $v$；

如果 $opt=3$，接下来有一个整数 $id$，代表询问以城市 $id$ 为根的子树中的最小防御值。

outputFormat: 对于每个 $opt=3$ 的操作，输出一行代表对应子树的最小点权值。


title: MloVtry的咸鱼树

background: 签到~

description:
俗话说种瓜得瓜，种豆得豆，MloVtry 把自己砍掉一半埋进了土里，于是它得到了一颗 $n$ 个点的咸鱼树。

但是问题是由于 MloVtry 只舍得埋下一半的自己，所以这个咸鱼树是不完整的---甚至它碎裂成了 $m$ 条边。

作为一条能够致癌的咸鱼，MloVtry 当然想要一颗咸鱼树来标榜自己的身份。

MloVtry 大概估计出了连接两个点之间的代价，它想知道，最少需要多少代价才能拼出咸鱼树？

值得注意的是，咸鱼树上的咸鱼边们对于 MloVtry 是很有意见的，所以每条边都会制定一个点集 $S$，只有 MloVtry 将 $S$ 这个特殊点集里的所有点都接入某个集合 $T$ 之后，这条边才可以被加入 $T$ 这个集合。

MloVtry 把脑子埋进了地里，所以这个问题只能由你来解决了。

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

接下来 $m$ 行，每行 $4$ 个整数 $u,v,S,l$，表示一条连接 $u$ 到 $v$ 的长为 $l$ 的双向边，要在已经选择了点集 $S$（这个集合用二进制数来表示，$1$ 号点对应第 $1$ 位，其余点同理）之后才能选择。

outputFormat: 一行 $1$ 个整数，表示最小代价。当然，可能存在无解的情况，此时请输出 $-1$。

hint:
$1\le n\le 15$，$1\le m\le n\times (n+10)$。

数据保证所有数值在 int 范围内。


title: [NOI2008] 志愿者招募

description: 申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要 $n$ 天才能完成，其中第 $i$ 天至少需要 $a_i$ 个人。布布通过了解得知，一共有 $m$ 类志愿者可以招募。其中第 $i$ 类可以从第 $s_i$ 天工作到第 $t_i$ 天，招募费用是每人 $c_i$ 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

inputFormat: 第一行包含两个整数 $n,m$，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含 $n$ 个非负整数，表示每天至少需要的志愿者人数。 接下来的 $m$ 行中每行包含三个整数 $s_i, t_i, c_i$，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。保证存在可行的招募方案。

outputFormat: 仅包含一个整数，表示你所设计的最优方案的总费用。

hint: $1\leq n\leq 1000$，$1\leq m\leq 10000$，题目中其他所涉及的数据均不超过 $2^{31}-1$。


title: 我永远喜欢珂朵莉~

background:
http://sukasuka-anime.com/

戒不掉的珂毒

出不动的分块

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

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

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

哦对了有没有想买BD的珂学家啊？支持一下墨鱼吧~

或者有没有人想来手办众筹啊？

description:
给珂朵莉一个长为 $n$ 的非负数序列 $a$，支持以下两个操作：

- $\verb!1 l r x!$：把区间 $[l,r]$ 中所有 $x$ 的倍数除以 $x$。
- $\verb!2 l r!$：查询区间 $[l,r]$ 内元素的和。

珂朵莉很可爱，所以你要帮珂朵莉写这个题。

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

第二行 $n$ 个非负整数表示 $a_i$。

之后 $m$ 行每行一个操作：

- $\verb!1 l r x!$：把区间 $[l,r]$ 中所有 $x$ 的倍数除以 $x$。
- $\verb!2 l r!$：查询区间 $[l,r]$ 内元素的和。

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

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

$1 \le n , m \le 10^5$，$0 \le a_i \le 5\times 10^5$，$1 \le x \le 5\times 10^5$。


title: 最大食物链计数

background: 你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

description:
给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是**生物学意义上的食物链**，即**最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者**。）

Delia 非常急，所以你只有 $1$ 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

inputFormat:
第一行，两个正整数 $n、m$，表示生物种类 $n$ 和吃与被吃的关系数 $m$。

接下来 $m$ 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

outputFormat: 一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

hint:
各测试点满足以下约定：

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

【补充说明】

数据中不会出现环，满足生物学的要求。（感谢 @AKEE ）


title: 不开心的金明

description:
金明今天很不开心，家里购置的二手房就要领钥匙了，房里并没有一间他自己专用的很宽敞的房间。更让他不高兴的是，妈妈昨天对他说：“你需要购买哪些物品，怎么布置，你说了不算（有很大的限制），而且不超过 $W$ 元钱。”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $W$ 元。于是，他把每件物品规定了一个重要度整数 $p_i$ 表示。他还从因特网上查到了每件物品的价格 $v_i$（都是整数元）。

妈妈看到购物单后进行了审查，要求购物单上所有的物品价格的极差（最贵的减去最便宜的）不超过 $3$（当然金明至今不知道为什么会这样）。他希望在不超过 $W$ 元（可以等于 $W$ 元）的前提下，使购买的重要度总和 $\sum p_i$ 的最大。

请你帮助金明设计一个满足要求的购物单，你只需要告诉我们重要度的最大的和。

inputFormat:
输入的第 $1$ 行，为两个正整数，用一个空格隔开：

$n,W$（其中 $W$ 表示总钱数，$n$ 为希望购买物品的个数。）

从第 $2$ 行到第 $n+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v_p$（其中 $v$ 表示该物品的价格，$p$ 表示该物品的重要度）

outputFormat: 输出只有一个正整数，为不超过总钱数的物品的重要度的总和的最大值。


title: 斐波那契数列

description:
定义一个数列：

$f(0) = a, f(1) = b, f(n) = f(n - 1) + f(n - 2)$

其中 $a, b$ 均为正整数，$n \geq 2$。

问有多少种 $(a, b)$，使得 $k$ 出现在这个数列里，且不是前两项。

由于答案可能很大，你只需要输出答案模 $10^9 + 7$ 的结果即可。

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

outputFormat: 一行一个数，表示答案模 $10^9 + 7$ 的结果。


title: [BJOI2017] 喷式水战改

background:
拿到了飞机的驾照(?)，这样补给就不愁了

XXXX年XX月XX日

拿到了喷气机(??)的驾照，这样就飞得更快了

XXXX年XX月XX日

拿到了攻击机(???)的驾照（不存在的）

XXXX年XX月XX日

用铅版做夹层的话，机身可是会变重的呢

XXXX年XX月XX日

幸酱的特制快递，精确投递到了目标地点

-------------------------------------

又是核平的一天。

天音正在给喷气机做保养，并充填燃料。

这种喷气机是某姬(?????)特别制作的，发动机拥有三种工作状态

1、通常型（Original）：在高空平飞或隐蔽飞行时进行的低功耗高效率工作状态

2、后期型（Extended）：为在俯冲时最大化能量利用率而特别改造过的工作状态

3、增强型（Enhanced）：在俯冲攻击结束后为产生极限扭力抬高高度的工作状态

在一次攻击中，喷气机将会经历"通常-后期-增强-通常"的工作流程

不同工作状态中，燃料的利用效率是不同的

现在天音正在调整喷气机燃料装填序列

你需要做的就是求出燃料能产生的最大总能量

为什么是你？

和平还是核平，选一个吧

description:
初始燃料序列为空。每次操作会向序列中的 $p _ i$ 位置添加 $x _ i$ 单位的同种燃料，该燃料每一单位在三种工作状态下能产生的能量分别为 $a _ i, b _ i, c _ i$。

添加的位置 $p _ i$ 是指，在添加后，加入的第一个单位燃料前面有 $p _ i$ 个单位的原燃料。

全部的 $x _ i$ 单位燃料依次放置，然后原来在 $p _ i$ 位置的燃料（如果有的话）依次向后排列。

对于一个确定的燃料序列，其能产生的最大总能量为：将序列依次分成"通常-后期-增强-通常"四段（每段可以为空），每一段在对应工作状态下产生的能量之和的最大值。

对于每次添加操作，你需要给出该次操作使得最大总能量增加了多少。

如果对于这种计算方式没有直观的感受，可以查看样例说明。

inputFormat:
第一行一个数 $n$，表示操作个数。

接下来 $n$ 行，每行 $5$ 个数 $p _ i, a _ i, b _ i, c _ i, x _ i$，空格分隔，表示向序列中的 $p _ i$ 位置添加 $x _ i$ 单位的同种燃料

这种燃料每单位在通常、后期、增强工作状态下产生的能量分别为 $a _ i, b _ i, c _ i$。

outputFormat: $n$ 行，每行一个数，表示该次操作后能量序列所能产生的最大总能量增加了多少。

hint:
第一次操作后，燃料序列为[1 1]，最大能量发生方式为[En1 En1]，共46+46=92。

第二次操作后，燃料序列为[1 2 2 2 1]，最大能量发生方式为[Or1 Or2 Or2 Or2 En1]，共25+32+32+32+46=167，增加了167-92=75。

第三次操作后，燃料序列为[1 2 2 3 3 3 2 1]，最大能量发生方式为[Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1]，增加了99\*4=396。

第四次操作后，燃料序列为[1 2 4 4 4 4 4 2 3 3 3 2 1]

最大能量发生方式为[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1]。

第五次操作后，燃料序列为[1 2 4 4 4 4 4 2 3 3 3 2 1 5 5 5 5 5 5]

最大能量发生方式为[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5]。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$, $1 \leq a_i, b_i, c_i \leq 10^4$， $1 \leq x_i \leq 10^9$。

对于 $100\%$ 的数据，保证插入时序列中至少已有 $p _ i$ 单位的燃料。

后 $50\%$ 数据有梯度。


title: [BJOI2017] 同构

description:
你有 $n$ 个点，你可以在这 $n$ 个点之间连无向边，两个点之间至多只能连一条边，也不允许连自环，问至多能连多少条边。

但这个问题的答案显然是 $\dfrac{n(n-1)}{2}$ 条。所以有一个额外的限制，要求这个图不存在非平凡的自同构。

一个图 $G$ 有非平凡的自同构定义为存在一个 $1$ 到 $n$ 的置换 $p(1)$ 到 $p(n)$ 满足对于所有点 $u,v$，$(u, v)$ 之间有边当且仅当 $(p(u), p(v))$ 之间有边，并且这个置换非平凡也就是存在一个点 $u$ 使得 $p(u) \ne u$。

比如对于一个 $5$ 个点的图 $(1,2),(2,3),(3,4),(4,5),(5,1),(1,3)$，那么 $p(1)=3$，$p(2)=2$，$p(3)=1$，$p(4)=5$，$p(5)=4$ 为这个图的一个非平凡的自同构。

你要回答一个 $n$ 个点的无向简单的不存在非平凡自同构的图最多有多少条边，如果答案不存在，即不存在 $n$ 个点满足条件的图，请输出 `-1`，否则输出答案对 $10^9+7$ 取模的结果。

inputFormat:
**本题有多组数据。**
一行一个正整数 $T$ 表示数据组数。
对于每组数据：
一个正整数 $n$ 表示你要回答的图的点的个数。

outputFormat:
对于每组数据：
一行一个整数代表答案对 $10^9+7$ 取模的结果，如果不存在 $n$ 个点满足条件的图，就输出 `-1`。


title: [BJOI2017] 开车

description:
有 $n$ 辆车，分别在 $a_1, a_2, \ldots , a_n$ 位置和 $n$ 个加油站，分别在 $b_1, b_2, \ldots ,b_n$ 位置。

每个加油站只能支持一辆车的加油，所以你要把这些车开到不同的加油站加油。一个车从 $x$ 位置开到 $y$ 位置的代价为 $|x-y|$，问如何安排车辆，使得代价之和最小。

同时你有 $q$ 个操作，每次操作会修改第 $i$ 辆车的位置到 $x$，你要回答每次修改操作之后最优安排方案的总代价。

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

接下来一行 $n$ 个整数 $a_1, a_2,\ldots,a_n$。

接下来一行 $n$ 个整数 $b_1, b_2,\ldots,b_n$。

接下来一行一个正整数 $q$，表示操作的个数。

接下来 $q$ 行，每行有两个整数 $i$（$1\leq i\leq n$）和 $x$，表示将i这辆车开到 $x$ 位置的操作。

所有的车和加油站的范围一直在 $0$ 到 $10^9$ 之间。

outputFormat:
共 $q+1$ 行，第一行表示一开始的最优代价。

接下来 $q$ 行，第 $i$ 行表示操作 $i$ 之后的最优代价。


title: 高速公路（疑似错题）

description:
C 国拥有一张四通八达的高速公路树。

C 国有 $n$ 个城市，城市之间由一共 $n-1$ 条高速公路连接。除了首都 $1$ 号城市，每个城市都有一家本地的客运公司，可以发车前往全国各地。你可以把它认作以 $1$ 为根的树。两城市的距离定义为它们之间简单路径的长度。

假设有一个人要从 $i$ 号城市坐车出发前往与其距离为 $D$ 的 $j$ 号城市，那么他要花费 $P_i \times D+Q_i$ 元。由于距离首都越远，国家的监管就越松，所以距离首都越远，客运公司的 $P_i$ 越大，如果 $i$ 号城市是 $j$ 号城市的某个祖先，那么一定存在 $P_i \leq P_j$。

小 T 成为了国家统计局的调查人员，他需要对现在的高速路网进行一次调查，了解从其他每一个城市到达首都 $1$ 号城市所花费的金钱。

因为可能出现多转车（或不转车）的抵达首都的方法，所以人工计算这个结果是十分复杂的。大宁非常的懒，所以请你编写一个程序解决它。

inputFormat:
第 $1$ 行包含一个整数 $n$，表示城市的个数。

第 $2$ 到 $n$ 行，每行描述一个除首都之外的城市。其中第 $i$ 行包含 $4$ 个整数 $F_i,S_i,P_i,Q_i$，分别表示 $i$ 号城市的父亲城市，它到父亲城市高速公路的长度，以及乘车价格的两个参数。

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

其中第 $i$ 行表示从 $i+1$ 号城市出发，到达首都最少的乘车费用。

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

- 对于前 $40\%$ 的数据 $n \leq 1000$。
- 对于另外 $20\%$ 的数据，$F_i=i-1$
- 对于所有的数据，$1 \leq n \leq 10^6$，$0 \leq Pi,Qi \lt 2^{31}$，保证结果不会大于 $2^{63}-1$。


title: 树链剖分

background: 树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。(摘自百度百科)

description:
大宁最近在研究树链剖分。他发现树链剖分的时间复杂度主要由轻重链的划分方式保证，最常见的剖分方式是按照子树大小剖分。如图（摘自百度百科），黑边为重链，长度任意，白边为轻链，长度全部为1。注意，下图 1-2, 1-3 为不同轻链。

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

其中对于每个节点，其在重链上的儿子叫做重儿子，且只有唯一一个，而叶子节点没有重儿子。例如对于图上 1 号点，重儿子是 4 号点。显然，对于不同剖分方式，同一组查询访问的链的数量不同。现在给定一棵根为 1 号节点的有根树和若干询问操作，每次询问访问从 $u$ 到 $v$ 上面的所有轻重链一次。例如在上图的剖分方式中，查询 3 到 8 一共访问了 3 条：轻链 1-3，重链 1-4，轻链 4-8；查询 3 到 11 一共访问了 3 条：轻链 1-3，轻链 1-2，重链 2-11。

大宁请你给出一种剖分方案，使所有询问操作总共访问的**轻重链总条数**最小，由于可能有许多合法方案，请任意输出一种，我们提供Special Judge检验你的方案的正确性。

设你的剖分方式的查询链数为 $x$，std 答案的查询数为 $x_0$，评分参数为 $a$ 。

你得到的分数是：

* $10$ 分  当 $x\leq x_0$ 。

* $8$ 分  当 $0<(x-x_0)\leq a$ 。

* $7$ 分  当 $a<(x-x0)\leq 2\times a$ 。

* $6$ 分  当 $2\times a<(x-x0)\leq 3\times a$ 。

* $1$ 分  输出了合法的方案。

$a=\lfloor\frac{q}{300}\rfloor$, $q$ 为询问总数。

我们提供了 `Div\_Checker.exe` 来检验你的答案。把它放到 `div.in` , `div.out` 同文件夹下运行，其中 `div.in` 是输入数据的文件形式, `div.out` 是你的程序在该输入下的输出。如果你的 `div.out` 答案合法，它会返回：

`Your answer is XXX.`

`XXX` 是你的剖分方式在该输入数据下的查询次数，否则返回：

`Wrong Outdata.`

**注意: 在正式提交的时候不能使用文件输入输出。**

inputFormat:
第一行有两个正整数 $n$ 和 $q$ ，表示该树的节点数 $n$ 和查询次数 $q$ 。

接下来 $n-1$ 行，各有两个正整数 $u$ ，$v$ ，表示 $u$ 和 $v$ 之间有一条边。

接下来 $q$ 行为 $q$ 个询问，为 $U$，$V$，表示有一次从 $U$ 到 $V$ 的询问。

outputFormat: 一共 $n$ 行，对于 $i$ 号节点，如果它不是叶子节点，那么输出它在你的剖分方案里的重儿子，否则输出 0。

hint:
样例即为上图，但图上的剖分方式对于此处的查询并非最优。

对于 $20\%$ 的数据，$n,q<=10$

对于 $60\%$ 的数据，$n,q<=1000$

对于 $100\%$ 的数据，$1<=n<=100000$,$1<=q<=200000$ ,保证给出的是一棵合法的树。

[Div\_Checker下载](https://pan.baidu.com/s/1c26OLf6)

如果对Checker的使用方式不太理解，请参照下面的图片

图中数据为样例。

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

一个合法方案的输出。

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

不合法方案的输出。

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

---

$\text{upd 2022.8.26}$：新增加一组 Hack 数据。


title: 失败的竞猜游戏

background: 大宁是一个喜欢赌博的人，最近在玩一款竞猜游戏，然而屡战屡败。大宁非常不高兴，就去找游戏的运营商理论，质疑游戏的数据是否有意针对玩家。

description:
游戏规则如下：玩家给出 $A_0$，$a$，$b$ 三个整数，代表一个线性递推式：

$A_i=a \times A_{i-1} +b$

它定义了一个无限长度的数列 {$A_1$，$A_2$，$A_3$……}，而游戏系统会随机生成一个数 $n$，如果 $n$ 可以表示为该数列中的若干个**互不相同**的项 ( $A_0$ 不计入数列中) 之和，那么玩家胜利，反之玩家失败。现在大宁通过逼迫运营商交出了一组最近的游戏数据，但是他懒得一个个去算了，现在请你帮忙计算一下，数据中玩家一共获胜了多少次。

inputFormat:
第一行一个正整数 $T$，表示进行了 $T$ 场游戏。

接下来 $T$ 行，每行四个整数，描述一场游戏，分别为题目中的 $A_0$，$a$，$b$，$n$。

outputFormat: 输出一行 $Ans$，表示玩家在 $T$ 场游戏中获胜的次数。


title: 跳舞的线 - 乱拐弯

background:
# 线初始面对方向请自己确定

![您可以写dp](https://cdn.luogu.com.cn/upload/pic/30733.png)

玩过了 $LCA$ 之后，Imakf 觉得甚是无聊，于是便打开了 DL。

Imakf：刺客传奇又死在 $70\%$！突然有一点弃坑的想法鸭……

Imakf 想起自己玩了 $1$ 年的 DL，卡在园林教堂混沌，肝了几个月终于过了的欣喜，却被这个刺客传奇困住，禁不住泪眼朦胧。泪眼中，他突然发现手机变成了一个一个的像素点！Imakf 非常惊喜！这样不就可以写一个程序自动通关了吗？

可是不一会，他又陷入了失望……

Imakf：我不会写啊！！

description:
线现在在一个地图上，它正在 $(1,1)$ 上（左上角），最终要去到 $(M,N)$ 上。它不但只能往下或往右走，还只能在整数格子上移动。

Imakf 有的时候想要炫技，又有时想偷懒，所以他会告诉你这张地图的全貌，你要告诉他到达终点的最多和最少拐弯次数。

inputFormat:
第一行两个正整数 $M,N$，意义见题目描述。

第 $2\sim M+1$ 行，每行 $N$ 个字符。如果为 `#` 就代表这里有障碍，反之没有。

outputFormat:
输出两个正整数 $max,min$，$max$ 表示最多拐弯次数，$min$ 表示最少拐弯次数。

**如果到达不了就仅输出** `-1`。


title: [SHOI2013] 扇形面积并

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

给定 n 个同心的扇形，求有多少面积，被至少 $k$ 个扇形所覆盖。

inputFormat:
第一行是三个整数 $n$，$m$，$k$。$n$ 代表同心扇形个数，$m$ 代表将 $(−\pi ,\pi]$ 的角度区间平均分成 $2m$ 份。

从第二行开始的 $n$ 行，每行三个整数 $r，a_1，a_2$。描述了一个圆心在原点的扇形，半径为 $r$，圆心角是从弧度 $\pi\times \frac{a_1}{m}$ 到 $\pi\times \frac{a_2}{m}$（$a_1$ 不一定小于 $a_2$）。

outputFormat:
输出一个整数 $ans$ ，$\frac{\pi}{2m}\times ans$ 等于至少 $k$ 个扇形所覆盖的总面积。

数据保证答案在 $2^{63} - 1$ 范围内。


title: [SHOI2013] 发微博

description:
刚开通的 SH 微博共有 $n$ 个用户（$1\sim n$ 标号），在这短短一个月的时间内，用户们活动频繁，共有 $m$ 条按时间顺序的记录：

```plain
! x 表示用户 x 发了一条微博；
+ x y 表示用户 x 和用户 y 成为了好友
− x y 表示用户 x 和用户 y 解除了好友关系
```
当一个用户发微博的时候，所有他的好友（直接关系）都会看到他的消息。

假设最开始所有人之间都不是好友关系，记录也都是合法的（即 `+ x y` 时 $x$ 和 $y$ 一定不是好友，而 `− x y` 时 $x$ 和 $y$ 一定是好友）。

问这 $m$ 条记录发生之后，每个用户分别看到了多少条消息。

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

接下来 $m$ 行，按时间顺序读入 $m$ 条记录，每条记录的格式如题目所述，用空格隔开。

outputFormat: 输出一行 $n$ 个用空格隔开的数（行末无空格），第 $i$ 个数表示用户 $i$ 最后看到了几条消息。


title: [SHOI2013] 二重镇

description:
这是一个充满爱的村子，它的名字叫二重镇。在这个爱意浓浓的村子里，居民们的生活快乐又安宁。二重镇呈长条形状，可分为排成一行的 $N$ 个方格。每个格子可能是空地，也可能是小草、灌木、大树、房屋或城堡中的一种物品。每种物品都有一个等级，小草的等级是 $1$，灌木的等级是 $2$，依此类推。

你是这个村庄的建造者。你会陆续获得 $D$ 件物品，你要将它们合理地放置在村庄的空地上。你的目标是要让村子的总人气尽可能大。人气的获得规则在后面说明。关于放置的规则有以下几条：

* 第一，每件物品都必须放在一个地方，不可丢弃，如果没有空地了，游戏直接结束；

* 第二，物品可以放在一格空地上，或者临时放在仓库里。仓库同时最多只能放一件物品，它一开始是空的。只存在一个仓库；

* 第三，一旦物品放在某个空格上，只要符合条件，系统就会自动将一些物品合成一个大的物品，这是强制被动的，也是瞬间的。直到合成结束后，才能放置下一个物品。

* 第四，存放在仓库中的物品，随时可以取出放到空地上（但注意不能在合成的过程中放置），也可以一直留在仓库里。

* 第五，除非利用仓库，不然不能更改物品的放置顺序；

总结起来，这个游戏的流程就是获得一个新物品，决定是否将这个物品存入仓库，再决定将仓库中的物品或新物品放到哪个空地上，系统自动判定合成，获得人气，直到所有物品都被放置完毕，或空地用完为止。

最后是关于合成的规则。合成是自动完成的，也是强制性的。如果有连续两个或以上相邻的格子里有相同等级的物品，它们会自动合体成一个新的物品，新物品的等级比之前高一个级别。合体分三步：

* 第一步，确定有多少物品参与合成，这些物品的位置必须连在一起，等级相同。参与合体的物品会全部消失，对应的格子边成空地；

* 第二步，假设有 $A$ 个 $K$ 级物品参与合体，那么将获得$A\times 2^K$ 点人气。例如有一次五棵小草进行了合体，那么总人气就会增加 $5 \times 2^1=10$；

* 第三步，一个 $K+1$ 等级的物品会出现在一个格子里。如果 $K+1$ 大于 $5$，则跳过这步，但第二步中的人气仍然要算，第一步中的旧物品也会被清除。这个高等级的物品只会出现在参与合体的格子上。每个格子会记录最后一次被放置物品的时间，新的物品会出现在该时间最晚的那个格子里，形象地说，就是出现在最近被放置过东西的格子；

最后，请注意合成是会触发多次的，比如两个小草合成一个灌木，如果这棵灌木旁边还有其他灌木，合体将继续发生下去。

现在，给出 $N$ 和获得物品的顺序及等级，请你要合理地将这些物品放置在一个初始全是空地的村子里，使得村子最终的人气值尽可能高。当所有物品都被放置，或者某一刻村子里没空地了，你都会结束村子的建设，而此时村子里累计人气值就是你的最终成果。

inputFormat:
第一行给出两个整数 $N$ 和 $D$，用空格隔开。$N$ 表示村庄大小，$D$ 表示建设村庄的天数。

第二行为一个字符串，每个字符为 $1 \ldots 5$ 之间的一个字符，表示每天你可以放置的物品的等级。

outputFormat: 输出一个整数，表示你能得到的最大的人气值。


title: [ICPC-Beijing 2006] 狼抓兔子

description:
现在小朋友们最喜欢的"喜羊羊与灰太狼"。话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

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

左上角点为 $(1,1)$，右下角点为 $(N,M)$（上图中 $N=3$，$M=4$）。有以下三种类型的道路：

1. $(x,y)\rightleftharpoons(x+1,y)$

2. $(x,y)\rightleftharpoons(x,y+1)$

3. $(x,y)\rightleftharpoons(x+1,y+1)$

道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的。左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里，现在它们要跑到右下角 $(N,M)$ 的窝中去，狼王开始伏击这些兔子。当然为了保险起见，如果一条道路上最多通过的兔子数为 $K$，狼王需要安排同样数量的 $K$ 只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。

inputFormat:
第一行两个整数 $N,M$，表示网格的大小。

接下来分三部分。

第一部分共 $N$ 行，每行 $M-1$ 个数，表示横向道路的权值。

第二部分共 $N-1$ 行，每行 $M$ 个数，表示纵向道路的权值。

第三部分共 $N-1$ 行，每行 $M-1$ 个数，表示斜向道路的权值。

outputFormat: 输出一个整数，表示参与伏击的狼的最小数量。

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

对于全部的测试点，保证 $3 \leq N,M \leq 1000$，所有道路的权值均为不超过 $10^6$ 的正整数。


title: 斐波那契数列

description:
大家都知道，斐波那契数列是满足如下性质的一个数列：

• $f_1 = 1$

• $f_2 = 1$

• $f_n = f_{n-1} + f_{n-2}$ ($n \geq 2$ 且 $n$ 为整数)

请你求出 $f_n \mod p$ 的值。

inputFormat:
- 第 1 行：一个整数 $n$。

- 第 2 行：一个整数 $p$。

outputFormat: - 第 1 行：$f_n \mod p$ 的值。


title: 分数统计

background: 大宁考完联赛回来，成功的躲过了期中考试，但是他的班主任 Yellow_sword  不会放过他。

description:
Yellow_sword 要大宁给他弄一个数据库，维护班级的考试平均分。每个人期中考试各科的分数已经被统一的转化为评价值，为一个 $[1,100]$ 之间的整数。它评价了这个人的总体水平，现在 Yellow_sword 丢给了大宁 $n$ 个班级的班级平均评价值和每个班的人数，由于 Yellow_sword 和大宁都很懒，所以都假装每个班每个人的评价值就是班级的平均评价值。他想知道：

1. 连续的若干个班所有人评价值的平均数。
2. 连续的若干个班所有人评价值的众数（若有多个取最小的那个众数）。
3. 连续的若干个班所有人评价值的极差（即评价值最高和最低的差）。

既然大家都很懒，那事情就给你来做了。

inputFormat:
第一行为两个整数 $n$ 和 $q$，表示有 $n$ 个班级和 $q$ 个询问。

第二行为 $n$ 个整数 $a_i$，表示第 $i$ 个班的平均评价值。

第三行为 $n$ 个整数 $b_i$，表示第 $i$ 个班的人数。

接下来 $q$ 行，每行一个查询，格式为：`Opt u v`。

表示在第 $u$ 到 $v$ 个班级里查询 $Opt$ 对应的项，$Opt\in[1,3]$，意义为前文所述。

outputFormat: 对于每一个询问，在 $q$ 行中输出对应的结果，平均数保留两位小数。


title: [清华集训2017] 生成树计数

description:
在一个 $s$ 个点的图中，存在 $s-n$ 条边，使图中形成了 $n$ 个连通块，第 $i$ 个连通块中有 $a_i$ 个点。

现在我们需要再连接 $n-1$ 条边，使该图变成一棵树。对一种连边方案，设原图中第 $i$ 个连通块连出了 $d_i$ 条边，那么这棵树 $T$ 的价值为：

$$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right) $$

你的任务是求出所有可能的生成树的价值之和，对 $998244353$ 取模。

inputFormat:
输入的第一行包含两个整数 $n,m$，意义见题目描述。

接下来一行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$ $(1\le a_i< 998244353)$。

* 你可以由 $a_i$ 计算出图的总点数 $s$，所以在输入中不再给出 $s$ 的值。

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


title: 无限之环

description:
曾经有一款流行的游戏，叫做 Infinity Loop，先来简单的介绍一下这个游戏：

游戏在一个 $n \times m$ 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 $15$ 种形状：

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

游戏开始时，棋盘中水管可能存在漏水的地方。

形式化地：如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。

玩家可以进行一种操作：选定一个含有**非直线型**水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 $90$ 度。

直线型水管是指左图里中间一行的两种水管。

现给出一个初始局面，请问最少进行多少次操作可以使棋盘上不存在漏水的地方。

inputFormat:
第一行两个正整数 $n$, $m$, 代表网格的大小。

接下来 $n$ 行每行 $m$ 个数，每个数是 $[0,15]$ 中的一个，你可以将其看作一个 $4$ 位的二进制数，从低到高每一位分别代表初始局面中这个格子上、右、下、左方向上是否有水管接头。

特别地，如果这个数是 $0$ ，则意味着这个位置没有水管。

比如 $3(0011_{(2)})$ 代表上和右有接头，也就是一个 $L$ 型，而 $12(1100_{(2)})$ 代表下和左有接头，也就是将 $L$ 型旋转 $180$ 度。

outputFormat: 输出共一行，表示最少操作次数。如果无法达成目标，输出 $-1$。

hint:
【样例 1 解释】

样例 1 棋盘如下:

旋转方法很显然，先将左上角虚线方格内的水管顺时针转 $90$ 度

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

然后右下角虚线方格内的水管逆时针旋转 $90$ 度，这样就使得水管封闭了

【样例 2 解释】

样例 2 为题目描述中的第一张图片，无法达成目标。

【样例 3 解释】

样例 3 为题目描述中的第二张图片，将除了中心方格以外的每个方格内的水管都转 $180$ 度即可。

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


title: Hello world!

background: 不远的一年前，小 V 还是一名清华集训的选手，坐在机房里为他已如风中残烛的OI 生涯做最后的挣扎。而如今，他已成为了一名光荣的出题人。他感到非常激动，不禁感叹道： “Hello world!”。

description:
小 V 有 $n$ 道题，他的题都非常毒瘤，所以关爱选手的 ufozgg 打算削弱这些题。为了逃避削弱，小 V 把他的毒瘤题都藏到了一棵 $n$ 个节点的树里（节点编号从 $1$ 至 $n$），这棵树上的所有节点与小 V 的所有题一一对应。小 V 的每一道题都有一个毒瘤值，节点 $i$ （表示标号为 $i$ 的树上节点，下同）对应的题的毒瘤值为 $a_i$。

魔法师小 V 为了保护他的题目，对这棵树施了魔法，这样一来，任何人想要一探这棵树的究竟，都必须在上面做跳跃操作。每一次跳跃操作包含一个起点 $s$ 、一个终点 $t$ 和一个步频 $k$ ，这表示跳跃者会从 $s$ 出发，在树上沿着简单路径多次跳跃到达 $t$ ，每次跳跃，如果从当前点到 $t$ 的最短路长度不超过 $k$ ，那么跳跃者就会直接跳到 $t$ ，否则跳跃者就会沿着最短路跳过恰好 $k$ 条边。

既然小 V 把题藏在了树里， ufozgg 就不能直接削弱题目了。他就必须在树上跳跃，边跳跃边削弱题目。 ufozgg 每次跳跃经过一个节点（包括起点 $s$ ，当 $s = t$ 的时候也是如此），就会把该节点上的题目的毒瘤值开根并向下取整：即如果他经过了节点 $i$，他就会使 $a_i = \lfloor \sqrt{a_i} \rfloor$。这种操作我们称为削弱操作。

ufozgg 还会不时地希望知道他对题目的削弱程度。因此，他在一些跳跃操作中会放弃对题目的削弱，转而统计该次跳跃经过节点的题目毒瘤值总和。这种操作我们称为统计操作。

吃瓜群众绿绿对小 V 的毒瘤题和 ufozgg 的削弱计划常感兴趣。他现在想知道ufozgg 每次做统计操作时得到的结果。你能帮帮他吗？

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

inputFormat:
从文件 helloworld.in 中读入数据。

输入的第一行一个正整数 $n$ ，表示树的节点数。

接下来一行 $n$ 个用空格隔开的正整数 $a_1, a_2, \ldots, a_n$，依次描述每个节点上题目的毒瘤值。

接下来 $n − 1$ 行，描述这棵树。每行 $2$ 个正整数 $u, v$ ，描述一条树上的边 $(u, v)$ 。（保证 $1 \leq u, v \leq n$ ，保证这 $n − 1$ 条边构成了一棵树）

接下来一行一个正整数 $Q$ ，表示 ufozgg 的操作总数。

接下来 $Q$ 行按 ufozgg 执行操作的先后顺序依次描述每个操作，每行 $4$ 个用空格隔开的整数 $op, s, t, k$ ，表示 ufozgg 此次跳跃的起点为 $s$ ，终点为 $t$ ，步频为 $k$ 。如果 $op = 0$ ，表示这是一次削弱操作；如果 $op = 1$ ，表示这是一次统计操作。

outputFormat: 对于每个统计操作，输出一行一个整数，表示此次统计操作统计到的所有题的毒瘤值总和。


title: 小 Y 和地铁

description:
小 Y 是一个爱好旅行的 OIer。一天，她来到了一个新的城市。由于不熟悉那里的交通系统，她选择了坐地铁。

她发现每条地铁线路可以看成平面上的一条曲线，不同线路的交点处一定会设有换乘站 。通过调查得知，没有线路是环线，也没有线路与自身相交。任意两条不同的线路只会在若干个点上相交，没有重合的部分，且没有三线共点的情况。即，如图所示的情况都是不存在的：

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

小 Y 坐着地铁 $0$ 号线，路上依次经过了 $n$ 个换乘站。她记下了每个换乘站可以换乘的线路编号，发现每条线路与她所乘坐的线路最多只有 $2$ 个换乘站。现在小 Y 想知道，除掉她经过的换乘站以外，这个城市里最少有几个换乘站。只有你告诉她正确的答案，她才会答应下次带你去玩呢。

inputFormat:
**请注意本题有多组输入数据。**

输入数据的第一行是一个整数 $T$，表示输入数据的组数。接下来依次给出每组数据。

对于每组数据，第一行是一个整数 $n$，表示小 Y 经过的换乘站的数目。第二行为 $n$ 个用空格隔开的整数，依次表示每个换乘站的可以换乘的线路编号。这些编号都在 $1\sim n$ 之内。

outputFormat: 对于每组输入数据，输出一行一个整数，表示除掉这 $n$ 个换乘站之外，最少有几个换乘站。

hint:
【样例 1 解释】

对于样例的前两组数据，一种可能的最优答案如下图所示。

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

【子任务】

一共有 $50$ 个测试点，每个测试点 $2$ 分。你只有在答案完全正确时才能得到该测试点的全部分数，否则不得分。

对于所有测试点，以及对于样例， $1 \leq T \leq 100$, $1 \leq n \leq 44$。对于每个测试点， $n$ 的范围如下表：

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


title: 小 Y 和二叉树

description:
小 Y 是一个心灵手巧的 OIer，她有许多二叉树模型。

小 Y 的二叉树模型中，每个结点都具有一个编号，小 Y 把她最喜欢的一个二叉树模型挂在了墙上，树根在最上面，左右子树分别在树根的左下方与右下方，且他们也都满足这样的悬挂规则。为了让这个模型更加美观，小 Y 选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法。所谓中序遍历最小，就是指中序遍历的结点编号序列的字典序最小。

一天，这个模型不小心被掉在了地上，幸运的是，所有结点和边都没摔坏，但是她想不起这个模型原来是怎么悬挂的了，也就是说：她想不起来树根节点的编号了。

小 Y 最近忙于准备清华集训，所以没太多时间处理别的事情，她只好找到同样心灵手巧的你帮忙复原她的二叉树模型。

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

后接 $n$ 行，每行若干个整数：

第 $i + 1$ 行的第一个整数为 $k_i$ ，表示编号为 $i$ 的结点的度数，后接 $k_i$ 个整数 $a_{i, j}$ ，表示编号为 $i$ 的结点与编号为 $a_{i, j}$ 的结点之间有一条边。

同一行输入的相邻两个元素之间，用恰好一个空格隔开。

outputFormat: 输出共一行， $n$ 个整数，表示字典序最小的中序遍历。

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

【子任务】

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

本题共 $20$ 个测试点，每个测试点 $5$ 分。各个测试点的数据范围如下：

随机数据的生成方式如下：对于第 $13$ 个测试点，从一棵两个结点的树开始，每次随机一个树上的度数为 $1$ 的结点（即叶结点），并生成两个与之直接相连的结点，直到这棵树上有 $n$ 个结点。显然，在这个测试点中， $n$ 是一个偶数。对于第 $15$ 和第 $16$ 个测试点，从一棵一个结点的树开始，每次随机一个树上的度数不超过 $2$ 的结点，并生成一个与之直接相连的结点，直到这棵树上有 $n$ 个结点。

【提示】

我们提供了一个只包含输入和输出功能的程序 `binary\_sample.cpp`。关于该程序的说明，见 `readme.txt`。你可以在答题时使用该程序的代码，也可以不使用，这将与你的得分无关。


title: 小 Y 和恐怖的奴隶主

background:
“A fight? Count me in!” 要打架了，算我一个。

“Everyone, get in here!” 所有人，都过来！

description:
小 Y 是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。

虽然这个 Boss 有 $10^{100}$ 点生命值，但它只带了一个随从——一个只有 $m$ 点生命值的“恐怖的奴隶主”。

这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 $\leq 0$），且 Boss 的随从数量小于上限 $k$，便会召唤一个新的具有 $m$ 点生命值的“恐怖的奴隶主”。

现在小 Y 可以进行 $n$ 次攻击，每次攻击时，会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个，并扣减 $1$ 点生命值，她想知道进行 $n$ 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差，你的答案需要对 $998244353$ 取模。

inputFormat:
输入第一行包含三个正整数 $T, m, k$，$T$ 表示询问组数，$m, k$ 的含义见题目描述。

接下来 $T$ 行，每行包含一个正整数 $n$，表示询问进行 $n$ 次攻击后扣减Boss的生命值点数的期望。

outputFormat:
输出共 $T$ 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 $998244353$ 取模的结果。

可以证明，所求期望一定是一个有理数，设其为 $p / q$ $(\mathrm{gcd}(p,q) = 1)$，那么你输出的数 $x$ 要满足 $p \equiv qx \pmod{998244353}$。

hint:
【样例 $1$ 解释】

对于第一次询问，第一次攻击有 $\frac{1}{2}$ 的概率扣减 Boss 的生命值，有 $\frac{1}{2}$ 的概率扣减随从的生命值，所以答案为 $\frac{1}{2}$。$1 \equiv 2 \times 499122177 \pmod{998244353}$。

对于第二次询问，如果第一次攻击扣减了 Boss 的生命值，那么有 $\frac{1}{2}$ 的概率第二次攻击仍扣减 Boss 的生命值，有 $\frac{1}{2}$ 的概率第二次攻击扣减随从的生命值；如果第一次攻击扣减了随从的生命值，那么现在又新召唤了一个随从（“恐怖的奴隶主”），于是有 $\frac{1}{3}$ 的概率第二次攻击扣减 Boss 的生命值，有 $\frac{2}{3}$ 的概率第二次攻击扣减随从的生命值。所以答案为 $\frac{1}{2}\times\frac{1}{2}\times2+\frac{1}{2}\times\frac{1}{2}\times1+\frac{1}{2}\times\frac{1}{3}\times1+\frac{1}{2}\times\frac{2}{3}\times0 = \frac{11}{12}$。 $11 \equiv 12 \times 415935148\pmod{998244353}$。

【提示】

题目顺序可能与难度无关。

【子任务】

在所有测试点中，$1 \leq T \leq 1000, 1 \leq n \leq {10}^{18}, 1 \leq m \leq 3, 1 \leq k \leq 8$。

各个测试点的分值和数据范围如下：

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


title: [NOI2003] 文本编辑器

description:
很久很久以前，$DOS3.x$ 的程序员们开始对 $EDLIN$ 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器⋯⋯

多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试） ！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？

为了明确目标，小明对“文本编辑器”做了一个抽象的定义:

文本：由 $0$ 个或多个 ASCII 码在闭区间 [$32$, $126$] 内的字符构成的序列。

光标：在一段文本中用于指示位置的标记，可以位于文本首部，文本尾部或文本的某两个字符之间。

文本编辑器：由一段文本和该文本中的一个光标组成的，支持如下操作的数据结构。如果这段文本为空，我们就说这个文本编辑器是空的。

| 操作名称  | 输入文件中的格式  | 功能  |
| :------------ | :------------ | :------------ |
| $\text{Move}(k)$  | Move k  |  将光标移动到第 $k$ 个字符之后，如果 $k=0$，将光标移到文本开头 |
| $\text{Insert}(n,s)$  | Insert n s  | 在光标处插入长度为 $n$ 的字符串 $s$，光标位置不变$n\geq1$|
| $\text{Delete}(n)$  | Delete n  | 删除光标后的 $n$ 个字符，光标位置不变，$n \geq 1$  |
| $\text{Get}(n)$  | Get n  |输出光标后的 $n$ 个字符，光标位置不变，$n \geq 1$   |
| $\text{Prev}()$  | Prev  | 光标前移一个字符  |
| $\text{Next}()$  | Next |  光标后移一个字符 |

你的任务是：

- 建立一个空的文本编辑器。

- 从输入文件中读入一些操作并执行。

- 对所有执行过的 `GET` 操作，将指定的内容写入输出文件。

inputFormat:
输入文件 `editor.in` 的第一行是指令条数 $t$，以下是需要执行的 $t$ 个操作。其中：

为了使输入文件便于阅读， `Insert` 操作的字符串中可能会插入一些回车符， 请忽略掉它们（如果难以理解这句话，可以参照样例） 。

除了回车符之外，输入文件的所有字符的 ASCII 码都在闭区间 [$32$, $126$] 内。且

行尾没有空格。

这里我们有如下假定：

-  `MOVE` 操作不超过 $50000$ 个， `INSERT` 和 `DELETE` 操作的总个数不超过 $4000$，`PREV` 和 `NEXT` 操作的总个数不超过 $200000$。

-  所有 `INSERT` 插入的字符数之和不超过 $2M$（$1M=1024\times 1024$ 字节） ，正确的输出文件长度不超过 $3M$ 字节。

-  `DELETE` 操作和 `GET` 操作执行时光标后必然有足够的字符。 `MOVE` 、 `PREV` 、 `NEXT` 操作必然不会试图把光标移动到非法位置。

-  输入文件没有错误。

对 C++ 选手的提示：经测试，最大的测试数据使用 `fstream` 进行输入有可能会比使用 `stdio` 慢约 $1$ 秒。

outputFormat: 输出文件 editor.out 的每行依次对应输入文件中每条 `Get` 指令的输出。

samples:
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22


title: 公主の#18文明游戏

background: 公主发现了一个游戏，998，于是我就花钱给她买下来了（捂脸）

description:
这个游戏叫做《文♂明》（滑稽），但是跟平常意义上的不一样。

这个游戏里有n个城市，标号1~n，有m条双向道路相连，编号1~m。

游戏里会系统会添加Ni个人到一个城市Xi，并给定这些人的信仰Ci

系统还会切断一条道路，并给定道路编号Xi

系统还会给定一个城市Xi，询问从Xi出发可以到达的所有城市中选择Ni个人，

使得他们信仰都为Ci的概率为多少，对19260817取模。

输入数据不保证没有重边和自环。

输入数据不保证同一条边不会被切断两次以上。

因为是公主的游戏，所以本题输入量较大，请注意输入的优化

inputFormat:
第一行三个正整数n,m,q

接下来n行，每行两个正整数Ni,Ci，分别代表第i个城市初始人数和信仰

接下来m行，每行两个正整数Xi,Yi，分别代表这条道路的起点和终点

接下来q行，每行第一个正整数opt（1<=opt<=3）

当opt=1时，表示系统添加人类，输入三个整数Xi,Ni,Ci

当opt=2时，表示系统切断道路，输入一个整数Xi

当opt=3时，表示系统询问概率，输入三个整数Xi,Ni,Ci

outputFormat: 对于每一个opt=3的操作，输出一行一个整数。

hint:
吐槽某人居然没告诉我 我没放样例

补发样例（其实我本来有样例来着）

在这里跟大家道歉

对于30%的数据，1<=n,m,q<=100

对于60%的数据，1<=n,m,q<=50000

对于100%的数据，1<=n,m,q<=400000

对于100%的数据，保证所有信仰在C++的int，Pascal的long int范围内

对于100%的数据，保证每次添加的人数和初始人数都不超过10

对于100%的数据，保证数据随机生成

题目 @玫葵之蝶


title: 公主の#19准备月考

background: 公主在玩完游戏后，也要月考了。（就算是公主也要月考啊QWQ）

description:
公主的文综太差了，全校排名1100+（全校就1100多人），她分析了好久，发现她如果把所有时间放在选择题上，得分会比较好一点。

文综题目共有n个，编号从1到n

公主给每个题目算出来了一个预估值Ai，她认为，一段连续题目的答案会在它们的预估值的gcd和lcm之间；有时候她的想法不同了，一些题目的预估值会改变；有时候，会出现多选题，多选题的答案数量就是一段连续题目答案的预估值的公约数的个数。

具体来说，对于一个数列，有四种操作：

L x y p 表示公主询问区间[x,y]的数字的lcm对p取模之后的值

G x y p 表示公主询问区间[x,y]的数字的gcd对p取模之后的值

C x y c 表示公主改变区间[x,y]的数字的值，统一为c

S x y p 表示公主询问区间[x,y]的数字的公因数个数对p取模之后的值

公主月考不能挂科，不然她就不能学习OI了（假的），所以请你帮帮她吧！

inputFormat:
第一行，两个正整数n和q，q表示操作次数

第二行，n个正整数，表示dkw对题目的预估值

接下来q行，每行输入一个操作，格式详见题目描述

outputFormat: 对于每个询问，输出它的答案。


title: 汽车加油行驶问题

description:
给定一个 $N \times N$ 的方形网格，设其左上角为起点◎，坐标$(1,1)$，$X$ 轴向右为正， $Y$ 轴向下为正，每个方格边长为 $1$ ，如图所示。

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

一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 $(N,N)$。

在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

1. 汽车只能沿网格边行驶，装满油后能行驶 $K$ 条网格边。出发时汽车已装满油，在起点与终点处不设油库。

1. 汽车经过一条网格边时，若其 $X$ 坐标或 $Y$ 坐标减小，则应付费用 $B$ ，否则免付费用。

1. 汽车在行驶过程中遇油库则应加满油并付加油费用 $A$。

1. 在需要时可在网格点处增设油库，并付增设油库费用 $C$(不含加油费用$A$ )。

1. $N,K,A,B,C$ 均为正整数， 且满足约束: $2\leq N\leq 100,2 \leq K \leq 10$。

设计一个算法，求出汽车从起点出发到达终点所付的最小费用。

inputFormat:
文件的第一行是 $N,K,A,B,C$ 的值。

第二行起是一个$N\times N$ 的 $0-1$ 方阵,每行 $N$ 个值,至 $N+1$ 行结束。

方阵的第 $i$ 行第 $j$ 列处的值为 $1$ 表示在网格交叉点 $(i,j)$ 处设置了一个油库,为 $0$ 时表示未设油库。各行相邻两个数以空格分隔。

outputFormat: 程序运行结束时,输出最小费用。

hint: $2 \leq n \leq 100,2 \leq k \leq 10$

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


title: [CTSC2012] 梭哈游戏

description:
小 Y 和小 Z 最近迷上了一种叫梭哈的扑克游戏。梭哈又称沙蟹，是英文 Show Hand 的音译，是一种使用黑桃、红心、梅花、方片的 A 到 K 共 $52$ 张牌(没有大小王）来进行的扑克牌游戏。

和其他扑克游戏一样，梭哈的目的是得到最大的牌型并赢得牌局：每名玩家首先需要下基本的注额，之后将获得一张底牌，这张牌只有自己知道。普通梭哈游戏的规则是，在发完底牌后的第一轮时，每个玩家都将得到一张明牌（明牌是摆在台面上的，所有人都能看见），拥有最大明牌的玩家首先发言，他可以下注、不下注（让牌）或盖牌（放弃）也可以全压（梭哈），其他玩家可以跟注（有玩家全压时必须全压）、加注或盖牌（放弃），放弃的玩家将无法继续游戏，并且之

前押的筹码无法取回。而全压之后将直接把每个人的手牌补充至 $5$ 张进行最后的判定；第二圈、第三圈和第四圈的进程与第一圈是类似的。最后，每位玩家要比牌型的大小以确定赢家。牌最大的玩家赢得牌局。

所有五张牌的组合，按以下秩序， 由大至小 排行分为不同牌型：

1、同花顺（`Straight Flush`）：同一花色，顺序的牌。 例： $Q♦ J♦ 10♦ 9♦ 8♦$；

2、四条（`Four of a Kind`）：有四张同一点数的牌。 例： $10♣ 10♦ 10♥ 10♠ 9♥$；

3、满堂红（`Full House`）：三张同一点数的牌，加一对其他点数的牌。 例： $8♣ 8♦ 8♠ K♥ K♠$；

4、同花（`Flush`）：五张同一花色的牌。 例： $A♠ K♠ 10♠ 9♠ 8♠$；

5、顺子（`Straight`）：五张顺连的牌。 例： $K♦ Q♥ J♠ 10♦ 9♦$；

6、三条（`Three of a kind`）：有三张同一点数的牌。 例： $J♣ J♥ J♠ K♦ 9♠$；

7、两对（`Two Pairs`）：两张相同点数的牌，加另外两张相同点数的牌。 例： $A♣ A♦ 8♥ 8♠ Q♠$；

8、一对（`One Pair`）：两张相同点数的牌。 例： $9♥ 9♠ A♣ J♠ 8♥$；

9、无对（`Zilch`）：不能排成以上组合的牌，以点数决定大小。例： $A♦ Q♦ J♠ 9♣ 8♣$。

若牌型一样则 利用 点数 和花色决定胜负 。（点数 优先）

点数 的顺序（ 从 大至小） 为：$A>K>Q>J>10>9>8>7>6>5>4>3>2$。（注：当 $5$ 张手牌是 $5, 4, 3, 2, A$ 的时候，$A$ 可以看作最小的牌，此时的牌型仍然为顺子，是顺子里面最小的一个）。

花色的顺序（大至小） 为：黑桃(♠)$>$红心(♥)$>$梅花(♣)$>$方块(♦)。

举例说明：

1、$Q♦ J♦ 10♦ 9♦ 8♦ > 8♣ 8♥ 8♠ K♥ K♠$ （前者牌型为同花顺，比后者大）；

2、$9♣ 9♦ 9♠ Q♥ Q♠ > 8♣ 8♦ 8♠ K♥ K♠$ （两者牌型均为满堂红，比较牌型中三张同一点数的牌 $9$ 比 $8$ 大）；

3、$A♣ A♦ 8♥ 8♠ Q♠ > A♠ A♥ 7♥ 7♠ K♠$ （两者牌型均为两对，且最大的对子相同，此时比较次大的对子，$8$ 比 $7$ 大）；

4、$A♠ Q♠ J♥ 9♥ 8♥ > A♦ Q♦ J♠ 9♣ 8♣$ （两者牌型均为无对，所有数码均相同，此时比较最大牌的花色，$A♠$ > $A♦$）。

5、$4♠ 4♥ A♦ Q♦ 5♦ > 4♣ 4♦ A♠ Q♠ 5♠$ （两者牌型均为一对，所有数码均相同，此时对 4 为牌型里最大的部分，因此比较 $4♠ > 4♣$）

在小 Y 和小 Z 玩梭哈的过程中，小 Y 总希望能够实时了解目前的形势，即根据自己手上的牌算出自己的胜率。但是他的编程能力有限，你能帮他完成这个任务么？

inputFormat:
第一行包含 $1$ 个正整数 $N$，表示小 Y 自己手上牌的数量。

接下来 $N$ 行每行用两个整数描述一张小 Y 手上的牌：第一个数表示牌的数码（$1$ 表示 $A$，$13$ 表示 $K$，$12$ 表示 $Q$，$11$ 表示 $J$），第二个数表示牌的花色（$1$ 表示黑桃，$2$ 表示红心，$3$ 表示梅花，$4$ 表示方块）。

接下来 $N – 1$ 行每行用两个整数描述一张小 Z 手上的明牌：第一个数表示牌的数码（$1$ 表示 $A$，$13$ 表示 $K$，$12$ 表示 $Q$，$11$ 表示 $J$），第二个数表示牌的花色（$1$ 表示黑桃，$2$ 表示红心，$3$ 表示梅花，$4$ 表示方块）。

outputFormat: 输出仅包含一行，格式为 `A/B` 形式。$A$, $B$ 为两个互质的自然数，`A/B` 表示了小 Y 当前局面下的获胜可能性。特别的，若 $A$ 为 $0$，则应输出 `0/1`。

hint:
【样例说明】

小 Y 手上牌的型是 $4$ 条，小 Z 若底牌是方块 $A$ 则也能构成 $4$ 条，并通过数码大获胜 。其他情况下都是小 Y 获胜。

【数据规模和约定】

对于 $10\%$ 的数据，$N = 5$;

对于 $30\%$ 的数据，$3 \leq N \leq 5$;

对于 $100\%$ 的数据，$1 \leq N \leq 5$。


title: 孤岛营救问题

description:
$1944$ 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 $N$ 行，东西方向被划分为 $M$ 列，于是整个迷宫被划分为 $N\times M$ 个单元。每一个单元的位置可用一个有序数对(单元的行号，单元的列号)来表示。南北或东西方向相邻的 $2$ 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成$P$ 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 $(N,M)$ 单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入 $(1,1)$ 单元。另外，麦克从一个单元移动到另一个相邻单元的时间为 $1$，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

inputFormat:
第 $1$ 行有 $3$ 个整数，分别表示 $N,M,P$ 的值。

第 $2$ 行是 $1$ 个整数 $K$，表示迷宫中门和墙的总数。

第 $I+2$ 行$(1\leq I\leq K)$，有 $5$ 个整数，依次为$X_{i1},Y_{i1},X_{i2},Y_{i2},G_i$：

- 当 $G_i \geq 1$ 时，表示 $(X_{i1},Y_{i1})$ 单元与 $(X_{i2},Y_{i2})$ 单元之间有一扇第 $G_i$ 类的门

- 当 $G_i=0$ 时，表示 $(X_{i1},Y_{i1})$ 单元与 $(X_{i2},Y_{i2})$ 单元之间有一堵不可逾越的墙（其中，$|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1$，$0\leq G_i\leq P$）。

第 $K+3$ 行是一个整数 $S$，表示迷宫中存放的钥匙总数。

第 $K+3+J$  行$(1\leq J\leq S)$，有 $3$ 个整数，依次为 $X_{i1},Y_{i1},Q_i$：表示第 $J$ 把钥匙存放在 $(X_{i1},Y_{i1})$单元里，并且第 $J$ 把钥匙是用来开启第 $Q_i$ 类门的。（其中$1\leq Q_i\leq P$）。

输入数据中同一行各相邻整数之间用一个空格分隔。

outputFormat: 将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出 $-1$。

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


title: 深海机器人问题

description:
深海资源考察探险队的潜艇将到达深海的海底进行科学考察。

潜艇内有多个深海机器人。潜艇到达深海海底后，深海机器人将离开潜艇向预定目标移动。

深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。

每条预定路径上的生物标本的价值是已知的，而且生物标本只能被采集一次。

本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动，而且多个深海机器人可以在同一时间占据同一位置。

用一个 $P\times Q$ 网格表示深海机器人的可移动位置。西南角的坐标为 $(0,0)$，东北角的坐标为 $(Q,P)$ 。

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

给定每个深海机器人的出发位置和目标位置，以及每条网格边上生物标本的价值。

计算深海机器人的最优移动方案， 使深海机器人到达目的地后，采集到的生物标本的总价值最高。

inputFormat:
文件的第 $1$ 行为深海机器人的出发位置数 $a$,和目的地数 $b$ 。

第 $2$ 行为 $P$ 和 $Q$ 的值。

接下来的 $P+1$ 行,每行有 $Q$ 个正整数,表示向东移动路径上生物标本的价值,行数据依从南到北方向排列。

再接下来的 $Q+1$ 行,每行有 $P$ 个正整数,表示向北移动路径上生物标本的价值,行数据依从西到东方向排列。

接下来的 $a$ 行，每行有三个正整数 $k,x,y$,表示有 $k$ 个深海机器人从 $(y,x)$ 位置坐标出发。

再接下来的 $b$ 行，每行有三个正整数 $r,x,y$ ,表示有 $r$ 个深海机器人可选择 $(y,x)$ 位置坐标作为目的地。

outputFormat: 输出采集到的生物标本的最高总价值.

hint:
$1\leq P,Q\leq15$

$1\leq a\leq 4$

$1\leq b\leq 6$

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


title: 数字梯形问题

description:
给定一个由 $n$ 行数字组成的数字梯形如下图所示。

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

梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

分别遵守以下规则：

1. 从梯形的顶至底的 $m$ 条路径互不相交；

1. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交；

1. 从梯形的顶至底的 $m$  条路径允许在数字结点相交或边相交。

inputFormat:
第 $1$ 行中有 $2$ 个正整数 $m$ 和 $n$，分别表示数字梯形的第一行有 $m$ 个数字，共有 $n$ 行。接下来的 $n$ 行是数字梯形中各行的数字。

第 $1$ 行有 $m$ 个数字，第 $2$ 行有 $m+1$ 个数字，以此类推。

outputFormat: 将按照规则 $1$，规则 $2$，和规则 $3$ 计算出的最大数字总和并输出，每行一个最大总和。

hint: $1\leq m,n \leq 20$

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


title: 分配问题

description: 有 $n$ 件工作要分配给 $n$ 个人做。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$ 。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案，使产生的总效益最小或最大。

inputFormat:
文件的第一行有 $1$ 个正整数 $n$，表示有 $n$ 件工作要分配给 $n$ 个人做。

接下来的 $n$ 行中，每行有 $n$ 个整数 $c_{i,j}$，表示第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{i,j}$。

outputFormat: 两行分别输出最小总效益和最大总效益。

hint:
$1 \leq n \leq 50, 0 \le c _ {i, j} \le 100$。

一个人只能修一个工件。

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


title: 运输问题

description:
$W$ 公司有 $m$ 个仓库和 $n$ 个零售商店。第 $i$ 个仓库有 $a_i$ 个单位的货物；第 $j$ 个零售商店需要 $b_j$ 个单位的货物。

货物供需平衡，即$\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$。

从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用为 $c_{ij}$ 。

试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

inputFormat:
第 $1$ 行有 $2$ 个正整数 $m$ 和 $n$，分别表示仓库数和零售商店数。

接下来的一行中有 $m$ 个正整数 $a_i$，表示第 $i$ 个仓库有 $a_i$个单位的货物。

再接下来的一行中有 $n$ 个正整数 $b_j$，表示第 $j$ 个零售商店需要 $b_j$ 个单位的货物。

接下来的 $m$ 行，每行有 $n$ 个整数，表示从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用 $c_{ij}$。

outputFormat: 两行分别输出最小运输费用和最大运输费用。

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


title: 负载平衡问题

description: $G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

inputFormat:
第一行一个正整数 $n$，表示有 $n$ 个仓库。

第二行 $n$ 个正整数，表示 $n$ 个仓库的库存量。

outputFormat: 输出最少搬运量。

hint: $1 \leq n \leq 100$。

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


title: [JSOI2007] 文本生成器

description:
JSOI 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 v6 版。

该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。 也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 $s$ 包含单词 $t$，当且仅当单词 $t$ 是文章 $s$ 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？

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

inputFormat:
第一行有两个整数，分别表示使用者了解的单词总数 $n$ 和生成的文章长度 $m$。

接下来 $n$ 行，每行一个字符串 $s_i$，表示一个使用者了解的单词。

outputFormat: 输出一行一个整数表示答案对 $10^4 + 7$ 取模的结果。

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

对于全部的测试点，保证：

- $1 \leq n \leq 60$，$1 \leq m \leq 100$。
- $1 \leq |s_i| \leq 100$，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。
- $s_i$ 中只含大写英文字母。


title: [CTSC2012] 电阻网络

description:
给定一个树型电网，树中的每条边上有一个电阻$R_i$，电阻值均为10000Ω。下图为一个包含4个节点的树型电路情况：

![图1](https://i.loli.net/2018/10/03/5bb46c0c587be.png)

树中的所有叶子节点（度为1的节点称为叶子）都接地，每条线上都接地，每条线上都附有10000Ω的电阻，最终形成的电网如下图所示：

![图2](https://i.loli.net/2018/10/03/5bb46c0c72576.png)

现有如下两种操作：

`C u v w`：表示在边`<u,v>`上串联一个电源，电源的大小为$w$伏，电源位于靠近节点$u$一侧（如下图所示），电源负极指向$u$。注意同一条边上可以串联多个电源。

![图3](https://i.loli.net/2018/10/03/5bb46c0c6a122.png)

`Q u` ：表示询问点$u$当前的电压，此是指对地。

如对上图进行`C 2 4 5`操作后，网络变为：

![图4](https://i.loli.net/2018/10/03/5bb46c0c86064.png)

此时每个节点上的电压见上图的标注。

inputFormat:
输入文件 circuit.in 的第一行包含两个整数 $N,M$，分别表示树的节点数和操作个数。接下来 $N-1$ 行，每行两个数 $u,v$，表示有一条连接节点 $u,v$ 的边，这条边上恰好包含一个电阻。

接下来 $M$ 行，每行一个命令，格式见题目描述。

outputFormat: 输出文件为 circuit.out。对于每个 `Q` 命令，输出一个数表示此刻该点的电压值。你可以输出任意多位的小数，只要你的答案和标准答案相差不超过 `10^(-3)` 就算合法。

hint:
【样例说明】

对于第一个询问，由于原图中没有电源，所以没有电流，所有点的电压都相

等（否则如果有 U i >U j ，则就有 i 流向 j 的电流，与没有电源矛盾）,都等于地电

压 0V。

之后在<2,4>中加一个 5V 的电源，得到的新图见题目描述。

整理后可以发现，新图的形式是串联(电源,R 2 +10000,并联(R 1 +10000,

R 3 +10000))，由此可以得到新图的总电阻为:

R 2 +10000+1/(1/(R 3 +10000)+1/(R 1 +10000))=30000 Ω.

所以流过节点 4 的电流就是 5/30000A，所以 U 4 =5/3V。U 2 =U 4 +R 2 \*I-5=-5/3V，由

于 U 1 和 U 3 形式对称，由分压关系可知 U 1 =U 3 =U 2 \*10000/(10000+10000)=-5/6V。

【数据规模】

30%的数据保证 N,M ≤ 30

60%的数据保证 N,M ≤ 3000

100%的数据保证 3 ≤ N,M ≤ 50000，1 ≤ u,v ≤ n，1 ≤ w ≤ 10，树中最长链的长

度不超过 50。


title: [CTSC2012] 最短路

description: 给定一个节点 1 和节点 N 连通的正权无向图 G，请你删除 不超过 K 条边 ，使得节点 1 和节点 N 仍然连通的同时，且这两点之间的 最短路 尽可能 长 。

inputFormat:
### 本题为提交答案试题，[输入文件](https://pan.baidu.com/s/1o7K2dCm)shortest1.in~shortest10.in请在链接中下载。

输入文件 shortest\*.in 的第一行包含三个正整数 N，M 和 K。其中 N 表示节点数，M 表示边数，节点的编号由 1 至 N，边的编号由 1 至 M。接下来 M 行，

每行三个正整数 u，v 和 w，表示有一条连接节点 u 和节点 v 的边，权值为 w。

outputFormat:
输出文件 shortest\*.out 的第一行包含一个非负整数 T (T ≤ K)，表示需要删掉的边数。

接下来 T 行，每行一个 1 到 M 之间的整数 x，表示删掉输入中的第 x 条边。你需要保证这 T 个整数互不相同。

hint:
【样例说明】

样例中从节点 1 到 3 的最短路径长度为 1，删去第三条边之后，最短路径长度为 2。

【评分标准】

对于每个测试点，设有评分四个参数 s 1 , s 2 , s 3 , s 4 。假设你的方案的最短路为ans。

如果你没有输出，或者输出不合法，或者最短路不存在，得 0 分。

如果最短路存在，得 1 分。

如果 ans ≥ s 1 ，得 3 分。

如果 ans ≥ s 2 ，得 5 分。

如果 ans ≥ s 3 ，得 8 分。

如果 ans = s 4 ，得 10 分。

如果 ans > s 4 ，得 12 分。

取满足条件的分数中的最高得分为该测试点你的得分。

【如何测试你的输出】

首先先编译checker.cpp

在你的目录下有一个名为 checker 的程序可以用来检查你的输出，你可以在终端中使用以下命令来检查你的输出：

./checker N

其中 N 为测试点的编号，例如，要测试第 3 个测试点可以使用

./checker 3

该程序会检测你的输出方案是否合法。如果方案合法，程序还会给出该方案的最短路的长度值。

【特别提示】

请妥善保存输入文件\*.in 和你的输出\*.out，及时备份，以免误删。


title: [WC2012] 最小生成树

description:
给定无向带权连通图$G$，我们希望通过修改边的权值，使它的最小生成树唯一，已知减小，增加一条边的权值的单位代价分别为 $a$ 和 $b$，且修改后的权值必须为非负整数。

例如，对某个图$G$，如果将一条边的权值减 $3$，另一条边的仅值加 $2$ 之后，它的最小生成树唯一，则此时的代价之和是 $3a$＋$2b$。试计算代价之和的最小值。

inputFormat:
从文件mst.in中读入数据。

第一行包含字符串“$mst$” 和数据编号。

第二行包含 $4$ 个正整数 $n$,$m$,$a$,$b$，分别表示图 $G$ 顶点的个数，边的条数，以及对一条边的权值减小 $1$，增加 $1$ 的代价。

接下来 $m$ 行，每行 $3$ 个正整数 $x$,$y$,$w$，表示顶点 $x$ 和顶点 $y$ 之间有一条初始权值为 $w$ 的边。

顶点由 $1$ 至 $n$ 编号。

outputFormat:
输出到文件mst.out中。

输出文件仅一行，包含一个整数，表示最小代价，无需修改则输出 $0$。

hint:
【样例说明】

将边$(2,4)$的权值减 $1$，边$(2,3)$的权值加 $1$ 之后，图 $G$ 的最小生成树唯一，且此时的代价之和为最小值。

【数据范围】

![QQ20180115212959.png](https://www.z4a.net/images/2018/01/15/QQ20180115212959.png)

[测试点$6$~$10$下载](https://pan.baidu.com/s/1bqiS6w3)


title: 土豆田

background:
大宁在他家门口种了一大片土豆田，划分为 $n \times m$ 的地块。

大宁准备搭建学校的 OJ，为了测试土豆田的性能，大宁找到了你，为他的土豆编写代码。

description:
大宁的土豆田是以地块为单位的，每个地块里的所有土豆的集合称为一个处理单元，可以储存两个值：key（键值）和 tmp（缓存值），均为 $32$ 位带符号整数，每个单元。可以执行若干命令。大宁会骑着自行车轮流给每个处理单元供电，顺序如图，展示的是一个被分割为 $4\times 4$ 处理单元的土豆田：

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

单元的编号就是供电的顺序，每次按编号顺序从 $1$ 号到 $n\times m$ 号遍历一遍。

每一次完整的遍历称为一个周期。

只有一块地上的土豆得到供电，它们才会工作，执行命令，所有命令执行完之后大宁会停止供电。

对于每一个处理单元，命令格式如下：

1. `in` 读取一个数，存放到该单元的 $\text{tmp}$ 中。（如果 $\text{tmp}$ 中有数，那么覆盖掉，以下的所有存放均如此）

1. `out` 输出当前处理单元的 $\text{key}$ 值。

1. `swap` 交换该单元的 $\text{key}$ 和 $\text{tmp}$。

1. `add X` 给 $\text{key}$ 值加上 $X$，$X$ 只能是一个常数或者 $\text{tmp}$，下同。

1. `set X` 把 $\text{key}$ 值修改为 $X$。

1. `opp` 对 $\text{key}$ 值取相反数。

1. `rev` 对 $\text{key}$ 值按位取反。

1. `L/R X` 左/右移 $\text{key}$ 值 $X$ 位。

1. `get u/d/l/r` 将当前单元上(u)/下(d)/左(l)/右(r)面的单元的 $\text{key}$ 值并把它复制到本单元的 $\text{tmp}$，位置规则按照前面的图片所示。

1. `or/and/or X` 对 $\text{key}$ 值按位或/与/异或 $X$。

1. `wait` 在本次供电的时间中等待，即什么事情也不做。

1. `if X` 如果此时 X(只能是 $\text{key}$ 或者 $\text{tmp}$ )不等于 $0$ 则在下一次供电执行该语句的下一条语句，否则跳过下一条语句，执行下下条(如果存在的话)。

1. `goto Y`  下一次供电从第 $Y$ 号命令开始执行，$Y$ 只能是常数。

1. `end` 强制结束所有的处理单元的命令，无视所有尚未执行的命令。

我们提供了 check.exe,把你的土豆程序 potato.out 和你想测试的输入数据 potato.in 放到与 check.exe 同文件夹下，运行之后可以在 report.txt 中查看你的程序的详细运行情况。

我们还提供了另一个样例土豆程序 example2.out,使用 $2\times2$ 处理单元的土豆程序，内容为计算一个整数 $a$ 的 $10$ 倍,可以自行解读（该样例并非该计算的最优解，只是为了展示命令）。

下面展示了一个 $1 \times 3$ 的处理单元，所有单元不一定需要全部使用。

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

你有以下任务需要用编写土豆程序完成：

|编号|输入|输出|数据范围|处理单元大小限制|分数|补充说明|
| :----------: | :----------: | :----------:| :----------:| :----------:|:----------: | :----------: |
|$1$|$a\text{，}b$|$b-a$|$\lvert a\rvert \text{，}\lvert b\rvert \le10^9 $|$1 \times 3$|$7$|无|
|$2$|$a$|$233\times a$|$1 \le\lvert a\rvert \le10^7 $|$2 \times 2$|$9$|无|
|$3$|$a$|$\lvert a \rvert$|$1 \le\lvert a\rvert \le10^9 $|$2 \times 2$|$12$|求 $a$ 的绝对值|
|$4$|$128$ 个整数 $a_i$|$\sum^{128}_{i=1}a_i$|$1 \le\lvert a\rvert \le2 \times 10^6 $|$4 \times 2$|$12$|无|
|$5$|$a\text{，}b$|$\lfloor \frac{a+b}{2}\rfloor$|$\lvert a\rvert \text{，}\lvert b\rvert \le2.1\times10^9 $|$2 \times 2$|$13$|无|
|$6$|$a$|$\operatorname{popcount}(a)$|$\lvert a\rvert\le10^9 $|$2 \times 2$|$13$|$\operatorname{popcount}(a)$表示 $a$ 在二进制表示下 $1$ 的个数|
|$7$|$a\text{，}b$|$\max {(a,b)}$|$\lvert a\rvert \text{，}\lvert b\rvert \le10^9 $|$2 \times 2$|$14$|无|
|$8$|$n$|$f(n)$|$1 \le n \le 42$|$3 \times 3$|$20$|$f(n)=\begin{cases}1 & n<2\\f(n-1)+f(n-2) & n\ge 2\end{cases}$|

inputFormat: 本题为提交答案题。

outputFormat:
第一行为 $n$ 和 $m$，表示你用了 $n$ 行 $m$ 列。

接下来$n\times m$个部分，第 $i$ 个部分的第一行 $t_i$ 表示在第 $i$ 个处理单元中命令的数量(可以为 $0$)，接下来 $t_i$ 行每行描述一个命令，见上文所述。

samples:
例：一个使用1*1的土豆田处理单元(下称处理单元)的A+B problem
输入两个整数a,b,|a|,|b|<=10^9
输出a+b

1 1
5
in
swap
in
add tmp
out

samples:
解释：
第一行的1 1表示用的处理单元为1*1
第二行表示第一个处理单元有5条指令。
第三行的命令在第一个周期执行，读入了一个数(假定为a) ，此时该单元的状态为key=0,tmp=a
第四行在第二个周期执行，交换了key和tmp,状态为key=a,tmp=0
第五行在第三个周期执行，读入了另一个数b，状态为key=a,tmp=b
第六行在第四个周期执行，给key加上tmp，状态为key=a+b,tmp=b
第七行在第五个周期执行，输出该单元的key，即输出了a+b

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

这个样例实现了 A+B problem。

第一行的 `1 1` 表示用的处理单元为 $1\times1$。

第二行表示第一个处理单元有 $5$ 条指令。

第三行的命令在第一个周期执行，读入了一个数(假定为 $a$) ，此时该单元的状态为 $\text{key}= 0 \text{，}\text{tmp}= a$。

第四行在第二个周期执行，交换了 $\text{key}$ 和 $\text{tmp}$，状态为 $\text{key}= a \text{，}\text{tmp}= 0$。

第五行在第三个周期执行，读入了另一个数 $b$，状态为 $\text{key}= a \text{，}\text{tmp}= b$。

第六行在第四个周期执行，给 $\text{key}$ 加上 $\text{tmp}$，状态为 $\text{key}= a+b \text{，}\text{tmp}= b$。

第七行在第五个周期执行，输出该单元的 $\text{key}$，即输出了 $a+b$。

如果你的程序在 $2000$ 个周期内没有运行完毕，或者有语法错误，或者超过处理单元尺寸限制，得 $0$ 分。

如果你的第 $i$ 个任务的程序能得出正确的结果，并且和标准答案运行所需的周期数量相同或比其更少，得会得到该测试点的满分，否则设你的程序运行了 $a$ 个周期，标准答案运行了 $s$ 个周期，你的分数为 $\lfloor\text{该测试点分数}\times(\frac{s}{a})\times0.8 \rfloor$(注意，部分正确显示WA,但是仍然有分数)。

```cpp
P1=7
P2=9
P3=12
P4=12
P5=13
P6=13
P7=14
P8=20
```

PS:如果你构造了什么好玩的土豆程序(可以和本题目中的任务无关)，请到答疑博客下或者私信告诉我，会酌情给予奖励。

Check 下载见附件。

example2.out：

```
2 2 8 in add tmp
L 3 get r add tmp
get d add tmp
out 3 wait get l add tmp
3 wait get u add tmp
```


title: [CTSC2012] 熟悉的文章

description:
阿米巴是小强的好朋友。

在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文 “熟悉程度”的量化指标：$L_0$ .小强首先将作文转化成一个 $01$ 串。之后，小强搜集了各路名家的文章，同样分别转化成 $01$ 串后，整理出一个包含了 $M$ 个 $01$ 串的 “ 标准作文库 ”。

小强认为：如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过（即，它是标准作文库的某个串的一个 连续子串），那么它是 “ 熟悉 ” 的。对于一篇作文（一个 $01$ 串）$A$，如果能够把 $A$ 分割成若干段子串，其中 “ 熟悉 ” 的子串的长度总和不少于 $A$ 总长度的 $90\%$，那么称 $A$ 是 “ 熟悉的文章 ”。 $L_0$ 是能够让 $A$ 成为 “ 熟悉的文章 ” 的 所有 $L$ 的最大值 （如果不存在这样的 $L$，那么规定 $L_0=0$）。

举个例子：

小强的作文库里包含了如下 $2$ 个字符串：

```cpp
10110
000001110
```
有一篇待考察的作文是：

```cpp
1011001100
```
小强计算出这篇作文 $L$ 的最大值是 $4$，因为待考察的作文可以视作 $10110+0110+0$，其中 $10110$ 和 $0110$ 被判定为 “熟悉” 的。而当 $L = 5$ 或是更大的时候，不存在符合题意的分割方法。所以，这篇作文的 $L_0 = 4$。小强认为阿米巴作文的 $L_0$ 值比其他同学的明显要大。请你帮他验证一下。

inputFormat:
输入第一行是两个整数 $N, M$，表示待检查的作文数量，和小强的标准作文库的行数。

接下来是 $M$ 行的 $01$ 串，表示标准作文库。

接下来是 $N$ 行的 $01$ 串，表示 $N$ 篇作文。

outputFormat: 输出包含 $N$ 行，每一行包含一个整数，表示该篇作文的 $L_0$ 值。

hint:
对于 $30\%$ 的测试数据，输入文件的长度不超过 $1000$ 字节。

对于 $50\%$ 的测试数据，输入文件的长度不超过 $61000$ 字节。

对于 $80\%$ 的测试数据，输入文件的长度不超过 $250000$ 字节。

对于 $100\%$ 的测试数据，输入文件的长度不超过 $1100000$ 字节。


title: [CTSC2012] 极点统计

description:
对于一个由平面上点组成的集合$S$，以及一个平面上的点，以及一个平面上的点$p$，函数$f(p,S)$**当且仅当$p$在$S$的凸包内部（包括$S$的凸包的边界）**时值为$1$，其余情况下其值为$0$。

现给定两个平面上的点集$P=\{p_1,p_2,\cdots,p_N\}$和$A=\{a_1,a_2,\cdots,a_M\}$，我们称$A$中的一个点$a_i$为极点，当且仅其满足$$\sum_{j\ne i} f(a_i,P\cup \{a_j\})=0$$

也就是说，**$a_i$不在任意$A$集合中非$a_i$的点与$P$组成的凸包内部。**

请统计出集合$A$中极点的个数。

inputFormat:
第一行包含两个用空格隔开正整数$N$和$M$；

第二行包含$N$个用空格隔开的整数对，第$i$个数对 $(x_i^p,y_i^p)$表示点$p_i$的坐标；

第二行包含$M$个用空格隔开的整数对，第$j$个数对 $(x_j^a,y_j^a)$表示点$a_j$的坐标。

对于同一个集合，输入数据保证不会出现坐标相同的两个点 。

outputFormat:
仅包含一行一个整数，表示集合$A$中极点的个数。

## 说明


title: [CTSC2012] 统计学家

background:
[输入文件](https://pan.baidu.com/s/1i5laUcH)

**由于洛谷评测机限制，最后请输出所有回答的异或和。**

description:
给定一个 $N\times M$ 的整数矩阵 $\{A[i,j]\}$（$1\le i\le N$，$1\le j\le M$）。请回答 $K$ 个询问，其中第 $i$ 个询问要求统计满足下述条件的二维逆序对 $(x_1,y_1,x_2,y_2)$ 的个数：

- $u_{i,1}\le x_1\le x_2\le u_{i,2}$
- 且 $v_{i,1}\le y_1\le y_2\le v_{i,2}$
- 且 $A[x_1,y_1]>A[x_2,y_2]$

inputFormat:
本题为提交答案试题，[输入文件](https://pan.baidu.com/s/1i5laUcH) `rev1.in ~ rev10.in`。

输入文件 `rev*.in` 的第一行依次包含三个正整数 $N, M, K$。

接下来 $N$ 行，每行 $M$ 个数给出整数矩阵 $A$，其中第 $i$ 行第 $j$ 个数为 $A[i,j]$。接下来 $K$ 行，每行四个整数给出所有的询问，其中第 $i$ 行依次为 $u_{i,1}, v_{i,1}, u_{i,2}, v_{i,2}$。

outputFormat:
输出文件 `rev*.out` 的包含 $K$ 行，其中第 $i$ 行为一个整数，对应的第 $i$ 个询问的答案，即满足相应条件的二维逆序对个数。

## 说明

### 评分标准

对于每个测试点，如果你有输出，且输出结果与标准输出完全一致，则该测试点得 $10$ 分，否则该测试点得 $0$ 分。

**由于洛谷评测机限制，最后请输出所有回答的异或和。样例仅为理解题目之用，并非最后输出格式。**

hint: 请妥善保存输入文件 `*.in` 和你的输出 `*.out`，及时备份，以免误删。


title: New Product

background:
**一个经商的神奇故事……**

(善意提醒：注意时限！）

description:
LiM 有一家手工糕点店，因为糕点既实惠又好吃，于是积累了 $P$ 个常客（$P$ 为质数）。

每次这家店出 New Product（新品）的时候，都会做很多个，这 $P$ 个人都会支持，支持方法是：

**每个人买的数量都相同，而且买的总数要尽量多。**

这家店共有 $B$ 个工人，一分钟可以生产已经生产的数量的 $A$ 倍。

（注：一开始有一个已制作的 New Product 作为制作样品）

而当制作完毕，抢购（只考虑常客）完后：

**为了考虑工人们，最后要剩下正好 $B$ 个。**

下面给出已知条件，请你帮 LiM 算算最少要工作多长时间吧！

inputFormat:
共 $T+1$ 行。

第一行一个数 $T$，表示共要出 $T$ 个 New Product。

第 $2 \sim T+1$ 行，每行三个数 $P$，$A$，$B$，意义如题。

outputFormat:
对于每个 New Product：

如果可以实现（有可能不行），输出最少工作的分钟数。

如果不行，输出 `Couldn't Produce!`。

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

有 $5$ 个常客，一分钟可以生产已生产的 $2$ 倍，有 $3$ 个工人。

则最小需要 $3$ 分钟（生产 $2^3=8$ 个）才能符合要求。

#### 样例 $2$ 解释：

有 $2$ 个常客，一分钟可以生产已生产的 $2$ 倍，有 $2$ 个工人。

因为不管是多长时间都会余下 $0$ 个，所以输出 `Couldn't Produce!`。

----------------------------------------------

说明：

LiM 不是工人哦！

对于每组 New Product，常客数量不同。

对于 $20\%$ 的数据，$T=1$，所有条件 $\leqslant 100$。

对于 $100\%$ 的数据，$T \leqslant 5000$，所有条件 $\leqslant 5 \times 10^4$。$P$ 为质数。


title: [NOI2007] 货币兑换

description:
小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。

每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 A 券和 B 券的价值分别为 $A_K$ 和 $B_K$（元/单位金券）。

为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。

比例交易法分为两个方面：

a)  卖出金券：顾客提供一个 $[0, 100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP\%$ 的 A 券和 $OP\%$ 的 B 券以当时的价值兑换为人民币；

b)  买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 $K$ 天恰好为 $\mathrm{Rate}_ K$；

例如，假定接下来 $3$ 天内的 $A_K,B_K,\mathrm{Rate}_ K$ 的变化分别为：

| 时间 | $A_K$ | $B_K$ | $\mathrm{Rate}_ K$ |
| ----- | ----- | ----- | ----- |
| 第一天 | $1$ | $1$ | $1$ |
| 第二天 | $1$ | $2$ | $2$ |
| 第三天 | $2$ | $2$ | $3$ |

假定在第一天时，用户手中有 $100$ 元人民币但是没有任何金券。

用户可以执行以下的操作：

| 时间 | 用户操作 | 人民币(元) | A 券的数量 | B 券的数量 |
| ----- | ----- | ----- | ----- | ----- |
| 开户 | 无 | $100$ | $0$ | $0$ |
| 第一天 | 买入 $100$ 元 | $0$ | $50$ | $50$ |
| 第二天 | 卖出 $50\%$ | $75$ | $25$ | $25$ |
| 第二天 | 买入 $60$ 元 | $15$ | $55$ | $40$ |
| 第三天 | 卖出 $100\%$ | $205$ | $0$ | $0$ |

注意到，同一天内可以进行多次操作。

小 Y 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 A 券和 B 券的价值以及 $\mathrm{Rate}$。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。

inputFormat:
第一行两个正整数 $N,S$，分别表示小 Y 能预知的天数以及初始时拥有的钱数。

接下来 $N$ 行，第 $K$ 行三个实数 $A_K,B_K,\mathrm{Rate} _ K$ ，意义如题目中所述。

outputFormat: 只有一个实数 $\mathrm{MaxProfit}$，表示第 $N$ 天的操作结束时能够获得的最大的金钱数目。答案保留 $3$ 位小数。

hint:
| 时间 | 用户操作 | 人民币(元) | A 券的数量 | B 券的数量 |
| ----- | ----- | ----- | ----- | ----- |
| 开户 | 无 | $100$ | $0$ | $0$ |
| 第一天 | 买入 $100$ 元 | $0$ | $50$ | $50$ |
| 第二天 | 卖出 $100\%$ | $150$ | $0$ | $0$ |
| 第二天 | 买入 $150$ 元 | $0$ | $75$ | $37.5$ |
| 第三天 | 卖出 $100\%$ | $225$ | $0$ | $0$ |

本题没有部分分，你的程序的输出只有和标准答案相差不超过 $0.001$ 时，才能获得该测试点的满分，否则不得分。

测试数据设计使得精度误差不会超过 $10^{-7}$ 。

对于 $40\%$ 的测试数据，满足 $N \le 10$。

对于 $60\%$ 的测试数据，满足 $N \le 1 000$。

对于 $100\%$ 的测试数据，满足 $N \le 10^5$。

对于 $100\%$ 的测试数据，满足：

$0 < A_K \leq 10$，$0 < B_K\le 10$，$0 < \mathrm{Rate}_K \le 100$，$\mathrm{MaxProfit}  \leq 10^9$。

输入文件可能很大，请采用快速的读入方式。

必然存在一种最优的买卖方案满足：

每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。


title: 山区建小学

description: 政府在某山区修建了一条道路，恰好穿越总共 $n$ 个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为 $d_i$（$d_i$ 为正整数），其中，$0<i<n$。为了提高山区的文化素质，政府又决定从 $n$ 个村中选择 $m$ 个村建小学。请根据给定的 $n$、$m$ 以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

inputFormat:
第一行为 $n$ 和 $m$，其间用空格间隔。

第二行为 $n-1$ 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。

例如

```
10 3
2 4 6 5 2 4 3 1 3
```

表示在 $10$ 个村庄中建 $3$ 所学校。第 $1$ 个村庄与第 $2$ 个村庄距离为 $2$，第 $2$ 个村庄与第 $3$ 个村庄距离为 $4$，第 $3$ 个村庄与第 $4$ 个村庄距离为 $6$，...，第 $9$ 个村庄到第 $10$ 个村庄的距离为 $3$。

outputFormat: 各村庄到最近学校的距离之和的最小值。


title: [Code+#2] 化学狂暴

background:
在那遥远的钦钦草原，住着 Yazid 和 YJQQQAQ，他们都是炼金术士。

一般而言，题目背景总是没有用的，但这道题是个例外。在这里，我们将严谨地介绍钦钦草原世界化学学科的一些基本知识。如果你对这些内容感到枯燥乏味，你也可以跳过这个部分，直接阅读题目描述中的简述并结合样例来帮助你更快地理解题目。

钦钦草原的世界里共有 $26$ 种元素，分别用大写字母A至Z表示。

钦钦草原世界中的物质由元素构成，对于任意的物质，每种元素的出现次数都是非负整数，且至少有 $1$ 种物质的出现次数为正整数，我们把每种元素在物质中的出现次数称作该元素在该物质中的下标。我们可以按A到Z的顺序写下每种元素及其下标来描述一个物质。这是一个例子：`A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0`。这个例子描述了一种 J、Q 各出现 $1$ 次，Y 出现 $2$ 次的物质。

然而，这种描述方法实在是太麻烦了，于是钦钦草原世界中的炼金术士们便尝试简化物质的描述。对于某种物质，我们定义“虚无元素”表示在该物质中下标为 $0$ 的元素，“单一元素”表示在该物质中下标为 $1$ 的元素。针对这两个定义，炼金术士们提出了两种化简方式：

省略“虚无元素”：将“虚无元素”的字母和下标省略。如上面的物质可以通过该操作化简为：`J1Q1Y2`。

省略“单一元素”的下标：将“单一元素”的下标省略。如上面的物质可以通过该操作化简为：`A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0`。

特别地，对于同时省略了“虚无元素”和“单一元素”下标的表示，我们把它叫做该物质的“最简式”。如上面物质的“最简式”即为：`JQY2`。

由于钦钦草原世界的化学研究仍处于起步阶段，因此对于任意的物质，所有元素下标均为不超过 $9$ 的非负整数。

化学方程式是描述化学反应的式子。一个化学方程式包含恰好一个等号（=），等号两边是由加号（+）连接的若干物质。形象地说，它的形式是这样的：

```
物质+物质+…+物质=物质+物质+…+物质
```
除了需要满足上述格式外，元素守恒也是不可忽视的。这表示等号两边所有元素在各物质中的出现次数总和必须相等。比如，这就是一个合法的（格式正确、元素守恒的）化学方程式：

```
JQY2+J2=J3QY2
```
需要特别注意的是，在化学方程式的书写中，未被化至“最简式”的元素也是可以被接受的。例如，下面的化学方程式也是合法的：

```
JQY2+J2=JQY
```
而下面这个化学方程式就不是合法的了，因为它并没有满足元素守恒。

```
JQY2+J2=JQY
```
钦钦草原化学学科的基本知识就介绍到这。祝各位选手武运昌隆！

description:
所谓化学方程式，即是用加号（+）和等号（=）连接一些化学物质的式子。保证一个化学方程式中含有恰好一个等号（=）。化学物质由一些元素（用大写字母A至Z表示）加上下标（保证下标为不超过 $9$ 的非负整数）连接而成的。例如：`JQY2`、`A0J1QY2` 等。书写时需要保证字典序越小的字母排在越前面。

需要注意的是，像 `A0J1QY2` 这样的物质书写同样是合法的，虽然事实上它和 `JQY2` 是等价的。我们把下标为 $1$ 的元素称为“单一元素”，把下标为 $0$ 的元素称为“虚无元素”。在书写一种物质时，我们既可以省去“单一元素”的下标，又可以直接省去“虚无元素”。特别地，我们把用这两种规则省略至最简的书写称为该物质的“最简式”。例如，`JQY2` 就是 `A0J1Q1Y2` 的最简式。

既然称之为“方程式”，元素守恒就是必须的了。对于一个化学方程式，元素守恒指的是指等号两边所有元素的下标之和相等。比如，这个化学方程式就是元素守恒的：

```
JQY2+J2=J3QY2
```
而这个化学方程式就是不合法的，因为它不满足元素守恒：

```
JQY2+J2=JQY
```
作为一名资深炼金术士，Yazid 自然是整日沉迷在化学狂暴中。某一天，Yazid 写下了 $n$ 个化学方程式，并把它们放在一边，为后续的研究做着准备。

然而，见习炼金术士 YJQQQAQ 不慎打翻了一瓶绿色的试剂，导致 Yazid 写下的所有化学方程式中，都有恰好 $1$ 个物质被绿色液体弄得模糊不清了。

暴怒的 Yazid 狠狠地把 YJQQQAQ 批判了一番，并要求他将所有模糊不清的物质重新写出来。除此之外，作为惩罚，无论原来 Yazid 如何书写这些物质，YJQQQAQ 都必须将它们以“最简式”的形式写出。

如果不能完成这些任务，Yazid 就会把他从钦钦草原放逐。面对这么多的化学方程式，弱小、无助的 YJQQQAQ 手足无措，于是他找到了钦钦草原最擅长编程的你，请你帮他完成任务。

inputFormat:
从标准输入读入数据。

第一行 $2$ 个整数 $n,m$，分别表示化学方程式的数目和Yazid的书写习惯。其中，书写习惯 $m$ 是 $0$ 到 $3$ 之间的整数，对于不同的 $m$，Yazid 书写物质的方式不同（这一信息可能对你解决部分测试点有帮助）：

如果 $m=0$，则 Yazid 在书写方程式时一定会将所有物质化为“最简式”；

如果 $m=1$，则 Yazid 在书写方程式时一定会将所有物质的“虚无元素”省略，且不会存在“单一元素”的下标被省略；

如果 $m=2$，则 Yazid 在书写方程式时一定会将所有物质“单一元素”的下标省略，且不会存在“虚无元素”被省略；

如果 $m=3$，则 Yazid 在书写方程式时一定不会省略“单一元素”的下标，也一定不会省略“虚无元素”。

接下来 $n$ 行，每行一个字符串，描述一个被污染的化学方程式。其中，被污染的物质用?表示，保证对于每一个方程式都会存在恰好 $1$ 个?。

数据保证化学方程式严格按照题目背景和题目描述中的格式，且不存在多余的空格或其他字符。

outputFormat:
输出到标准输出。

输出 $n$ 行，每行一个字符串，表示化为“最简式”的?所表示的物质。特别地，对于无解的情况（即?表示的物质超出钦钦草原世界化学学科的研究范围），请输出 `No Solution`。

hint:
|测试点编号|m|?在方程式最左端|等号左边不含+|等号右边不含+|
|:-:|:-:|:-:|:-:|:-:|
|1|0|Yes|Yes|Yes|
|2|1|Yes|Yes|Yes|
|3|2|Yes|Yes|Yes|
|4|3|Yes|Yes|Yes|
|5|0|Yes|Yes||
|6|1|Yes|Yes||
|7|2|Yes|Yes||
|8|3|Yes|Yes||
|9|0|Yes||Yes|
|10|1|Yes||Yes|
|11|2|Yes||Yes|
|12|3|Yes||Yes|
|13|0||||
|14|1||||
|15|2||||
|16|3||||
|17|0||||
|18|1||||
|19|2||||
|20|3|||

如表格中“?在方程式的最左端”为 `Yes`，则表示该测试点保证每个字符串的第一个字符均为?；否则无特殊保证。

如表格中“等号左边不含+”为 `Yes`，则表示该测试点保证等号左边没有加号（+），即等号左边只有一种物质；否则无特殊保证。

如表格中“等号右边不含+”为 `Yes`，则表示该测试点保证等号右边没有加号（+），即等号右边只有一种物质；否则无特殊保证。

对于所有的测试点，保证 $n\leq 100$，保证每个方程式中等式两边的加号+都不超过 $5$ 个，这也意味着每行字符串（每个化学方程式）的长度不超过 $635$。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/王聿中 命题/王聿中 验题/陈宇

Git Repo：[https://git.thusaac.org/publish/CodePlus201712](https://git.thusaac.org/publish/CodePlus201712)

感谢腾讯公司对此次比赛的支持。

感谢 @[ChampionCyan](https://www.luogu.com.cn/user/1036180) 提供了修复后的题面。


title: [Code+#2] 可做题1

background:
“codeplus比赛的时候在做什么？有没有空？能来解决停机问题吗？”qmqmqm这样问sublinekelzrip。

当然，sublinekelzrip并不会停机问题，所以qmqmqm改为提出了另一个题目，现在请你帮助sublinekelzrip解决这个题目。

description:
这个问题是这样的：

对于任何一个$n$阶方阵，若任意从其中选择$n$个不同行不同列的位置，其上的权值之和均相等，则我们称这个矩阵是巧妙的。注意对于$n=1$的任何矩阵都是巧妙的。 例如矩阵：

```cpp
1 2 3
4 5 6
7 8 9
```
是巧妙的，因为$1+5+9=1+6+8=2+4+9=2+6+7=3+5+7=3+4+8=15$。

而矩阵：

```cpp
1 2
2 1
```
不巧妙，因为$1+1 \neq 2+2$。

现在有一个$n \times m$大小的矩阵$M$以及$T$个询问，每次询问其一个子方阵是否是巧妙的。

inputFormat:
从标准输入读入数据。

输入第一行包含三个正整数$n,m,T$。

之后$n$行每行$m$个空格分割的非负整数，表示矩阵$M$。

之后$T$行每行$3$个正整数$x,y,k$,表示询问第$x$行第$y$列为左上角的$k$阶方阵是否是巧妙的。保证这个矩阵完全位于$M$之中。

outputFormat:
输出到标准输出。

输出包含$T$行每行一个字符Y或者N。Y表示被询问的方阵是巧妙的，N表示不是。

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

对于所有的数据，$0 \leq M_{ij} \leq 10^9$，$1 \leq x \leq n$，$1 \leq y \leq m$。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/卢政荣 命题/卢政荣 验题/吕时清，王聿中

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。


title: [Code+#2] 可做题2

background:
“codeplus比赛的时候在做什么？有没有空？能来解决丢番图方程问题吗？”sublinekelzrip这样问qmqmqm。

当然，qmqmqm并不会丢番图方程问题，所以sublinekelzrip改为提出了另一个题目，现在请你帮助qmqmqm解决这个题目。

description:
这个问题是这样的：

若一个数列$a$满足条件$a_n=a_{n-1}+a_{n-2}$,$n \geq 3$,而$a_1,a_2$为任意实数，则我们称这个数列为广义斐波那契数列。

现在请你求出满足条件$a_1=i$，$a_2$为区间$[l,r]$中的整数，且$a_k mod p = m$的广义斐波那契数列有多少个。

inputFormat:
从标准输入读入数据。

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

一行六个用空格隔开的整数$i,l,r,k,p,m$，意义如「题目描述」所示。

outputFormat:
输出到标准输出。

输出共$T$行，每行一个数表示该组数据的答案。

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

对于所有数据，$0 \leq l \leq r$,$1 \leq p \leq 10^9$,$0 \leq m < p$,$T=10$,$0 \leq i \leq 10^{18},k \geq 3$。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/卢政荣 命题/卢政荣 验题/吕时清，茹逸中，王聿中

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。


title: [Code+#2] 火锅盛宴

background: SkyDec 和 YJQQQAQ 都是 Yazid 的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。

description:
在这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和 $n$ 种食物，每种食物数量都是无限的。我们用 $1$ 至 $n$ 将这些食材编号。

每种食物煮熟所需要的时间不同，第 $i$ 种食物煮熟需要 $s_i$ 单位时间。这表示如果你在第 $T$ 个时刻将一个食物 $i$ 下到火锅里，那么它会在第 $T+s_i$ 个时刻被煮熟，并且此后一直会延续被煮熟的状态，直到它被拿走为止。

Yazid 和 YJQQQAQ 的口味不同：YJQQQAQ 觉得所有食物的好吃程度都是相同的；而 Yazid 则觉得没有两种食材的好吃程度是相同的，并且，巧合的是，编号越小的食物 Yazid 越喜欢吃。可怜的 SkyDec 由于不能吃辣，所以只能帮 Yazid 和 YJQQQAQ 煮食物。

整个火锅盛宴持续 $10^9$ 单位时间。在整个盛宴中，三位好朋友除了谈笑风生之外，最重要的事当然就是吃东西了。在任意整数时刻，都有可能发生下列 $4$ 种事件中的任意一种，我们用 $0$ 至 $3$ 之间的整数 $op$ 描述事件类型：

- $0\ id$：表示 SkyDec 往火锅里下了一个编号为 $id$ 的食物。
- $1$：Yazid 在锅内搜寻熟了的且最喜欢吃的食物，并拿走一个这种食物。特别地，如果锅里没有熟了的食物，那么 Yazid 会很愤怒。
- $2\ id$：YJQQQAQ 在锅内搜寻编号为 $id$ 的食物：
   - 如果锅里不存在该种食物，则 YJQQQAQ 会很愤怒；
   - 如果锅里存在熟了的该食物，则 YJQQQAQ 会取走一个并食用；
   - 如果锅里只有未煮熟的该种食物，那么 YJQQQAQ 会希望知道最接近煮熟的该种食物（即锅内存在时间最长的该种食物）还需要多少时间被煮熟。
- $3\ l\ r$：馋涎欲滴的 SkyDec 想知道，锅里编号在 $[l,r]$ 之间的且熟了的食物总共有多少个。

inputFormat:
从标准输入读入数据。

本题包含多组数据，输入的第一行为一个正整数 $T$，表示数据组数。接下来依次描述每组数据，对于每组数据：

第一行一个正整数 $n$，表示食物的种类数。

第二行 $n$ 个用空格隔开的正整数 $s_1,s_2,\cdots, s_n$，描述每种食物煮熟需要的时间。

第三行一个正整数 $Q$，表示事件的数目。

接下来 $Q$ 行，每行若干个用空格隔开的非负整数，描述一个事件。先是两个整数 $t,op$，分别表示发生事件的时间以及事件的类型。

- 如果 $op=0$ 或 $op=2$，则接下来 $1$ 个正整数 $id$，意义见题目描述；
- 如果 $op=1$，则接下来没有其他数；
- 如果 $op=3$，则接下来 $2$ 个正整数 $l,r$，意义见题目描述。

数据保证 $t$ 按输入顺序严格递增。

outputFormat:
对于每个 $op\neq 0$ 的操作，输出一行表示答案。对于不同的 $op$，需要输出的内容如下：

- 对于 $op=1$，如果 Yazid 成功取走食物，则输出他取走食物的编号；否则输出 $\text{``\texttt{Yazid is angry.}''}\!\!$（不含引号，下同）。
- 对于 $op=2$，如果 YJQQQAQ 成功取走食物，则输出 $\!\!\text{``\texttt{Succeeded!}''}\!\!$；否则，如果锅里有未煮熟的该类食物，输出最接近煮熟的该种食物还需要多少时间被煮熟；否则，输出 $\!\!\text{``\texttt{YJQQQAQ is angry.}''}\!$。
- 对于 $op=3$，输出锅内编号在指定范围内的熟食的数量。

samples:
Succeeded!
97
YJQQQAQ is angry.
2
1
2
Yazid is angry.

hint:
对于所有数据，保证$ T\leq 4$，保证 $n\leq 100,000$，$Q\leq 500,000$，$1\leq s_i\leq 10^8$，$1\leq t\leq 10^9$，$op\in\{0, 1, 2, 3\}$，$1\leq id\leq n$，$1\leq l\leq r\leq n$。数据保证 $t$ 按输入顺序严格递增。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/王聿中 命题/王聿中 验题/吕时清，杨景钦

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。


title: [Code+#2] 白金元首与独舞

background:
```cpp
到河北省 见斯大林 / 在月光下 你的背影 / 让我们一起跳舞吧
```
うそだよ~ 河北省怎么可能有 Stalin。

可是…… 可是如果 Stalin 把自己当作炸弹扔到地堡花园里来了呢？

怀揣着这份小小的希望，元首 Adolf 独自走进了花园。终有一天会重逢的吧，Stalin。或许是在此处，或许是在遥远的彼方。

无论如何，在此之前，好好装点一番花园，编排一段优美的舞步吧！

description:
元首把花园分为 $n$ 行 $m$ 列的网格。每个格子中都可以放置一个标识，指向上、下、左、右四个方向中的任意一个。元首位于一个格子时，会按照其中标识所指的方向进入周围的格子，或者走出花园（即目的格子不在网格之内）。举个例子 —— 对于下面的放置方式，元首从第 $3$ 行第 $2$ 列的格子开始，会沿着以红色标出的路径走出花园；从第 $2$ 行第 22 列的格子开始，则会在以蓝色标出的环路内不断地行走。

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

元首已经设计好了大部分格子的标识。元首用字符 L、R、U、D 分别表示指向左、右、上、下四个方向的标识，用字符 . 表示未决定的格子。现在，元首希望将每个 . 替换为 L、R、U、D 中任意一种，使得从花园中的任意一个格子出发，按照上述规则行走，都可以最终走出花园。

你需要编写程序帮助元首计算替换的不同方案数。两个方案不同当且仅当存在一个格子，使得两个方案中该格子内的标识不同。当然，由于答案可能很大，只需给出方案数除以 $10^9 + 7$所得的余数即可。

inputFormat:
从标准输入读入数据。

输入的第一行包含一个正整数 $T$ —— 测试数据的组数。接下来包含 $T$ 组测试数据，格式如下，测试数据间没有空行。

第 $1$ 行：两个空格分隔的正整数 $n$、$m$ —— 依次表示花园被分成的行数和列数。

接下来 $n$ 行：每行一个长度为 $m$ 的由字符 L、R、U、D 和 . 组成的字符串 —— 表示花园内已经确定的格子状态。

outputFormat:
输出到标准输出。

对于每组测试数据输出一行 —— 满足条件的方案数除以 $10^9 + 7 $所得的余数。

samples:
5
3 9
LLRRUDUUU
LLR.UDUUU
LLRRUDUUU
4 4
LLRR
L.LL
RR.R
LLRR
4 3
LRD
LUL
DLU
RDL
1 2
LR
2 2
..
..

hint:
**样例解释**

第 $1$ 组数据中，将惟一的 . 替换成 R、U 或 D 均满足要求。

第 $2$ 组数据中，将左上方和右下方的两个 . 分别替换成 LR、LU、LD、UR、UU、UD、DR 或 DD 均满足要求。

第 $3$ 组数据中，没有待决定的格子，原本的安排会使得元首陷入无尽的环路，故答案为 $0$。该组数据与**题目描述**中的例子相同。

第 $4$ 组数据中，也没有待决定的格子，但原本的安排已经满足要求，故答案为 $1$。

令 $k$ 表示标记未确定（即包含 “.”）的格子总数。

对于所有数据，有 $1 \leq T \leq 10$，$1 \leq n, m \leq 200$，$0 \leq k \leq \min(nm, 300)$。

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

“... wie Stalin!”

题面与史实无关。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/吕时清 命题/吕时清 验题/王聿中，杨景钦

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。


title: [Code+#2] 寄蒜几盒

background:
R姓出题人：第一次出CodePlus月赛，好紧脏，怎么才能装作经常出CodePlus月赛的样子？

某W姓出题人：写题面记得要加背景。

R姓出题人：可是我的题目没有什么背景可以写，怎么办？

某W姓出题人：其实背景和题面没有关系也是可以的。

R姓出题人：原来如此，那我知道了。

description:
在二维平面上有$n$条直线，这些直线会将平面划分成若干个区域。给定$m$个点，求每个点所在的区域的面积。

聪明的读者会发现有些点所在的区域面积是无穷大的。R姓出题人早就想到了这一点，所以他给出了一个实数$L$，由额外的四条直线$x=L,x=-L,y=L,y=-L$框定了一个有限的平面区域，并且所有的询问点都在这个框定的平面区域内部。

聪明绝顶的读者会发现如果询问点恰好落在某条直线上或者离某条直线的距离非常近，那么精度误差会严重影响答案。R姓出题人早就想到了这一点，所以在他造的数据中，任意一个询问点距离任意一条直线的距离大于$10^{-7}$。

inputFormat:
从标准输入读入数据。

第一行两个正整数$n,m$和一个正实数$L$。

接下来$n$行每行三个实数$A,B,C$，表示这条直线的方程为$Ax+By+C=0$

接下来$m$行，第$i$行两个实数$x_i,y_i$，表示第$i$个点的坐标。

outputFormat:
输出到标准输出。

输出$m$行，每行一个实数，第iii行输出的实数表示第$i$个点所在的区域的面积。保留两位小数。

hint:
对于$20\%$的数据，$n,m \le 10$。

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

对于$100\%$的数据，$n \le 500,m \le 100000$。

对于$100\%$的数据，输入数据的绝对值$ \le 10^7$，且输入数据最多保留两位小数。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/茹逸中 命题/茹逸中 验题/陈宇，王聿中

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。


title: [JSOI2008] 球形空间产生器

description: 有一个球形空间产生器能够在 $n$ 维空间中产生一个坚硬的球体。现在，你被困在了这个 $n$ 维球体中，你只知道球面上 $n+1$ 个点的坐标，你需要以最快的速度确定这个 $n$ 维球体的球心坐标，以便于摧毁这个球形空间产生器。

inputFormat: 第一行是一个整数 $n$ $(1\le N\le 10)$。接下来的 $n+1$ 行，每行有 $n$ 个实数，表示球面上一点的 $n$ 维坐标。每一个实数精确到小数点后 $6$ 位，且其绝对值都不超过 $20000$。

outputFormat: 有且只有一行，依次给出球心的 $n$ 维坐标（ $n$ 个实数），两个实数之间用一个空格隔开。每个实数精确到小数点后 $3$ 位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。

hint:
提示：给出两个定义：

1. 球心：到球面上任意一点距离都相等的点。
2. 距离：设两个 $n$ 维空间上的点 $A,B$ 的坐标为 $(a_1, a_2, \cdots , a_n), (b_1, b_2, \cdots , b_n)$，则 $A,B$ 的距离定义为：$dist = \sqrt{ (a_1-b_1)^2 + (a_2-b_2)^2 + \cdots + (a_n-b_n)^2 }$。


title: [JSOI2008] 火星人

description:
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。

比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：
```
序号 1 2 3 4 5 6 7 8 9 10 11
字符 m a d a m i m a d a m
```
现在，火星人定义了一个函数 $LCQ(x, y)$，表示：该字符串中第 $x$ 个字符开始的字串，与该字符串中第 $y$ 个字符开始的字串，两个字串的公共前缀的长度。比方说，$LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0$

在研究 $LCQ$ 函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出 $LCQ$ 函数的值；同样，如果求出了 $LCQ$ 函数的值，也可以很快地将该字符串的后缀排好序。

尽管火星人聪明地找到了求取 $LCQ$ 函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取 $LCQ$ 函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取 $LCQ$ 函数的值。

inputFormat:
第一行给出初始的字符串。第二行是一个非负整数 $M$ ，表示操作的个数。接下来的M行，每行描述一个操作。操作有 $3$ 种，如下所示

1. 询问。语法：$Q$ $x$ $y$ ，$x$ ,$y$ 均为正整数。功能：计算 $LCQ(x,y)$ 限制：$1$ $\leq$ $x$ , $y$ $\leq$ 当前字符串长度 。
2. 修改。语法：$R$ $x$ $d$，$x$ 是正整数，$d$ 是字符。功能：将字符串中第 $x$ 个数修改为字符 $d$ 。限制：$x$ 不超过当前字符串长度。
3. 插入：语法：$I$ $x$ $d$ ，$x$ 是非负整数，$d$ 是字符。功能：在字符串第 $x$ 个字符之后插入字符 $d$ ，如果 $x=0$，则在字符串开头插入。限制：$x$ 不超过当前字符串长度

outputFormat: 对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。

samples:
madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

hint:
1. 所有字符串自始至终都只有小写字母构成。
2. $M\leq150,000$
3. 字符串长度L自始至终都满足$L\leq100,000$
4. 询问操作的个数不超过 $10,000$ 个。

对于第 $1$，$2$ 个数据，字符串长度自始至终都不超过 $1,000$
对于第 $3$，$4$，$5$ 个数据，没有插入操作。

2024/07/40 更新一组 hack。


title: [NOI2007] 调兵遣将

background:
下发文件：
链接：https://pan.baidu.com/s/1JlHZ72eFapfEyqjL_uphoA
提取码：7v4i

由于上传答案文件有大小限制，请尽量使用代码提交= =。

description:
我军截获的情报显示，敌军正在集结兵力试图向我军重要的军械研究所发起进攻。由于我军正处于多线作战的状态，无法抽调大批兵力前去支援，指挥部决定通过有效的战前部署来提高胜率，减少伤亡和损失。

该军械研究所的平面图可以看作是一个 $N\times M$ 的矩阵，每个$1\times 1$ 的格子都表示一个区域，每个区域只与它上下左右的四个区域相邻。每个区域的用途可分为以下3 种之一：

1． 该区域被用于军事研究（用字母 `O` 表示）；

2． 该区域内驻扎有一个机械化中队（用 `#` 表示）；

3． 该区域是空地（用`.`表示）。

由于空间有限，任一个 $1\times 1$ 的格子内都无法驻扎两队以上的机械化中队（包括两队），否则会大大降低战斗时的机动性。

遗憾的是，由于战前估计不足，我军的防御部署显得十分分散，这很容易让敌军所擅长的偷袭战术得逞。为了确保万无一失，我军决定利用为数不多的防御部队以最少的移动步骤将所有重要研究区域都包围起来。所谓的“包围”即从该矩阵边界侵入的敌军找不到任意一条路，使得他们不遭受任何机械化中队的反抗就能到达某研究区域。

由于军队内部的传令权限的限制，每个单位时间指挥部只能向所有中队中的一个中队下达指令（朝上/下/左/右移动 $1$ 格）。由于时间紧迫，指挥部希望能够尽快完成部署，这个任务就交给你来完成。

注意：在部署的过程中军队可以进入研究区域，而在最终的部署结果中军队不可以在研究区域中。另外，在任何时刻，两个军队都不可以在同一个方格中。

inputFormat:
该题为提交答案型题目。

对于每个数据：

第一行 $2$ 个整数 $N$,$M$，接下来 $N$ 行，每行包括 $M$ 个字符（`.`, `O`或 `#`）。

outputFormat:
每个输出文件的第一行，包括你的答案所花费的时间 $T$。

接下来 $T$ 行，按顺序输出每条命令，每行包括 $4$ 个整数 $x1, y1, x2, y2$，表示将位于 $(x1,y1)$ 的部队移向 $(x2,y2)$。

hint:
如果选手的输出方案不合法（方案执行过程中出现军队重叠，军队移出矩形边界，最终方案有军队和研究所在同一区域，军队没有包围研究所等），则得零分，否则设选手输出的方案耗时为ans ，则得分按如下计算：

$$score=
\begin{cases}
\ 10&ans \leq A_i\\
\ 1+\left\lfloor\dfrac{ans-B_i}{A_i-B_i}\right\rfloor \times 9&A_i<ans \leq B_i\\
\ 1&B_i<ans\\
\end{cases}
$$

对于每个数据，都有两个评分参数 $A_i$ 与 $B_i$，其中保证 $A_i<B_i$。


title: [JSOI2007] 麻将

description:
麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东、南、西、北、中、发、白七种）和序数牌（分为条子、饼子、万子三种花色，每种花色各有一到九的九种牌），每种牌各四张。

在麻将中，通常情况下一组和了的牌（即完成的牌）由十四张牌组成。十四张牌中的两张组成对子（即完全相同的两张牌），剩余的十二张组成三张一组的四组，每一组须为顺子（即同花色且序数相连的序数牌，例如条子的三、四、五）或者是刻子（即完全相同的三张牌）。一组听牌的牌是指一组十三张牌，且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。

在这里，我们考虑一种特殊的麻将。在这种特殊的麻将里，没有字牌，花色也只有一种。但是，序数不被限制在一到九的范围内，而是在1到n的范围内。同时，也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成，其中两张组成对子，其余3m张组成三张一组的m组，每组须为顺子或刻子。现给出一组3m + 1张的牌，要求判断该组牌是否为听牌（即还差一张就可以和牌）。如果是的话，输出所有可能的等待牌。

inputFormat: 包含两行。第一行包含两个由空格隔开整数n, m (9<=n<=400, 4<=m<=1000)。第二行包含3m + 1个由空格隔开整数，每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。

outputFormat: 输出为一行。如果该组牌为听牌，则输出所有的可能的等待牌的序数，数字之间用一个空格隔开。所有的序数必须按从小到大的顺序输出。如果该组牌不是听牌，则输出"NO"。


title: [JSOI2008] 魔兽地图

description:
DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。

DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。

比如，Sange and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无限制地合成某些性价比很高的装备。

现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗？他会教你魔法Haunt（幽灵附体）作为回报的。

inputFormat:
第一行包含两个整数，N (1 <= n <= 51) 和 m (0 <= m <= 2,000)。分别表示装备的种类数和金币数。装备用1到N的整数编号。

接下来的N行，按照装备1到装备n的顺序，每行描述一种装备。

每一行的第一个非负整数表示这个装备贡献的力量值。

接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备。如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。如果是高级装备，后面紧跟着一个正整数C，表示这个高级装备需要C种低级装备。后面的2C个数，依次描述某个低级装备的种类和需要的个数。

outputFormat: 第一行包含一个整数S，表示最多可以提升多少点力量值。


title: [JSOI2009] 密码

description:
众所周知，密码在信息领域起到了不可估量的作用。对于普通的登陆口令以，唯一的破解方法就是暴力破解——逐个尝试所有可能的字母组合，但这是一项很耗时又容易被发现的工作。所以，为了获取对方的登陆口令，在暴力破解密码之前，必须先做大量的准备工作。经过情报的搜集，现在得到了若干有用信息，形如：

>      “我观察到，密码中含有字符串*。”

例如，对于一个 $10$ 位的密码以及观察到的字符串 `hello` 与 `world`，可能的密码组合为 `helloworld`与 `worldhello`；而对于 $6$ 位的密码以及到的字符串 `good` 与 `day`,可能的密码组合为 `gooday`。

有了这些信息，就能够大大地减少尝试的次数了。请编一个程序，计算所有密码组合的可能。密码中仅可能包含 `a-z` 之间的小写字母。

inputFormat:
输入数据首先输入两个整数 $L,N$，分别表示密码的长度与观察到子串的个数。

接下来 $N$ 行，每行若干个字符，描述了每个观察到的字符串。

outputFormat:
输出数据第一行为一个整数，代表了满足所有观察条件字符串的总数。

若这个数字小于等于 $42$，则按字典顺序输出所有密码的可能情况，每行一个，否则，只输出满足所有观察条件字符串的总数即可。

hint: 对于 $100\%$ 的数据，$1\leq L\leq 25,1\leq N\leq 10$，每个观察到的字符串长不超过 $10$，并且保证输出结果小于 $2^{63}$。


title: [JSOI2010] 旅行

description:
2009 的新年即将到来，JSK 决定开车去拜访他小镇上的所有朋友，由于他在每一个街道都有一个朋友，他开始考虑如何使旅程尽可能地短。很快他意识到最短的方法就是经过所有的街道一次且仅一次。很自然地，他希望能在旅行结束时回到开始的地方，即他父母的房子。

JSK 计划他的环城旅行：城镇的街道编号为 $1\sim n$，交汇点编号为 $1\sim m$ ，没有哪个交汇点连接了多于 $44$ 个街道。所有的交汇点有着不同的数字编号。

每个街道恰好联接着两个交汇点，任两个街道的数字编号不同。如果存在一个以上满足条件的旅行路径，则按旅行经过的街道顺序排列街道编号，选择其字典序最小的那一个路径。

由于 JSK 连一条这样的街道都无法找到，只有请你帮他写一个程序来找这样最短的旅行路径。如果不存在这样的路径则打印出一条信息。假定 JSK 住在和街道 $1$ 相连的编号较小的那个交汇点。

城镇中每一个街道都是相同的（不是死胡同），任两个街道之间有路可以达到。这些街道很窄因此一旦车进了一条路它不可能调头回走。

inputFormat: 每一行包括三个整数 $x,y,z$，若 $x>0$，$y>0$ 表示与编号为 $z$ 的街道相连的交汇点编号。如果 $x=0$，$y=0$ 则标志输入结束。

outputFormat: 输出文件共一行，描述了 JSK 的环城旅行（街道号的序列，由空格隔开）。如果没有发现满足条件的环城路线。则该行给出信息：`Round trip does not exist`。

hint:
【数据范围】
$1\le n \le 1994$，$1\le m \le 43$。


title: [SDOI2016] 储能表

description:
有一个 $n$ 行 $m$ 列的表格，**行从 $0$ 到 $n-1$ 编号，列从 $0$ 到 $m-1$ 编号**。每个格子都储存着能量。最初，第 $i$ 行第 $j$ 列的格子储存着 $(i \oplus j)$ 点能量（$\oplus$ 表示**按位异或**）。所以，整个表格储存的总能量是

$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} i \oplus j$$

随着时间的推移，格子中的能量会渐渐减少。每经过一个时间单位，每个格子中的能量都会减少 $1$。显然，**一个格子的能量减少到 $0$ 之后就不会再减少了。**

也就是说，$k$ 个时间单位后，整个表格储存的总能量是

$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \max((i \oplus j)-k,0)$$

给出一个表格，求 $k$ 个时间单位后它储存的总能量。

由于总能量可能较大，输出时对 $p$ 取模。

inputFormat: 第一行一个整数 $T$，表示数据组数。接下来 $T$ 行，每行四个整数 $n,m,k,p$。

outputFormat: 共 $T$ 行，每行一个数，表示总能量对 $p$ 取模后的结果。


title: [SDOI2016] 数字配对

description:
有 $n$ 种数字，第 $i$ 种数字是 $a_i$、有 $b_i$ 个，权值是 $c_i$。

若两个数字 $a_i$、$a_j$ 满足，$a_i$ 是 $a_j$ 的倍数，且 $a_i/a_j$ 是一个质数，

那么这两个数字可以配对，并获得 $c_i \times c_j$ 的价值。

一个数字只能参与一次配对，可以不参与配对。

在获得的价值总和不小于 $0$ 的前提下，求最多进行多少次配对。

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

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

第三行 $n$ 个整数 $b_1,b_2,\cdots,b_n$。

第四行 $n$ 个整数 $c_1,c_2,\cdots,c_n$。

outputFormat: 一行一个数，最多进行多少次配对。


title: [SDOI2016] 游戏

description:
Alice 和 Bob 在玩一个游戏。

游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。

有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$，若 $r$ 与 $s$ 的距离是 $dis$，那么 Alice 在点 $r$ 上添加的数字是 $a\times dis+b$。

有时，Bob 会选择一条从 $s$ 到 $t$ 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。

Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

inputFormat:
第一行两个数字 $n,m$，表示树的点数和进行的操作数。

接下来 $n-1$ 行，每行三个数字 $u,v,w$，表示树上有一条连接 $u,v$ 的边，长度是 $w$。

接下来 $m$ 行。每行第一个数字是 $1$ 或 $2$。

若第一个数是 $1$，表示 Alice 进行操作，接下来四个数字 $s,t,a,b$。

若第一个数是 $2$，表示 Bob 进行操作，接下来两个数字 $s,t$。

outputFormat: 每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字


title: [SDOI2016] 生成魔咒

description:
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $1,2$ 拼凑起来形成一个魔咒串 $[1,2]$。

一个魔咒串 $S$ 的非空字串被称为魔咒串 $S$ 的生成魔咒。

例如 $S=[1,2,1]$ 时，它的生成魔咒有 $[1],[2],[1,2],[2,1],[1,2,1]$ 五种。$S=[1,1,1]$ 时，它的生成魔咒有 $[1],[1,1],[1,1,1]$ 三种，最初 S 为空串。

共进行 $n$ 次操作，每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 $S$ 共有多少种生成魔咒。

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

第二行 $n$ 个数，第 $i$ 个数表示第 $i$ 次操作加入的魔咒字符 $x_i$。

outputFormat:
输出 $n$ 行，每行一个数。
第 $i$ 行的数表示第 $i$ 次操作后 $S$ 的生成魔咒数量。

hint:
#### 数据规模与约定
对于 $10\%$ 的数据，保证 $1 \le n \le 10$；
对于 $30\%$ 的数据，保证 $1 \le n \le 100$；
对于 $60\%$ 的数据，保证 $1 \le n \le 10^3$；
对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \leq x_i \leq 10^9$。


title: [SDOI2016] 排列计数

description:
求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$。

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

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

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

以下 $T$ 行，每行描述一组测试数据。

对于每组测试数据，每行输入两个整数，依次代表 $n$ 和 $m$。

outputFormat: 共输出 $T$ 行，对于每组测试数据，输出一行一个整数代表答案。


title: [SDOI2016] 征途

description:
Pine 开始了从 $S$ 地到 $T$ 地的征途。

从 $S$ 地到 $T$ 地的路可以划分成 $n$ 段，相邻两段路的分界点设有休息站。

Pine 计划用 $m$ 天到达 $T$ 地。除第 $m$ 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。

Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。

帮助 Pine 求出最小方差是多少。

设方差是 $v$，可以证明，$v\times m^2$ 是一个整数。为了避免精度误差，输出结果时输出 $v\times m^2$。

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

第二行 $n$ 个数，表示 $n$ 段路的长度。

outputFormat: 一个数，最小方差乘以 $m^2$ 后的值。

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

- 对于 $30\%$ 的数据，$1 \le n \le 10$；
- 对于 $60\%$ 的数据，$1 \le n \le 100$；
- 对于 $100\%$ 的数据，$1 \le n \le 3000$。

保证从 $S$ 到 $T$ 的总路程不超过 $3\times 10^4$。

$2 \leq m \leq n+1$，每段路的长度为不超过 $3 \times 10^4$ 的**正整数**。


title: [SDOI2016] 模式字符串

description:
给出 $n$ 个结点的树 $T$，其中每一个结点上有一个字符，这里我们所说的字符只考虑大写字母 A 到 Z，再给出长度为 $m$ 的模式串 $S$，其中每一位仍然是 A 到 Z 的大写字母。

Alice 希望知道，有多少对结点 $(u,v)$ 满足 $T$ 上从 $u$ 到 $v$ 的最短路径形成的字符串可以由模式串 $S$ 重复若干次得到l。

这里结点对 $(u,v)$ 是有序的，也就是说 $(u,v)$ 和 $(v,u)$ 需要被区分。

所谓模式串的重复，是将若干个模式串 $s$ 依次相接（不能重叠)。例如当 $S=$ `PLUS`的时候，重复两次会得到 `PLUSPLUS`，重复三次会得到 `PLUSPLUSPLUS`，同时要注意，重复必须是整数次的。例如当 $S= $ `XYXY` 时，因为必须重复整数次，所以 `XYXYXY` 不能看作是 $S$ 重复若干次得到的。

inputFormat:
每一个数据有多组测试，

第一行输入一个整数 $C$，表示总的测试个数。

对于每一组测试来说：

第一行输入两个整数，分别表示树 $T$ 的结点个数 $n$ 与模式长度 $m$。结点被依次编号为 $1$ 到 $n$。

之后一行，依次给出了 $n$ 个大写字母（以一个长度为n的字符串的形式给出），依次对应树上每一个结点上的字符（第 $i$ 个字符对应了第 $i$ 个结点)。

之后 $n-1$ 行，每行有两个整数 $u$ 和 $v$ 表示树上的一条无向边，之后一行给定一个长度为 $m$ 的由大写字母组成的字符串，为模式串 $S$。

outputFormat:
给出 $C$ 行，对应 $C$ 组测试。

每一行输出一个整数，表示有多少对节点 $(u,v)$ 满足从 $u$ 到 $v$ 的路径形成的字符串恰好是模式串的若干次重复。

hint: $1\leq C\leq 10$，$3\leq \sum N\leq 10^6$，$3\leq \sum M\leq 10^6$。


title: [SDOI2016] 墙上的句子

description:
考古学家发现了一堵写有未知语言的白色墙壁，上面有一个 $n$ 行 $m$ 列的格子，其中有些格子内被填入了某个 `A` 至 `Z` 的大写字母，还有些格子是空白的。

一直横着或竖着的连续若干个字母会形成一个单词，且每一行的阅读顺序可能是从左向右或从右向左，每一列的阅读顺序可能是从下往上或从上往下。也就是说对于每一行来说，从左向右可以被看做是若干个单词形成的句子，相邻两个单词被一个或多个空白格子分割开来；也有可能是从右向左被看成是一个句子，竖直方向类似。

遗憾的是，我们并不完全知道每一行每一列的阅读顺序是怎样的。但可以猜测，有些单词会满足反转过来也是一个单词。例如单词 `BOY`，翻转过来的 `YOB` 也是一个英文单词。

此外观察者发现，对每一行（列）来说，按照确定后的阅读顺序读出的所有单词同时满足“自己的字典序不小于翻转后的字典序”，或同时满足“自己的字典序不大于翻转后的字典序”。

在确定了所有行列的阅读顺序之后，我们可以构造出关于这种未知语言的字典。

请问字典中出现的“翻转过来也是一个单词”的单词最少有多少种请注意，如果一个单词翻转后是不同的另外一个单词，它们需要被分别计入；而对于本身是回文的单词则不需要重复计入

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

对于每一组数据来说：第一行输入两个整数 $n,m$。

第二行给出了 $n$ 个数字，对应 $n$ 行，其中若第 $i$ 个数字为 `1`，则表示第 $i$ 行的阅读顺序从左往右；若为 `-1` 则为从右向左；若为 `0` 则表示无法确定。

第三行给出了 $m$ 个数字，对应 $n$ 行，其中若第 $i$ 个数字为 `1`，则表示第 $i$ 列的阅读顺序从上往下；若为 `-1` 则为从下向上；若为 `0` 则表示无法确定

之后 $n$ 行，每行给出了长度为 $m$ 的字符串，由 `A` ~ `Z` 和下划线组成，对应了每个格子的符号，其中下划线表示格子为空。

outputFormat:
输出 $T$ 行。每一组数据输出一行一个整数，表示最少有多少个单词，满足翻转后依然是单词。

注意，如果一个单词是回文，那么它一定满足“翻转后依旧是单词”

samples:
1
2 10
0 0
0 0 0 0 0 0 0 0 0 0
ADA_JARVIS
ADA_SIVRAJ

hint: 对于 $100\%$ 的数据，$1\leq n,m\leq 72$，$T\leq 64$。


title: [SDOI2016] 硬币游戏

description:
Alice 和 Bob 现在在玩的游戏，主角是依次编号为 1 到 n 的 n 枚硬币。每一枚硬币都有两面，我们分别称之为正面和反面。一开始的时候，有些硬币是正面向上的，有些是反面朝上的。Alice 和 Bob 将轮流对这些硬币进行翻转操作，且Alice 总是先手。

具体来说每次玩家可以选择一枚编号为 x，要求这枚硬币此刻是反面朝上的。对于编号 x 来说，我们总可以将 x 写成 $ \cdot 2^a \cdot 3^b$ ，其中 a 和 b 是非负整数，c 是与 2,3 都互质的非负整数，然后有两种选择：

选择整数 p,q 满足 $a \ge pq , p \ge 1$  且 $1 \leq q \leq \text{MAXQ}$，然后同时翻转所有编号为 $c \cdot 2^{a-pj} \cdot 3^b$  的硬币，其中 $j = 0, 1, 2, \ldots q$。

选择整数 p,q 满足 $b \geq pq, p \ge 1$  且 $1 \leq q \leq \text{MAXQ}$，然后同时翻转所有编号为 $c \cdot 2^a \cdot 3^{b-pj}c$的硬币，其中$j = 0, 1, 2, \ldots q$。

可以发现这个游戏不能无限进行下去，当某位玩家无法继续操作上述操作时，便输掉了游戏。作为先手的 Alice，总是希望可以在比赛开始之前就知道自己能否获胜。她知道自己和 Bob 都是充分聪明的，所以在游戏过程中，两人都会最优化自己的策略并尽量保证自己处于不败的情形中。

inputFormat:
本题有多组测试数据，第一行输入一个整数T，表示总的数据组数。之后给出T组数据

每组数据第一行输入两个整数n,MAXQ

第二行输入n个整数，第i个数表示第i个硬币的初始状态，0表示反面朝上，1表示正面朝上

outputFormat: 输出共有t行。对于每一组数据来说，如果Alice先手必胜，则输出"win"（不包括引号），否则输出"lose"


title: [SDOI2016] 探险路线

description:
你所面对的丛林，可以被刻画为n行m列的格点图，其中第i行第j列的格子代表了一块区域，每个格子有整数权值v(i,j)（可能为负），表明了访问这一块区域的收益或代价。每一个格子最多只能被访问一次，且不可走出地图的边界，你被要求从第一行第一列出发，到第n行第m列结束，你的目标是最大化途经的所有格子的权值和。

因为一些缘故，你的探险路线受到了一些限制。起初你在起点，之后每一天的行动中，首先你需要选择上下左右中的某一个方向，沿着这个方向走0步（也就是不走）或任意步；之后重新选择一个方向（可以与原来方向相同，也可以是不同的方向），沿着这个方向一直走下去，走到地图的某个边界位置结束这一天的探险。探险可以有任意多天，每一天探险结束的边界位置就是第二天的起点位置，除非这一天就是探险的结束。注意，因为每一块格子只能被访问一次，且你最终的结束点必须是第n行第m列的位置，所以你需要谨慎计划每一天的路线。

你希望知道最优方案下，整个探险之旅的收益有多大，即你可以获得的权值和最大是多少。

inputFormat: 第一行输入两个整数，分别表示总行数n与总列数m。之后n行，每行有m个整数，。其中第i行第j列的整数对应了访问第i行第j列区域的收益或代价。

outputFormat: 输出一个整数，表示最优探险路线中所有被访问格子的权值和。

hint: 对于所有数据3<=n<=800且3<=m<=800，保证收益代价绝对值在100000以内


title: [SDOI2016] 齿轮

description: 现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x: y。即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这Ｎ个组合齿轮能否同时转动。

inputFormat:
有多组数据。

第一行给定整数Ｔ，表示总的数据组数，之后依次给出Ｔ组数据。

每一组数据的第一行给定整数Ｎ和Ｍ，表示齿轮总数和链条总数。

之后有Ｍ行，依次描述了每一个链条，其中每一行给定四个整数u，v，x和y，表示只考虑这一组联动关系的情况下，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。请注意，x为正整数，而y为非零整数，但是y有可能为负数。

outputFormat: 输出T行，对应每一组数据。首先应该输出标识这是第几组数据，参见样例输出。之后输出判定结果，如果N个组合齿轮可以同时正常运行，则输出Yes，否则输出No。

hint: 对于所有数据，T<=32，N<=1000，M<=10000且x与y的绝对值均不超过100。


title: [SDOI2016] 平凡的骰子

description:
这是一枚平凡的骰子。它是一个均质凸多面体，表面有n个端点，有f个面，每一面是一个凸多边形，且任意两面不共面。将这枚骰子抛向空中，骰子落地的时候不会发生二次弹跳（这是一种非常理想的情况）。

你希望知道最终每一面着地的概率。每一面着地的概率可以用如下的方法计算：我们假设O为骰子的重心，并以O为球心，做半径为1的单位球面（记为S）。

我们知道S的表面积即单位球的表面积，为4\*pi，这里pi为圆周率。对于骰子的某一面C来说，球面S上存在一块区域T满足：当下落时若骰子所受重力方向与S的交点落在T中，则C就是最终着地的一面。那么C着地的概率为区域T的面积除以4\*pi。

为了能更好地辅助计算球面上一块区域的面积，我们给出单位球面S上三角形的面积计算公式。考虑单位球面S上的三个两两相交的大圆，交点依次为A，B和C。则曲面三角形ABC的面积为 $\text{Area}(ABC)=\alpha+\beta+\gamma-\pi$，其中 $\alpha,\beta , \gamma$ 分别对应了三个二面角的大小。如下图所示。

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

我们保证：每一面着地的时候，重心的垂心都恰好在这一面内。也就是说不会出现摆不稳的情况。

inputFormat:
第一行输入两个整数，分别表示端点总数n与表面总数f，分别从1开始编号。

之后n行，每行有三个浮点数x，y和z，给出了每一个端点的坐标。

之后f行依次描述了每一块表面，首先给出不小于3的整数d，表示这一面的端点个数，之后d个整数按照逆时针方向（视角在骰子的外面）给出了每一个端点的编号。

outputFormat: 输出f行，第i行有一个浮点数，表示第i个面着地的概率。本题中您的输出应该保留距离答案最近的7位小数，即在需要保留7位小数的前提之下与标准答案最接近。数据保证可以避免对小数点后第八位四舍五入后产生的精度误差

hint: 对于所有数据，4<=n<=50且4<=m<=50，所有坐标的绝对值都在10000以内


title: [JSOI2010] 快递服务

description:
「飞奔」快递公司成立之后，已经分别与市内许多中小企业公司签订邮件收送服务契约。由于有些公司是在同一栋大楼内，所以「飞奔」公司收件的地点（收件点）最多只有 $m$ 点（$1,2,\dots,m$），因此「飞奔」仅先行采购了三辆货车并聘用了三名司机，每天早上分别从收件地点 $1,2,3$ 出发。而在与客户的服务契约中有明确订约：「飞奔」必须在客户提出邮件寄送要求的隔天派人至该公司（地点）收件。

为了能更有效率的服务客户并节省收件时间，该公司设立了收件服务登记网站，客户如有邮件需要寄送，必须在需要收件的前一天就先上网登记。为了节省油量，「飞奔」就利用晚上先行安排三位司机隔天的收件路线。每位司机至各地点收件的顺序应与各公司上网登记的顺序相符且必须能在最省油的情况下完成当天所有的收件服务。因此每位司机有可能需要在不同时间重复到同一地点收件，或不同的司机有可能需在不同的时间点前往同一地点收件。

如下面范例二（收件公司地点依序为：`4 2 4 1 5 4 3 2 1`）所示，虽然司机 $1$ 一开始就已经在收件地点 $1$ 了，但是他却不能先把后面第四个登记的公司（地点 $1$）邮件先收了再前往第一、第二、或第三个登记收件地点（地点 $4,2,4$）收件。但是如果前三个登记收件的服务是由司机 $2$ 或 $3$ 来负责，则司机 $1$ 就可以在地点 $1$ 收了第四个登记的邮件后再前往后面所登记的地点收件。此外，在某些情况下，不一定每辆车都要收到货，也就是说，最佳收件方式也有可能是只需出动一或两辆车去收货。请写一个程序来帮「飞奔」公司计算每天依预约顺序至各收件地点收件的最少总耗油量。

### 简要题意

给定一个 $m \times m$ 的矩阵 $D$。我们规定一个序列 $a(a_0,a_1,a_2,\dots,a_n)$ 的花费为 $\sum\limits_{i=1}^{n}D_{a_{i-1},a_i}$。

现在给定你一个长度 $\leq 1000$ 的序列 $s$，请你把它分成三个子序列 $a,b,c$，并且规定 $a_0=1,b_0=2,c_0=3$，求出所有划分方案中它们的最小化费和。

特殊地，矩阵 $D$ 满足三角不等式，具体见输入格式中的详细解释。

（By El_destructor）

inputFormat:
输入文件第一行有一个整数 $m$，代表「飞奔」公司收件的地点数，以 $1$ 至 $m$ 之间的整数代号来表示每个地点。

接下来的 $m$ 行（第 $2$ 到第 $m+1$ 行），每行有 $m$ 个整数，代表一个矩阵 $D$。第 $i$ 行的第 $j$ 个整数 $D(i,j)$ 表示司机开车从收件点 $i$ 到收件点 $j$ 所需耗油量。最后一行是一个序列，按照顺序为前一天上网登记要求收件的公司地点代号，最多会有 $1000$ 个收件请求。

输入文件中任两个相邻的整数都以一个空格隔开。

注意：油量矩阵 $D$ 满足三角不等式，也就是说 $\forall 1 \leq i,j,k \leq m,D(i,j) \leq D(i,k)+D(k,j)$。因此，每辆车前往下一个收件地点时一定是直接前往，不必先绕道至其它地点再抵达下个收件地点。

outputFormat: 输出一个整数，代表收件所需最少总耗油量。

hint:
#### 样例解释

到每个请求收件地点的司机分别为 `1 1 1 1 3 3 2 2 2 1`，因此司机 $1$ 只需从起使点 $1$ 移动到地点 $3$，司机 $2$ 只需停留在地点 $2$，司机 $3$ 从起始点 $3$ 移动到地点 $4$。

#### 数据范围

$3 \leq m \leq 200,1 \leq s_i \leq m$。


title: [JSOI2010] 部落划分

description:
聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。

不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了 $n$ 个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了 $k$ 个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法：

对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。

例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

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

inputFormat:
输入文件第一行包含两个整数 $n$ 和 $k$，分别代表了野人居住点的数量和部落的数量。

接下来 $n$ 行，每行包含两个整数 $x$，$y$，描述了一个居住点的坐标。

outputFormat: 输出一行一个实数，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

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

对于 $100\%$ 的数据，保证 $2 \leq k \leq n \leq 10^3$，$0 \leq  x, y \leq 10^4$。


title: [JSOI2010] 冷冻波

description:
WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。

当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。

在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。

现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？

inputFormat:
输入文件第一行包含三个整数N、M、K(N,M,K<=200)，分别代表巫妖的数量、小精灵的数量和树木的数量。

接下来N行，每行包含四个整数x, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。

再接下来M行，每行两个整数x, y，分别代表了每个小精灵的坐标。

再接下来K行，每行三个整数x, y, r，分别代表了每个树木的坐标。

输入数据中所有坐标范围绝对值不超过10000，半径和施法间隔不超过20000。

outputFormat: 输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出-1。


title: [AHOI2014/JSOI2014] 拼图

description:
JYY 最近迷上了拼图游戏。作为一个计算机科学家，JYY 有一套黑白色的拼图，他希望通过合理的拼接，使得拼出的最终图案中，能包含面积最大的全白色子矩形。

JYY 一共有 $S$ 块拼图，并且由 $1$ 到 $S$ 编号。编号为 $i$ 的拼图是一个 $N$ 行列的方格矩形，每个方格都为黑色或者白色。一开始 JYY 将他的这 $S$ 块拼图按照编号顺序左右相连依次放在桌上拼成了一个 $N$ 行 $M$ 列（这里 $M=\sum_{i=1}^S W_i$）的大矩形。

之后 JYY 发现，可以通过改变这 $S$ 块拼图的连接次序，使得拼成的 $N$ 行 $M$ 列的大矩形中，最大全白子矩形面积变大。

现在 JYY 想知道，怎么拼才能得到最大的全白子矩形呢？请你帮助他计算出最佳的拼接方案。

inputFormat:
第一行包含一个整数 $T$，代表测试数据的组数，接下来按顺序描述了每组测试数据。

每组测试数据的第一行包含两个整数 $S$ 和 $N$。

接下来 $S$ 组输入，第 $i$ 组对应编号为 $i$ 的拼图。

在第 $i$ 组输入中，第一行包含一个整数 $W_i$；

接下来 $N$ 行描述一个 $N$ 行 $W_i$ 列的 $0/1$ 矩形；

其中第 $x$ 行 $y$ 列为 $0$ 则表示该拼图对应位置的颜色是白色，反之则为黑色。

outputFormat: 对于每组数据输出一行包含一个整数 ans，表示最大可能的全白色子矩形的面积。

hint: 对于 $100\%$ 的数据满足$1\le S,N,W \le 10^5$，$N\times \sum W_i \le10^5$，$1\le T\le3$。


title: [AHOI2014/JSOI2014] 宅男计划

background: 自从迷上了拼图，JYY 就变成了个彻底的宅男。为了解决温饱问题，JYY 不得不依靠叫外卖来维持生计。

description:
外卖店一共有 $n$ 种食物，分别从 $1$ 到 $n$ 编号。第 $i$ 种食物有固定的价钱 $p_i$ 和保质期 $s_i$。第 $i$ 种食物会在 $s_i$ 天后过期。JYY 是不会吃过期食物的。

比如 JYY 如果今天点了一份保质期为 $1$ 天的食物，那么 JYY 必须在今天或者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为 $0$ 天，这样这份食物就必须在购买当天吃掉。

JYY 现在有 $m$ 块钱，每一次叫外卖需要额外付给送外卖小哥外送费 $f$ 元。

送外卖的小哥身强力壮，可以瞬间给 JYY 带来任意多份食物。JYY 想知道，在满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？

inputFormat:
第一行包含三个整数，分别表示 $m, f, n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数表示第 $i$ 种食物的价格 $p_i$ 和保质期 $s_i$。

outputFormat: 输出一行一个整数，表示 JYY 可以宅的最多的天数。

hint:
#### 样例输入输出 1 解释
JYY的最佳策略是：
- 第一天买一份食物 $1$ 和一份食物 $2$ 并且吃一份食物 $1$；
- 第二天吃一份食物 $2$；
- 第三天买一份食物 $1$ 并且吃掉。

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 200$，$0 \leq s_i \leq 10^{18}$，$1 \leq f, p_i, m \leq10^{18}$。


title: [AHOI2014/JSOI2014] 骑士游戏

background: 长期的宅男生活中，JYY 又挖掘出了一款 RPG 游戏。在这个游戏中 JYY 会扮演一个英勇的骑士，用他手中的长剑去杀死入侵村庄的怪兽。

description:
在这个游戏中，JYY 一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗 JYY 一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统 bug，并不保证这一点）。

游戏世界中一共有 $N$ 种不同的怪兽，分别由 $1$ 到 $N$ 编号，现在 $1$ 号怪兽入侵村庄了，JYY 想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？

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

接下来 $N$ 行，每行描述一个怪兽的信息；

其中第 $i$ 行包含若干个整数，前三个整数为 $S_i$，$K_i$ 和 $R_i$，表示对于 $i$ 号怪兽，普通攻击需要消耗 $S_i$ 的体力，法术攻击需要消耗 $K_i$ 的体力，同时 $i$ 号怪兽死亡后会产生 $R_i$ 个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。

outputFormat: 输出一行一个整数，表示最少需要的体力值。

hint:
首先用消耗 $4$ 点体力用普通攻击，然后出现的怪兽编号是 $2$，$2$ 和 $3$。花费 $10$ 点体力用法术攻击杀死两个编号为 $2$ 的怪兽。剩下 $3$ 号怪兽花费 $1$ 点体力进行普通攻击。此时村庄里的怪兽编号是 $2$ 和 $4$。最后花费 $11$ 点体力用法术攻击将这两只怪兽彻底杀死。一共花费的体力是 $4+5+5+1+5+6=26$。

对于所有数据 $2 \le N \le 2 \times 10^5$，$1 \le R_i,\sum R_i \le 10^6$，$1 \le K_i,S_i \le 5 \times 10^{14}$。


title: [AHOI2014/JSOI2014] 支线剧情

background: 宅男 JYY 非常喜欢玩 RPG 游戏，比如仙剑，轩辕剑等等。不过 JYY 喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在 JYY 想花费最少的时间看完所有的支线剧情。

description:
JYY 现在所玩的 RPG 游戏中，一共有 $N$ 个剧情点，由 $1$ 到 $N$ 编号，第 $i$ 个剧情点可以根据 JYY 的不同的选择，而经过不同的支线剧情，前往 $K_i$ 种不同的新的剧情点。当然如果为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。

JYY 观看一个支线剧情需要一定的时间。JYY 一开始处在 $1$ 号剧情点，也就是游戏的开始。显然任何一个剧情点都是从 $1$ 号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。由于 JYY 过度使用修改器，导致游戏的“存档”和“读档”功能损坏了，

所以 JYY 要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到 $1$ 号剧情点。JYY 可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情是很痛苦，JYY 希望花费最少的时间，看完所有不同的支线剧情。

inputFormat:
输入一行包含一个正整数 $N$。

接下来 $N$ 行，第 $i$ 行为 $i$ 号剧情点的信息；

第一个整数为 $K_i$，接下来 $K_i$ 个整数对，$b_{i,j}$ 和 $t_{i,j}$，表示从剧情点 $i$ 可以前往剧情点 $b_{i,j}$，并且观看这段支线剧情需要花费 $t_{i,j}$ 的时间。

outputFormat: 输出一行包含一个整数，表示 JYY 看完所有支线剧情所需要的最少时间。

hint:
### 样例解释

JYY 需要重新开始 $3$ 次游戏，加上一开始的一次游戏，$4$ 次游戏的进程是：

- $1 \to 2 \to 4$；
- $1 \to 2 \to 5$；
- $1 \to 3 \to 5$；
- $1 \to 3 \to 6$。

对于 $100\%$ 的数据满足 $N \le 300$，$0 \le K_i \le 50$，$1 \le T_{i,j} \le 300$，$\sum K_i \le 5000$。


title: [AHOI2014/JSOI2014] 保龄球

background: JYY 很喜欢打保龄球，虽然技术不高，但是还是总想着的高分。这里 JYY 将向你介绍他所参加的特殊保龄球比赛的规则，然后请你帮他得到尽量多的分数。

description:
一场保龄球比赛一共有 $n$ 个轮次，每一轮都会有十个木瓶放置在木板道的另一端。每一轮中，选手都有两次投球的机会来尝试击倒全部的十个木瓶。对于每一次投球机会，选手投球的得分等于这一次投球所击倒的木瓶数量。选手每一轮的得分是他两次机会击倒全部木瓶的数量。

对于每一个轮次，有如下三种情况：

1、 “全中”：如果选手第一次尝试就击倒了全部十个木瓶，那么这一轮就为“全中”。在一个“全中”轮中，由于所有木瓶在第一次尝试中都已经被击倒，所以选手不需要再进行第二次投球尝试。同时，在计算总分时，选手在下一轮的得分将会被乘2计入总分。

2、“补中”：如果选手使用两次尝试击倒了十个木瓶，那么这一轮就称为“补中”。同时，在计算总分时，选手在下一轮中的第一次尝试的得分将会以双倍计入总分。

3、“失误”：如果选手未能通过两次尝试击倒全部的木瓶，那么这一轮就被称为“失误”。同时，在计算总分时，选手在下一轮的得分会被计入总分，没有分数被翻倍。此外，如果第 $n$ 轮是“全中”，那么选手可以进行一次附加轮：也就是，如果第 $n$ 轮是“全中”，那么选手将一共进行 $n+1$ 轮比赛。显然，在这种情况下，第 $n+1$ 轮的分数一定会被加倍。

附加轮的规则只执行一次。也就是说，即使第 $n+1$ 轮选手又打出了“全中”，也不会进行第 $n+2$ 轮比赛。因而，附加轮的成绩不会使得其他轮的分数翻番。最后，选手的总得分就是附加轮规则执行过，并且分数按上述规则加倍后的每一轮分数之和。

JYY 刚刚进行了一场 $n$ 个轮次的保龄球比赛，但是，JYY非常不满意他的得分。JYY想出了一个办法：他可以把记分表上，他所打出的所有轮次的顺序重新排列，这样重新排列之后，由于翻倍规则的存在，JYY就可以得到更高的分数了！

当然了，JYY不希望做的太假，他希望保证重新排列之后，所需要进行的轮数和重排前所进行的轮数是一致的：比如如果重排前JYY在第 $n$ 轮打出了“全中”，那么重排之后，第 $n$ 轮还得是“全中”以保证比赛一共进行 $n+1$ 轮；同样的，如果 JYY 第 $n$ 轮没有打出“全中”，那么重排过后第 $n$ 轮也不能是全中。请你帮助 JYY 计算一下，他可以得到的最高的分数。

inputFormat:
第一行包含一个整数 $n$，表示保龄球比赛所需要进行的轮数。

接下来包含 $n$ 或 $n+1$ 行，第i行包含两个非负整数 $x_i,y_i$，表示 JYY 在这一轮两次投球尝试所得到的分数，$x_i$ 表示第一次尝试，$y_i$ 表示第二次尝试。

特别地，`10 0` 表示一轮“全中”。

读入数据存在 $n+1$ 行，当且仅当 $x_n=10$ 且 $y_n=0$。

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

hint:
【样例说明】
按照输入顺序，JYY 将得到 $37$ 分。
最佳方案是排列成如下顺序：
```plain
3 7
10 0
5 2
```

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 50$。


title: [AHOI2014/JSOI2014] 奇怪的计算器

background: JYY 有个奇怪的计算器，有一天这个计算器坏了，JYY 希望你能帮助他写一个程序来模拟这个计算器的运算。

description:
JYY 的计算器可以执行 $N$ 条预设好的指令。每次 JYY 向计算器输入一个正整数 $X$，计算器就会以 $X$ 作为初始值，接着依次执行预设的 $N$ 条指令，最后把最终得出的结果返回给 JYY。

每一条指令可以是以下四种指令之一：（这里 $a$ 表示一个正整数。）

1. $+a$：表示将当前的结果加上 $a$；
2. $-a$：表示将当前的结果减去 $a$；
3. $\times a$：表示将当前的结果乘以 $a$；
4. $@a$：表示将当前的结果加上 $a\times X$（$X$ 是一开始 JYY 输入的数）。

计算器用于记录运算结果的变量的存储范围是有限的，所以每次运算结束之后会有计算结果溢出的问题。

JYY 的计算器中，存储每计算结果的变量只能存储 $L$ 到 $R$ 之间的正整数，如果一次指令执行过后，计算结果超过了 $R$，那么计算器就会自动把结果变成 $R$，然后再以 $R$ 作为当前结果继续进行之后的计算。同理，如果运算结果小于 $L$，计算器也会把结果变成 $L$，再接着计算。

比如，假设计算器可以存储 $1$ 到 $6$ 之间的值，如果当前的计算结果是 $2$，那么在执行 $+5$ 操作之后，存储结果的变量中的值将会是 $6$。虽然 $2+5$ 的实际结果是 $7$，但是由于 $7$ 超过了存储范围的上界，所以结果就被自动更正成了上界的大小，也就是 $6$。

JYY 一共想在计算器上输入 $Q$ 个值，他想知道这 $Q$ 个值输入计算器之后，分别会得到什么结果呢？

inputFormat:
第一行包含三个正整数，$N$，$L$ 和 $R$。

接下来 $N$ 行，每行一个指令，每个指令如题述，由一个字符和一个正整数组成，字符和正整数中间有一个空格隔开。

第 $N+2$ 行包含一个整数 $Q$，表示 JYY 希望输入的数的数量。

第接下来 $Q$ 行每行一个正整数，第 $k$ 个正整数 $X_k$ 表示 JYY 在第 $k$ 次输入的整数。

outputFormat: 输出 $Q$ 行每行一个正整数，第 $k$ 行的整数表示输入 $X_k$ 后，依次经过 $N$ 个指令进行计算所得到的结果。

hint:
### 样例解释

当 JYY 输入 $2$ 时，计算器会进行 $5$ 次运算，每一次运算之后得到的结果分别是 $6$（实际计算结果为 $7$ 但是超过了上界），$3,6,1$（实际结果为 $-1$ 但是低于了下界）和 $5$（由于一开始输入的是 $2$，所以这一次计算为 $1+2 \times 2$）。

### 数据范围及约定

对于所有测试数据，$1\le N$，$Q\le 10^5$，$1\le L\le X_k\le R\le 10^9$，$1\le a\le 10^9$。


title: [NOI2007] 生成树计数

description:
最近，小栋在无向连通图的生成树个数计算方面有了惊人的进展，他发现：

- $n$ 个结点的环的生成树个数为 $n$。
- $n$ 个结点的完全图的生成树个数为 $n^{n-2}$ 。

这两个发现让小栋欣喜若狂，由此更加坚定了他继续计算生成树个数的想法，他要计算出各种各样图的生成树数目。

一天，小栋和同学聚会，大家围坐在一张大圆桌周围。小栋看了看，马上想到了生成树问题。如果把每个同学看成一个结点，邻座（结点间距离为 $1$）的同学间连一条边，就变成了一个环。可是，小栋对环的计数已经十分娴熟且不再感兴趣。于是，小栋又把图变了一下：不仅把邻座的同学之间连一条边，还把相隔一个座位（结点间距离为 $2$）的同学之间也连一条边，将结点间有边直接相连的这两种情况统称为 有边相连，如图 $1$ 所示。

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

小栋以前没有计算过这类图的生成树个数，但是，他想起了老师讲过的计算任意图的生成树个数的一种通用方法：构造一个 $n\times n$ 的矩阵 $A=\{ a_{i,j}\}$，其中：

$$a_{i,j}=\begin{cases}
d_i & i=j \\
-1 & \text{$i, j$ 之间有边直接相连} \\
0 & \text{其他情况}
\end{cases}$$

与图 1 相应的 $A$ 矩阵如下所示。为了计算图 1 所对应的生成数的个数，只要去掉矩阵 $A$ 的最后一行和最后一列，得到一个 $(n-1)\times(n-1)$ 的矩阵 $B$，计算出矩阵 $B$ 的行列式的值便可得到图 1 的生成树的个数。

$$
A=\begin{bmatrix}
4 & -1 & -1 & 0 & 0 & 0 & -1 & -1 \\
-1 & 4 & -1 & -1 & 0 & 0 & 0 & -1 \\
-1 & -1 & 4 & -1 & -1 & 0 & 0 & 0 \\
0 & -1 & -1 & 4 & -1 & -1 & 0 & 0 \\
0 & 0 & -1 & -1 & 4 & -1 & -1 & 0 \\
0 & 0 & 0 & -1 & -1 & 4 & -1 & -1 \\
-1 & 0 & 0 & 0 & -1 & -1 & 4 & -1 \\
-1 & -1 & 0 & 0 & 0 & -1 & -1 & 4 \\
\end{bmatrix},\\
B=\begin{bmatrix}
4 & -1 & -1 & 0 & 0 & 0 & -1  \\
-1 & 4 & -1 & -1 & 0 & 0 & 0  \\
-1 & -1 & 4 & -1 & -1 & 0 & 0 \\
0 & -1 & -1 & 4 & -1 & -1 & 0 \\
0 & 0 & -1 & -1 & 4 & -1 & -1 \\
0 & 0 & 0 & -1 & -1 & 4 & -1 \\
-1 & 0 & 0 & 0 & -1 & -1 & 4 \\
\end{bmatrix},
$$

所以生成树的个数为 $\det B =3528$。小栋发现利用通用方法，因计算过于复杂而很难算出来，而且用其他方法也难以找到更简便的公式进行计算。于是，他将图做了简化，从一个地方将圆桌断开，这样所有的同学形成了一条链，连接距离为 1 和距离为 2 的点。例如八个点的情形如下：

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

这样生成树的总数就减少了很多。小栋不停的思考，一直到聚会结束，终于找到了一种快捷的方法计算出这个图的生成树个数。可是，如果把距离为 $3$ 的点也连起来，小栋就不知道如何快捷计算了。现在，请你帮助小栋计算这类图的生成树的数目。

inputFormat: 输入文件中包含两个整数 $k,n$，由一个空格分隔。$k$ 表示要将所有距离不超过 $k$（含 $k$）的结点连接起来，$n$ 表示有 $n$ 个结点。

outputFormat: 输出文件输出一个整数，表示生成树的个数。由于答案可能比较大，所以你只要输出答案除 $65521$ 的余数即可。


title: [NOI2007] 追捕盗贼

background:
spj来源：loj-Robin。已获得授权。

https://www.luogu.org/paste/dxytr6gc

附spj，一些修改部分未按照代码规范，请各位谅解。

description:
魔法国度 Magic Land 里最近出现了一个大盗 Frank，他在 Magic Land 四处作案，专门窃取政府机关的机密文件（因而有人怀疑 Frank 是敌国派来的间谍）。

为了捉住 Frank，Magic Land 的安全局重拳出击！

Magic Land 由 N 个城市组成，并且这 N 个城市又由恰好 N-1 条公路彼此连接起来，使得任意两个城市间都可以通过若干条公路互达。从数据结构的角度我们也可以说，这 N 个城市和 N-1 条公路形成了一棵树。

例如，下图就是 Magic Land 的一个可能格局（4 个城市用数字编号，3 条公路用字母编号）：

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

大盗 Frank 能够在公路上以任意速度移动。

比方说，对于上图给出的格局，在 0.00001 秒钟内（或者任意短的一段时间内），Frank 就可以从城市 1 经过城市 2 到达城市 4，中间经过了两条公路。

想要生擒 Frank 困难重重，所以安全局派出了经验丰富的警探，这些警探具有非凡的追捕才能：

1.  只要有警探和 Frank 同处一个城市，那么就能够立刻察觉到Frank，并且将其逮捕。

2.  虽然 Frank 可以在公路上以任意快的速度移动，但是如果有警探和 Frank 在同一条公路上相遇，那么警探也可以立刻察觉到 Frank 并将其逮捕。

安全局完全不知道 Frank 躲在哪个城市，或者正在哪条公路上移动，所以需要制定一个周密的抓捕计划，计划由若干 步骤组成。在每一步中，可以做如下几件事中的一个：

1.  在某个城市空降一位警探。警探可以直接从指挥部空降到 Magic Land 的任意一个城市里。此操作记为“L x”，表示在编号为 x 的城市里空降一位警探。耗时 1 秒。

2.  把留在某个城市里的一位警探直接召回指挥部。以备在以后的步骤中再度空降到某个城市里。此操作记为“B x”。表示把编号为 x 的城市里的一位警探召回指挥部。耗时 1 秒。

3.  让待在城市 x 的一位警探沿着公路移动到城市 y，此操作记为“M x y”。耗时 1 秒。当然，前提是城市 x 和城市 y 之间有公路。如果在警探移动的过程中，大盗 Frank 也在同一条公路上，那么警探就抓捕到了Frank。

现在，由你来制定一套追捕计划，也就是给出若干个步骤，需要保证：无论大盗 Frank 一开始躲在哪儿，也无论 Frank 在整个过程中如何狡猾地移动（Frank大盗可能会窃取到追捕行动的计划书，所以他一定会想尽办法逃避），他一定会被缉拿归案。

希望参与的警探越少越好，因为经验丰富的警探毕竟不多。

例如对于前面所给的那个图示格局，一个可行的计划如下：

1.  L 2 在城市 2 空降一位警探。注意这一步完成之后，城市 2 里不会有 Frank，否则他将被捉住。

2.  L 2 再在城市 2 空降一位警探。

3.  M 2 1 让城市 2 的一位警探移动到城市 1。注意城市 2 里还留有另一位警探。这一步完成之后，城市 1 里不会有 Frank，公路 A 上也不会有 Frank。也就是说，假如 Frank 还没有被逮捕，那么他只能是在城市 3 或城市 4 里，或者公路 B 或公路 C 上。

4.  B 1 召回城市 1 的一位警探。注意虽然召回了这位警探，但是由于我们始终留了一位警探在城市 2 把守，所以 Frank 仍然不可能跑到城市 1 或者是公路 A 上。

5.  L 3 在城市 3 空降一位警探。注意这一步可以空降在此之前被召回的那位警探。这一步完成之后，城市 3 里不会有 Frank，否则他会被捉住。

6.  M 3 2 让城市 3 里的一位警探移动到城市 2。这一步完成之后，如果 Frank 还没有被捉住，那他只能是在公路 C 上或者城市 4 里。注意这一步之后，城市 2 里有两位警探。

7.  M 2 4 让城市 2 里的一位警探移动到城市 4。这一步完成之后，Frank 一定会被捉住，除非他根本就没来 Magic Land。

这个计划总共需要 2 位警探的参与。可以证明：如果自始至终只有 1 名或者更少的警探参与，则 Frank 就会逍遥法外。

你的任务很简单：对于一个输入的 Magic Land 的格局，计算 S，也就是为了追捕 Frank 至少需要投入多少位警探，并且给出相应的追捕计划步骤。

inputFormat:
输入文件给出了 Magic Land 的格局。

第一行一个整数 N，代表有 N 个城市，城市的编号是 1~N。

接下来 N-1 行，每行有两个用空格分开的整数 x i ，y i ，代表城市 x i ，y i之间有公路相连。保证 1≤x i ,y i ≤N

outputFormat:
向输出文件输出你所给出的追捕计划。

第一行请输出一个整数 S，代表追捕计划需要多少位警探。

第二行请输出一个整数 T，代表追捕计划总共有多少步。

接下来请输出 T 行，依次描述了追捕计划的每一步。每行必须是以下三种形式之一：

”L x”，其中 L 是大写字母，接着是一个空格，再接着是整数 x，代表在城市 x 空降一位警探。你必须保证 1≤x≤N。

“B x”，其中 B 是大写字母，接着是一个空格，再接着是整数 x，代表召回城市 x 的一位警探。你必须保证 1≤x≤N，且你的计划执行到这一步之前，城市 x 里面确实至少有一位警探。

“M x y”，其中 M 是大写字母，接着是一个空格，再接着是整数 x，再跟一个空格，最后一个是整数 y。代表让城市 x 的一位警探沿着公路移动到城市 y。你必须保证 1≤x, y≤N，且你的计划执行到这一步之前，城市 x 里面确实至少有一位警探，且城市 x, y 之前确实有公路。

必须保证输出的 S 确实等于追捕计划中所需要的警探数目。

hint:
对于任何一个测试点：

如果输出的追捕计划不合法，或者整个追捕计划的步骤数 T 超过了 20000，或者追捕计划结束之后，不能保证捉住 Frank，则不能得分。

```cpp
否则，用你输出的 S 和我们已知的标准答案 S * 相比较：
1. 若 S<S * ，则得到 120%的分。
2. 若 S=S * ，则得到 100%的分。
3. 若 S * <S≤S * +2，则得到 60%的分。
4. 若 S * +2<S≤S * +4，则得到 40%的分。
5. 若 S * +4<S≤S * +8，则得到 20%的分。
6. 若 S>S * +8，则得到 10%的分。
```
输入保证描述了一棵连通的 N 结点树，1≤N≤1 000。


title: [NOI2006] 网络收费

background: noi2006 day1t1

description:
网络已经成为当今世界不可或缺的一部分。每天都有数以亿计的人使用网络进行学习、科研、娱乐等活动。然而，不可忽视的一点就是网络本身有着庞大的运行费用。所以，向使用网络的人进行适当的收费是必须的，也是合理的。

MY 市NS 中学就有着这样一个教育网络。网络中的用户一共有$2^N$个，编号依次为1, 2, 3, …, $2^N$。这些用户之间是用路由点和网线组成的。用户、路由点与网线共同构成一个满二叉树结构。树中的每一个叶子结点都是一个用户，每一个非叶子结点（灰色）都是一个路由点，而每一条边都是一条网线（见下图，用户结点中的数字为其编号）。

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

MY 网络公司的网络收费方式比较奇特，称为“ 配对收费 ”。即对于每两个用户$i, j (1≤i < j ≤2^N )$ 进行收费。由于用户可以自行选择两种付费方式A、B中的一种，所以网络公司向学校收取的费用与每一位用户的付费方式有关。该费用等于每两位不同用户配对产生费用之和。

为了描述方便，首先定义这棵网络树上的一些概念：

- 祖先：根结点没有祖先，非根结点的祖先包括它的父亲以及它的父亲的祖先；
- 管辖叶结点：叶结点本身不管辖任何叶结点，非叶结点管辖它的左儿子所管辖的叶结点与它的右儿子所管辖的叶结点；
- 距离：在树上连接两个点之间的用边最少的路径所含的边数。

对于任两个用户$i, j (1≤i<j≤2^N )$，首先在树上找到与它们距离最近的公共祖先：路由点$P$，然后观察$P$ 所管辖的叶结点（即用户）中选择付费方式A 与B的人数，分别记为$n_A$ 与$n_B$，接着按照网络管理条例第X 章第Y 条第Z 款进行收费（如下表），其中$F_{i,j}$ 为$i$ 和$j$ 之间的流量，且为已知量。

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

由于最终所付费用与付费方式有关，所以NS 中学的用户希望能够自行改变自己的付费方式以减少总付费。然而，由于网络公司已经将每个用户注册时所选择的付费方式记录在案，所以对于用户$i$，如果他/她想改变付费方式（由A 改为B 或由B 改为A），就必须支付$C_i$ 元给网络公司以修改档案（修改付费方式记录）。

现在的问题是，给定每个用户注册时所选择的付费方式以及$C_i$，试求这些用户应该如何选择自己的付费方式以使得NS 中学支付给网络公司的总费用最少（更改付费方式费用+配对收费的费用）。

inputFormat:
输入文件中第一行有一个正整数N。

第二行有$2^N$ 个整数，依次表示$1$ 号，$2$ 号，…，$2^N$ 号用户注册时的付费方式，每一个数字若为`0`，则表示对应用户的初始付费方式为A，否则该数字为`1`，表示付费方式为B。

第三行有$2^N$ 个整数，表示每一个用户修改付费方式需要支付的费用，依次为$C_1$, $C_2$, …,$C_M$。( M=$2^N$ )

以下 $2^N$-1 行描述给定的两两用户之间的流量表F，总第(i + 3)行第j 列的整数为$F_{i, j+i}$ 。（1≤i<$2^N$，1≤j≤$2^N$ – i）

所有变量的含义可以参见题目描述。

outputFormat: 你的程序只需要向输出文件输出一个整数，表示NS 中学支付给网络公司的最小总费用。（单位：元）

hint:
【样例说明】

将 1 号用户的付费方式由B 改为A，NS 中学支付给网络公司的费用达到最小。

【数据范围】

40%的数据中$N≤4$；
80%的数据中$N≤7$；
100%的数据中$N≤10$，$0≤F_{i, j}≤500$，$0≤C_i≤500 000$。


title: [Code+#1] 晨跑

description:
“无体育，不清华”、“每天锻炼一小时，健康工作五十年，幸福生活一辈子”

在清华，体育运动绝对是同学们生活中不可或缺的一部分。为了响应学校的号召，模范好学生王队长决定坚持晨跑。不过由于种种原因，每天都早起去跑步不太现实，所以王队长决定每$a$天晨跑一次。换句话说，假如王队长某天早起去跑了步，之后他会休息$a-1$天，然后第$a$天继续去晨跑，并以此类推。

王队长的好朋友小钦和小针深受王队长坚持锻炼的鼓舞，并决定自己也要坚持晨跑。为了适宜自己的情况，小钦决定每$b$天早起跑步一次，而小针决定每$c$天早起跑步一次。

某天早晨，王队长、小钦和小针在早起跑步时相遇了，他们非常激动、相互鼓励，共同完成了一次完美的晨跑。为了表述方便，我们把三位同学相遇的这天记为第$0$天。假设三位同学每次晨跑的时间段和路线都相同，他们想知道，下一次三人在跑步时相遇是第几天。由于三位同学都不会算，所以希望由聪明的你来告诉他们答案。

inputFormat: 输入共一行，包含三个正整数$a,b,c$，表示王队长每隔$a$天晨跑一次、小钦每隔$b$天晨跑一次且小针每隔$c$天晨跑一次。

outputFormat: 输出共一行，包含一个正整数$x$，表示三位同学下次将在第$x$天相遇。

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

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/何昊天 命题/何昊天 验题/卢政荣

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。


title: [Code+#1] 木材

description: 有 $n$ 棵树，初始时每棵树的高度为 $H_i$，第 $i$ 棵树每月都会长高 $A_i$。现在有个木料长度总量为 $S$ 的订单，客户要求每块木料的长度不能小于  $L$，而且木料必须是整棵树（即不能为树的一部分）。现在问你最少需要等多少个月才能满足订单。

inputFormat:
第一行 $3$ 个用空格隔开的非负整数 $n,S,L$，表示树的数量、订单总量和单块木料长度限制。

第二行 $n$ 个用空格隔开的非负整数，依次为 $H_1,H_2, ... ,H_n$。

第三行 $n$ 个用空格隔开的非负整数，依次为 $A_1,A_2, ... ,A_n$。

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

hint:
对于样例，在六个月后，各棵树的高度分别为 $14,47,56$，此时无法完成订单。

在七个月后，各棵树的高度分别为 $16,54,65$，此时可以砍下第 $2$ 和第 $3$ 棵树完成订单了。

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

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/郑林楷 命题/郑林楷 验题/王聿中

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。


title: [Code+#1] 找爸爸

description:
小 A 最近一直在找自己的爸爸，用什么办法呢，就是 DNA 比对。

小 A 有一套自己的 DNA 序列比较方法，其最终目标是最大化两个 DNA 序列的相似程度，具体步骤如下：

1. 给出两个 DNA 序列，第一个长度为 $n$，第二个长度为 $m$。

2. 在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同

3. 逐位进行匹配，**如果两个序列相同位置上的字符都不是空格**，假设第一个是 $x$，第二个是 $y$，那么他们的相似程度由 $d(x,y)$ 定义。对于两个序列中任意一段极长的长度为 $k$ 的连续空格，我们定义这段空格的相似程度为 $g(k)=-A-B(k-1)$。

那么最终两个序列的相似程度就是所有的 $d(x,y)$ 加上所有的极长空格段的相似程度之和。

现在小 A 通过某种奥妙重重的方式得到了小 B 的 DNA 序列中的一段，他想请你帮他算一下小 A 的 DNA 序列和小 B 的 DNA 序列的最大相似程度。

inputFormat:
输入第 $1$ 行一个字符串，表示小 A 的 DNA 序列。

输入第 $2$ 行一个字符串，表示小 B 的 DNA 序列。

接下来 $4$ 行，每行 $4$ 个整数，用空格隔开，表示 $d$ 数组，具体顺序如下所示。

```plain
d(A,A) d(A,T) d(A,G) d(A,C)
d(T,A) d(T,T) d(T,G) d(T,C)
d(G,A) d(G,T) d(G,G) d(G,C)
d(C,A) d(C,T) d(C,G) d(C,C)
```
最后一行两个用空格隔开的正整数 $A,B$，意义如题中所述。

outputFormat: 输出共一行，表示两个序列的最大相似程度。

hint:
### 样例解释

首先，将序列补成如下形式（"-"代表空格）

```cpp
ATGG--
AT--CC
```
然后所有 $d(x,y)$ 的和为 $d(A,A)+d(T,T)=10$

所有极长连续空格段的相似程度之和为 $g(2)+g(2)=-6$

总和为 $4$，可以验证，这是相似程度最大的情况。

对于所有测试点，有 $0< B<A \le 1000, -1000\le d(x,y)\le 1000,d(x,y)=d(y,x)$，序列只包含${A,T,G,C}$四种字符。

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

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/卢政荣 命题/卢政荣 验题/何昊天

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。