title: 道路相遇

description:
在 H 国的小 w 决定到从城市 $u$ 到城市 $v$ 旅行，但是此时小 c 由于各种原因不在城市 $u$，但是小 c 决定到在中途与小 w 相遇

由于 H 国道路的原因，小 w 从城市 $u$ 到城市 $v$ 的路线不是固定的，为了合理分配时间，小 c 想知道从城市 $u$ 到城市 $v$ 有多少个城市小 w 一定会经过，特别地，$u, v$ 也必须被算进去，也就是说无论如何答案不会小于 2

由于各种特殊的原因，小 c 并不知道小 w 的起点和终点，但是小 c 知道小 w 的起点和终点只有 $q$ 种可能，所以对于这 $q$ 种可能，小 c 都想知道小 w 一定会经过的城市数

H 国所有的边都是无向边，两个城市之间最多只有一条道路直接相连，没有一条道路连接相同的一个城市

任何时候，H 国不存在城市 $u$ 和城市 $v$ 满足从 $u$ 无法到达 $v$

inputFormat:
第一行两个正整数 $n,m$，表示 H 国的城市数，以及道路数。

下面 $m$ 行，每行两个不同的正整数 $u, v$，表示城市 $u$ 到城市 $v$ 之间有一条边。

然后一行一个正整数 $q$。
接下来 $q$ 行，每行两个正整数 $u, v$ 表示小 w 旅行的一种可能的路线

outputFormat: 输出共 $q$ 行，每行一个正整数

hint:
从城市 $1$ 到城市 $5$ 总共有 $4$ 种可能 :

$1 \to 2 \to 3 \to 4 \to 5$

$1 \to 2 \to 3 \to 5$

$1 \to 3 \to 4 \to 5$

$1 \to 3 \to 5$

可以发现小 w 总会经过城市 $1,3,5$，所以答案为 $3$

你可以认为小 w 不会经过相同的城市两次，当然，如果你认为可以经过相同的城市两次也不会影响答案

subtask1 : 15分，$m = 5, q = 50$

subtask2 : 15分，$n = 100, q = 5000$

subtask3 : 20分，$n = 3000, q = 5\times 10^5$

subtask4 : 20分，$n = 499999, q = 5 \times 10^5, m = n-1$

subtask5 : 30分，$n = q = 5 \times 10^5$

对于所有数据 : $1\leq n\leq 5 \times 10^5, 1\leq q\leq 5\times 10^5, 1\leq m\leq \min(\frac{n(n-1)}{2}, 10^6)$


title: 随机漫游

type: P

description:
H 国有 $N$ 个城市

在接下来的 $M$ 天，小 c 都会去找小 w，但是小 c 不知道小 w 的具体位置，所以小 c 决定每次随机找一条路走，直到遇到了小 w 为止

小 c 知道小 w 只有可能是在 $c_1, c_2.. c_n$ 这 $n$ 个城市中的一个，小 c 想知道在最坏情况下，小 c 遇到小 w 期望要经过多少条道路

H 国所有的边都是无向边，两个城市之间最多只有一条道路直接相连，没有一条道路连接相同的一个城市

任何时候，H 国不存在城市 $u$ 和城市 $v$ 满足从 $u$ 无法到达 $v$

inputFormat:
输入第 1 行一个正整数$N, E$，分别表示 H 国的城市数与边的数量

输入第 2 行至第 $E+1$ 行，每行两个正整数 $u, v$，分别表示城市 $u$ 到城市 $v$ 有一条道路

输入第 $E+2$ 行一个正整数 $M$

输入第 $E+3$ 行至第 $E+M+2$ 行每行 $n+2$ 个正整数，第一个正整数为 $n$，接下来 $n$ 个互不相同的正整数 $c_i$，最后一个正整数 $s$ 表示小 c 所在的城市

outputFormat:
输出共 $M$ 行，每行一个正整数 $r$ 表示答案

如果你计算出来的期望为 $\frac{q}{p}$，其中$p, q$互质，那么你输出的 $r$ 满足 $r\times p \equiv q(\mathrm{mod}\ 998244353)$，
且$0\leq r < 998244353$，可以证明这样的 $r$是唯一的

hint:
$H$ 国的道路构成一条链，所以最坏情况下就是小 w 在深度最大的点上(以小 c 所在的城市为根)

对于第一天，小 c 所在的城市为 1，深度最大的点为 2，城市 1 只能到达城市 2，期望经过 1 条道路到达

对于第二天，小 c 所在的城市为 1，深度最大的点为 3，计算的期望经过 4 条道路到达

第三天同第二天

最坏情况也就是说经过所有 $n$ 个可能的城市至少一遍

subtask1 : 10分，$N = 4, M = 12$

subtask2 : 15分，$N =10, M = 100000$

subtask3 : 15分，$N = 18, M = 1$

subtask4 : 10分，$N = 18, M = 99995$，图是一条链

subtask5 : 10分，$N = 18, M = 99996$，所有的 $s$ 都相同

subtask6 : 15分，$N = 18, M = 99997$，$E = N-1$

subtask7 : 15分，$N = 18, M = 99998$，所有的 $s$ 都相同

subtask8 : 10分，$N = 18, M = 99999$

对于所有数据 : $1\leq N\leq 18, 1\leq M\leq 100000, 1\leq E\leq \frac{N(N-1)}{2}$


title: [WC2016] 挑战NPC

description:
小 N 最近在研究 NP 完全问题，小 O 看小 N 研究得热火朝天，便给他出了一道这样的题目：

有 $n$ 个球，用整数 $1$ 到 $n$ 编号。还有 $m$ 个筐子，用整数 $1$ 到 $m$ 编号。每个筐子最多能装 $3$ 个球。

每个球只能放进特定的筐子中。 具体有 $e$ 个条件，第 $i$ 个条件用两个整数
$v_i$ 和 $u_i$ 描述，表示编号为 $v_i$ 的球可以放进编号为 $u_i$ 的筐子中。

每个球都必须放进一个筐子中。如果一个筐子内有不超过 $1$ 个球，那么我们称这样的筐子为半空的。

求半空的筐子最多有多少个，以及在最优方案中， 每个球分别放在哪个筐子中。

小 N 看到题目后瞬间没了思路，站在旁边看热闹的小 I 嘿嘿一笑：“水题！”
然后三言两语道出了一个多项式算法。

小 N 瞬间就惊呆了，三秒钟后他回过神来一拍桌子：“不对！这个问题显然是 NP 完全问题，你算法肯定有错！”

小 I 浅笑：“所以，等我领图灵奖吧！”

小 O 只会出题不会做题，所以找到了你——请你对这个问题进行探究，并写一个程序解决此题。

inputFormat:
输入文件 $\tt{npc.in}$ 第一行包含 $1$ 个正整数 $T$， 表示有 $T$ 组数据。

对于每组数据，第一行包含 $3$ 个正整数 $n, m, e$， 表示球的个数，筐子的个数和条件的个数。

接下来 $e$ 行，每行包含 $2$ 个整数 $v_i, u_i$， 表示编号为 $v_i$ 的球可以放进编号为 $u_i$ 的筐子。

outputFormat:
输出文件为 $\tt{npc.out}$。

对于每组数据，先输出一行，包含一个整数，表示半空的筐子最多有多少个。

然后再输出一行，包含 $n$ 个整数 $p_1, p_2, ... , p_n$，相邻整数之间用空格隔开，表示一种最优解。其中 $p_i$ 表示编号为 $i$ 的球放进了编号为 $p_i$ 的筐子。 如果有多种最优解，可以输出其中任何一种。

hint:
对于所有数据， $T \leq 5, 1 \leq n \leq 3m$。 保证 $1 \leq v_i \leq n, 1 \leq u_i \leq m$，且不会出现重复的条件。

保证至少有一种合法方案，使得每个球都放进了筐子，且每个筐子内球的个
数不超过 $3$。

各测试点满足以下约定：
![QQ20180303134704.png](https://www.z4a.net/images/2018/03/03/QQ20180303134704.png)


title: 封兽鵺的激光游戏

background:
#盛大的宴会已经开始
![](https://cdn.luogu.com.cn/upload/pic/15071.png)

description:
在你的帮助下，萃香终于在一天内送出了所有的请柬。

夜幕低垂，随着由河城荷取提供的烟花"嗖"的一声蹿上天际，这场盛大的宴会终于如期开始。

顷刻之间，偌大的会场就已经被大家的欢声笑语充满：萃香和勇仪把酒言欢，散发着醉醺醺的酒香；帕秋莉和爱丽丝拽着魔理沙的两只胳膊争论着先逛哪边；琪露诺和大妖精在地上写写画画钻研着数学难题......一切都显得和谐而美满。

可是，随着会场愈发热闹，宴会的举办者萃香总感觉还是少了些什么，转念一想，她方才发觉自己没有准备游戏活动。没有游戏的宴会又怎能叫做宴会？为了解决这个严重的问题，萃香放下了酒葫芦，找到了路边的封兽鵺请她帮忙。

这可愁死封兽鵺啦！只擅长搞事情和打马赛克的她苦思冥想，终于想出了一个好主意，于是她将自己的UFO翻出来一些，再找圣白莲借几束激光，而下面就是封兽鵺制定的游戏规则：

封兽鵺在平面上放置了一些实心的质量均匀的UFO(可视为凸多边形)，由于她的能力有限，所以这些UFO最多只有五条边。现在你可以从一给定点向任意方向发射一束激光(x轴正方向为0°，y轴正方形为90°，保证发射角度为两位小数，即激光从0°开始旋转，每次旋转0.01°)，激光碰到UFO的边界便会发生反射，且激光每反射一次能量便会增加w(初始能量为0)，这里要注意的是，每当一条边被激光打中过一次后便会失去反射的能力变成一条可以直接透过的边，这时候你的激光可以直接穿进UFO的内部从内部进行反射。

如果你还没有理解，封兽鵺已经贴心的为你准备了下面这张图：
![](https://cdn.luogu.com.cn/upload/pic/15112.png)

本来唯恐天下不乱的封兽鵺想让激光射出时能量最大，但是萃香担心会场被破坏而将"能量最大"改为"能量最接近一整数E"。同时为了保证游戏的难度，封兽鵺会在游戏开始前将每个UFO绕重心顺时针旋转k*90°。

现在，轮到了你参加这个游戏，如果你射出激光的角度与封兽鵺的答案相符，那么你就会获得两份奖励——100分和封兽鵺的写真集！

当然，拥有电脑的你当然不会一次一次去试，而是通过编程预先解决这个问题，然后真正实践的时候直接用最优解拔得头筹。

inputFormat:
第一行一个整数n，为UFO的数量。

之后n行每行一个整数m，随后有m个实数对x[i],y[i]表示按顺时针顺序给出的UFO的m个顶点。

之后n行每行一个整数k，表示将该UFO顺时针旋转k*90°。

第2n+2行两个整数w和E，分别为每次反射激光的能量增量及规定的接近量。

最后一行两个实数x0，y0表示激光的射出点。

outputFormat: 一个实数d，保留到两位小数，表示使激光出射能量最接近E的出射角度。(如果有多个解符合题意，请输出角度最小的那个)

hint:
【样例解释】：

如图所示，当激光射出偏角为300.97度时恰好能反射两次，E1-2*w=2=E，符合题意
![](https://cdn.luogu.com.cn/upload/pic/15105.png)

#你需要特别注意的一些事:
1. 当一束激光碰到UFO顶点的时候不认为它们相撞
2. 多边形不会重叠，初始激光射出点不会在UFO上或UFO内
3. 不要在这里讲科学，所以激光可以射到UFO内部进行反射

【数据范围】：

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

奖励：

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

(没错就是zun绘写真集，如果你AC了此题就可以获得)


title: 萃香的请柬

background:
**管理员提示：数据中存在 $l=0$，请等同于 $l=1$ 处理。**

现在是宴会开始前一天

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

description:
萃香在小时候就一直有一个梦想，就是邀请全乡居民一起参加宴会，在上次发动异变被灵梦退治之后她仍旧没有放弃，而是在元宵节前早早准备好了难以计数的请柬。

现在，宴会即将开始，萃香却还是有一大堆请柬没有送出。经过大数学家琪露诺的严谨推算，到2018年时幻想乡的居民数目已经远远超过了外界，而这就使得宴会的邀请变得极为困难。

但是，拥有"操纵密度程度的能力"的萃香可以分成大大小小的萃香一起去送请柬。由于小萃香的移动速度过慢，因此她决定只让大萃香曲去送请柬。

开始时有S只萃香，之后每过一秒每一个大萃香会分成一大一小两个萃香，与此同时上一次分出的小萃香会积聚能量变大为大萃香。

直观的说，下面是开始只有一个大萃香时前四秒的变化情况(大萃香用"B"表示，小萃香用"L"表示)
![](https://cdn.luogu.com.cn/upload/pic/15043.png)

(很容易看出，第一次的大萃香经过一秒后分成了一大一小两只萃香，之后一秒刚才分出的大萃香继续分裂，而刚才的小萃香长大为大萃香)

可是，我们这位"小小的百鬼夜行"发现了一个严重的问题:在**经过无限长的时间**后，萃香的数目太多了。于是她决定每一次只让一段区间内的大萃香去送请柬，而她现在想要知道每一次能够送出的请柬个数。

如果你能帮她完成这个任务，她就会送给你两个奖励——100分和宴会的请柬!

inputFormat:
第一行 $S$ 个大写字母 $\verb!B!$ 或 $\verb!L!$，表示开始时萃香的状态。

之后是一个整数 $n$ 表示询问的个数。

接下来 $n$ 行每行两个整数 $l,r$ 表示询问的区间。

outputFormat: 共 $n$ 行，每行一个整数 $k$，表示区间 $[l,r]$ 中大萃香的个数。


title: [USACO06MAR] Ski Lift G

description:
科罗拉多州的山脉是二维平面上的一条折线。这条折线由 $N$ 个端点，$N−1$ 段线段组成，第 $i$ 个端点的横坐标就是 $i$，纵坐标是 $H_i$，纵坐标代表高度，也可以称为海拔。

罗恩打算为奶牛建造一个滑雪场，为此要在山脉上规划一条缆车线路。缆线也是一条折线，由若干段缆绳组成，起点在山脉的第一个端点，终点在最后一个端点。每段缆绳可以贴着山脉的轮廓，也可以悬浮于空中，跳过山脉上几个海拔低的端点。每段缆绳的水平跨度有限制，不能超过给定的整数 $K$。罗恩需要在每段缆绳的端点处修建支柱，用来固定缆绳。

请帮助他规划一下，选择在山脉的哪些端点上修建，才能使得支柱数量最少？注意，根据题意，起点和终点上是一定要修建的。

inputFormat:
第一行：两个整数 $N$ 和 $K$。

第二行到第 $N + 1$ 行，第 $i+1$ 行有一个整数 $H_i$。

outputFormat: 一行一个整数表示最少需要修建的支柱数量。

hint:
解释 最优方案是把支柱设在 $1,5,7,9,13$。$5$ 不能直接连 $9$，因为 $9$ 的海拔较高，$1$ 不能直接连 $7$，因为跨度超过了 $K$。

### 数据范围

$2 \le N \le 5000$，$1 \le K \le N − 1$，$0\le H_i \le 10^9$。


title: [Wind Festival] Finding RhFe

background:
$[Morning - 8:00 A.M.]$

热衷于结交老铁的$gyx$小哥哥听说了风筝节的举办，一大早就来到了现场，现在他已经迫不及待见到来玩的同学们啦~

description:
$gyx$的人格魅力是无限哒~

已知风筝节上有$N$($1\le N\le 10^6$)个同学（来玩的人真的很多），每个同学都对$gyx$有一个兴趣程度$c_i$（$ |c_i|\le 10^9$），因为$gyx$的性格特点太明显啦，不存在对$gyx$兴趣程度为$0$的同学，对于每个同学，都可以和$gyx$结交为老铁，$gyx$的高兴程度就是所有结！交！过！成为老铁的同学对$gyx$兴趣程度之和。$gyx$不愿意做令自己伤心的事情，所以如果所有同学对$gyx$感到反感（即兴趣程度为负）$gyx$就会直接离开风筝节。

$gyx$可以选择其中的$k$（$1\le k\le N$）个同学来结交，但一旦选择好，$gyx$的结交顺序就不可以变化了。

因为来风筝节的人实在是太多啦，$gyx$不愿意记住所有的老铁太长的时间，但是$gyx$的脑子里记着与越早结交的老铁的点点滴滴越多，也越难忘记，$gyx$忘记每个人的条件是当且仅当，在$gyx$还记着的老铁里当前的这个老铁是最后结交的。

但是由于$gyx$希望与更多不同性格的同学结交，$gyx$与每一个同学只愿意结交一次，即使遗忘以后也不会再次结交。

当风筝节上$gyx$选择的同学都结交结束后，随着时间的流逝，$gyx$也会渐渐地把所有同学都忘掉，遗忘方式与之前相同，直到最后忘记了自己结交过的所有老铁，再出发前往新的征程。

由于不同的交友并遗忘的顺序可能会发生有趣的事情，$gyx$想知道在保证自己高兴程度最大时选择好结交范围和结交顺序的情况下，$gyx$可以有多少种不同的交友并遗忘的顺序呢？

由于来风筝节的人实在是太多了，$gyx$只想知道不同顺序的方案数的值对$P$（$0<P\le 10^9$）取模后的结果。

inputFormat:
第一行是两个数$N$和$P$，分别表示来风筝节的同学人数和方案数要对P取模；

接下来的$N$行每行一个$c_i$的值，表示第$i$个同学对$gyx$的兴趣程度；

outputFormat:
如果所有人对$gyx$都感到讨厌输出“$Terrible Place$”；

其他情况输出对$P$取模后不同的顺序的方案数的值；


title: [CSP-S 2022] 星战

description:
在这一轮的星际战争中，我方在宇宙中建立了 $n$ 个据点，以 $m$ 个单向虫洞连接。我们把终点为据点 $u$ 的所有虫洞归为据点 $u$ 的虫洞。

战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：

1. 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
2. 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则**不会摧毁**。

注意：摧毁只会导致虫洞不可用，而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：

- A 型特种部队则可以将某个特定的虫洞修复。
- B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。

为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：

- 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以**实现反击**。
- 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当**只有一个从该据点出发的虫洞可用**时，这个据点可以**实现连续穿梭**。
- 如果我方所有据点都可以**实现反击**，也都可以**实现连续穿梭**，那么这个时刻就是一个绝佳的**反攻**时刻。

总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次**反攻**。

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

接下来 $m$ 行每行两个数 $u,v$，表示一个从据点 $u$ 出发到据点 $v$ 的虫洞。保证 $u \ne v$，保证不会有两条相同的虫洞。初始时所有的虫洞和据点都是完好的。

接下来一行一个正整数 $q$ 表示询问个数。

接下来 $q$ 行每行表示一次询问或操作。首先读入一个正整数 $t$ 表示指令类型：

- 若 $t = 1$，接下来两个整数 $u, v$ 表示敌人摧毁了从据点 $u$ 出发到据点 $v$ 的虫洞。保证该虫洞存在且未被摧毁。
- 若 $t = 2$，接下来一个整数 $u$ 表示敌人摧毁了据点 $u$。如果该据点的虫洞已全部被摧毁，那么这次袭击不会有任何效果。
- 若 $t = 3$，接下来两个整数 $u, v$ 表示我方修复了从据点 $u$ 出发到据点 $v$ 的虫洞。保证该虫洞存在且被摧毁。
- 若 $t = 4$，接下来一个整数 $u$ 表示我方修复了据点 $u$。如果该据点没有被摧毁的虫洞，那么这次修复不会有任何效果。

在每次指令执行之后，你需要判断能否进行一次反攻。如果能则输出 `YES` 否则输出 `NO`。

outputFormat: 输出一共 $q$ 行。对于每个指令，输出这个指令执行后能否进行反攻。


title: [Code+#3] 投票统计

description:
为了总结过去一段时间的命题工作，王队长组织了“我最喜欢的题目”评选活动，并邀请各位选手给题目进行投票。

具体来说，每道题目有一个正整数作为它的编号，一共有 $n$ 名选手给它们进行投票，每位选手投且仅投给一道题，其中第 $i$ 位选手所投票的题目编号为 $a_i$。

由于投票的选手众多，所以王队长请你来帮忙统计得票数。你需要找出收获选手投票最多的**题目数量**与**他们的编号**，并按**从小到大**的顺序列出这些编号。但这里有一个**例外情况**：如果所有被投票的题目得票数都相同，则王队长认为这次活动比较失败，你应该**输出-1**。

inputFormat:
输入数据第一行包含一个正整数 $T$，表示测试数据的组数，各组数据之间没有空行。

接下来 $2T$ 行，依次描述每组数据：

每组数据包含两行，其中第一行包含一个正整数 $n$，表示参与这次活动的选手人数。第二行包含 $n$ 个由空格隔开的正整数 $a_1\sim a_n$，其中第 $i$ 个数 $a_i$ 表示第 $i$ 位选手所投票的题目编号。

outputFormat:
输出应由 $T$ 组数据组成，各组数据之间没有空行。对于每一组数据：

若没有出现题面所述的例外情况，则这组测试数据输出两行，其中第一行输出一个正整数 $m$，表示收获选手投票最多的题目数量，第二行按**从小到大**的顺序输出 $m$ 个正整数，表示这些题目的编号。

若出现题面所述的例外情况，则这组测试数据输出一行，请**输出-1**。

hint:
测试点编号|$n$的范围|$a_i$的范围|特殊约定
-|-|-|-
1|$=2000$|$\leq n$|得票数最多的题目唯一
2|同上|同上|同上
3|同上|$\leq 10^9$|同上
4|同上|$\leq n$|不会出现例外情况
5|同上|同上|同上
6|同上|$\leq 10^9$|同上
7|同上|$\leq n$|无
8|同上|同上|同上
9|同上|$\leq 10^9$|同上
10|同上|同上|同上
11|$=100000$|$\leq n$|得票数最多的题目唯一
12|同上|同上|同上
13|同上|$\leq 10^9$|同上
14|同上|$\leq n$|不会出现例外情况
15|同上|同上|同上
16|同上|$\leq 10^9$|同上
17|同上|$\leq n$|无
18|同上|同上|同上
19|同上|$\leq 10^9$|同上
20|同上|同上|同上

Credit： https://www.luogu.org/discuss/show?postid=35727


title: [Code+#3] 白金元首与莫斯科

background:
> 莫斯科吹的寒风 / 仿佛昨日那场梦 / 啊 你还会记得我吗

1941.12.

寒冷刺骨的天气、疲惫不堪的军队…… 包围首都的作战计划陷入了困境。空军或许是拯救战况的最后希望了，元首 Adolf 想道。

description:
在一个 $n \times m$ 的网格区域中存在一个陆军单位需要补给，区域中的每个格子为空地或障碍物中的一种。航空舰队需要派遣若干运输机前往此区域，每一架运输机可以向两个相邻（有一条公共边）的空地投放物资。为防止不必要的损坏，一个标记为空地的格子至多只能得到一次投放。

由于天气原因，陆军单位所在的确切位置并不能确定。因此元首想知道，对于每个空地格子，当陆军单位在其中（视作障碍物）时，用若干（可以为 $0$）架运输机向其余空地投放任意数量的物资的不同方案数。两个投放方案不同，当且仅当存在一个格子在一个方案中被投放而另一方案中未被投放，或存在两个被投放的格子，在一个方案中被同一架运输机投放而在另一方案中非然。若仍有疑问，请参考【样例 1 解释】。

你需要编写程序帮助元首计算这些值。

inputFormat:
第 $1$ 行：两个空格分隔的正整数 $n, m$ —— 网格区域的行数和列数。
接下来 $n$ 行：其中第 $i$ 行包含 $m$ 个空格分隔的整数 $A_{i1}, A_{i2}, \ldots, A_{im}$ —— 其中 $A_{ij} = 0$ 表示第 $i$ 行第 $j$ 列的格子为空地；$A_{ij} = 1$ 表示该格为障碍物。

outputFormat: 输出 $n$ 行，第 $i$ 行包含 $m$ 个空格分隔的整数 $B_{i1}, B_{i2}, \ldots, B_{im}$ —— 若第 $i$ 行第 $j$ 列的格子为空地，$B_{ij}$ 为该格变为障碍物后投放的方案数；否则 $B_{ij} = 0$。每个答案对 $10^9+7$ 取模。


title: [Code+#3] 白金元首与克劳德斯

background:
> 千里白金雪满天　烽火江山起狼烟　分手竟兵刃相见

1941.7.

苏联军队出乎意料的反抗力量、前线德军的补给困难 —— 元首 Adolf 望着天空的云层陷入沉思……

description:
在 $xy$-直角坐标平面的天空中，有 $n$ 片四边平行于坐标轴的矩形云朵。每一片云由一个五元组 $(x_i, y_i, w_i, h_i, d_i)$ 表示，其中 $(x_i, y_i)$ 为云左下角顶点的坐标，$w_i$ 表示云在 $x$ 轴方向的宽度，$h_i$ 表示云在 $y$ 轴方向的长度，$d_i \in \{0, 1\}$ 为云的移动方向（$0$ 为横向，$1$ 为纵向）。具体来说，满足 $d_i = 0$ 的云沿 $x$ 轴正方向以每秒 $1$ 长度单位的速率不断移动，而满足 $d_i = 1$ 的云沿 $y$ 轴正方向以每秒 $1$ 长度单位的速率不断移动。

元首发现，**所有的云在此时没有重叠的面积**。他将这个时刻记作时刻 $0$。他想知道，对于 $(-\infty, +\infty)$ 中的**任意时刻**和平面上的**任意一个点**，最多可以同时被多少片云覆盖。一个点在某时刻被一朵云覆盖当且仅当这个点位于该时刻云朵所处矩形的**内部（不含边界）**。

你需要编写程序帮助元首满足他的好奇心。

inputFormat:
输入的第一行包含一个正整数 $T$ —— 数据的组数。接下来包含 $T$ 组数据，格式如下，数据间没有空行。

* 第 $1$ 行：一个正整数 $n$ —— 云朵的数量。
* 接下来 $n$ 行：每行五个空格分隔的整数 $x_i$、$y_i$、$w_i$、$h_i$ 和 $d_i$ —— 描述一朵云在时刻 $0$ 的状态。

outputFormat: 对于每组数据输出一行 —— 在任意时刻，覆盖平面上任意一个点的云朵数目的最大值。

hint:
第 $1$ 组数据中，任意时刻的任意一个点至多被惟一的一片云覆盖。

第 $2$ 组数据中，下图从左至右分别示意时刻 $0$、时刻 $4$、时刻 $11$ 的情形。

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

第 $3$ 组数据中，时刻 $0$ 对应第 $2$ 组数据时刻 $20$ 的情形。在该组数据中，$(-20, 0)$ 内的时刻均有 $2$ 片云覆盖同一个点。请注意考察范围 $(-\infty, +\infty)$ 包含时刻 $0$ 之前的时间段。

对于所有数据，有 $1 \leq T \leq 15$，$-5\times 10^8 \leq x_i, y_i \leq 5\times 10^8$，$1 \leq w_i, h_i \leq 5\times 10^8$，$d_i \in {0, 1}$。

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

Credit：https://www.luogu.org/discuss/show?postid=35727


title: [Code+#3] 博弈论与概率统计

description:
Alice 和 Bob 在玩一个双人游戏。每一轮中，Alice 有 $p$ 的概率胜利，$1-p$ 的概率失败，不会出现平局。

双方初始时各有 $0$ 分，当一个人胜利的时候，他会获得一分，失败则扣掉一分。遗憾的是，博弈论世界的人目前是无法理解负数的，因此，如果某个人输掉一轮比赛的时候他只有 $0$ 分，那么他就不会被扣分（对方会照常加一分）。游戏一共要进行 $N+M$ 轮，Alice 想请你帮她算算在游戏结束时她的得分的数学期望。

“这算啥，我小 L 分分钟搞定！”。比小 L 更熟练的你当然也是随手就算出来了，但就在你打算告诉 Alice 答案之前，博弈论世界之神——temporaryDO 出现了，他给大家带来了一个重要信息：这 $N+M$ 轮游戏中， Alice 恰好赢了 $N$ 轮！

熟知条件概率那套理论的你**立刻**注意到，你需要修改自己的计算方法来得到正确的答案了。

为了避免精度问题，请将结果对 $10^9+7$ 取模。即，我们的数据保证答案是一个有理数 $\frac{p}{q}$，且有 $10^9+7\nmid q$，你只需要找到一个整数 $x\in [0, 10^9+7)$ 使得 $qx\equiv p\pmod{10^9+7}$ 即可。

inputFormat:
输入的第一行包含两个正整数 $T$, $P'$，其中 $T$ 表示数据组数，$\frac{P'}{1000}$ 表示 $p$ ，即 Alice 在每轮游戏中的获胜概率。

接下来 $T$ 行，每行两个非负整数 $N,M$，表示一组数据。

outputFormat: 输出 $T$ 行，每行一个整数，表示对应数据的答案。

hint:
每一轮游戏 Alice 均有 $\frac{1}{2}$ 的概率胜利。

* 对于第一组数据，Alice 的胜利可能在第一轮或第二轮，并且概率相等。若她在第一轮胜利，则最终得分为 $0$，否则她的得分为 $1$。故期望为 $\frac{1}{2}$，验证发现 $2\times 500000004\equiv 1\pmod{10^9+7}$。
* 对于第二组数据，所求期望为 $\frac{3}{5}$。
* 对于第三组数据，所求期望为 $\frac{93}{70}$。

【数据范围与约定】
1. 对于 10% 的数据，$N,M,T\le 50$ 。
2. 对于另外 20% 的数据，$N,M,T\le 2000$ 。
3. 对于另外 20% 的数据，$N,M\le 10^5$，$|N-M|\le 200$，$T\le 2\times 10^5$ 。
4. 对于另外 20% 的数据，$N,M,T\le 5\times 10^4$ 。
5. 对于 100% 的数据，$N+M,T\le 2.5\times 10^5$， $0 < P' < 1000$ 。

Credit：https://www.luogu.org/discuss/show?postid=35727


title: [Code+#3] 寻找车位

description:
access_globe 有一个巨大的停车场，这个停车场有 $n$ 行，每行有 $m$ 个车位。为了美观，access_globe 在建立这个停车场时，规定这个停车场必须是长条形的，即 $n\ge m$。每个车位都是一个正方形的区域。

最近，access_globe 正在为抽不到 Missing Poster 而苦恼，因此他请你帮他维护这个停车场。你需要支持两个个事件：

- 一辆车停到某一个车位中，或一辆车从某个车位开走
- 查询一个矩形区域内最大的只包含空车位的正方形区域

如果你能帮 access_globe 高效地解决这个问题，access_globe 一定会好好奖励你的。

inputFormat:
第一行包含三个正整数 $n$、$m$、$q$，表示停车场的大小和事件的个数；

接下来 $n$ 行，每行 $m$ 个 0 或 1 的数，如果第 $i$ 行第 $j$ 的数**为 $1$**，则表示第 $i$ 行第 $j$ 列的车位**为空**，否则表示这个车位**非空**；

接下来 $q$ 行，每行表示一个事件，有以下两种形式：

- $0$ $x$ $y$ ：第 $x$ 行第 $y$ 列的车位的停车情况改变，即若此事件发生前这个车位为空，则此事件后这个车位非空，否则此事件后这个车位为空，保证 $1\le x\le n$，$1\le y\le m$
- $1$ $l$ $s$ $r$ $t$：询问以 $(l, s)$ 和 $(r,t)$ 为对角的矩形区域中，最大的全空正方形区域的边长，保证 $1\le l\le r\le n$，$1\le s\le t\le m$

outputFormat: 对每个询问输出一行一个整数，表示该询问的全空正方形的边长。

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

所有子任务的分值均等分布。

对于所有数据，保证 $n\times m\le4\times 10^6$，$q\le 2000$。

Credit：https://www.luogu.org/discuss/show?postid=35727


title: [USACO18FEB] Slingshot P

description:
One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up with an intriguing idea: instead of hauling manure between two points in a cart behind his tractor, why not shoot it through the air with a giant manure slingshot? (indeed, what could possibly go wrong...)
Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). FJ builds $N$ slingshots ($1 \leq N \leq 10^5$), where the $i$th slingshot is described by three integers $x_i$, $y_i$, and $t_i$, specifying that this slingshot can shoot manure from position $x_i$ to position $y_i$ in only $t_i$ total units of time.

FJ has $M$ piles of manure to transport ($1 \leq M \leq 10^5$). The $j$th such pile needs to be moved from position $a_j$ to position $b_j$. Hauling manure with the tractor for a distance of $d$ takes $d$ units of time. FJ is hoping to reduce this by allowing up to one use of any slingshot for transporting each pile of manure. Time FJ spends moving his tractor without manure in it does not count.

For each of the $M$ manure piles, please help FJ determine the minimum possible transportation time, given that FJ can use up to one slingshot during the process.

inputFormat: The first line of input contains $N$ and $M$. The next $N$ lines each describe a single slingshot in terms of integers $x_i$, $y_i$, and $t_i$ ($0 \leq x_i, y_i, t_i \leq 10^9$). The final $M$ lines describe piles of manure that need to be moved, in terms of integers $a_j$ and $b_j$.

outputFormat: Print $M$ lines of output, one for each manure pile, indicating the minimum time needed to transport it.

translation:
Farmer John最讨厌的农活是运输牛粪。为了精简这个过程，他产生了一个新奇的想法：与其使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点，为什么不用一个巨大的便便弹弓把牛粪直接发射过去呢？（事实上，好像哪里不太对……）
Farmer John的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。FJ建造了$N$个弹弓（$1 \leq N \leq 10^5$），其中第$i$个弹弓可以用三个整数$x_i$，$y_i$以及$t_i$描述，表示这个弹弓可以在$t_i$单位时间内将牛粪从位置$x_i$发射到位置$y_i$。

FJ有$M$堆牛粪需要运输（$1 \leq M \leq 10^5$）。第$j$堆牛粪需要从位置$a_j$移动到位置$b_j$。使用拖拉机运输牛粪，经过路程$d$需要消耗$d$单位时间。FJ希望通过对每一堆牛粪使用至多一次弹弓来减少运输时间。FJ驾驶没有装载牛粪的拖拉机的时间不计。

对这$M$堆牛粪的每一堆，在FJ可以在运输过程中使用至多一次弹弓的条件下，帮助FJ求出其最小运输时间。

输入格式（文件名：slingshot.in）：
输入的第一行包含$N$和$M$。下面$N$行，每行用$x_i$，$y_i$，$t_i$（$0 \leq x_i, y_i, t_i \leq 10^9$）描述了一个弹弓。最后$M$行用$a_j$和$b_j$描述了需要移动的牛粪。

输出格式（文件名：slingshot.out）：
输出$M$行，每堆牛粪一行，表示运输这堆牛粪需要的最短时间。

hint:
Here, the first pile of manure needs to move from position 1 to position 12. Without using an slingshot, this would take 11 units of time. However, using the first slingshot, it takes 1 unit of time to move to position 0 (the slingshot source), 1 unit of time to fling the manure through the air to land at position 10 (the slingshot destination), and then 2 units of time to move the manure to position 12. The second pile of manure is best moved without any slingshot, and the third pile of manure should be moved using the second slingshot.

Problem credits: Brian Dean


title: [USACO18FEB] New Barns P

description:
给你一棵树，初始没有节点。你需要支持两种操作：

- `B p` 表示新建一个节点，将它与 $p$  节点连接；若 $p=-1$，则表示不与其它节点相连

- `Q k` 表示查询在 $k$ 节点所在的连通块中，距它最远的点的距离。这里距离的定义是两点间经过的边数。

inputFormat:
第一行一个正整数 $q$，表示操作个数。
接下来 $q$ 行，每行表示一个操作。

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

hint:
【数据范围】

对于 $100%$ 的数据，$1 \le q \le 10^5$。
保证操作合法。

The example input corresponds to this network of barns:
```
  (1)
    \
     (2)---(4)
    /
  (3)
```
In query 1, we build barn number 1. In query 2, we ask for the distance of 1 to the farthest connected barn. Since barn 1 is connected to no other barns, the answer is 0. In query 3, we build barn number 2 and connect it to barn 1. In query 4, we build barn number 3 and connect it to barn 2. In query 5, we ask for the distance of 3 to the farthest connected barn. In this case, the farthest is barn 1, which is 2 units away. In query 6, we build barn number 4 and connect it to barn 2. In query 7, we ask for the distance of 2 to the farthest connected barn. All three barns 1, 3, 4 are the same distance away, which is 1, so this is our answer.

Problem credits: Anson Hu


title: [USACO18FEB] Cow Gymnasts P

description:
Bored of farm life, the cows have sold all their earthly possessions and joined the crew of a traveling circus. So far, the cows had been given easy acts: juggling torches, walking tightropes, riding unicycles -- nothing a handy-hoofed cow couldn't handle. However, the ringmaster wants to create a much more dramatic act for their next show.
The stage layout for the new act involves $N$ platforms arranged in a circle. On each platform, between $1$ and $N$ cows must form a stack, cow upon cow upon cow. When the ringmaster gives the signal, all stacks must simultaneously fall clockwise, so that the bottom cow in a stack doesn't move, the cow above her moves one platform clockwise, the next cow moves two platforms clockwise, and so forth. Being accomplished gymnasts, the cows know they will have no trouble with the technical aspect of this act. The various stacks of cows will not "interfere" with each other as they fall, so every cow will land on the intended platform. All of the cows landing on a platform form a new stack, which does not fall over.

The ringmaster thinks the act will be particularly dramatic if after the stacks fall, the new stack on each platform contains the same number of cows as the original stack on that platform. We call a configuration of stack sizes "magical" if it satisfies this condition. Please help the cows by computing the number of magical configurations. Since this number may be very large, compute its remainder modulo $10^9 + 7$.

Two configurations are considered distinct if there is any platform for which the configurations assign a different number of cows.

inputFormat: The input is a single integer, $N$ ($1 \leq N \leq 10^{12}$).

outputFormat: A single integer giving the number of magical configurations modulo $10^9 + 7$.

translation:
厌倦了农场生活，奶牛们变卖了所有尘世的财产，加入了一支巡回马戏团。到现在为止，奶牛们已经能够进行简单的表演了：耍火把、走钢丝、骑独轮车——没什么是拥有灵巧蹄子的奶牛做不到的。但是，马戏团指挥想要为他们的下一次演出创作一个更加激动人心的表演。

新的表演所用的舞台由$N$个围成一圈的平台组成。在每个平台上，$1$至$N$头奶牛叠成一摞，一头叠在一头上面。当指挥给出信号的时候，每摞奶牛同时顺时针落下，最下面的奶牛不动，在她上面的奶牛顺时针移动一个平台，再上面的奶牛顺时针移动两个平台，等等。作为技艺高超的体操家，奶牛们明白她们在这个表演的技术方面没有任何问题。不同摞的奶牛在下落的过程中不会相互“干扰”，所以每头奶牛都会落在预期的平台上。然后所有落在同一平台上的奶牛又会重新叠成一摞，这次她们不会再落下来。

指挥认为，如果在奶牛们落下之后，每个平台上新的那一摞奶牛的数量和原来这个平台上的那一摞奶牛数量相等的话，这次表演就会格外激动人心。我们把满足这种性质的各摞奶牛的数量排列称为是“魔幻的”。请帮助奶牛计算魔幻的排列数。由于这个数字可能非常大，计算该数mod $10^9 + 7$的余数。

两个排列被认为是不同的，如果这两个排列在任何一个平台上分配了不同数量的奶牛。

输入格式（文件名：gymnasts.in）：
输入包含一个整数$N$（$1 \leq N \leq 10^{12}$）。

输出格式（文件名：gymnasts.out）：
输出一个整数，为魔幻的排列数mod $10^9 + 7$的余数。


title: [USACO18FEB] Snow Boots G

description:
It's winter on the farm, and that means snow! There are $N$ tiles on the path from the farmhouse to the barn, conveniently numbered $1 \dots N$, and tile $i$ is covered in $f_i$ feet of snow.
In his farmhouse cellar, Farmer John has $B$ pairs of boots, numbered $1 \dots B$. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair $i$ lets FJ step in snow at most $s_i$ feet deep, and lets FJ move at most $d_i$ forward in each step.

Farmer John starts off on tile $1$ and must reach tile $N$ to wake up the cows. Tile $1$ is sheltered by the farmhouse roof, and tile $N$ is sheltered by the barn roof, so neither of these tiles has any snow. Help Farmer John determine which pairs of snow boots will allow him to make the trek.

inputFormat:
The first line contains two space-separated integers $N$ and $B$ ($1 \leq N,B \leq 10^5$).
The second line contains $N$ space-separated integers; the $i$th integer is $f_i$, the depth of snow on tile $i$ ($0 \leq f_i \leq 10^9$). It's guaranteed that $f_1 = f_N = 0$.

The next $B$ lines contain two space-separated integers each. The first integer on line $i+2$ is $s_i$, the maximum depth of snow in which pair $i$ can step. The second integer on line $i+2$ is $d_i$, the maximum step size for pair $i$. It's guaranteed that $0 \leq s_i \leq 10^9$ and $1 \leq d_i \leq N-1$.

outputFormat: The output should consist of $B$ lines. Line $i$ should contain a single integer: $1$ if Farmer John can trek from tile $1$ to tile $N$ wearing the $i$th pair of boots, and $0$ otherwise.

translation:
到冬天了，这意味着下雪了！从农舍到牛棚的路上有 $N$ 块地砖，方便起见编号为 $1 \dots N$，第 $i$ 块地砖上积了 $f_i$ 英尺的雪。
在 Farmer John 的农舍的地窖中，总共有 $B$ 双靴子，编号为 $1 \dots B$。其中某些比另一些结实，某些比另一些轻便。具体地说，第 $i$ 双靴子能够让 FJ 在至多 $s_i$ 英尺深的积雪中行走，能够让 FJ 每步至多前进 $d_i$。

Farmer John 从 $1$ 号地砖出发，他必须到达 $N$ 号地砖才能叫醒奶牛们。$1$ 号地砖在农舍的屋檐下，$N$ 号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。帮助 Farmer John 求出哪些靴子可以帮助他走完这段艰辛的路程。

**【输入格式】**

第一行包含两个空格分隔的整数 $N$ 和 $B$（$1 \leq N,B \leq 10^5$）。
第二行包含$N$个空格分隔的整数；第 $i$ 个整数为 $f_i$，即 $i$ 号地砖的积雪深度（$0 \leq f_i \leq 10^9$）。输入保证 $f_1 = f_N = 0$。

下面 $B$ 行，每行包含两个空格分隔的整数。第 $i+2$ 行的第一个数为 $s_i$，表示第 $i$ 双靴子能够承受的最大积雪深度。第 $i+2$ 行的第二个数为 $d_i$，表示第 $i$ 双靴子的最大步长。输入保证 $0 \leq s_i \leq 10^9$ 以及 $1 \leq d_i \leq N-1$。

**【输出格式】**

输出包含 $B$ 行。第 $i$ 行包含一个整数：如果 Farmer John 能够穿着第 $i$ 双靴子从 $1$ 号地砖走到 $N$ 号地砖，为 $1$，否则为 $0$。

hint: Problem credits: Dhruv Rohatgi


title: [USACO18FEB] Directory Traversal G

description:
Bessie the cow is surprisingly computer savvy. On her computer in the barn, she stores all of her precious files in a collection of directories; for example:

```
bessie/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4
```

There is a single "top level" directory, called bessie.

Bessie can navigate to be inside any directory she wants. From a given directory, any file can be referenced by a "relative path". In a relative path, the symbol ".." refers to the parent directory. If Bessie were in folder2, she could refer to the four files as follows:

```
../file1
file2
../../folder3/file3
../../file4
```

Bessie would like to choose a directory from which the sum of the lengths of the relative paths to all the files is minimized.

inputFormat:
The first line contains an integer N ($2 \leq N \leq 100,000$), giving the total number of files and directories. For the purposes of input, each object (file or directory) is assigned a unique integer ID between 1 and $N$, where ID 1 refers to the top level directory.
Next, there will be $N$ lines. Each line starts with the name of a file or directory. The name will have only lower case characters a-z and digits 0-9, and will be at most 16 characters long. Following the name is an integer, $m$. If $m$ is 0, then this entity is a file. If $m > 0$, then this entity is a directory, and it has a total of $m$ files or directories inside it. Following $m$ there will be $m$ integers giving the IDs of the entities in this directory.

outputFormat: Output the minimal possible total length of all relative paths to files. Note that this value may be too large to fit into a 32-bit integer.

translation:
奶牛Bessie令人惊讶地精通计算机。她在牛棚的电脑里用一组文件夹储存了她所有珍贵的文件，比如：
```
bessie/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4
```
只有一个“顶层”的文件夹，叫做bessie。

Bessie可以浏览任何一个她想要访问的文件夹。从一个给定的文件夹，每一个文件都可以通过一个“相对路径”被引用。在一个相对路径中，符号“..”指的是上级目录。如果Bessie在folder2中，她可以按下列路径引用这四个文件：
```
../file1
file2
../../folder3/file3
../../file4
```
Bessie想要选择一个文件夹，使得从该文件夹出发，对所有文件的相对路径的长度之和最小。

输入格式（文件名：dirtraverse.in）：
第一行包含一个整数N（$2 \leq N \leq 100,000$），为所有文件和文件夹的总数量。为了便于输入，每个对象（文件或文件夹）被赋予一个唯一的1至$N$之间的ID，其中ID 1指的是顶层文件夹。
接下来有$N$行。每行的第一项是一个文件或是文件夹的名称。名称仅包含小写字母a-z和数字0-9，长度至多为16个字符。名称之后是一个整数$m$。如果$m$为0，则该对象是一个文件。如果$m > 0$，则该对象是一个文件夹，并且该文件夹下共有$m$个文件或文件夹。在$m$之后有$m$个整数，为该文件夹下的对象的ID。

输出格式（文件名：dirtraverse.out）：
输出所有文件的相对路径的长度之和的最小值。注意这个值可能超过32位整数的表示范围。

samples:
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0

hint:
This input describes the example directory structure given above.

The best solution is to be in folder1. From this directory, the relative paths are:

```
file1
folder2/file2
../folder3/file3
../file4
```

Problem credits: Mark Gordon


title: [USACO18FEB] Taming the Herd G

description:
Early in the morning, Farmer John woke up to the sound of splintering wood. It was the cows, and they were breaking out of the barn again!
Farmer John was sick and tired of the cows' morning breakouts, and he decided enough was enough: it was time to get tough. He nailed to the barn wall a counter tracking the number of days since the last breakout. So if a breakout occurred in the morning, the counter would be $0$ that day; if the most recent breakout was $3$ days ago, the counter would read $3$. Farmer John meticulously logged the counter every day.

The end of the year has come, and Farmer John is ready to do some accounting. The cows will pay, he says! But something about his log doesn't look quite right...

Farmer John wants to find out how many breakouts have occurred since he started his log. However, he suspects that the cows have tampered with his log, and all he knows for sure is that he started his log on the day of a breakout. Please help him determine, for each number of breakouts that might have occurred since he started the log, the minimum number of log entries that must have been tampered with.

inputFormat:
The first line contains a single integer $N$ ($1 \leq N \leq 100$), denoting the number of days since Farmer John started logging the cow breakout counter.
The second line contains $N$ space-separated integers. The $i$th integer is a non-negative integer $a_i$ (at most $100$), indicating that on day $i$ the counter was at $a_i$, unless the cows tampered with that day's log entry.

outputFormat: The output should consist of $N$ integers, one per line. The $i$th integer should be the minimum over all possible breakout sequences with $i$ breakouts, of the number of log entries that are inconsistent with that sequence.

translation:
一大清早，Farmer John就被木材破裂的声音吵醒了。是这些奶牛们干的，她们又逃出牛棚了！
Farmer John已经厌烦了奶牛在清晨出逃，他觉得受够了：是时候采取强硬措施了。他在牛棚的墙上钉了一个计数器，追踪从上次出逃开始经过的天数。所以如果某一天早上发生了出逃事件，这一天的计数器就为$0$；如果最近的出逃是$3$天前，计数器读数就为$3$。Farmer John一丝不苟地记录了每一天计数器的读数。

年末到了，Farmer John准备做一些统计。他说，你们这些奶牛会付出代价的！然而他的某些记录看上去不太对劲……

Farmer John想要知道从他开始记录以来发生过多少次出逃。但是，他怀疑这些奶牛篡改了它的记录，现在他所确定的只有他是从发生出逃的某一天开始记录的。请帮助他求出，对于每个从他开始记录以来可能发生的出逃次数，他被篡改了的记录条数的最小值。

输入格式（文件名：taming.in）：
输入的第一行包含一个整数$N$（$1 \leq N \leq 100$），表示从Farmer John开始对奶牛出逃计数器进行计数以来已经经过的天数。
第二行包含$N$个空格分隔的整数。第$i$个整数是一个非负整数$a_i$（不超过$100$），表示在第$i$天计数器的数字是$a_i$，除非奶牛篡改了这一天的记录条目。

输出格式（文件名：taming.out）：
输出包含$N$个整数，每行一个。第$i$个整数为所有发生$i$次出逃的事件序列中，与该事件序列不一致的记录条目条数的最小值。

hint:
If there was only 1 breakout, then the correct log would look like 0 1 2 3 4 5, which is 4 entries different from the given log.

If there were 2 breakouts, then the correct log might look like 0 1 2 3 0 1, which is 2 entries different from the given log. In this case, the breakouts occurred on the first and fifth days.

If there were 3 breakouts, then the correct log might look like 0 1 2 0 0 1, which is just 1 entry different from the given log. In this case, the breakouts occurred on the first, fourth, and fifth days.

And so on.

Problem credits: Brian Dean and Dhruv Rohatgi


title: 河城荷取的烟花

background:
#宴会已经接近尾声
![](https://cdn.luogu.com.cn/upload/pic/15119.png)

description:
快乐的时光总是这么短暂，这场宴会终究将要闭幕。

为了给大家留下一个深刻而美好的印象，萃香拜托掌握着顶尖科技的河城荷取用她刚刚研制出的装置来点燃烟花。

这个装置由3部分构成——一些长度为1的绳子，一些长度为$\sqrt{ 2 }$的绳子，还有一块不能燃烧的木板。河城荷取将木板划分成长度为 1 的单元格，并标上坐标，之后将这些绳子摆在木板上连接成一个连通图(即绳子上的任意两点均可互相到达)。注意，这些绳子的两端必须放在单元格的顶点上，即长度为 1 的绳子只能放在单元格的某一边上，长度为$\sqrt{ 2 }$的绳子只能放在单元格的某一对角线上。

现在，河城荷取会在木板上任意一根绳子的端点处点火(不能从绳子的中间处点火)，点火后，火会沿着绳子向前燃烧（每根绳子都有自己的燃烧速度），并能点燃与它相接的其它绳子。

比如说下面这张图，河城荷取不能在 A 点点火，但在 C 点或 B点点火都是充许的。

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

为了演出效果，河城荷取必须保证所有绳子都燃烧完的总时间最短，可是由于绳子的条数过多，所以河城荷取找到了你来帮忙，让你帮她求出最短的总时间是多少。

如果你能完成这个任务，你就会获得两个奖励——100分和观赏一场盛大的烟花盛宴！

inputFormat:
第一行为一个正整数n，表示绳子的条数

接下来n行每行 5 个数： X1 Y1 X2 Y2 T,其中（X1, Y1）和（X2, Y2）分别表示绳子两端的坐标，T表示这根绳子的燃烧时间，是指从绳子的某一端点火燃烧到另一端，燃完所需的时间。

outputFormat: 第一行一个实数t，保留 4 位小数，表示所有绳子完全燃烧的最少时间。

hint:
【样例一解释】:从任一端点火都行，燃烧时间都是 1

【样例二解释】:

在 (0,0)位置点火，绳子 1, 3 和 4 将被点燃，燃烧 0.5 分钟后，绳子 2 将被从中间点燃向两端燃烧，再过 0.5 分钟，绳子 1, 3, 4 将被完全燃烧，绳子5将被点燃并在 1分钟后燃烧完 (比绳子 2 早燃完)。

绳子 2 从中间向两端燃烧 0.5 分钟以后，变成两小段，每段的燃烧时间是 4.5
分钟。但因为此时两小段绳子的另一端也同时被点燃，燃烧速度变成原来的
两倍，还需 2.25 分钟的燃烧时间， 所以总时间： 1 + 2.25 = 3.25

【数据范围】:

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


title: [NOI2004] 降雨量

description:
M 国是个多雨的国家，尤其是 P 城，频繁的降雨给人们的出行带来了不少麻烦。为了方便行人雨天过马路，有关部门在每处人行横道的上空都安装了一种名为“自动伞”的装置。（如图 $1$ 所示）
![QQ20180304213823.png](https://www.z4a.net/images/2018/03/04/QQ20180304213823.png)
每把自动伞都可以近似地看作一块长方形的板，厚度不计。这种伞有相当出色的吸水能力，落到上面的雨水都会完全被伞顶的小孔吸入，并通过管道运走。不下雨时，这些伞闲置着。一旦下雨，它们便立刻开始作匀速率直线往返运动：从马路的一边以固定的速率移动到另一边，再从另一边以相同的速率返回，如此往复，直到雨停为止。任何时刻自动伞都不会越过马路的边界。有了自动伞，下雨天没带伞的行人只要躲在伞下行走，就不会被雨淋着了。

由于自动伞的大小有限，当需要使用自动伞过马路的人比较多时，一把自动伞显然是不够的，所以有关部门在几处主要的人行横道上空安装了多把自动伞。每把自动伞的宽度都等于人行横道的宽度，高度各不相同，长度不一定相同，移动速率也不一定相同。

现在已知一处人行横道的详细情况，请你计算从开始下雨到 $T$ 秒钟后的这段时间内，一共有多少体积的雨水降落到人行横道上。

inputFormat:
第一行有四个整数 $N$，$W$，$T$，$V$。$N$ 表示自动伞的数目，$W$ 表示马路的宽度，$T$ 表示需要统计从开始下雨到多长时间后的降雨情况，$V$ 表示单位面积单位时间内的降雨体积。

为了描述方便，我们画出了一个如图 $2$ 所示的天空中五把伞的剖面图，取马路左边界为原点，取向右为 $x$ 轴正方向，取向上为 $y$ 轴正方向，建立平面直角坐标系。这样，每把自动伞都可以看作平面上的一条线段。
![QQ20180304213835.png](https://www.z4a.net/images/2018/03/04/QQ20180304213835.png)
接下来的 $N$ 行，每行用三个整数描述一把自动伞。第一个数 $x$ 是伞的初始位置，用它左端点的横坐标表示。第二个数 $l$ 是伞的长度，即 $x$ 方向上的尺寸。第三个数 $v$ 是伞的速度，$v$ 的大小表示移动的速率。如果 $v > 0$，表示开始时伞向右移动；如果 $v < 0$，表示开始时伞向左移动；如果 $v = 0$，表示伞不动。

outputFormat:
输出文件只包含一个实数，表示从开始下雨到 $T$ 秒钟后，一共有多少体积的
水降落到人行横道上。输出结果精确到小数点后第二位。

hint:
【约定】

○ 雨点均匀地匀速竖直下落

○ 自动伞和马路两者都是水平的

○ 自动伞的宽度和人行横道的宽度相等，都等于 $1$

○ $N \leq 10$

○ $W \leq 100$

○ $T \leq 100$

○ $V \leq 50$

○ 所有自动伞的往返次数之和不超过 $250$，一来一回算一个往返。


title: [NOI2004] 小H的小屋

description:
小 H 发誓要做 $21$ 世纪最伟大的数学家。他认为，做数学家与做歌星一样，第一步要作好包装，不然本事再大也推不出去。为此他决定先在自己的住所上下功夫，让人一看就知道里面住着一个“未来的大数学家”。

为了描述方便，我们以向东为 $x$ 轴正方向，向北为 $y$ 轴正方向，建立平面直角坐标系。小 H 的小屋东西长为 $100$  Hil（Hil 是小 H 自己使用的长度单位，至于怎样折合成“m”，谁也不知道）。东墙和西墙均平行于 $y$ 轴，北墙和南墙分别是斜率为 $k_1$ 和 $k_2$ 的直线，$k_1$ 和 $k_2$ 为正实数。北墙和南墙的墙角处有很多块草坪，每块草坪都是一个矩形，矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上，接触点的横坐标被称为它所在墙的“分点”，这些分点必须是 $1$ 到 $99$ 的整数。

小 H 认为，对称与不对称性的结合才能充分体现“数学美”。因此，在北墙角要有 $m$ 块草坪，在南墙角要有 $n$ 块草坪，并约定 $m \leq n$。如果记北墙和南墙的分点集合分别为 $X_1$，$X_2$，则应满足 $X_1 \subseteq X_2$，即北墙的任何一个分点一定是南墙的分点。

由于小 H 目前还没有丰厚的收入，他必须把草坪的造价降到最低，即草坪
的占地总面积最小。你能编程帮他解决这个难题吗？

inputFormat: 仅一行，包含 $4$ 个数 $k_1$，$k_2$，$m$，$n$。$k_1$ 和 $k_2$ 为正实数，分别表示北墙和南墙的斜率，精确到小数点后第一位。$m$ 和 $n$ 为正整数，分别表示北墙角和南墙角的草坪的块数。

outputFormat: 一个实数，表示草坪的最小占地总面积。精确到小数点后第一位。

hint:
![QQ20180304215637.png](https://www.z4a.net/images/2018/03/04/QQ20180304215637.png)
【约定】

○ $2 \leq m \leq n \leq 100$

○ 南北墙距离很远，不会出现南墙草坪和北墙草坪重叠的情况


title: [USACO18FEB] Rest Stops S

description:
Farmer John and his personal trainer Bessie are hiking up Mount Vancowver. For their purposes (and yours), the mountain can be represented as a long straight trail of length $L$ meters ($1 \leq L \leq 10^6$). Farmer John will hike the trail at a constant travel rate of $r_F$ seconds per meter ($1 \leq r_F \leq 10^6$). Since he is working on his stamina, he will not take any rest stops along the way.
Bessie, however, is allowed to take rest stops, where she might find some tasty grass. Of course, she cannot stop just anywhere! There are $N$ rest stops along the trail ($1 \leq N \leq 10^5$); the $i$-th stop is $x_i$ meters from the start of the trail ($0 < x_i < L$) and has a tastiness value $c_i$ ($1 \leq c_i \leq 10^6$). If Bessie rests at stop $i$ for $t$ seconds, she receives $c_i \cdot t$ tastiness units.

When not at a rest stop, Bessie will be hiking at a fixed travel rate of $r_B$ seconds per meter ($1 \leq r_B \leq 10^6$). Since Bessie is young and fit, $r_B$ is strictly less than $r_F$.

Bessie would like to maximize her consumption of tasty grass. But she is worried about Farmer John; she thinks that if at any point along the hike she is behind Farmer John on the trail, he might lose all motivation to continue!

Help Bessie find the maximum total tastiness units she can obtain while making sure that Farmer John completes the hike.

inputFormat:
The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest stop and the tastiness of the grass there.
It is guaranteed that $r_F > r_B$, and $0 < x_1 < \dots < x_N < L $. **Note that $r_F$ and $r_B$ are given in seconds per meter!**

outputFormat: A single integer: the maximum total tastiness units Bessie can obtain.

translation:
Farmer John和他的私人教练Bessie正在徒步攀登温哥牛山。基于他们的目的（也是你的目的），这座山可以用一条长为$L$米（$1 \leq L \leq 10^6$）的长直路径表示。Farmer John会沿着这条路径以每米$r_F$秒（$1 \leq r_F \leq 10^6$）的固定速度攀登。由于他正在训练他的耐力，他在途中不会进行任何的休息。
然而Bessie可以在休息站休息，在那里她能够找到一些美味的嫩草。当然，她也不能在任何地方都休息！在路径上总共有$N$个休息站（$1 \leq N \leq 10^5$）；第$i$个休息站距离路径的起点$x_i$米（$0 < x_i < L$），美味值为$c_i$（$1 \leq c_i \leq 10^6$）。如果Bessie在休息站$i$休息了$t$秒，她能够得到$c_i \cdot t$个美味单位。

不在休息站的时候，Bessie会以每米$r_B$秒（$1 \leq r_B \leq 10^6$）的固定速度攀登。由于Bessie年轻而健康，$r_B$严格小于$r_F$。

Bessie想要吃到最多的美味嫩草。然而她也担心Farmer John；她认为如果在任何时候她位于Farmer John身后，Farmer John可能就会失去前进的动力了！

帮助Bessie求出，在确保Farmer John能够完成登山的情况下，她能够获得的最多的美味单位。

输入格式（文件名：reststops.in）：
输入的第一行包含四个整数：$L$，$N$，$r_F$，以及$r_B$。下面$N$行描述了休息站。对于$1$至$N$之间的每一个$i$，第$i+1$行包含了两个整数$x_i$和$c_i$，描述了第$i$个休息站的位置和那里的草的美味值。
输入保证$r_F > r_B$，并且$0 < x_1 < \dots < x_N < L $。注意$r_F$和$r_B$的单位为秒每米！

输出格式（文件名：reststops.out）：
输出一个整数：Bessie可以获得的最多的美味单位。

hint:
In this example, it is optimal for Bessie to stop for $7$ seconds at the $x=7$ rest stop (acquiring $14$ tastiness units) and then stop for an additional $1$ second at the $x=8$ rest stop (acquiring $1$ more tastiness unit, for a total of $15$ tastiness units).

Problem credits: Dhruv Rohatgi


title: [USACO18FEB] Snow Boots S

description:
It's winter on the farm, and that means snow! There are $N$ tiles on the path from the farmhouse to the barn, conveniently numbered $1 \dots N$, and tile $i$ is covered in $f_i$ feet of snow.
Farmer John starts off on tile $1$ and must reach tile $N$ to wake up the cows. Tile $1$ is sheltered by the farmhouse roof, and tile $N$ is sheltered by the barn roof, so neither of these tiles has any snow. But to step on the other tiles, Farmer John needs to wear boots!

In his foul-weather backpack, Farmer John has $B$ pairs of boots, numbered $1 \dots B$. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair $i$ lets FJ step in snow at most $s_i$ feet deep, and lets FJ move at most $d_i$ forward in each step.

Unfortunately, the boots are packed in such a way that Farmer John can only access the topmost pair at any given time. So at any time, Farmer John can either put on the topmost pair of boots (discarding his old pair) or discard the topmost pair of boots (making a new pair of boots accessible).

Farmer John can only change boots while standing on a tile. If that tile has $f$ feet of snow, both the boots he takes off AND the boots he puts on must be able to withstand at least $f$ feet of snow. Intermediate pairs of boots which he discards without wearing do not need to satisfy this restriction.

Help Farmer John minimize waste, by determining the minimum number of pairs of boots he needs to discard in order to reach the barn. You may assume that Farmer John is initially not wearing any boots.

inputFormat:
The first line contains two space-separated integers $N$ and $B$ ($2 \leq N,B \leq 250$).
The second line contains $N$ space-separated integers. The $i$th integer is $f_i$, giving the depth of snow on tile $i$ ($0 \leq f_i \leq 10^9$). It's guaranteed that $f_1 = f_N = 0$.

The next $B$ lines contain two space-separated integers each. The first integer on line $i+2$ is $s_i$, the maximum depth of snow in which pair $i$ can step. The second integer on line $i+2$ is $d_i$, the maximum step size for pair $i$. It's guaranteed that $0 \leq s_i \leq 10^9$ and $1 \leq d_i \leq N-1$.

The boots are described in top-to-bottom order, so pair $1$ is the topmost pair in FJ's backpack, and so forth.

outputFormat: The output should consist of a single integer, giving the minimum number of boots Farmer John needs to discard. It's guaranteed that it will be possible for FJ to make it to the barn.

translation:
到冬天了，这意味着下雪了！从农舍到牛棚的路上有$N$块地砖，方便起见编号为$1 \dots N$，第$i$块地砖上积了$f_i$英尺的雪。
Farmer John从$1$号地砖出发，他必须到达$N$号地砖才能叫醒奶牛们。$1$号地砖在农舍的屋檐下，$N$号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。但是在其他的地砖上，Farmer John只能穿靴子了！

在Farmer John的恶劣天气应急背包中，总共有$B$双靴子，编号为$1 \dots B$。其中某些比另一些结实，某些比另一些轻便。具体地说，第$i$双靴子能够让FJ在至多$s_i$英尺深的积雪中行走，能够让FJ每步至多前进$d_i$。

不幸的是，这些靴子都套在一起，使得Farmer John在任何时刻只能拿到最上面的那一双。所以在任何时刻，Farmer John可以穿上最上面的一双靴子（抛弃原来穿着的那双），或是丢弃最上面的那一双靴子（使得可以拿到下面那一双）。

Farmer John只有在地砖上的时候才能换靴子。如果这块地砖的积雪有$f$英尺，他换下来的靴子和他换上的那双靴子都要能够承受至少$f$英尺的积雪。中间没有穿就丢弃的靴子无需满足这一限制。

帮助Farmer John最小化他的消耗，确定他最少需要丢弃的靴子的双数。你可以假设Farmer John在开始的时候没有穿靴子。

输入格式（文件名：snowboots.in）：
第一行包含两个空格分隔的整数$N$和$B$（$2 \leq N,B \leq 250$）。
第二行包含$N$个空格分隔的整数。第$i$个整数为$f_i$，即$i$号地砖的积雪深度（$0 \leq f_i \leq 10^9$）。输入保证$f_1 = f_N = 0$。

下面$B$行，每行包含两个空格分隔的整数。第$i+2$行的第一个数为$s_i$，表示第$i$双靴子能够承受的最大积雪深度。第$i+2$行的第二个数为$d_i$，表示第$i$双靴子的最大步长。输入保证$0 \leq s_i \leq 10^9$以及$1 \leq d_i \leq N-1$。

输出格式（文件名：snowboots.out）：
输出包含一个整数，为Farmer John需要丢弃的靴子的最小双数。输入保证Farmer John能够到达牛棚。

hint: Problem credits: Brian Dean and Dhruv Rohatgi


title: [USACO18FEB] Teleportation S

description:
One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up with a brilliant invention: the manure teleporter! Instead of hauling manure between two points in a cart behind his tractor, he can use the manure teleporter to instantly transport manure from one location to another.
Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). A teleporter is described by two numbers $x$ and $y$, where manure brought to location $x$ can be instantly transported to location $y$.

Farmer John decides to build a teleporter with the first endpoint located at $x=0$; your task is to help him determine the best choice for the other endpoint $y$. In particular, there are $N$ piles of manure on his farm ($1 \leq N \leq 100,000$). The $i$th pile needs to moved from position $a_i$ to position $b_i$, and Farmer John transports each pile separately from the others. If we let $d_i$ denote the amount of distance FJ drives with manure in his tractor hauling the $i$th pile, then it is possible that $d_i = |a_i-b_i|$ if he hauls the $i$th pile directly with the tractor, or that $d_i$ could potentially be less if he uses the teleporter (e.g., by hauling with his tractor from $a_i$ to $x$, then from $y$ to $b_i$).

Please help FJ determine the minimum possible sum of the $d_i$'s he can achieve by building the other endpoint $y$ of the teleporter in a carefully-chosen optimal position. The same position $y$ is used during transport of every pile.

inputFormat: The first line of input contains $N$. In the $N$ lines that follow, the $i$th line contains $a_i$ and $b_i$, each an integer in the range $-10^8 \ldots 10^8$. These values are not necessarily all distinct.

outputFormat: Print a single number giving the minimum sum of $d_i$'s FJ can achieve. Note that this number might be too large to fit into a standard 32-bit integer, so you may need to use large integer data types like a "long long" in C/C++. Also you may want to consider whether the answer is necessarily an integer or not...

translation:
Farmer John最讨厌的农活是运输牛粪。为了精简这个过程，他制造了一个伟大的发明：便便传送门！与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比，他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。
Farmer John的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。一个传送门可以用两个数$x$和$y$表示，被拖到地点$x$的牛粪可以瞬间传送到地点$y$。

Farmer John决定建造一个起点位于$x=0$的传送门；你的任务是帮助他确定最佳的终点$y$。具体地说，在他的农场上有$N$堆牛粪（$1 \leq N \leq 100,000$）。第$i$堆牛粪需要被从位置$a_i$移动到位置$b_i$，Farmer John会分别运输每一堆牛粪。我们设$d_i$为FJ使用拖拉机运输第$i$堆牛粪的距离，则当他直接使用拖拉机运输第$i$堆牛粪时，有$d_i = |a_i-b_i|$，或者$d_i$可能在他使用传送门的情况下可以变得更小（比方说，用他的拖拉机从$a_i$运到$x$，再从$y$运到$b_i$）。

请帮助FJ求出，在他恰当选择传送门的终点$y$的情况下，能够达到的所有$d_i$的和的最小值。在所有牛粪的运输中，终点位置$y$是相同的。

输入格式（文件名：teleport.in）：
输入的第一行包含$N$。在下面的$N$行中，第$i$行包含$a_i$和$b_i$，每个整数都在$-10^8 \ldots 10^8$之间。这些数值不一定各不相同。
输出格式（文件名：teleport.out）：
输出一个数，为能够达到的$d_i$的和的最小值。注意这个数字可能超过标准的32位整数型能够表示的范围，所以你可能需要使用更大的数据类型，例如C/C++中的“long long”。同样你可能需要考虑答案是否一定是一个整数……

hint:
In this example, by setting $y = 8$ FJ can achieve $d_1 = 2$, $d_2 = 5$, and $d_3 = 3$. Note that any value of $y$ in the range $[7,10]$ would also yield an optimal solution.

Problem credits: Brian Dean


title: [CQOI2016] 手机号码

description:
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。

工具需要检测的号码特征有两个：号码中要出现至少 $3$ 个相邻的相同数字；号码中不能同时出现 $8$ 和 $4$。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。

手机号码一定是 $11$ 位数，且不含前导的 $0$。工具接收两个数 $L$ 和 $R$，自动统计出 $[L,R]$ 区间内所有满足条件的号码数量。$L$ 和 $R$ 也是 $11$ 位的手机号码。

inputFormat: 输入文件内容只有一行，为空格分隔的 $2$ 个正整数 $L,R$。

outputFormat: 输出文件内容只有一行，为 $1$ 个整数，表示满足条件的手机号数量。


title: [CTSC2009] 移盘子

description: 已知有三根柱子，分别记为 $A$， $B$ 和 $C$。初始状态时 $A$ 上放有 $N$ 个盘子，而 $B$ 和 $C$ 两个柱子上没有放任何盘子。你每次能做的移动操作就是把某根柱子最上面的一个盘子拿下来，然后放到另一个柱子上。盘子有三类，分别用 $1$， $2$， $3$ 来表示。你的目标是，让所有 $1$ 类盘子最终放在 $A$ 上，让所有 $2$ 类盘子最终放在 $B$ 上，所有 $3$ 类盘子最终放在 $C$ 上。现在让你求出实现上述目标总共最少需要多少次移动？

inputFormat:
输入文件 trique.in 第一行包含一个整数 $N$，为盘子的总数。
第二行有 $N$ 个数，每个数只能是 $1$， $2$， $3$ 之一。这 $N$ 个数表示在初始状态时第一个柱子上所有盘子的类型，按照从上往下的顺序。

outputFormat: 输出文件 trique.out 只包含一个数，即最少的移动次数。


title: [CTSC2009] 序列变换

description:
给定一个整数序列 $X_1, X_2, X_3, ... ,X_n$ 和三个正整数 $Q, A, B$ 满足：

- $1 \leq X_i \leq Q$ 对于任意 $1 \leq i \leq n$；

- $X_i \leq X_{i+1}$ 对于任意 $1 \leq i < n$；

- $A \leq \frac{Q-1}{n-1}$ 且 $A \leq B$。

对于任意 $1 \leq i \leq n$，做如下变换：$Y_i = X_i + \delta_i$，其中 $\delta_i$ 是一个整数。使得新序列 $Y$ 满足如下性质：

- $1 \leq Y_i \leq Q$ 对于任意 $1 \leq i \leq n$；

- $Y_{i+1} - Y_i \in [A, B]$ 对于任意 $1 \leq i < n$。

对于这样一个变换，所需代价定义为 $\operatorname{TransformCost}(X, Y) = \sum_{i = 1}^{n}{\left\lvert\delta_i\right\rvert}$。

本题的任务即为寻找一个变换，使得 $\operatorname{TransformCost}(X, Y)$ 最小化。

inputFormat: 输入文件 sequence.in 包含两行。第一行 $4$ 个整数，$N, Q, A, B$。接下来一行包含 $N$ 个整数，分别为 $X_1, X_2, X_3, ... , X_n$。

outputFormat: 输出文件 sequence.out 仅包含一行，为最小的 $\operatorname{TransformCost}(X, Y)$。

hint:
### 样例说明

可以将序列变换为 $2\ 4\ 6$ 或者 $1\ 3\ 5$。前者变换代价为 $1$，后者为 $2$。因此最小 $\operatorname{TransformCost}$ 为 $1$。

### 数据规模

对于 $10\%$ 的数据 , $N \leq 100, Q \leq 10000, 1\leq A, B \leq 100$。

对于 $30\%$ 的数据 , $N \leq 10000, Q \leq 10000, 1\leq A, B \leq 100$。

对于 $60\%$ 的数据 , $N \leq 10000, Q \leq 10^9, 1\leq A, B \leq Q$。

对于 $100\%$ 的数据, $N \leq 500000, Q \leq 10^9, 1\leq A, B \leq Q$。


title: [CQOI2016] 不同的最小割

description:
学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 $s,t$ 不在同一个部分中，则称这个划分是关于 $s,t$ 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 $s,t$ 的最小割指的是在关于 $s,t$ 的割中容量最小的割。

而对冲刺 NOI 竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽，考虑有 $N$ 个点的无向连通图中所有点对的最小割的容量，共能得到 $N(N-1)/2$ 个数值。这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。

inputFormat:
第一行包含两个数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行三个数 $u,v,w$，表示点 $u$ 和点 $v$ (从 $1$ 开始标号) 之间有一条权值是 $w$ 的边。

outputFormat: 第一行为一个整数，表示不同的最小割容量的个数。


title: CPU 监控

background:
Bob 家的机子很烂……真的很烂……

以至于看视频或者跑邪恶的暴力程序的时候，由于 CPU 使用率持续过高而宕机。

description:
Bob 需要一个程序来监视 CPU 使用率。这是一个很繁琐的过程，为了让问题更加简单，Bob 会慢慢列出今天会在用计算机时做什么事。

Bob 会干很多事，除了跑暴力程序看视频之外，还会做出去玩玩和用鼠标乱点之类的事，甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内 CPU 使用率增加或减少一个值；有的事还会直接让 CPU 使用率变为一个值。

当然 Bob 会询问：在之前给出的事件影响下，CPU 在某段时间内，使用率最高是多少。有时候 Bob 还会好奇地询问，在某段时间内 CPU 曾经的最高使用率是多少。

为了使计算精确，使用率不用百分比而用一个整数表示。

不保证 Bob 的事件列表没有出莫名的问题，使得使用率为负………………

inputFormat:
第一行一个正整数 $T$，表示 Bob 需要监视 CPU 的总时间。

然后第二行给出 $T$ 个数表示在你的监视程序执行之前，Bob 干的事让 CPU 在这段时间内每个时刻的使用率达已经达到了多少。

第三行给出一个整数 $E$，表示 Bob 需要做的事和询问的总数。

接下来 $E$ 行每行表示给出一个询问或者列出一条事件：

- `Q X Y`：询问从 $X$ 到 $Y$ 这段时间内 CPU 最高使用率。
- `A X Y`：询问从 $X$ 到 $Y$ 这段时间内之前列出的事件使 CPU 达到过的最高使用率。
- `P X Y Z`：列出一个事件这个事件使得从 $X$ 到 $Y$ 这段时间内 CPU 使用率增加 $Z$。
- `C X Y Z`：列出一个事件这个事件使得从 $X$ 到 $Y$ 这段时间内 CPU 使用率变为 $Z$。

时间的单位为秒，使用率没有单位。

$X$ 和 $Y$ 均为正整数（$X\le Y$），$Z$ 为一个整数。

从 $X$ 到 $Y$ 这段时间包含第 $X$ 秒和第 $Y$ 秒。

保证必要运算在有符号 32 位整数以内。

outputFormat: 对于每个询问，输出一行一个整数回答。

hint:
数据分布如下：

第 $1,2$ 个数据保证 $T$ 和 $E$ 均小于等于 $10^3$。

第 $3,4$ 个数据保证只有 `Q` 类询问。

第 $5,6$ 个数据保证只有 `C` 类事件。

第 $7,8$ 个数据保证只有 `P` 类事件。

对于 $100\%$ 的数据，$1\le T,E\le 10^5$，$1\le X\le Y\le T$，$-2^{31}\leq Z\lt 2^{31}$。


title: [AHOI2008] 逆序对

description:
暑假到了，小可可和伙伴们来到海边度假，距离海滩不远的地方有个小岛，叫做欢乐岛，整个岛是一个大游乐园，里面有很多很好玩的益智游戏。碰巧岛上正在举行“解谜题赢取免费门票”的活动，只要猜出来迷题，那么小可可和他的朋友就能在欢乐岛上免费游玩两天。

迷题是这样的：给出一串全部是正整数的数字，这些正整数都在一个范围内选取，谁能最快求出这串数字中“逆序对”的个数，那么大奖就是他的啦！

当然、主办方不可能就这么简单的让迷题被解开，数字串都是被处理过的，一部分数字被故意隐藏起来，这些数字均用-1来代替，想要获得大奖就必须求出被处理的数字串中最少能有多少个逆序对。小可可很想获得免费游玩游乐园的机会，你能帮助他吗？

注：“逆序对”就是如果有两个数A和B，A在B左边且A大于B，我们就称这两个数为一个“逆序对”，例如：4 2 1 3 3里面包含了5个逆序对：(4, 2)、(4, 1)、(4, 3)、(4, 3)、(2, 1)。

    假设这串数字由5个正整数组成，其中任一数字N均在1～4之间，数字串中一部分数字被“-1”替代后，如：4 2 -1 -1 3 ，那么这串数字，可能是4 2 1 3 3，也可能是4 2 4 4 3，也可能是别的样子。你要做的就是根据已知的数字，推断出这串数字里最少能有多少个逆序对。

inputFormat:
第一行两个正整数N和K；

第二行N个整数，每个都是-1或是一个在1~K之间的数（N<=10000，K<=100）。

outputFormat: 一个正整数，即这些数字里最少的逆序对个数。

hint:
100%的数据中，N<=10000，K<=100。

60%的数据中，N<=100。

40%的数据中，-1出现不超过两次。


title: [AHOI2008] 紧急集合 / 聚会

description:
欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有 $n$ 个等待点，有 $n-1$ 条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在 $n$ 个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

inputFormat:
第一行两个正整数 $n$ 和 $m$，分别表示等待点的个数（等待点也从 $1$ 到 $n$ 进行编号）和获奖所需要完成集合的次数。

随后 $n-1$ 行，每行两个正整数 $a,b$，表示编号为 $a$ 和编号为 $b$ 的等待点之间有一条路。

随后 $m$ 行，每行用三个正整数 $x,y,z$，表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

outputFormat: 输出共 $m$ 行，每行两个用空格隔开的整数 $p,c$。其中第 $i$ 行表示第 $i$ 次集合点选择在编号为 $p$ 的等待点，集合总共的花费是 $c$ 个游戏币。

hint:
对于 $40\%$ 的数据，$n\leq2\times10^3$，$m\leq2\times 10^3$。

对于 $100\%$ 的数据，$1\leq x,y,z\leq n\leq 5\times10^5$，$1\leq m\leq 5\times 10^5$。


title: [AHOI2008] 计算器

description:
小可可在欢乐岛的快乐旅程还在继续，他想买一些纪念品带回去给同学们，于是来到了礼品部，在这里他发现了一个有趣的计算器.

这个计算器是一种特殊的、支持变进制整数加减运算的计算器（所谓变进制，就是每一位的进制可以不同。例如，如果最低位是 3 进制，次低位是 5 进制，那么这种情况的 42 转化成十进制就是 $4\times 3+2=14$）。

店主看小可可对这个计算器非常感兴趣，于是他问小可可：“小朋友，如果我告诉你这个计算器最多可以支持 $N$ 位的变进制整数，且每一位的进制分别是 $x_1,x_2,\ldots,x_n$，那么你知道它能表示的最大整数 $M$ 是多少吗?”，小可可想了想说到：“它所能表示的最大的整数 $M$ 是 $(x_1\times x_2\times \cdots\times x_n)-1$。”

店主非常高兴，说道：“你真是个聪明的孩子，如果我告诉你两个长度为 $N$ 的变进制整数 $A,B$，你按照我的要求来计算 $(A＋B)\bmod(M+1)$ 或 $(A-B)\bmod(M+1)$，答案还是用相同的变进制来表示，如果你算对了，那么我就把这个计算器送给你。”

这下把小可可难住了，但是他非常想要这个计算器，聪明的你能够帮助小可可吗?

inputFormat:
第一行包含一个整数 $N$，表示计算器所支持的变进制数的长度。

第二行包含 $N$ 个整数 $x_1,x_2,\ldots,x_N$，表示第 $1\sim n$ 位的进制（从最高位到最低位）。

第三行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示第一个运算数。

第四行包含一个字符 $op$，表示需要实现的运算类型。

第五行包含 $N$ 个整数 $B_1,B_2,\ldots,B_N$，表示第二个运算数。

outputFormat: 若 $op$ 为 `＋`，则输出 $(A+B)\bmod(M+1)$ 的值，否则输出 $(A-B)\bmod(M+1)$ 的值，每一位之间用一个空格隔开，注意高位补零，最高位之前和最低位之后不要有空格。


title: [AHOI2008] Y型项链

description:
欢乐岛上众多新奇的游乐项目让小可可他们玩的非常开心。现在他们正在玩比赛串项链的游戏，谁串的最快就能得到优厚的奖品。

这可不是普通的项链，而是一种 Y 型项链，项链的最中间有一颗大珍珠作为结合点，从大珍珠上连出来 3 条由各种宝石串起来的链子。

比赛的规则是这样的：每次可以从三条链子中某一条的一端取下来一个宝石，或者安上去一个宝石，称为一次操作，经过若干次操作，最终使得三条链子完全相同。想要赢得比赛，那么只能使用尽量少的操作次数。

假设每种宝石都有无数多个以供使用，且链子足够长。你能帮助小可可赢得比赛吗？

注：由于对 Y 型项链的宝石数没有特殊的要求，所以即使你把所有宝石都取下来，也是一个可以接受的方案（三根没有串宝石的绳子也是完全一样的）。

inputFormat: 一共有 $3$ 行，表示 Y 型项链的三条链子，每行开始有一个整数 $N$ ，表示初始时这条链子上串有 $N$ 个宝石，随后是一个空格，然后是 $N$ 个大写字母，表示这个链子上的宝石，每个字母表示一种不同的宝石，这个字符串最左边的字符表示的是离大珍珠最近的那个宝石，而最右边的表示的是在链子末端的宝石。

outputFormat: 只有一个整数，表示所需要的最少的操作次数。


title: [SHOI2008] 小约翰的游戏

description:
小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有 $n$ 堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。

小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。

inputFormat:
本题的输入由多组数据组成，第一行包括一个整数 $T$（$1 \leq T \leq 500$），表示输入总共有 $T$ 组数据。

每组数据的第一行包括一个整数 $N$（$1 \leq N \leq 50$），表示共有 $N$ 堆石子，接下来有 $N$ 个不超过 $5000$ 的整数，分别表示每堆石子的数目。

outputFormat: 对于每组数据，如果约翰能赢得比赛，则输出 `John`，否则输出 `Brother`，请注意单词的大小写。


title: [SHOI2008] 汉诺塔

description:
汉诺塔由三根柱子（分别用A、B、C表示）和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上，大的在下面，小的在上面，形成了一个塔状的锥形体。
    对汉诺塔的一次合法的操作是指：从一根柱子的最上层拿一个盘子放到另一根柱子的最上层，同时要保证被移动的盘子一定放在比它更大的盘子上面（如果移动到空柱子上就不需要满足这个要求）。我们可以用两个字母来描述一次操作：第一个字母代表起始柱子，第二个字母代表目标柱子。例如，AB就是把柱子A最上面的那个盘子移到柱子B。汉诺塔的游戏目标是将所有的盘子从柱子A移动到柱子B或柱子C上面。
有一种非常简洁而经典的策略可以帮助我们完成这个游戏。首先，在任何操作执行之前，我们以任意的次序为六种操作（AB、AC、BA、BC、CA和CB）赋予不同的优先级，然后，我们总是选择符合以下两个条件的操作来移动盘子，直到所有的盘子都从柱子A移动到另一根柱子：
（1）这种操作是所有合法操作中优先级最高的；
（2）这种操作所要移动的盘子不是上一次操作所移动的那个盘子。
可以证明，上述策略一定能完成汉诺塔游戏。现在你的任务就是假设给定了每种操作的优先级，计算按照上述策略操作汉诺塔移动所需要的步骤数。

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

inputFormat: 输入有两行。第一行为一个整数n（1≤n≤30），代表盘子的个数。第二行是一串大写的ABC字符，代表六种操作的优先级，靠前的操作具有较高的优先级。每种操作都由一个空格隔开。

outputFormat: 只需输出一个数，这个数表示移动的次数。我们保证答案不会超过10的18次方。

hint:
对于20%的数据，n ≤ 10。
对于100%的数据，n ≤ 30。


title: [SHOI2008] 安全的航线

description:
在设计航线的时候，安全是一个很重要的问题。首先，最重要的是应采取一切措施确保飞行不会发生任何事故，但同时也需要做好最坏的打算，一旦事故发生，就要确保乘客有尽量高的生还几率。

当飞机迫降到海上的时候，最近的陆地就是一个关键的因素。航线中最危险的地方就是距离最近的陆地最远的地方，我们称这种点为这条航线“孤地点”。孤地点到最近陆地的距离被称为“孤地距离”。作为航空公司的高级顾问，你接受的第一个任务就是尽量找出一条航线的孤地点，并计算这条航线的孤地距离。

为了简化问题，我们认为地图是一个二维平面，陆地可以用多边形近似，飞行线路为一条折线。航线的起点和终点都在陆地上，但中间的转折点是可能在海上（如下图所示，方格标示出了孤地点）。

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

inputFormat:
输入的第一行包括两个整数C和N（1≤C≤20，2≤N≤20），分别代表陆地的数目的航线的转折点的数目。

接下来有N行，每行有两个整数x,y。(x,y)表示一个航线转折点的坐标，第一个转折点为航线的起点，最后一个转折点为航线的终点。

接下来的输入将用来描述C块大陆。每块输入由一个正整数M开始（M≤30），M表示多边形的顶点个数，接下来的M行，每行会包含两个整数x,y，(x,y)表示多边形的一个顶点坐标，我们保证这些顶点以顺时针或逆时针给出了该多边形的闭包，不会出现某些边相交的情况。此外我们也保证输入数据中任何两块大陆不会相交。

输入的所有坐标将保证在-10,000到10,000的范围之间。

outputFormat: 输出一个浮点数，表示航线的孤地距离，数据保留2位小数。

hint:
对于50%的数据，1≤C≤2，2≤N≤5;

对于100%的数据，1≤C≤20，2≤N≤20。


title: [SHOI2011] 双倍回文

description:
记字符串 $w$ 的倒置为 $w^{\mathsf R}$。例如$\tt (abcd)^{\mathsf R}=dcba$，$\tt (abba)^{\mathsf R}=abba$。

对字符串 $x$，如果 $x$ 满足 $x^{\mathsf R}=x$，则称之为回文。例如 $\tt abba$ 是一个回文，而 $\tt abed$ 不是。

如果 $x$ 能够写成 $ww^{\mathsf R} ww^{\mathsf R}$ 形式，则称它是一个“双倍回文”。换句话说，若要 $x$ 是双倍回文，它的长度必须是 $4$ 的倍数，而且 $x$，$x$ 的前半部分，$x$ 的后半部分都要是回文。例如 $\tt abbaabba$ 是一个双倍回文，而 $\tt abaaba$ 不是，因为它的长度不是 $4$ 的倍数。

- $x$ 的子串是指在 $x$ 中连续的一段字符所组成的字符串。例如 $\tt be$ 是 $\tt abed$ 的子串，而 $\tt ac$ 不是。
- $x$ 的回文子串，就是指满足回文性质的 $x$ 的子串。
- $x$ 的双倍回文子串，就是指满足双倍回文性质的 $x$ 的子串。

你的任务是，对于给定的字符串，计算它的最长双倍回文子串的长度。

inputFormat:
输入分为两行。

第一行为一个整数，表示字符串的长度。
第二行有个连续的小写的英文字符，表示字符串的内容。

outputFormat: 输出文件只有一行即输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出 $0$。

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

对于全部数据，$1\le N \le 500000$。


title: [SHOI2014] 信号增幅仪

description:
无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功
耗与圆的半径的平方成正比。现给出平面上若干网络用户的位置，请你选择一
个合适的位置建设无线基站 ……

就在你拿起键盘准备开始敲代码的时候，你的好朋友发明家SHTSC 突然出
现了。SHTSC 刚刚完成了他的新发明——无线信号增幅仪。增幅仪能够在不增
加无线基站功耗的前提下，使得有效信号的覆盖范围在某一特定方向上伸长若
干倍。即：使用了增幅仪的无线基站覆盖范围是个椭圆，其功耗正比于半短轴
长的平方。

现给出平面上若干网络用户的位置，请你选择一个合适的位置建设无线基
站，并在增幅仪的帮助下使所有的用户都能接收到信号，且无线基站的功耗最
小。

注意：由于SHTSC 增幅仪的工作原理依赖地磁场，增幅的方向是恒定的。

inputFormat:
第一行一个整数：n。平面内的用户个数。之后的n 行每行两个整数x, y，表示一个用户的位置。

第n+2 行一个整数：a。表示增幅仪的增幅方向，单位是度。表示增幅仪的
方向是从x 正方向逆时针转a 度。

第n+3 行一个整数：p。表示增幅仪的放大倍数。

outputFormat: 输出一行一个实数，为能够覆盖所有用户的最小椭圆的半短轴长，四舍五入到三位小数。

hint:
- 对于10%的数据，保证最优方案的中心在原点。
- 对于20%的数据，保证点是随机生成的。
- 对于30%的数据，n≤100。
- 对于50%的数据，n≤5000。
- 对于100%的数据，n≤50000，0≤a<180，1≤p≤100，|x|,|y|≤$2×10^8$。


title: [SHOI2014] 概率充电器

description:
著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器：

“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI 概率充电器，您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”

SHOI 概率充电器由 $n-1$ 条导线连通了 $n$ 个充电元件。进行充电时，每条导线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

作为 SHOI 公司的忠实客户，你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道，进入充电状态的元件个数的期望是多少呢？

inputFormat:
第一行一个整数 $n$。概率充电器的充电元件个数。充电元件由 $1 \sim n$ 编号。

之后的 $n-1$ 行每行三个整数 $a, b, p$，描述了一根导线连接了编号为 $a$ 和 $b$ 的充电元件，通电概率为 $p\%$。

第 $n+2$ 行 $n$ 个整数 $q_i$。表示 $i$ 号元件直接充电的概率为 $q_i\%$。

outputFormat: 输出一行一个实数，为能进入充电状态的元件个数的期望，四舍五入到小数点后 6 位小数。

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

对于 $100\%$ 的数据，$n \leq 5 \times 10^5$，$0 \leq p,q_i \leq 100$。


title: [HAOI2008] 移动玩具

description: 在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

inputFormat: 前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。

outputFormat: 一个整数，所需要的最少移动次数。


title: [HAOI2008] 玩具取名

description:
某人有一套玩具，并想法给玩具命名。首先他选择 `W, I, N, G` 四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用 `W, I, N, G` 中任意两个字母代替，使得自己的名字能够扩充得很长。

现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

inputFormat:
第一行四个整数 $W, I, N, G$。表示每一个字母能由几种两个字母所替代。

接下来 $W$ 行，每行两个字母,表示 `W` 可以用这两个字母替代。

接下来 $I$ 行，每行两个字母，表示 `I` 可以用这两个字母替代。

接下来 $N$ 行，每行两个字母，表示 `N` 可以用这两个字母替代。

接下来 $G$ 行，每行两个字母，表示 `G` 可以用这两个字母替代。

最后一行一个长度不超过 $L$ 的字符串。表示这个玩具的名字。

outputFormat:
一行字符串，该名字可能由哪些字母变形而得到。（按照 `W, I, N, G` 的顺序输出）

如果给的名字不能由任何一个字母变形而得到则输出 `The name is wrong!`。


title: [SCOI2003] 字符串折叠

description:
折叠的定义如下：

1. 一个字符串可以看成它自身的折叠。记作 ```S = S```

2. ```X(S)``` 是 $X$ 个 ```S``` 连接在一起的串的折叠。记作 ```X(S) = SSSS…S```。

3. 如果 ```A = A’```, ```B = B’```，则 ```AB = A’B’ ```。例如：因为 ```3(A) = AAA```, ```2(B) = BB```，所以 ```3(A)C2(B) = AAACBB```，而 ```2(3(A)C)2(B) = AAACAAACBB```

给一个字符串，求它的最短折叠。

例如 ```AAAAAAAAAABABABCCD``` 的最短折叠为：```9(A)3(AB)CCD```。

inputFormat: 仅一行，即字符串 `S`，长度保证不超过 $100$。

outputFormat: 仅一行，即最短的折叠长度。


title: 首都

description:
在 X 星球上有 $n$ 个国家，每个国家占据着 X 星球的一座城市，城市从 $1$ 至 $n$ 编号。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。

X 星球上战乱频发，如果 A 国打败了 B 国，那么 B 国将永远从这个星球消失，而 B 国的国土也将归 A 国管辖。A 国国王为了加强统治，会在 A 国和 B 国之间修建一条公路，即选择原 A 国的某个城市和 B 国某个城市，修建一条连接这两座城市的公路。

同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。

现在告诉你发生在 X 星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：

- `A x y`：表示某两个国家发生战乱，战胜国选择了 $x$ 城市和 $y$ 城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
- `Q x`：询问当前编号为 $x$ 的城市所在国家的首都。
- `Xor`：询问当前所有国家首都编号的异或和。

inputFormat:
输入的第一行有两个整数，分别表示城市数 $n$ 和需要处理的信息数 $m$。

接下来 $m$ 行，每行首先有一个字符串 $op$，表示信息类型，后有若干个整数，其格式如【题目描述】所示。

outputFormat: 对于每个 `Q` 操作和 `Xor` 操作，输出一行一个整数表示答案。

samples:
10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor

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

对于全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq x, y \leq n$。


title: [WC2010] 重建计划

description:
X 国遭受了地震的重创, 导致全国的交通近乎瘫痪，重建家园的计划迫在眉睫。X 国由 $N$ 个城市组成, 重建小组提出，仅需建立 $N-1$ 条道路即可使得任意两个城市互相可达。于是，重建小组很快提出了一个包含 $N-1$ 条道路的方案，并满足城市之间两两可达，他们还计算评估了每条道路 $e$ 建设之后可以带来的价值 $v(e)$。

由于重建计划复杂而艰难，经费也有一定限制。因此，政府要求第一期重建工程修建的道路数目为 $k$ 条，但需满足 $L \leq k \leq U$，即不应少于$L$ 条，但不超过 $U$ 条。同时，为了最大化利用率，要求建设的这些道路恰好组成一条简单路径，即所建设的 $k$ 条路径可以构成一个排列 $e_1 = (p_1, q_1), e_2 = (p_2, q_2), \cdots , e_k = (p_k, q_k)$， 对于 $1 \leq i < k$， 有$(q_i = p_{i+1})$。

重建小组打算修改他们的原有方案以满足要求，即在原有的 $N-1$ 条道路中寻找一条路径 $S$ 作为新的方案，使得新方案中的道路平均价值

$$AvgValue = \frac{\sum _{e \in S} v(e)}{|S|}$$

最大。这里 $v(e)$ 表示道路 $e$ 的价值，$|S|$ 表示新方案中道路的条数。请你帮助重建小组寻找一个最优方案。  注: 在本题中 $L$ 和 $U$ 的设置将保证有解。

inputFormat:
第一行包含一个正整数 $N$ ，表示 X 国的城市个数。

第二行包含两个正整数 $L,U$，表示政府要求的第一期重建方案中修建道路数的上下限。

接下来的 $N-1$ 行描述重建小组的原有方案，每行三个正整数 $a_i, b_i, v_i$，分别表示道路 $(a_i, b_i)$，其价值为 $v_i$ 。其中城市由$1 \cdots N$标号。

outputFormat:
仅包含一行，为一个实数 $AvgValue$，即最大平均价值。

小数点后保留三位。

hint:
新方案中选择路径 $(3, 1), (1, 4)$ 可以得到的平均价值为 $2.5$，为最大平均价值。

对于20%的数据，$N \leq 5 000$;

另有30%的数据，$N \leq 100 000$， 原有方案恰好为一条路径(链);

对于100%的数据，$N \leq 100 000, 1 \leq L \leq U \leq N-1, v_i \leq 10^6$。


title: [WC2010] 能量场

background:
官方spj：https://www.luogu.org/paste/03wjc4ne

spj provider: @hehezhou

description:
物理学家栋栋最近在研究一个能量场。在这个能量场中有n个粒子，每个粒子都有两个属性：质量m和结合系数c。

栋栋发现，在这个能量场中，每个粒子都有两极，N极和S极。两个粒子相遇时，符合“同极相斥，异极相吸”的原则，只能是一个粒子的N极和另一个粒子的S极连接到一起。当质量为ma，结合系数为ca的粒子a的N极与另一个质量为mb，结合系数为cb的粒子b的S极直接连接时，可以产生大小为  $m_a m_b (c_a - c_b)$  的结合能量。

请解决以下两个问题：
1. 在能量场的n个粒子中哪两个粒子直接连接的能量最大。
2. 栋栋发明了一种方法，能选择其中的任意k个粒子p1, p2, …, pk，将pi的 N极与pi+1的S极连接(1 ≤ i < k)， pk的N极与p1的S极连接， 其中p1, p2, …, pk两两不同。k可以在1至n中任意取值，如使用栋栋的这种方法连接，选择哪些粒子可以得到最大的能量。

inputFormat:
第一行包含一个整数n，表示粒子的个数。

 接下来n行，每行两个实数，第i+1行的两个实数表示第i个粒子的质量mi和结合系数ci。(0< mi, ci <10^5)

outputFormat:
第一行包含两个整数a, b，表示将粒子a的N极与粒子b的S极连接可以得到最大的能量。

第二行包含一个整数k，表示第二问中要得到最大的能量需要多少个粒子。 第三行包含k个整数，表示p1, p2, …, pk，即第二问中的最优方案。

hint:
【样例说明】
对于第一问，第三个粒子的N极与第二个粒子的S极连接，能得到的能量为$5\times3\times(4-1) = 45$。

对于第二问，顺次连接1, 3, 2号粒子，能量为  $1\times5\times(2-4) + 5\times3\times(4-1) + 3\times1\times(1-2) = 32$。

【数据规模】

10%的数据，n ≤ 8；

20%的数据，n ≤ 15；

40%的数据，n ≤ 1 000；

50%的数据，n ≤ 5 000；

100%的数据，n ≤ 50 000。

【评分标准】

此题可能有多解，如果用你的解产生的能量与参考答案的绝对误差或相对误差小于10–5，则得满分。否则不得分。  对于本题，每问的分数各占50%。如果你的输出任何一问的格式或结果不正确，则不得分；否则如果其中的一问正确，则得到该测试点50%的分数；如果两问都正确，得到该测试点100%的分数。


title: [WC2008] 游览计划

background:
UPD：

- @panda_2134 提供 Special Judge；

- @yzy1 提供了[两组 hack 数据](https://www.luogu.com.cn/discuss/527294)，即不算分的 subtask1；

- @kradcigam [完善](https://www.luogu.com.cn/discuss/873182)了 Special Judge。

description:
从未来过绍兴的小D有幸参加了Winter Camp 2008，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。

主办者将绍兴划分为N行M列(N×M)个分块，如下图(8×8)：

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

景点含于方块内，且一个方块至多有一个景点。无景点的方块视为路。

为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的志愿者；在景点内聘请导游（导游不是志愿者）。在选择旅游方案时，保证任意两个景点之间，存在一条路径，在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要，又能够让志愿者的总数最少。

例如，在上面的例子中，在每个没有景点的方块中填入一个数字，表示控制该方块最少需要的志愿者数目：

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

图中用深色标出的方块区域就是一种可行的志愿者安排方案，一共需要20名志愿者。由图可见，两个相邻的景点是直接（有景点内的路）连通的（如沈园和八字桥）。

现在，希望你能够帮助主办方找到一种最好的安排方案。

inputFormat:
第一行有两个整数，N和M，描述方块的数目。

接下来N行，每行有M个非负整数，如果该整数为0，则该方块为一个景点；

否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，

行首行末也可能有多余的空格。

outputFormat:
由N+1行组成。第一行为一个整数，表示你所给出的方案中安排的志愿者总数目。

接下来N行，每行M个字符，描述方案中相应方块的情况：

'_'（下划线）表示该方块没有安排志愿者；

'o'（小写英文字母o）表示该方块安排了志愿者；

'x'（小写英文字母x）表示该方块是一个景点；

注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不一致（任何一行中，多余的空格都不允许出现），都可能导致该测试点不得分。

hint:
所有的 10 组数据中 N, M ，以及景点数 K 的范围规定如下：

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

输入文件中的所有整数均不小于 0 且不超过 2^16。


title: [SCOI2003] 严格N元树

description:
如果一棵树的所有非叶节点都恰好有 $n$ 个儿子，那么我们称它为严格 $n$ 元树。如果该树中最底层的节点深度为 $d$（根的深度为 $0$），那么我们称它为一棵深度为 $d$ 的严格 $n$ 元树。例如，深度为２的严格２元树有三个，如下图：

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

给出 $n,d$，编程数出深度为 $d$ 的 $n$ 元树数目。

inputFormat: 仅包含两个整数 $n,d(0<n \le 32,0 \le d \le 16)$。输入数据保证你不需要考虑某一层多于 $1024$ 个节点的树（即 $nd \le 1024$）。提示：答案保证不超过 $200$ 位十进制数。

outputFormat: 仅包含一个数，即深度为 $d$ 的 $n$ 元树的数目。


title: [AHOI2007] 密码箱

description:
在一次偶然的情况下，小可可得到了一个密码箱，听说里面藏着一份古代流传下来的藏宝图，只要能破解密码就能打开箱子，而箱子背面刻着的古代图标，就是对密码的提示。

经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数与密码的关系。假设这个数是 $n$，密码为 $x$，那么可以得到如下表述： 密码 $x$ 大于等于 $0$，且小于 $n$，而 $x$ 的平方除以 $n$，得到的余数为 $1$。 小可可知道满足上述条件的 $x$ 可能不止一个，所以一定要把所有满足条件的 $x$ 计算出来，密码肯定就在其中。计算的过程是很艰苦的，你能否编写一个程序来帮助小可可呢？

inputFormat: 一行，一个数字 $n$（$1 \leq n \leq 2 \times 10^9$）。

outputFormat: 你的程序需要找到所有满足前面所描述条件的 $x$，如果不存在这样的 $x$，你的程序只需输出一行 `None`，否则请按照从小到大的顺序输出这些 $x$，每行一个数。


title: [FJOI2014] 最短路径树问题

description:
给一个包含 $n$ 个点，$m$ 条边的无向连通图。从顶点 $1$ 出发，往其余所有点分别走一次并返回。

往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径（如路径 A 为 $1,32,11$，路径 B 为 $1,3,2,11$，路径 B 字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小）。到达该点后按原路返回，然后往其他点走，直到所有点都走过。

可以知道，经过的边会构成一棵最短路径树。请问，在这棵最短路径树上，最长的包含 $K$ 个点的简单路径长度为多长？包含 $K$ 个点的长度为该最长长度的不同路径有多少条？

这里的简单路径是指：对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同，点 A 到点 B 的路径和点 B 到点 A 视为同一条路径。

inputFormat:
第一行输入三个正整数 $n,m,K$，表示有 $n$ 个点 $m$ 条边，要求的路径需要经过 $K$ 个点。

接下来输入 $m$ 行，每行三个正整数 $A_i,B_i,C_i(1\leq Ai,Bi\leq n,1\leq C_i \leq 10000)$，表示 $A_i$ 和 $B_i$ 间有一条长度为 $C_i$ 的边。

数据保证输入的是连通的无向图。

outputFormat: 输出一行两个整数，以一个空格隔开，第一个整数表示包含 $K$ 个点的路径最长为多长，第二个整数表示包含 $K$ 个点的长度为该最长长度的不同路径有多少条。

hint:
对于所有数据 $n\leq 30000,m\leq 60000，2\leq K\leq n$。

数据保证最短路径树上至少存在一条长度为 $K$ 的路径。


title: [CTSC2008] 祭祀

description:
在遥远的东方，有一个神秘的民族，自称 Y 族。他们世代居住在水面上，奉龙王为神。每逢重大庆典，Y 族都会在水面上举办盛大的祭祀活动。我们可以把 Y 族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口，并且水在河道内按照一个固定的方向流动。显然，水系中不会有环流（下图描述一个环流的例子）。

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

由于人数众多的原因，Y 族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重，这些祭祀地点的选择必须非常慎重。准确地说，Y 族人认为，如果水流可以从一个祭祀点流到另外一个祭祀点，那么祭祀就会失去它神圣的意义。族长希望在保持祭祀神圣性的基础上，选择尽可能多的祭祀的地点。

inputFormat:
第一行包含两个用空格隔开的整数 $N$、$M$，分别表示岔口和河道的数目，岔口从 $1$ 到 $N$ 编号。

接下来 $M$ 行，每行包含两个用空格隔开的整数 $u$、$v$，描述一条连接岔口 $u$ 和岔口 $v$ 的河道，水流方向为自 $u$ 向 $v$。

outputFormat:
第一行包含一个整数 $K$，表示最多能选取的祭祀点的个数。

接下来一行输出一种可行的选取方案。对于每个岔口依次输出一个整数，如果在该岔口设置了祭祀点，那么输出一个 `1`，否则输出一个 `0`。应确保你输出的 `1` 的个数最多，且中间没有空格。

接下来一行输出，在选择最多祭祀点的前提下，每个岔口是否能够设置祭祀点。对于每个岔口依次输出一个整数，如果在该岔口能够设置祭祀点，那么输出一个 `1`，否则输出一个 `0`。

注意：多余的空格和换行可能会导致你的答案被判断为错误答案。

hint:
$N \le 100, M \le 1000$

在样例给出的水系中，不存在一种方法能够选择三个或者三个以上的祭祀点。包含两个祭祀点的测试点的方案有两种：

选择岔口 $1$ 与岔口 $3$（如样例输出第二行），选择岔口 $1$ 与岔口 $4$。

水流可以从任意岔口流至岔口 $2$。如果在岔口 $2$ 建立祭祀点，那么任意其他岔口都不能建立祭祀点但是在最优的一种祭祀点的选取方案中我们可以建立两个祭祀点，所以岔口 $2$ 不能建立祭祀点。对于其他岔口至少存在一个最优方案选择该岔口为祭祀点，所以输出为 `1011`。

感谢@ACdreamer 提供SPJ


title: [AHOI2006] 上学路线

description:
可可和卡卡家住 HF 市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。

可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！”

HF 市一共设有 $N$ 个公交车站，不妨将它们编号为 $1\sim N$ 的自然数，并认为可可和卡卡家住在 $1$ 号汽车站附近，而他们学校在 $N$ 号汽车站。市内有 $M$ 条直达汽车路线，执行第 $i$ 条路线的公交车往返于站点 $p_i$ 和 $q_i$ 之间，从起点到终点需要花费的时间为 $t_i$（$1\leq i\leq M$，$1\leq p_i,q_i\leq N$）。

两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线 $i$ 事实上都有一个代价 $c_i$：删去路线的 $c_i$ 越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线 $c_i$ 之和最小。

编写一个程序：
-  从输入文件中读取 HF 市公交路线的信息；
-  计算出实际上可可和卡卡上学需要花费的最少时间；
-  帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的 $c_i$ 和最小；
- 向输出文件输出答案。

inputFormat:
输入文件中第一行有两个正整数 $N$ 和 $M$，分别表示 HF 市公交车站和公交汽车路线的个数。

以下 $M$ 行，每行（第 $i$ 行，总第 $(i+1)$ 行）用四个正整数描述第 $i$ 条路线：$p_i,q_i,t_i,c_i$，具体含义见上文描述。

outputFormat:
第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。

第二行输出一个整数 $C$，表示 $c_i$ 之和。

hint:
$2\leq N\leq 500$，$1\leq M\leq 124750$，$1\leq t_i,c_i\leq 10^4$。

HF 市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。


title: [CQOI2013] 新Nim游戏

description:
传统的 Nim 游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。

本题的游戏稍微有些不同：在第一个回合中，双方可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。从第二个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。

如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。

inputFormat:
第一行为整数 $k$，即火柴堆数。

第二行包含 $k$ 个整数 $a_i$，即各堆的火柴个数。

outputFormat: 输出第一回合拿的火柴数目的最小值。如果不能保证取胜，输出 $-1$。

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

对于全部的测试点，保证 $1 \leq k \leq 100$，$1 \leq a_i \leq 10^9$。


title: [HAOI2008] 排名系统

description: 排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。

inputFormat:
第一行是一个整数n（10<=n<=250000）表示请求总数目。接下来n行,每行包含了一个请求。请求的具体格式如下：

+Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多8位的正整数。

?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。如果两个玩家的得分相同，则先得到该得分的玩家排在前面。

?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。

outputFormat:
对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。

对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。

samples:
2
CATHY TOM ADAM BOB
CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM
4


title: [AHOI2006] 基因匹配

description:
卡卡昨天晚上做梦梦见他和可可来到了另外一个星球，这个星球上生物的DNA序列由无数种碱基排列而成（地球上只有4种），而更奇怪的是，组成DNA序列的每一种碱基在该序列中正好出现5次！这样如果一个DNA序列有N种不同的碱基构成，那么它的长度一定是5N。

卡卡醒来后向可可叙述了这个奇怪的梦，而可可这些日子正在研究生物信息学中的基因匹配问题，于是他决定为这个奇怪星球上的生物写一个简单的DNA匹配程序。

为了描述基因匹配的原理，我们需要先定义子序列的概念：若从一个DNA序列（字符串）s中任意抽取一些碱基（字符），将它们仍按在s中的顺序排列成一个新串u，则称u是s的一个子序列。对于两个DNA序列s1和s2，如果存在一个序列u同时成为s1和s2的子序列，则称u是s1和s2的公共子序列。

卡卡已知两个DNA序列s1和s2，求s1和s2的最大匹配就是指s1和s2最长公共子序列的长度。

[任务]
编写一个程序：
- 从输入文件中读入两个等长的DNA序列；
- 计算它们的最大匹配；
- 向输出文件打印你得到的结果。

inputFormat:
输入文件中第一行有一个整数N，表示这个星球上某种生物使用了N种不同的碱基，以后将它们编号为1…N的整数。

以下还有两行，每行描述一个DNA序列：包含5N个1…N的整数，且每一个整数在对应的序列中正好出现5次。

outputFormat: 输出文件中只有一个整数，即两个DNA序列的最大匹配数目。


title: 完全平方数

description:
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。

这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。

然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？

inputFormat:
包含多组测试数据。文件第一行有一个整数 $T$，表示测试数据的组数。
第$2$ 至第$T+1$ 行每行有一个整数$K_i$，描述一组数据，含义如题目中所描述。

outputFormat: 含T 行，分别对每组数据作出回答。第 $i$ 行输出相应的第$K_i$ 个不是完全平方数的正整数倍的数。


title: [JLOI2011] 不重复数字

description: 给定 $n$ 个数，要求把其中重复的去掉，只保留第一次出现的数。

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

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个数，表示给定的数。

outputFormat: 对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。


title: [JSOI2010] 连通数

background:
本题数据过水，可前往 https://www.luogu.com.cn/problem/U143178 提交

$\text{upd 2022.8.4}$：已作为 Hack 数据合并进来。

description:
度量一个有向图连通情况的一个指标是连通数，指图中可达顶点对个的个数。

如图

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

顶点 $1$ 可达 $1, 2, 3, 4, 5$

顶点 $2$ 可达 $2, 3, 4, 5$

顶点 $3$ 可达 $3, 4, 5$

顶点 $4, 5$ 都只能到达自身。

所以这张图的连通数为 $14$。

给定一张图，请你求出它的连通数

inputFormat:
输入数据第一行是图顶点的数量，一个正整数 $N$。
接下来 $N$ 行，每行 $N$ 个字符。第 $i$ 行第 $j$ 列的 `1` 表示顶点 $i$ 到 $j$ 有边，`0` 则表示无边。

outputFormat: 输出一行一个整数，表示该图的连通数。


title: 绝世好题

description: 给定一个长度为 $n$ 的数列 $a_i$，求 $a_i$ 的子序列 $b_i$ 的最长长度 $k$，满足 $b_i \& b_{i-1} \ne 0 $，其中 $2\leq i\leq k$， $\&$ 表示位运算取与。

inputFormat:
输入文件共 2 行。
第一行包括一个整数 $n$。
第二行包括 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

outputFormat:
输出文件共一行。
包括一个整数，表示子序列 $b_i$ 的最长长度。


title: [CTSC2011] 幸福路径

description:
有向图 $G$ 有 $n$ 个顶点 $1, 2, \cdots, n$，点 $i$ 的权值为 $w(i)$。

现在有一只蚂蚁，从给定的起点 $v_0$ 出发，沿着图 $G$ 的边爬行。开始时，它的体力为 $1$。每爬过一条边，它的体力都会下降为原来的 $\rho$ 倍，其中 $\rho$ 是一个给定的小于 $1$ 的正常数。而蚂蚁爬到某个顶点时的幸福度，是它当时的体力与该点权值的乘积。

我们把蚂蚁在爬行路径上幸福度的总和记为 $H$。很显然，对于不同的爬行路径，$H$ 的值也可能不同。小 Z 对 $H$ 值的最大可能值很感兴趣，你能帮助他计算吗？注意，蚂蚁爬行的路径长度可能是无穷的。

inputFormat:
每一行中两个数之间用一个空格隔开。

输入文件第一行包含两个正整数 $n,m$，分别表示 $G$ 中顶点的个数和边的条数。

第二行包含 $n$ 个非负实数，依次表示 $n$ 个顶点权值  $w(1), w(2), \cdots, w(n)$。

第三行包含一个正整数 $v_0$，表示给定的起点。

第四行包含一个实数 $\rho$，表示给定的小于 $1$ 的正常数。

接下来 $m$ 行，每行两个正整数 $x, y$，表示 $(x, y)$ 是 $G$ 的一条有向边。可能有自环，但不会有重边。

outputFormat: 仅包含一个实数，即 $H$ 值的最大可能值，四舍五入到小数点后一位。


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

description: 给定一个序列，初始为空。现在我们将 $1$ 到 $N$ 的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

inputFormat:
第一行一个整数 $N$，表示我们要将 $1$ 到 $N$ 插入序列中。

接下是 $N$ 个数字，第 $k$ 个数字 $X_k$，表示我们将 $k$ 插入到位置 $X_k(0\le X_k\le k-1,1\le k\le N)$

outputFormat: $N$ 行，第 $i$ 行表示 $i$ 插入 $X_i$ 位置后序列的最长上升子序列的长度是多少。


title: 士兵占领

description: 有一个 $M \times N$ 的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第 $i$ 行至少放置了 $L_i$ 个士兵，第 $j$ 列至少放置了 $C_j$ 个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

inputFormat:
第一行两个数 $M, N, K$ 分别表示棋盘的行数，列数以及障碍的个数。
第二行有 $M$ 个数表示 $L_i$。
第三行有 $N$ 个数表示 $C_i$。
接下来有 $K$ 行，每行两个数 $X, Y$ 表示 $(X, Y)$ 这个格子是障碍。

outputFormat: 输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)

hint: 对于 $100 \%$ 的数据，$1 \le M, N \le 100$，$0 \le K \le M \cdot N$。


title: [COI2009] OTOCI

background: 注：本题原题通过**交互**的形式强制在线。但是在本题您不需要考虑交互的问题。

description:
不久之前，Mirko 建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了 $n$ 座冰岛，并且提供观光服务。

当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko 的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。

Mirko 希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在 $[0, 1000]$ 之间。你的程序需要处理以下三种命令：

- `bridge u v`：询问结点 $u$ 与结点 $v$ 是否连通。如果是则输出 `no`；否则输出 `yes`，并且在结点 $u$ 和结点 $v$ 之间连一条无向边。
- `penguins u x`：将结点 $u$ 对应的权值 $w_u$ 修改为 $x$。
- `excursion u v`：如果结点 $u$ 和结点 $v$ 不连通，则输出 `impossible`。否则输出结点 $u$ 到结点 $v$ 的路径上的点对应的权值的和。

共有 $q$ 个操作。

inputFormat:
第一行包含一个整数 $n$，表示节点的数目。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个节点初始时的权值 $w_i$。

第三行包含一个整数 $q$，表示操作的数目。

以下 $q$ 行，每行包含一个操作，操作的类别见题目描述。

outputFormat: 输出所有 `bridge` 操作和 `excursion` 操作对应的输出，每个一行表示答案。

samples:
5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

samples:
6
1 2 3 4 5 6
10
bridge 1 2
bridge 2 3
bridge 4 5
excursion 1 3
excursion 1 5
bridge 3 4
excursion 1 5
penguins 3 10
excursion 1 3
bridge 1 5

hint:
【数据范围】
对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^4$，$1 \le q \le 3\times 10^5$, $0 \le w_i \le 1000$。


title: [JSOI2009] 球队收益 / 球队预算

description:
在一个篮球联赛里，有$n$支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是$C_i\times x^2+D_i \times y^2,D_i \le C_i$。(赢得多，给球员的奖金就多嘛)
其中$x,y$分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半，每只球队分别取得了$a_i$场胜利和$b_i$场失利。而接下来还有$m$场比赛要进行。问联盟球队的最小总支出是多少。

inputFormat:
第一行$n$，$m$

接下来$n$行每行$4$个整数$a_i,b_i,C_i,D_i$

再接下来$m$行每行两个整数$s$，$t$表示第$s$支队伍和第$t$支队伍之间将有一场比赛，注意两只队间可能有多场比赛。

outputFormat: 一个整数代表总支出的最小值。


title: [TJOI2013] 攻击装置

description:
给定一个 01 矩阵，其中你可以在 0 的位置放置攻击装置。每一个攻击装置 $(x,y)$ 都可以按照“日”字攻击其周围的 $8$ 个位置 $(x-1,y-2)$，$(x-2,y-1)$，$(x+1,y-2)$，$(x+2,y-1)$，$(x-1,y+2)$，$(x-2,y+1)$，$(x+1,y+2)$，$(x+2,y+1)$。

求在装置互不攻击的情况下，最多可以放置多少个装置。

inputFormat:
第一行一个整数 $N$，表示矩阵大小为 $N \times N$。

接下来 $N$ 行每一行一个长度 $N$ 的 01 串，表示矩阵。

outputFormat: 一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。

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

对于 $100\%$ 的数据，保证 $N \le 200$。


title: 绿豆蛙的归宿

background: 随着新版百度空间的上线，Blog 宠物绿豆蛙完成了它的使命，去寻找它新的归宿。

description:
给出张 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$，终点为 $n$，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 $k$ 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 $\frac{1}{k}$ 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

inputFormat:
输入的第一行是两个整数，分别代表图的点数 $n$ 和边数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行有三个整数 $u, v, w$，代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。

outputFormat: 输出一行一个实数代表答案，四舍五入保留两位小数。

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

- 对于 $20\%$ 的数据，保证 $n \leq 10^2$。
- 对于 $40\%$ 的数据，保证 $n \leq 10^3$。
- 对于 $60\%$ 的数据，保证 $n \leq 10^4$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times n$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^9$，给出的图无重边和自环。


title: 花神的数论题

background: 众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。

description: 话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的：设  $\text{sum}(i)$  表示  $i$  的二进制表示中  $1$  的个数。给出一个正整数  $N$  ，花神要问你  $\prod_{i=1}^{N}\text{sum}(i)$ ，也就是  $\text{sum}(1)\sim\text{sum}(N)$  的乘积。

inputFormat: 一个正整数 $N$。

outputFormat: 一个数，答案模 $10000007$ 的值。


title: 带插入区间K小值

background:
# 本题时限已经修改为 2s

# 请使用常数较小的写法或者比较好的科技去过本题

description:
从前有$n$只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力$a_i$。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间$k$小值。他每次向它的随从伏特提出这样的问题: 从左往右第$x$个到第$y$个跳蚤中，$a_i$第$k$小的值是多少。

这可难不倒伏特，他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。

这时伏特发现有些跳蚤跳久了弹跳力会有变化，有的会增大，有的会减少。

这可难不倒伏特，他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。（orz 主席树）

这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上，他感到非常生气，因为……他不会做了。

请你帮一帮伏特吧。

**快捷版题意：带插入、修改的区间k小值在线查询**。

inputFormat:
第一行一个正整数$n$，表示原来有$n$只跳蚤排成一行做早操。
第二行有$n$个用空格隔开的非负整数，从左至右代表每只跳蚤的弹跳力。
第三行一个正整数$q$，表示下面有多少个操作。
下面一共$q$行，一共三种操作对原序列的操作：（假设此时一共$m$只跳蚤）
1. `Q x y k`: 询问从左至右第$x$只跳蚤到从左至右第$y$只跳蚤中，弹跳力第$k$小的跳蚤的弹跳力是多少。($1 \le x \le y \le m, 1 \le k \le y - x + 1$)
2. `M x val`: 将从左至右第x只跳蚤的弹跳力改为$val$。($1 \le x \le m$)
3. `I x val`: 在从左至右第$x$只跳蚤的前面插入一只弹跳力为$val$的跳蚤。即插入后从左至右第$x$只跳蚤是我刚插入的跳蚤。($1 \le x \le m + 1$)

为了体现在线操作，设$lastAns$为上一次查询的时候程序输出的结果，如果之前没有查询过，则$lastAns = 0$。

则输入的时候实际是：

- `Q _x _y _k` ——> 表示 `Q _x^lastAns _y^lastAns _k^lastAns`
- `M _x _val`  ——> 表示 `M _x^lastAns _val^lastAns`
- `I _x _val`  ——> 表示 `I _x^lastAns _val^lastAns`

简单来说就是操作中输入的整数都要异或上一次询问的结果进行解码。

(祝Pascal的同学早日转C++，就不提供pascal版的描述了。)

outputFormat: 对于每个询问输出回答，每行一个回答。


title: [BalticOI 2004] Sequence 数字序列

description: 给定一个整数序列 $a_1, a_2, \cdots , a_n$，求出一个递增序列 $b_1 < b_2 < ··· < b_n$，使得序列 $a_i$ 和 $b_i$ 的各项之差的绝对值之和 $|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|$ 最小。

inputFormat: 第一行为数字 $n (1≤n≤10^6)$，接下来一行共有 $n$ 个数字，表示序列 $a_i (0≤a_i≤2^{31}-1)$。

outputFormat:
第一行输出最小的绝对值之和。

第二行输出序列 $b_i$，若有多种方案，只需输出其中一种。

hint:
【数据范围】

- $40\%$ 的数据 $n≤5000$；
- $60\%$ 的数据 $n≤300000$；
- $100\%$ 的数据 $n≤10^6 , 0≤a_i≤2^{31}-1$；

题目来源：BalticOI 2004 Day 1, Sequence。

感谢 @TimeTraveller 提供 SPJ。


title: [JSOI2016] 独特的树叶

description:
JYY有两棵树 $A$ 和 $B$ ：树 $A$ 有 $N$ 个点，编号为 $1$ 到 $N$ ；树 $B$ 有$N+1$ 个节点，编号为 $1$ 到$N+1$

JYY 知道树 $B$ 恰好是由树 $A$ 加上一个叶节点，然后将节点的编号打乱后得到的。他想知道，这个多余的叶子到底是树 $B$ 中的哪一个叶节点呢？

inputFormat: 输入一行包含一个正整数 $N$。 接下来 $N-1$ 行，描述树$ A$，每行包含两个整数表示树 $A$ 中的一条边； 接下来 $N$ 行，描述树 $B$，每行包含两个整数表示树 $B$ 中的一条边。

outputFormat: 输出一行一个整数，表示树 $B$ 中相比树 $A$ 多余的那个叶子的编号。如果有多个符合要求的叶子，输出 $B$ 中编号最小的那一个的编号。

hint: 对于所有数据，$1 \leq n \leq 10 ^ 5$


title: [JSOI2016] 扭动的回文串

description:
JYY 有两个长度均为 $N$ 的字符串 $A$ 和 $B$。

一个扭动字符串 $S(i,j,k)$ 由 $A$ 中的第 $i$ 个字符到第 $j$ 个字符组成的子串与 $B$ 中的第 $j$ 个字符到第 $k$ 个字符组成的子串拼接而成。

比如，若 $A= \mathtt{XYZ}$，$B= \mathtt{UVW}$，则扭动字符串 $S(1,2,3)=\mathtt{XYVW}$。

JYY 定义一个扭动的回文串为如下情况中的一个：

1. $A$ 中的一个回文串；
2. $B$ 中的一个回文串；
3. 或者某一个回文的扭动字符串 $S(i,j,k)$。

现在 JYY 希望找出最长的扭动回文串。

inputFormat:
第一行包含一个正整数 $N$。
第二行包含一个长度为 $N$ 的由大写字母组成的字符串 $A$。
第三行包含一个长度为 $N$ 的由大写字母组成的字符串 $B$。

outputFormat: 输出的第一行一个整数，表示最长的扭动回文串。

hint:
**样例解释**
最佳方案中的扭动回文串如下所示（不在回文串中的字符用 . 表示）：

```pain
.BC..
..ECB
```

对于所有的数据，$1 \leq n \leq 10 ^ 5$


title: 付公主的背包

background: 付公主有一个可爱的背包qwq

description:
这个背包最多可以装 $10^5$ 大小的东西

付公主有 $n$ 种商品，她要准备出摊了

每种商品体积为 $v_i$，都有无限件

给定 $m$，对于 $s\in [1,m]$，请你回答用这些商品恰好装 $s$ 体积的方案数

inputFormat:
第一行两个正整数 $n,m$。
第二行 $n$ 个正整数，表示每种商品的体积。

outputFormat: 输出 $m$ 行，第 $i$ 行代表 $s=i$ 时方案数，对 $998244353$ 取模。

hint:
【数据范围】
对于 $30\%$ 的数据，$1\le n,m \le 3000$；
对于 $60\%$ 的数据，纯随机生成；
对于 $100\%$ 的数据， $1\le n,m \le 10^5$，$1\le v_i \le m$。


title: [COCI2006-2007#1] Modulo

description: Given two integers A and B, A modulo B is the remainder when dividing A by B. For example, the numbers 7, 14, 27 and 38 become 1, 2, 0 and 2, modulo 3. Write a program that accepts 10 numbers as input and outputs the number of distinct numbers in the input, if the numbers are considered modulo 42.

inputFormat: The input will contain 10 non-negative integers, each smaller than 1000, one per line.

outputFormat: Output the number of distinct values when considered modulo 42 on a single line.

translation:
给出 $10$ 个整数，问这些整数除以 $42$ 后得到的余数有多少种。

- 第一个样例的十个结果是 $1,2,3,4,5,6,7,8,9,10$，有 $10$ 个不同的结果；
- 第二个样例结果都是 $0$，只有一个不同的结果；
- 第三个样例余数是 $39,40,41,0,1,2,40,41,0,1$，有 $0,1,2,39,40,41$ 这六个不同的结果。

hint:
In the first example, the numbers modulo 42 are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10.
In the second example all numbers modulo 42 are 0.
In the third example, the numbers modulo 42 are 39, 40, 41, 0, 1, 2, 40, 41, 0 and 1. There are 6 distinct numbers.


title: [COCI2006-2007#1] Herman

description:
The 19th century German mathematician Hermann Minkowski investigated a non-Euclidian geometry, called the taxicab geometry. In taxicab geometry the distance between two points T1(x1, y1) and T2(x2, y2) is defined as:
D(T1,T2) = |x1 - x2| + |y1 - y2|
All other definitions are the same as in Euclidian geometry, including that of a circle:
A circle is the set of all points in a plane at a fixed distance (the radius) from a fixed point (the centre of the circle).
We are interested in the difference of the areas of two circles with radius R, one of which is in normal (Euclidian) geometry, and the other in taxicab geometry. The burden of solving this difficult problem has fallen onto you.

inputFormat: The first and only line of input will contain the radius R, an integer smaller than or equal to 10000.

outputFormat:
On the first line you should output the area of a circle with radius R in normal (Euclidian) geometry.
On the second line you should output the area of a circle with radius R in taxicab geometry.
Note: Outputs within ±0.0001 of the official solution will be accepted.

translation:
19世纪的德国数学家赫尔曼·闵可夫斯基(Hermann Minkowski)研究了一种名为出租车几何学的非欧几何。
在出租车几何里$T_1(x_1,y_1)$ $T_2(x_2,y_2)$两点之间的距离被定义为$dis(T_1,T_2)=|x_1-x_2|+|y_1-y_2|$(曼哈顿距离)。
其他定义均与欧几里得几何相同。
例如圆的定义：在同一平面内，到定点(圆心)的距离等于定长(半径)的点的集合。

我们对欧几里得几何与出租车几何两种定义下半径为$R$的圆的面积很感兴趣。解决这个问题的重担就落在你身上了。

## 输入输出格式

### 输入格式

仅有一行为圆的半径$R$。 $(R \leq 10000)$

### 输出格式

第一行输出欧几里得几何下半径为$R$的圆的面积，第二行输出出租车几何下半径为$R$的圆的面积。

注意：你的输出与标准答案绝对误差不超过$0.0001$将会被认为正确


title: [COCI2006-2007#1] Okviri

description:
“Peter Pan frames” are a way of decorating text in which every character is framed by a diamond shaped frame, with frames of neigbhouring characters interleaving. A Peter Pan frame for one letter looks like this ('X' is the letter we are framing):
```
..#..
.#.#.
#.X.#
.#.#.
..#..
```
However, such a framing would be somewhat dull so we'll frame every third letter using a “Wendyframe”. A Wendy frame looks like this:

```
..*..
.*.*.
*.X.*
.*.*.
..*..
```
When a Wendy frame interleaves with a Peter Pan frame, the Wendy frame (being much nicer) is put on top. For an example of the interleaving check the sample cases.

inputFormat: The first and only line of input will contain at most 15 capital letters of the English alphabet.

outputFormat: Output the word written using Peter Pan and Wendy frames on 5 lines.

translation:
“彼得·潘框架”是一种装饰文字，每一个字母都是由一个菱形框架。一个彼得·潘框架看起来像这样 （x是字母，#是框架）：
```
..#..
.#.#.
#.X.#
.#.#.
..#..
```
然而，只是一个框架会有些沉闷，所以我们每遇到三个字母会把第三个字母用温迪框架把它框起来。温迪框架看起来像这样：
```
..*..
.*.*.
*.X.*
.*.*.
..*..
```
当温迪和彼得·潘的框架重叠时，温迪框架覆盖在上面。 （见样例3和4）

输入格式： 一行包含至多15个英文字母的大写字母。

输出格式： 输出使用彼得·潘和温迪框架写成的5行文字。


title: [COCI2006-2007#1] Slikar

description:
The evil emperor Cactus has in his possession the Magic Keg and has flooded the Enchanted Forest! The Painter and the three little hedgehogs now have to return to the Beaver's den where they will be safe from the water as quickly as possible!
The map of the Enchanted Forest consists of R rows and C columns. Empty fields are represented by '.' characters, flooded fields by '*' and rocks by 'X'. Additionally, the Beaver's den is represented by 'D' and the Painter and the three little hedgehogs are shown as 'S'.
Every minute the Painter and the three little hedgehogs can move to 4 neighbouring fields (up, down, left or right). Every minute the flood expands as well so that all empty fields that have at least one common side with a flooded field become flooded as well. Neither water nor the Painter and the three little hedgehogs can pass through rocks. Naturally, the Painter and the three little hedgehogs cannot pass through flooded fields, and water cannot flood the Beaver's den.
Write a program that will, given a map of the Enchanted Forest, output the shortest time needed for the Painter and the three little hedgehogs to safely reach the Beaver's den.
Note: The Painter and the three little hedgehogs cannot move into a field that is about to be flooded (in the same minute).

inputFormat:
The first line of input will contain two integers, R and C, smaller than or equal to 50.
The following R lines will each contain C characters ('.', '*', 'X', 'D' or 'S'). The map will contain exactly one 'D' character and exactly one 'S' character.

outputFormat: Output the shortest possible time needed for the Painter and the three little hedgehogs to safely reach the Beaver's den. If this is impossible output the word “KAKTUS” on a line by itself.

translation:
给你一个$R*C$ 的矩阵，这个矩阵由 $*$  , $.$ (点) , $D$  , $S$  , $X$ 组成，会有洪水从$*$ 处涌出，每单位时间都会淹没和其四联通的平地，$.$ (点)表示平地，$X$ 是障碍，不可通行，也不会没淹没，$S$ 是出发点，三只刺猬(?)从这里出发前往庇护所，它们只能在没有被洪水淹没的平地上移动，并且每单位时间只能移动到周围一个四联通的格子，$D$ 表示庇护所，庇护所不会被洪水淹没。

输入第一行两个整数$R,C$ （$R,C\leq 50$ ），接下来使这个矩阵。

输出到达庇护所的最短时间，或者输出“KAKTUS”，表示根本不可能到。

感谢@Khassar 提供的翻译

hint: Clarification of the second sample test: The best they can do is to go along the lower border and then the left border, and get flooded one minute before reaching the den.


title: [COCI2006-2007#1] Bond

description:
Everyone knows of the secret agent double-oh-seven, the popular Bond (James Bond). A lesser known fact is that he actually did not perform most of his missions by himself; they were instead done by his cousins, Jimmy Bonds. Bond (James Bond) has grown weary of having to distribute assign missions to Jimmy Bonds every time he gets new missions so he has asked you to help him out.
Every month Bond (James Bond) receives a list of missions. Using his detailed intelligence from past missions, for every mission and for every Jimmy Bond he calculates the probability of that particular mission being successfully completed by that particular Jimmy Bond. Your program should process that data and find the arrangement that will result in the greatest probability that all missions are completed successfully.
Note: the probability of all missions being completed successfully is equal to the product of the probabilities of the single missions being completed successfully.

inputFormat:
The first line will contain an integer N, the number of Jimmy Bonds and missions (1 ≤ N ≤ 20).
The following N lines will contain N integers between 0 and 100, inclusive. The j-th integer on the ith line is the probability that Jimmy Bond i would successfully complete mission j, given as a percentage.

outputFormat: Output the maximum probability of Jimmy Bonds successfully completing all the missions, as a percentage.

translation:
有 $n$ 个人去执行 $n$ 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。

输入第一行，一个整数 $n$（$1\leq n\leq 20$），表示人数兼任务数。接下来 $n$ 行每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示第 $i$ 个人去执行第 $j$ 个任务的成功率（这是一个百分数，在 $0$ 到 $100$ 间）。

输出最大的总成功率（这应也是一个百分数）

hint:
Clarification of the third example: If Jimmy bond 1 is assigned the 3rd mission, Jimmy Bond 2 the 1st mission and Jimmy Bond 3 the 2nd mission the probability is: 1.0 * 0.13 * 0.7 = 0.091 = 9.1%. All other arrangements give a smaller probability of success.
Note: Outputs within ±0.000001 of the official solution will be accepted.


title: [COCI2006-2007#1] Debug

description:
While debugging a program Mirko noticed that a bug in the program may be linked with the existence of so called square killers in the program memory. The program memory is a matrix composed of R rows and C columns consisting only of zeroes and ones. A square killer is a square submatrix in memory, consisting of more than one character, that, when rotated 180 degrees looks exactly the same. For example, the following matrix contains 3 square killers:

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

Mirko is wondering if there is a connection between the size of the largest square killer and the bug in the program. Help Mirko by writing a program that, given the layout of the memory, outputs the size of the largest square killer. The size of the square killer is the number of rows (or columns) that the killer consists of. In the example above the killer sizes are 2, 2 and 3, respectively.

inputFormat:
The first will contain two integers, R and C, smaller than or equal to 300.
The next R lines will each contain C characters ('0' or '1') with no spaces.

outputFormat: Output the size of the largest killer on a single line, or output -1 if there are no square killers.

translation:
Mirko在写bug的时候，注意到这样一个问题：程序中的bug可能与内存中的”square killer”有关。程序的内存是一个r行c列的01矩阵。”square killer”是其中包含一个**以上**字符的一个正方形子矩阵，而且”square killer”旋转180°后与原来相同。例如，下面的矩阵中含有三个”square killer”:

Mirko想知道程序中最大的”square killer”与bug的联系。帮助他写一个程序，求出最大的”square killer”的大小。”square killer”的大小是指它含有的行数或列数。图中的”square killer”的大小分别是2、2、3。

Translated by @ACdreamer


title: [COI2007] Policija

description:
To help capture criminals on the run, the police are introducing a new computer system. The area covered by the police contains N cities and E bidirectional roads connecting them. The cities are labelled 1 to N.

为了帮助抓捕逃犯，警方引进了一套新的电脑系统。警察的辖区包含 $N$ 座城市和 $E$ 条双向道路，城市的编号是 $1\sim N$。

The police often want to catch criminals trying to get from one city to another. Inspectors, looking at a map, try to determine where to set up barricades and roadblocks. The new computer system should answer the following two types of queries:

警察常常要抓住那些逃往另一个城市的罪犯。侦查员看着地图，试着确定在哪里设置路障。新的计算机系统要回答以下两种问题：

1. Consider two cities A and B, and a road connecting cities G1 and G2. Can the criminals get
from city A to city B if that one road is blocked and the criminals can't use it?

考虑城市 $A$ 和 $B$，以及连接城市 $G_1$ 和 $G_2$ 的道路。罪犯能否在那条路不通的情况下从 $A$ 逃到 $B$？

2. Consider three cities A, B and C. Can the criminals get from city A to city B if the entire city C is cut off and the criminals can't enter that city?

考虑三个城市 $A, B, C$。罪犯能否在无法通过 $C$ 的情况下从 $A$ 逃到 $B$?

Write a program that implements the described system.

写一个程序实现上述系统。

inputFormat:
The first line contains two integers N and E (2 ≤ N ≤ 100 000, 1 ≤ E ≤ 500 000), the number of cities and roads.

第一行两个整数 $N, E$（$2\leq N\leq 10 ^ 5$，$1\leq E\leq 5\times 10 ^ 5$），表示城市数量和道路数量。

Each of the following E lines contains two distinct integers between 1 and N – the labels of two cities connected by a road. There will be at most one road between any pair of cities.

接下来 $E$ 行，每行两个不同的数字 $u, v$，表示编号为 $u, v$ 的城市之间有一条道路。一对城市之间最多只有一条道路。

The following line contains the integer Q (1 ≤ Q ≤ 300 000), the number of queries the system is being tested on.

接下来一行，一个整数 $Q$（$1\leq Q\leq 3\times 10 ^ 5$），表示询问数量。

Each of the following Q lines contains either four or five integers. The first of these integers is the type of the query – 1 or 2.

接下来 $Q$ 行，每行四或五个整数描述一组询问。第一个数表示询问的类型 —— $1$ 或 $2$。

If the query is of type 1, then the same line contains four more integers A, B, G1 and G2 as described earlier. A and B will be different. G1 and G2 will represent an existing road.

如果询问类型为 $1$，那么在同一行还有四个整数 $A, B, G_1, G_2$。$A, B$ 不同，且 $G_1, G_2$ 之间存在道路。

If the query is of type 2, then the same line contains three more integers A, B and C. A, B and C will be distinct integers.

如果询问类型为 $2$，那么在同一行还有三个整数 $A, B, C$。$A, B, C$ 两两不同。

The test data will be such that it is initially possible to get from each city to every other city.

保证图中每两个点相互连通。

outputFormat:
Output the answers to all Q queries, one per line. The answer to a query can be "yes" or "no".

对于每组询问，输出 `yes` 或 `no` 表示回答。

hint: Croatian Olympiad in Informatics 2007 Task 2


title: [COI2007] Sabor

description:
The president of the political party in power is holding a conference in the party headquarters.
Politicians, members of the party, live in a two-dimensional grid, one member in each cell (except in cells containing obstacles). The headquarters are located in cell (0, 0). This is also where the president of the party lives.

执政党的总书记正在人民大会堂举行会议。党员们都在一个二维平面的网格中，一个党员在一个格子中（除了含有障碍的格子）。会堂位于（0,0），是总书记的位置。

Politicians make steps in one of the four directions (up, down, left, right), moving to one of the four adjacent cells in one step. They can't enter cells with obstacles. The conference will be attended by all party members that can reach headquarters in S steps or less. Each member coming to the conference will take the shortest route to headquarters (or any such route, if there is more than one).

党员们选择上、下、左、右四个方向中的一个，移动到相邻的格子中去。他们不能进入有障碍的格子。会议将由所有能在$S$步以内到达会堂的党员参加。每个与会代表将走最短路到达总部（如果有多条最短路，走任意一条）。

The president has observed that politicians change their party affiliation with each step they take,becoming a member of the other party (there are only two parties on the political scene).
Write a program that determines how many politicians come to the conference as members of the party in power, and how many come as members of the opposing party.

总书记发现，代表们每走一步，就会改变他们的党派关系，成为另一个政党的成员（国家实行两党制）。编写一个程序来计算有多少代表是执政党，多少代表是反对党。

inputFormat:
The first line contains two integers B and S (0 ≤ B ≤ 10 000, 1 ≤ S ≤ 10 000 000), the number of obstacles and the largest number of steps from the task description.

Each of the following B lines contains two integers, the coordinates of one obstacle. The absolute value of both coordinates will be less than 1000.

No two obstacles will be in the same cell and there will be no obstacle in cell (0, 0).

outputFormat: Output two integers on a single line separated by a space, the number of politicians that come to the conference as members of the party in power and the opposing party, respectively.

hint:
Croatian Olympiad in Informatics 2007
Task 3


title: [SHOI2005] 树的双中心

inputFormat:
第一行为N，1<N<=50000,表示树的节点数目，树的节点从1到N编号。
接下来N-1行，每行两个整数U，V，表示U与V之间有一条边。
再接下N行，每行一个正整数，其中第i行的正整数表示编号为i的节点权值为W(I),树的深度<=100

hint: 选取的两个中心节点分别为2和3


title: [SHOI2014] 三叉神经树

description:
计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做 SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。

SHOI 组织由若干个 SHOI 细胞构成，SHOI 细胞之间形成严密的树形结构。每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞；并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有 $0$和 $1$ 两种。每个 SHOI 细胞根据三个输入端中 $0$和 $1$ 信号的多寡输出较多的那一种。

现在给出了一段 SHOI 组织的信息，以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。

inputFormat:
输入的第一行包含一个整数 $n$。表示 SHOI 组织的总细胞个数。SHOI 细胞由 $1\sim n$ 编号,编号为 $1$ 的是根细胞。

从第二行开始的 $n$ 行,每行三个整数 $x_1, x_2, x_3$，分别表示编号为 $1\sim n$ 的 SHOI 细胞的树突连接。$1 < x_i \leq n$ 表示连向编号为 $x_i$ 的细胞的轴突, $n < x_i \leq 3n+1$ 表示连向编号为 $x_i$ 的外界输入。输入数据保证给出的 SHOI 组织是合法的，且所有的 $x_i$ 两两不同。

接下来一行包含 $2n+1$ 个整数（$0$ 或者 $1$），表示初始时的外界输入。

第 $n+3$ 行有一个整数 $q$，表示总操作数。

之后 $q$ 行，每行一个整数 $x$，表示编号为 $x$ 的外界输入发生了变化。

outputFormat: 输出共 $q$ 行，每行一个整数，对应第 $i$ 次外界输入变化后的根细胞的输出。


title: [SHOI2016] 黑暗前的幻想乡

background:
四年一度的幻想乡大选开始了，最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡，扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪（人类）博丽灵梦和八云紫等人整日高谈所有妖怪平等，幻想乡多元化等等，对于幻想乡目前面临的种种大问题却给不出合理的解决方案。

风见幽香是幻想乡里少有的意识到了问题严重性的大妖怪。她这次勇敢地站了出来参加幻想乡大选，提出包括在幻想乡边境建墙（并让人类出钱），大力开展基础设施建设挽回失业率等一系列方案，成为了大选年出人意料的黑马并顺利地当上了幻想乡的大统领。

description:
幽香上台以后，第一项措施就是要修建幻想乡的公路。幻想乡一共有 $n$ 个城市，之前原来没有任何路。幽香向选民承诺要减税，所以她打算只修 $n-1$ 条公路将这些城市连接起来。但是幻想乡有正好 $n-1$ 个建筑公司，每个建筑公司都想在修路的过程中获得一些好处。虽然这些建筑公司在选举前没有给幽香钱，幽香还是打算和他们搞好关系，因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。

每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算 $n - 1$ 条能够连接幻想乡所有城市的边，然后每条边都交给一个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修建一条边。

幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它们要么修的边的集合不同，要么边的分配方式不同。

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

第 $2$ 到第 $n$ 行，第 $(i + 1)$ 行表示 第 $i$ 个建筑公司可以修建的路的列表：以一个非负整数 $m_i$ 开头，表示其可以修建条路的条数；接下来有 $m_i$ 对整数 $u, v$，每对数表示一条边的两个端点。其中不会出现重复的边，也不会出现自环。

outputFormat: 输出一行一个整数，表示所有可能的方案数对 $10^9+7$ 取模的结果。

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

+ 对于 $20\%$ 的测试点，$n \le 5$。
+ 对于 $50\%$ 的测试点，$n \le 8$。
+ 对于 $60\%$ 的测试点，$n \le 10$。
+ 对于 $100\%$ 的测试点，$2 \leq n \le 17$，$0 \leq m_i \leq \frac{n(n - 1)}{2}$，$1 \leq u, v \leq n$。


title: [ZJOI2018] 线图

background: 九条可怜是一个热爱出题的女孩子。

description:
今天可怜想要出一道和图论相关的题。在一张无向图 $G$ 上，我们可以对它进行一些非常有趣的变换，比如说对偶，又或者说取补。这样的操作往往可以赋予一些传统的问题新的活力。例如求补图的连通性、补图的最短路等等，都是非常有趣的问题。

最近可怜知道了一种新的变换：求原图的线图 (line graph)。对于无向图 $G = ⟨V, E⟩$，它的 线图 $L(G)$ 也是一个无向图：
- 它的点集大小为 $|E|$，每个点唯一对应着原图的一条边。
- 两个点之间有边当且仅当这两个点对应的边在原图上有公共点（注意不会有自环）。 下图是一个简单的例子，左图是原图，右图是它对应的线图。其中点 $1$ 对应原图的边 $(1, 2)$，点 $2$ 对应 $(1, 4)$，点 $3$ 对应 $(1, 3)$，点 $4$ 对应 $(3, 4)$。

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

经过一些初步的摸索，可怜发现线图的性质要比补图复杂很多，其中突出的一点就是补图 的补图会变回原图，而 $L(L(G))$ 在绝大部分情况下不等于 $G$，甚至在大多数情况下它的点数和边数会以很快的速度增长。

因此，可怜想要从最简单的入手，即计算 $L^k(G)$ 的点数（$L^k(G)$ 表示对 $G$ 求 $k$ 次线图）。 然而遗憾的是，即使是这个问题，对可怜来说还是太困难了，因此她进行了一定的弱化。她给出了一棵 $n$ 个节点的树 $T$，现在她想让你计算一下 $L^k(T)$ 的点数。

inputFormat:
第一行输入两个整数 $n, k$，表示树的点数以及连续求线图的次数。

接下来 $n − 1$ 行每行两个整数 $u, v$ 表示树上的一条边。

outputFormat: 输出一行一个整数，表示答案对 $998244353$ 取模后的值。

hint:
如下图所示，左图为原树，中图为 $L(G)$，右图为 $L^2(G)$。这儿并未画出 $L^3(G)$，但是由于 $L^2(G)$ 有 5 条边，因此 $L^3(G)$ 中有 5 个点。

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

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


title: [ZJOI2018] 历史

background: 九条可怜是一个热爱阅读的女孩子。

description:
这个世界有 n 个城市，这 n 个城市被恰好 $n-1$ 条双向道路联通，即任意两个城市都可以 互相到达。同时城市 1 坐落在世界的中心，占领了这个城市就称霸了这个世界。

在最开始，这 n 个城市都不在任何国家的控制之下，但是随着社会的发展，一些城市会崛 起形成国家并夺取世界的霸权。为了方便，我们标记第 i 个城市崛起产生的国家为第 i 个国家。 在第 i 个城市崛起的过程中，第 i 个国家会取得城市 i 到城市 1 路径上所有城市的控制权。

新的城市的崛起往往意味着战争与死亡，若第 i 个国家在崛起中，需要取得一个原本被国 家 $j(j ≠ i)$ 控制的城市的控制权，那么国家 i 就必须向国家 j 宣战并进行战争。

现在，可怜知道了，在历史上，第 i 个城市一共崛起了 $a_i$ 次。但是这些事件发生的相对顺 序已经无从考究了，唯一的信息是，在一个城市崛起称霸世界之前，新的城市是不会崛起的。

战争对人民来说是灾难性的。可怜定义一次崛起的灾难度为崛起的过程中会和多少不同的国家进行战争（和同一个国家进行多次战争只会被计入一次）。可怜想要知道，在所有可能的崛 起顺序中，灾难度之和最大是多少。

同时，在考古学家的努力下，越来越多的历史资料被发掘了出来，根据这些新的资料，可怜会对 $a_i$ 进行一些修正。具体来说，可怜会对 $a_i$ 进行一些操作，每次会将 $a_x$ 加上 w。她希望 在每次修改之后，都能计算得到最大的灾难度。

然而可怜对复杂的计算并不感兴趣，因此她想让你来帮她计算一下这些数值。
对题面的一些补充：

- 同一个城市多次崛起形成的国家是同一个国家，这意味着同一个城市连续崛起两次是不会 和任何国家开战的：因为这些城市原来就在它的控制之下。
- 在历史的演变过程中，第 i 个国家可能会有一段时间没有任何城市的控制权。但是这并不 意味着第 i 个国家灭亡了，在城市 i 崛起的时候，第 i 个国家仍然会取得 1 到 i 路径上的城市的控制权。

inputFormat:
第一行输入两个整数 n,m 表示城市个数和操作个数。

第二行输入 n 个整数表示 ai 的初始值。 接下来 n − 1 行，每行输入两个整数 $u_i, v_i(1\leq ui, vi \leq n)$ 描述了一条道路。

接下来 m 行每行输入两个整数 $x_i$, $w_i$ 表示将 $a_{x_i}$
加上 $w_i$。

outputFormat: 输出共 $m+1$ 行，第一行表示初始的 ai 的答案，接下来 m 行每行表示这次修正后的答案。

hint:
在修正开始之前，如果按照所在城市 4, 1, 5, 3, 2 的顺序崛起，那么依次会和 0, 1, 2, 1, 2 个 国家进行战争。

这时一共会产生 6 对敌对关系。可以证明这是所有崛起顺序中的最大值。

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


title: [ZJOI2018] 迷宫

background: 九条可怜是一个贪玩的女孩子。

description:
暑假快要到了，可怜打算在她家的私人海滩旁边建一座城堡，这样就可以在放暑假的时候 邀请她的朋友们来玩了。同时，可怜打算在城堡的地下修建一座迷宫，因为探险总是一件充满 乐趣的事情。

经过简单的设计，可怜打算修建一座这样的迷宫：
- 迷宫可以被抽象成 $n$ 个点，$nm$ 条边的有向图。$1$ 号点是唯一的入口也是唯一的出口。
- 每一个点恰好有 $m$ 条出边，且这些出边被依次标号为 $[0,m)$ 的正整数。
- 迷宫允许自环和重边。

同时，一座优秀的迷宫应该有一定的解谜因素。因此可怜希望每一条从 $1$ 号点出发并回到 $1$ 号点的回路都有着一定的规律。可怜发现，如果把一条从 $1$ 出发的路径经过的所有边的编号都记录下来，那么能得到一个（可能有前导 $0$）的 $m$ 进制数；同时对于每一个（可能有前导 $0$）的 $m$ 进制数，都能对应回一 条从 $1$ 出发的路径。

于是可怜选定了一个整数 $K$，她希望这个迷宫满足一条从 $1$ 出发的路径能回到 $1$ **当且仅当**这条路径对应的数是 $K$ 的倍数。

现在可怜已经选定了 $m$ 和 $K$，但是她发现并不是对所有的 $n$，都存在满足上述所有条件的迷宫设计方案。建造迷宫是一件费时费力的事情，于是可怜想要找到一个最小的满足条件的 $n$。

然而可怜对复杂的计算并不感兴趣，因此她想让你来帮她计算一下这个数值。

inputFormat:
第一行输入一个整数 $T$ 表示数据组数。

接下来 $T$ 行每行两个十进制正整数 $m,K$ 表示可怜选定的整数。

outputFormat: 对于每组数据，输出一行一个整数表示能够满足所有条件的最小的 $n$。如果不存在这样的 $n$，输出 `-1`。

hint:
第一组数据（左）和第二组数据（右）的一种设计方案如下图所示。其中紫色边表示 $0$ 号边，蓝色边表示 $1$ 号边。

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

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


title: [SHOI2016] 随机序列

description:
你的面前有 $n$ 个数排成一行，分别为 $a_1,a_2,...,a_n$ 。你打算在每相邻的两个 $a_i$  和 $a_{i+1}$ 间都插入一个加号、减号或者乘号。那么一共有$3^{n-1}$ 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个 $a_i$ 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

inputFormat:
第一行包含两个正整数 $n$ 和 $Q$，为数的个数和询问的个数。
第二行包含 $n$ 个非负整数，依次表示 $a_1,a_2,...,a_n$。
接下来 $Q$ 行，每行包含两个非负整数 $t$ 和 $v$，表示要将 $a_t$ 修改为 $v$，其中 $1≤t≤n$。

保证对于 $1≤j≤n$,$1≤i≤Q$，都有 $aj,vi≤10^4$

outputFormat: 输出 $Q$ 行。对于每个修改输出一行，包含一个整数，表示修改之后所有可能表达式的和，对 $10^9+7$ 取模。


title: [BJWC2010] 外星联络

description:
小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。

虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由 `0` 和 `1` 构成的串， 并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以他希望找到他接受到的 01 串中所有重复出现次数大于 $1$ 的子串。

但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

inputFormat:
输入文件的第一行是一个整数$N$ ，代表小 P 接收到的信号串的长度。
输入文件第二行包含一个长度为$N$ 的 01 串，代表小 P 接收到的信号串。

outputFormat: 输出文件的每一行包含一个出现次数大于$1$ 的子串所出现的次数。输出的顺序按对应的子串的字典序排列。

hint: 对于 100%的数据，满足 $0 \le N \le 3000$


title: [IOI1998] Polygon

description:
Polygon is a game for one player that starts on a polygon with $N$ vertices, like the one in Figure 1, where $N=4$. Each vertex is labelled with an integer and each edge is labelled with either the symbol `+` (addition) or the symbol `*` (product). The edges are numbered from $1$ to $N$.

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

On the first move, one of the edges is removed. Subsequent moves involve the following steps:
- pick an edge $E$ and the two vertices $V_1$ and $V_2$ that are linked by $E$; and
- replace them by a new vertex, labelled with the result of performing the operation indicated in $E$ on the labels of $V_1$ and $V_2$.

The game ends when there are no more edges, and its score is the label of the single vertex remaining.

Consider the polygon of Figure 1. The player started by removing edge 3. After that, the player picked edge 1, then edge 4, and, finally, edge 2. The score is 0.

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

Write a program that, given a polygon, computes the highest possible score and lists all the edges that, if removed on the first move, can lead to a game with that score.

inputFormat:
Your program is to read from standard input. The input describes a polygon with N vertices. It contains two lines. On the first line is the number N. The second line contains the labels of edges 1, ..., N, interleaved with the vertices' labels (first that of the vertex between edges 1 and 2, then that of the vertex between edges 2 and 3, and so on, until that of the vertex between edges N and 1), all separated by one space. An edge label is either the letter t (representing +) or the letter x (representing *).

3 <= N <= 50

For any sequence of moves, vertex labels are in the range [-32768,32767].

outputFormat: Your program is to write to standard output. On the first line your program must write the highest score one can get for the input polygon. On the second line it must write the list of all edges that, if removed on the first move, can lead to a game with that score. Edges must be written in increasing order, separated by one space.

translation:
# 题目可能有些许修改，但大意一致

多边形是一个玩家在一个有n个顶点的多边形上的游戏，如图所示，其中n＝4。每个顶点用整数标记，每个边用符号+（加）或符号*（乘积）标记。

![](https://cdn.luogu.org/upload/pic/16086.png)

第一步，删除其中一条边。随后每一步：

选择一条边连接的两个顶点V1和V2，用边上的运算符计算V1和V2得到的结果来替换这两个顶点。

游戏结束时，只有一个顶点，没有多余的边。

如图所示，玩家先移除编号为3的边。之后，玩家选择计算编号为1的边，然后计算编号为4的边，最后，计算编号为2的边。结果是0。

![](https://cdn.luogu.org/upload/pic/16088.png)

（翻译者友情提示：这里每条边的运算符旁边的数字为边的编号，不拿来计算）

编写一个程序，给定一个多边形，计算最高可能的分数。

## 输入格式

输入描述一个有n个顶点的多边形，它包含两行。第一行是数字n，为总边数。

第二行描述这个多边形，一共有2n个读入，每两个读入中第一个是字符，第二个是数字。

第一个字符为第一条边的计算符号(t代表相加，x代表相乘)，第二个代表顶点上的数字。首尾相连。

3 < = n < = 50

对于任何一系列的操作，顶点数字都在[-32768,32767]的范围内。

## 输出格式

第一行，输出最高的分数。在第二行，它必须写出所有可能的被清除后的边仍能得到最高得分的列表，必须严格递增。

感谢@2016c01 提供的翻译


title: [SHOI2015] 自动刷题机

background: 曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。

description:
自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

1.写了 $x$ 行代码
2.心情不好，删掉了之前写的 $y$ 行代码。（如果 $y$ 大于当前代码长度则相当于全部删除。）

对于一个 OJ，存在某个固定的正整数长度 $n$，一旦自动刷题机在某秒结束时积累了大于等于 $n$ 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 $n$ 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 $k$ 道题，希望你计算 $n$ 可能的最小值和最大值。

inputFormat:
第一行两个整数 $l , k$，表示刷题机的日志一共有 $l$ 行，一共了切了 $k$ 题。

接下来 $l$ 行，每行一个整数 $x_i$，依次表示每条日志。若 $x_i \geq 0$，则表示写了 $x_i$ 行代码，若 $x_i \lt 0$，则表示删除了 $-x_i$ 行代码。

outputFormat:
输出一行两个整数，分别表示 $n$ 可能的最小值和最大值。
如果这样的 $n$ 不存在，请输出一行一个整数 $-1$。