title: [ZJOI2010] 基站选址

description: 有 $N$ 个村庄坐落在一条直线上，第 $i(i>1)$ 个村庄距离第 $1$ 个村庄的距离为 $D_i$。需要在这些村庄中建立不超过 $K$ 个通讯基站，在第 $i$ 个村庄建立基站的费用为 $C_i$。如果在距离第 $i$ 个村庄不超过 $S_i$ 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 $i$ 个村庄没有被覆盖，则需要向他们补偿，费用为 $W_i$。现在的问题是，选择基站的位置，使得总费用最小。

inputFormat:
输入文件的第一行包含两个整数 $N,K$，含义如上所述。

第二行包含 $N-1$ 个整数，分别表示 $D_2,D_3,\cdots,D_N$ ，这 $N-1$ 个数是递增的。

第三行包含 $N$ 个整数，表示 $C_1,C_2,\cdots,C_N$。

第四行包含 $N$ 个整数，表示 $S_1,S_2,\cdots,S_N$。

第五行包含 $N$ 个整数，表示 $W_1,W_2,\cdots,W_N$。

outputFormat: 输出文件中仅包含一个整数，表示最小的总费用。


title: [ZJOI2010] 排列计数

type: P

description:
称一个 $1 \sim n$ 的排列 $p_1,p_2, \dots ,p_n$ 是 Magic 的，当且仅当
$$\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor}$$
计算 $1 \sim n$ 的排列中有多少是 Magic 的，答案可能很大，只能输出模 $m$ 以后的值。

inputFormat: 一行两个整数 $n,m$，含义如上所述。

outputFormat: 输出文件中仅包含一个整数，表示 $1\sim n$ 的排列中， Magic 排列的个数模 $m$ 的值。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^6$, $1\le m \le 10^9$，$m$ 是一个质数。


title: [ZJOI2008] 骑士

description:
Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。

最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。

骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。

战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。

为了描述战斗力，我们将骑士按照 $1$ 至 $n$ 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

inputFormat:
第一行包含一个整数 $n$，描述骑士团的人数。

接下来 $n$ 行，每行两个整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

outputFormat: 应输出一行，包含一个整数，表示你所选出的骑士军团的战斗力。

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

对于 $30\%$ 的测试数据，满足 $n \le 10$；

对于 $60\%$ 的测试数据，满足 $n \le 100$；

对于 $80\%$ 的测试数据，满足 $n \le 10 ^4$。

对于 $100\%$ 的测试数据，满足 $1\le n \le 10^6$，每名骑士的战斗力都是不大于 $10^6$ 的正整数。


title: [ZJOI2010] 任务安排

description:
小 Y 最近遇到了一个棘手的问题。她有两项任务需要完成，其中第一项任务是重复操作 $1$（下文称作 op1）共 $S_1$ 次，第二项任务是重复操作 $2$（下文称作 op2）共 $S_2$ 次。为了完成这些任务，小 Y 雇佣了 $N$ 名工人。其中，第 $i$ 个工人完成 op1 所需时间为 $T_{1,i}$，完成 op2 所需时间为 $T_{2,i}$。每个 op1 和 op2 都只能被一名工人完成，每名工人在任意时刻都只能做一项工作。

所有的工人从第 $0$ 秒开始工作。每当一个工人开始执行一项操作（op1 或 op2），他必须一直执行下去直到完成而不能被打断。我们记第一项任务完成的时间为 $E_1$，第二项任务完成的时间为 $E_2$，你的任务就是安排这些工人的工作，使得 $E_1+E_2$ 最小。

inputFormat:
输入文件的第一行包含一个整数 $T$，表示输入文件中数据的组数。

每个测试数据的第一行包含三个整数 $N,S_1,S_2$，含义如上文所述。

接下来的 $N$ 行每行包含两个整数 $T_{1,i},T_{2,i}$，分别表示第 $i$ 个工人完成 op1 和 op2 所需的时间。

outputFormat: 输出文件包含 $T$ 行，每行只有一个整数，表示你找到的 $E_1+E_2$ 的最小值。

hint:
### 样例说明

第一组数据中，唯一的工人首先执行 $2$ 次 op1，在第 $20$ 秒完成任务一 $(E_1=20)$。然后执行 $2$ 次 op2，在第 $80$ 秒完成任务二 $(E_2=80)$。因此答案为 $20+80=100$。

第二组数据中，工人 $\#1$ 连续执行 $5$ 次 op1，在第 $50$ 秒完成任务一 $(E_1=50)$，工人 $#2$ 执行 $7$ 次 op2，在第 $112$ 秒完成任务二 $(E_2=112)$。因此答案为 $50+112=162$。

第三组数据和第二组数据类似。

第四组数据中，工人 $\#2$ 首先连续执行 $6$ 次 op2，在第 $18$ 秒完成任务二 $(E_2=18)$。于此同时，工人 $#3$ 执行 $3$ 次 op1，同样在第 $18$ 秒完成。此时还需要执行一次 op1，因此让工人 $#2$ 去执行最后一次 op1，在第 $23$ 秒完成任务一 $(E_1=23)$ 、因此答案为 $18+23=41$。

### 数据范围及约定

对于 $100\%$ 的数据，$1 \le T \le 7$，$1 \le N \le 100$，$1 \le S_1,S_2 \le 7$，$1 \le T_{1,i},T_{2,i} \le 10^6$。


title: [ZJOI2012] 数列

description:
小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式：

$$a_0=0,a_1=1,a_{2i}=a_i,a_{2i+1}=a_i+a_{i+1}$$

小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数 $n$，小白则说出 $a_n$ 的值，如果当 $n$ 很大时小白仍能很快的说出正确答案，这就说明小白的确得到了公式。但这个方法有一个很大的漏洞：小蓝自己不会做，没法验证小白的答案是否正确。作为小蓝的好友，你能帮帮小蓝吗？

inputFormat:
输入文件第一行有且只有一个正整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行一个整数 $n$。

outputFormat: 对于每组数据：输出一行一个整数代表 $a_n$。


title: yyy 棋

description:
uim 最近在研究一种游戏，叫做“ yyy 棋”。

这种游戏的规则很简单，就是有一个 $A \times B$ 的棋盘和黑白两色的棋子，两个人轮流在下在格子里面。你可以下黑棋或者白棋，中途可以更换颜色，可以下在任何你喜欢的地方，但是要符合以下条件：

1. 这个位置不能已经被别的棋子占用。

2. 你准备下的地方，上下左右一格范围中不能有和你准备下的颜色一样的棋子。

3. 第一个下的人必须出黑子。

当谁没有地方可以放子，谁就输了。

uim 把你拉了出来，希望你好好地陪他玩。

由于你很忙不太情愿，uim 就让步了，允许你选择先手或者后手。

你突然灵光一现，想到了你小学奥数做到的一个问题：两个人坐在一张桌子的两边，轮流往桌子上放硬币，硬币不能重叠，谁放不下谁就输了。感觉有点类似，所以，你打算借鉴这个办法。

你知道，通过某种策略，你一定是 $100\%$ 赢的。

既然如此，就让 uim 输个痛快吧。

inputFormat:
第一行，$A, B$，两个整数，表示棋盘大小

接下来若干行为 uim 依次下的顺序，每行三个整数 $x_i, y_i, c_i$，分别表示位置和颜色，颜色 $1$ 为黑，$0$ 为白。位置 $1 \le x_i \le A$，$  1 \le y _ i \le B$。

如果 uim 发现没地方可走，就可能会耍赖，将棋子下在了不合法的地方。遇到这种情况，你也要指出。当然 uim 也有可能知道自己输了后就不下了。不存在游戏胜负还没定 uim 就投降的情况。

outputFormat:
第一行，选择先手还是后手，先手请输出 `First`，后手输出 `Second`。

接下来几行，如果你是第一个下子的，请输出你的第一步下法。然后对 uim 的下的每一个子做出回应。输出 $x _ i \ y _ i \ c _ i$，意思和上面相同。

**你必须输出必胜的下法，否则你将 `WA` 这个点。**

如果多个下法都是必胜点，请输出个能够尽早结束游戏的下法。

**在你下完这个子之前，请假装你不知道uim的下一步走法。**

如果 uim 耍赖，那么这一行输出 `Buwanle` 并结束程序，多余的输入就不管它了。

hint:
$40\%$ 数据，$2 \le A, B \le 3$。

$100\%$ 数据，$2 \le A, B \le 9$。

然而作为月赛的第一题，自然是简单的。因为标程的核心代码只有 $6$ 行。并不需要使用什么复杂算法就可以得到答案。


title: [ZJOI2012] 小蓝的好友

background:
终于到达了这次选拔赛的最后一题，想必你已经厌倦了小蓝和小白的故事。

为了回馈各位比赛选手，此题的主角是贯穿这次比赛的关键人物——小蓝的好友。

在帮小蓝确定了旅游路线后，小蓝的好友也不会浪费这个难得的暑假。

与小蓝不同，小蓝的好友并不想将时间花在旅游上，而是盯上了最近发行的即时战略游戏——SangoCraft。

但在前往通关之路的道路上，一个小游戏挡住了小蓝的好友的步伐。

description:
“国家的战争其本质是抢夺资源的战争”是整款游戏的核心理念，这个小游戏也不例外。

简单来说，用户需要在一块 $R\times C$ 的长方形土地上选出一块子矩形。

而系统随机生成了 $N$ 个资源点，第 $i$ 个资源点的坐标为 $(x_i,y_i)$。

位于用户所选的长方形土地上的资源点越多，给予用户的奖励也越多。

悲剧的是，小蓝的好友虽然拥有着极其优秀的能力，但同时也有着极差的 RP，小蓝的好友所选的区域总是没有一个资源点。

终于有一天，小蓝的好友决定投诉这款游戏的制造厂商，为了搜集证据，小蓝的好友想算出至少包含一个资源点的区域的数量。

具体的说，你需要计算有多少个四元组 $(LB,DB,RB,UB)$ 满足 $1\le LB\le RB\le R,1\le DB\le UB\le C$ ，且存在一个 $i$ 使得 $LB\le xi\le RB,DB\le yi\le UB$ 均成立。

作为小蓝的好友，这自然是你分内之事。

inputFormat:
第一行三个正整数 $R,C,N$。

接下来有 $N$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 个资源点的坐标。

outputFormat: 一行一个整数，表示至少包含一个资源点的区域的数量。

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

- 对于 $20\%$ 的数据，$N\le 50$。
- 对于 $40\%$ 的数据，$N\le 2\times 10^3$。
- 对于 $100\%$ 的数据，$1\le R,C\le 4\times 10^4$，$1\le N\le 10^5$，题目保证资源点的位置两两不同，且位置为随机生成。


title: [ZJOI2012] 波浪

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

阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮，他兴奋地叫个不停。而阿米巴则很淡定，他回想起曾经的那些日子，事业的起伏，情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来，简直什么都不算。

于是，这对好朋友不可避免地产生了分歧。为了论证自己的观点，小强建立了一个模型。他海面抽象成一个 $1$ 到 $N$ 的排列 $P_{1\ldots N}$。定义波动强度等于相邻两项的差的绝对值的和，即：

$$L = | P_2 – P_1 | + | P_3 – P_2 | +\ldots + | P_N – P_{N-1} |$$

给你一个 $N$ 和 $M$，问：随机一个 $1\ldots N$ 的排列，它的波动强度不小于 $M$ 的概率有多大？

答案请保留小数点后 $K$ 位输出，四舍五入。

inputFormat: 第一行包含三个整数 $N, M$ 和 $K$，分别表示排列的长度，波动强度，输出位数。

outputFormat: 第一行包含一个小数点后 $K$ 位的实数。


title: 【模板】有理数取余

description:
给出一个有理数 $c=\frac{a}{b}$，求 $c \bmod 19260817$ 的值。

这个值被定义为 $bx\equiv a\pmod{19260817}$ 的解。

inputFormat:
一共两行。

第一行，一个整数 $a$。
第二行，一个整数 $b$。

outputFormat: 一个整数，代表求余后的结果。如果无解，输出 `Angry!`。

tags: 扩展欧几里德算法,exgcd


title: 入阵曲

background:
pdf题面和大样例链接：http://pan.baidu.com/s/1cawM7c 密码：xgxv

```cpp
丹青千秋酿，一醉解愁肠。
无悔少年枉，只愿壮志狂。
```

description:
小 F 很喜欢数学，但是到了高中以后数学总是考不好。

有一天，他在数学课上发起了呆；他想起了过去的一年。一年前，当他初识算法竞赛的 时候，觉得整个世界都焕然一新。这世界上怎么会有这么多奇妙的东西？曾经自己觉得难以 解决的问题，被一个又一个算法轻松解决。

小 F 当时暗自觉得，与自己的幼稚相比起来，还有好多要学习的呢。

一年过去了，想想都还有点恍惚。

他至今还能记得，某天晚上听着入阵曲，激动地睡不着觉，写题写到鸡鸣时分都兴奋不 已。也许，这就是热血吧。

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

也就是在那个时候，小 F 学会了矩阵乘法。让两个矩阵乘几次就能算出斐波那契数列的 第 $10^{100}$ 项，真是奇妙无比呢。

不过，小 F 现在可不想手算矩阵乘法——他觉得好麻烦。取而代之的，是一个简单的小 问题。他写写画画，画出了一个 $n \times m$ 的矩阵，每个格子里都有一个不超过 $k$ 的正整数。

小 F 想问问你，这个矩阵里有多少个不同的子矩形中的数字之和是 $k$ 的倍数？ 如果把一个子矩形用它的左上角和右下角描述为 $(x_1,y_1,x_2,y_2)$，其中$x_1 \le x_2,y_1 \le y_2$； 那么，我们认为两个子矩形是不同的，当且仅当他们以 $(x_1,y_1,x_2,y_2)$ 表示时不同；也就是 说，只要两个矩形以 $(x_1,y_1,x_2,y_2)$ 表示时相同，就认为这两个矩形是同一个矩形，你应该 在你的答案里只算一次。

inputFormat:
从标准输入中读入数据。

输入第一行，包含三个正整数 $n,m,k$。

输入接下来 $n$ 行，每行包含 $m$ 个正整数，第 $i$ 行第 $j$ 列表示矩阵中第 $i$ 行第 $j$ 列 中所填的正整数 $a_{i,j}$。

outputFormat:
输出到标准输出中。

输入一行一个非负整数，表示你的答案。

hint:
【样例 1 说明】

这些矩形是符合要求的： (1, 1, 1, 3)，(1, 1, 2, 2)，(1, 2, 1, 2)，(1, 2, 2, 3)，(2, 1, 2, 1)，(2, 3, 2, 3)。

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解 决一部分测试数据。

每个测试点的数据规模及特点如下表：

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

特殊性质：保证所有 $a_{i,j}$ 均相同。


title: 计算器弹琴

description:
总所周知，计算器可以拿来干很多它本不应该干的事情，比如写作文。（参看洛谷P2549）

小A发现了一个计算器的另一个隐藏功能——弹琴。

http://www.bilibili.com/video/av2205500/

如果按上一个键，比如说1，就会发出中音“Do”。

这边给出按键音高表

```cpp
+ 低音Fa
< 低音So
* 低音La
/ 低音Xi
1 中音Do
2 中音Re
3 中音Mi
4 中音Fa
5 中音So
6 中音La
7 高音Xi
8 高音Do
9 高音Re
= 高音Mi
% 高音Fa
C 高音So
M 高音La
```
现在小A搞到了一份乐谱——我们称为计算器谱，一种变形的简谱。

时值（也就是按的时间长度）是这么记录的，例如：

1 是四分音符，占1拍。

1- 是二分音符，占2拍。

1--- 是全音符，占四拍。

对于小于四分音符的音符，我们用嵌套括号表示，例如

(1(34(56))2)

1和2在一层括号中，是八分音符，占0.5拍。

3和4在两层括号中，是16分音符，占0.25拍。

5和6在三层括号中，是32分音符，占1/8拍。当然实际上比较少见。

括号中不会出现‘-’这个符号。

不会出现四层或以上的括号。

在一个音符后面添加一个附点即“.”表示这个音符延长1/2倍。

例如
1-.是3拍，1.是1.5拍，(3.(45.))3是3/4拍，4是1/4拍，5是3/8拍。

附点不会连续添加两个或以上，也不会出现超过四拍的音符。

不考虑其他的乐理符号。

另外整个乐谱会给一个速度，整数，意思是一分钟多少拍。

为了美观，乐谱可以随便换行、添加空格。这个忽略即可。

现在小A想知道，按完这个谱子，需要多少时间（单位：秒）

inputFormat:
第一行，两个整数n,T，表示谱子行数以及速度（拍每分）

接下来n行，给出乐谱。

outputFormat: 一个整数，表示演奏需要花费的时间，单位秒，舍去小数部分。

hint:
样例1说明：（一共32拍，每分钟60拍，所以是32秒。对了，这是欢乐颂的开头部分）

样例2说明：（一共80拍，别问我怎么数的，一分钟120拍的话，是40秒。至于这是什么曲子？根据相关的法律政策，该部分未予显示。）

http://bd.kuwo.cn/yinyue/4641527

对于40%的数据，没有附点没有括号

对于100%的数据，括号层数不会超过3层，不超过100行，每行不超过100个字符。

对于其中的一个数据，是《千本樱》。


title: 大海战

background: 一天，GD和MW正在玩一款名叫大海战的游戏。

description:
游戏在一个 $1 \times n$ 的棋盘上进行。一开始 GD 拥有 $c$ 种战舰，每种战舰的宽度为 $1$，长度为 $c_i$，共有 $t_i$ 个。GD 要将所有这些战舰放置在棋盘上，并且任意两艘战舰间不能重叠（但可以相邻）。

接下来，MW 进行 $q$ 次“攻击”，每次攻击一个 $1 \times 1$ 的格子，而 MW 将告知他这次攻击是否“打中”了一艘战舰（或者它的某个部分）。

令人疑惑的是，每次 MW 都告诉 GD 说他没有打中任何一艘战舰，而这显然是不现实的。现在 MW 把整个游戏的过程告诉了你，他想知道，最早在他的第几次询问之后，可以断定 GD 一定（至少有一次）说了谎。

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

第一行一个整数 $t$，表示测试数据的组数。

每组数据的输入格式如下：

每组数据的第一行有三个整数，分别代表棋盘的长度 $n$ 、战舰的种数 $c$ 和攻击的次数 $q$。

对于每组数据的第 $2$ 到第 $(c + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的两个整数分别代表第 $i$ 种战舰的长度 $c_i$ 和数量 $t_i$。

第 $(c + 2)$ 行有 $q$ 个整数，第 $i$ 个整数 $a_i$ 代表 MW 第 $i$ 次攻击的位置。

outputFormat: 对于每组数据，输出一个整数 $ans$，表示最早在第 $ans$ 次操作后可以断定 GD 说了谎。特别地，如果一开始就不可能按要求摆上所有的战舰，输出 $0$；如果 $q$ 次询问后都不能判断 GD 是否说了谎，则输出 $-1$。

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

- 对于第一个样例，存在布阵 $\{1,22,22,0,22,22,22\}$（$0$ 表示没有放置），使得第一次不会受到攻击；不存在一个布阵使得两次都没有受到攻击。
- 对于第二个样例，存在布阵 $\{0,333,0\}$，使得两次均不会受到攻击。
- 对于第三个样例，一开始就不可能把所有战舰合法地布置在棋盘上。

---

#### 数据规模与约定

- 对于测试点1，$n \leq 1000000000$，$c \leq 100000$，$q=0$；
- 对于测试点2、3，所有的 $t_i$ 均为 $1$；
- 对于测试点2-8，$n \leq 400000$，$c \leq 100$，$q=1$；
- 对于测试点9，$n \leq 100$，$c=1$，$q \leq 100$；
- 对于测试点10-14，$n \leq 200000$，$c=1$，$q \leq 200000$；
- 对于测试点15、16，$n \leq 200$，$c=2$，$q \leq 200$；
- 对于测试点17-20，$n \leq 4000$，$c=2$，$q \leq 4000$。
- 对于 $100\%$ 的数据，$1 \le t \le 5,n \ge 1,c \ge 1,q \ge 0,1 \le q_i \le n,0 \le c_i \le 10^5,0 \le t_i \le 10^5$。

---

#### 提示

- 请注意常数因子对程序效率造成的影响。


title: [USACO10JAN] Buying Feed, II S

description:
Farmer John needs to travel to town to pick up K (1 <= K <= 100) pounds of feed. Driving D miles with K pounds of feed in his truck costs D\*K cents.

The county feed lot has N (1 <= N <= 100) stores (conveniently numbered 1..N) that sell feed. Each store is located on a segment of the X axis whose length is E (1 <= E <= 350). Store i is at location X\_i (0 < X\_i < E) on the number line and can sell FJ as much as F\_i (1 <= F\_i <= 100) pounds of feed at a cost of C\_i (1 <= C\_i <= 1,000,000) cents per pound. Amazingly, a given point on the X axis might have more than one store.

FJ starts at location 0 on this number line and can drive only in the positive direction, ultimately arriving at location E, with at least K pounds of feed. He can stop at any of the feed stores along the way and buy any amount of feed up to the the store's limit.

What is the minimum amount FJ has to pay to buy and transport the K pounds of feed? FJ knows there is a solution.

Consider a sample where FJ needs two pounds of feed from three stores (locations: 1, 3, and 4) on a number line whose range is 0..5:

```
0   1   2   3   4   5
+---|---+---|---|---+
    1       1   1      Available pounds of feed
    1       2   2      Cents per pound
```
It is best for FJ to buy one pound of feed from both the second and third stores. He must pay two cents to buy each pound of feed for a total cost of 4. When FJ travels from 3 to 4 he is moving 1 unit of length and he has 1 pound of feed so he must pay 1\*1 = 1 cents.

When FJ travels from 4 to 5 he is moving one unit and he has 2 pounds of feed so he must pay 1\*2 = 2 cents.

The total cost is 4+1+2 = 7 cents.

FJ 开车去买 $K$ 份食物，如果他的车上有 $X$ 份食物。每走一里就花费 $X$ 元。FJ 的城市是一条线，总共 $E$ 里路，有 $E+1$ 个地方，标号 $0\sim E$。 FJ 从 $0$ 开始走，到 $E$ 结束（不能往回走），要买 $K$ 份食物。 城里有 $N$ 个商店，每个商店的位置是 $X_i$（一个点上可能有多个商店），有 $F_i$ 份食物，每份 $C_i$ 元。 问到达 $E$ 并买 $K$ 份食物的最小花费。


title: [NOIP2015 提高组] 神奇的幻方

background: NOIp2015 提高组 Day1T1

description:
幻方是一种很神奇的 $N\times N$ 矩阵：它由数字 $1,2,3,\cdots \cdots ,N \times N$ 构成，且每行、每列及两条对角线上的数字之和都相同。

当 $N$ 为奇数时，我们可以通过下方法构建一个幻方：

首先将 $1$ 写在第一行的中间。

之后，按如下方式从小到大依次填写每个数 $K \ (K=2,3,\cdots,N \times N)$ ：

1. 若 $(K-1)$ 在第一行但不在最后一列，则将 $K$ 填在最后一行， $(K-1)$ 所在列的右一列；
2. 若 $(K-1)$ 在最后一列但不在第一行，则将 $K$ 填在第一列， $(K-1)$ 所在行的上一行；
3. 若 $(K-1)$ 在第一行最后一列，则将 $K$ 填在 $(K-1)$ 的正下方；
4. 若 $(K-1)$ 既不在第一行，也不在最后一列，如果 $(K-1)$ 的右上方还未填数，则将 $K$ 填在 $(K-1)$ 的右上方，否则将 $K$ 填在 $(K-1)$ 的正下方。

现给定 $N$ ，请按上述方法构造 $N \times N$ 的幻方。

inputFormat: 一个正整数 $N$，即幻方的大小。

outputFormat: 共 $N$ 行，每行 $N$ 个整数，即按上述方法构造出的 $N \times N$ 的幻方，相邻两个整数之间用单空格隔开。

hint: 对于 $100\%$ 的数据，对于全部数据， $1 \leq N \leq 39$ 且 $N$ 为奇数。


title: 将军令

background:
> 历史/落在/赢家/之手
> 至少/我们/拥有/传说
> 谁说/败者/无法/不朽
> 拳头/只能/让人/低头
> 念头/却能/让人/抬头
> 抬头/去看/去爱/去追
> 你心中的梦

description:
又想起了四月。

如果不是省选，大家大概不会这么轻易地分道扬镳吧？  只见一个又一个昔日的队友离开了机房。

凭君莫话封侯事，一将功成万骨枯。

梦里，小 F 成了一个给将军送密信的信使。

现在，有两封关乎国家生死的密信需要送到前线大将军帐下，路途凶险，时间紧迫。小 F 不因为自己的祸福而避趋之，勇敢地承担了这个任务。

不过，小 F 实在是太粗心了，他一不小心把两封密信中的一封给弄掉了。

小 F 偷偷打开了剩下的那封密信。他 发现一副十分详细的地图，以及几句批文——原来 这是战场周围的情报地图。他仔细看后发现，在这张地图上标记了 n 个从 1 到 n 标号的 驿站，n − 1 条长度为 1 里的小道，每条小道双向连接两个不同的驿站，并且驿站之间可以 通过小道两两可达。

小 F 仔细辨认着上面的批注，突然明白了丢失的信的内容了。原来，每个驿站都可以驻 扎一个小队，每个小队可以控制距离不超过 k 里的驿站。如果有驿站没被控制，就容易产 生危险——因此这种情况应该完全避免。而那封丢失的密信里，就装着朝廷数学重臣留下的 精妙的排布方案，也就是用了最少的小队来控制所有驿站。

小 F 知道，如果能计算出最优方案的话，也许他就能够将功赎过，免于死罪。他找到了 你，你能帮帮他吗？  当然，小 F 在等待你的支援的过程中，也许已经从图上观察出了一些可能会比较有用的 性质，他会通过一种特殊的方式告诉你。

inputFormat:
从标准输入中读入数据。

输入第 1 行一个正整数 n,k,t，代表驿站数，一支小队能够控制的最远距离，以及特 殊性质所代表的编号。关于特殊性质请参照数据范围。

输入第 2 行至第 n 行，每行两个正整数 $u_i$,$v_i$，表示在 $u_i$ 和 $v_i$ 间，有一条长度为 一里的小道。

outputFormat:
输出到标准输出中。

输出一行，为最优方案下需要的小队数。

hint:
【样例 1 说明】

如图。由于一号节点到周围的点距离均是 1，因此可以控制所有驿站。

【样例 2 说明】

如图，和样例 1 类似。

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

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解 决一部分测试数据。

关于 t 的含义如下： t = 0：该测试点没有额外的特殊性质；  t = 1：保证最多 8 个点的所连接的小道超过 1 条； t = 2：保证所有点到 1 号点的距离不超过 2。

每个测试点的数据规模及特点如下表

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


title: 星空

background:
pdf题面和大样例链接：http://pan.baidu.com/s/1cawM7c 密码：xgxv

```cpp
命运偷走如果只留下结果， 时间偷走初衷只留下了苦衷。
你来过，然后你走后，只留下星空。
```

description:
逃不掉的那一天还是来了，小 F 看着夜空发呆。

天上空荡荡的，没有一颗星星——大概是因为天上吹不散的乌云吧。

心里吹不散的乌云，就让它在那里吧，反正也没有机会去改变什么了。

小 C 拿来了一长串星型小灯泡，假装是星星，递给小 F，想让小 F 开心一点。不过，有着强迫症的小 F 发现，这串一共 $n$ 个灯泡的灯泡串上有 $k$ 个灯泡没有被点亮。小 F 决定和小 C 一起把这个灯泡串全部点亮。

不过，也许是因为过于笨拙，小 F 只能将其中连续一段的灯泡状态给翻转——点亮暗灯泡，熄灭亮灯泡。经过摸索，小 F 发现他一共能够翻转 $m$ 种长度的灯泡段中灯泡的状态。

小 C 和小 F 最终花了很长很长很长很长很长很长的时间把所有灯泡给全部点亮了。他们想知道他们是不是蠢了，因此他们找到了你，让你帮忙算算：在最优的情况下，至少需要几次操作才能把整个灯泡串给点亮？

inputFormat:
从标准输入中读入数据。

输入第 $1$ 行三个正整数 $n,k,m$。

输入第 $2$ 行 $k$ 个正整数，第 $i$ 个数表示第 $i$ 个被没点亮的灯泡的位置 $a_i$。

输入第 $3$ 行 $m$ 个正整数，第 $i$ 个数表示第 $i$ 种操作的长度 $b_i$。

保证所有 $b_i$ 互不相同；保证对于 $1\le i<k$，有 $a_i<a_{i+1}$；保证输入数据有解。

outputFormat:
输出标准输入中。

输出一行一个非负整数，表示最少操作次数。

hint:
【样例 1 解释】

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

【数据范围与约定】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解 决一部分测试数据。

每个测试点的数据规模及特点如下表

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

特殊性质：保证答案小于 4


title: [国家集训队] 等差子序列

description:
给一个 $1$ 到 $N$ 的排列 $\{A_i\}$，询问是否存在

$$1 \le p_1<p_2<p_3<p_4<p_5<…<p_{Len} \le N (Len \ge 3)$$

使得 $Ap_1,Ap_2,Ap_3,\cdots,Ap_{Len}$ 是一个等差序列。

inputFormat:
输入的第一行包含一个整数 $T$，表示组数。

下接 $T$ 组数据，每组第一行一个整数 $N$，每组第二行为一个 $1$ 到 $N$ 的排列，数字两两之间用空格隔开。

outputFormat: 对于每组数据，如果存在一个等差子序列，则输出一行 Y，否则输出一行 N。

hint:
对于后 $20$ 个测试点的数据，$1 \leq N \leq10000,T\leq 7$，时限 2s。

对于前 $5$ 个测试点的数据，$1 \leq N \leq 5\times 10^5,T \leq 5$，时限 5s。


title: [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目

background: NOIP2017 提高组 D1T1

description:
小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？

注意：输入数据保证存在小凯无法准确支付的商品。

inputFormat: 两个正整数 $a$ 和 $b$，它们之间用一个空格隔开，表示小凯中金币的面值。

outputFormat: 一个正整数 $N$，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。

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

小凯手中有面值为 $3$ 和 $7$ 的金币无数个，在不找零的前提下无法准确支付价值为 $1,2,4,5,8,11$ 的物品，其中最贵的物品价值为 $11$，比 $11$ 贵的物品都能买到，比如：

$12 = 3 \times 4 + 7 \times 0$；

$13 = 3 \times 2 + 7 \times 1$；

$14 = 3 \times 0 + 7 \times 2$；

$15 = 3 \times 5 + 7 \times 0 $。

【数据范围与约定】

对于 $30\%$ 的数据： $1 \le a,b \le 50 $。

对于 $60\%$ 的数据： $1 \le a,b \le 10^4 $。

对于$ 100\%$ 的数据：$1 \le a,b \le 10^9 $。


title: [NOIP2017 提高组] 时间复杂度

background: NOIP2017 提高组 D1T2

description:
小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序， 于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下：

```cpp
F i x y
    循环体
E
```

其中`F i x y`表示新建变量 $i$（变量 $i$ 不可与未被销毁的变量重名）并初始化为 $x$， 然后判断 $i$ 和 $y$ 的大小关系，若 $i$ 小于等于 $y$ 则进入循环，否则不进入。每次循环结束后 $i$ 都会被修改成 $i +1$，一旦 $i$ 大于 $y$ 终止循环。

$x$ 和 $y$ 可以是正整数（$x$ 和 $y$ 的大小关系不定）或变量 $n$。$n$ 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 $100$。

`E` 表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母 $\operatorname O$ 表示通常意义下 $Θ$ 的概念。

inputFormat:
输入文件第一行一个正整数 $t$，表示有 $t$（$t \le 10$）个程序需要计算时间复杂度。 每个程序我们只需抽取其中 `F i x y` 和 `E` 即可计算时间复杂度。注意：循环结构允许嵌套。

接下来每个程序的第一行包含一个正整数 $L$ 和一个字符串，$L$ 代表程序行数，字符串表示这个程序的复杂度，`O(1)` 表示常数复杂度，`O(n^w)` 表示复杂度为 $n^w$，其中 $w$ 是一个小于 $100$ 的正整数，输入保证复杂度只有 `O(1)` 和 `O(n^w)` 两种类型。

接下来 $L$ 行代表程序中循环结构中的`F i x y`或者 `E`。 程序行若以`F`开头，表示进入一个循环，之后有空格分离的三个字符（串）`i x y`， 其中 $i$ 是一个小写字母（保证不为$n$），表示新建的变量名，$x$ 和 $y$ 可能是正整数或 $n$ ，已知若为正整数则一定小于 $100$。

程序行若以`E`开头，则表示循环体结束。

outputFormat:
输出文件共 $t$ 行，对应输入的 $t$ 个程序，每行输出 `Yes` 或 `No` 或者 `ERR`，若程序实际复杂度与输入给出的复杂度一致则输出 `Yes`，不一致则输出 `No`，若程序有语法错误（其中语法错误只有: ① `F` 和 `E` 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出 `ERR`。

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 `ERR`。

samples:
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

hint:
【输入输出样例解释 $1$】

第一个程序 $i$ 从 $1$ 到 $1$ 是常数复杂度。

第二个程序 $x$ 从 $1$ 到 $n$ 是 $n$ 的一次方的复杂度。

第三个程序有一个 `F` 开启循环却没有 `E` 结束，语法错误。

第四个程序二重循环，$n$ 的平方的复杂度。

第五个程序两个一重循环，$n$ 的一次方的复杂度。

第六个程序第一重循环正常，但第二重循环开始即终止（因为 $n$ 远大于 $100$，$100$ 大于 $4$）。

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量 $x$ 与第一重循环中的变量重复，出现语法错误②，输出 `ERR`。

【数据规模与约定】

对于 $30\%$ 的数据：不存在语法错误，数据保证小明给出的每个程序的前 $L/2$ 行一定为以 `F` 开头的语句，第 $L/2+1$ 行至第 $L$ 行一定为以 `E` 开头的语句，$L  \le 10$，若 $x$、$y$ 均为整数，$x$ 一定小于 $y$，且只有 $y$ 有可能为 $n$。

对于 $50\%$ 的数据：不存在语法错误，$L  \le 100$，且若 $x$、$y$ 均为整数，$x$ 一定小于 $y$， 且只有 $y$ 有可能为 $n$。

对于 $70\%$ 的数据：不存在语法错误，$L  \le 100$。

对于 $100\%$ 的数据：$L  \le 100$。

---
如果需要Hack请私信@zhouyonglong或发讨论，提供数据和能Hack掉的本题的AC记录。


title: [国家集训队] Tree I

description:
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 $need$ 条白色边的生成树。

题目保证有解。

inputFormat:
第一行 $V,E,need$ 分别表示点数，边数和需要的白色边数。

接下来 $E$ 行，每行 $s,t,c,col$ 表示这边的端点（点从 $0$ 开始标号），边权，颜色（$0$ 白色 $1$ 黑色）。

outputFormat: 一行，表示所求生成树的边权和。

hint:
对于 $5\%$ 的数据，$V\leq 10$。

对于另 $15\%$ 的数据，$V\leq 15$。

对于 $100\%$ 的数据，$V\leq 5\times10^4,E\leq 10^5$。

所有数据边权为 $[1,100]$ 中的正整数。

By WJMZBMR


title: 弹幕考察

background: zeromaker 是个手残，但是他喜欢玩东方 project，ex 什么的最喜欢了

description: zeromaker 对弹幕的视野控制有着深刻的研究。 每个弹幕在一段特定的时间内会出现在 zeromaker 的视野内，除此之外的时间都在 zeromaker 看不到的地方。在 zeromaker 看来，视野内的弹幕数量越多，图就越难，因为这意味着 @#￥%。 现在，zeromaker 想要评测这张图的难度，他已经知道了每个弹幕会在什么时候出现在视野内，他想知道，在一段时间内，总共有多少个弹幕出现在他的视野内过。

inputFormat:
第一行有两个整数 $n$ ， $m$ ,表示一共有 $n$ 个弹幕，而 zeromaker 有 $m$ 个问题。

接下来 $n$ 行，每行两个数 $a$，$b$，表示这个弹幕 $a$ 秒时出现在 zeromaker 的视野内，出现了 $b$ 秒。 接下来 $m$ 行，每行两个整数 $x$ ， $y$ ，表示从 $x$ 秒开始，经过 $y$ 秒，其中有多少个弹幕出现过。

注意：查询区间为**左闭右闭**，弹幕出现区间为**左开右开**。

outputFormat: $m$ 行，即对于 zeromaker 提出的每个问题的答案。


title: 虫洞

background: applepi 想进行宇宙旅行。当然，applepi 知道这是有可能的，因为 applepi 的特殊能力能使他观测到宇宙中的虫洞。所谓虫洞就是一个在三维之外的维度打开的快捷通道，通过虫洞能够从一个地方瞬间移动到另外一个地方。

description:
为了简化问题，我们建立一个一维坐标系，地球的位置为 $0$，而applepi 的目的地的位置是一个正整数 $W$。

在每一个单位时间里，applepi 可以向正方向移动不超过 $S$ 的一个整数。虫洞可以被表示为二元组 $(B, E)$，即如果在某次移动之后 applepi 在位置 $B$，那么 applepi 就会被立刻传送到位置 $E$。

注意，applepi 在移动过程中如果经过位置 $B$，由于applepi 的速度极快是不会被传送的。而且，applepi 不能够向负方向移动，但是虫洞引起的除外。

现在applepi 想请你帮助他计算一下他至少需要多少个单位时间才能够到达目的地。

inputFormat:
输入包含多组测试数据。

每组测试数据的第一行是三个正整数 $W,S,P$，表示目的地位置，移动限制和虫洞的数目。之后 $P$ 行，每行两个整数 $B$ 和 $E$，表示一个虫洞。

输入文件的最后一行是一个整数 $0$，表示输入的结束。

outputFormat: 对于每组测试数据，在单独的一行内输出结果。

hint:
对于 $30\%$ 的数据，$W≤1000$。

对于 $100\%$ 的数据，$W≤10^9$，$2≤S≤6$，$1≤P≤40$，没有 $B = 0$ 或者 $B = W$ 的虫洞，输入数据保证目的地可达。


title: 关灯问题II

description:
现有 $n$ 盏灯，以及 $m$ 个按钮。每个按钮可以同时控制这 $n$ 盏灯——按下了第 $i$ 个按钮，对于所有的灯都有一个效果。按下 $i$ 按钮对于第 $j$ 盏灯，是下面 $3$ 中效果之一：如果 $a_{i,j}$ 为 $1$，那么当这盏灯开了的时候，把它关上，否则不管；如果为 $-1$ 的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是 $0$，无论这灯是否开，都不管。

现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。

inputFormat:
前两行两个数，$n, m$。

接下来 $m$ 行，每行 $n$ 个数 $,a_{i, j}$ 表示第 $i$ 个开关对第 $j$ 个灯的效果。

outputFormat: 一个整数，表示最少按按钮次数。如果没有任何办法使其全部关闭，输出 $-1$。

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

- 对于 $20\%$ 数据，输出无解可以得分。
- 对于 $20\%$ 数据，$n \le 5$。
- 对于 $20\%$ 数据，$m \le 20$。

上面的数据点可能会重叠。

对于 $100\%$ 数据 $n \le 10,m \le 100$。


title: 《瞿葩的数字游戏》T1-数字王国的门神

background: 一来到数字王国的大门，我们就看到硕大的两个数字8和9分别镭射(请不要吐槽这个词...)在两侧大门。于是瞿葩心想，这有什么意义呢？于是他找到了你。

description:
鬼知道89有什么意义啊TAT，但是瞿葩知道，89是Fibonacci数列的第二个非孪生质数。(还有哦，因为89被镭射在了门上...所以之后的故事(题目)中都不会出现89...但是这道题要计算89)

那么看来这个现象与Fibonacci数列有关系咯，所以现在瞿葩想知道，Fibonacci数列的累积和中的第M位到第N位，累积和就是第1项\*10^(K)到第K项\*10^1的总和，即

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

请你写一个程序帮帮他。

任务：给定M、N，要求输出累积和的第M~N位。

一开始的累积和：1123595505...

inputFormat: 两个整数M~N

outputFormat: 累积和第M~第N位数字，不省略首尾的0。

hint: 当然有10<=M<=N<=200000，因为前10位瞿葩已经算出来了，知道200000以后的数字位也没什么用是吧 \(^o^)/而且瞿葩只想研究一点点，所以其中0<N-M+1<=2000。不过正是因为瞿葩最多只要得到2000位结果，所以他要求你的程序要在1s内出结果。


title: 物品选取

background: 小X确信所有问题都有个多项式时间算法，为了证明，他决定自己去当一次旅行商，在上路之前，小X需要挑选一些在路上使用的物品，但他只有一个能装体积为m的背包。显然，背包问题对小X来说过于简单了，所以他希望你来帮他解决这个问题。

description:
小X可以选择的物品有n样，一共分为甲乙丙三类：

 1．甲类物品的价值随着你分配给他的背包体积变化，它的价值与分配给它的体积满足函数关系式，v(x) = A\*x^2-B\*x，A，B是每个甲类物品的两个参数。注意每个体积的甲类物品只有一个。

 2．乙类物品的价值A和体积B都是固定的，但是每个乙类物品都有个参数C，表示这个物品可供选择的个数。

 3．丙类物品的价值A和体积B也是固定的，但是每个丙类物品可供选择的个数都是无限多个。

你最终的任务是确定小X的背包最多能装有多大的价值上路。

inputFormat:
第一行两个整数n，m，表示背包物品的个数和背包的体积；

 接下来n行，每行描述一个物品的信息。第一个整数x，表示物品的种类：

若x为1表示甲类物品，接下来两个整数A, B，为A类物品的两个参数；

若x为2表示乙类物品，接下来三个整数A，B，C。A表示物品的价值，B表示它的体积，C表示它的个数；

若x为3表示丙类物品，接下来两个整数A，B。A表示它的价值，B表示它的体积。

outputFormat: 输出文件仅一行为一个整数，表示小X的背包能装的最大价值。


title: [HNOI2008] 明明的烦恼

background: 原 编译优化 参见P1792

description:
自从明明学了树的结构,就对奇怪的树产生了兴趣......
给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

inputFormat: 第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

outputFormat: 一个整数,表示不同的满足要求的树的个数,无解输出0


title: Count on a tree

description:
给定一棵 $n$ 个节点的树，每个点有一个权值。有 $m$ 个询问，每次给你 $u,v,k$，你需要回答 $u \text{ xor last}$ 和 $v$ 这两个节点间第 $k$ 小的点权。

其中 $\text{last}$ 是上一个询问的答案，定义其初始为 $0$，即第一个询问的 $u$ 是明文。

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

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

后面 $n-1$ 行每行两个整数 $x,y$，表示点 $x$ 到点 $y$ 有一条边。

最后 $m$ 行每行三个整数 $u,v,k$，表示一组询问。

outputFormat: $m$ 行，每行一个正整数表示每个询问的答案。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n,m \le 10^5$，点权在 $[1, 2 ^ {31} - 1]$ 之间。

暴力自重。。。

来源：bzoj2588 Spoj10628.

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


title: 好消息，坏消息

description:
Uim 在公司里面当秘书，现在有 $n$ 条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于老板之前的心情加上这条消息的好坏度。最开始老板的心情是 $0$，一旦老板心情到了 $0$ 以下就会勃然大怒，炒了 Uim 的鱿鱼。

Uim 为了不被炒，提前知道了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望知道如何才能不让老板发怒。

Uim 必须按照事件的发生顺序逐条将消息告知给老板。不过 Uim 可以使用一种叫 “倒叙” 的手法，例如有 $n$ 条消息，Uim 可以按 $k,k+1,k+2,\ldots,n,1,2,\ldots,k-1$（事件编号）这种顺序通报。

他希望知道，有多少个 $k$，可以使从 $k$ 号事件开始通报到 $n$ 号事件然后再从 $1$ 号事件通报到 $k-1$ 号事件可以让老板不发怒。

inputFormat:
第一行一个整数 $n$（$1 \le n \le10^6$），表示有 $n$ 个消息。

第二行 $n$ 个整数，按时间顺序给出第 $i$ 条消息的好坏度 $A_i$（$-10^3\le A_i \le 10^3$）。

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

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

通报事件的可行顺序（用编号表示）为 $2\rightarrow3\rightarrow4\rightarrow1$ 或 $3\rightarrow4\rightarrow1\rightarrow2$（分别对应 $k=2$ 和 $k=3$）

通报事件的可行顺序（用好坏度表示）为 $5\rightarrow1\rightarrow2\rightarrow(-3)$ 或 $1\rightarrow2\rightarrow(-3)\rightarrow5$

**【数据范围】**

对于 $25\%$ 的数据，$n\le10^3$；
对于 $75\%$ 的数据，$n\le10^4$；
对于 $100\%$ 的数据，$1 \le n\le 10^6$。


title: 豪华游轮

description:
有一条豪华游轮（其实就是条小木船），这种船可以执行 $4$ 种指令：

`right X`：其中 $X$ 是一个 $1$ 到 $719$ 的整数，这个命令使得船顺时针转动 $X$ 度。

`left X`：其中 $X$ 是一个 $1$ 到 $719$ 的整数，这个命令使得船逆时针转动 $X$ 度。

`forward X`：其中 $X$ 是一个整数（$1$ 到 $1000$），使得船向正前方前进 $X$ 的距离。

`backward X`：其中 $X$ 是一个整数（$1$ 到 $1000$），使得船向正后方前进 $X$ 的距离。

随意的写出了 $n$ 个命令，找出一个种排列命令的方法，使得船最终到达的位置距离起点尽可能的远。

inputFormat:
第一行一个整数 $n (1 \leq n \leq 50)$，表示给出的命令数。

接下来 $n$ 行，每行表示一个命令。

outputFormat: 一个浮点数，能够走的最远的距离，四舍五入到 $6$ 位小数。


title: [USACO11OPEN] Mowing the Lawn G

description:
在一年前赢得了小镇的最佳草坪比赛后，Farmer John 变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farmer John 希望能够再次夺冠。

然而，Farmer John 的草坪非常脏乱，因此，Farmer John 只能够让他的奶牛来完成这项工作。Farmer John 有 $N$（$1\le N\le 10^5$）只排成一排的奶牛，编号为 $1\ldots N$。每只奶牛的效率是不同的，奶牛 $i$ 的效率为 $E_i$（$0\le E_i\le 10^9$）。

靠近的奶牛们很熟悉，因此，如果 Farmer John安排超过 $K$ 只连续的奶牛，那么，这些奶牛就会罢工去开派对 :)。因此，现在 Farmer John 需要你的帮助，计算 FJ 可以得到的最大效率，并且该方案中没有连续的超过 $K$ 只奶牛。

inputFormat:
第一行：空格隔开的两个整数 $N$ 和 $K$。

第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $E_i$。

outputFormat: 第一行：一个值，表示 Farmer John 可以得到的最大的效率值。


title: 冒险岛

background: 冒险岛是费老师新开发的一种情景模拟电脑的游戏，通过掷骰子（1~6个数字之间），让一种人物（棋子）在棋纸上从左至右的行走，从而模拟冒险的故事……

description:
棋纸上有一条从左至右的很长的路，整条路是一连串符号组成，表明路的状况，棋子必须在符号组成的路上行走。每掷一下骰子得到的数字，棋子就可以走掷得的数字所对应的步数，比如掷3，就可以走3步。

路上有两种特殊符号可以改变棋子的行走。

一种是“>”符号，一旦棋子走完了掷骰子的步数，最终停留在这个符号上，后面有紧跟着2个以上“>”，那么棋子就可以获得前进奖励，可以沿着“>”一直一步步前进，直到遇到一个不是“>”的符号位置停下来。

还有一种是“\*”符号，一旦棋子走完了掷骰子的步数，最终停留在这个符号上，后面又紧跟着两个以上“\*”，就要受到后退惩罚，需要退后k步，这个k步就是从当前“\*”开始的连续的“\*”的数量。

每次掷数后，奖励或惩罚至多一次，如果奖励或惩罚后棋子又落在第二种特殊符号上，则不能再受到奖励或惩罚。

如果走的棋子超出棋纸右边界最后一个符号，则停在最后一个符号上；如果超出左边界，则停在第一个符号上。

若干次掷骰子后，请问游戏中的人物（棋子）走到了哪步？离终点还差几步？

inputFormat:
第一行为一个字符串s，字符串中的每个字符表示棋纸的路的状况。

第二行是一个n，表示掷了n次骰子。

第三行是n个整数（1~6的范围），表明掷了n次骰子得到的数字，数字之间有一个空格。

outputFormat: 只有两个数字，表明目前所在符号的序号和离终点符号的步数，数子中间有一个空格。注意输出末尾有换行。

hint:
【样例说明】

在游戏中，第一次掷的是5，则走到第一个>的位置，获得奖励前进至左起第二个f处。第二次掷的是6，则走到\*的位置，受惩罚退3步，至d处。第三次掷的是6，则走至左起第四个>号处，获奖励前进至f。最终棋子停留的符号是第20个（从左至右的数），离终点符号d（含）相差5步数。

【数据范围】

对于50%的数据，1<=s的长度<=255,0<=n<=1000。

对于100%的数据，256<=s的长度<=1000000,0<=n<=100000。


title: 图像变换

description:
给定 $3$ 行 $3$ 列的图像各像素点灰度值，给定最终图像，求最短、字典序最小的操作序列。

其中，可能的操作及对应字符有如下四种：

`A`：顺时针旋转 $90$ 度；

`B`：逆时针旋转 $90$ 度；

`C`：左右翻转；

`D`：上下翻转。

inputFormat:
一个矩阵，表示初始的图像。

一个矩阵，表示最终的图像。

outputFormat:
最短、字典序最小的操作序列，保证长度不超过 $10^8$，不保证有解。

若长度不超过 $10^8$ 无解则输出 `Poland cannot into space!!!` 。

hint: 字符串长度不超过 $10^8$。


title: 带通配符的字符串匹配

background:
通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(\*)等，其中，“?”可以代替一个字符，而“\*”可以代替零个或多个字符。

现又定义一个通配符“@”，规定在一个字符串中，“@”代替的字符个数是固定的。

description: 用户在使用“@”时，当然希望输入的“@”越少越好。现在给出一个带有“?”“\*”通配符的字符串和一个原字符串，要求首先判断通配符字符串与原字符串是否匹配，若匹配则求出将原通配符字符串中的“?”“\*”字符替换为“@”且保证修改后的通配符字符串与原字符串匹配，最少需要多少个通配符“@”。

inputFormat:
输入文件第一行为一个字符串，描述通配符字符串；

第二行也为一个字符串，描述原字符串。

outputFormat: 输出文件第一行为一个字符串，若通配符字符串与原字符串能够匹配则输出“matched”，并在接下来的一行输出一个整数，描述最少需要的通配符“@”的数量；若不匹配则输出“not matched”。

hint:
【样例说明1】

两字符串显然可以匹配，通配符字符串1\*456??可以替换为1@@@456@，最少需要4个“@”，其中每个“@”代替两个字符，可以证明，此为最优情况。

通配符字符串1\*456??也可以替换为1@@@@@@456@@，此时每个“@”代替一个字符，需要8个“@”，没有上面的情况优。

【样例说明2】

两字符串不可以匹配。

【数据范围】

对于100%的数据，字符串的长度均小于3000。

保证原字符串中仅出现字母和数字，通配符字符串中仅出现字母、数字和通配符“?”“\*”，且保证匹配方式唯一。


title: [国家集训队] 聪聪可可

description:
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。

他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 $n$ 个“点”，并用 $n-1$ 条“边”把这 $n$ 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随机选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 $3$ 的倍数，则判聪聪赢，否则可可赢。

聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

inputFormat: 输入的第 $1$ 行包含 $1$ 个正整数 $n$。后面 $n-1$ 行，每行 $3$ 个整数 $x,y,w$，表示 $x$ 号点和 $y$ 号点之间有一条边，上面的数是 $w$。

outputFormat: 以即约分数形式输出这个概率（即 `a/b` 的形式，其中 $a$ 和 $b$ 必须互质。如果概率为 $1$，输出 `1/1`）。


title: [NOIP2017 提高组] 逛公园

background: NOIP2017 D1T3

description:
策策同学特别喜欢逛公园。公园可以看成一张 $N$ 个点 $M$ 条边构成的有向图，且没有 自环和重边。其中 $1$ 号点是公园的入口，$N$ 号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从 $1$ 号点进去，从 $N$ 号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 $1$ 号点 到 $N$ 号点的最短路长为 $d$，那么策策只会喜欢长度不超过 $d + K$ 的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对 $P$ 取模。

如果有无穷多条合法的路线，请输出 $-1$。

inputFormat:
第一行包含一个整数 $T$, 代表数据组数。

接下来 $T$ 组数据，对于每组数据： 第一行包含四个整数 $N,M,K,P$，每两个整数之间用一个空格隔开。

接下来 $M$ 行，每行三个整数 $a_i,b_i,c_i$，代表编号为 $a_i,b_i$ 的点之间有一条权值为 $c_i$ 的有向边，每两个整数之间用一个空格隔开。

outputFormat: 输出文件包含 $T$ 行，每行一个整数代表答案。


title: [NOIP2017 普及组] 图书管理员

background: NOIP2017 普及组 T2

description: 图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。 每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。 小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出 `-1`。

inputFormat:
第一行，包含两个正整数 $n , q$，以一个空格分开，分别代表图书馆里 书的数量和读者的数量。

接下来的 $n$ 行，每行包含一个正整数，代表图书馆里某本书的图书编码。

接下来的 $q$ 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆 里读者的需求码的长度，第二个正整数代表读者的需求码。

outputFormat: $ q$ 行，每行包含一个整数，如果存在第 $i$ 个读者所需要的书，则在第 $i$ 行输出第 $i$ 个读者所需要的书中图书编码最小的那本书的图书编码，否则输出$-1$。

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

对于 $20\%$ 的数据，$1 ≤ n ≤ 2$。

另有 $20\%$ 的数据，$q = 1$。

另有 $20\%$ 的数据，所有读者的需求码的长度均为 $1$。

另有 $20\%$ 的数据，所有的图书编码按从小到大的顺序给出。

对于 $100\%$ 的数据，$1 ≤ n ≤ 1000,1 ≤ q ≤ 1000$，所有的图书编码和需求码均不超过 $10^7$。


title: [NOIP2017 普及组] 成绩

background: NOIP2017 普及组 T1

description:
牛牛最近学习了 C++ 入门课程，这门课程的总成绩计算方法是：

$$
\text{总成绩}=\text{作业成绩}\times 20\%+\text{小测成绩}×30\%+\text{期末考试成绩} \times 50\%
$$

牛牛想知道，这门课程自己最终能得到多少分。

inputFormat: 三个非负整数 $A,B,C$，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是 $100$ 分。

outputFormat: 一个整数，即牛牛这门课程的总成绩，满分也是 $100$ 分。


title: Explorer

background: 提示：本题数据较水，通过本题不代表程序/做法完全正确。

description: 给出两条直线，上面分别有 $n,m$ 个点，求这 $n+m$ 个点组成的最小生成树。

inputFormat:
输入包括 $5$ 行。

第一行为 $n$ 和 $m$。

第二行为四个整数 $AX,AY,BX,BY$。

第三行为四个整数 $CX,CY,DX,DY$。

第四行为 $n$ 个实数，代表在第一条直线上的n个点。对于某个点，用一个实数 $t$ 来表示该点的坐标为 $(AX\times t + BX \times (1 - t), AY \times t + BY \times (1 - t))$。

第五行为 $m$ 个实数，代表第二条直线上的 $m$ 个点，表示方法同上。

outputFormat: 一行一个实数，为其最小生成树长度，四舍五入至三位小数。


title: 密码破解者

background: 1941 年 12 月 7 日凌晨，珍珠港驻守美军通信员截获了一份日军电报。早上 8 时日军的正式进攻就会展开，为了减少太平洋战场伤亡，你被指派去协助破解密文。情报部门已得知了密文加密的层数和每层加密的方法。由于时间紧急，你只剩 1 秒的时间来破解日军的密文。

description:
据情报得知日军共有 $3$ 种加密方式：

一、栅栏密码：

所谓栅栏密码，就是把要加密的明文分成 $L$ 个一组，然后把每组的第 $1$ 个字连起来，形成一段无规律的话。一般比较常见的是 $2$ 栏的棚栏密码。

比如明文：`THERE IS A CIPHER`
去掉空格后变为：`THEREISACIPHER`
两个一组，得到：`TH ER EI SA CI PH ER`
先取出第一个字母：`TEESCPE`
再取出第二个字母：`HRIAIHR`
连在一起就是：`TEESCPEHRIAIHR`

这样就得到我们需要的密码了。

但也可能有更多的栏数。

注：若明文长度不能整除栏数，则分组后剩下的单独为一组，如：

`THERE IS A CIPHER`，$3$ 栏加密分组为：`THE REI SAC IPH ER`

先后取出第一二三个字母(最后一组只能取前两个)，加密后为: `TRSIE HEAPR EICH`（去掉空格）。

二、维吉尼亚(Vigenère)密码：

维吉尼亚密码首先应用了“密钥”的思想，其在密码届具有十分重要的意义。

在密码学中，我们称需要加密的信息为明文，用 $M$ 表示；称加密后的信息为密文，用 $C$ 表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为 $k$。在 Vigenère 密码中，密钥 $k$ 是一个字母串，$k=k_1k_2\cdots k_n$。当明文 $M=m_1m_2\cdots m_n$ 时，得到的密文 $C=c_1c_2\cdots c_n$，其中 $c_i=m_i\oplus k_i$，运算 $\oplus$ 的规则如下表所示：

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C -C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D -D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E -E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F -F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G -G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H -H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I -I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J -J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K -K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M -M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N -N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O -O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P -P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q -Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R -R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S -S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T -T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U -U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V -V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W -W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X -X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y -Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Vigenère 加密在操作时需要注意：

当明文 M 的长度大于密钥 k 的长度时，将密钥 k 重复使用。

例如，明文 M=Helloworld，密钥 k=abc 时，密文 C=Hfnlpyosnd。

三、QWE键盘码：

随着键盘普及，也出现了相应的键盘码。

这是一个常见的键盘,在左边字母区有三行字母分别为：

QWERTYUIOP

ASDFGHJKL

ZXCVBNM

从第一排第一列开始分别用Q替代A，W替代B……M替代Z以此类推。

如 CODING 加密后即为 EGROFU.

这对于现在来说算是简单的加密方法，但对于键盘不普及的二战时期却是一大难题。

inputFormat:
输入第一行为一个正整数N 表示截获的密文共用了N重密码加密。

第二行为一个字符串S表示加密后的密文。

以下3-N+2行共N行每行开头一个正整数K(1<=K<=3)表示对应的加密方式。

给出的加密方式按顺序给出，即给出的第I重加密为实际加密过程的第I重(1<=I<=N)。

若K=1则表示用栅栏密码加密，之后一个正整数L表示加密所用栏数。

若K=2则表示用维吉尼亚码加密，之后一个字符串T表示密钥。

若K=3则表示用QWE键盘码加密。

outputFormat: 共一行。一个字符串，表示破解N重加密后的明文。


title: 安全系统

description:
特斯拉公司的六位密码被轻松破解后，引发了人们对电动车的安全性能的怀疑。李华听闻后，自己设计了一套密码：

- 假设安全系统中有 $n$ 个储存区，每个储存区最多能存储存 $2$ 个种类不同的信号（可以不储存任何信号）。有 $0$ 和 $1$ 这两种信号，其中 $0$ 有 $a$ 个，$1$ 有 $b$ 个，单独一个 $0$ 或 $1$ 算一个信号。现要将这些信号储存在储存区中，$0$ 和 $1$ **可以不用全部储存**，一个存储区可以存放任意多个 $0$ 和任意多个 $1$。一种不同的储存方案经过李华处理后就将是一串不同的密码。

现在给出 $n,a,b$，求可能的不同储存方案的个数。

inputFormat: 第一行：共 $3$ 个整数，$n,a,b$。

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


title: 第一次，第二次，成交！

description:
因为奶牛们的节食运动给 FJ 余下了一大批干草无法处理，所以他准备要开一个拍卖会去出售他的干草。

他有 $n$ 批干草。他的客户有 $m$ 个，都是和他一样的农夫。第 $i$ 名农夫会告诉 FJ 他会为 FJ 的每批干草付 $p_i$ 的钱。每个农夫都想买（也只想买）FJ 的一批草料。

为了确保农夫们不会互相嫉妒，所以 FJ 决定要以一个固定的价格出售他的草料。每一个出价大于等于 FJ 的要价的农夫将会买到草料。

请你帮助 FJ 找出能让他卖出最多的钱的最低的单批草料的售价。

inputFormat:
第一行：两个被空格隔开的整数，$n$ 和 $m$。

第二行到第 $m+1$ 行：第 $i+1$ 行只包含一个整数：$p_i$。

outputFormat: 共一行，包含由空格隔开的两个整数：FJ 能出的每批草料的最低价格，以及他能赚到的最多的钱。

hint:
FJ 有 $5$ 批草料，$4$ 个农夫想要购买。他们出价分别为：每批草料为 $2$，$8$，$10$ 和 $7$。

FJ 应该把价格设定为 $7$，这样会有 $3$ 个农夫会付钱买草料，FJ 自己会挣到 $21$ 的钱。

---

对于 $100\%$ 的数据，$1\leq m, n\leq 1000$，$1\leq p_i\leq 1,000,000$。


title: [USACO09OCT] Bessie's Weight Problem G

description: Bessie 像她的诸多姊妹一样，因为从 Farmer John 的草地吃了太多美味的草而长出了太多的赘肉。所以 FJ 将她置于一个及其严格的节食计划之中。她每天不能吃多过 $H (5 \le H \le 45,000)$ 公斤的干草。 Bessie 只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的$N (1 \le N \le 500)$ 捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。 给定一个列表表示每捆干草的重量 $S_i (1 \le S_i \le H)$ , 求 Bessie 不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。

inputFormat:
第一行有两个由空格隔开的整数 $H$ 和 $N$。

第 $2$ 到第 $N+1$ 行，第 $i+1$ 行是一个单独的整数，表示第 $i$ 捆干草的重量 $S_i$。

outputFormat: 第一行一个单独的整数表示 Bessie 在限制范围内最多可以吃多少公斤的干草。

hint:
#### 输入说明

有四捆草，重量分别是 $15,19,20$ 和 $21$。Bessie 在 $56$ 公斤的限制范围内想要吃多少就可以吃多少。

#### 输出说明

Bessie 可以吃 $3$ 捆干草（重量分别为 $15, 20, 21$）。恰好达到她的 $56$ 公斤的限制。


title: 《瞿葩的数字游戏》T2-多边形数

background:
数字王国里有一类特殊的数，它们叫做多边形数。并且国王 $1$ 规定数字间的联姻只能在同为一种多边形数中进行。（请不要吐槽这个规定……）

瞿葩对这个现象十分好奇，见 $36$ 和 $10$ 这一对情侣在散步，便上前询问 $36$ 它是什么多边形数。可是 $36$ 拍拍脑门，想了想说：“我也不知道啊，你去问问国王吧。”

看来国民们并不知道自己是什么多边形数啊，国王 $1$ 急的发愁。国王 $1$ 只知道多边形数怎么计算，但是多边形数要怎么给国民做解释呢，干脆这样解释吧：可以排成正多边形的整数都是多边形数。当然多边形数可以分为三边（角）形数、四边形数（正方形数）、五边形数、六边形数……

description:
**此题为规律题，请自行寻找规律，以锻炼数学归纳能力！！**

我们拿三角形数做例子：图中的 $1$、$3$、$6$、$10$ 就是三角形数。

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

任务：求出 $N$ 是哪一种多边形数（假设 $N$ 是 $K$ 边形数），比如我们求出 $36$ 是三边形数和四边形数（貌似叫做三角形数和正方形数呵）。若不是多边形数，输出 Poor + 该数字。若同时是多种多边形数，输出最小的一个和第二小的一个。每个读入文件里有 $ng$ 组数据。

inputFormat: 先是一个数 $ng$，然后 $ng$ 行，每行一个整数。

outputFormat: $ng$ 行，$N$ 相应的 $K_1$ 和 $K_2$，若不是多边形数，输出 Poor + 该数字。（中间无空格）


title: [USACO4.3] 逢低吸纳Buy Low, Buy Lower

description:
“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:

"逢低吸纳,越低越买"

这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。

给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。

以下面这个表为例, 某几天的股价是:

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

股价 68 69 54 64 68 64 70 67 78 62 98 87

这个例子中, 聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法):

天数 2  5  6  10

股价 69 68 64 62

inputFormat:
第1行: N (1 <= N <= 5000), 表示能买股票的天数。

第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++).

outputFormat:
只有一行，输出两个整数：

能够买进股票的天数和长度达到这个值的股票购买方案数量

在计算方案的数量的时候，如果两个方案的股价序列相同，那么这样的两个方案被认为是相同的（只能算做一个方案）。因此，两个不同的天数序列可能产生同一个股价序列，这样只能计算一次。


title: 斯诺克

background: 镇海中学开设了很多校本选修课程，有体育类、音乐类、美术类、无线电测向、航空航海航天模型制作等，力争使每位学生高中毕业后，能学到一门拿得出手的兴趣爱好，为将来的终身发展打下基础。在体育类的校本选修课程中，有一门课程是斯诺克台球。

description:
斯诺克台球比赛中有21个球，其中有15个红球，6个彩球（黄、绿、棕、蓝、粉、黑）。甲乙二人轮流打球。打一个红球得1分，打一个彩球的得分如下：

黄球：2分；        绿球：3分；         棕球：4分；

蓝球：5分；        粉球：6分；         黑球：7分；

最后以得分高者为胜。

简化后的打球规则如下：

1．如果有红球，第奇数次必须打红球，打过的红球从桌面上拿走；

2．每打一个红球后，可以任意选一个彩球打，打红球后接着打的彩球不从桌面上拿走；

3. 如果桌面上已经没有红球可打了，那么按照分值从小到大的次序打彩球，这时候每打一个彩球都从桌面上拿走。

打球时犯规的判罚如下：

1. 没有打中球，给对方加4分；

2．没有按照打球规则打该打的球，即打中了错误的球时：

（1）如果这个错误的球的分值大于4，那么给对方加等于这个球的分值；

（2）如果这个错误的球的分值不大于4，那么给对方加4分；

打中的错误球不从桌面上拿走。

请统计某局比赛进行到现在为止的比分。

inputFormat:
输入有两行，第一行有二个整数n和m，表示甲打了n个球，乙打了m个球。n和m之间以一个空格分隔。

第二行，有n个以空格分隔的整数，表示甲的n次连续打球情况。

第三行，有m个以空格分隔的整数，表示乙的m次连续打球情况。

第二行和第三行中：

（1）1至7的整数表示打了相应分值的球；

（2）最后一个数字是0,表示没有打中球犯规，0只会出现在这二行的最后一个数字处；

（3）打了错误球的犯规也只会出现在这二行最后一个数字处；

输入数据保证是正确，不会出现打到桌面上不存在的球的情况，数据不必检验。

outputFormat: 输出仅有一行，该行有二个整数(互相之间以一个空格分隔)，表示比赛进行到现在为止甲乙二人的得分（先打的甲在前）。

hint:
【样例说明】

甲依次打了红球、黑球、红球、粉球，甲得15分（1+7+1+6）。

乙依次打了红球、黑球、红球，乙得9分（1+7+1）。

【数据范围】

80%的数据，每次总是打中球的，并且每次打中的球总是正确的，没有犯规情况。100%的数据，会有未打中或犯规情况。

保证输出不超过2^64-1.

没有什么难的，从头到尾除了判断就是循环，但是要特别细心，注意这道题强大的特判！


title: 神秘磁石

background: 在遥远的阿拉德大陆，有一种神秘的磁石，是由魔皇制作出来的，

description:
1. 若给他一个一维坐标系，那么他的磁力一定要在素数坐标的位置上才能发挥的最大（不管位置坐标的大小，只要是素数那么磁力就一样大）。
2. 若两个磁石相距为 $k$，那么磁石间的破坏力将会达到当前磁力的峰值

显然，两磁石间最大破坏力取决于磁力大小和磁石间距，那么请问给出长度不超过 $n$ 的一维坐标系，有哪几对坐标间磁石破坏力最大。

inputFormat: 两个正整数 $n,k$。

outputFormat: 所有小于等于 $n$ 的素数对。每对素数对输出一行，中间用单个空格隔开。若没有找到任何素数对，输出 `empty`。

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


title: 双子序列最大和

description: 给定一个长度为 $n$ 的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出最大和。一个连续子序列的和为该子序列中所有数之和。每个连续子序列的最小长度为 $1$，并且两个连续子序列之间至少间隔一个数。

inputFormat:
第一行是一个整数表示 $n$。

第二行是 $n$ 个整数表示整数序列。

outputFormat: 一个数，两个连续子序列的序列和之和。

hint:
对于 $30\%$ 的数据 $N\le 100$。

对于 $60\%$ 的数据有 $N\le 10000$。

对于 $100\%$ 的数据有 $N\le 1000000$。

数据保证运算过程不会超过 `long long`（`int64`）。


title: 机房中出了一只大触！

background: 机房中出了一只大触Kurunie！作为一只大触，它当然喜欢刷题。然而NOIp复赛临近，大触要抽出更多的时间来刷OI题，所以它就把一些简单的题目丢给你啦。

description:
显然，任何题目对于K触来说都是水题，倒是K触怕你不会写，于是给了你最最简单的化学卷子。

原来K触正在准备化学方程式配平大赛，所以卷子全都是配平练习题。

K触给你举了个简单的例子，比如下列物质在氧气中燃烧的化学方程式，要求配平：

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

K触当然知道这是绿原酸(C16H18O9)（O和0要分清楚哦），它在氧气中燃烧的方程式是：

C16H18O9+O2=CO2+H2O

什么？你说配平？这种简单的事情当然就交给你啦。

inputFormat:
一行一个字符串表示待配平的化学方程式。由一个等号隔开反应物和生成物，物质间用加号分隔。输

入的数字均在元素后面，作为下标。

outputFormat: 一行一个字符串表示配平后的化学方程式。不需要加沉淀或气体符号，

hint:
保证输入字符串长度小于等于50，字符串只包含大小写英文字母、数字、小括号、加号、等号。

涉及到的物质均不包含带结晶水。

涉及到的元素最多只有两个字母。

小括号中不会嵌套小括号。

配平后每种物质系数、原字符串中的所有下标均在32位带符号整数范围内。


title: 数数zzy

description: zzy 自从数学考试连续跪掉之后，上数学课就从来不认真听了（事实上他以前也不认真听）。于是他开始在草稿纸上写写画画，比如写一串奇怪的字符串。然后他决定理♂性♂愉♂悦♂一下：统计这串字符串当中共有多少个为 `zzy` 的子序列，**注意是子序列而非子串**。但是由于他写的字符串实在是太长啦，而且他是个超级大蒟蒻，根本就数不过来。所以他决定请求你这个超级大神犇的帮助。你可以帮帮他吗？

inputFormat: 一行仅含小写字母的字符串 $s$。

outputFormat: 一行，一个非负整数，表示输入的字符串中为 `zzy` 的子序列的个数。


title: 最大收益

description:
现在你面前有 $n$ 个物品，编号分别为 $1,2,3,\cdots,n$。你可以在这当中任意选择任意多个物品。其中第 $i$ 个物品有两个属性 $W_i$ 和 $R_i$，当你选择了第 $i$ 个物品后，你就可以获得 $W_i$ 的收益；但是，你选择该物品以后选择的所有物品的收益都会减少 $R_i$。现在请你求出，该选择哪些物品，并且该以什么样的顺序选取这些物品，才能使得自己获得的收益最大。

注意，收益的减少是会叠加的。比如，你选择了第 $i$ 个物品，那么你就会获得了 $W_i$ 的收益；然后你又选择了第 $j$ 个物品，你又获得了 $W_j-R_i$ 收益；之后你又选择了第 $k$ 个物品，你又获得了 $W_k-R_i-R_j$ 的收益；那么你获得的收益总和为 $W_i+(W_j-R_i)+(W_k-R_i-R_j)$。

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

接下来第 $2$ 行到第 $n+1$ 行，每行两个正整数 $W_i$ 和 $R_i$，含义如题目所述。

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

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

- $20\%$ 的数据满足：$n \le 5$，$0 \le W_i,R_i \le 1000$；
- $50\%$ 的数据满足：$n \le 15$，$0 \le W_i,R_i \le 1000$；
- $100\%$ 的数据满足：$n \le 3000$，$0 \le W_i,R_i \le 2\times 10^5$。

### 样例解释

我们可以选择 $1$ 号物品，获得了 $5$ 点收益；之后我们再选择 $2$ 号物品，获得 $3-2=1$ 点收益。最后总的收益值为 $5+1=6$。


title: 白金莲花池

background:
为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 $M$ 行 $N$ 列个方格（$1≤M,N≤30$）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝还可能掩藏着宝藏的水。

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

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

约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务，当然莲花不能种在岩石上。

description:
但是！约翰在种植莲花的时候发现了一件很有趣的事，有些格子是不能直接种植莲花的，原因是……实不相瞒，无法直接种植莲花的格子的泥土中大部分都是货真价实的铂金，正是它们妨碍了莲花的正常生长！而恰好约翰刚刚学到了铂金的开采方法，也有相关的开采工具，而且他还发现开采铂金后的格子就可以正常地种植莲花，不必担心泥土缺失的问题。（由于贝西迫切地想练习，所以约翰不会开采不打算种莲花的铂金格子）

开采铂金很累，就像是种植莲花一样累，它们都会消耗掉约翰 $1$ 点体力（也就是说想把铂金格子变成莲花格子需要 $2$ 点体力），约翰最初有 $P$ 点体力来种植莲花或开采铂金。

请帮助约翰计算至少需要消耗多少体力才能帮助贝西完成任务，这个数字记作 $S$，以及有多少种消耗这些体力的方法能帮助贝西完成任务，这个数字记作 $W_S$；铂金当然是越多越好，请计算在消耗 $S$ 点体力帮助贝西完成任务的同时最多能开采多少铂金，这个数字记作 $G$，以及消耗 $S$ 点体力开采 $G$ 块铂金帮助贝西完成任务的方法数，这个数字记作 $W_G$。

若在 $P$ 点体力内无法帮助到贝西，那么只输出 `-1`。

若在 $S$ 点体力内无法开采铂金，那么第二行只输出 `-1`。

inputFormat:
第一行：三个用空格分开的整数：$P$，$M$ 和 $N$

第二行到 $M+1$ 行：第 $i+1$ 行有 $N$ 个用空格分开的整数，描述了池塘第 $i$ 行的状态：

$0$ 为水，$1$ 为莲花，$2$ 为岩石，$3$ 为贝西所在的起点，$4$ 为贝西想去的终点，$5$ 为铂金的埋藏地。

outputFormat:
第一行：用空格分隔开 $S$ 和 $W_S$（两个整数，需要最少消耗的体力及方案数；如果无法帮助，输出 `-1`。）

第二行：用空格分隔开 $G$ 和 $W_G$（两个整数，在消耗最少的前提下开采最多的铂金数及方案数，若在 $S$ 点体力内无法开采铂金，第二行输出 `-1`。）

如果第一行是 `-1`，不要输出第二行。

保证输出的数字不会超过 `long long`。

hint: 约翰可以用开采到的铂金小赚一笔，但如果用多余的体力开采铂金而不往上种莲花的话贝西会很生气！


title: 赚钱

background: 改编自某题

description:
zzy现在决定环游中国，顺便赚点钱。zzy在一个城市最多只能赚D元，然后他可以选择退休也就是停止赚钱，或者去其它城市工作。当然，他可以在别处工作一阵子后又回到原来的城市再赚D元。这样的往返次数是没有任何限制的。

城市间有P条单向路径连接，共有C座城市，编号从1到C。路径i从城市Ai到城市Bi，在路径行走上不用任何花费。

zzy还可以乘飞机从某个城市飞到另一个城市。共有F条单向的航线，第i条航线是从城市Ji飞到另一座城市Ki，费用是Ti元。假如zzy身上没有现钱，他可以用以后赚的钱来付机票钱。

zzy可以从任何一个城市出发开始赚钱，并且选择在任何时候、任何城市退休。现在zzy想要知道，如果在工作时间上不做限制，那么zzy共可以赚多少钱呢？如果赚的钱也不会出现限制，那么就输出orz。

inputFormat:
第一行，4个用空格分开的正整数，D，P，C，F。

第二行到P+1行，第i+1行包含2个用空格分开的整数，表示一条从城市Ai到城市Bi的单向路径。

接下来的F行，每行3个用空格分开的正整数，表示一条从城市Ji到城市Ki的单向航线，费用为Ti。

outputFormat: 如果zzy赚的钱没有限制，输出orz。如果有限制，那么就输出在给定的规则下zzy最多可以赚到的钱数。


title: [SCOI2009] windy 数

background: windy 定义了一种 windy 数。

description: 不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

inputFormat: 输入只有一行两个整数，分别表示 $a$ 和 $b$。

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

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

对于全部的测试点，保证 $1 \leq a \leq b \leq 2 \times 10^9$。


title: 采蘑菇

description:
小胖和 ZYR 要去 ESQMS 森林采蘑菇。

ESQMS 森林间有 $N$ 个小树丛，$M$ 条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。小胖和 ZYR 经过某条小径一次，可以采走这条路上所有的蘑菇。由于 ESQMS 森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，再下取整。

比如，一条路上有 $4$ 个蘑菇，这条路的“恢复系数”为 $0.7$，则第一~四次经过这条路径所能采到的蘑菇数量分别为 $4,2,1,0$。

现在，小胖和 ZYR 从 $S$ 号小树丛出发，求他们最多能采到多少蘑菇。

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

第二行到第 $M+1$ 行，每行四个数，分别表示一条小路的起点，终点，初始蘑菇数，恢复系数。

第 $M+2$ 行，一个整数 $S$。

outputFormat: 一行一个整数，表示最多能采到多少蘑菇，保证答案不超过 $(2^{31}-1)$。

hint:
对于 $30\%$ 的数据，$N\le 7$，$M\le15$

另有 $30\%$ 的数据，满足所有“恢复系数”为 $0$。

对于 $100\%$ 的数据，$1
\le N\le 8\times 10^4$，$1\le M\le 2\times 10^5$，$0\le\text{恢复系数}\le 0.8$ 且最多有一位小数， $1\le S\le N$。


title: 游戏预言

description: John 和朋友们在玩纸牌游戏，他们一共有 $m$ 个人（包括 John）。他们的纸牌比较特殊，一共有 $n \times m$ 张牌，牌号分别为 $1,2,\dots,n \times m$，没有牌号相同的牌。每个人先拿到 $n$ 张牌，然后，每一轮，每个人出一张牌，谁最大则谁赢得这一轮。现在已知 John 手中的 $n$ 张牌，计算他最少能赢得多少轮。

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

第二行有 $n$ 个正整数，表示 John 手中的 $n$ 张牌的数值。

outputFormat: 仅一个整数，表示 John 最少能赢的次数。


title: 原核生物培养

description:
W 教授最近正在研究一种原核生物，这种生物的生长方式很奇特，只能通过吃掉同类而生长。两个该种生物相遇，较大质量的会把较小的吃掉（相同的话就看 RP 了），吃掉后较大的生物的质量会变为两只原核生物重量之和，但这个过程会消耗酶，消耗的酶近似为它们重量之和。

W 教授现在有 $n$ 只原核生物，他每次会从培养皿中取重量最小的 $m$ 个生物进行实验，让它们自相残杀。

实验的操作是这样的，教授将这 $m$ 个原核生物按某种重量大小的顺序放在一个环形的管道里，然后给其中相邻两只原核生物酶，如此反复。最后把剩下的那只放回培养皿，接着进行下次实验。W 教授希望经过 $k$ 次实验后耗能最少。输入数据保证，不会出现生物不够的情况。

inputFormat:
第一行有三个整数，分别为 $n$, $m$, $k$。

第二行有 $n$ 个整数，代表最初 $n$ 个生物的重量。

接下来的 $k$ 行，每行 $m$ 个整数，第 $i+2$ 行的第 $j$ 个数代表第 $i$ 次实验的第 $j$ 小的生物放在哪个位置。例如 $m=5$，第三行为，$14235$ 代表最小的生物放在第一个位置，第二小的放第三个 $\ldots$ 最大的放在第五个位置（和第一个位置相邻）。

outputFormat: 只有一个整数，代表 $k$ 次实验之后最小消耗酶的量。

hint:
对于 $100\%$ 的数据，$1<n\leq 1000$, $1\leq m\leq 10$, $1\leq k\leq 100$。数据保证结果不超过 $2^{31}$。

样例解释：

第一次是用重量为 $1, 2$ 消耗酶 $3$，变为一个重量 $3$。

第二次是用重量为 $3, 3$ 消耗酶 $6$，变为一个重量 $6$。

第三次是用重量为 $4, 5$ 消耗酶 $9$，变为一个重量 $9$。

所以消耗总酶为 $18$。


title: [USACO07OCT] Bessie's Secret Pasture S

description:
Farmmer John 最近收割了几乎无限多块牧草，将它们堆放在空地上。这些牧草都是正方形的，而且都有非负整数长度的边长（当然有 $0$）。一天它的奶牛 Bessie 发现了这些美味的牧草，于是希望把它们种在自己的秘密牧场上。他总将草皮分割成 $1\times1$ 的小块，以放入他牧场上的 $N$ 个格子中。

Bessie 感兴趣的是，她若选取四块会有多少种不同方法。如果 $N=4$，那么她就有 $5$ 种不同分法：$(1,1,1,1), (2,0,0,0), (0,2,0,0),(0,0,2,0),(0,0,0,2)$，括号内数表示边长。注意这里不讲究顺序，如 $(1,2,3,4)$ 与 $(4,3,2,1)$ 是两种不同方法。

inputFormat: 仅一行，一个整数 $N$ 。

outputFormat: 同样为一行，包含一个整数，为方案总数。


title: 同花顺

background: 所谓同花顺，就是指一些扑克牌，它们花色相同，并且数字连续。

description: 现在我手里有 $n$ 张扑克牌，但它们可能并不能凑成同花顺。我现在想知道，最少更换其中的多少张牌，我能让这 $n$ 张牌都凑成同花顺？

inputFormat:
第一行一个整数 $n$ ，表示扑克牌的张数。

接下来 $n$ 行，每行两个整数 $a_{i}$ 和 $b_{i}$。其中 $a_{i}$ 表示第 $i$ 张牌的花色，$b_{i}$ 表示第  $i$ 张牌的数字。

outputFormat: 一行一个整数，表示最少更换多少张牌可以达到目标。


title: 添加括号III

description:
现在给出一个表达式，形如 $a_{1}/a_{2}/a_{3}/.../a_{n}$。

如果直接计算，就是一个个除过去，比如 $1/2/1/4 = 1/8$。

然而小$\text{A}$看到一个分数感觉很不舒服，希望通过添加一些括号使其变成一个整数。一种可行的办法是 $(1/2)/(1/4)=2$ 。

现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。

inputFormat:
一个测试点中会有多个表达式。

第一行 $t$ ，表示表达式数量。

对于每个表达式，第一行是 $n$，第二行 $n$ 个数，第 $i$ 个数表示 $a_{i}$。

outputFormat:
输出 $t$ 行。

对于每个表达式，如果可以通过添加括号改变顺序使其变成整数，那么输出 `Yes`，否则输出 `No`。


title: 美丽的序列

background: GD是一个热衷于寻求美好事物的人，一天他拿到了一个美丽的序列。

description: 为了研究这个序列的美丽程度，GD定义了一个序列的“美丽度”和“美丽系数”：对于这个序列的任意一个区间[l，r]，这个区间的“美丽度”就是这个区间的长度与这个区间的最小值的乘积，而整个序列的“美丽系数”就是它的所有区间的“美丽度”的最大值。现在GD想要你帮忙计算这个序列的“美丽系数”。

inputFormat: 第一行一个整数n，代表序列中的元素个数。 第二行n个整数a1、a2„an，描述这个序列。

outputFormat: 一行一个整数，代表这个序列的“美丽系数”。

hint: 样例解释 选取区间［2，3］，可以获得最大“美丽系数”为2\*2=4。 数据范围 对于20%的数据，n<=2000； 对于60%的数据，n<=200000； 对于100%的数据，1<=n<=2000000，0<=ai<=2000000。 提示 你可能需要一个读入优化。


title: [TJOI2012] 防御

description:
在一个塔防小游戏中，有很多防线。每条防线由一排 $n$ 个独立的防御体 $[1 : n]$ 进行防御。

游戏过程中，会不断有敌人对防线进行攻击，每次攻击会指定防御体 $[l : r]$ 进行攻击力为 $a$ 的攻击。第一防线具有护甲，护甲承受攻击后，对应的防御体所受到的伤害为攻击力，但护甲承受的伤害总量到达一定程度后就会破碎，此时防御体所受的伤害加倍。目前第一防线的力量充足，玩家致力于对后面的防线的建设，不过为确认游戏进度和第一防线的情况，玩家会不时地将鼠标移动到第一防线的某个防御体上，以查看其所受到的伤害。

inputFormat:
第一行，两个整数 $n$ 和 $q$，分别表示防御体个数以及攻击和查询的总数。

第二行，$n$ 个数，表示每个防御体护甲的承受能力 $p_i$ 。

接下来 $q$ 行，每行可能具有如下形式：

`A l r a` 表示对防御体 $l,l+1,\cdots,r$ 进行攻击力为 $a$ 的攻击；

`Q x` 表示查询防御体 $x$ 目前所受到的伤害，初始时伤害为 $0$ 。

outputFormat: 一行，一个整数，表示所有查询结果之和对 ${10}^9+9$ 取模的余数。


title: 【模板】负环

description:
给定一个 $n$ 个点的有向图，请求出图中是否存在**从顶点 $1$ 出发能到达**的负环。

负环的定义是：一条边权之和为负数的回路。

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

输入的第一行是一个整数 $T$，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 $n$ 和接下来给出边信息的条数 $m$。

接下来 $m$ 行，每行三个整数 $u, v, w$。

- 若 $w \geq 0$，则表示存在一条从 $u$ 至 $v$ 边权为 $w$ 的边，还存在一条从 $v$ 至 $u$ 边权为 $w$ 的边。
- 若 $w < 0$，则只表示存在一条从 $u$ 至 $v$ 边权为 $w$ 的边。

outputFormat: 对于每组数据，输出一行一个字符串，若所求负环存在，则输出 `YES`，否则输出 `NO`。

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

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

- $1 \leq n \leq 2 \times 10^3$，$1 \leq m \leq 3 \times 10^3$。
- $1 \leq u, v \leq n$，$-10^4 \leq w \leq 10^4$。
- $1 \leq T \leq 10$。

#### 提示

请注意，$m$ **不是**图的边数。


title: zzc 种田

background: 可能以后 zzc 就去种田了。

description: 田地是一个巨大的矩形，然而 zzc 每次只能种一个正方形,而每种一个正方形时 zzc 所花的体力值是正方形的周长，种过的田不可以再种，zzc 很懒还要节约体力去泡妹子，想花最少的体力值去种完这块田地，问最小体力值。

inputFormat: 两个正整数 $x,y$，表示田地的长和宽。

outputFormat: 输出最小体力值。


title: 心碎

background: NOIP2015初赛。CYD大神在他的母校跪掉了。初赛那天，他回到原来的教室参观了一下，发现那张遍布了N个洞的课桌还摆在那里——那是他初中时和XHY同学坐过的桌子。这时，CYD大神的心都碎了。

description:
CYD大神的心可以看做一个环，内外都顺时针均匀分布了N个一一正对应的点。当他看到第i个洞时，就会想起第Ai件往事，这会在CYD大神的心上外侧第i个点和内侧第Ai个点间留下一道伤痕(i<Ai时为顺时针，i>Ai时逆时针，i=Ai时正对应)。

CYD大神觉得，他的心一定不会再碎了，所以，他想让你帮他写一个程序，确定一个Ai的排列，使得他的心碎的块数最多。

inputFormat: 第一行，一个正整数N。

outputFormat: 仅一行，一个正整数表示CYD大神的心最多碎成多少块。


title: 排版

background: 某兄弟学校就是这么良(sang)心(xin)温(bing)暖(kuang)，国庆节作业写了满满一黑板，连信息技术都有作业！更过分的是，作业就是做一个“国庆旅游计划”PPT。（老师，您能再假一点吗）

description:
然而，XHY同学并不会做PPT，于是她找到了CYD大神求助。她想把N张4\*3的照片不重叠，无缝隙地拼成一个矩形作为背景图片。为了美观，她希望背景图片的长与宽尽可能接近，并且在长宽均相等的情况下，使得旋转的照片张数尽可能少。（4\*3的不算旋转，3\*4的算作旋转，且照片只能有这两种尺寸）。

请你帮CYD大神写一个程序，帮XHY同学设计一种满足她要求的照片排列方式，使得旋转的照片张数最少。

outputFormat: 仅一行，一个非负整数表示最少的旋转照片张数。


title: 报纸

background: 终于熬过了初中三年，《学英语报》却阴魂不散。当高一的第一张《学英语报》飘到我面前时，CYD 大神心里充满了绝望，然而，他还有一线希望——XHY 同学总是做得比他快。

description:
作为做 PPT 的回报，XHY 同学决定送点“温暖”给 CYD 大神——一份英语报纸的答案。这份报纸是一个 $N \times N$ 的方阵，其中某些格子写有答案。答案的分布似乎很有规律：对于格子 $(x,y)$，当且仅当 $x$ 和 $y$ 不互质时，这个格子上有答案。

XHY 同学的手机每次能拍下一个 $1 \times 2$ 的区域（横竖均可）。请你帮她写一个程序，求出至少要拍多少张照片，才能把所有的答案发给 CYD 大神。

inputFormat: 仅一行，一个正整数 $N$。

outputFormat: 仅一行，一个非负整数表示至少要拍的照片张数。


title: 越越的组队

description:
班级要组织一场综合能力竞赛，班里共有 $n$ 位学生，将分成两队互相竞争。

老师找到了越越并给了越越一张全班同学综合能力测试的成绩，要求他从全班同学中选出**一半**，并要求这些同学综合能力测试的成绩之和在**不超过班级总分一半**的前提下尽量达到最高。这样分成的两队实力是最平均的。越越堆着满脸的笑容找到了你，你就帮他写一个程序吧。

inputFormat:
第一行有一个整数，表示班级的学生人数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $a_i$ 表示第 $i$ 位同学的成绩。

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

hint:
#### 样例 1 解释

班级总分为 $550$，总分的一半是 $275$，选则成绩分别为 $56,77,84,56$ 的同学可以达到总分 $273$，是不超过 $275$ 的最大值。

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 100$，$0 \leq a_i \leq 100$，数据保证 $n$ 均为偶数。


title: [USACO08FEB] Game of Lines S

background: Farmer John 最近发明了一个游戏，来考验自命不凡的贝茜。

description:
Farmer John has challenged Bessie to the following game: FJ has a board with dots marked at N (2 ≤ N ≤ 200) distinct lattice points. Dot i has the integer coordinates Xi and Yi (-1,000 ≤ Xi ≤ 1,000; -1,000 ≤ Yi ≤ 1,000).

Bessie can score a point in the game by picking two of the dots and drawing a straight line between them; however, she is not allowed to draw a line if she has already drawn another line that is parallel to that line. Bessie would like to know her chances of winning, so she has asked you to help find the maximum score she can obtain.

游戏开始的时 候，FJ 会给贝茜一块画着 $N (2 \le N \le 200)$ 个不重合的点的木板，其中第 $i$ 个点的横、纵坐标分别为 $X_i$ 和 $Y_i (-1000 \le X_i \le 1000, -1000 \le Y_i \le 1000)$。

贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线 平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

inputFormat:
第 $1$ 行: 输入 1 个正整数：$N$

第 $2 \cdots N+1$ 行: 第 $i+1$ 行用 $2$ 个用空格隔开的整数$X_i,Y_i$，描述了点 $i$ 的坐标。

outputFormat: 第 1 行: 输出 1 个整数，表示贝茜的最大得分，即她能画出的互不平行的线段数

hint: 贝茜能画出以下 $4$ 种斜率的直线：$-1$，$0$，$\dfrac{1}{3}$ 以及 $1$。


title: 【模板】矩阵快速幂

background:
一个 $m \times n$ 的**矩阵**是一个由 $m$ 行 $n$ 列元素排列成的矩形阵列。即形如

$$ A = \begin{bmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \end{bmatrix} \text{.} $$

本题中认为矩阵中的元素 $a_{i j}$ 是整数。

两个大小分别为 $m \times n$ 和 $n \times p$ 的矩阵 $A, B$ **相乘**的结果为一个大小为 $m \times p$ 的矩阵。将结果矩阵记作 $C$，则

$$ c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} $$

而如果 $A$ 的列数与 $B$ 的行数不相等，则无法进行乘法。

可以验证，矩阵乘法满足结合律，即 $(A B) C = A (B C)$。

一个大小为 $n \times n$ 的矩阵 $A$ 可以与自身进行乘法，得到的仍是大小为 $n \times n$ 的矩阵，记作 $A^2 = A \times A$。进一步地，还可以递归地定义任意高次方 $A^k = A \times A^{k - 1}$，或称 $A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}$。

特殊地，定义 $A^0$ 为单位矩阵 $I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}$。

description: 给定 $n\times n$ 的矩阵 $A$，求 $A^k$。

inputFormat:
第一行两个整数 $n,k$。
接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 的数表示 $A_{i,j}$。

outputFormat:
输出 $A^k$

共 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $(A^k)_{i,j}$，每个元素对 $10^9+7$ 取模。


title: 【模板】二分图最大匹配

description:
给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

inputFormat:
输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。

接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

outputFormat: 输出一行一个整数，代表二分图最大匹配的边数。

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

对于全部的测试点，保证：
- $1 \leq n, m \leq 500$。
- $1 \leq e \leq 5 \times 10^4$。
- $1 \leq u \leq n$，$1 \leq v \leq m$。

**不保证给出的图没有重边**。


title: 【模板】缩点

description:
给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

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

第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。

第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\rightarrow v$ 的有向边。

outputFormat: 共一行，最大的点权之和。


title: 【模板】割点（割顶）

background: 割点

description: 给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。

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

下面 $m$ 行每行输入两个正整数 $x,y$ 表示 $x$ 到 $y$ 有一条边。

outputFormat:
第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

hint:
对于全部数据，$1\leq n \le 2\times 10^4$，$1\leq m \le 1 \times 10^5$。

点的编号均大于 $0$ 小于等于 $n$。

**tarjan图不一定联通。**


title: 《瞿葩的数字游戏》T3-三角圣地

background: 国王1带大家到了数字王国的中心：三角圣地。

description:
不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是1~N。1~N可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为“基”。国王1希望“基”越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你输出它mod 10007 的结果。

任务：给定N，求三角形1~N的基的最大值 再去 mod 10007。

inputFormat: 一个整数N

outputFormat: 一个整数，表示1~N构成的三角形的最大的“基”

hint:
数据：

20%    0<=N<=100

50%    0<=N<=3000

100% 0<=N<=1000000

样例解释：

1   3   4   2

4    7   6

11  13

24
是N=4的时候的最大值，当然还有别的构成形式。

PS：它叫做三角圣地，其实它就是个三角形~

本题数据已经更新，目前全部正确无误！

不要面向数据编程！


title: 【模板】高斯消元法

background: 如果想要更好地测试高斯消元算法模板请在通过此题后尝试通过 [SDOI2006 线性方程组](https://www.luogu.com.cn/problem/P2455) 这一题。

description:
给定一个线性方程组，对其求解。

$$ \begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}$$

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

第二至 $n+1$ 行，每行 $n+1$ 个整数，为 $ a_1, a_2, \dots ,a_n$ 和 $b$，代表一组方程。

outputFormat:
共 $n$ 行，每行一个数，第 $i$ 行为 $x_i$（四舍五入保留 $2$ 位小数）。

如果不存在唯一解或无解，在第一行输出 `No Solution`.

hint:
本题 special judge 用于处理可能由于浮点数问题输出 `-0.00` 的情况。若某个 $x_i$ 的解四舍五入后是 `0.00`，那么你的程序输出 `-0.00` 和输出 `0.00` 都是正确的。

数据范围：$1 \leq n \leq 100, \left | a_i \right| \leq {10}^4 , \left |b \right| \leq {10}^4 $。保证数据若有解则所有解均满足 $|x_i|\le 10^3$，且 $x_i\pm 10^{-6}$ 和 $x_i$ 四舍五入后的结果相同（即不会因为较小的精度误差导致四舍五入后的结果不同）。


title: [NOIP2015 提高组] 斗地主

background: NOIP2015 Day1T3

description:
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的 $A$ 到 $K$ 加上大小王的共 $54$ 张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：$3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{小王}<\text{大王}$，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 $n$ 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

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

**本题数据随机，不支持hack，要hack或强力数据请点击[这里](https://www.luogu.org/problem/P2540)**。

inputFormat:
第一行包含用空格隔开的 $2$ 个正整数 $T,n$，表示手牌的组数以及每组手牌的张数。

接下来 $T$ 组数据，每组数据 $n$ 行，每行一个非负整数对 $a_i,b_i$，表示一张牌，其中 $a_i$ 表示牌的数码，$b_i$ 表示牌的花色，中间用空格隔开。特别的，我们用 $1$ 来表示数码 $A$，$11$ 表示数码 $J$，$12$ 表示数码 $Q$，$13$ 表示数码 $K$；黑桃、红心、梅花、方片分别用 $1-4$ 来表示；小王的表示方法为 `0 1`，大王的表示方法为 `0 2`。

outputFormat: 共 $T$ 行，每行一个整数，表示打光第 $i$ 组手牌的最少次数。


title: [NOIP2015 普及组] 金币

background: NOIP2015 普及组 T1

description:
国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 $n$ 天每天收到 $n$ 枚金币后，骑士会在之后的连续 $n+1$ 天里，每天收到 $n+1$ 枚金币。

请计算在前 $k$ 天里，骑士一共获得了多少金币。

inputFormat: 一个正整数 $k$，表示发放金币的天数。

outputFormat: 一个正整数，即骑士收到的金币数。

hint:
**【样例 1 说明】**

骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 $1+2+2+3+3+3=14$ 枚金币。

对于 $100\%$ 的数据，$1\le k\le 10^4$。


title: [NOIP2015 普及组] 扫雷游戏

background: NOIP2015 普及组 T2

description:
扫雷游戏是一款十分经典的单机小游戏。在 $n$ 行 $m$ 列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。

现在给出 $n$ 行 $m$ 列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。

注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。

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

接下来 $n$ 行，每行 $m$ 个字符，描述了雷区中的地雷分布情况。字符 $\texttt{*}$ 表示相应格子是地雷格，字符 $\texttt{?}$ 表示相应格子是非地雷格。相邻字符之间无分隔符。

outputFormat: 输出文件包含 $n$ 行，每行 $m$ 个字符，描述整个雷区。用 $\texttt{*}$ 表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。


title: [NOIP2015 普及组] 求和

background: NOIP2015 普及组 T3

description:
一条狭长的纸带被均匀划分出了 $n$ 个格子，格子编号从 $1$ 到 $n$。每个格子上都染了一种颜色 $color_i$ 用 $[1,m]$ 当中的一个整数表示），并且写了一个数字 $number_i$。

| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| **颜色和数字** | $\color{blue}{5}$ | $\color{blue}{5}$ | $\color{red}{3}$ | $\color{red}{2}$ | $\color{blue}{2}$ | $\color{red}{2}$ |

定义一种特殊的三元组：$(x,y,z)$，其中 $x,y,z$ 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

1. $x,y,z$ 都是整数，$x<y<z,y-x=z-y$。

2. $color_x=color_z$。

满足上述条件的三元组的分数规定为 $(x+z) \times (number_x+number_z)$。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 $10007$ 所得的余数即可。

inputFormat:
第一行是用一个空格隔开的两个正整数 $n$ 和 $m,n$ 表纸带上格子的个数，$m$ 表纸带上颜色的种类数。

第二行有 $n$ 用空格隔开的正整数，第 $i$ 个数字表示纸带上编号为 $i$ 格子上面写的数字 $number_i$。

第三行有 $n$ 用空格隔开的正整数，第 $i$ 数字表示纸带上编号为 $i$ 格子染的颜色 $color_i$。

outputFormat: 一个整数，表示所求的纸带分数除以 $10007$ 所得的余数。


title: [NOIP2015 普及组] 推销员

background: NOIP2015 普及组 T4

description:
阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 $N$ 家住户，第 $i$ 家住户到入口的距离为 $S_i$ 米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 $X$ 家住户推销产品，然后再原路走出去。

阿明每走 $1$ 米就会积累 $1$ 点疲劳值，向第 $i$ 家住户推销产品会积累 $A_i$ 点疲劳值。阿明是工作狂，他想知道，对于不同的 $X$，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

inputFormat:
第一行有一个正整数 $N$，表示螺丝街住户的数量。

接下来的一行有 $N$ 个正整数，其中第 $i$ 个整数 $S_i$ 表示第 $i$ 家住户到入口的距离。数据保证 $S_1 \le S_2 \le \cdots \le S_n <10^8$。

接下来的一行有 $N$ 个正整数，其中第 $i$ 个整数 $A_i$ 表示向第 $i$ 户住户推销产品会积累的疲劳值。数据保证 $A_i<1000$。

outputFormat: 输出 $N$ 行，每行一个正整数，第 $i$ 行整数表示当 $X=i$ 时，阿明最多积累的疲劳值。


title: [USACO07DEC] Bookshelf B

description:
Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

所有 $N(1 \le N \le 20,000)$ 头奶牛都有一个确定的身高 $H_i(1 \le H_i \le 10,000)$。设所有奶牛身高的和为S。书架的高度为 $B$，并且保证 $1 \le B \le S < 2,000,000,007$。

为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。

显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

inputFormat:
* 第 $1$ 行: 2 个用空格隔开的整数：$N$ 和 $B$；
* 第 $2\dots N+1$ 行: 第 $i+1$ 行是 $1$ 个整数：$H_i$。

outputFormat: * 第 $1$ 行: 输出 $1$ 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部

hint:
输入说明:

一共有 $6$ 头奶牛，书架的高度为 $40$，奶牛们的身高在 $6\dots19$之间。

输出说明:

一种只用 $3$ 头奶牛就达到高度 $40$ 的方法：$18+11+13$。当然还有其他方法，在此不一一列出了。


title: [USACO07DEC] Bookshelf 2 B

description: Farmer John最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。 所有N(1 <= N <= 20)头奶牛都有一个确定的身高H\_i(1 <= H\_i <= 1,000,000 - 好高的奶牛>\_<)。设所有奶牛身高的和为S。书架的 高度为B，并且保证1 <= B <= S。 为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不象演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。 塔叠得越高便越不稳定，于是奶牛们希望找到一种方案，使得叠出的塔在高度不小于书架高度的情况下，高度尽可能小。你也可以猜到你的任务了：写一个程序，计算奶牛们叠成的塔在满足要求的情况下，最少要比书架高多少。

inputFormat: \* 第1行: 2个用空格隔开的整数：N 和 B \* 第2..N+1行: 第i+1行是1个整数：H\_i

outputFormat: \* 第1行: 输出1个非负整数，即奶牛们叠成的塔最少比书架高的高度

hint:
输出说明:

我们选用奶牛1、3、4、5叠成塔，她们的总高度为3 + 3 + 5 + 6 = 17。任何方案都无法叠出高度为16的塔，于是答案为1。


title: [NOIP2015 提高组] 跳石头

background: NOIP2015 Day2T1

description:
一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

inputFormat:
第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$， 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

outputFormat: 一个整数，即最短跳跃距离的最大值。

hint:
### 输入输出样例 1 说明

将与起点距离为 $2$ 和 $14$ 的两个岩石移走后，最短的跳跃距离为 $4$（从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石，或者从距离 $21$ 的岩石跳到终点）。

### 数据规模与约定

对于 $20\%$的数据，$0 \le M \le N \le 10$。
对于 $50\%$ 的数据，$0 \le M \le N \le 100$。
对于 $100\%$ 的数据，$0 \le M \le N \le 50000,1 \le L
 \le 10^9$。


title: [NOIP2015 提高组] 子串

background: NOIP2015 Day2T2

description:
有两个仅包含小写英文字母的字符串 $A$ 和 $B$。

现在要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串，然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 $B$ 相等？

注意：子串取出的位置不同也认为是不同的方案。

inputFormat:
第一行是三个正整数 $n,m,k$，分别表示字符串 $A$ 的长度，字符串 $B$ 的长度，以及问题描述中所提到的 $k$，每两个整数之间用一个空格隔开。

第二行包含一个长度为 $n$ 的字符串，表示字符串 $A$。

第三行包含一个长度为 $m$ 的字符串，表示字符串 $B$。

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

由于答案可能很大，所以这里要求输出答案对 $1000000007$ 取模的结果。

hint:
**样例解释**

所有合法方案如下：（加下划线的部分表示取出的字串）

样例 1：$\texttt{\underline{aab}\,aab,aab\,\underline{aab}}$。
样例 2：$\texttt{\underline{a}\,\underline{ab}\,aab,\underline{a}\,aba\,\underline{ab},a\,\underline{a}\,ba\,\underline{ab},aab\,\underline{a}\,\underline{ab},\underline{aa}\,\underline{b}\,aab,\underline{aa}\,baa\,\underline{b},aab\,\underline{aa}\,\underline{b}}$。
样例 3：$\texttt{\underline{a}\,\underline{a}\,\underline{b}\,aab,\underline{a}\,\underline{a}\,baa\,\underline{b},\underline{a}\,ab\,\underline{a}\,a\,\underline{b},\underline{a}\,aba\,\underline{a}\,\underline{b},a\,\underline{a}\,b\,\underline{a}\,a\,\underline{b},a\,\underline{a}\,ba\,\underline{a}\,\underline{b},aab\,\underline{a}\,\underline{a}\,\underline{b}}$。

**数据范围**

对于第 1 组数据：$1≤n≤500,1≤m≤50,k=1$;
对于第 2 组至第 3 组数据：$1≤n≤500,1≤m≤50,k=2$;
对于第 4 组至第 5 组数据：$1≤n≤500,1≤m≤50,k=m$;
对于第 1 组至第 7 组数据：$1≤n≤500,1≤m≤50,1≤k≤m$;
对于第 1 组至第 9 组数据：$1≤n≤1000,1≤m≤100,1≤k≤m$;
对于所有 10 组数据：$1≤n≤1000,1≤m≤200,1≤k≤m$。


title: [NOIP2015 提高组] 运输计划

background: NOIP2015 Day2T3

description:
公元 $2044$ 年，人类进入了宇宙纪元。

L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$，任意飞船驶过它所花费的时间为 $t_j$，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？

inputFormat:
第一行包括两个正整数 $n, m$，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行描述航道的建设情况，其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $t_i$，表示第 $i$ 条双向航道修建在 $a_i$ 与 $b_i$ 两个星球之间，任意飞船驶过它所花费的时间为 $t_i$。

数据保证

接下来 $m$ 行描述运输计划的情况，其中第 $j$ 行包含两个正整数 $u_j$ 和 $v_j$，表示第 $j$ 个运输计划是从 $u_j$ 号星球飞往 $v_j$号星球。

outputFormat: 一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

hint:
所有测试数据的范围和特点如下表所示

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

**请注意常数因子带来的程序效率上的影响。**

对于 $100\%$ 的数据，保证：$1 \leq a_i,b_i \leq n$，$0 \leq t_i \leq 1000$，$1 \leq u_i,v_i \leq n$。


title: 东南西北

description:
给出起点和终点的坐标，及接下来 $T$ 个时刻的风向（东南西北），每个时刻可以选择顺风偏移 $1$ 个单位或者停在原地。求到达终点的**最少移动步数**。

坐标采用平面直角坐标系，$x$ 轴正向为东，$y$ 轴正向为北。

如果无法偏移至终点，输出 $-1$。

inputFormat:
第一行两个正整数 $x_1,y_1$，表示小明所在位置。

第二行两个正整数 $x_2,y_2$，表示小明想去的位置。

第三行一个整数 $T$，表示 $T$ 个时刻。

第四至第 $N+3$ 行，每行一个字符，表示风向，即东（$\verb!E!$）南（$\verb!S!$）西（$\verb!W!$）北（$\verb!N!$）的英文单词的首字母。

outputFormat: 一行一个整数，表示最少移动步数。

hint:
### 样例解释

- 样例 $1$：向东走一步，向北走一步。
- 样例 $2,3$：无法到达。

### 数据范围

对于全部数据，$1\le T\le 50$。


title: 老虎的题目

description:
随着小老虎做题越来越多，现在可做小老师了，小老虎经常帮老师出题供信息学奥赛班的同学测试用。出题确实是一件麻烦事。现在有更麻烦的事了：

小老虎收集到了一大堆的题目，并且按照收集的时间顺序排成一排。每个题目都有自己的题面长度和难度。小老虎想用这些题出好多好多场比赛。但是呢，有要求：

同一场比赛的题目，必须是这一排中，连续的一段，但题目数量不限。

题面长度的总和，不能超过high，也不能低于low。

不允许出现两场比赛，使得其中一场的题目全部在另一场出现过了。（就是说，不同比赛的题目集合不能出现包含和被包含关系）

题目可以在不同比赛中重复使用。

现在，小老虎想知道，在满足以上条件的基础上……对不起，小老虎不是想知道最多出多少场，而是想知道，所有比赛的难度总和最大是多少？（定义一场比赛的难度为本场比赛出现的所有题目的难度和）

inputFormat:
第一行是三个整数，N、low、high。

第二行有N个整数，描述了题面的长度。

第三行有N个整数，描述了题目的难度。

outputFormat: 输出一个整数，所有比赛的最大难度总和。

samples:
21

注：样例中，3场，第一场选1，2两题，第二场选3，4两题，第三场选4，5，6三题。

hint:
对于40%的数据，1 <= N <= 100；

对于100%的数据，1 <= N <= 1000；

单个题目的题面长度和难度都小等于100000；

其余给出的均在longint范围内。


title: [JSOI2007] 建筑抢修

description: 小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有 $N$ 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

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

接下来 $N$ 行，每行两个整数 $T_1,T_2$ 描述一个建筑：修理这个建筑需要 $T_1$ 秒，如果在 $T_2$ 秒之内还没有修理完成，这个建筑就报废了。

outputFormat: 输出一个整数 $S$，表示最多可以抢修 $S$ 个建筑。


title: [TJOI2012] 桥

description:
有 $n$ 个岛屿，$m$ 座桥，每座桥连通两座岛屿，桥上会有一些敌人，玩家只有消灭了桥上的敌人才能通过，与此同时桥上的敌人会对玩家造成一定伤害。而且会有一个大 Boss 镇守一座桥，以玩家目前的能力，是不可能通过的。而 Boss 是邪恶的， Boss 会镇守某一座使得玩家受到最多的伤害才能从岛屿 $1$ 到达岛屿 $n$（当然玩家会选择伤害最小的路径）。问，Boss 可能镇守的桥有哪些。

注意可以有**重边**和**自环**。

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

接下来 $m$ 行，每行三个整数 $s,t,c$，表示一座连接岛屿 $s$ 和 $t$ 的桥上的敌人会对玩家造成 $c$ 的伤害。

outputFormat: 一行，两个整数 $d,cnt$，$d$ 表示有 Boss 的情况下，玩家至少要受到的伤害，$cnt$ 表示 Boss 可能镇守的桥的数目。


title: 搞清洁

description: FJ准备分配它的N只奶牛(1 <= N <= 25,000) 做清洁工作，他把一天分成T(1 <= T <= 1,000,000)个时间段，他希望每一个时间段都有奶牛在清洁，但搞清洁的奶牛数越少越好。

inputFormat:
第一行，两下整数N和T。

接下来N行，每行两个整数，表示第i头奶牛能工作的时间段。

outputFormat: 使每一个时间段都有奶牛工作的最少奶牛数，如果不可能，则输出-1。

hint:
样例解释：

有3头奶牛，第1头能工作的时间段是1至7，即从时间1开始工作，时间7结束（时间7也在工作的），第2头是3-6，第3头是8-10，则只需要第1头和第3头奶牛就能使每一个时间都有奶牛工作。


title: 树的数量

description:
求出包含 $n$ 个节点（无标号）的有根 $m$ 叉树的个数，对 $10\,007$ 取模。

两个有根树相同，当且仅当其根节点相同，且**从左到右**每一棵子树也相同。特别地，两个有根树均为空树，视为两个有根树相同。

inputFormat: 输入两个整数 $n$，$m$。

outputFormat: 输出包含 $n$ 个节点（无标号）的有根 $m$ 叉树的个数，对 $10\,007$ 取模后的值。


title: [USACO04NOV] Apple Catching G

description: 很少有人知道奶牛爱吃苹果。农夫约翰的农场上有两棵苹果树（编号为 $1$ 和 $2$ ）， 每一棵树上都长满了苹果。奶牛贝茜无法摘下树上的苹果，所以她只能等待苹果 从树上落下。但是，由于苹果掉到地上会摔烂，贝茜必须在半空中接住苹果（没有人爱吃摔烂的苹果）。贝茜吃东西很快，她接到苹果后仅用几秒钟就能吃完。每一分钟，两棵苹果树其中的一棵会掉落一个苹果。贝茜已经过了足够的训练， 只要站在树下就一定能接住这棵树上掉落的苹果。同时，贝茜能够在两棵树之间 快速移动（移动时间远少于 $1$ 分钟），因此当苹果掉落时，她必定站在两棵树其中的一棵下面。此外，奶牛不愿意不停地往返于两棵树之间，因此会错过一些苹果。苹果每分钟掉落一个，共 $T$（$1 \le T \le 1000$）分钟，贝茜最多愿意移动 $W$（$1 \le W \le 30$） 次。现给出每分钟掉落苹果的树的编号，要求判定贝茜能够接住的最多苹果数。 开始时贝茜在 1 号树下。

inputFormat: 第一行 $2$ 个数， $T$ 和 $W$。接下来的 $t$ 行，每行一个数，代表在时刻 $t$ 苹果是从 $1$ 号苹果树还是从 $2$ 号苹果树上掉下来的。

outputFormat: 对于每个测试点，输出一行，一个数，为奶牛最多接到的苹果的数量。


title: 骑士的工作

background: 你作为一个村的村长，保卫村庄是理所当然的了。今天，村庄里来了一只恶龙，他有 $n$ 个头，恶龙到处杀人放火。你着急了。不过天无绝人之路，现在来了一个骑士团。里面有 $m$ 位成员（往下看）。

description: 每个人都可以砍掉**至多**一个大小不超过 $z_i$ 的头，需要 $z_i$ 个金币，求最小花费。

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

下接 $n$ 行，一个整数表示 $n$ 个头的大小。

下接 $m$ 行，每个人可以砍的头大小和需要的金币数 $z_1, \cdots, z_m$。

outputFormat: 一个整数，最小花费。如果无解，输出 `you died!`。

hint: 对于所有数据，$1 \le n,m \le 2 \times 10^4$，$1 \leq z_i \leq 10^5$。


title: 逃离

description:
**译自 CLRS Problem 26-1 Escape problem**

在一个 $n\times n$ 的网格中有 $m$ 个起始点 $(x_1, y_1),$ $(x_2, y_2),$ $\dots,$ $(x_m, y_m)$，试问：能否为这些结点分别找一条到边界的路径，且这 $m$ 条路径互不相交（即任意两条路径上没有一个相同的结点）。

![https://i.loli.net/2018/10/14/5bc2ec2948f8b.png](https://i.loli.net/2018/10/14/5bc2ec2948f8b.png)

黑点表示起始点，其他点用白点表示。找出的路径用加粗的线表示。图 (a) 存在符合条件的 $m$ 条路径，图 (b) 则不存在。

inputFormat:
第一行是一个整数，为 $n$ $(1\le n≤35)$。

第二行还是一个整数，为 $m(1\le m\le n^2)$。

以下 $m$ 行，第 $(i+2)$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 行第 $j$ 列的点是起始点。保证起始点坐标互不相同。

outputFormat: 只包括一行。若存在逃脱输出 `YES`，不存在逃脱输出 `NO`。


title: 接金币

description: 在二维坐标系里，有 $n$ 个金币，编号 $0\sim n-1$。初始时，第 $i$ 个金币位于 $(x_i,y_i)$。所有的金币每秒向下垂直下降 $1$ 个单位高度。例如有个金币当前坐标是 $(x,y)$，那么 $t$ 秒后金币所在的位置就是$(x,y-t)$。初始时，FJ 在 $(0,0)$ 处，FJ 每秒只能向左右移动 $1$ 个单位距离，当然 FJ 也可以不移动。如果在某个时刻某个金币和 FJ 所在的位置重合，那么 FJ 就能接住这个金币。求 FJ 能否把所有的金币都接住，如果行输出 $\texttt{Abletocatch}$，否则输出 $\texttt{Notabletocatch}$。

inputFormat:
本题有 $g$ 组数据。

第一行，一个整数 $g$，表示有 $g$ 组测试数据。

对于每组测试数据，格式如下：

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

接下来有 $n$ 行，第 $i$ 行两个整数表示 $x_i,y_i$。

outputFormat: 共 $g$ 行，每行输出 $\texttt{Abletocatch}$ 或 $\texttt{Notabletocatch}$。

samples:
Abletocatch
Notabletocatch
Notabletocatch
Abletocatch
Notabletocatch


title: [USACO1.3] 号码锁 Combination Lock

background: 感谢 @[Fond_Dream](https://www.luogu.com.cn/user/321680) 提供五道 USACO 题目的标准题面。

description:
农夫约翰的奶牛不停地从他的农场中逃出来，导致了很多损害。为了防止它们再逃出来，他买了一只很大的号码锁以防止奶牛们打开牧场的门。

农夫约翰知道他的奶牛很聪明，所以他希望确保它们不会在简单地试了很多不同的号码组合之后就能轻易开锁。锁上有三个转盘，每个上面有数字 $1$ ~ $n$，因为转盘是圆的，所以 $1$ 和 $n$ 是相邻的。有两种能开锁的号码组合，一种是农夫约翰设定的，还有一种“预设”号码组合是锁匠设定的。但是，锁有一定的容错性，所以，在每个转盘上的数字都与一个合法的号码组合中相应的数字相距两个位置以内时，锁也会打开。

比如说，如果农夫约翰的号码组合是 ( $1$ , $2$ , $3$ )，预设号码组合是 ( $4$ , $5$ , $6$ )，在转盘被设定为 ( $1$ , $4$ , $5$)（因为这和农夫约翰的号码组合足够接近）或 ( $2$ , $4$ , $8$ )（因为这和预设号码组合足够接近）时可以打开锁。注意，( $1$ , $5$ , $6$ )并不会打开锁，因为它与任一号码组合都不够接近。

给出农夫约翰的号码组合和预设号码组合，请计算能够开锁的不同的号码组合的数目。号码是有序的，所以 ( $1$ , $2$ , $3$ ) 与 ( $3$ , $2$ , $1$ ) 不同。

inputFormat:
输入的第一行是一个整数 $n$，代表锁上的数字个数。

输入的第二行有三个整数 $x, y, z$，代表农夫约翰的号码组合。

输入的第三行有三个整数 $a, b, c$，代表预设的号码组合。

outputFormat: 输出一行一个整数代表能够开锁的组合数目。

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

每个转盘的标号是 $1$ ~ $50$。农夫约翰的号码组合是 ( $1$ , $2$ , $3$ )，预设号码组合是 ( $5$ , $6$ , $7$ )。

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$1 \leq x, y, z, a, b, c \leq n$。


title: 搞笑世界杯

background: 很久很久以后，一次世界杯。

description:
随着世界杯小组赛的结束，法国，阿根廷等世界强队都纷纷被淘汰，让人心痛不已。 于是有人组织了一场搞笑世界杯，将这些被淘汰的强队重新组织起来和世界杯一同比赛。你和你的朋友欣然去购买球票。不过搞笑世界杯的球票出售方式也很特别，它们只准备了两种球票。

- A 类票——免费球票
- B 类票——双倍价钱球票。

购买时由工作人员通过掷硬币决定，投到正面的买 A 类票， 反面的买 B 类票。主办方总是准备了同样多的 A 类票和 B 类票。你和你的朋友十分幸运的排到了某场精彩比赛的最后两个位置。

这时工作人员开始通过硬币售票。不过更为幸运的是当工作人员到你们面前时他发现已无需再掷硬币了，因为剩下的这两张票全是免费票。

你和你的朋友在欣喜之余，想计算一下排在队尾的两个人同时拿到一种票的概率是多少(包括同时拿 A 类票或 B 类票) 假设工作人员准备了 $2n$ 张球票，其中 $n$ 张 A 类票，$n$ 张 B 类票，并且排在队伍中的人每人必须且只能买一张球票(不管掷到的是该买 A 还是该买 B)。

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

outputFormat: 输出只包含一行一个浮点数，为拿到同一种票的概率，精确到小数点后 4 位。

hint:
## 数据规模与约定

对全部的测试点，保证 $1 \leq n \leq 1250$。


title: 小球

description:
有 $R$ 个红色盒子和 $B$ 个蓝色盒子，还有 $R$ 个红色小球和 $B$ 个蓝色小球。每个盒子只能装一个小球，每个小球都要放在一个盒子里。

- 如果把一个红色小球放在一个红色盒子里，那么得分是 $C$。
- 如果把一个蓝色小球放在一个蓝色盒子里，那么得分是 $D$。
- 如果把一个红色小球放在一个蓝色盒子里，那么得分是 $E$。
- 如果把一个蓝色小球放在一个红色盒子里，那么得分也是 $E$。

现在给出 $R,B,C,D,E$。应该如何放置这些小球进盒子，才能使得总得分最大？输出最大的总得分。

inputFormat: 输入共一行 $5$ 个整数，分别是 $R,B,C,D,E$。

outputFormat: 一个整数，表示最大总得分。


title: [SDOI2017] 序列计数

description:
Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。

Alice 还希望，这 $n$ 个数中，至少有一个数是质数。

Alice 想知道，有多少个序列满足她的要求。

inputFormat: 一行三个数，$n,m,p$。

outputFormat: 一行一个数，满足 Alice 的要求的序列数量，答案对 $20170408$ 取模。


title: [USACO12MAR] Flowerpot S

description:
Farmer John has been having trouble making his plants grow, and needs your help to water them properly.  You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:

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

Each drop falls downward (towards the x axis) at a rate of 1 unit per second.  You would like to place Farmer John's flowerpot of width W somewhere along the x axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount D (so that the flowers in the pot receive plenty of water).  A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.

Given the value of D and the locations of the N raindrops, please compute the minimum possible value of W.

老板需要你帮忙浇花。给出 $N$ 滴水的坐标，$y$ 表示水滴的高度，$x$ 表示它下落到 $x$ 轴的位置。

每滴水以每秒 $1$ 个单位长度的速度下落。你需要把花盆放在 $x$ 轴上的某个位置，使得从被花盆接着的第 $1$ 滴水开始，到被花盆接着的最后 $1$ 滴水结束，之间的时间差至少为 $D$。

我们认为，只要水滴落到 $x$ 轴上，与花盆的边沿对齐，就认为被接住。给出 $N$ 滴水的坐标和 $D$ 的大小，请算出最小的花盆的宽度 $W$。

inputFormat:
第一行 $2$ 个整数 $N$ 和 $D$。

接下来 $N$ 行每行 $2$ 个整数，表示水滴的坐标 $(x,y)$。

outputFormat: 仅一行 $1$ 个整数，表示最小的花盆的宽度。如果无法构造出足够宽的花盆，使得在 $D$ 单位的时间接住满足要求的水滴，则输出 $-1$。


title: 宝石串

description:
有一种宝石串，由绿宝石和红宝石串成，仅当绿宝石和红宝石数目相同的时候，宝石串才最为稳定，不易断裂。安安想知道从给定的宝石串中，可以截取一段最长的稳定的宝石串，有多少颗宝石组成。请你帮助他。

绿宝石用 $\texttt G$ 表示，红宝石用 $\texttt R$ 表示。

inputFormat: 一行，一个由 $\texttt G$ 和 $\texttt R$ 组成的字符串。

outputFormat: 一行一个整数，表示最长的稳定的宝石串有多少颗宝石组成。

hint:
$\texttt {RGGR}$ 为答案。

宝石数小于等于 $10^6$。


title: 逐个击破

background: 三大战役的平津战场上，傅作义集团在以北平、天津为中心，东起唐山西至张家口的铁路线上摆起子一字长蛇阵，并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌不让其逃走，指挥官制定了先切断敌人东西两头退路然后再逐个歼灭敌人的战略方针。秉承伟大军事家的战略思想，作为一个有智慧的军长你，遇到了一个类似的战场局面。

description: 现在有 $N$ 个城市，其中 $K$ 个被敌方军团占领了，$N$ 个城市间有 $N-1$ 条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你 $K$ 个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这 $K$ 个地方军团互相隔离开，以便第二步逐个击破敌人。

inputFormat:
第一行包含两个正整数 $N$ 和 $K$。

第二行包含 $K$ 个整数，表示哪个城市被敌军占领。

接下来 $N-1$ 行，每行包含三个正整数 $a,b,c$，表示从 $a$ 城市到 $b$ 城市有一条公路，以及破坏的代价 $c$。城市的编号从 $0$ 开始。

outputFormat: 输出一行一个整数，表示最少花费的代价。


title: 教主的魔法

description:
教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 $N$ 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 $1, 2, \ldots, N$。

每个人的身高一开始都是不超过 $1000$ 的正整数。教主的魔法每次可以把闭区间 $[L, R]$（$1≤L≤R≤N$）内的英雄的身高全部加上一个整数 $W$。（虽然 $L=R$ 时并不符合区间的书写规范，但我们可以认为是单独增加第 $L(R)$ 个英雄的身高）

CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 $[L, R]$ 内有多少英雄身高大于等于 $C$，以验证教主的魔法是否真的有效。

WD 巨懒，于是他把这个回答的任务交给了你。

inputFormat:
第 $1$ 行为两个整数 $N, Q$。$Q$ 为问题数与教主的施法数总和。

第 $2$ 行有 $N$ 个正整数，第 $i$ 个数代表第 $i$ 个英雄的身高。

第 $3$ 到第 $Q+2$ 行每行有一个操作：

1. 若第一个字母为 `M`，则紧接着有三个数字 $L, R, W$。表示对闭区间 $[L, R]$ 内所有英雄的身高加上 $W$。

2. 若第一个字母为 `A`，则紧接着有三个数字 $L, R, C$。询问闭区间 $[L, R]$ 内有多少英雄的身高大于等于 $C$。

outputFormat: 对每个 `A` 询问输出一行，仅含一个整数，表示闭区间 $[L, R]$ 内身高大于等于 $C$ 的英雄数。

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

原先 $5$ 个英雄身高为 $1, 2, 3, 4, 5$，此时 $[1, 5]$ 间有 $2$ 个英雄的身高大于等于 $4$。教主施法后变为 $1, 2, 4, 5, 6$，此时 $[1, 5]$ 间有 $3$ 个英雄的身高大于等于 $4$。

【数据范围】

对于 $30\%$ 的数据，$N≤1000$，$Q≤1000$。

对于 $100\%$ 的数据，$N≤10^6$，$Q≤3000$，$1≤W≤1000$，$1≤C≤10^9$。

---

$\text{upd 2022.8.18}$：新增加一组 Hack 数据。
$\text{upd 2023.8.16}$：新增加一组 [Hack 数据](https://www.luogu.com.cn/discuss/661585)。


title: [NOI2006] 千年虫

description:
千年虫是远古时代的生物，时隔几千万年，千年虫早已从地球上销声匿迹，人们对其知之甚少。考古生物学家最近开始对其有了兴趣，因为一批珍贵的千年虫化石被发现，这些化石保留了千年虫近乎完整的形态。

理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型，并且据此判定出千年虫就是蜈蚣的祖先！但科学家 J 发现了实际与理论的一些出入，他仔细的研究了上百个千年虫化石，发现其中大部分千年虫的形态都不完全符合理论模型，这到底是什么因素造成的呢？理论科学家 K 敏锐的指出，千年虫的形态保存在化石中很有可能发生各种变化，即便最细微的变化也能导致它不符合模型。

于是，摆在科学家面前的新问题诞生了：判断一个化石中的千年虫与理论模型的差距有多大？具体来说，就是根据一个千年虫化石的形态 $A$，找到 一个符合理论模型的形态 $B$，使得 $B$ 是最有可能在形成化石时变成形态 $A$。理论学家提出的“千年虫形态特征模型”如下（如左图所示）：躯体由头、尾、躯干、足四大部分构成。

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

- 头，尾用一对平行线段表示。称平行于头、尾的方向为 $x$ 方向；垂直于 $x$ 的方向为 $y$ 方向；

- 在头尾之间有两条互不相交的折线段相连，他们与头、尾两条线段一起围成的区域称为躯干，两条折线段都满足以下条件：拐角均为钝角或者平角，且包含奇数条线段，从上往下数的奇数条垂直于 $x$ 方向。

- 每条折线段从上往下数的第偶数条线段的躯干的另一侧长出一条足，即一个上、下底平行于 $x$ 方向的梯形或矩形，且其中远离躯干一侧的边垂直于 $x$ 方向。

注意：足不能退化成三角形（即底边的长度均大于零），躯干两侧足的数目可以不一样。（如上图，左边有 $4$ 条足，右边有 $5$ 条足）

可见，$x$-$y$ 直角坐标系内，躯干和所有足组成的实心区域的边界均平行或垂直于坐标轴。为了方便，我们假设所有这些边界的长度均为正整数。因此可以认为每个千年虫的躯体 都由一些单位方格拼成。每个单位方格都由坐标 $(x,y)$ 唯一确定。设头尾之间的距离为 $n$，则我们可以用 $2\times n$ 个整数来描述一条千年虫 $B$（如右图）：将 $B$ 沿平行 $x$ 轴方向剖分成 $n$ 条宽度为 $1$ 的横条，每个横条最左边一格的 $x$ 坐标设为 $L_i$，最右一格的的 $x$ 坐标设为 $R_i$。则  $(n,L_1,L_2,\dots,L_n,R_1,R_2,\dots,R_n)$ 就确定了一条千年虫。

由于岁月的侵蚀，在实际发现的化石中，千年虫的形状并不满足上面理论模型的规则，一些格子中的躯体已经被某些矿物质溶解腐蚀了。地质、物理、生物学家共同研究得出：

- 腐蚀是以格子为单位的，只能一整格被腐蚀；

- 腐蚀是分步进行的，每一步只有一格被腐蚀；

- 如果去掉一个格子后躯体不连通了，那么这个格子当前不会被腐蚀；

- 如果一个格子的左边邻格和右边邻格都还没被腐蚀，那么这个格子当前不会被腐蚀；

- 与头相邻的格子不能全部被腐蚀，与尾相邻的格子不能全部被腐蚀。

倘若满足上面五条，我们仍然可以用 $(n,L_1,L_2,\dots,L_n,R_1,R_2,\dots,R_n)$ 来描述一个化石里头的千年虫的形态。其中 $L_i\le R_i$。

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

例如下图：

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

现在你的任务是，输入一个化石里的千年虫的描述 $A$，找一个满足理论模型的千年虫的描述 $B$，使得 $B$ 可以通过腐蚀过程得以变为 $A$，且由 $B$ 转化为 $A$ 的代价（须被腐蚀的格子数）最少。输出此最小代价。

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

以下 $n$ 行，每行两个整数，其中第 $i$ 行为两个整数 $L'_i$、$R'_i$，用一个空格分开；保证输入数据合法。

outputFormat: 仅一行，为一个整数，表示最少代价。

hint:
【样例说明】

如图：

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

【评分方法】

本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。

【数据范围】

对于 $30\%$ 的数据，$n\le100$，$R_i\le100$；

对于 $50\%$ 的数据，$n\le1000$，$R_i\le1000$；

对于 $70\%$ 的数据，$n\le10 ^ 5$，$R_i\le 1000$；

对于 $100\%$ 的数据，$1\leq n\le10 ^ 6$，$0\le L_i\le R_i\le10 ^ 6$。


title: [NOI2001] 炮兵阵地

description:
司令部的将军们打算在 $N\times M$ 的网格地图上部署他们的炮兵部队。

一个 $N\times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用 $\texttt{H}$ 表示），也可能是平原（用 $\texttt{P}$ 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

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

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

inputFormat:
第一行包含两个由空格分割开的正整数，分别表示 $N$ 和 $M$。

接下来的 $N$ 行，每一行含有连续的 $M$ 个字符，按顺序表示地图中每一行的数据。

outputFormat: 一行一个整数，表示最多能摆放的炮兵部队的数量。

hint: 对于 $100\%$ 的数据，$1 \leq N\le 100$，$1 \leq M\le 10$，保证字符仅包含 `P` 与 `H`。


title: 寒假作业

background: zzs 和 zzy 正在被寒假作业折磨，然而他们有答案可以抄啊。

description:
他们共有 $n$ 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 $a_i$，表示抄这个作业所要花的精力。

zzs 现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于 $k$？

简单地说，给定一个长度为 $n$ 的正整数序列 $\{a_i\}$，求出有多少个**连续**子序列的平均值不小于 $k$。

inputFormat:
第一行是两个整数，分别表示序列长度 $n$ 和给定的参数 $k$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

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


title: 和谐的雪花

background: 没有背景

description: 现在有 $n\times m$ 个雪花，被放在了一个 $n\ \times m$ 的矩阵当中。每个雪花都有一个优美值。一个正方形的和谐度被定义为在这个正方形中雪花的最大优美值和最小优美值的差，和谐度越大这个正方形就越和谐。现在给出这个矩阵和一个非负整数 $k$，zzs 和 zzy 希望你能告诉他，在所有和谐度不小于 $k$ 的正方形中，边长最小的正方形的边长（即找到一个最小的边长 $a$，使得存在一个边长为 $a$ 的正方形它的和谐度不小于 $k$）。如果没有解，输出 $-1$。

inputFormat:
第一行两个正整数和一个非负整数，$n,m$ 和 $k$。

接下来 $n$ 行，每行 $m$ 个非负整数，表示题目中的矩阵。

outputFormat: 如果有解，则输出一个正整数，表示答案。如果无解，则是 $-1$。


title: 数列

description:
维护一个数列,共 $7$ 种操作:

I. `INSERT x n a1 a2 .. an` 在第 $x$ 个数后插入 $n$ 个数分别为 $a_1\dots a_n$。

II. `DELETE x n` 删除第 $x$ 个数开始的 $n$ 个数。

III. `REVERSE x n` 翻转第 $x$ 个数开始的 $n$ 个数的区间。

IV. `MAKE-SAME x n t` 将第 $x$ 个数开始的 $n$ 个数统一改为 $t$。

V. `GET-SUM x n` 输出第 $x$ 个数开始的 $n$ 个数的和。

VI. `GET x` 输出第 $x$ 个数的值。

VII. `MAX-SUM x n` 输出第 $x$ 个数开始的 $n$ 个数的最大连续子序列和。

inputFormat:
第一行为 $N$，$M$，$N$ 表示初始序列中数的个数，$M$ 表示操作的个数。

第二行为 $N$ 个数 $A_1\dots A_n$，表示初始序列。

第三行到第 $M+2 $行，每行一个操作。

outputFormat: 输出每个`GET-SUM`，`GET`，`MAX-SUM`操作的结果。

samples:
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM 1 9
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET 5
MAX-SUM 1 11

hint:
共 $20$ 组数据，每组数据随机生成，
保证每个时刻数列里的数不超过 $200000$ 个，
任何一个输入的数字均在 $-1000\sim1000$之间，结果不超过 $2^{30}$。

第 $1\sim2$ 组 $\quad1\le N\le 5$，$1\le M\le 10$。

第 $3\sim4$ 组 $\quad1\le N\le 10$，$1\le M\le 20$。

第 $5\sim6$ 组 $\quad1\le N \le 20$，$1\le M\le 50$。

第 $7\sim8$ 组 $\quad1\le N\le 50$，$1\le M\le 100$。

第 $9\sim10$ 组 $\quad1\le N\le 100$，$1\le M\le 500$。

第 $11\sim12$ 组 $\quad 1\le N\le 1000$，$1\le M\le 1000$。

第 $13\sim14$ 组 $\quad1\le N\le 5000$，$1\le M\le 2000$。

第 $15\sim16$ 组 $\quad1\le N\le 10^4$，$1\le M\le 5000$。

第 $17\sim18$ 组 $\quad1\le N\le 10^5$，$1\le M\le 10^4$。

第 $19\sim20$ 组 $\quad1\le N\le 2\times 10^5$，$1\le M\le 2\times 10^4$。


title: 四元组统计

description: 有 $n$ 个正整数 $a _ i$，你要统计有多少个四元组满足 $\gcd(a _ i, a _ j, a _ k, a _ l) = 1$。

inputFormat:
输入包含多组数据。
对于每组数据：第一行一个正整数 $n$，接下来一行 $n$ 个正整数 $a _ i$。

outputFormat: 若干行，每行对应一个输入数据，表示满足要求的四元组的个数。


title: 罗马游戏

description:
罗马皇帝很喜欢玩杀人游戏。 他的军队里面有  $n$ 个士兵，每个士兵都是一个独立的团。最近举行了一次平面几何测试，每个士兵都得到了一个分数。 皇帝很喜欢平面几何，他对那些得分很低的士兵嗤之以鼻。

他决定玩这样一个游戏。 它可以发两种命令：

- `M i j` 把  $i$ 所在的团和  $j$ 所在的团合并成一个团。如果  $i,j$ 有一个士兵是死人，那么就忽略该命令。
- `K i` 把   $i$ 所在的团里面得分最低的士兵杀死。如果  $i$ 这个士兵已经死了，这条命令就忽略。

皇帝希望他每发布一条 `K i` 命令，下面的将军就把被杀的士兵的分数报上来
（如果这条命令被忽略，那么就报  $0$ 分）。

保证**士兵的分数互不相同**。

inputFormat:
第一行一个整数  $n$，表示士兵数。

第二行  $n$ 个整数   $a_1,a_2,\ldots a_n$，其中  $a_i$ 表示编号为   $i$ 的士兵的分数。

第三行一个整数  $m$。

第   $3+i$ 行描述第i条命令。命令为如下两种形式：`M i j` 或 `K i`。

outputFormat: 如果命令是 `K i`，对应的请输出被杀士兵的分数（如果这个人不存在，就输出  $0$）。

hint:
对于   $100\%$ 的数据，  $1\le n\le 10^6$，$1\le m\le 10^5$，$0\le a_i\le 10^7$，
**注意测试数据中 `M i j` 的 $i,j$ 可能在同一个团中。**


title: 摄像头

description:
食品店里有 $n$ 个摄像头，这种摄像头很笨拙，只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店，为了不让摄像头拍下他们犯罪的证据，他们抢劫前的第一件事就是砸毁这些摄像头。

为了便于砸毁摄像头，松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号，一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。

现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头，如不能则输出还没砸掉的摄像头的数量。

inputFormat:
第 $1$ 行，一个整数 $n$，表示摄像头的个数。

第 $2$ 到 $n+1$ 行是摄像头的信息，包括：摄像头的位置 $x$，以及这个摄像头可以监视到的位置数 $m$，之后 $m$ 个数 $y$ 是此摄像头可以监视到的位置。(砸了这些摄像头之后自然这些位置就监视不到了)

outputFormat: 若可以砸掉所有摄像头则输出“ $\texttt{YES}$ ”，否则输出还没砸掉的摄像头的数量。（不带引号）

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

$0 \leq m \leq 100$。

$0 \leq x,y \leq 500$。


title: 小 Q 的赚钱计划

background: 小 Q（郑重其事地）：今年我一定要赚大钱！！！

description: 小 Q 决定在新的一年里赚大钱，小 P 给 TA 推荐了理财。小 Q 在今年初（非闰年）有 $10^5$ 元（好有钱啊），有 $N$ 个理财产品，每个理财产品用三个参数描述：购买时间，投资天数，年利息率。每个时刻小 Q 只能拥有最多一件产品，求一年后最多可以获得多少钱。

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

接下来 $N$ 行，每行为 $3$ 个空格隔开的字符串 $A, B, C$；

- $A$ 表示发行时间，格式为 MMDD；
- $B$ 是一个整数，为投资天数，范围 $[10,300]$；
- $C$ 为最多 $2$ 位小数，代表百分之几的年利息，范围 $[3,30]$；

outputFormat: 一个数，为年底最多可以获得的连本带利的资金数目，保留两位有效小数。


title: [USACO3.1] 总分 Score Inflation

background:
选手在我们 USACO 的竞赛中的得分越多我们越高兴。

我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。

description:
我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。

你的任务是写一个程序来告诉 USACO 的职员,应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。

inputFormat:
输入的第一行是用空格隔开的两个整数，分别代表竞赛时间 $m$ 和题目类 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个用空格隔开的整数，第 $(i + 1)$ 行的整数 $p_i, t_i$ 分别代表解决第 $i$ 类题得到的分数和需要花费的时间。

既然是某一类题目，那么这一类题目可以重复选择。

outputFormat: 输出一行一个整数，代表最大的总分。

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

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^4$，$1 \leq p_i, t_i \leq 10^4$。


title: [USACO3.1] 丑数 Humble Numbers

description:
对于一给定的素数集合 $S = \{ p_1, p_2, ..., p_k \}$, 考虑一个正整数集合，该集合中任一元素的质因数全部属于 $S$。这个正整数集合包括，$p_1$、$p_1 \times p_2$、$p_1 \times p_1$、$p_1 \times p_2 \times p_3$ ...(还有其它)。该集合被称为 $S$ 集合的“丑数集合”。注意：我们认为 $1$不是一个丑数。

你的工作是对于输入的集合 $S$ 去寻找“丑数集合”中的第 $n$ 个“丑数”。保证答案可以用 32 位有符号整数表示。

补充：丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第 $n$ 个“丑数”就是在能由素数集合中的数相乘得来的（包括它本身）第 $n$ 小的数。

inputFormat:
输入的第一行是两个的整数，分别代表集合 $S$ 的大小 $k$ 和给定的参数 $n$。

输入的第二行有 $k$ 互不相同的整数，第 $i$ 个整数代表 $p_i$。

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

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

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

- $1 \leq k \leq 100$。
- $1 \leq n \leq 10^5$。
- $2 \leq p_i < 2^{31}$，且 $p_i$ 一定为质数。

---
#### 说明

题目翻译来自 NOCOW。

USACO Training Section 3.1


title: [USACO3.1] 联系 Contact

background: 奶牛们开始对用射电望远镜扫描牧场外的宇宙感兴趣。最近，他们注意到了一种非常奇怪的脉冲调制微波从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的，还是仅仅是普通的的星星发出的。

description:
帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在 $A$ 到 $B$ 之间（包含 $A$ 和 $B$ 本身）在每天的数据文件中重复次数前 $n$ 多的比特序列。

符合的序列可能会重叠，并且至少出现一次的序列会被计数。

inputFormat:
输入的第一行是三个整数 $A, B, n$，其含义见【题目描述】。

第二行是及以后一个字符串 $s$，每行的字符数不超过 $80$。所有行的字符串依次连接即为 $s$。

outputFormat:
输出 $n$ 个频率最高的序列（按照频率由高到低的次序）。由短到长排列频率相同的这些序列，如果长短相同，按二进制大小排列。如果出现的序列个数小于 $n$，输出存在的序列。

对于每个存在的频率，先输出单独包含该频率的一行，再输出以空格分隔的这些序列。每行六个（除非剩下的少于六个）。

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

在样例里，序列 $100$ 出现了 $12$ 次，而序列 $1000$ 出现了 $5$ 次。次数最多的序列是 $00$，出现了 $23$ 次。

---

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 50$，$1 \leq A \leq B \leq 12$，$s$ 中只含字符 `0` 和字符 `1`，且长度不超过 $2 \times 10^5$。

---
#### 说明

题目翻译来自 NOCOW。


title: [USACO3.1] 邮票 Stamps

description: 给一组 $n$ 枚邮票的面值集合和一个上限 $k$ —— 表示信封上能够贴 $k$ 张邮票。请求出最大的正整数 $m$，满足 $1$ 到 $m$ 的面值都可以用不超过 $k$ 张邮票表示出来。

inputFormat:
输入的第一行是两个整数，分别代表邮票上限 $k$ 和邮票面值数 $n$。

自第二行起，除最后一行外，每行有 $15$ 个整数 $a_i$ ，最后一行的整数个数不超过 $15$，共有 $n$ 个整数，第 $i$ 个整数代表第 $i$ 种邮票的面值 $a_i$。

outputFormat: 输出一行一个整数代表 $m$。若 $m$ 不存在请输出 $0$。


title: [USACO3.2] 01串 Stringsobits

background: 考虑排好序的 $N$（$1 \leq N \leq 31$）位二进制数。

description:
他们是排列好的，而且包含所有长度为 $N$ 且这个二进制数中 $1$ 的位数的个数小于等于 $L$（$L \leq N$）的数。

你的任务是输出满足长度为 $N$，且 $1$ 的个数小于等于 $L$ 的第 $i$ 小的那个二进制数（保证这个数存在）。

例：$100101$ 中，$N=6$，含有 $1$ 的个数为 $3$。

inputFormat: 一行三个整数 $N,L,i$。

outputFormat: 输出满足条件的第 $i$ 小的二进制数。

hint:
题目翻译来自NOCOW。

USACO Training Section 3.2


title: [USACO3.2] 纺车的轮子 Spinning Wheels

background: 一架纺车有五个纺轮（也就是五个同心圆），这五个不透明的轮子边缘上都有一些缺口。这些缺口必须被迅速而准确地排列好。每个轮子都有一个起始标记（在0度），这样所有的轮子都可以在统一的已知位置开始转动。轮子按照角度变大的方向旋转（即0经过旋转到达1的位置），所以从起始位置开始，在一定的时间内，它们依次转过1度，2度等等（虽然这些轮子很可能不会同时转过这些角度）。

description:
这是一个整数问题。轮子不会转过1.5度或23.51234123度这样的角度。例如，轮子可能在一秒钟内转过20到25度甚至30到40度（如果转得快的话）。

这个问题中的所有角度都限制在 0 <= 角度 <= 359 这个范围内。轮子转过 359 度后接下来就是 0 度。每个轮子都有一个确定的旋转速度，以秒作为单位。1 <= 速度 <= 180。

轮子上的缺口的起始角度和缺口大小（或宽度）各由一个整数表示，都以度为单位。在一个轮子上，两个缺口之间至少有一度的间隔。宽度也包含缺口起始的角度，**即0 179包括0..179共计180个角度**

在起始位置，设时间为 0，所有的轮子的起始标记排列成一条直线。你的程序必须计算，最早出现每个的轮子上的缺口同其他轮子上的缺口对准（也就是一束光可以通过五个轮子上的五个缺口）情况的时间。这些缺口在任意一个角度对准。

inputFormat:
输入中的五行对应五个轮子。

第一个数字表示轮子的转动速度。下一个数字是缺口的数目 W。1 <= W <= 5。接下来的 W 对数字表示每个缺口的起始角度和宽度。

outputFormat: 只有一行，包括一个整数，表示光能够通过这五个轮子的最早时间。如果无解，输出'none'（小写，不含引号）。


title: [USACO3.2] 饲料调配 Feed Ratios

background: 农夫约翰从来只用调配得最好的饲料来喂他的奶牛。饲料用三种原料调配成：大麦，燕麦和小麦。他知道自己的饲料精确的配比，在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料（同样都由三种麦子组成），然后将它们混合，来调配他的完美饲料。

description:
给出三组整数，表示 大麦：燕麦：小麦 的比例，找出用这三种饲料调配 x：y：z 的饲料的方法。

例如，给出目标饲料 3：4：5 和三种饲料的比例：

1:2:3
3:7:1
2:1:2
你必须编程找出使这三种饲料用量最少的方案，要是不能用这三种饲料调配目标饲料，输出“NONE”。“用量最少”意味着三种饲料的用量（整数）的和必须最小。

对于上面的例子，你可以用8份饲料1，1份饲料2，和5份饲料3，来得到7份目标饲料：

8\*(1:2:3) + 1\*(3:7:1) + 5\*(2:1:2) = (21:28:35) = 7\*(3:4:5)

表示饲料比例的整数以及目标饲料的都是小于100的非负整数。表示各种饲料的份数的整数，都小于100。一种混合物的比例不会由其他混合物的比例直接相加得到。

inputFormat:
Line 1: 三个用空格分开的整数，表示目标饲料

Line 2..4: 每行包括三个用空格分开的整数，表示农夫约翰买进的饲料的比例

outputFormat: 输出文件要包括一行，这一行要么有四个整数，要么是“NONE”。前三个整数表示三种饲料的份数，用这样的配比可以得到目标饲料。第四个整数表示混合三种饲料后得到的目标饲料的份数。


title: [USACO3.2] 魔板 Magic Squares

background:
在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有 $8$ 个大小相同的格子的魔板：

$1\quad2\quad3\quad4$

$8\quad7\quad6\quad5$

description:
我们知道魔板的每一个方格都有一种颜色。这 $8$ 种颜色用前 $8$ 个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列 $\{1,2,3,4,5,6,7,8\}$ 来表示。这是基本状态。

这里提供三种基本操作，分别用大写字母 $\text A$，$\text B$，$\text C$ 来表示（可以通过这些操作改变魔板的状态）：

$\text A$：交换上下两行；

$\text B$：将最右边的一列插入最左边；

$\text C$：魔板中央四格作顺时针旋转。

下面是对基本状态进行操作的示范：

$\text A$：

$8\quad7\quad6\quad5$

$1\quad2\quad3\quad4$

$\text B$：

$4\quad1\quad2\quad3$

$5\quad8\quad7\quad6$

$\text C$：

$1\quad7\quad2\quad4$

$8\quad6\quad3\quad5$

对于每种可能的状态，这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。

inputFormat: 只有一行，包括 $8$ 个整数 $a_1,a_2\cdots a_8(1\leq a_1,a_2\cdots a_8\leq8)$，用空格分开，不换行，表示目标状态。

outputFormat:
第一行包括一个整数，表示最短操作序列的长度。

第二行在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出 $60$ 个字符。

hint:
题目翻译来自 NOCOW。

USACO Training Section 3.2


title: [USACO3.3] 骑马修栅栏 Riding the Fences

background: Farmer John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

description:
John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。

John 的农场上一共有 $m$ 个栅栏，每一个栅栏连接两个顶点，顶点用 $1$ 到 $500$ 标号（虽然有的农场并没有那么多个顶点）。一个顶点上至少连接 $1$ 个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John 能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。

你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个 $500$ 进制的数，那么当存在多组解的情况下，输出 $500$ 进制表示法中最小的一个 （也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。

输入数据保证至少有一个解。

inputFormat:
第一行一个整数 $m$，表示栅栏的数目。

从第二行到第 $(m+1)$ 行，每行两个整数 $u,v$，表示有一条栅栏连接 $u,v$ 两个点。

outputFormat:
共 $(m+1)$ 行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

数据保证至少有一组可行解。

hint:
对于 $100\%$ 的数据，$1 \leq m \leq 1024,1 \leq u,v \leq 500$。

题目翻译来自NOCOW。

USACO Training Section 3.3


title: [USACO3.3] 商店购物 Shopping Offers

background: 在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是 $2$ ，而一个花瓶的价格是 $5$ 。为了吸引更多的顾客，商店举行了促销活动。

description:
促销活动把一个或多个商品组合起来降价销售，例如：

三朵花的价格是 $5$ 而不是 $6$ ，$2$ 个花瓶和一朵花的价格是 $10$ 而不是 $12$ 。 请编写一个程序，计算顾客购买一定商品的花费，尽量地利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。

对于上面的商品信息，购买三朵花和两个花瓶的最少花费的方案是：以优惠价购买两个花瓶和一朵花（$10$），以原价购买两朵花（$4$）。

inputFormat:
输入文件包括一些商店提供的优惠信息，接着是购物清单。（最多有 $5$ 种商品）

第一行 优惠方案的种类数（$0\leq s\leq99$）。

第 $2$ 行 $\sim$ 第 $s+1$ 行  每一行都用几个整数来表示一种优惠方式。第一个整数 $n$ （$\leq n\leq5$），表示这种优惠方式由 $n$ 种商品组成。后面 $n$ 对整数 $c$ 和 $k$ 表示 $k$ （$1\leq k\leq5$）个编号为 $c$ （$1\leq c\leq999$）的商品共同构成这种优惠，最后的整数 $p$ 表示这种优惠的优惠价（$1\leq p\leq9,999$）。优惠价总是比原价低。

第 $s+2$ 行 这一行有一个整数 $b$ （$0\leq b\leq5$），表示需要购买 $b$ 种不同的商品。

第 $s+3$ 行 $\sim$ 第 $s+b+2$ 行 这 $b$ 行中的每一行包括三个整数：$c,k,p$ 。 $c$ 表示唯一的商品编号（$1\leq c\leq999$），$k$ 表示需要购买的 $c$ 商品的数量（$1\leq k\leq5$）。$p$ 表示 $c$ 商品的原价（$1\leq p\leq999$）。最多购买 $5\times5=25$ 个商品。

outputFormat: 只有一行，输出一个整数：购买这些物品的最低价格。

hint:
题目翻译来自NOCOW。

USACO Training Section 3.3


title: [USACO3.3] 家的范围 Home on the Range

background: 农民约翰在一片边长是N (2 <= N <= 250)英里的正方形牧场上放牧他的奶牛。(因为一些原因，他的奶牛只在正方形的牧场上吃草。)遗憾的是,他的奶牛已经毁坏一些土地。( 一些1平方英里的正方形)

description:
农民约翰需要统计那些可以放牧奶牛的正方形牧场(至少是2x2的,在这些较大的正方形中没有一个点是被破坏的，也就是说，所有的点都是“1”)。

你的工作要在被供应的数据组里面统计所有不同的正方形放牧区域(>=2x2)的个数。当然，放牧区域可能是重叠。

inputFormat:
第 1 行:N,牧区的边长。

第 2 到 n+1 行:N个没有空格分开的字符。0 表示 "那一个区段被毁坏了";1 表示 " 准备好被吃"。

outputFormat: 输出那些存在的正方形的边长和个数，一种一行。


title: [USACO3.3] 游戏 A Game

background: 有如下一个双人游戏：$N (2 \leq N \leq 100)$ 个正整数的序列放在一个游戏平台上，游戏由玩家 $1$ 开始，两人轮流从序列的任意一端取一个数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。

description: 编一个执行最优策略的程序，最优策略就是使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。

inputFormat:
第一行: 正整数 $N$，表示序列中正整数的个数。

第二行至末尾: 用空格分隔的 $N$ 个正整数（大小为 $1-200$）。

outputFormat: 只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。

hint:
题目翻译来自 NOCOW。

USACO Training Section 3.3


title: [USACO3.4] 网 Electric Fences

description:
在本题中，格点是指横纵坐标皆为整数的点。

为了圈养他的牛，农夫约翰（Farmer John)建造了一个三角形的电网。他从原点（0,0）牵出一根通电的电线，连接格点(n,m)（0<=n<32000,0<m<32000），再连接格点(p,0)（p>0），最后回到原点。

牛可以在不碰到电网的情况下被放到电网内部的每一个格点上（十分瘦的牛）。如果一个格点碰到了电网，牛绝对不可以被放到该格点之上（或许Farmer John会有一些收获）。那么有多少头牛可以被放到农夫约翰的电网中去呢？

inputFormat: 输入文件只有一行，包含三个用空格隔开的整数：n,m和p。

outputFormat: 输出文件只有一行，包含一个整数，代表能被指定的电网包含的牛的数目。

hint:
题目翻译来自NOCOW。

USACO Training Section 3.4


title: [USACO3.4] “破锣摇滚”乐队 Raucous Rockers

description:
你刚刚继承了流行的 “破锣摇滚” 乐队录制的尚未发表的 $N$（$1\leq N\leq 20$）首歌的版权。你打算从中精选一些歌曲，发行 $M$（$1\leq M\leq 20$）张 CD。每一张 CD 最多可以容纳 $T$（$1\leq T\leq 20$）分钟的音乐，一首歌不能分装在两张 CD 中。CD 数量可以用完，也可以不用完。

不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：

* 1.歌曲必须按照创作的时间顺序在所有的 CD 盘上出现。(注：第 $i$ 张盘的最后一首的创作时间要早于第 $i+1$ 张盘的第一首)

* 2.选中的歌曲数目尽可能地多。

inputFormat:
第一行：三个整数：$N,T,M$。

第二行：$N$ 个整数，分别表示每首歌的长度，按创作时间顺序排列。

outputFormat: 一个整数，表示可以装进 $M$ 张 CD 盘的乐曲的最大数目。


title: [USACO4.1] 麦香牛块Beef McNuggets

description:
农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”奶牛们说，“如果你只用一次能装 $3$ 块、 $6$ 块或者 $10$ 块的三种包装盒包装麦香牛块，你就不可能满足一次只想买 $1$ 、 $2$ 、 $4$ 、 $5$ 、 $7$ 、 $8$ 、 $11$ 、 $14$ 或者 $17$ 块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”。

你的任务是帮助这些奶牛。给出包装盒的种类数 $N(1 \le N \le 10)$ 和 $N$ 个代表不同种类包装盒容纳麦香牛块个数的正整数 $(1 \le i \le 256)$，输出顾客不能用上述包装盒（每种盒子数量无限）买到麦香牛块的最大块数。如果所有购买方案都能得到满足或者不存在不能买到块数的上限，则输出 $0$。不能买到的最大块数（倘它存在）不超过 $2\times 10^9$。

inputFormat:
第 $1$ 行：包装盒的种类数 $N$。

第 $2$ 行到 $N+1$ 行：每个种类包装盒容纳麦香牛块的个数。

outputFormat: 输出文件只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或 $0$（如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限）。

hint:
题目翻译来自 NOCOW。

USACO Training Section 4.1


title: [USACO4.1] 篱笆回路Fence Loops

description:
农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段，有时给定的一个端点上会有两个以上的篱笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样，出于这个考虑，他首先得知道牧场上哪一块区域的周长最小。 布朗将他的每段篱笆从1到N进行了标号（N=线段的总数）。他知道每段篱笆有如下属性：

该段篱笆的长度

该段篱笆的一端所连接的另一段篱笆的标号

该段篱笆的另一端所连接的另一段篱笆的标号

幸运的是，没有篱笆连接它自身。对于一组有关篱笆如何分割牧场的数据，写一个程序来计算出所有分割出的区域中最小的周长。

例如，标号1~10的篱笆由下图的形式组成（下面的数字是篱笆的标号）：

```cpp
           1
   +---------------+
   |\             /|
  2| \7          / |
   |  \         /  |
   +---+       /   |6
   | 8  \     /10  |
  3|     \9  /     |
   |      \ /      |
   +-------+-------+
       4       5
```
上图中周长最小的区域是由2，7，8号篱笆形成的。

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 100$）；

第 $2$ 行到第 $3\times N+1$ 行：每三行为一组，共 $N$ 组信息：

每组信息的第 $1$ 行有 $4$ 个整数：$s$，这段篱笆的标号（$1\le s\le N$）；$L_s$，这段篱笆的长度（$1\le L_s\le255$）；$N1_s$（$1\le N1_s\le 8$）与本段篱笆的一端所相邻的篱笆的数量；$N2_s$（$1\le N2_s\le 8$）与本段篱笆的另一端所相邻的篱笆的数量。

每组信息的的第 $2$ 行有 $N1_s$ 个整数，分别描述与本段篱笆的一端所相邻的篱笆的标号。

每组信息的的第 $3$ 行有 $N2_s$ 个整数，分别描述与本段篱笆的另一端所相邻的篱笆的标号。`

outputFormat: 输出的内容为单独的一行，用一个整数来表示最小的周长。

hint:
题目翻译来自NOCOW。

USACO Training Section 4.1


title: 洗牌问题

description:
有 $ 2n $ 张牌，编号为

$$ 1,2,3 \dots n,n+1, \dots 2n$$

这也是最初的牌的顺序。一次洗牌是把序列变为

$$ n+1,1,n+2,2,n+3,3,n+4,4 \dots 2n,n $$

可以证明，对于任意自然数 $ n $，都可以在经过 $ m $ 次洗牌后第一次重新得到初始的顺序。

现给定 $n$（$n \le 10^8$），求出 $ m $ 的值。

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

outputFormat: 一行，一个正整数 $m$。


title: 奇怪的函数

description: 使得 $x^x$ 达到或超过 $n$ 位数字的最小正整数 $x$ 是多少？

inputFormat: 一个正整数 $n$。

outputFormat: 使得 $x^x$ 达到 $n$ 位数字的最小正整数 $x$。

hint: 对于全部数据，$1\le n\le 2\times 10^9$。


title: [USACO4.2] 草地排水Drainage Ditches

background: 在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

description:
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

inputFormat:
第一行：两个用空格分开的整数 $N$（$0 \le N \le 200$）和 $M$（$2 \le M \le 200$）。$N$ 是农夫 John 已经挖好的排水沟的数量，$M$ 是排水沟交叉点的数量。交点 $1$ 是水潭，交点 $M$ 是小溪。

第二行到第 $N + 1$ 行：每行有三个整数，$S_i, E_i, C_i$。$S_i$ 和 $E_i$（$1 \le S_i, E_i \le M$）指明排水沟两端的交点，雨水从 $S_i$ 流向 $E_i$。$C_i$（$0 \le C_i \le {10}^7$）是这条排水沟的最大容量。

outputFormat: 输出一个整数，即排水的最大流量。

hint:
题目翻译来自NOCOW。

USACO Training Section 4.2

**【数据范围】**

对于 $100 \%$ 的数据，$0 \le N, M \le 200$，$0 \le C_i \le {10}^7$。


title: [USACO4.4] 重叠的图像Frame Up

description:
看下面的五张 9 x 8 的图像：

```cpp
........   ........   ........   ........   .CCC....
EEEEEE..   ........   ........   ..BBBB..   .C.C....
E....E..   DDDDDD..   ........   ..B..B..   .C.C....
E....E..   D....D..   ........   ..B..B..   .CCC....
E....E..   D....D..   ....AAAA   ..B..B..   ........
E....E..   D....D..   ....A..A   ..BBBB..   ........
E....E..   DDDDDD..   ....A..A   ........   ........
E....E..   ........   ....AAAA   ........   ........
EEEEEE..   ........   ........   ........   ........

   1          2           3          4          5
```
现在，把这些图像按照 1—5 的编号从下到上重叠，第 1 张在最下面，第 5 张在最顶端。如果一张图像覆盖了另外一张图像，那么底下的图像的一部分就变得不可见了。我们得到下面的图像：

```cpp
             .CCC....
             ECBCBB..
             DCBCDB..
             DCCC.B..
             D.B.ABAA
             D.BBBB.A
             DDDDAD.A
             E...AAAA
             EEEEEE..
```
对于这样一张图像，计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。

下面是这道题目的规则：

矩形的边的宽度为 1 ，每条边的长度都不小于 3 。

矩形的每条边中，至少有一部分是可见的。注意，一个角同时属于两条边。

矩形用大写字母表示，并且每个矩形的表示符号都不相同。

inputFormat:
第一行 两个用空格分开的整数：图像高 H (3 <= H <=30) 和图像宽 W (3 <= W <= 30) 。

第二行到第 H+1 行 H 行，每行 W 个字母。

outputFormat: 按照自底向上的顺序输出字母。如果有不止一种情况，按照字典顺序输出每一种情况（至少会有一种合法的顺序）。

samples:
9 8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

hint:
题目翻译来自NOCOW。

USACO Training Section 4.4


title: [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包

background: upd: 新增一组 hack 数据。

description: 农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

inputFormat:
输入数据的第一行是一个整数。表示农夫约翰想要围住的放牧点的数目 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数 $x_i, y_i$ 分别代表第 $i$ 个放牧点的横纵坐标。

outputFormat: 输出输出一行一个四舍五入保留两位小数的实数，代表围栏的长度。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$-10^6 \leq x_i, y_i \leq 10^6$。小数点后最多有 $2$ 位数字。


title: [USACO5.1] 乐曲主题Musical Themes

description:
我们用 $N$（$1 \le N \le 5000$）个音符的序列来表示一首乐曲，每个音符都是 $1 \sim 88$ 范围内的整数，每个数表示钢琴上的一个键。很不幸这种表示旋律的方法忽略了音符的时值，但这项编程任务是关于音高的，与时值无关。

许多作曲家围绕一个重复出现的“主题”来构建乐曲。在我们的乐曲表示法中，“主题”是整个音符序列的一个子串，它需要满足如下条件：

1. 长度至少为 $5$ 个音符。
2. 在乐曲中重复出现（可能经过转调，见下）。
3. 重复出现的同一主题不能有公共部分。

“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。给定一段乐曲，计算其中最长主题的长度（即音符数）。

本题时限为 $1$ 秒钟！

inputFormat:
输入文件的第一行包含整数 $N$。

下面的每一行（最后一行可能除外）包含 $20$ 个整数，表示音符序列。

最后一行可能少于 $20$ 个音符。

outputFormat: 输出文件应只含一个整数，即最长主题的长度。如果乐曲中没有主题，那么输出 `0`。

hint:
题目翻译来自NOCOW。

USACO Training Section 5.1


title: [USACO5.3] 量取牛奶Milk Measuring

description:
农夫约翰要量取 $Q$（$1 \le Q \le 20,000$）夸脱（译注：即 quarts，容积单位）他的最好的牛奶，并把它装入一个大瓶子中卖出。消费者要多少，他就给多少，从不有任何误差。

农夫约翰总是很节约。他现在在奶牛五金商店购买一些桶，用来从他的巨大的牛奶池中量出 $Q$ 夸脱的牛奶。每个桶的价格一样。你的任务是计算出一个农夫约翰可以购买的最少的桶的集合，使得能够刚好用这些桶量出 $Q$ 夸脱的牛奶。另外，由于农夫约翰必须把这些桶搬回家，对于给出的两个极小桶集合，他会选择“更小的”一个，即：把这两个集合按升序排序，比较第一个桶，选择第一个桶容积较小的一个。如果第一个桶相同，比较第二个桶，也按上面的方法选择。否则继续这样的工作，直到相比较的两个桶不一致为止。例如，集合 $\{3,5,7,100\}$ 比集合 $\{3,6,7,8\}$ 要好。

为了量出牛奶，农夫约翰可以从牛奶池把桶装满，然后倒进瓶子。他决不把瓶子里的牛奶倒出来或者把桶里的牛奶倒到别处。用一个容积为 $1$ 夸脱的桶，农夫约翰可以只用这个桶量出所有可能的夸脱数。其它的桶的组合没有这么方便。

计算需要购买的最佳桶集，保证所有的测试数据都至少有一个解。

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

第二行一个整数 $P\ (1 \le  P \le 100)$，表示商店里桶的数量。

第 $3$ 至第 $P+2$ 行，每行一个整数 $h_i$ 表示第 $i$ 个桶的容积。$(1\le h_i\le 10^4)$。

outputFormat:
输出文件只有一行，由空格分开的整数组成：

为了量出想要的夸脱数，需要购买的最少的桶的数量，接着是：

一个排好序的列表（从小到大），表示需要购买的每个桶的容积

hint:
题目翻译来自NOCOW。

USACO Training Section 5.3


title: [USACO5.3] 窗体面积Window Area

description:
你刚刚接手一项窗体界面工程。窗体界面还算简单，而且幸运的是，你不必显示实际的窗体。有 5 种基本操作：

创建一个新窗体

将窗体置顶

将窗体置底

删除一个窗体

输出窗体可见部分的百分比（就是，不被其它窗体覆盖的部分）。

在输入文件中，操作（不超过 600 个）以如下的格式出现。

创建一个新窗体：w(I,x,y,X,Y)

将窗体置顶： t(I)

将窗体置底： b(I)

删除一个窗体：d(I)

输出窗体可见部分的百分比：s(I)

I 是每个窗体唯一的标识符，标识符可以是 'a'..'z', 'A'..'Z' 和 '0'..'9' 中的任何一个。输入文件中没有多余的空格。

（x,y）和（X,Y）是窗体的对角。当你创建一个窗体的时候，它自动被“置顶”。你不能用已经存在的标识符来创建窗体，但是你可以删除一个窗体后再用已删除窗体的标识符来创建窗体。坐标用正整数来表示，并且所有的窗体面积都不为 0（x <> X 且 y <> Y）。x 坐标和 y 坐标在 1 —— 32767 的范围内。

inputFormat: 输入文件包含给你的解释程序的一系列命令，每行一个。当输入文件结束时，停止程序。

outputFormat: 只对于 s(I) 命令进行输出。当然，输入文件可能有许多 s(I) 命令(不超过500次)，所以输出文件应该是一个百分比的序列，每行一个，百分比是窗体可见部分的百分比。百分比应该四舍五入到三位小数。


title: [USACO5.3] 校园网Network of Schools

description:
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 $B$ 在 $A$ 学校的分发列表中，$A$ 也不一定在 $B$ 学校的列表中。

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

inputFormat:
输入文件的第一行包括一个正整数 $N$，表示网络中的学校数目。学校用前 $N$ 个正整数标识。

接下来 $N$ 行中每行都表示一个接收学校列表（分发列表），第 $i+1$ 行包括学校 $i$ 的接收学校的标识符。每个列表用 $0$ 结束，空列表只用一个 $0$ 表示。

outputFormat:
你的程序应该在输出文件中输出两行。

第一行应该包括一个正整数，表示子任务 A 的解。

第二行应该包括一个非负整数，表示子任务 B 的解。

hint:
$2 \le N \le 100$。

题目翻译来自NOCOW。

USACO Training Section 5.3


title: [USACO5.4] 周游加拿大Canada Tour

description:
你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市必定要被访问两次（在旅行的开始和结束）。

当然不允许使用其他公司的航线或者用其他的交通工具。

给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。

inputFormat:
第 $1$ 行: 航空公司开放的城市数 $N$ 和将要列出的直达航线的数量 $V$。$N$ 是一个不大于 $100$ 的正整数。$V$ 是任意的正整数。

第 $2\sim N+1$ 行: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都 是一个字符串，最多 $15$ 字节，由拉丁字母表上的字母组成；城市名称中没有空格。

第 $N+2\sim N+2+V-1$ 行: 每行包括两个城市名称（由上面列表中的城市名称组成），用一个空格分开。这样就表示两个城市之间的直达双程航线。

outputFormat: Line 1: 按照最佳路线访问的不同城市的数量 M。如果无法找到路线，输出 1。

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

hint:
题目翻译来自NOCOW。

USACO Training Section 5.4


title: [USACO5.5] 贰五语言Two Five

description:
有一种奇怪的语言叫做“贰五语言”。它的每个单词都由A～Y这25个字母各一个组成。但是，并不是任何一种排列都是一个合法的贰五语言单词。贰五语言的单词必须满足这样一个条件：把它的25个字母排成一个5\*5的矩阵，它的每一行和每一列都必须是递增的。比如单词ACEPTBDHQUFJMRWGKNSXILOVY，它排成的矩阵如下所示：

A C E P T

B D H Q U

F J M R W

G K N S X

I L O V Y

因为它的每行每列都是递增的，所以它是一个合法的单词。而单词YXWVUTSRQPONMLKJIHGFEDCBA则显然不合法。 由于单词太长存储不便，需要给每一个单词编一个码。编码方法如下：从左到右，再从上到下，可以由一个矩阵的得到一个单词，再把单词按照字典顺序排序。比如，单词ABCDEFGHIJKLMNOPQRSTUVWXY的编码为1，而单词ABCDEFGHIJKLMNOPQRSUTVWXY的编码为2。

现在，你需要编一个程序，完成单词与编码间的转换。

inputFormat:
第一行为一个字母N或W。N表示把编码转换为单词，W表示把单词转换为编码。

若第一行为N，则第二行为一个整数，表示单词的编码。若第一行为W，则第二行为一个合法的单词。

outputFormat: 每行一个整数或单词。

hint:
题目翻译来自NOCOW。

USACO Training Section 5.5


title: [USACO4.2] 工序安排 Job Processing

description:
一家工厂的流水线正在生产一种产品，这需要两种操作：操作 $A$ 和操作 $B$。每个操作只有一些机器能够完成。

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

上图显示了按照下述方式工作的流水线的组织形式。$A$ 型机器从输入库接受工件，对其施加操作 $A$，得到的中间产品存放在缓冲库。$B$ 型机器从缓冲库接受中间产品，对其施加操作 $B$，得到的最终产品存放在输出库。所有的机器平行并且独立地工作，每个库的容量没有限制。每台机器的工作效率可能不同，一台机器完成一次操作需要一定的时间。

给出每台机器完成一次操作的时间，计算完成 $A$ 操作的时间总和的最小值，和完成 $B$ 操作的时间总和的最小值。

注：

1. 机器在一次操作中干掉一个工件；

2. 时间总和的意思是最晚时间点。

inputFormat:
第一行：三个用空格分开的整数：$N$，工件数量（$1\leq N\leq1000$）；$M_1$，$A$ 型机器的数量（$1\leq M_1\leq30$）；$M_2$，$B$ 型机器的数量 （$1\leq M_2\leq30$）。

第二行：$M_1$ 个整数，表示 $A$ 型机器完成一次操作的时间；接着是 $M_2$ 个整数，$B$ 型机器完成一次操作的时间。

outputFormat: 只有一行。输出两个整数：完成所有 $A$ 操作的时间总和的最小值，和完成所有 $B$ 操作的时间总和的最小值（$A$ 操作必须在 $B$ 操作之前完成）。

hint:
题目翻译来自 NOCOW。

USACO Training Section 4.2


title: [USACO4.3] 街道赛跑Street Race

description:
图一表示一次街道赛跑的跑道。可以看出有一些路口（用 $0$ 到 $N$ 的整数标号），和连接这些路口的箭头。路口 $0$ 是跑道的起点，路口 $N$ 是跑道的终点。箭头表示单行道。运动员们可以顺着街道从一个路口移动到另一个路口（只能按照箭头所指的方向）。当运动员处于路口位置时，他可以选择任意一条由这个路口引出的街道。

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

图一：有 $10$ 个路口的街道

一个良好的跑道具有如下几个特点：

1. 每一个路口都可以由起点到达。
2. 从任意一个路口都可以到达终点。
3. 终点不通往任何路口。

运动员不必经过所有的路口来完成比赛。有些路口却是选择任意一条路线都必须到达的（称为“不可避免”的）。在上面的例子中，这些路口是 $0$，$3$，$6$，$9$。对于给出的良好的跑道，你的程序要确定“不可避免”的路口的集合，不包括起点和终点。

假设比赛要分两天进行。为了达到这个目的，原来的跑道必须分为两个跑道，每天使用一个跑道。第一天，起点为路口 $0$，终点为一个“中间路口”；第二天，起点是那个中间路口，而终点为路口 $N$。对于给出的良好的跑道，你的程序要确定“中间路口”的集合。如果良好的跑道 $C$ 可以被路口 $S$ 分成两部分，这两部分都是良好的，并且 $S$ 不同于起点也不同于终点，同时被分割的两个部分满足下列条件：（1）它们之间没有共同的街道（2）$S$ 为它们唯一的公共点，并且 $S$ 作为其中一个的终点和另外一个的起点。那么我们称 $S$ 为“中间路口 ”。在例子中只有路口 $3$ 是中间路口。

inputFormat:
输入文件包括一个良好的跑道，最多有 $50$ 个路口，$100$ 条单行道。

共有 $N+2$ 行，前面 $N+1$ 行中第 $i$ 行表示以编号为 $i-1$ 的路口作为起点的街道，每个数字表示一个终点。行末用 `-2` 作为结束。最后一行只有一个数字 `-1`。

outputFormat:
第一行：跑道中“不可避免的路口”的数量，接着是这些路口的序号，序号按照升序排列。

第二行：跑道中“中间路口”的数量，接着是这些路口的序号，序号按照升序排列。

hint:
题目翻译来自NOCOW。

USACO Training Section 4.3


title: [USACO4.3] 字母游戏Letter Game

description:
在家里用电视机做字母游戏是很流行的，其中一种玩法是:每一个字母有一个数值与之对应.你收集字母组成一个或多个词以得到尽可能高的得分.除非你已有了 “找词的方法”(“a way with words”)，你会把你知道的字都试一遍.有时你也许会查阅其拼写，然后计算得分。显然可以用计算机更为准确地完成此任务。上图示出了英文字母及其所对应的值，当给出英文单词(word) 的表列及收集的字母时，请找出所能形成的得分最高的词或词对(pairs of words)。

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

inputFormat:
(file lgame.in)

输入文件lgame.in中有一行由小写字母(`a'到`z')组成的字符串， 这就是收集到字母(就是可以使用的字母)，字符串由至少3个字母至多7个字母(以任意顺序) 组成。

(file lgame.dict)

词典文件lgame.dict由至多40，000行组成，文件的最后一行有'.' 表示文件的结束。其它各行每一行都是由至少3个小写字母，至多7 个小写字母组成的字符串。文件中的词已按字典顺序排序。

（管理员注：读入不用开文件，先读.in，再读.dict）

outputFormat:
(file lgame.out)

在文件lgame.out的第一行，你的程序应写上最高得分(子任务A).使用上面图形中给出的字母-值对应表。

随后的每一行是由文件lgame.dict中查到的具有这个得分的所有的词和或词对(word pairs)(子任务B)。要利用图中给定的字母的值。

当两个词能够形成 一个组合(具有给定的字母)时，这两个词应该打印到同一行，两个词中间用一个空格隔开。不许重复表示词对，例如'rag prom'和'prom rag'是同样的词对，只输出字典顺序较小的那个。

输出要按照字典顺序排序，如果两个词对第一个单词的顺序相同，则按照第二个单词。一个词对中的两个单词可以相同。

samples:
SAMPLE INPUT(file lgame.in)

prmgroa
[编辑] SAMPLE INPUT(file lgame.dict)

profile
program
prom
rag
ram
rom
.

hint:
样例输入请参考原题

题目翻译来自NOCOW。

USACO Training Section 4.3


title: [USACO5.1] 夜空繁星Starry Night

background:
高高的星空，簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系，这里的连通是指水平，垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分， 星座可以相似(similar)。如果两个星座有相同的形状，而且包括相同数目的星体，那么不管其方向性如何，就算相似。一般而言，星座可能的方向有八个，如图1所示。

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

description: 夜空可以表示为一份天体图(sky map)，它是一个由字符0和1组成的二维矩阵，字符1表示所在的位置有一颗星；字符0表示该位置上是空的.给定一份天体图，用同一个小写英文标识(mark)相似的所有星座。相似的星座必须用相同的字母标识，不同的星座表示为不同的字母。标识一个星座，就是将其中各星体对应的字符1替换为相应的小写字母.

inputFormat: 文件的前两行分别记录了天体图的宽度W、深度H。而天体图则是由接下来的H行表示，每行包括W个字符. ……

outputFormat:
输出文件记录了天体图与文件STARRY.IN相似，不同之处在于，各个星座按照“任务”中的要求进行了标识(mark)。

对于同一个输入文件，可能会有很多不同的标识，此时，输出字典序最小的标识。

hint:
在这种情况下，天体图是一个长23宽为15的二维矩阵。请注意这幅天体图是对应（corresponds to）下面这个矩阵的图像。

Starry-2.gif 图starry-2：天体图

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

这是上述输入实例的一个可能的结果。请注意，该输出文件对应于下面的天空景象。

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

### 数据范围

0 <= 星空的长和宽 <= 100

0 <= 星座个数 <= 500

0 <= 不相似的星座个数 <= 26

1 <= 每个星座中星星个数 <= 160