title: [GZOI2017] 河神

background:
GZOI2017 D2T1

终于忍受不了苦 X 的搬砖生活, Shlw 把手里的板砖扔进了河里.

不出意料地, 河神冒了出来.

Shlw 说: “我掉了金砖, 快给我金砖!”

“!!! 你已经知道套路了吗,”河神说道, “但是你要金砖的话, 我就不给你2017 彩虹小马大电影的资源了哦. 如果你说实话的话, 我还可以考虑一下.”

Shlw 发现事情并不简单, 在金钱和信仰面前, 难以抉择.

突然, Shlw 不理会河神, 自顾自的地跑走了.

“唉, 现在的年轻人啊... 真不知道在想什么.”Pinkie Pie 感叹, 卸下了河神伪装.

description:
Shlw 从河神给的选择中, 获得了一道当年挂掉的代数题的灵感.

但现在他希望你来帮忙解答, 因为他自己忙着去搜小马资源去了.

给出数列 $\{a_n\}$ 和 $\{b_n\}$ 以及 $\{A_n\}$ 的递推关系, 试求出数列 $\{A_n\}$ 第 $N$ 项.

递推关系为:

$$A_n=\begin{cases}a_n  &  0 \le n < K \\ \bigoplus (A_{n-K+t} \otimes b_t) & n \ge K \end{cases}$$

其中，$\otimes$ 表示与操作，$\oplus$ 表示或操作。

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

第二行 $K$ 个空格隔开的非负整数, 表示 $\{a_n\}$。

第三行 $K$ 个空格隔开的非负整数, 表示 $\{b_n\}$。

outputFormat: 一行, 一个整数, 表示$\{A_n\}$。

hint:
【样例解释】

从 $A_0$ 至 $A_{10}$ 分别为: $2, 3, 5, 7, 12, 15, 15, 13, 15, 15, 15$

【数据约束】

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

【后记】

后来, Pinkie Pie 偷偷来到 Shlw 家里, 她把这题拿回去考 Apple Jack, 于是 Apple Jack就有了狂吃苹果来畅游多重宇宙的本领.


title: [GZOI2017] 等差子序列

type: P

background: GZOI2017 D2T2

description: 给出一个长度为 $N$ 的正整数序列，问是否存在一个长度不小于三的等差子序列。

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

接下来 $T$ 组数据，每组数据第一行一个正整数 $N$，表示序列长度，接下来第二行有 $N$ 个正整数，依次表示序列中的数。

outputFormat: 对于每组数据，输出单独的一行 `YES` 或 `NO`。

hint:
【数据约束】

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

对于 $40\%$的数据：$N\le 10^3$。

对于 $100\%$的数据：$1\le T \le 10$，$1\le N\le 2\times 10^4$，序列中的数 $\le 2\times 10^4$。


title: [GZOI2017] 共享单车

background: GZOI2017 D2T3

description:
某校校内有 A 公司与 B 公司两家共享单车公司相互竞争。A 公司为了尽可能提升自己在校园内的占有率，会设法阻碍 B 公司的回收行动。

整个校园由 $N$ 个区域和 $M$ 条道路组成，每条道路连接两个区域。校园有一个区域 $K$ 是 B 公司的大本营，所有的单车回收行动从该区域 **出发**。B 公司为了减少成本，回收时从区域 $K$ 到任何一个区域 $X$ 都选择长度 **最短** 的路径，如果有多条到某一个区域的最短路径，则选择所有最短路径中该区域的前一区域 **编号最小** 的一条路径，称这条路径为 $K$ 到 $X$ 的 **回收路线**。所有的 **回收路线** 组成一棵树状结构，称之为 **回收路线树**。如下图中，绿色的边构成的就是一棵 **回收路线树**。

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

B 公司每次会回收若干个区域的单车，称这些区域为 **回收区域**。B 公司还将某些区域设为 **投放区域**，称其余区域为 **非投放区域**。在 **回收路线树** 上，标记出区域 $K$，标记出所有的 **回收区域**，以及标记出任意两个 **回收区域** 在 **回收路线树** 上的最近公共祖先。

如下图，假设 $4$ 与 $6$ 号区域是 **投放区域**，$4, 5, 6$ 号区域是**回收区域**，则被标记的区域有 $1, 4, 5, 6$。

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

A 公司对 B 公司的回收行动造成了阻碍，**当且仅当** 对任意一个 $K$ 以外的被标记的 **投放区域** $X$，从区域 $K$ 到 $X$ 的 **回收路线上** 都存在两个被标记的区域，它们之间 **所有道路**（回收路线树上两点路径）被阻碍。

阻碍一条道路的代价为该道路的长度。上图中 A 公司选择阻碍 $1 \rightsquigarrow  4$，$5 \rightsquigarrow 6$ 两条路径，代价为 $3+4+3=10$。

你的任务是帮助 A 公司计算如何以最小的代价，阻碍 B 公司的回收行动。

inputFormat:
第一行四个整数 $N, M, K, Q$ 分别表示 X 校校园内区域数量、道路数量以及 B 公司大本营的编号 $K$ 和操作数量。

第二到第 $M + 1$ 行描述道路，每行三个整数 $S,T,Len$ 表示有一条从 $S$ 出发 $T$ 结束的长度为 $Len$ 双向道路。

接下来第 $M + 2$ 行到第 $M + Q + 1$ 行，每行第一个整数表示操作类型，$0$ 表示 B 公司会改变**投放区域**，$1$ 表示 B 公司的一次回收行动。

操作类型为 $0$时，后接一个整数 $num$，表示 B 公司改变的区域数目，紧接着 $num$ 个数字分别表示区域编号。对于一个被改变的区域，如果它是 **投放区域**，把它改为 **非投放区域**；如果它是 **非投放区域**，把它改为 **投放区域**；

操作类型为 $1$ 时，后接一个整数 $num$ 表示 **回收区域** 数目，紧接着 $num$ 个整数表示 B 公司的 **回收区域** 编号。每次需要在 **回收路线树** 上重新标记。

outputFormat: 对于每一次回收行动，输出一行表示 A 公司对 B 公司造成阻碍的最小代价。注意，如果没有被标记的 **投放区域**，输出 $-1$。

hint:
【数据约束】

对于 $30\%$ 的数据，$N\le 200$，$Q\le 200$；

对于 $60\%$ 的数据，保证每次 **回收区域** 数量恒为 $N-1$；

对于 $80\%$ 的数据，$N\le 20000$，$M=N-1$，$Q\le 1000$，$num\le 200$；

对于 $100\%$ 的数据，$N\le 50000$，$M\le 100000$，$Q\le 1500$，$num\le 500$。

所有数据保证道路无自环，所有道路长度小于 $2000$，且区域 $K$ 任意时刻均非**投放区域**。


title: [QkOI#R1] Quark and Game

description:
给定 $n$ 个二元组 $(a_i,b_i)$，当 $b_i\le 0$ 时该二元组不再可以被操作。你可以执行两个操作：

1. 对于**所有**可以被操作的二元组，执行 $b_i\gets b_i-a_i$，即令 $b_i$ 的值减少 $a_i$，花费 $p$。

2. 对于**所有**可以被操作的二元组，执行 $\operatorname{Swap}(a_i,b_i)$，其中 $\operatorname{Swap}(x,y)$ 表示交换 $x,y$ 的值，花费 $q$。

现在，你要用最少的花费，使得所有二元组都不可以被操作.

inputFormat:
第一行有三个正整数 $n,p,q$。

接下来 $n$ 行每行有两个正整数 $a_i,b_i$ 表示第 $i$ 个二元组 $(a_i,b_i)$。

outputFormat: 输出一行一个整数，表示你所求得的最小花费。

hint:
### 样例解释

对于第一个样例，我们可以先后进行 $1$ 次操作 1，$1$ 次操作 2，$1$ 次操作 1，最小花费为 $9 + 5 + 9 = 23$。
对于第二个样例，我们可以进行 $2$ 次操作 1，最小花费为 $500 \times 2 = 1000$。
对于第三个样例，我们可以进行 $500$ 次操作 1，最小花费为 $1 \times 500 = 500$。

---

### 数据范围

**本题采用捆绑测试。**

- Subtask 1（10 pts）：$n\le 100$，$a_i,b_i\le 20$。
- Subtask 2（20 pts）：$n\le 1000$，$a_i,b_i\le 1000$。
- Subtask 3（17 pts）：$p=1$，$q=10^7$。
- Subtask 4（53 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le p,q\le 10^7$，$1\le a_i,b_i\le 10^5$。


title: [QkOI#R1] Quark and Graph

background: SPFA 被卡时在做什么？有没有空？可以来计数吗？

description:
现有一张边权全为 $1$ 的有标号简单无向连通图，其包含 $n$ 个节点和 $m$ 条边，已知该图上点 $1$ 到所有点的最短路长，求这张图有多少种形态。

特别地，我们认为点 $1$ 到点 $1$ 的最短路为 $0$。

两个图的形态不同当且仅当存在至少一条边 $(u,v)$ 在一张图中出现且在另一张图中没出现。

**由于 little_sun 太巨了，所以数据保证至少存在一张满足条件的图。**

答案对 $998244353$ 取模。

inputFormat:
第一行两个正整数 $n,m$ —— $n$ 表示图的节点数，$m$ 表示图的边数。

第二行 $n$ 个非负整数 $d_1,d_2,\cdots,d_n$ 表示点 $1$ 到其它点的最短路。

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

hint:
### 样例解释

对于第一个样例，有 $\{(1,2),(1,3),(2,4)\}$ 和 $\{(1,2),(1,3),(3,4)\}$ 两种形态。

对于第二个样例，我想到了一个绝妙的解释，可惜这里空白太小，写不下。

### 数据范围

**本题采用捆绑测试。**

- Subtask 1（10 pts），满足 $n\le 7$，$m\le 14$，时限 1s；
- Subtask 2（20 pts），满足 $n\le 50$，$m\le 600$，时限 1s；
- Subtask 3（20 pts），满足 $n\le 1000$，$m\le 5000$，时限 1s；
- Subtask 4（50 pts），无特殊限制，时限 3s。

对于 $100\%$ 的数据，满足 $n\le 10^5$，$m\le 2\times 10^5$。设 $t_i=\sum_j[d_j=i]$，还应满足 $\sum_{i}t_it_{i-1}\le 2\times 10^5$。

**本题强制开启 O2 优化。**


title: [CQOI2008] 矩阵的个数

description: 给出一个 $n\times 3$ 的非负整数矩阵的各行各列之和，统计有多少个矩阵满足此条件。输出答案模 $10^{17}$ 的值。

inputFormat: 第一行包含四个正整数 $N$，$c_1$，$c_2$，$c_3$，即行数与三列之和。第二行包含 $N$ 个正整数，即各行三个数之和。每行每列之和均不超过 $125$。

outputFormat: 仅一个数，满足条件的矩阵个数模 $10^{17}$ 的值。


title: 【L&K R-03】课表的排列

background: 小 L 早上来到教室，发现今天的课表非常有趣。

description:
今天的课表是：

    语文 数学 英语 语文 英语 数学

今天的课表上一共有三个科目：语文、数学、英语。每个科目都有两节课。每科的两节课间隔的课程数分别为 $2,3,1$，从小到大排序后为 $1,2,3$，是一个公差为 $1$ 的等差数列。

小 L 想知道，对于更多的科目，具有这样有趣性质的课表是否存在。换句话说，如果课表上一共有 $n$ 个科目，每个科目都有且仅有两节课，小 L 想知道是否存在一个课表，满足这 $n$ 科的两节课间隔的课程数从小到大排序后是一个公差为 $1$ 的等差数列。

但是，小 L 只会写时间复杂度为 $O((2n)!\times n\log_2 n)$ 的算法，于是他求助于你，请你判断是否存在这样的课表，如果存在，还要输出一种可能的情况。

inputFormat: 输入仅一行，一个 **奇数** $n$，表示课表上的课程数。

outputFormat:
输出仅一行。

如果不存在这样的课表，输出  `-1`；

如果存在这样的课表，输出 $2n$ 个整数，表示课表。令 $1,2,\ldots ,n$ 中的每一个整数对应一个科目，每个整数在课表中均会出现两次，且满足小 L 的性质。由于可能有多种可能的答案，你可以给出任意一种课表，刚到教室的小 K 会写出程序来检验你的课表是否满足小 L 的性质。


title: [CSP-S2019 江西] 和积和

background: JXCSP-S T2

description:
给定两个下标从 $1$ 到 $n$ 编号的序列 $a_i,b_i$，定义函数 $S(l,r)(1\le l\le r\le n)$ 为：

$$\sum_{i=l}^r a_i\times \sum_{i=l}^r b_i$$

请你求出下列式子的值：

$$\sum_{l=1}^n \sum_{r=l}^n S(l,r)$$

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

inputFormat:
第一行一个正整数 $n$ 表示序列长度。
第二行 $n$ 个正整数表示 $a_i$。
第三行 $n$ 个正整数表示 $b_i$。

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


title: [CSP-J2019 江西] 面积

description: Alice 有一个边长为 $a$ 的正方形，Bob 有一个长宽分别为 $b,c$ 的矩形，请你告诉他们俩谁的图形面积更大。

inputFormat: 仅一行三个正整数 $a,b,c$

outputFormat: 输出仅一行一个字符串，若正方形面积大则输出 `Alice`，否则输出 `Bob`。

samples:
5 4 6
Alice

hint:
【数据范围】
对于 $30\%$ 的数据，$1 \le a,b,c \le 100$，$b=c$；
对于 $80\%$ 的数据，$1\le a,b,c \le 10^4$；
对于 $100\%$ 的数据，$1\le a,b,c \le 10^9$。

【样例 $1$ 解释】
正方形面积为  $25$，矩形面积为 $24$。

【样例 $2$ 解释】
正方形面积为  $49$，矩形面积为 $50$。


title: [CSP-J2019 江西] 次大值

description:
Alice 有 $n$ 个正整数，数字从 $1 \sim n$ 编号，分别为 $a_1,a_2, \dots , a_n$。
Bob 刚学习取模运算，于是便拿这 $n$ 个数进行练习，他写下了所有

$$a_i \bmod a_j (1 \le i,j \le n \wedge i \neq j)$$

的值，其中 $\bmod$ 表示取模运算。

Alice 想知道所有的结果中，严格次大值是多少。将取模后得到的所有值进行去重，即相同的结果数值只保留一个，剩余数中第二大的值就称为严格次大值。

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

outputFormat:
仅一行一个整数表示答案。
若取模结果去重后剩余数字不足两个，则输出 $-1$。


title: [CSP-J2019 江西] 道路拆除

description:
A 国有 $n$ 座城市，从 $1 \sim n$ 编号。$1$ 号城市是 A 国的首都。城市间由 $m$ 条双向道路连通，通过每一条道路所花费的时间均为 $1$ 单位时间。

现在 A 国打算拆除一些不实用的道路以减小维护的开支，但 A 国也需要保证主要线路不受影响。因此 A 国希望道路拆除完毕后，利用剩余未被拆除的道路，从 A 国首都出发，能到达 $s_1$ 号与 $s_2$ 号城市，且所要花费的最短时间分别不超过 $t_1$ 与 $t_2$（注意这是两个独立的条件，互相之间没有关联，即不需要先到 $s_1$ 再到 $s_2$）。

A 国想请你帮他们算算，在满足上述条件的情况下，他们最多能拆除多少条道路。 若上述条件永远无法满足，则输出 $-1$。

inputFormat:
第一行两个正整数 $n,m$，表示城市数与道路数。

接下来 $m$ 行，每行两个正整数 $x,y$，表示一条连接 $x$ 号点与 $y$ 号点的道路。

最后一行四个整数，分别为 $s_1,t_1,s_2,t_2$。

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

hint:
【数据范围】
对于 $30\%$ 的数据，$n,m \le 15$；
另有 $20\%$ 的数据，$n \le 100$，$m = n-1$；
另有 $30\%$ 的数据，$s_1 = s_2$；
对于 $100\%$ 的数据，$2 \le n,m \le 3000$，$1\le x,y \le n$，$2 \le s_1,s_2 \le n$，$0 \le t_1,t_2 \le n$。

【样例 $1$ 解释】
拆除 $(1,2),(2,3),(3,4)$ 三条边。
注意：不需要令首都与除了 $s_1,s_2$ 外的点在拆除之后依然连通。

【样例 $2$ 解释】
即使一条边都不拆除，首都到 $3$ 号点的最短时间也都达到了 $2$ 单位时间。

testdata by @DYH060310


title: [CSP-J2019 江西] 非回文串

description:
Alice 有 $n$ 个字符，它们都是英文小写字母，从 $1 \sim n$ 编号，分别为 $c_1,c_2, \dots , c_n$。
Bob 准备将这些字符重新排列，组成一个字符串 $S$。Bob 知道 Alice 有强迫症，所以他打算将 $S$ 组成一个非回文串来折磨 Alice。

现在 Bob 想知道他共有多少种不同的排列字符的方案，能使得 $S$ 是个非回文串。一种排列字符的方案指的是一个 $1 \sim n$ 的排列 $p_i$，它所组成的 $S = c_{p_1}c_{p_2} \dots c_{p_n}$。

一个字符串是非回文串，当且仅当它的逆序串与原串不同。例如 `abcda` 的逆序串为 `adcba`，与原串不同，故 `abcda` 是非回文串。而 `abcba` 的逆序串与原串相同，是回文串。

由于最后的结果可能很大，你只需要告诉 Bob 总方案数对 $10^9+7$ 取模后的值。

inputFormat:
第一行一个正整数 $n$ 表示字符个数。
第二行 $n$ 个英文小写字母 $c_i$。

outputFormat: 仅一行一个整数表示答案。答案对 $10^9+7$ 取模。

hint:
【数据范围】
对于 $20\%$ 的数据，$n \le 8$；
对于 $50\%$ 的数据，$n \le 20$；
另有 $30\%$ 的数据，字符只包含 `a` 和 `b`；
对于 $100\%$ 的数据，$3 \le n \le 2000$。


title: 【深基4.习5】求极差 / 最大跨度值

description: 给出 $n$ 和 $n$ 个整数 $a_i$，求这 $n$ 个整数中的极差是什么。极差的意思是一组数中的最大值减去最小值的差。

inputFormat:
第一行输入一个正整数 $n$，表示整数个数。

第二行输入 $n$ 个整数 $a_1,a_2 \dots a_n$，以空格隔开。

outputFormat: 输出一个整数，表示这 $n$ 个整数的极差。

hint: 数据保证，$1 \leq n\leq 100$，$0\le a_i \le 1000$。


title: 【深基4.习8】求三角形

description: 模仿例题，打印出不同方向的正方形，然后打印三角形矩阵。中间有个空行。

inputFormat: 输入矩阵的规模，不超过 $9$。

outputFormat: 输出矩形和正方形


title: 【深基5.例3】冰雹猜想

description:
给出一个正整数 $n$，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 $3$ 再加 $1$，否则除以 $2$。经过若干次循环后，最终都会回到 $1$。经过验证很大的数字（$7\times10^{11}$）都可以按照这样的方式比变成 $1$，所以被称为“冰雹猜想”。例如当 $n$ 是 $20$，变化的过程是 $20\to 10\to 5\to 16\to 8\to 4\to 2\to 1$。

根据给定的数字，验证这个猜想，并从最后的 $1$ 开始，倒序输出整个变化序列。

inputFormat: 输入一个正整数 $n$。

outputFormat: 输出若干个由空格隔开的正整数，表示从最后的 $1$ 开始倒序的变化数列。

hint: 数据保证，$1 \le n\le 100$。


title: 【深基5.例5】旗鼓相当的对手

description: 现有 $N$ 名同学参加了期末考试，并且获得了每名同学的信息：语文、数学、英语成绩（均为不超过 $150$ 的自然数）。如果某对学生 $\lang i,j\rang$ 的每一科成绩的分差都不大于 $5$，且总分分差不大于 $10$，那么这对学生就是“旗鼓相当的对手”。现在想知道这些同学中，有几对“旗鼓相当的对手”？同样一个人可能会和其他好几名同学结对。

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

接下来 $N$ 行，每行三个整数，其中第 $i$ 行表示第 $i$ 名同学的语文、数学、英语成绩。最先读入的同学编号为 $1$。

outputFormat: 输出一个整数，表示“旗鼓相当的对手”的对数。

hint: 数据保证，$2 \le N\le 1000$ 且每科成绩为不超过 $150$ 的自然数。


title: 【深基5.例7】工艺品制作

description:
现有一个长宽高分别为 $w,x,h$ 组成的实心玻璃立方体，可以认为是由 $1\times1\times1$ 的数个小方块组成的，每个小方块都有一个坐标 $ ( i,j,k ) $。现在需要进行 $q$ 次切割。每次切割给出 $(x_1,y_1,z_1),(x_2,y_2,z_2)$ 这 6 个参数，保证 $x_1\le x_2$，$y_1\le y_2$，$z_1\le z_2$；每次切割时，使用激光工具切出一个立方体空洞，空洞的壁平行于立方体的面，空洞的对角点就是给出的切割参数的两个点。

换句话说，所有满足  $x_1\le i\le x_2$，$y_1\le j \le y_2 $，$z_1\le k\le z_2$ 的小方块 $(i,j,k)$ 的点都会被激光蒸发。例如有一个  $4\times4\times 4$ 的大方块，其体积为 $64$；给出参数 $(1,1,1),(2,2,2)$ 时，中间的 $8$ 块小方块就会被蒸发，剩下 $56$ 个小方块。现在想知道经过所有切割操作后，剩下的工艺品还剩下多少格小方块的体积？

inputFormat:
第一行三个正整数 $w,x,h$。

第二行一个正整数 $q$。

接下来 $q$ 行，每行六个整数 $(x_1,y_1,z_1),(x_2,y_2,z_2)$。

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

hint: 数据保证，$1\le w,x,h\le 20$，$1 \leq q\le 100$。$1 \leq x_1 \leq x_2 \leq w$，$1 \leq y_1\leq y_2 \leq x$，$1 \leq z_1 \leq z_2 \leq h$。


title: 【深基5.例10】显示屏

description: 液晶屏上，每个阿拉伯数字都是可以显示成 $3\times5$ 的点阵的（其中 `X` 表示亮点，`.` 表示暗点）。现在给出数字位数（不超过 $100$）和一串数字，要求输出这些数字在显示屏上的效果。数字的显示方式如同样例输出，注意每个数字之间都有一列间隔。

inputFormat:
第一行输入一个正整数 $n$，表示数字的位数。

第二行输入一个长度为 $n$ 的自然数。

outputFormat: 输出五行，表示显示屏上的数字。

hint: 数据保证，$1 \leq n \leq 100$。


title: 【深基5.习6】蛇形方阵

description:
给出一个不大于 $9$ 的正整数 $n$，输出 $n\times n$
的蛇形方阵。

从左上角填上 $1$ 开始，顺时针方向依次填入数字，如同样例所示。注意每个数字有都会占用 $3$ 个字符，前面使用空格补齐。

inputFormat: 输入一个正整数 $n$，含义如题所述。

outputFormat: 输出符合题目要求的蛇形矩阵。

hint: 数据保证，$1 \leq n \leq 9$。


title: 【深基5.习7】杨辉三角

description:
给出 $n(1\le n\le20)$，输出杨辉三角的前 $n$ 行。

如果你不知道什么是杨辉三角，可以观察样例找找规律。


title: 【深基6.例1】自动修正

description: 大家都知道一些办公软件有自动将字母转换为大写的功能。输入一个长度不超过 $100$ 且不包括空格的字符串。要求将该字符串中的所有小写字母变成大写字母并输出。

inputFormat: 输入一行，一个字符串。

outputFormat: 输出一个字符串，即将原字符串中的所有小写字母转化为大写字母。


title: 【深基6.例6】文字处理软件

description:
你需要开发一款文字处理软件。最开始时输入一个字符串作为初始文档。可以认为文档开头是第 $0$ 个字符。需要支持以下操作：

- `1 str`：后接插入，在文档后面插入字符串 $\texttt{str}$，并输出文档的字符串；
- `2 a b`：截取文档部分，只保留文档中从第 $a$ 个字符起 $b$ 个字符，并输出文档的字符串；
- `3 a str`：插入片段，在文档中第 $a$ 个字符前面插入字符串 $\texttt{str}$，并输出文档的字符串；
- `4 str`：查找子串，查找字符串 $\texttt{str}$ 在文档中最先的位置并输出；如果找不到输出 $-1$。

为了简化问题，规定初始的文档和每次操作中的 $\texttt{str}$ 都不含有空格或换行。最多会有 $q$ 次操作。

inputFormat:
第一行输入一个正整数 $q$，表示操作次数。

第二行输入一个字符串 $\texttt{str}$，表示最开始的字符串。

第三行开始，往下 $q$ 行，每行表示一个操作，操作如题目描述所示。

outputFormat:
一共输出 $q$ 行。

对于每个操作 $1,2,3$，根据操作的要求输出一个字符串。

对于操作 $4$，根据操作的要求输出一个整数。

hint: 数据保证，$1 \leq q\le 100$，开始的字符串长度 $\leq 100$。


title: 【深基7.例1】距离函数

description:
给出平面坐标上不在一条直线上三个点坐标 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，坐标值是实数，且绝对值不超过 100.00，求围成的三角形周长。保留两位小数。

对于平面上的两个点 $(x_1,y_1),(x_2,y_2)$，则这两个点之间的距离 $dis=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

inputFormat: 输入三行，第 $i$ 行表示坐标 $(x_i,y_i)$，以一个空格隔开。

outputFormat: 输出一个两位小数，表示由这三个坐标围成的三角形的周长。

hint: 数据保证，坐标均为实数且绝对值不超过 $100$，小数点后最多仅有 $3$ 位。


title: 【深基7.例2】质数筛

description: 输入 $n$ 个不大于 $10^5$ 的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

inputFormat:
第一行输入一个正整数 $n$，表示整数个数。

第二行输入 $n$ 个正整数 $a_i$，以空格隔开。

outputFormat: 输出一行，依次输出 $a_i$ 中剩余的质数，以空格隔开。

hint: 数据保证，$1\le n\le100$，$1 \leq a_i \leq 10^5$。


title: 【深基7.例3】闰年展示

description: 输入 $x,y$，输出 $[x,y]$ 区间中闰年个数，并在下一行输出所有闰年年份数字，使用空格隔开。

inputFormat: 输入两个正整数 $x,y$，以空格隔开。

outputFormat:
第一行输出一个正整数，表示 $[x,y]$ 区间中闰年个数。

第二行输出若干个正整数，按照年份单调递增的顺序输出所有闰年年份数字。


title: 【深基7.例4】歌唱比赛

description: $n(n\le 100)$ 名同学参加歌唱比赛，并接受 $m(m\le 20)$ 名评委的评分，评分范围是 $0$ 到 $10$ 分。这名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下 $m-2$ 个评分的平均数。请问得分最高的同学分数是多少？评分保留 $2$ 位小数。

inputFormat:
第一行两个整数 $n,m$。
接下来 $n$ 行，每行各 $m$ 个整数，表示得分。

outputFormat: 输出分数最高的同学的分数，保留两位小数。


title: 【深基7.例7】计算阶乘

description:
求 $n!$，也就是 $1\times2\times3\dots\times n$。

挑战：尝试不使用循环语句（for、while）完成这个任务。

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

outputFormat: 输出一个正整数，表示 $n!$。

hint: 数据保证，$1 \leq n\le12$。


title: 【深基7.例9】最厉害的学生

description: 现有 $N$ 名同学参加了期末考试，并且获得了每名同学的信息：姓名（不超过 $8$ 个字符的仅有英文小写字母的字符串）、语文、数学、英语成绩（均为不超过 $150$ 的自然数）。总分最高的学生就是最厉害的，请输出最厉害的学生各项信息（姓名、各科成绩）。如果有多个总分相同的学生，输出靠前的那位。

inputFormat:
第一行输入一个正整数 $N$，表示学生个数。

第二行开始，往下 $N$ 行，对于每一行首先先输入一个字符串表示学生姓名，再输入三个自然数表示语文、数学、英语的成绩。均用空格相隔。

outputFormat: 输出最厉害的学生。

hint: 数据保证，$1 \leq N \leq 1000$，姓名为长度不超过 $8$ 的字符串，语文、数学、英语成绩均为不超过 $150$ 的自然数。


title: 【深基7.例10】旗鼓相当的对手 - 加强版

description:
现有 $N(N\le 1000)$ 名同学参加了期末考试，并且获得了每名同学的信息：姓名（不超过 $8$ 个字符的字符串，没有空格）、语文、数学、英语成绩（均为不超过 $150$ 的自然数）。如果某对学生 $\text{<}i,j\text{>}$ 的每一科成绩的分差都不大于 $5$，且总分分差不大于 $10$，那么这对学生就是“旗鼓相当的对手”。现在我们想知道这些同学中，哪些是“旗鼓相当的对手”？请输出他们的姓名。

所有人的姓名是按照字典序给出的，输出时也应该按照字典序输出所有对手组合。也就是说，这对组合的第一个名字的字典序应该小于第二个；如果两个组合中第一个名字不一样，则第一个名字字典序小的先输出；如果两个组合的第一个名字一样但第二个名字不同，则第二个名字字典序小的先输出。

outputFormat: 输出若干行，每行两个以空格隔开的字符串，表示一组旗鼓相当的对手。注意题目描述中的输出格式。


title: 【深基7.例11】评等级

description:
现有 $N$ 名同学，每名同学需要设计一个结构体记录以下信息：学号、学业成绩和素质拓展成绩、综合分数（实数）。每行读入同学的学号、学业成绩和素质拓展成绩，并且计算综合分数（分别按照 $70\%$ 和 $30\%$ 权重累加），存入结构体中。还需要在结构体中定义一个成员函数，返回该结构体对象的学业成绩和素质拓展成绩的总分。

然后需要设计一个函数，其参数是一个学生结构体对象，判断该学生是否“优秀”。优秀的定义是学业和素质拓展成绩总分**大于** $140$ 分，且综合分数**不小于** $80$ 分。

> 当然通过本题很容易啦，本题只是为了帮助你训练结构体的使用方法。

本题存在精度误差问题，请将 `a * 0.7 + b * 0.3` 与 80 比较 转化为 `a * 7 + b * 3` 与 800 比较。

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

接下来 $N$ 行，每行 $3$ 个整数，依次代表学号、学业成绩和素质拓展成绩。

outputFormat: $N$ 行，如果第 $i$ 名学生是优秀的，输出 `Excellent`，否则输出 `Not excellent`。

samples:
Excellent
Not excellent
Not excellent
Excellent

hint: 数据保证，$1 \le N\le 1000$，学号为不超过 $100000$ 的正整数，学业成绩和素质拓展成绩为 $0 \sim 100$ 之间的正整数。


title: 【深基7.习8】猴子吃桃

description: 一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半，又贪嘴多吃了一个；接下来的每一天它都会吃剩余的桃子的一半外加一个。第 $n$ 天早上起来一看，只剩下 $1$ 个桃子了。请问小猴买了几个桃子？

inputFormat: 输入一个正整数 $n$，表示天数。

outputFormat: 输出小猴买了多少个桃子。

hint: 数据保证，$1\le n\le20$。


title: 【深基7.习9】培训

description:
某培训机构的学员有如下信息：

- 姓名（字符串）
- 年龄（周岁，整数）
- 去年 NOIP 成绩（整数，且保证是 $5$ 的倍数）

经过为期一年的培训，所有同学的成绩都有所提高，提升了 $20\%$（当然 NOIP 满分是 $600$ 分，不能超过这个得分）。

输入学员信息，请设计一个结构体储存这些学生信息，并设计一个函数模拟培训过程，其参数是这样的结构体类型，返回同样的结构体类型，并输出学员信息。

inputFormat:
第一行输入一个正整数 $n$，表示学员个数。

第二行开始往下 $n$ 行。每行首先是一个字符串表示学员姓名，再是一个整数表示学员年龄，再是一个整数为去年 NOIP 成绩。

outputFormat: 输出 $n$ 行，每行首先输出一个字符串表示学生姓名，再往后两个整数，表示经过一年的培训后学员的年龄和他们今年的 NOIP 成绩。以空格隔开。

hint: 数据保证，$1 \leq n \leq 5$。年龄为 $0 \sim 100$（含 $0$ 与 $100$）的整数。成绩为 $0 \sim 600$（含 $0$ 与 $600$）的 $5$ 的整倍数。


title: [CSP-S2019 江西] 网格图

background: JXCSP-S T3

description:
给定一个 $n\times m$ 的网格图，行从 $1\sim n$ 编号，列从 $1\sim m$ 编号，每个点可用它所在的行编号 $r$ 与所在的列编号 $c$ 表示为 $(r, c)$。

点 $(i,j)$ 与 $(i,j+1)$ 间连有一条权值为 $a_i$ 的边，其中 $1\le i\le n, 1\le j<m$。

点 $(i, j)$ 与 $(i+1,j)$ 间连有一条权值为 $b_j$ 的边，其中 $1\le i< n, 1\le j \le m$。

请你求出这个网格图的最小生成树。

inputFormat:
第一行两个正整数 $n, m$ 表示行数与列数。

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

第三行 $m$ 个正整数表示 $b_j$。

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

hint:
#### 【输入输出样例 1 说明】
最小生成树中的边包括：第一行上的所有边，第一列、第二列、第三列上的所有边。

#### 【数据规模与约定】

对于 $20\%$ 的数据，$n, m\le 3$，$a_i, b_j \le 10$；

对于 $40\%$ 的数据，$n, m\le 20$，$a_i, b_j\le 100$；

对于 $64\%$ 的数据，$n, m\le 300$，$a_i, b_j\le 1000$；

对于 $100\%$ 的数据：$3\le n, m \le 3\times 10^5$，$1 \le a_i, b_j\le 10^5$。


title: [CSP-S2019 江西] 散步

background: JXCSP-S T4

description:
公园内有 $n$ 个人正在散步，随着天色渐晚，所有人准备回家离开公园。公园的结构是一个首尾相连的环形图，它共有 $m$ 个出口，为了方便叙述，我们将人从 $1\sim n$ 编号，将出口按逆时针顺序从 $1\sim m$ 编号。

公园总长 $L$ 米，我们令 $1$ 号出口所在的位置为 $0$ 米，则 编号为 $i\ (2\le i\le m)$ 的出口在 $1$ 号出口逆时针方向 $a_i$ 米的位置上，其中 $a_i$ 严格递增 ，即 $i\ (1\le i < m)$ 号出口与 $i+1$ 号出口相邻，由于公园是环形图，故 $m$ 号出口与 $1$ 号出口也相邻。每个出口还有一个通行限制 $l_i$，表示最多有 $l_i$ 个人能从 $i$ 号出口离开。

所有人回家时将按自己的朝向，可能是顺时针方向，也可能是逆时针方向不断前行，当他们走到一个还能离开的出口时，将从该出口离开公园。特别地，当两个人同时走到一个只能允许 $1$ 个人离开的出口时，编号小的那个人能从该出口离开，编号较大的人将继续前进。

现在给定 $n$ 个人所在的起始位置与他们的前进方向，请你求出每个人从哪个出口离开，若编号为 $i$ 的 人从 $k_i$ 号出口离开，你只需要给出 $i\times k_i$ 的异或和，即：

$$ (1\times k_1) \operatorname{xor} (2\times k_2) \operatorname{xor}\cdots \operatorname{xor} (n\times k_n) $$

其中 $\operatorname{xor}$ 是位异或运算。特别地若一个人最后无法离开，则他的 $k_i = 0$。

inputFormat:
第一行三个正整数 $n, m, L$，意义见题目描述。

第二行 $m - 1$ 个正整数 $a_i\ (2\le i \le m)$ 表示出口位置。保证 $a_i$ 严格递增。

第三行 $m$ 个正整数 $l_i$ 表示出口的人数限制。

接下来 $n$ 行每行两个整数 $s_i,b_i\ (1 \le i \le n)$。若 $s_i$ 为 $0$ 表示编号为 $i$ 的人前进方向是逆时针方向，为 $1$ 表示是顺时针方向。 $b_i$ 表示编号为 $i$ 的人的起始位置为：离 $1$ 号出口逆时针方向 $b_i$ 米的位置。

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

hint:
#### 【输入输出样例 1 说明】
编号为 $1 ,2, 3$ 的人分别从 $2, 1, 1$ 号出口离开。

#### 【输入输出样例 2 说明】
编号为 $1,2$ 的人分别从 $1 ,2$ 号出口离开，编号为 $3$ 的人无法离开公园。

#### 【数据规模与约定】
对于 $12\%$ 的数据：$n, m, L \le 10$；

对于 $32\%$ 的数据：$n, m \le 100$，$L \le 1000$；

对于 $52\%$ 的数据：$n, m \le 1000$；

另有 $20\%$ 的数据：$n, m \le 10000$，所有 $s_i = 0$；

对于 $100\%$ 的数据：$1 \le n,m \le 2 \times 10^5 $，$2 \le L \le 10^9$，$1\le a_i <L$，$1\le l_i \le n$，$s_i\in\{0,1\}$，$0\le b_i<L$。


title: [CSP-S2019 江西] 多叉堆

background: JXCSP-S T5

description:
多叉堆是一种树形数据结构，本题中我们只考虑小根堆，它满足除了根以外的结点，每个点的权值都不小于父亲的权值。除了叶结点，每个点有至少一个子结点。

初始时有 $n$ 个结点，编号分别为 $0 \sim n - 1$ ，每个结点都是一棵以自身为根的单点树。接下来按顺序有 $q$ 次操作，每次操作有以下两种：

* `1 x y`：选择不在同一棵树里的结点 $x$ 和 $y$，将 $x$ 所在树的根直接接在 $y$ 所在树的根之下，此时 $x$ 和 $y$ 所在树将合并为同一棵树。

* `2 x`：选择结点 $x$，设 $x$ 当前所在树的结点数为 $size$。你需要计算将 $0 \sim size - 1$ 这 $size$ 个数分别填入 $x$ 所在树的结点中，能够产生多少种不同的多叉堆。两种堆不同当且仅当存在某个结点填入的值不同。由于答案可能很大，你只需要求出答案模 $10^9+7$ 后的结果。

inputFormat:
第一行两个整数 $n, q$，具体含义见题目描述。

接下来 $q$ 行每行可能是下面两种格式之一：

* `1 x' y'`：你需要通过计算 $x=(x'+ans) \bmod n , y=(y'+ans) \bmod n$ 来得到真正的 $x$ 和 $y$，输入保证 $x$ 和 $y$ 所在树不同。

* `2 x'`：你需要通过计算 $x=(x'+ans) \bmod n$ 来得到真正的 $x$。

其中 $ans$ 表示上一次 $2$ 操作的输出结果 ，初始时 $ans=0$。

outputFormat: 对于每次 $2$ 操作输出一行一个整数表示答案。

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

第 $1$ 次操作时，将 $1$ 所在树的根 $1$ 接在 $0$ 所在树的根 $0$ 下。

第 $2$ 次操作时，将 $2$ 所在树的根 $2$ 接在 $0$ 所在树的根 $0$ 下。

第 $3$ 次操作时，$1$ 所在树如图 $1$，在 $0,1,2$ 中分别填入 $[0,1,2]$ 和 $[0,2,1]$ 可以产生 $2$ 种不同的堆。

第 $4$ 次操作时 $x=(3+2) \bmod 5=0$，$y=(1+2) \bmod 5=3$，将 $0$ 所在树的根 $0$ 接在 $3$ 所在树的根 $3$ 下。

第 $5$ 次操作 时，$x=(2+2) \bmod 5=4$，$y=(0+2) \bmod 5=2$，将 $4$ 所在树的根 $4$ 接在 $2$ 所在树的根 $3$ 下。

第 $6$ 次操作 时，$x=(4+2) \bmod 5=1$，$1$ 所在树如图 $2$，在 $0\sim 4$ 中分别填入 $[1,2,3,0,4]$，$[1,3,2,0,4]$，$[1,2,4,0,3]$，$[1,4,2,0,3]$，$[1,3,4,0,2]$，$[1,4,3,0,2]$，$[2,4,3,0,1]$ 可以产生 $8$ 种不同的堆。

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

#### 【数据规模与约定】

对于 $100\%$ 的数据，$0\le x',y' <n \le 3\times 10^5$，$1\le Q\le 3\times 10^5$。

对于不同测试点，我们约定

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

特殊性质 $1$：存在 $1\le i<n $，前 $i$ 次操作均为 $1$ 操作，之后全是 $2$ 操作。

特殊性质 $2$：对于所有输入 $x$ 和 $y$ 本身即是其所在树的根。

感谢 @Fairicle 提供的数据。


title: [QkOI#R1] Quark and Strings

description:
你需要维护一个字符串序列 $\{S_n\}$，其中有 $n$ 个字符串，初始全为空。接下来有 $q$ 次操作，支持两种操作，下面设当前为第 $i$ 次操作，且本题中字符集为 $[1,q]\cap \N_+$：

- `1 l r`，表示在所有编号在 $[l,r]$ 内的字符串末尾添加字符 $i$，这里 $i$ 是一个 $[1,q]$ 范围内的整数。
- `2 l r`，表示询问所有编号在 $[l,r]$ 内的字符串的最长公共子序列长度。当 $l=r$ 时，我们认为其最长公共子序列长度即为该字符串的长度。

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

接下来 $q$ 行每行三个正整数形如 `1 l r` 或 `2 l r`。

outputFormat: 对于每次操作 $2$，输出一行非负整数作为你的答案。

hint:
### 样例解释

对于第一组样例：
第一次操作后，序列为 $\{[1],[1],[1],[],[]\}$。
第二次操作后，序列为 $\{[1,2],[1,2],[1,2],[2],[2]\}$。
第三次操作，容易发现询问的最长公共子序列为 $[2]$，长度为 $1$。

---

### 数据范围

**本题采用捆绑测试。**

- Subtask 1（10 pts）：$n,q\le 500$。
- Subtask 2（20 pts）：$n,q\le 1000$。
- Subtask 3（15 pts）：$n\le 1000$，操作 $1$ 不超过 $500$ 次，时限 $2000$ms。
- Subtask 4（15 pts）：$n\le 1000$，操作 $2$ 不超过 $500$ 次，时限 $2000$ms。
- Subtask 5（40 pts）：无特殊限制，时限 $3000$ms。

对于 $100\%$ 的数据，$1\le n,q\le 10^5$，除了特殊标明的 Subtask，其它 Subtask 时限均为 $1000$ms。


title: calc加强版

background: [原题链接](https://www.luogu.com.cn/problem/P4463)

description:
一个序列 $a_1,\cdots,a_n$ 是合法的，当且仅当：

长度为给定的 $n$。

$a_1,\cdots,a_n$ 都是 $[1,k]$ 中的整数。

$a_1,\cdots,a_n$ 互不相等。

一个序列的值定义为它里面所有数的乘积，即 $a_1\times a_2\times\cdots\times a_n$ 。

求所有不同合法序列的值的和。

两个序列不同当且仅当他们任意一位不一样。

输出答案对 $998244353$ 取余的结果。

inputFormat: 一行两个数 $k,m$。

outputFormat: 共 $m$ 行，第 $i(1\le i\le m)$ 行表示 $n=i$ 时的答案。

hint:
$\text{subtask 1 (84 pts)}$：$1\le m\le 500$

$\text{subtask 2 (16 pts)}$：$1\le m\le 5\times 10^5$，建议使用高效输出方式。

对所有数据，$1\le m\le k\le 998244352$。


title: [CSP-S2019 江西] 日期

background: CSP-SJX2019 T1

description:
Alice在纸上写下了一个日期，形式为 $\text{MM-DD}$，其中 $\text{MM}$ 与 $\text{DD}$ 都是两位数字，分别表示月和天，然而这个日期并不一定存在。 Alice找来了Bob要他更改若干位上的数字，使得这个日期存在。请你帮Bob算算他最少需要更改几位数字。

本题中我们认为 $2$ 月固定为 $28$ 天。

inputFormat: 仅一行一个五个字符的字符串，表示 $\text{MM-DD}$ 。

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

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

更改方式不止一种，其中一种方式是改为： $\text{03-22}$。

【输入输出样例2说明】

一种更改方式为：$\text{02-09}$。

【输入输出样例3说明】

一种更改方式为：$\text{07-09}$。

【数据规模与约定】
对于 $100\%$ 的数据：$\text{MM}$ 与 $\text{DD}$ 一定为 $4$ 个数字。

**update: 2024/07/04 增加 hack 一组**


title: [NOI2001] 陨石的秘密

description:
公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：

```
1 1 1 1 6
0 0 6 3 57
8 0 11 3 2845
```

著名的科学家 SS 发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种 SS 表达式：

1. SS 表达式是仅由 `{`, `}`, `[`, `]`, `(`, `)` 组成的字符串。
2. 一个空串是 SS 表达式。
3. 如果 $ A $ 是SS表达式，且 $ A $ 中不含字符 `{`, `}`, `[`, `]`，则 $ (A) $ 是SS表达式。
4. 如果 $ A $ 是 SS 表达式，且 $ A $ 中不含字符 `{`, `}`，则 $ [A] $ 是 SS 表达式。
5. 如果 $ A $ 是 SS 表达式，则 $ \{A\} $ 是 SS 表达式。
6. 如果 $ A $ 和 $ B $ 都是 SS 表达式，则 $ AB $ 也是 SS 表达式。

一个 SS 表达式 $ E $ 的深度 $ D(E) $定义如下：

$$
\scriptstyle{
D(E) =
\begin{cases}
 \scriptstyle{0}, & \scriptstyle{\text{如果 } E \text{ 是空串}} \\
 \scriptstyle{D(A) + 1}, &  \scriptstyle{\text{如果 } E = (A) \text{ 或者 } E = [A] \text{ 或者 } E = \{A\}, \text{ 其中 } A \text{ 是 SS 表达式}} \\
 \scriptstyle{\max(D(A), D(B))}, &  \scriptstyle{\text{ 如果 } E = AB, \text{其中 } A, B \text{ 是 SS 表达式}}
\end{cases}
}
$$

例如 `(){()}[]` 的深度为 $ 2 $。

密文中的复杂运算是这样进行的：

设密文中每行前 $ 4 $ 个数依次为 $ L_1, L_2, L_3, D $，求出所有深度为 $ D $，含有 $ L_1 $ 对 `{}`，$ L_2 $ 对 `[]`，$ L_3 $ 对 `()` 的 SS 串的个数，并用这个数对当前的年份 $ 11380 $ 求余数，这个余数就是密文中每行的第 $ 5 $ 个数，我们称之为“神秘数”。

密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

inputFormat: 共一行，$ 4 $ 个整数 $ L_1, L_2, L_3, D $。相邻两个数之间用一个空格分隔。

outputFormat: 共一行，包含一个整数，即神秘数。


title: [MtOI2019] 手牵手走向明天

background:
2019 年 5 月 17 日，Ynoi2018 Day 2 的题目上传至洛谷公共题库。

2019 年 5 月 19 日，mrsrz 想出了[[Ynoi2018]天降之物](https://www.luogu.com.cn/problem/P5397)的序列分块做法，并尝试 AC 该题。

2019 年 5 月 21 日，在 lxl 略微放宽时限，加上各种玄学优化下，mrsrz 通过了此题（现在时限改回来了所以没希望了）。

过了若干日，mrsrz 发现该序列分块做法可以支持区间查询，和 lxl 讨论后，发现也可以做到区间修改。

2019 年 10 月，mrsrz 找到 disangan233 并告诉了他这个题。disangan233 收下了这个题并打算作为 MtOI2019 Extra Round 的 F 题。

2019 年 11 月 1 日，mrsrz 发现某个地方的某个比赛的某个题和该题有类似的地方。观察题解后发现了几乎一样的做法。然后这个原来的 F 题没了。

2019 年 11 月 2 日，MtOI2019 Extra Round 顺利进行。

2019 年 11 月 30 日，mrsrz 想起了这道题，决定将这道饱经风霜的题贡献至公共题库中。希望这道题，能对大家有所帮助。

by mrsrz

2019 年 11 月 30 日

### Update：

2019 年 12 月 2 日，经 disangan233 同意，本题仍使用原来的题面。

2021 年 8 月 13 日，更新了 std，现在 std 的空间复杂度为 $O(n+m)$。

---

「俺、セツナは、お前を永遠に愛することちか！」
「我，Setsuna，发誓将会永远爱着你！」

「私の、あなたを永遠に愛することちかう！」
「我也是，发誓会永远爱着你！」

「歴史がかでもまた得た、ウェディングドレスてあみあをそ！」
「要是我们在其他的历史中再次相遇，那就披上婚纱再来一次吧！」

![rinne.png](https://i.loli.net/2019/10/03/oR4tNIQ6rBMe8GU.png)

description:
Rinne 给了你一个数列 $a_1,a_2,\dots,a_n$，你需要依次执行 $m$ 个操作。

操作共有两种：

1. 给定 $l,r,x,y$，将 $a_l,a_{l+1},a_{l+2},\dots,a_r$ 中等于 $x$ 的数全部改成 $y$。

2. 给定 $l,r,x,y$，找到 $i,j$ 满足 $i,j\in[l,r]$ 且 $a_i=x,a_j=y$，并要求 $|i-j|$ 最小。求这个最小值。无解输出 $-1$。

inputFormat:
第一行两个正整数 $n,m$，表示序列长度和操作个数。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行五个正整数 $op,l,r,x,y$。若 $op=1$，表示修改操作。若 $op=2$，表示询问操作。$l,r,x,y$ 对应的含义见题目描述。

outputFormat: 对每个 $op=2$ 的操作，输出一行一个整数表示答案。

hint:
对于 $100\%$ 的数据，$1\leq n,m,a_i,x,y\leq 10^5$，$1\leq l\leq r\leq n$。

本题共有 $6$ 个子任务，每个子任务的限制如下：

子任务 $1$（$1$ 分）：保证对于任意操作，$l=1,r=n$。

子任务 $2$（$5$ 分）：$n,m\leq 50$。

子任务 $3$（$18$ 分）：$n,m\leq 2000$。

子任务 $4$（$7$ 分）：保证 $a_i,x,y\in\{1,2\}$。

子任务 $5$（$29$ 分）：保证当 $op=2$ 时，$x=y$。

子任务 $6$（$40$ 分）：没有特殊限制。

**时间限制**：$1.5\rm s$

**空间限制**：$512\rm MB$

Idea：nzhtl1477，mrsrz

Solution：mrsrz，nzhtl1477

Code：mrsrz

Data：mrsrz

Background：disangan233，mrsrz


title: 【深基9.例1】选举学生会

description: 学校正在选举学生会成员，有 $n$（$n\le 999$）名候选人，每名候选人编号分别从 $1$ 到 $n$，现在收集到了 $m$（$m \le 2000000$）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

inputFormat: 输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

outputFormat: 求出排序后的选票编号。


title: 【深基9.例4】求第 k 小的数

description:
输入 $n$（$1 \le n < 5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1 \le a_i < {10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 `nth_element` 来写本题，因为本题的重点在于练习分治算法。


title: 【深基12.例1】部分背包问题

description: 阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 $N(N \le 100)$ 堆金币，第 $i$ 堆金币的总重量和总价值分别是 $m_i,v_i(1\le m_i,v_i \le 100)$。阿里巴巴有一个承重量为 $T(T \le 1000)$ 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

inputFormat:
第一行两个整数 $N,T$。

接下来 $N$ 行，每行两个整数 $m_i,v_i$。

outputFormat: 一个实数表示答案，输出两位小数


title: 【深基13.例1】查找

description: 输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。

inputFormat:
第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。

第二行 $n$ 个整数，表示这些待查询的数字。

第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。

outputFormat: 输出一行，$m$ 个整数，以空格隔开，表示答案。

hint:
数据保证，$1 \leq n \leq 10^6$，$0 \leq a_i,q \leq 10^9$，$1 \leq m \leq 10^5$

本题输入输出量较大，请使用较快的 IO 方式。


title: 【深基15.例1】询问学号

description: 有 $n(n \le 2 \times 10^6)$ 名同学陆陆续续进入教室。我们知道每名同学的学号（在 $1$ 到 $10^9$ 之间），按进教室的顺序给出。上课了，老师想知道第 $i$ 个进入教室的同学的学号是什么（最先进入教室的同学 $i=1$），询问次数不超过 $10^5$ 次。

inputFormat:
第一行 $2$ 个整数 $n$ 和 $m$，表示学生个数和询问次数。

第二行 $n$ 个整数，表示按顺序进入教室的学号。

第三行 $m$ 个整数，表示询问第几个进入教室的同学。

outputFormat: 输出 $m$ 个整数表示答案，用换行隔开。


title: 【深基15.例2】寄包柜

description:
超市里有 $n(1\le n\le10^5)$ 个寄包柜。每个寄包柜格子数量不一，第 $i$ 个寄包柜有 $a_i(1\le a_i\le10^5)$ 个格子，不过我们并不知道各个 $a_i$ 的值。对于每个寄包柜，格子编号从 1 开始，一直到 $a_i$。现在有 $q(1 \le q\le10^5)$ 次操作：

- `1 i j k`：在第 $i$ 个柜子的第 $j$ 个格子存入物品 $k(0\le k\le 10^9)$。当 $k=0$ 时说明清空该格子。
- `2 i j`：查询第 $i$ 个柜子的第 $j$ 个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 $10^7$ 个寄包格子，$a_i$ 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

inputFormat:
第一行 2 个整数 $n$ 和 $q$，寄包柜个数和询问次数。

接下来 $q$ 个行，每行有若干个整数，表示一次操作。

outputFormat: 对于查询操作时，输出答案，以换行隔开。

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


title: 【深基15.习9】验证栈序列

description: 给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 $n(n\le100000)$。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 `Yes`，否则输出 `No`。为了防止骗分，每个测试点有多组数据，不超过 $5$ 组。

inputFormat:
第一行一个整数 $q$，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

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


title: 【深基16.例1】淘汰赛

description: 有 $2^n$（$n\le7$）个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？

inputFormat:
第一行一个整数 $n$，表示一共 $2^n$ 个国家参赛。

第二行 $2^n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的国家的能力值（$1\leq i \leq 2^n$）。

数据保证不存在平局。

outputFormat: 仅一个整数，表示亚军国家的编号。


title: 【深基16.例3】二叉树深度

description:
有一个 $n(n \le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 $n$），建立一棵二叉树（根节点的编号为 $1$），如果是叶子结点，则输入 `0 0`。

建好这棵二叉树之后，请求出它的深度。二叉树的**深度**是指从根节点到叶子结点时，最多经过了几层。

inputFormat:
第一行一个整数 $n$，表示结点数。

之后 $n$ 行，第 $i$ 行两个整数 $l$、$r$，分别表示结点 $i$ 的左右子结点编号。若 $l=0$ 则表示无左子结点，$r=0$ 同理。

outputFormat: 一个整数，表示最大结点深度。


title: 【深基17.例5】木材仓库

description:
博艾市有一个木材仓库，里面可以存储各种长度的木材，但是保证没有两个木材的长度是相同的。作为仓库负责人，你有时候会进货，有时候会出货，因此需要维护这个库存。有不超过 100000 条的操作：

- 进货，格式`1 Length`：在仓库中放入一根长度为 Length(不超过 $10^9$) 的木材。如果已经有相同长度的木材那么输出`Already Exist`。
- 出货，格式`2 Length`：从仓库中取出长度为 Length 的木材。如果没有刚好长度的木材，取出仓库中存在的和要求长度最接近的木材。如果有多根木材符合要求，取出比较短的一根。输出取出的木材长度。如果仓库是空的，输出`Empty`。


title: 【深基16.例7】普通二叉树（简化版）

description:
您需要写一种数据结构，来维护一些数（都是绝对值 $10^9$ 以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 $q$ 不超过 $10^4$：

1. 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。查询数 $x$ 的排名。**注意 $x$ 不一定在集合里**。
2. 查询排名为 $x(x\ge 1)$ 的数。**保证集合里至少有 $x$ 个数**。
3. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。若不存在则输出 $-2147483647$。
4. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。若不存在则输出 $2147483647$。
5. 插入一个数 $x$，本题的数据保证插入前 $x$ 不在集合中。

保证执行 $1,3,4$ 操作时，集合中有至少一个元素。

inputFormat:
第一行是一个整数 $q$，表示操作次数。

接下来 $q$ 行，每行两个整数 $op,x$，分别表示操作序号以及操作的参数 $x$。

outputFormat: 输出有若干行。对于操作 $1,2,3,4$，输出一个整数，表示该操作的结果。


title: 【深基17.例6】学籍管理

description:
您要设计一个学籍管理系统，最开始学籍数据是空的，然后该系统能够支持下面的操作（不超过 $10^5$ 条）：

- 插入与修改，格式`1 NAME SCORE`：在系统中插入姓名为 NAME(由字母和数字组成不超过 20 个字符的字符串，区分大小写) ，分数为 $\texttt{SCORE}$（$0<\texttt{SCORE}<2^{31}$） 的学生。如果已经有同名的学生则更新这名学生的成绩为 SCORE。如果成功插入或者修改则输出`OK`。
- 查询，格式`2 NAME`：在系统中查询姓名为 NAME 的学生的成绩。如果没能找到这名学生则输出`Not found`，否则输出该生成绩。
- 删除，格式`3 NAME`：在系统中删除姓名为 NAME 的学生信息。如果没能找到这名学生则输出`Not found`，否则输出`Deleted successfully`。
- 汇总，格式`4`：输出系统中学生数量。


title: 【深基18.例3】查找文献

description:
小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$）以及 $m(m\le10^6)$ 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

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

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

inputFormat:
共 $m+1$ 行，第 1 行为 2 个数，$n$ 和 $m$，分别表示一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$）以及$m(m\le10^6)$ 条参考文献引用关系。

接下来 $m$ 行，每行有两个整数 $X,Y$ 表示文章 X 有参考文献 Y。

outputFormat:
共 2 行。
第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。


title: 「SWTR-4」Collecting Coins

background:
小 A 喜欢 Collecting Coins。他还有个好朋友叫做小 c。

小 c 在外出游玩的时候被困在了一个迷宫里面，小 A 得知消息后，立刻放下了自己手中正在打的树套树套树套树，出发去营救她。

description:
经过一番勘察，小 A 发现小 c 被困的迷宫由 $n$ 个房间组成，这些房间用 $n-1$ 扇门连接，**形成了一颗树**。小 c 被困在 $d$ 号房间。

小 A 还发现每扇门上都写有一个数字 $v$，经过该扇门就会获得 $v$ 个金币，但每扇门上的金币只能获得一次。

由于把小 c 困在迷宫里的坏人早已知道小 A 会来救她，所以他们在每个房间里都布下了陷阱，使得第 $i$ 个房间最多可以进入 $k_i$ 次，否则小 A 也会被困在迷宫里。Luckily，小 c 在向小 A 求救的时候，已经将这个陷阱告诉了他。

小 A 在进入迷宫的时候可以任选初始房间 $r$（进入迷宫算一次进入房间 $r$）。**小 A 可以离开迷宫，当且仅当他在房间 $r$。**

如果小 A 进入了 $d$ 号房间，我们就认为他成功地救下了小 c。在救下小 c 后，小 A 还可以带着她继续在迷宫中行动。

虽然小 A 并不是一个非常贪财的人，但还是想知道：在**成功救下小 c** 且离开迷宫的前提下，他最多能获得多少金币。

inputFormat:
第一行，两个整数 $n,d$ —— 表示房间个数和小 c 被困的房间号。

接下来 $n-1$ 行，每行三个整数 $x_i,y_i,v_i$ —— 分别表示第 $i$ 扇门连接的两个房间编号和这扇门上写的数。

接下来一行，$n$ 个整数 $k_1,k_2,\cdots,k_n$ —— 表示每个房间最多可进入的次数。

outputFormat: 一行一个整数，表示小 A 能获得的金币数量的最大值。

hint:
【样例 $1$ 说明】

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

一种最优的走法为：$2\to 4\to 2$，共可获得 $5$ 金币。

【样例 $2$ 说明】

如上图，小 A 只能空降到 $4$ 号房间，然后再离开迷宫，共可获得 $0$ 金币。

【样例 $4$ 说明】

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

一种最优的走法为：$3\to 9\to 10\to 8\to 10\to 12\to 6\to 12\to 10\to 9\to 3$，共可获得 $100+59+65+9+30=263$ 金币。

【数据范围与约定】

**本题使用捆绑测试。**

Subtask 编号 | $n\leq$ | 特殊性质 | 分值 |
:-: | :-: | :-: | :-: |
$1$ | $12$ | $k_i=1$ | $3$ |
$2$ | $12$ | $k_i\leq 3$ | $12$ |
$3$ | $10^3$ | 迷宫为一条链 | $9$ |
$4$ | $10^3$ | 无 | $16$ |
$5$ | $10^5$ | 迷宫为一条链 | $9$ |
$6$ | $10^5$ | 迷宫为一个菊花图 | $16$ |
$7$ | $10^5$ | 无 | $35$ |

对于 $100\%$ 的数据，$1\leq d,k_i\leq n\leq 10^5$，$1\leq v_i\leq 10^4$。

【Source】

[Sweet Round 04](https://www.luogu.com.cn/contest/26414)$\ \ $E

idea & std：[Alex_Wei](https://www.luogu.com.cn/user/123294)，验题：[chenxia25](https://www.luogu.com.cn/user/138400)


title: 【深基2.例12】上学迟到

description:
学校和 yyy 的家之间的距离为 $s$ 米，而 yyy 以 $v$ 米每分钟的速度匀速走向学校。

在上学的路上，yyy 还要额外花费 $10$ 分钟的时间进行垃圾分类。

学校要求必须在上午 $\textrm{8:00}$  到达，请计算在不迟到的前提下，yyy 最晚能什么时候出门。

由于路途遥远，yyy 可能不得不提前一点出发，但是提前的时间不会超过一天。

inputFormat: 一行两个正整数 $s,v$，分别代表路程和速度。

outputFormat:
输出一个 $24$ 小时制下的时间，代表 yyy 最晚的出发时间。

输出格式为 $\texttt{HH:MM}$，分别代表该时间的时和分。必须输出两位，不足前面补 $0$。


title: 【深基4.习9】打分

description: 现在有 $n(n \le 1000)$ 位评委给选手打分，分值从 $0$ 到 $10$。需要去掉一个最高分，去掉一个最低分（如果有多个最高或者最低分，也只需要去掉一个），剩下的评分的平均数就是这位选手的得分。现在输入评委人数和他们的打分，请输出选手的最后得分，精确到 $2$ 位小数。

inputFormat:
第一行输入一个正整数 $n$，表示有 $n$ 个评委。

第二行输入 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个评委打出的分值。

outputFormat: 输出一行一个两位小数，表示选手的最后得分。

hint: 数据保证，$3 \leq n \leq 1000$，每个评委打出的分值为为 $0$ 到 $10$（含 $0$ 与 $10$）之间的整数。


title: EI 的第六分块

background:
他说他解决了经典根号复杂度问题，怕引起轰动所以撤回了.jpg

不过 [EntropyIncreaser](https://www.luogu.com.cn/user/21423) 确实得到了此题更优的做法。

description:
给定一个整数序列 $a$，支持两种操作：

- `1 l r x` 表示给区间 $[l,r]$ 中每个数加上 $x$
- `2 l r` 表示查询区间 $[l,r]$ 的最大子段和（可以为空）

inputFormat:
第一行两个正整数 $n,q$，表示序列长度和操作个数。
接下来一行 $n$ 个整数，表示初始的序列 $a$。
接着有 $q$ 行，每行若干个整数，表示一次操作。

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

hint:
【数据范围】
对于 $20\%$ 的数据，$1\le n,q \le 1000$；
对于 $60\%$ 的数据，$1\le n,q \le 10^5$；
对于 $100\%$ 的数据，$1\le n,q \le 4\times 10^5$，$|a_i| \le 10^9$，$1 \le x \le 10^6$。

Idea：nzhtl1477
Solution：EntropyIncreaser
Code：EntropyIncreaser
Data：NaCly_Fish

### 请注意常数优化。


title: [NOI2001] 反正切函数的应用

background:
反正切函数可展开成无穷级数，有如下公式

$$ \arctan(x) = \sum_{n = 0}^\infty \frac{(-1) ^ n x ^ {2n + 1}}{2n + 1} ( 0 \le x \le 1 ) \tag{1} $$

使用反正切函数计算 是一种常用的方法。例如，最简单的计算 的方法：

$$
\begin{aligned}
\pi & = 4 \arctan(1) \\
    & = 4(1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \frac{1}{11} + \dots)
\end{aligned}
\tag{2}
$$

然而，这种方法的效率很低，但我们可以根据角度和的正切函数公式：

$$ \tan(\alpha + \beta) = \frac{\tan(\alpha) + \tan(\beta)}{1 - \tan(\alpha) \tan(\beta)} \tag{3} $$

通过简单的变换得到：

$$ \arctan(p) + \arctan(q) = \arctan(\frac{p + q}{1 - p q}) \tag{4} $$

利用这个公式，令 $ p = \frac{1}{2}, q = \frac{1}{3} $，则 $ \frac{p + q}{1 - p q} = 1 $，有

$$ \arctan(\frac{1}{2}) + \arctan(\frac{1}{3}) = \arctan(\frac{\frac{1}{2} + \frac{1}{3}}{1 - \frac{1}{2} \cdot \frac{1}{3}}) = \arctan(1) $$

description:
我们将公式 $ 4 $ 写成如下形式

$$ \arctan(\frac{1}{a}) = \arctan(\frac{1}{b}) + \arctan(\frac{1}{c}) $$

其中 $ a, b, c \in \mathbb{N^+} $。

我们的问题是：对于每一个给定的 $a$，求 $ b + c $ 的值。我们保证对于任意的 $ a $ 都存在整数解。如果有多个解，要求你给出 $ b + c $ 最小的解。

inputFormat: 输入文件中只有一个正整数 $ a $。

outputFormat: 输出文件中只有一个整数，为 $ b + c $ 的值。

hint: $1 \le a \le 6\times 10^4 $。


title: [CTSC1998] 算法复杂度

background:
CTSC1998 D1T3

我们在编程时，最关心的一个问题就是算法的时间复杂度。但是分析一个程序的复杂度是一项很困难的工作，在程序的码风不是很好的情况下更是如此。

所以，专门研究算法的 SERKOI 小组决定开发出一个分析程序时间复杂度的软件。由于这是一个全新的领域，所以 SERKOI 小组决定先从简单情况入手进行分析。

description:
为了简化问题,程序只包含循环和顺序结构,程序的结构定义如下：

$\texttt{begin <statement> end}$

一个语句块的结构是**递归定义**的，如下所示：

$\texttt{loop x <statement> end}$

或者 $\texttt{op <statement>}$

或者为 $\texttt{break <statement>}$

或者为 $\texttt{continue <statement>}$

语句块可以为空。

注意：

1. 一个程序都是以 $\texttt{begin}$ 开始，以相应的 $\texttt{end}$ 结束；

2. $\texttt{loop x <statement> end}$ 表示其中的语句重复执行 $x$ 次；

3. $\texttt{op x}$ 表示执行 $x$ 个单位操作；

4. 上面两点中的 $x$ 可以是一个正整数或 $n$；

5. $\texttt{break}$ 语句的作用是跳出这一层循环, $\texttt{continue}$ 语句的作用是跳过这一层循
环的其它语句，直接进入下一次循环。如果它（$\texttt{break}$ 或 $\texttt{continue}$）不在任何一层循环中，**请忽略它们**。

你需要写一个程序，用来求出题目描述的程序的时间复杂度，并以多项式的形式输出。

注意，该多项式是关于 $n$ 的多项式，而且，**常数项和系数不能省略**。

数据保证能求出该程序的时间复杂度。

inputFormat:
输入中包含一个完整的程序，
每两条语句之间至少用一个空格或换行符隔开。

outputFormat: 将计算出的时间复杂度多项式按**降幂排列**输出。

samples:
begin loop n loop 3 loop n
op 20
end end end
loop n op 3 break end
loop n loop n
op 1
break
end end
end

samples:
begin
op n
loop 3
op n
break
end
loop n
loop n
op 1
continue
op n
end
end
end

hint:
循环的嵌套最多不超过 $20$ 层。

保证最终时间复杂度多项式每项的系数不超过 ${10}^9$。


title: [CTSC1998] 监视摄像机

background:
CTSC1998 D1T2

一个著名的仓库管理公司 SERKOI 请你的公司为其安装一套闭路监视系统。

由于 SERKOI 财力有限,每个房间只能安装一台摄像机作监视用，不过它的镜头可以向**任意方向**旋转。

description:
我们的问题是确定摄像机的位置，以确保房间的每一个角落都能被它监视到。

例如，图一和图二是某两个房间的示意图，每个房间用一个封闭的多边形表示。

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

图中的每条边表示一面墙。

对于图一所示的房间，我们将摄像机安置在标黑点的位置就能满足要求；

而对于图二所示的房间，无论将摄像机安置在哪里都无法使其满足要求。

写一个程序，对于给定的房间示意图，判断是否有可能在这个房间中的某一位置安置**一台**摄像机，使其能监视到这个房间的**任何一个**角落。

inputFormat:
输入文件包含一个或多个房间示意图的描述信息。

每个描述信息的第一行是一一个正整数 $n$，表示该房间的示意图为一个 $n$ 边形。

以下 $n$ 行每行包括用空格符隔开的两个整数 $x,y$，依次为这个 $n$ 边形的按顺时针方向排列的 $n$ 个顶点在直角坐标系中的横纵坐标。

$n=0$ 表示输入文件结束。

outputFormat:
对于每个房间，首先输出一行该房间的编号信息 `Room #k:`，$k$ 按照输入次序从 $1$ 开始计数。

下一行是判断结果，如果摄像机在房间中某处安置能满足条件，输出 `Surveillance is possible.`，否则输出 `Surveillance is impossible.`

每两个房间的输出结果之间用一个空行隔开。

samples:
Room #1:
Surveillance is possible.

Room #2:
Surveillance is impossible.

hint:
【数据范围】

$4 \leq n \leq 100$，$-1000 \leq x,y \leq 1000$。


title: [CTSC1998] 罗杰游戏

background: CTSC1998 D2T1

description:
罗杰游戏由一张棋盘和罗杰构成。棋盘由很多个小格组成，每个小格上刻有一个数字。其为 $-1$ 或 $0$ 至 $255$ 之间的一个数。罗杰是一个立方体，有六个面，每个面上分别有一个 $1$ 至 $6$ 之间的数字。

我们开始时把罗杰放在棋盘中的一个小格上，然后让其向前、后、左、右四个方向**翻滚**至邻近小格中。

游戏要求经过若干次翻滚后，让罗杰到达指定小格。

**罗杰不得进入标有 $-1$ 的小格，否则游戏结束**。

罗杰每进入一个小格后，将其顶面的数字同该小格的数字相乘，所得结果累加即得到罗杰的旅行费用。

开始时我们能看到罗杰的某些面上的数字，也可以指定当罗杰最终到达目的格时某些面上应出现的数字。对于**不确定的数字**，我们可以在**合法的基础上任意指定**。

**任务一**

罗杰只能向前或向右翻滚。

**任务二**

罗杰可以自由活动。

inputFormat:
输入文件的第一行是数字 $1$ 或 $2$ 。表示是任务一还是任务二。

文件的第二行是两个整数 $M$ 和 $N$ ，给出了棋盘的列数和行数。

接下来的 $N$ 行每行表示棋盘的一行，有 $M$ 个数，依次给出了该行上每列的数。

其后的两行分别给出了罗杰的出发点信息和到达点信息。

每行开始的两个正整数给出了该格子的列号和行号。

接下来的六个数字分别表示了罗杰的顶，底，前、后、左、右各面的数字。 $0$ 表示可以任意指定。

outputFormat:
输出文件的第一行给出罗杰的最小旅行费用。

如果罗杰不可能按要求到达目的地，则输出 $-1$ 。

否则其后每行给出罗杰的旅行情况：

从出发格到目的格，每行表示了罗杰的一个位置，

依次给出罗杰的当前旅行费用、所在格的列编号、行编号，以及罗杰6个面上的数字。

注意这时你的程序必须给出罗杰的完整信息，即各面上的数字不能为 $0$。

hint:
【数据范围】

$M \le 40$ , $N \le 40$  。


title: [NOI2008] 赛程安排

description:
随着奥运的来临，同学们对体育的热情日益高涨。在 NOI2008 来临之际，学校正在策划组织一场乒乓球赛。小 Z 作为一名狂热的乒乓球爱好者，这正是他大展身手的好机会，于是他摩拳擦掌，积极报名参赛。

本次乒乓球赛采取淘汰赛制，获胜者晋级。恰好有 $n$($n$ 是 $2$ 的整数次幂，不妨设 $n = 2^k$)个同学报名参加，因此第一轮后就会有 $2^{k-1}$ 个同学惨遭淘汰，另外 $2^{k-1}$ 个同学晋级下一轮；第二轮后有 $2^{k-2}$ 名同学晋级下一轮，… 依次类推，直到 $k$ 轮后决出冠亚军：具体的，每个人都有一个 $1\sim n$ 的初始编号，其中小 Z 编号为 $1$，所有同学的编号都不同，他们将被分配到 $n$ 个位置中，然后按照类似下图的赛程进行比赛：

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

上图：$n=8$ 时比赛的赛程表

为了吸引更多的同学参加比赛，本次比赛的奖金非常丰厚。在第 $i$ 轮被淘汰的选手将得到奖金 $a_i$ 元，而冠军将获得最高奖金 $a_{k+1}$ 元。显然奖金应满足 $a_1<a_2<\cdots<a_{k+1}$。

在正式比赛前的热身赛中，小 Z 连连败北。经过认真分析之后，他发现主要的失败原因不是他的球技问题，而是赢他的这几个同学在球风上刚好对他构成相克的关系，所以一经交手，他自然败阵。小 Z 思索：如果在正式比赛中能够避开这几位同学，该有多好啊!

假设已知选手两两之间交手的胜率，即选手 $A$ 战胜选手 $B$ 的概率为 $P_{A,B}$ (保证 $P_{A,B}+P_{B,A}=1$)。于是小 Z 希望能够通过确定比赛的对阵形势（重新给每个选手安排位置），从而能够使得他获得尽可能多的奖金。你能帮助小 Z 安排一个方案，使得他这场比赛期望获得的奖金最高么？

inputFormat:
这是一道提交答案型试题，所有的输入文件 `match*.in` 已在附加文件中。

输入文件 `match*.in` 第一行包含一个正整数 $n$，表示参赛的总人数，数据保证存在非负整数 $k$，满足 $2^k=n$。

接下来 $n$ 行，每行有 $n$ 个 $0$ 到 $1$ 间的实数 $P_{i,j}$，表示编号为 $i$ 的选手战胜编号为 $j$ 的选手的概率，每个实数精确到小数点后两位。特别注意 $P_{i,i}=0.00$。

接下来 $k+1$ 行，每行一个整数分别为晋级各轮不同的奖金，第 $i$ 行的数为 $a_i$。

outputFormat: 输出文件 `match*.out` 包括 $n$ 行，第 $i$ 行的数表示位于第 $i$ 个位置的同学的编号，要求小 Z 的编号一定位于第 $1$ 个位置。

hint:
#### 样例解释

第一轮比赛过后，编号为 $1$ 的选手(小 Z)晋级的概率为 $80\%$，编号为 $2$ 的选手晋级的概率为 $60\%$，编号为 $3$ 的选手晋级的概率为 $40\%$，编号为 $4$ 的选手晋级的概率为 $20\%$。

第二轮（决赛），编号为 $1$ 的选手（小 Z）前两轮均获胜的概率为 $80\%\times (60\%\times 70\%+40\%\times 60\%)=52.8\%$，因此，小 Z 在第一轮失败的概率 $P_1=1-0.8=0.2$，第一轮胜出但第二轮败北的概率 $P_2=0.8-0.528=0.272$，获得冠军的概率 $P_3=0.528$。

从而，期望奖金为 $0.2\times 1+(0.8-0.528)\times 2+0.528\times 3=2.328$。

#### 如何测试你的输出

我们提供 `checker` 来测试你的输出文件是否可接受。

调用这个程序后，`checker` 将根据你得到的输出文件给出测试的结果，其中包括：
- 非法退出：未知错误；
- `Format error`：输出文件格式错误；
- `Not a permutation`：输出文件不是一个 $1\sim n$ 的排列；
- `OK.Your answer is xxx`：输出文件可以被接受，`xxx`为对应的期望奖金。

#### 评分方法

每个测试点单独评分。

对于每一个测试点，如果你的输出文件不合法，如文件格式错误、输出解不符合要求等，该测试点得 $0$ 分。否则如果你的输出的期望奖金为 $\text{your\_ans}$，参考期望奖金为 $\text{our\_ans}$，我们还设有一个用于评分的参数 $d$，你在该测试点中的得分如下：

- 如果 $\text{your\_ans}>\text{our\_ans}$，得 $12$ 分。
- 如果 $\text{your\_ans}<\text{our\_ans}\times d$，得 $1$ 分。
- 否则得分为：
  $$
  \left\lfloor\frac{\text{your\_ans}-\text{our\_ans}\times d}{\text{our\_ans}-\text{our\_ans}\times d}\times 8\right\rfloor+2
  $$

#### 特别提示

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

#### 附加文件

checker 需要自行编译后使用。

请前往 [Github](https://github.com/MikeMirzayanov/testlib) 下载 testlib.h 的最新源代码。


title: [CTSC1998] 站牌位置

background: CTSC1998 D2T2

description:
某城市市区规划成网格状，市区由 $n+1$ 条南北走向和 $n+1$ 条东西走向的干道将其平均分为 $n^2$ 个区域， $(n+1)^2$ 个叉路口。区域及叉路口均**由上至下，由左至右**编号。

现在要在城市中划分出若干区域作为游览胜地，每一个游览胜地将会有且仅有一路公共汽车围绕它的四周运行，这路公共汽车将仅在该区域四周的四个叉路口设立四个公共汽车车站。相邻的两个区域（两个区域相邻当且仅当它们有一段公共的公路）将会共用两个公共汽车车站。

政府为每一个公共汽车车站设立一个站牌，站牌号用自然数 $1$ , $2$ ...表示且互不相同，可没想到站牌号的设置令政府大伤脑筋。原来，该城市有三个公交公司，他们有各自的规定，即：

1. 甲公司的一路公共汽车绕某一个区域运行的四个站，应该满足下面条件：从某一个站出发，**顺时针方向**经过的三个站牌牌号**单调递减**，最后回到原来的那个站。

2. 乙公司的一路公共汽车绕某一个区域运行的四个站，应该满足下面条件：从某一个站出发，**逆时针方向**经过的三个站牌牌号**单调递减**，最后回到原来的那个站。

3. 丙公司的一路公共汽车绕某个区域运行的四个站，应该满足下面条件：从某一个站出发，顺时针方向经过的三个站应是站牌号依次**先减少，再增加，再减少，最后再增加**，然后回到原来的那个站。

为公平起见，政府希望找出一个安排站牌的方法，对这 $n$ 个区域所涉及的所有的 $K$ 个站分配站牌。使三个公司能在游览胜地中开辟尽量一样多的公共汽车路线。请你编程解决上述问题。

设三个公司可开辟的公共汽车路线数分别为 $X$ , $Y$ , $Z$ ,

**你应使$S=(X-Y)^2+(Y-Z)^2+(Z-X)^2$最小**。

inputFormat: 输入文件的第一行为 $n$，第二行为 $m$，表示有 $m$ 个区域为游览胜地，第三行的 $m$ 个数分别为这 $m$ 个区域的编号，相邻的两数之间用一个空格隔开。

outputFormat: 输出文件的第一行为你所找到的 $S$ 值，第二行为 $K$ ，以下的 $K$ 行每行各有两个数，第一个数为叉路口号，第二个数为你安排该叉路口的公共汽车站牌号（站牌号应为由 $1$ 到 $K$ 的自然数，且各不相同），这 $K$ 行应按叉路口号从小到大输出。

hint:
【数据范围】

$1 \leq n \leq 7$


title: 集合划分计数

description:
一个有 $n$ 个元素的集合，将其分为任意个非空子集，求方案数。
注意划分出的集合间是无序的，即 $\{\{1,2\},\{3\}\}$ 和 $\{\{3\},\{2,1\}\}$ 算作一种方案。

由于答案可能会很大，所以要对 $998244353$ 取模。

inputFormat:
第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个正整数 $n$。

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


title: 「SWTR-4」Lining up

background: 作为班长的小 S 在指挥操场上的一群同学排队，Lining up 可不是一件容易的事情。

description:
操场上有排成一列的 $n$ 个同学，每个同学要么是男生，用 ```B``` 表示；要么是女生，用 ```G``` 表示。

我们定义两个相邻的同学的满意度如下：

- 如果两个相邻的同学的性别相同，那么就会像普通同学一样聊天，产生 $0$ 点满意度。

- 如果前面的同学是男生，后面的同学是女生，那么就不会有任何事件发生。同学们都很活跃，他们不希望这么无聊，产生 $-b$ 点满意度。

- 如果前面的同学是女生，后面的同学是男生，那么他们就会聊得很开心，产生 $a$ 点满意度。

由于小 S 是近视眼，所以他无法分辨有些同学的性别，用 ```?``` 表示。

为了提高自己在大家心目中的地位，小 S 想保证所有相邻同学的满意度之和不小于 $m$。

他想知道满足“所有相邻同学的满意度之和不小于 $m$”的概率是多少，对 $10^9+7$ 取模。

inputFormat:
第一行，四个整数 $n,m,a,b$ —— 意义见题目描述。

第二行，一个长度为 $n$ 的字符串 $s$ 表示队列 —— 第 $i$ 个字符表示**从前往后**数第 $i$ 位同学。

outputFormat: 一行，表示概率。

hint:
【样例 $1$ 说明】

共有 $1$ 个满足题意的队形 $\tt BGB$。概率为 $\frac{1}{2} \bmod (10^9+7)=500000004$。

【样例 $2$ 说明】

共有 $6$ 个满足题意的队形 $\tt BBB,BGB,GBB,GBG,GGB,GGG$。概率为 $\frac{6}{8} \bmod (10^9+7)=750000006$。

【样例 $5$ 说明】

真实答案为 $\dfrac{29}{64}$。

【数据范围与约定】

**本题使用捆绑测试。**

Subtask 编号 | $n\leq$ | 特殊性质 | 分数
:-: | :-: | :-: | :-:
$1$ | $2020$ | 没有```?``` | $8$
$2$ | $20$ | 无 | $17$
$3$ | $250$ | 无 | $29$
$4$ | $2020$ | $a=1,b=1$ | $10$
$5$ | $2020$ | 无 | $36$

对于全部数据，$2 \leq n \leq 2020$，$1 \leq |m| \leq 10^{12}$，$1 \leq a,b \leq 10^9$，$s_i \in \tt{\{B,G,?\}}$。

**请注意特殊的空间限制。**

【Tips】

如果你不会对分数取模，可以看看[这里](https://www.luogu.com.cn/problem/P2613)。

【Source】

[Sweet Round 04](https://www.luogu.com.cn/contest/26414)$\ \ $D

idea：[ET2006](https://www.luogu.com.cn/user/115194)，std：[Isaunoya](https://www.luogu.com.cn/user/96580)，验题：[Isaunoya](https://www.luogu.com.cn/user/96580) & [FrenkiedeJong21](https://www.luogu.com.cn/user/203968) & [chenxia25](https://www.luogu.com.cn/user/138400)


title: [NOI2002] 机器人M号

description:
3030 年，Macsy 正在火星部署一批机器人。

第 $1$ 秒，他把机器人 $1$ 号运到了火星，机器人 $1$ 号可以制造其他的机器人。

第 $2$ 秒，机器人 $1$ 号造出了第一个机器人——机器人 $2$ 号。

第 $3$ 秒，机器人 $1$ 号造出了另一个机器人——机器人 $3$ 号。

之后每一秒，机器人 $1$ 号都可以造出一个新的机器人。第 $m$ 秒造出的机器人编号为 $m$。我们可以称它为机器人 $m$ 号，或者 $m$ 号机器人。

机器人造出来后，马上开始工作。$m$ 号机器人，每 $m$ 秒会休息一次。比如 $3$ 号机器人，会在第 $6$，$9$，$12$，$\ldots$ 秒休息，而其它时间都在工作。

机器人休息时，它的记忆将会被移植到当时出生的机器人的脑中。比如 $6$ 号机器人出生时，$2$，$3$ 号机器人正在休息，因此，$6$ 号机器人会收到第 $2$，$3$ 号机器人的记忆副本。我们称第 $2$，$3$ 号机器人是 $6$ 号机器人的老师。

如果两个机器人没有师徒关系，且没有共同的老师，则称这两个机器人的知识是互相独立的。**注意：$1$ 号机器人与其他所有机器人的知识独立（因为只有 $1$ 号才会造机器人），它也不是任何机器人的老师。**

一个机器人的**独立数**，是指所有编号比它小且与它知识互相独立的机器人的个数。比如 $1$ 号机器人的独立数为 $0$，$2$ 号机器人的独立数为 $1$（$1$ 号机器人与它知识互相独立），$6$ 号机器人的独立数为 $2$（$1$，$5$ 号机器人与它知识互相独立，$2$，$3$ 号机器人都是它的老师，而 $4$ 号机器人与它有共同的老师——$2$ 号机器人）。

新造出来的机器人有 $3$ 种不同的职业。对于编号为 $m$ 的机器人，如果能把 $m$ 分解成偶数个不同奇素数的积，则它是政客，例如编号 $15$；否则，如果 $m$ 本身就是奇素数或者能把 $m$ 分解成奇数个不同奇素数的积，则它是军人，例如编号 $3$，编号 $165$。其它编号的机器人都是学者，例如编号 $2$, 编号 $6$, 编号 $9$。

第 $m$ 秒诞生的机器人 $m$ 号，想知道它和它的老师中，所有政客的独立数之和，所有军人的独立数之和，以及所有学者的独立数之和。可机器人 $m$ 号忙于工作没时间计算，你能够帮助它吗？

为了方便你的计算，Macsy 已经帮你做了 $m$ 的素因子分解。为了输出方便，只要求输出总和除以 $10000$ 的余数。

inputFormat:
输入的第一行是一个正整数 $k$，$k$ 是 $m$ 的不同的素因子个数。

以下 $k$ 行，每行两个整数，$p_i$, $e_i$,表示 $m$ 的第 $i$ 个素因子和它的指数 $(i=1,2,\ldots,k)$。$p_1,p_2,\ldots,p_k$ 是不同的素数，$\prod_{i=1}^kp_i^{e_i}$。所有素因子按照从小到大排列，即 $p_1<p_2<\ldots<p_k$。

outputFormat:
输出包括三行。

- 第一行是机器人 $m$ 号和它的老师中，所有政客的独立数之和除以 $10000$ 的余数。
- 第二行是机器人 $m$ 号和它的老师中，所有军人的独立数之和除以 $10000$ 的余数。
- 第三行是机器人 $m$ 号和它的老师中，所有学者的独立数之和除以 $10000$ 的余数。

hint:
#### 样例解释
$m = 2\times 3^2\times 5=90$。$90$ 号机器人有 $10$ 个老师，加上它自己共 $11$ 个。其中政客只有 $15$ 号；军人有 $3$ 号和 $5$ 号；学者有 $8$ 个，它们的编号分别是：$2,6,9,10,18,30,45,90$。

#### 数据范围
对于全部的数据，$1\le k\le 1000$，$2\le p_i<10,000$，$1\le e_i\le 1,000,000$。

#### 评分规则

你在一个测试点的得分与你正确解决的问题数 $x$ 有关。

请注意：**对每一行，即使不会解决该问题，也请在该行输出一个数字，否则 checker 将无法正确评分。**

| $x$  | 得分 |
| :--: | :--: |
|  3   |  10  |
|  2   |  7   |
|  1   |  4   |
|  0   |  0   |


title: [NOI2004] 曼哈顿

description:
P 城是 M 国的著名旅游城市。在市长 G 先生的治理下，人民安居乐业，城市欣欣向荣。然而，G 市长并没有被自己的政绩冲昏头脑，他清醒地意识到城市的治理还存在着一些问题，其中之一就是交通问题。

P 城有 $m$ 条横向街道和 $n$ 条纵向街道，横向街道横贯东西，纵向街道纵穿南北，构成了 P 城整齐的交通网络（如图1所示）。

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

由于街道狭窄，每条街道都只允许单向行驶，单向行驶的方向是事先设定好了的。一条横向街道的行驶方向只能是向东或者向西，一条纵向街道的行驶方向只能是向南或者向北，逆向行驶是绝对禁止的。

这项限制给交通带来了巨大的不便。如图 1，很多游人希望从宾馆前往购物中心，但限于街道的行驶方向，他们不得不绕一个大圈才能够到达。

这个问题一直困扰着 G 市长，每天他都会收到不少游人的来信，抱怨P城不合理的交通设计。但由于街道数目过多，他和他的部下始终不能解决这个问题……

令人高兴的是这个问题不久就可能得以解决。因为最近他们以重金聘请了著名的交通规划大师 B 先生，请他对 P 城的交通进行有效合理的改造。

B 先生知道不能通过拓宽街道的方法解决问题，因为这样势必影响到街道两旁的旅游景点，这是大家都不希望看到的。于是他准备重新设计街道的行驶方向（整条街道的行驶方向），使之尽可能满足大家的要求。

B 先生先把 P 城的街道编号，横向街道由北向南编号为 $1$，$2$，$\ldots$，$m$，纵向街道由西向东编号为 $1$，$2$，$\ldots$，$n$。这样任何一个十字路口的位置都可以用一对正整数来表示，第一个数是该路口所在的横向街道的编号，第二个数是它所在的纵向街道的编号，这对整数被称为该十字路口的坐标。比如图 1 中宾馆所在的十字路口的坐标是 $(2,3)$。
经过长期调查，他整理出了游人们提得相对集中的一些要求。每条要求都可以写成如下的形式：从一个十字路口到另一个十字路口的最短路径的长度必须等于它们之间的曼哈顿距离。所谓曼哈顿距离是指两个十字路口在东西方向上的距离加上在南北方向上的距离，坐标分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的两个十字路口之间的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$。

好了，B 先生已经知道了 P 城目前所有街道的行驶方向和游人们提得相对集中的要求，他能不能重新设计街道的行驶方向，使之满足所有要求呢？

另外，改变每条街道的行驶方向都有一定的工作量，工作量的大小因道路而异。B 先生不仅想找到一个可行的改造计划，而且还希望这个计划的总工作量尽可能小。你能帮帮他吗？

inputFormat:
输入文件的第一行有两个正整数 $m$ 和 $n$，分别表示横向街道和纵向街道的数目。

第二行是一个长度为 $m$ 的字符串，由北向南列出了 $m$ 条横向街道改造前的行驶方向。`E` 表示向东，`W` 表示向西。

第三行是一个长度为 $n$ 的字符串，由西向东列出了 $n$ 条纵向街道改造前的行驶方向。`S` 表示向南，`N` 表示向北。

第四行有 $m$ 个非负整数，由北向南列出了改变每条横向街道的行驶方向的工作量。

第五行有 $n$ 个非负整数，由西向东列出了改变每条纵向街道的行驶方向的工作量。

第六行是一个正整数 $k$，表示游人们提得相对集中的要求的数目。

接下来的 $k$ 行，每行有四个正整数 $x_1$，$y_1$，$x_2$，$y_2$，表示一条要求。这条要求的内容是希望从坐标为 $(x_1,y_1)$ 的十字路口到坐标为 $(x_2,y_2)$ 的十字路口的最短路径的长度等于这两个路口之间的曼哈顿距离。

outputFormat:
第一行是一个字符串，`possible` 或者 `impossible`。输出 `possible` 表示可以通过改变街道的行驶方向满足输入数据中的所有要求，输出 `impossible` 表示无论怎么设计都不可能满足输入数据中的所有要求。

如果在第一行输出的是 `possible` 的话，在第二行输出一个整数，表示最小的总工作量，在第三行输出一个长度为 $m$ 的字符串，由北向南列出改造后的 $m$ 条横向街道的行驶方向，`E` 表示向东，`W` 表示向西，在第四行输出一个长度为 $n$ 的字符串，由西向东列出改造后的 $n$ 条纵向街道的行驶方向，`S` 表示向南，`N` 表示向北。

hint:
#### 数据范围
对于全部的数据，$m\le 10$，$n\le 100$，$k\le 100$；改变一条街道的行驶方向的工作量不超过 $10000$。

#### 评分方式
- 如果你的输出文件的第一行是 `impossible`，
  - 如果确实无解，则该测试点满分。
  - 如果实际有解，则该测试点 $0$ 分。
- 如果你的输出文件的第一行是 `possible`，
  - 如果你的程序输出的方案不可行，则该测试点 $0$ 分。
  - 如果你的程序输出的总工作量与实际总工作量不一致，则该测试点 $0$ 分。
  - 如果你的程序输出的方案可行，但总工作量不是最小的，则该测试点 $4$ 分。
  - 如果你的程序输出的方案可行，且总工作量最小，则该测试点满分。


title: 【化学】实验

background:
小 Z 紧张地坐在了一张化学实验桌前，进行着化学实验。

教室里又传来了一阵哀叹声：

我…我好像又错了…我能再试一次吗?

description:
在她的面前，摆放着 $n$ 个试管。试管里装着不明液体。对于每种不明液体，有 $2$ 个已知的化学属性：$a$ 和 $b$。第 $i$ 种液体的两个属性值分别为 $a_i$ 和 $b_i$。

现在，老师给她布置了 $m$ 个实验。

对于每一次实验，有一个参照量 $x$（第 $i$ 次实验的参照量记作 $x_i$）。她需要把不明液体分成尽可能多的组，且满足：任意两种不同组的液体$i$和$j$， $\operatorname{gcsd(a_i,a_j)}$ 都不能大于 $x^2$。

其中 $\operatorname{gcsd}$ 代表他们的最大公约平方数。$k$是两个数的公约平方数，当且仅当满足以下两个条件：

- $k$ 为这两个数的公约数；

- $k$ 为完全平方数。

而最大公约平方数 $\operatorname{gcsd}$ 为所有满足条件的 $k$ 中的最大者。

形象的说， $\operatorname{gcsd}$ 可以理解成两个数的最大公约数的算术平方根的整数因式部分的平方。

例如：

求 $\operatorname{gcsd(24,64)}$，就是先求出 $24,64$ 的最大公约数，是 $8$ ，然后 $\sqrt 8=2\sqrt 2$，其整数因式是 $2$，所以 $\operatorname{gcsd(24,64)}=2^2=4$。

她还需要在分组数最多的情况下，使自己的实验得分最大。

实验得分的定义：对于每一种试剂，定义其得分 $c_i$ 为 $b_i$ 分解质因数之后最大的**指数**。

例如：$b_i=12=2^2\times 3^1$，$c_i=\max\{2,1\}=2$。

$b_i=90=2^1\times 3^2\times 5^1$，$c_i=\max\{1,2,1\}=2$。

而实验得分即为所有组内的 $c_i$ 的最大值之和。

当然，她的 $IQ$ 并不高，所以需要请求你的帮助。

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

第二行 $n$ 个整数 $a_{1\dots n}$。

第三行 $n$ 个整数 $b_{1\dots n}$。

第四行 $m$ 个整数 $x_{1\dots m}$。

outputFormat: 共 $m$ 行，对于第 $i$ 行，输出 $2$ 个整数：第 $i$ 次试验的组数和实验得分。


title: 十二重计数法

background:
组合数学是一门古老而迷人的学科。

传说早在 $114514$ 年前，一位名为忆哀的神灵来到地球，发现了人类——另一种有智慧的物种。

她觉得这很有趣，为了加速人类文明的发展，她向人间传下了一类计数问题——十二重计数，这也正是组合数学的开端。

而只有搞明白这类问题，才能在组合数学上继续深入。

description:
有 $n$ 个球和 $m$ 个盒子，要全部装进盒子里。
还有一些限制条件，那么有多少种方法放球？（与放的先后顺序无关）

限制条件分别如下：

$\text{I}$：球之间互不相同，盒子之间互不相同。
$\text{II}$：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
$\text{III}$：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。

$\text{IV}$：球之间互不相同，盒子全部相同。
$\text{V}$：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
$\text{VI}$：球之间互不相同，盒子全部相同，每个盒子至少装一个球。

$\text{VII}$：球全部相同，盒子之间互不相同。
$\text{VIII}$：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
$\text{IX}$：球全部相同，盒子之间互不相同，每个盒子至少装一个球。

$\text{X}$：球全部相同，盒子全部相同。
$\text{XI}$：球全部相同，盒子全部相同，每个盒子至多装一个球。
$\text{XII}$：球全部相同，盒子全部相同，每个盒子至少装一个球。

由于答案可能很大，所以要对 $998244353$ 取模。

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

outputFormat: 输出十二行，每行一个整数，对应每一种限制条件的答案。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n,m \le 2\times 10^5$。

orz $\mathsf E \color{red}\mathsf{ntropyIncreaser}$


title: [CSGRound3] 斗牛

background:
又是一年过去了。小 Z 在春节期间可以好好的放松放松，于是小 Z 和小伙伴们玩起了牛哄哄（斗牛）。

游戏规则是这样的：

给定 $5$ 张牌，分别从 $1 \sim 10$。你需要挑选其中的三张牌加起来是 $10$ 的倍数，另外两张牌的和的个位数则为你最后获得的点数，特别的，如果这两张牌的和是 $10$ 的倍数，则点数为 $10$，也叫做牛哄哄。如果不能构成 $10$ 的倍数，则点数为 $0$，也叫做牛不拢。

如 $5$ $3$ $2$ $3$ $4$ 的点数是 $7$，又叫做牛七。

小 Z 觉得玩的不过瘾，于是对上述规则进行了一些改变。

description:
给定 $n$ 张牌，牌的大小为 $1 \sim 10$。你需要挑选其中的 $n-2$ 张牌加起来是 $10$ 的倍数，另外两张牌和的个位数即为你所获得的点数。特别地，如果这两张牌的和是 $10$ 的倍数，则点数为 $10$，也叫做牛哄哄。如果任意 $n-2$ 张牌不能构成 $10$ 的倍数，则点数为 $0$，也叫做牛不拢。

由于小 Z 想要更开心的玩耍，所以需要你来完成这个程序来帮助小 Z 在 $1$ 秒内知道点数。

inputFormat:
第一行一个整数 $n$，表示一共有 $n$ 张牌。

第二行 $n$ 个整数，表示这 $n$ 张牌的大小。

outputFormat: 一行一个整数，表示这局牌的点数，点数的范围是 $0 \sim 10$。

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

$10$ $10$ $10$ 三张牌凑成 $10$ 的倍数，$2+3=5$。

**【样例 2 解释】**

任意三张牌都不能凑成 $10$ 的倍数。

---

**【数据范围】**

**本题采用捆绑测试。**

- Subtask 1（50 points）：$n = 5$。
- Subtask 2（30 points）：$n \le 5 \times 10^3$。
- Subtask 3（20 points）：无特殊限制。

对于 $100\%$ 的数据，$5 \le n \le 10^6$。


title: [NOI1999] 钉子和小球

description:
有一个三角形木板,竖直立放，上面钉着 $ \frac{ n (n+1) } { 2 } $ 颗钉子，还有 ($n+1$) 个格子 （当 $n=5$ 时如图 1 ） 。每颗钉子和周围的钉子的距离都等于 $d$ ，每个格子的宽度也都等于 $d$ ，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。

让一个直径略小于 $d$ 的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边 （概率各 $1/2$ ） ，且球的中心还会正对着下一颗将要碰上的钉子。例如图2 就是小球一条可能的路径。

我们知道小球落在第 $i$ 个格子中的概率 $p_i$ = $ \frac{C_n^i}{2^n}$ = $ \frac{ n! }{ 2^n i! (n-i)! } $ ，其中 $i$ 为格子的编号，从左至右依次为 $ 0 , 1 , ... , n $.

现在的问题是计算拔掉某些钉子后，小球落在编号为 $m$ 的格子中的概率 $p_m$ 。假定最下面一排钉子不会被拔掉。例如图3 是某些钉子被拔掉后小球一条可能的路径。

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

 图1  $\qquad$$\qquad$ $\quad$$\quad$  图2    $\quad$$\qquad$ $\qquad$$\quad$                       图3

inputFormat: 第1行为整数 $n$ （$ 2 \leq n \leq  50 $）和 $m$ （ $ 0 \leq m \leq n $ ）。以下 $n$ 行依次为木板上从上至下$n$行钉子的信息，每行中 ‘*’ 表示钉子还在， ‘.’ 表示钉子被拔去，注意在这 $n$ 行中空格符可能出现在任何位置。

outputFormat:
仅一行，是一个既约分数( $0$ 写成 $0/1$ ) ，为小球落在编号为 $m$ 的格子中的概率 $p_m$ 。

既约分数的定义： $A/B$ 是既约分数，当且仅当 $A$ 、 $B$ 为正整数且 $A$ 和 $B$ 没有大于$1$的公因子。


title: [NOI1999] 01串

description:
给定 $7$ 个整数 $N , A_0 , B_0 , L_0 , A_1 , B_1 , L_1 $，要求设计一个01串$ S=s_1 s_2 … s_i … s_N $，满足：
1.	$ s_i = 0 $ 或 $ s_i = 1 $， $ 1 \leq i \leq N $；
2.	对于 $S$ 的任何连续的长度为 $L_0$ 的子串 $s_j s_{j+1} … s_{j+L0-1}  $ ($1 \leq j \leq N-L_0+1 $) ， $0$ 的个数大于等于 $A_0$ 且小于等于 $B_0$ ;
3.	对于 $S$ 的任何连续的长度为 $L_1$ 的子串 $s_j s_{j+1} …  s_{j+L1-1} $ ($ 1 \leq  j  \leq N-L_1+1 $) ， $1$ 的个数大于等于 $A_1$ 且小于等于 $B_1$ ;

例如， $ N = 6 ,  A_0 = 1 ,  B_0 = 2  ,  L_0 = 3 ,  A_1 = 1 ,  B_1 = 1 ,  L_1 = 2 $，则存在一个满足上述所有条件的 $01$ 串 $ S = 010101 $ 。

inputFormat: 仅一行，有 $7$ 个整数，依次表示 $N , A_0 , B_0 , L_0 , A_1 , B_1 , L_1 $ （$3 \leq N \leq 1000$，$1 \leq  A_0 \leq B_0 \leq L_0 \leq N$，$1 \leq A_1 \leq B_1 \leq L_1 \leq N$），相邻两个整数之间用一个空格分隔。

outputFormat: 仅一行，若不存在满足所有条件的 $01$ 串，则输出一个整数 `-1`，否则输出满足所有条件的 $01$ 串中 $1$ 的个数的最大值。


title: [NOI1999] 棋盘分割

description:
将一个 8 $\times$ 8 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了 $(n-1)$ 次后，连同最后剩下的矩形棋盘共有 $n$ 块矩形棋盘。 (每次切割都只能沿着棋盘格子的边进行)

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

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 $n$ 块矩形棋盘，并使各矩形棋盘总分的均方差最小。

均方差 $\sigma = \sqrt{ \frac{ \sum_{i=1}^n (x_i - \bar x)^2 } { n }}$                ，其中平均值 $\bar x = \frac{\sum_{i=1}^n x_i}{n}$ ,  $x_i$ 为第 $i$ 块矩形棋盘的分。

请编程对给出的棋盘及 $n$ ，求出 $\sigma$ 的最小值。

inputFormat:
第一行为一个整数 $n$ ($ 1 < n< 15 $)。

第二行至第九行每行为 $8$ 个小于 $100$ 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

outputFormat: 仅一个数，为 $\sigma$ （四舍五入精确到小数点后三位）。


title: [NOI1997] 最优乘车

description:
H 城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。

一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。

现在用整数 $1 , 2 , … , N$ 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 $1$，S 公园巴士站的编号为 $N$。

写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换车的次数最少。

inputFormat:
第一行有两个数字 $M$ 和 $N$（$ 1 \le M \le 100$，$ 1 < N \le 500 $），表示开通了 $M$ 条单程巴士线路，总共有 $N$ 个车站。

从第二行到第 $M$ 行依次给出了第 $1$ 条到第 $M$ 条巴士线路的信息。其中第 $i+1$ 行给出的是第 $i$ 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。

outputFormat:
只有一行。如果无法乘巴士从饭店到达 S公园，则输出 `NO` ；

否则输出你的程序所找到的最少换车次数，换车次数为 $0$ 表示不需换车即可到达。


title: [NOI2000] 瓷片项链

description:
原始部落用一种稀有的泥土烧制直径相同的圆瓷片并串成项链，串的时候沿瓷片的直径方向顺次连接，瓷片之间没有空隙也不重叠，一条项链至少由一个瓷片构成。

下图示出四片同样大小的瓷片串接所成的项链，其总长为单个瓷片直径的四倍。

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

每个烧制的瓷片厚度是一定的，直径 $D$ 和所用泥土的体积 $V$ 有以下关系：

$$D = \begin{cases}
0.3\sqrt{V-V_0} & V > V_0 \cr
0 & V \le V_0
\end{cases}$$

其中 $V_0$ 为烧制每一片的损耗，单位与 $V$ 相同。当用料小于等于 $V_0$ 时，不能烧制成瓷片。
例： $V_总 = 10，V_0 = 1 $，若烧制成一片瓷片，$ V = V_总= 10，D = 0.9 $。如果把泥土均分成 $2$ 份，每份泥土的体积为 $V = \frac{V_总}{2} = 5 $，单个瓷片的直径为 $ D' = 0.3 \times \sqrt{5-1} =0.6 $ ,串起来的总长为 $1.2$ 。

给定了泥土的总体积和烧制单个瓷片的损耗，烧制的瓷片数不同，能够得到的项链总长度也不相同，请计算烧制多少个瓷片能使所得到的项链最长。

inputFormat:
共两行，每一行仅包含一个整数。

第一行的数字为泥土总体积 $ V_总$ ( $ 0 < V_总 < 60000 $ )，第二行为烧制单个瓷片的损耗 $V_0$ ($ 0 <  V_0 < 600 $)。

outputFormat:
共一行，一个整数。

该整数为能获得最长项链而烧制的瓷片数。如果不能烧制成瓷片或者最优解不唯一（存在两个或者两个以上方案均能获得最长项链），输出 `0`。


title: [NOI2000] 单词查找树

description:
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
-	根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
-	从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
-	在满足上述条件下，该单词查找树的节点数最少。

例：图一的单词列表对应图二的单词查找树

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

对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）

inputFormat: 一个单词列表，每一行仅包含一个单词。每个单词仅由大写的英文字符组成，长度不超过 $63$ 个字符。文件总长度不超过 32K，至少有一行数据。

outputFormat: 仅包含一个整数。该整数为单词列表对应的单词查找树的节点数。


title: [NOI2000] 程序分析器

description:
Tiny Basm语言(简称为TB语言)的巴科斯-瑙尔范式(BNF)为：

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

错误语句示例(在输入文件中不会出现任何错误语句)：

- `10A+1.5`（不符合累加语句的定义，所加的不是整数）
- `20A?`（不符合输出语句的定义，多加了一个空格）
- `30IFA=BGO10`（不符合条件语句的定义，不应变量=变量）

$\\$

TB程序的执行：
-	程序从行号最小的一条语句开始执行，在未遇到条件语句时按行号由小至大顺序执行。
-	所有变量在程序执行前被自动初始化为 $0$。
-	累加语句将语句中变量的值加上语句中的整数送回该变量。
-	输出语句将语句中变量的值在监视器上显示出来。
-	执行条件语句时，当且仅当该语句中的变量与紧跟在等号后面的整数值相等，后面的转移语句才被执行。该语句中的所有整数值至多为 $4$ 位。
-	转移语句被执行后，程序将转去执行 $\tt GO$ 后面指定的行号的语句。
-	当程序执行结束语句后，结束整个程序的执行。
-	假设该系统能处理任意大小的整数，而不会发生溢出。

请编程，对于给定的 TB 语言程序 $P$，求该程序所执行的语句数（执行条件语句不论是否成功转移，仅记为执行一条语句）。

inputFormat:
- 为一个TB语言程序 $P$ ，语句数不超过 $100$ 行。
- $P$ 中每条语句的长度不超过 $20$ 个字符。
- $P$ 中转移语句里 $\tt GO$ 后面的行号一定有对应的语句。
- $P$ 中可能有多个不同行号的结束语句。
- $P$ 中行号最大的语句一定是结束语句。
- $P$ 中的行号都不大于 $3000$。
- 输入文件不一定是按行号递增顺序给出 $P$ 的。

outputFormat:
-	有且仅有一行：

如果程序能够正常结束，输出该程序所执行的语句数；

如果程序不能正常结束，输出 $-1$。

hint:
**样例说明**

执行语句行号按顺序为 $10→20→30→40→50→20→30→40→50→20→60$。

共 $11$ 条语句被执行。


title: [NOI2000] 古城之谜

description:
著名的考古学家石教授在云梦高原上发现了一处古代城市遗址。让教授欣喜的是在这个他称为冰峰城 (Ice-Peak City) 的城市中有 $12$ 块巨大石碑，上面刻着用某种文字书写的资料，他称这种文字为冰峰文。然而当教授试图再次找到冰峰城时，却屡屡无功而返。

幸好当时教授把石碑上的文字都拍摄了下来，为了解开冰峰城的秘密，教授和他的助手牛博士开始研究冰峰文，发现冰峰文只有陈述句这一种句型和名词 (n) 、动词 (v) 、辅词 (a) 这三类单词，且其文法很简单：

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

在研究了大量资料后，他们总结了一部冰峰文词典，由于冰峰文恰好有 $26$ 个字母，为了研究方便，用字母 $a$ 到 $z$ 表示它们。

冰峰文在句子和句子之间以及单词和单词之间没有任何分隔符，因此划分单词和句子令石教授和牛博士感到非常麻烦，于是他们想到了使用计算机来帮助解决这个问题。假设你接受了这份工作，你的第一个任务是写一个程序，将一篇冰峰文文章划分为最少的句子，在这个前提下，将文章划分为最少的单词。

inputFormat:
-	第 $1$ 行为词典中的单词数 $n$ （$ n \le 1000 $）。
-	第 $2$ 行至第 $(n+1)$ 行每行表示一个单词，形为 $"α.mot"$ ，$α$ 表示词性，可能是 n (名词), v（动词）, a（辅词）中的一个， $mot$ 为单词，单词的长度不超过 $20$ 。拼写相同而词性不同的单词视为不同的单词，如输入示例中的 n.kick 与 v.kick 是两个不同的单词。
-	输入文件第 $(n+2)$ 行为需要划分的文章，以 "." 结束。
-	输入文件中的文章确保为冰峰文。文章是由有限个句子组成的，每个句子只包含有限个单词。文章长度不超过 5KB。

outputFormat:
-	为两行，每行一个整数。
-	第 $1$ 行为划分出来的句子数。
-	第 $2$ 行为划分出来的单词数。

samples:
11
n.table
n.baleine
a.silly
n.snoopy
n.sillysnoopy
v.is
v.isnot
n.kick
v.kick
a.big
v.cry
sillysnoopyisnotbigtablebaleinekicksnoopysillycry.

hint:
**样例说明**

（为了阅读方便，划分的单词用空格分隔，在单词的右上角标出它的词性，每行写一个句子，用句号表示句子结束。）

输出对应的划分：

$ sillysnoopy^n \quad isnot^v \quad big^a \quad table^n. \\
baleine^n \quad kick^v \quad snoopy^n \quad silly^a \quad cry^v. $

如果用下面的划分：

$ silly^a \quad snoopy^n \quad isnot^v \quad big^a \quad table^n. \\
baleine^n \quad kick^v \quad snoopy^n \quad silly^a \quad cry^v.$

则划分的句子数仍为 $2$ 个，但单词数却多了 $1$ 个，为 $10$ 个，显然应该按前者而不是后者划分。


title: [NOI2000] 算符破译

description:
考古学发现，几千年前古梅文明时期的数学非常的发达，他们懂得多位数的加法和乘法，其表达式和运算规则等都与现在通常所用的方式完全相同（如整数是十进制，左边是高位，最高位不能为零；表达式为中缀运算，先乘后加等），唯一的区别是其符号的写法与现在不同。有充分的证据表明，古梅文明的数学文字一共有 $13$ 个符号，与
 $0,1,2,3,4,5,6,7,8,9,+,*,=$ 这 $13$ 个数字和符号（称为现代算符）一一对应。为了便于标记，我们用 $13$ 个小写英文字母 $a,b,…m$ 代替这些符号（称为古梅算符）。但是，还没有人知道这些古梅算符和现代算符之间的具体对应关系。

在一个石壁上，考古学家发现了一组用古梅算符表示的等式，根据推断，每行有且仅有一个等号，等号左右两边为运算表达式（只含有数字和符号），并且等号两边的计算结果相等。

假设这组等式是成立的，请编程序破译古梅算符和现代算符之间的对应关系。

inputFormat:
-	第一行为等式的个数 $N$ （$ 1 \le N \le 1000 $），以下 $N$ 行每行为一个等式。
-	每个等式的长度为 $5$ 个字符到 $11$ 个字符。

outputFormat:
-	如果不存在对应关系能够满足这组等式，输出`noway`。
-	如果有对应关系能够满足这组等式，输出所有能够确定的古梅算符和现代算符的对应关系。每一行有两个字符，其中第一个字符是古梅算符，第二个字符是对应的现代算符。输出按照字典顺序排序。

hint:
**样例说明**

在上例中，可能对应的现代表达式为 $ \{6*2=12，2=1+1 \}， \{6*4=24，4=2+2 \}，\{ 6*8=48，8=4+4 \} $。可见，能够确定的对应关系只有 $a$ 对应 $6$ ，$b$ 对应 $*$ ，$d$ 对应 $=$，$f$ 对应 $+$ ，应该输出；而 ${c,e}$ 虽然能够找到对应的现代算符使得等式成立，但没有唯一的对应关系，不能输出。其他古梅算符 ${g,h…m}$ 完全不能确定，也不能输出。


title: [NOI1997] 竞赛排名

description:
某市组织了一次中学生科技全能竞赛，每个选手要参加数学、物理、化学、天文、地理、生物、计算机和英语共八项竞赛,最后综合八项竞赛的成绩排出总名次。

选手编号依次为： $1,2,\dots,N$（$N$ 为参赛总人数）。设 $x_{i, j}$（$1 \le i \le N, 1 \le j \le 8$）分别表示编号为 $i$ 的选手第 $j$ 项竞赛的成绩。其它指标如下：

- 第 $j$（$1 \le j \le 8$）项竞赛的平均分 $avg_j = \frac{1}{N} \sum_{i=1}^N x_{i, j}$
- 选手 $i$（$1 \le i \le N$）的总分 $sumx_i = \sum_{j=1}^8 x_{i, j}$
- 选手 $i$（$1 \le i \le N$）第 $j$（$1 \le j \le 8$）项竞赛的位置分

$$
y_{i, j}= \begin{cases} 0 & \left(\sum_{i = 1} ^ N |x_{i, j} - avg_j| = 0\right) \\ \frac{x_{i, j} - avg_j}{\frac{1}{N} \sum_{i = 1} ^ N |x_{i ,j} - agv_j|} & \left(\sum_{i = 1} ^ N |x_{i, j} - avg_j| \ne 0\right)\end{cases}
$$

- 选手 $i$（$1 \le i \le N$）的总位置分 $sumy_i = \sum_{j=1}^3 y_{i, j} + 0.8 \sum_{j=4}^8 y_{i, j}$

排名规则如下:
1. 总位置分高的选手名次在前；
2. 若两个或两个以上的选手总位置分相同，则总分高的选手名次在前；
3. 若两个或两个以上的选手总位置分和总分均相同，则编号在前的选手名次在前。

请你为竞赛组委会编一程序，计算本次全能竞赛的总排名情况。

inputFormat: 第一行为参赛总人数 $N$，从第二行到第 $N$ 行依次为编号为 $1$ 到编号为 $N$ 的选手的成绩，每行有 $8$ 个 $0 \sim 100$ 之间的整数，代表该选手的 $8$ 项竞赛成绩 。同一行相邻两个数之间用一个空格符隔开。

outputFormat: 有 $N$ 行，从第 $1$ 行到第 $N$ 行依次为排名第 $1$ 的选手的编号，排名第 $2$ 的选手的编号，……，排名第 $N$ 的选手的编号。

hint:
#### 数据范围

对于所有测试数据，满足 $1 \le N \le 1000$。


title: [NOI1997] 积木游戏

description:
SERCOI 最近设计了一种积木游戏。每个游戏者有 $N$ 块编号依次为 $1 ，2，…，N$ 的长方体积木。对于每块积木,它的三条不同的边分别称为"a 边"、"b 边"和"c 边"，如下图所示：

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

游戏规则如下：
1. 从 $N$ 块积木中选出若干块，并将它们分成 $M$ （$ 1 \le M \le N $） 堆，称为第 $1$ 堆，第 $2$ 堆…，第 $M$ 堆。每堆至少有 $1$ 块积木，并且第 $K$ 堆中任意一块积木的编号要大于第 $K+1$ 堆中任意一块积木的编号($ 2 \le K \le M $)。

2.  对于每一堆积木,游戏者要将它们垂直摞成一根柱子,并要求满足下面两个条件：

$\qquad$ 1)除最顶上的一块积木外，任意一块积木的上表面同且仅同另一块积木的下表面接触，并且要求下面的积木的上表面能包含上面的积木的下表面，也就是说，要求下面的积木的上表面的两对边的长度分别大于等于上面的积木的两对边的长度。

$\qquad$ 2)对于任意两块上下表面相接触的积木，下面的积木的编号要小于上面的积木的编号。

最后，根据每人所摞成的 $M$ 根柱子的高度之和来决出胜负。

请你编一程序，寻找一种摞积木的方案，使得你所摞成的 $M$ 根柱子的高度之和最大。

inputFormat:
一行有两个正整数 $N$ 和 $M$ （$ 1 \le M \le N \le 100 $），分别表
示积木总数和要求摞成的柱子数。这两个数之间用一个空格符隔开。

接下来 $N$ 行依次是编号从 $1$ 到 $N$ 的 $N$ 个积木的尺寸，每行有三个 $1$ 至 $1000$ 之间的整数，分别表示该积木 a 边, b 边和  c 边的长度。
同一行相邻两个数之间用一个空格符隔开。

outputFormat: 只有一行，为一个整数，表示 $M$ 根柱子的高度之和的最大值。


title: [CQOI2005] 新年好

description:
重庆城里有 $n$ 个车站，$m$ 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 $1$，他有五个亲戚，分别住在车站 $a,b,c,d,e$。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

inputFormat:
第一行：$n,m$，分别为车站数目和公路的数目。

第二行：$a,b,c,d,e$，分别为五个亲戚所在车站编号。

以下 $m$ 行，每行三个整数 $x,y,t$，为公路连接的两个车站编号和时间。

outputFormat: 仅一行，包含一个整数 $T$，为最少的总时间。保证 $T\le 10^9$。


title: [NOI1997] 最佳游览

description:
有一座旅游城，它的街道成网格状（如图）．其中东西向的街道是“风景线"、两旁分布着许多景观：南北向的街道都是"林萌道"，两旁没有任何建筑物。由于游客众多，" 风景线”被规定为单行道，游客在风景线上只能从西走到东，林荫道上则可以任意行走。

一名游客将到这座旅游城旅游。他根据自己对景观的喜好给所有的风景线打了分，分值是从 $-100$ 到 $+100$ 的整数，分值越大表示我们的旅游者越喜欢这条风景线上的景致。显然这位游客不可能给这座旅游城的所有风景线都打负分。

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

游客可以从旅游城的任一个十字路口开始游览，在任一个十字路口结束游览。我们的旅游者希望一路上游览的所有风景线的分值之和能够尽可能地大。请你写一个程序，帮助这位游客寻找一条最佳的游览路线。

inputFormat:
第一行是两个整数 $M$ 和 $N$ ，之间用一个空格符隔开， $M$ 表示旅游城南北向林萌道的段数， $N$ 表示东西向风景线的段数，($ 1 \le M \le 100$，$1 \le N \le 20001 $)。

接下来的 $M$ 行依次给出了由北向南各条风景线的分值信息。每行有 $N-1$ 个整数，依次表示了自西向东每段风景线的分值。同一行相邻两个数之间用一个空格隔开。

outputFormat: 只有一行，含一个整数，表示你的程序所找到的最佳游览路线的总分值。


title: [NOI1997] 卫星覆盖

description:
SERCOI（Space-Earth Resource Cover-Observe lnstitute） 是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星 -SERCOI-308。这种卫星可以覆盖空间直角坐标系中一定大小的立方体空间，卫星处于该立方体的中心。
    其中 $（x,y,z）$ 为立方体的中心点坐标， $r$ 为此中心点到立方体各个面的距离（即 $r$ 为立方体高的一半）．立方体的各条边均平行于相应的坐标轴。我们可以用一个四元组 $(x,y,z,r)$ 描述一颗卫星的状态，它所能覆盖的空间体积 。
由于一颗卫星所能覆盖的空间体积是有限的，因此空间中可能有若干颗卫星协同工作。它们所覆盖的空间区域可能有重叠的地方，如下图所示（阴影部分表示重叠的区域）。

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

写一个程序，根据给定的卫星分布情况，计算它们所覆盖的总体积。

inputFormat: 第一行是一个正整数 $N$ （$ 1 \le N \le 100 $）：表示空间中的卫星总数。接下来的 $N$ 行每行给出了一颗卫星的状态，用空格隔开的四个正整数 $x,y,z,r$ 依次表示了该卫星所能覆盖的立方体空间的中心点坐标和半高，其中 ($ -1000 \le x,y,z \le 1000$，$1 \le r \le 200 )$。

outputFormat: 只有一行,包括一个正整数，表示所有这些卫星所覆盖的空间总体积。


title: [NOI1999] 内存分配

description:
内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。

经典的内存分配过程是这样进行的：
1. 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从 $0$ 开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 $i$ 开始的 $s$ 个连续的内存单元称为首地址为 $i$ 长度为 $s$ 的地址片。
2. 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻 $T$ ，需要内存单元数 $M$ 及运行时间 $P$。在运行时间 $P$ 内（即 $T$ 时刻开始，$T+P$ 时刻结束），这 $M$ 个被占用的内存单元不能再被其他进程使用。
3. 假设在 $T$ 时刻有一个进程申请 $M$ 个单元，且运行时间为 $P$ ，则：

$\qquad$ 1)	若 $T$ 时刻内存中存在长度为 $M$ 的空闲地址片，则系统将这 $M$ 个空闲单元分配给该进程。若存在多个长度为 $M$ 个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。

$\qquad$ 2)    如果 $T$ 时刻不存在长度为 $M$ 的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为 $M$ 的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

inputFormat:
第一行是一个数 $N$ ，表示总内存单元数（即地址范围从 $0$ 到 $N-1$ ）
从第二行开始每行描述一个进程的三个整数 $T、M、P$ （$ M \le N$）。

**数据已按 $T$ 从小到大排序。**

最后一行用`000`表示结束。

输入文件最多 $10000$ 行，且所有数据都小于 $10^9$。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

outputFormat:
共两行。

第一行是全部进程都运行完毕的时刻。

第二行是被放入过等待队列的进程总数。


title: [NOI1999] 最优联通子集

description:
众所周知，我们可以通过直角坐标系把平面上的任何一个点 $P$ 用一个有序数对 $(x,y)$ 来唯一表示，如果 $x,y$ 都是整数，我们就把点 $P$ 称为整点，否则点 $P$ 称为非整点。我们把平面上所有整点构成的集合记为 $W$。

定义 1 ：两个整点 $P_1(x_1,y_1),P_2(x_2,y_2)$，若 $|x_1-x_2|+|y_1-y_2|=1$，则称 $P_1,P_2$ 相邻，记作 $P_1$~$P_2$ ，否则称 $P_1,P_2$ 不相邻。

定义 2 ：设点集 $S$ 是 $W$ 的一个有限子集，即 $S$=$\{P_1,P_2,…,P_n\}$ $(n \ge 1)$，其中 $P_i (1 \le i \le n)$ 属于 $W$，我们把 $S$ 称为整点集。

定义 3 ：设 $S$ 是一个整点集，若点 $R$,$T$ 属于 $S$ ，且存在一个有限的点序列 $Q_1,Q_2,…,Q_k$ 满足:
1. $Q_i$ 属于 $S$ （$ 1 \le i \le k $）;
2. $Q_1$ = $R$,$Q_k$ = $T$;
3. $Q_i$~$Q_{i+1} (1 \le i \le k-1)$，即 $Q_i$ 与
 $Q_{i+1}$ 相邻;
4. 对于任何 $1 \le i<j \le k$ 有 $Q_i≠Q_j$;

我们则称点 $R$ 与点 $T$ 在整点集 $S$ 上连通，把点序列 $Q_1,Q_2,…,Q_k$ 称为整点集 $S$ 中连接点 $R$ 与点 $T$ 的一条道路。

定义 4 ：若整点集 $V$ 满足：对于 $V$ 中的任何两个整点， $V$ 中有且仅有一条连接这两点的道路，则 $V$ 称为单整点集。

定义 5 ：对于平面上的每一个整点，我们可以赋予它一个整数，作为该点的权，于是我们把一个整点集中所有点的权的总和称为该整点集的权和。

我们希望对于给定的一个单整点集 $V$ ，求出一个 $V$ 的最优连通子集 $B$ ，满足：
1. $B$ 是 $V$ 的子集
2. 对于 $B$ 中的任何两个整点，在 $B$ 中连通；
3. $B$ 是满足条件 (1) 和 (2) 的所有整点集中权和最大的。

inputFormat:
第一行是一个整数 $N$ ，表示单整点集 $V$ 中点的个数；

以下 $N$ 行中，第 $i$ 行 $(1 \le i \le N) $ 有三个整数，$X_i,Y_i,C_i$ 依次表示第 $i$ 个点的横坐标，纵坐标和权。同一行相邻两数之间用一个空格分隔。

outputFormat: 仅一个整数，表示所求最优连通集的权和。


title: [CQOI2005] 珠宝

description: 有一棵 $n$ 个结点的树，给每个点安排一个正整数编号，使得相邻点具有不同的编号，编号的总和尽量小。

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

以下 $n-1$ 行，每行两个数 $u,v(1\le u,v\le n)$，表示 $u$ 和 $v$ 间有一条边。

outputFormat: 仅一行，为最小编号和。


title: 【政治】划分

background: 小蒟建立了一个城市，$\texttt{TA}$ 凭借优（cu）异（bi）的政治素养，管理着城市并进行规划。

description:
对于一座新建的城市，可以将其视为一片连通的区域。

现在，小蒟需要建造一些道路，将城市分为若干片互不连通的区域。

首先，小蒟要建造 $a_1$ 条主干道。主干道是一条贯通整个城市的直线。

接着，小蒟要建造 $a_2$ 个环岛。环岛是一条首尾相接的圆形道路。

然后，小蒟要建造一些道路网络。这些道路网络包括 $a_3$ 条正三角形道路（即三条道路连成一个封闭的三角形），$a_4$ 条正四边形道路……$a_n$ 条正 $n$ 边形道路。

小蒟希望用这些道路将城市划分为尽可能多片互不连通区域。可是他不会计算最多能划分成为多少个区域，所以他只能来求助你。

由于最后的答案可能很大很大，你只需要输出答案对 $10^9+7$ 取模的值。

inputFormat:
第一行，一个正整数 $n$，代表小蒟的计划中边数最多的道路网络是几边形。

第二行，$n$ 个整数，为 $a_{1\dots n}$。

outputFormat: 一行一个整数，表示答案对 $10^9+7$ 取模后的值。

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

如下图所示：

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

#### 数据范围

对于 $20\%$ 的数据：$1\le n \le 10^3$，$0 \le a_i \le 100$。

对于 $100\%$ 的数据：$1\le n \le 3 \times 10^6$，$0 \le a_i \le 10^3$。

**注意内存限制，你的 UKE 很有可能就是 MLE**。

**若 $n=1$ 则只存在直线道路，若 $n=2$ 则只存在直线道路和圆形道路。**


title: [CQOI2016] 路由表

description:
路由表查找是路由器在转发 IP 报文时的重要环节。通常路由表中的表项由目的地址、掩码、下一跳（Next Hop）地址和其他辅助信息组成。例如：
| 目的地址 | 掩码长度 | 下一跳 |
| :----------: | :----------: | :----------: |
| 0.0.0.0 | /1 | 192.168.1.1 |
| 128.0.0.0 | /1 | 192.168.1.1 |
| 8.8.8.0 | /24 | 192.168.1.1 |
| 8.8.8.8 | /32 | 192.168.1.253 |

当路由器收到一个 IP 报文时，会将报文中的目的 IP 地址与路由表中的表项逐条进行比较，选择匹配且**最明确**的表项，将报文转发给该表项中指定的下一跳。

匹配的过程是将报文中的目的地址和表项中的目的地址分别转为二进制串，再查看表项中的掩码长度，若掩码长度为 $x$ ，则将两个二进制串的前 $x$ 位进行比较，如果相同则认为匹配。

所谓**最明确**是指在有多个表项匹配时，掩码长度最大的表项。也可以理解为匹配的二进制位最多的项。

IP 地址转为二进制串的操作是把地址中 $4$ 个整数（一定在 $0$ 到 $255$ 的范围内）分别转为 $8$ 位二进制数，再顺序拼接起来，得到一个  位的二进制串。例如，$192.168.1.253$ 转为二进制串后为 $11000000 $ $10101000$ $00000001$ $11111101$。

我们以报文的目的地址为 $8.8.8.8$ 为例，说明其在上述路由表的匹配过程。

| 8.8.8.8 | 00001000 00001000 00001000 00001000 |
| :----------: | :----------: |
| 0.0.0.0/1 | $\color{red}{0}$0000000 00000000 00000000 00000000 |
| 128.0.0.0/1 | $\color{red}{1}$0000000 00000000 00000000 00000000 |
| 8.8.8.0/24 | $\color{red}{00001000}$ $\color{red}{00001000 }$ $\color{red}{00001000}$ 00000000 |
| 8.8.8.8/32 | $\color{red}{00001000}$ $\color{red}{00001000 }$ $\color{red}{00001000}$ $\color{red}{00001000}$  |

上表将地址均转为二进制串，并用红色标记出待比较的位（由掩码长度决定）。将红色部分与报文中的目的地址比较，可知 $0.0.0.0/1$、$8.8.8.0/24$、$8.8.8.8/32$ 均能够匹配。路由器从中选取掩码长度最长（/32）的表项 $8.8.8.8/32$，将报文转发给其对应的下一跳地址 $192.168.1.253$。

在实际的核心路由器中，路由表通常较大（现在互联网的全局路由表已经接近 $60$
 万条记录），并且会随着新接入设备不断扩张。为了分析路由表变化对转发产生的影响，网络工程师想要知道一段时间内某个 IP 地址的路由表项选择发生了多少次变化（变化是指由于最明确匹配等因素选择了不同的表项，不考虑下一跳地址）。

inputFormat:
第一行为整数 $M$，表示共有 $M$ 次操作。接下来 $M$ 行，每行描述一次操作。操作有两种：

`A <D>/<L>`

其中 $D$ 为一个 IP 地址，$L$ 为整数 ($1 \le L \le 32 $)。添加一条表项至路由表，其目的地址为 $D$，掩码长度为 $L$。下一跳地址由于没有用到，故省略。

`Q <D> <a> <b>`

其中 $D$ 为一个 IP 地址，$a,b$ 为正整数($a \le b$) 。查询从第 $a$ 次至第 $b$ 次添加表项期间（含 $a,b$），目的地址 $D$ 的路由表项选择发生了多少次变化。保证查询时表中至少有 $b$ 个表项。

outputFormat: 包含若干行，每行仅有一个整数，依次对应每个查询操作。

hint:
对于一次查询的一种理解方式是：无视其它所有查询操作，只看添加操作。先清空路由表，然后执行第 $1$ 到 $a-1$ 次添加操作。之后再统计第 $a$ 到 $b$ 次添加操作过程中匹配改变的次数。

--------

对于 $30\%$ 的数据，$M \le 10^3$；

对于 $100\%$ 的数据，$M \le 10^6$。

设一条表项的掩码长度为 $L$，数据保证将目的地址转为二进制串后，末尾的 $32-L$ 位均为 $0$。另外，保证不会重复添加目的地址和掩码长度都相同的表项。


title: [JSOI2016] 位运算

description:
JYY 最近在研究位运算。他发现位运算中最有趣的就是异或 (xor) 运算。对于两个数的异或运算，JYY 发现了一个结论：两个数的异或值为 $0$ 当且仅当他们相等。于是 JYY 又开始思考，对于 $N$ 个数的异或值会有什么性质呢？

JYY 想知道，如果在 $0$ 到 $R-1$ 的范围内，选出 $N$ 个不同的整数，并使得这 $N$ 个整数的异或值为 $0$，那么一共有多少种选择的方法呢？（选择的不同次序并不作重复统计，请参见样例）

JYY 是一个计算机科学家，所以他脑海里的 $R$ 非常非常大。为了能够方便的表达，如果我们将 $R$ 写成一个 $01$ 串，那么 $R$ 是由一个较短的 $01$ 串 $S$ 重复 $K$ 次得到的。比如，若 $S=101$，$K=2$，那么 $R$ 的二进制表示则为 $101101$。由于计算的结果会非常大，JYY 只需要你告诉他选择的总数对 $10^9+7$ 取模的结果即可。

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

接下来一行包含一个由 $0$ 和 $1$ 组成的字符串 $S$；

我们保证 $S$ 的第一个字符一定为 $1$。

outputFormat: 一行一个整数，表示选择的方案数对 $10^9+7$ 取模的值。


title: [JSOI2016] 反质数序列

description:
对于一个长度为 $L \ge 2$ 的序列 $X:\{x_1,x_2,...,x_L\}$，如果满足对于任意 $1 \le i < j \le L$，均有 $x_i+x_j$ 不为质数，则 JYY 认为序列 $X$ 是一个「反质数序列」。

JYY 有一个长度为 $N$ 的序列 $A:\{a_1,a_2,...,a_N\}$，他希望从中选出一个包含元素最多的**子序列**，使得这个子序列是一个反质数序列。

inputFormat:
输入第一行包含一个正整数 $N$；

接下来一行包含 $N$ 个正整数，依次描述 $a_1,a_2,...,a_N$。

outputFormat: 输出一行一个整数，表示最长反质数子序列的长度。输入保证存在反质数子序列。


title: [JSOI2016] 无界单词

description:
对于一个单词 $S$ ，如果存在一个长度 $l$，满足 $0 < l < |S|$，并且使得 $S$ 长度为 $l$ 的前缀与 $S$ 长度为 $l$ 的后缀相同，JYY 则称 $S$ 是有界的。比如 `aabaa` 和 `ababab` 就都是有界的字符串。如果一个单词不存在这样的 $l$ ，则 JYY 称之为无界单词。

现在考虑所有仅由字母 `a` 和 `b` 组成的长度为 $N$ 的字符串，JYY想知道：

1. 一共有多少个无界单词？
2. 这些无界单词中，按字典序排列第 $K$ 小的单词是哪一个？

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

第一行包含一个正整数 $T$，表示测试数据的组数；

接下来 $T$ 行，每行包含两个正整数 $N$ 和 $K$，表示一组测试数据。

outputFormat:
对于每一个测试数据，输出两行。

其中第一行包含一个整数，表示长度为 $N$ 的无界单词的数量；

其中第二行包含一个长度为 $N$ 的字符串，表示第 $K$ 小的无界单词。

samples:
12
aaaab
12
aaabb
12
aabab
12
aabbb
12
ababb

hint:
对于 $20\%$ 的数据，满足 $N \le 20 $；

对于全部数据，满足 $1 \le T \le 5$，$1 \le N \le 64$，并且保证对于任意测试数据，总存在第 $K$ 小的无界单词。


title: [JSOI2016] 飞机调度

description:
JSOI 王国里有 $N$ 个机场，编号为 $1$ 到 $N$。从 $i$ 号机场到 $j$ 号机场需要飞行 $T_{i,j}$ 的时间。由于风向，地理位置和航空管制的因素，$T_{i,j}$  和 $T_{j,i}$ 并不一定相同。

此外，由于飞机降落之后需要例行维修和加油。当一架飞机降落 $k$ 号机场时，需要花费 $P_k$ 的维护时间才能再次起飞。

JS Airways 一共运营 $M$ 条航线，其中第 $i$ 条直飞航线需要在 $D_i$ 时刻从 $X_i$ 机场起飞，不经停，飞往 $Y_i$ 机场。

为了简化问题，我们假设 JS Airway 可以在 $0$ 时刻在任意机场布置任意多架加油维护完毕的飞机；为了减少飞机的使用数，我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。

JYY 想知道，理论上 JS Airways 最少需要多少架飞机才能完成所有这 $M$ 个航班。

inputFormat:
第一行包含两个正整数 $N$,$M$；

接下来一行包含 $N$ 个正整数表示每一个机场的飞机维护时间；

接下来 $N$ 行，每行 $N$ 个非负整数，其中第 $i$ 行第 $j$ 个非负整数为 $T_{i,j}$，表示从 $i$ 号机场飞往 $j$ 号机场所需要花费的时间。数据保证 $T_{i,i}=0$；

接下来 $M$ 行，每行三个正整数，其中第 $i$ 行为 $X_i,Y_i,D_i$，表示第 $i$ 条航线的起飞机场，降落机场，以及起飞时间。数据保证 $X_i \neq Y_i$。

outputFormat: 一行一个正整数，表示 JS Airways 理论上最少需要的飞机数。

hint:
**样例说明1**

在第一个样例中，JS Airways 可以在 $0$ 时刻在 $2$ 号机场安排一架飞机并执飞第 $2$ 条航线（$2→1$）。此外还需要在 $0$ 时刻在 $1$ 号机场安排一架飞机，这架飞机首先执飞第 $1$ 条航线（$1→2$），然后通过临时新增一条航线从 $2$ 号机场起飞飞往 $3$ 号机场，降落 $3$ 号机场之后执飞第 $3$ 条航线（$3→1$）。

**样例说明2**

在第二个样例中，执行完第 $1$ 条航线的飞机无法赶上第 $3$ 条航线的起飞时间，因此 JS Airways 必须使用 $3$ 架不同的飞机才能完成所有的航班。

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

**数据范围**

对于 $30\%$ 的数据，满足 $N,M \le 10$；

对于 $60\%$ 的数据，满足 $N,M \le 100$；

对于全部数据，满足 $1 \le N,M \le 500$，$0 \le P_i,T_{i,j} \le 10^6$，$1 \le D_i \le 10^6$。


title: [JSOI2016] 轻重路径

description:
JYY 最近学习了一种处理树形结构的高级技巧，叫「轻重路径剖分」。这种技术会将树中的边划分成轻边和重边。相连的重边会形成一些树上相离的路径。「轻重路径剖分」可以使得从树上任意一点走到根，都至多只会经过 $(\log N)$ 条不同的重路径。

如果你不了解轻重路径剖分，JYY 在这里简单介绍一下：对于一棵有根树中的任意一个点 $u$，我们用 $size(u)$ 表示其为根的子树中的点的数量。对于 $u$ 的所有孩子中，我们选出 $size$ 值最大的孩子 $v$，并将边 $(u,v)$ 设置成重边，$u$ 和其他孩子之间的边我们均设置为轻边。

为了简化问题，这里 JYY 仅考虑一棵 $N$ 个点的有根二叉树。这 $N$ 个点由 $1$ 到 $N$ 编号。并且如果 $u$ 存在两个 $size$ 值一样的孩子，则我们默认 $u$ 和其左孩子的连边为重边。

现在 JYY 希望执行额外 $Q$ 次删点操作，每次 JYY 会随机删掉一个当前二叉树的叶子节点，而你则需要动态的维护这棵树的轻重路径剖分。

为了方便输出，你只需要在每次操作后输出所有重边指向的点的编号之和即可。

如果删除一个点之后，存在一个点 $u$ 拥有两个 $size$ 值一样的孩子，则我们保持 $u$ 在该操作执行之前的重边划分。

inputFormat:
第一行包含一个整数 $N$；

接下来 $N$ 行，第 $i$ 行包含两个整数 $L_i,R_i$，表示编号为 $i$ 的点的左孩子编号和右孩子编号，$L_i=0$表示点 $i$ 没有左孩子， $R_i=0$表示点 $i$ 没有右孩子；

第 $N+2$ 行包含一个整数 $Q$，表示 JYY 进行的删点操作；

第 $N+3$ 行包含 $Q$ 个空格分开的正整数，表示 JYY 删去的叶子的编号。

输入数据保证每次删除操作均删除了一个叶子。

outputFormat: 输出 $Q+1$ 行，每行包含一个整数，表示在轻重路径剖分中所有重边指向的点的编号的和。其中第一行对应初始的路径剖分，之后的 $Q$ 行对应进行了相应删点操作之后路径划分。

hint:
对于 $30\%$ 的数据，满足 $N \le 1000$；

对于 $50\%$ 的数据，满足 $N \le 5 \times 10^4$；

对于全部数据，满足 $N \le 2 \times 10^5$。


title: [JSOI2016] 病毒感染

description:
JOSI 的边陲小镇爆发了严重的 Jebola 病毒疫情，大批群众感染生命垂危。计算机科学家 JYY 采用最新的算法紧急研制出了 Jebola 疫苗，并火速前往灾区救治患者。

一共有 $N$ 个小镇爆发了 Jebola 疫情。这些小镇由于地处边陲，仅仅通过一条长直公路连接。方便起见我们将这些小镇按照公路连接顺序由 $1$ 编号到 $N$。JYY 会在第一天一早抵达 $1$ 号小镇。

一开始在 $i$ 号小镇，有 $a_i$ 名患者感染了 Jebola 病毒。

每一天 JYY 可以选择：

1. 花费一天时间彻底治愈 JYY 目前所在的村庄的所有 Jebola 患者。这一天不会有任何患者死去；
2. 花费一天的时间前往一个相邻的村庄。

当一天开始时，如果一个村庄里有 $k$ 个 Jebola 患者，那么这一天结束时，这 $k$ 个患者会感染另外 $k$ 个这个村子里的健康村民并死去。所以对于 $i$ 号村庄，只要这个村庄没有被 JYY 彻底消灭疫情，那么每一天都会有 $a_i$ 个村民死去。

JYY 希望采用措施使得疫情被整体消灭时，总共死去的村民数量尽量少。

为了达成这一目标，JYY 有时会选择抵达一个村庄但是并不对村民进行施救。这样的行为如果不加限制，往往会造成更加严重的后果。

试想这样的情形：假设当 JYY 第一次抵达村庄 $i$，未作救治并直接前往了另一个村庄。那么由于 $i$ 村庄的人们求生心切，一旦当 JYY 朝向靠近 $i$ 村庄的方向前行时，$i$ 村庄的村民就会以为 JYY 是来救他们了，而产生巨大的期望。之后倘若 JYY 再次掉头朝着远离 $i$ 村庄的方向行进，那么 $i$ 村庄的村民就会因为巨大的失落而产生绝望的情绪。

为了避免这种情况，JYY 对他的行程做了如下规定：

假设 JYY 进入 $i$ 村庄并在第二天立即离开（村庄 $i$ 的疫情并未治愈）。如果在之后的某一天，JYY 从村庄 $j$ 前往村庄 $k$，并满足 $|k-i| \lt |k-j|$。那么在之后的日子里 JYY 只能朝着 $i$ 村庄前进直到抵达 $i$ 村庄并立即治愈该村的患者。在前往 $i$ 村庄的过程中，JYY 可以选择将途经村庄的疫情治愈。

比如，如果 JYY 有如下行程：

第一天：从村庄 $1$ 前往村庄 $2$；

第二天：从村庄 $2$ 前往村庄 $3$；

第三天：治愈村庄 $3$；

第四天：前往村庄 $2$。

此时 JYY 对于之后三天的行程只有唯一一种选择：

第五天：治愈村庄 $2$；

第六天：前往村庄 $1$；

第七天：治愈村庄 $1$。

JYY 想知道在治愈所有村庄之前，至少会有多少村民因 Jebola 死去。

inputFormat:
输入第一行包含一个正整数 $N$；

接下来一行包含 $N$ 个整数，分别为 $a_1,a_2,...,a_N$。

outputFormat: 输出一行一个整数，表示最优行程安排下会死去的村民数量。

hint:
**样例说明**

我们用 $C(k)$ 表示治愈 $k$ 号村庄，$i \rightarrow j$ 表示从村庄 $i$ 前进到村庄 $j$，用逗号分隔每一天的行程安排，那么样例中的最优策略为：

$1 \rightarrow 2 , C(2),2 \rightarrow 3 , 3 \rightarrow 4 , C(4) , 4 \rightarrow 3 , C(3) , 3 \rightarrow 2 , 2 \rightarrow 1 , C(1) , 1 \rightarrow 2 , 2 \rightarrow 3 , 3 \rightarrow 4 , 4 \rightarrow 5 , 5 \rightarrow 6 , C(6) , 6 \rightarrow 5 , C(5)$;

整个过程耗时 $18$ 天。

------

**数据范围**

对于 $10\%$ 的数据，满足 $N \le 10$；

对于 $30\%$ 的数据，满足 $N \le 20$；

对于 $50\%$ 的数据，满足 $N \le 60$；

对于 $100\%$ 的数据，满足 $1 \le N \le 3000$，$1 \le a_i \le 10^9$。


title: [WC2001] 高性能计算机

description:
现在有一项时间紧迫的工程计算任务要交给你——国家高性能并行计算机的主管工程师——来完成。为了尽可能充分发挥并行计算机的优势，我们的计算任务应当划分成若干个小的子任务。

这项大型计算任务包括 $A$ 和 $B$ 两个互不相关的较小的计算任务。为了充分发挥并行计算机的运算能力，这些任务需要进行分解。研究发现，$A$ 和 $B$ 都可以各自划分成很多较小的子任务，所有的 $A$ 类子任务的工作量都是一样的，所有的 $B$ 类子任务也是如此（$A$ 和 $B$ 类的子任务的工作量不一定相同）。$A$ 和 $B$ 两个计算任务之间，以及各子任务之间都没有执行顺序上的要求。

这台超级计算机拥有 $p$ 个计算节点，每个节点都包括一个串行处理器、本地主存和高速 cache。然而由于常年使用和不连贯的升级，各个计算节点的计算能力并不对称。一个节点的计算能力包括如下几个方面：

1. 就本任务来说，每个节点都有三种工作状态：待机、$A$ 类和 $B$ 类。其中，$A$ 类状态下执行 $A$ 类任务；$B$ 类状态下执行 $B$ 类任务；待机状态下不执行计算。所有的处理器在开始工作之前都处于待机状态，而从其它的状态转入 $A$ 或 $B$ 的工作状态（包括 $A$ 和 $B$ 之间相互转换），都要花费一定的启动时间。对于不同的处理节点，这个时间不一定相同。用两个正整数 $t_{i}^{A}$ 和 $t_{i}^{B}$ ($i = 1,2,\cdots,p$)分别表示节点 $i$ 转入工作状态 $A$ 和工作状态 $B$ 的启动时间（单位：ns）。

2. 一个节点在连续处理同一类任务的时候，执行时间——不含状态转换的时间——随任务量（这一类子任务的数目）的平方增长，即：

若节点 $i$ 连续处理 $x$ 个 $A$ 类子任务，则对应的执行时间为：$t = k_{i}^{A} x^2$；

类似的，若节点 $i$ 连续处理 $x$ 个 $B$ 类子任务，对应的执行时间为：$t = k_{i}^{B} x^2$。

其中，$k_{i}^{A}$ 和 $k_{i}^{B} $ 是系数，单位是 ns，$i=1,2,\cdots,p$。

任务分配必须在所有计算开始之前完成，所谓任务分配，即给每个计算节点设置一个任务队列，队列由一串 $A$ 类和 $B$ 类子任务组成。两类子任务可以交错排列。

计算开始后，各计算节点分别从各自的子任务队列中顺序读取计算任务并执行，队列中连续的同类子任务将由该计算节点一次性读出，队列中一串连续的同类子任务不能被分成两部分执行。

现在需要你编写程序，给这 $p$ 个节点安排计算任务，使得这个工程计算任务能够尽早完成。假定任务安排好后不再变动，而且所有的节点都同时开始运行，任务安排的目标是使最后结束计算的节点的完成时间尽可能早。

inputFormat:
第一行是对计算任务的描述，包括两个正整数 $n_A$ 和 $n_B$，分别是 $A$ 类和 $B$ 类子任务的数目，两个整数之间由一个空格隔开。

后面部分是对此计算机的描述：

第二行是一个整数 $p$，即计算节点的数目。

随后连续的 $p$ 行按顺序分别描述各个节点的信息，第 $i$ 个节点由第 $i+2$ 行描述，该行包括下述四个正整数（相邻两个整数之间有一个空格）：$t_{i}^{A},t_{i}^{B},k_{i}^{A},k_{i}^{B}$。

outputFormat: 只有一行，包含有一个正整数，即从各节点开始计算到任务完成所用的时间。


title: [AHOI2006] 斐波卡契的兔子

description:
卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎 $a$ 对兔子，接着在出生后的二个月又将生出 $b$ 对兔子，在第三个月和以后每个月都会繁殖 $c$ 对兔子（$a \le b \le c$）。   由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友，卡卡想在 $m$ 个月后有 $k$ 对兔子，以便分给他们的好友，他的愿望是否能够实现呢？

[任务] 编写一个程序：从输入文件中读入输入信息；计算 $m$ 个月后卡卡将有多少对兔子，设之为 $P$；计算如果 $m$ 个月后卡卡要拥有至少 $k$ 对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为 $Q$ ；将结果输出至输出文件。

inputFormat: 输入文件的第一行有四个正整数：$a$，$b$，$c$ 和 $m$；而第二行则仅含一个正整数 $k$。它们的含义见上文描述。

outputFormat: 输出两行，第一行是一个整数 $P$ 而第二行是一个整数 $Q$。


title: [CTSC2001] 逻辑电路最优设计

description:
W 教授在 T 大学计算机系里开了一门「数字逻辑」课，主要讲授如何设计逻辑电路。这一天，W 教授布置了一个实验：设计并实现一个 $4$ 端输入、$4$ 端输出的逻辑译码电路。设计这样的电路原本并不困难，但是，教授给出了如下的要求：
1. 只允许使用 $2$ 端输入、$1$ 端输出的门电路作为实现电路的组件，而且可用门电路的种类和数目都已给定；
2. 使用最少数目的门电路。

这两个要求难倒了全系的同学，于是，Q 同学找到了正在参加 CTSC（中国队选拔赛）的你，希望你能帮忙编写一个程序，自动找出符合要求的连接方式。

在数字逻辑中，所有信号都可以看作只有两个值：「高电平」和「低电平」，分别用 $1$ 和 $0$ 来表示。

一个门电路元件的特性由其输入/输出功能表唯一给出，所谓功能表，就是输入信号电平与输出信号电平之间的关系表。比如，「与门」的符号和功能表如下图所示：

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

|X|Y|S|
|:-:|:-:|:-:|
|0|0|0|
|1|0|0|
|0|1|0|
|1|1|1|

上图中，如果「与门」的两个输入端 X 和 Y 都是高电平 $1$，则输出端 S 也是高电平 $1$，否则，输出端 S 是低电平 $0$。

假定，本次实验提供的门电路都具有输入对称性，即交换两个输入端的信号，输出不变。但是，如果门电路的输入端悬空（即没有加输入信号），则输出无意义。

在连接电路的过程中，一个门电路的输出端可以将信号送到其他多个元件的输入端；而门电路的一个输入端则只能接收来自一个输出端的信号。如下图所示：

![](https://cdn.luogu.com.cn/upload/image_hosting/7fp5byqu.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/8gad519v.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/5tg1p4j0.png)

其中，前两个连接方式是允许的，最后一个是不允许的。

另外，规定信号必须单向传输，即一个门电路的输出不能直接或间接通过其他门电路回到同一门电路的输入端。如下图所示即为两种不允许的连接方式：

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

要求你设计的译码电路是一个有四个输入端和四个输出端的逻辑电路，该译码电路的输入和输出关系通过功能表给出，即给出每种输入组合下的四个输出端的情况。显然，一共有 $2^4=16$ 种输入组合。比如，一个由前述「与门」构成的 $2$ 输入，$2$ 输出的简单译码电路如下图所示（其中，A1, A2 是输入端，Y1, Y2 是输出端）

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

|A1|A2|Y1|Y2|
|:-:|:-:|:-:|:-:|
|0|0|0|0|
|1|0|0|0|
|0|1|0|0|
|1|1|1|1|

inputFormat:
第一行为一个正整数 $n(n\le 5)$，表示元件的种类数，其后有连续的 $n$ 行，每行描述一种元件。对正整数 $1\le k\le n$：

第 $k+1$ 行有四个以空格隔开的整数，依次为：$m_k,Y_{00},Y_{01},Y_{11}$。

其中，正整数 $m_k$ 表示第 $k$ 种元件的数目（$k$ 即这种元件的种类编号），所有元件的数目之和不会超过 $10$（用于实验的经费并不充足）。$Y_{ij}$ 表示两个输入端分别为 $i$ 和 $j$ 时的输出，即 $Y_{00},Y_{01},Y_{11}$ 是三个非 $0$ 即 $1$ 的数，分别表示在两个输入端均为 $0$；两个输入端一个为 $0$ 另一个为 $1$；以及两个输入端均为 $1$ 的时候，该元件的输出。

第 $n+2$ 到第 $n+17$ 行，表示需组成的集成电路的功能表，每行有 $8$ 个数，分别为 $0$ 或 $1$。其中，前四个数依次对应四个输入端（编号为 $1\sim 4$）的信号，不存在两行的前四个数完全相同；而后面四个数则对应在各输入端信号为前四个数时，四个输出端依次应输出的信号。

outputFormat:
第一行为一个单词，`Yes` 或 `No`，如果存在符合要求的设计方案，则为 `Yes`，否则为 `No`。

如果第一行是 `No`，则输出结束。

否则第二行只有一个非负整数 $p$，表示最少需要的门电路数目。下面 $p$ 行分别给出每个门电路在电路中的连接情况的描述。每行有四个以空格隔开的正整数：$S ,K, A, B$，其中 $S$ 表示该门电路的编号（所有用到的门电路按 $5\sim p+4$ 编号，$1\sim 4$ 的编号用来表示四个输入端）；$K$ 表示该元件的种类编号（按照输入文件中的顺序由 $1\sim n$ 编号）；$A$ 和 $B$ 分别表示接入该元件的两个输入端的门电路或译码电路输入端的编号（其中，$A<S,B<S$）。

最后一行有四个正整数，表示组成的译码电路的四个输出端分别所接的元件的编号（在 $1\sim p+4$ 之间）。

hint:
#### 样例解释
样例对应的电路连接方式如下图所示：

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


title: [CTSC2001] GPA 排名系统

description:
目前，高等院校往往采用 GPA *(Grade Point Average)* 来评价学生的学术表现。传统的排名方式是求每一个学生的平均成绩，以平均成绩作为依据进行排名。

但是这样的排名方法已经引起了教育界以及社会各界人士的争议。因为它存在着许多弊端。对于不同的课程，选课学生的平均成绩会不同程度地受到课程的难易程度和老师的严厉程度的制约。因而这样的排名系统无形中就鼓励了学生选择一些比较容易的课程，因为这样可以事半功倍地获得较高的平均分。

为了克服这些弊端，我们需要对排名系统做一定的改进。

一种改进的方案是对选第 $i$ 门课的每一个学生的成绩加上一个特定的修正值 $d_i$，例如编号为 $j$ 的学生该课的成绩 $G_{ij}$ 修改为 $G’_{ij}=G_{ij}+d_i$。最终使得经过调整后，该课的平均分等于选该课的所有学生的所有课的平均分。对每一门课都做这样的调整，使得上述条件对所有课程都满足。这种调整方案一定程度地避免了传统排名系统的不公正。而你的任务正是根据一个大学某一个年级学生某学年的成绩，给出他们的排名。假设每一个学生都至少选一门课。

inputFormat:
第一行是两个正整数 $m$ 和 $n$，分别表示学生人数和课程数目。

接下来 $m$ 行是一个矩阵，矩阵中第 $i$ 行的第 $j$ 个元素表示第 $i$ 个学生第 $j$ 门课的成绩 $G_{ij}$。如果该学生没有选这门课，那么 $G_{ij}＝-1$。由于该方案的施行只是为了获得更加科学的排名，因此调整后的成绩的数值大小本身没有什么意义，因此调整后的成绩可以不是 $0\sim 100$ 之间的数。

outputFormat:
输出采用改进方案后这些学生的排名。以学生编号的形式输出，每行是一个学生的编号。

如果在上述调整后，有若干学生平均分相等（精确到小数点后的三位），则他们的名次相同，按照字典序输出。

当然许多时候，上述调整无法顺利进行，即调整的目标无法达到。（因此，在实际问题中，我们往往在最小二乘意义下获得一种最接近目标的调整方案。）也有可能或者因调整不唯一而不能确定学生的名次。若以上两种情况发生，则输出 `fail`。

hint:
#### 样例解释
一种可行的调整方法是：

第一门课每一个学生的成绩加上 $10$，第二门课每一个学生的成绩加上 $35$。
调整后的情况是：
```plain
70 –1
80 –1
90 80
-1 100
```
调整后第一门课的平均分为：$(70＋80+90)/3=80$，选第一门课的所有学生的所有课的平均分为：$(70+80+90+80)/4=80$。

第二门课的平均分为：$(80+100)/2=90$，选第二门课的所有学生的所有课的平均分为：$(90+80+100)/3=90$。

然后，计算每一个学生的平均分并且排名，即得到了输出的结果。

#### 数据范围
对于全部数据，$1\le m\le 500$，$1\le n\le 100$，$-1\le G_{ij}\le 100$。


title: [CTSC2001] 聪明的学生

description:
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生 A，B 和 C。有一天,教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。

这时，教授先对学生 A 发问了：「你能猜出自己的数吗？」A 回答：「不能。」

教授又转身问学生 B：「你能猜出自己的数吗？」B 想了想，也回答：「不能。」

教授再问学生 C 同样的问题，C 思考了片刻后，摇了摇头：「不能。」

接着，教授又重新问 A 同样的问题，再问 B 和 C，……，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。

现在，如果告诉你：教授在第 $N$ 次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是 $M$，你能推断出另外两个学生的头上贴的是什么数吗？

#### 提示
在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是「不能」；而且除此之外在 A，B，C 之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。

教授总是从学生 A 开始提问的。

你可以假定，这三个足够聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。

稍经分析和推理，你将得出以下结论：**总是头上贴着最大的那个数的人最先猜出自己头上的数。**

inputFormat:
输入包括若干组测试数据，其中的每一行代表一组测试数据。

对于每组测试数据，由两个整数 $N$ 和 $M$ 组成，即在教授第 $N$ 次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是 $M$。两个数之间用空格分隔开。

最后，由 `-1 -1` 组成的一行标志着输入数据的结束。

outputFormat:
按照输入中的顺序依次给出各组数据的结果。

输出中对应每组数据的输出的第一行是一个整数 $p$，是可能情况的总数。接下来的 $p$ 行，每一行包括三个数，分别为贴在 A，B，C 头上的三个数。输出时，所有解按照 A 头上的数增序排列；在 A 头上的数相同的情况下，按照 B 头上的数增序排列。

hint: 对于全部数据，$N<500$，$M<3\times 10^4$。


title: [CTSC2001] 终极情报网

description:
在最后的诺曼底登陆战开始之前，盟军与德军的情报部门围绕着最终的登陆地点展开了一场规模空前的情报战。 这场情报战中，盟军的战术是利用那些潜伏在敌军内部的双重间谍，将假的登陆消息发布给敌军的情报机关的负责人。那些已经潜入敌后的间谍们都是盟军情报部的精英，忠实可靠；但是如何选择合适的人选，以及最佳的消息传递方法，才能保证假消息能够尽快而且安全准确地传递到德军指挥官们的耳朵里，成了困扰盟军情报部长的最大问题。他需要你的帮助。

以下是情报部长提供的作战资料：

在敌后一共潜伏着我方最优秀的 $N$ 名间谍，分别用数字 $1,2,\cdots,N$ 编号。在给定的作战时间内，任意两人之间至多只进行一次点对点的双人联系。 我将给你一份表格，表格中将提供任意两位间谍 $i$ 和 $j$ 之间进行联系的安全程度，用一个 $[0,1]$ 的实数 $S_{i,j}$ 表示；以及他们这次联系时，能够互相传递的消息的最大数目，用一个正整数表示 $M_{i,j}$（如果在表格中没有被提及，那么间谍 $i$ 和 $j$ 之间不进行直接联系）。 假消息从盟军总部传递到每个间谍手里的渠道也不是绝对安全，我们用 $[0,1]$ 的实数 $AS_j$ 表示总部与间谍 $j$ 之间进行联系的安全程度，$AM_j $  则表示总部和间谍 $j$ 之间进行联系时传递的消息的最大数目。对于不和总部直接联系的间谍，他的  $AM_j = 0$（而表格中给出的他的 $AS_j$ 是没有意义的）。 当然，假消息从间谍手中交到敌军的情报部官员的办公桌上的过程是绝对安全的，也即是说，间谍与敌军情报部门之间要么不进行直接联系，要么其联系的安全程度是 $1$（即完全可靠）。

现在情报部打算把 $K$ 条假消息“透露”到德军那里。消息先由总部一次性发给 $N$ 名间谍中的一些人，再通过他们之间的情报网传播，最终由这 $N$ 名间谍中的某些将情报送到德军手中。 对于一条消息，只有安全的通过了所有的中转过程到达敌军情报部，这个传递消息的过程才算是安全的；因此根据乘法原理，它的安全程度 $P$ 就是从总部出发，经多次传递直到到达德军那里，每一次传递该消息的安全程度的乘积。 而对于整个计划而言，只有当 $N$ 条消息都安全的通过情报网到达德军手中，没有一条引起怀疑时，才算是成功的。所以计划的可靠程度是所有消息的安全程度的乘积。 显然，计划的可靠性取决于这些消息在情报网中的传递方法。 我需要一个方案，确定消息应该从哪些人手中传递到哪些人手中，使得最终计划的可靠性最大。

你可以利用计算机，来求得这个最可靠的消息传递方案。

inputFormat:
输入包含了盟军的作战资料表格。

第一行包括两个整数 $N$ 和 $K$ ，分别是间谍的总人数和计划包含的消息总数。

第二行包括 $2N$ 个数，前 $N$ 个数是实数 $AS_1,AS_2,\cdots,AS_N$ （范围在 $[0,1]$ 以内）；后 $N$ 个数是整数 $AM_1,AM_2,\cdots,AM_N$ 。

第三行包含了 $N$ 个整数，其中第 $i$（$i = 1,2,\cdots,N$）个整数如果为 $0$ 表示间谍 $i$ 与德军情报部不进行联系，如果为 $1$ 则表示间谍 $i$ 与德军情报部进行联系。

第四行开始，每行包括 $4$ 个数，依次分别是：代表间谍编号的正整数 $i$ 和 $j$ ，间谍 $i$ 和 $j$ 联系的安全性参数 $S_{i,j}$ ( $[0,1]$ 范围内的实数)，以及 $i,j$ 之间传递的最大消息数 $M_{i,j}$ (每一行的 $i$ 均小于 $j$)。

最后的一行为 `-1 -1` ，表示输入数据的结束。

outputFormat:
输出只有一行。这一行中包含一个实数 $P$ ，给出的是整个计划的可靠程度 $P$ ，**保留 $5$ 位有效数字**（四舍五入）。

如果情报网根本不能将 $K$ 条消息传到德军手中，那么计划的可靠性为 $0$ 。

(你可以假定，如果计划存在，那么它的可靠性大于 $10^{-12}$)


title: [CTSC2011] 排列

description:
沫沫很喜欢找规律填数字，譬如 $1,4,7,( ),\cdots$，相邻的数相差为 $3$，括号中的数应为 $10$；又如 $3,6,12,( ),\cdots$，每个数是前一个数的两倍，括号中的数应为 $24$。

由于常年玩这种游戏，沫沫厌倦了等差数列与等比数列。当看到数列 $1,2,\cdots,n$ 时，她想尽量小的改变其顺序使得不存在公差为 $A$ 或者公比为 $B$ 的子列。

具体地，给定整数 $n,A,B$，求一个 $1$ 到 $n$ 的排列 $P = (P_1,P_2,\cdots,P_n)$，满足 $\forall i,j \in \{1,2,\cdots,n \}$，若 $i<j$ 且 $P_i<P_j$，则 $P_j \neq P_i+A$ 且 $P_j \neq P_i \times B$。排列 $P$ 保留原有顺序的程度 $S$ 定义为：

$$S = \sum\limits_{1 \le i \le j \le n , P_i<P_j} (P_j-P_i)$$

请你在满足前述要求的前提下，使得 $S$ 的值尽量大。

inputFormat: 第一行包含三个正整数 $n,A,B$，意义如前所述。相邻的数之间用一个空格隔开。

outputFormat: 第一行包含 $n$ 个整数，为你求得的排列 $P$，相邻的数之间用空格隔开。


title: [IOI2019] 矩形区域

background: # 滥用本题评测将封号！

description:
19 世纪初，统治者下令在俯瞰美丽河景的高原上建造一座宫殿。这块高原被看做是一个由正方形单元格组成的 $n \times m$ 网格。网格的行从 $0$ 到 $n-1$ 编号，列从 $0$ 到 $m-1$ 编号。第 $i$ 行第 $j$ 列（$0 \le i \le n-1$，$0 \le j \le m-1$）的单元格记为单元格 $(i,j)$。每个单元格 $(i,j)$ 有特定的海拔高度，记为 $a_{i,j}$。

统治者指示他的建筑师选择一个矩形区域来建造宫殿。该区域不能包含网格边界（第 $0$ 行，第 $n-1$ 行，第 $0$ 列，以及第 $m-1$ 列）上的任何单元格。为此，建筑师应选出四个整数 $r_1$，$r_2$，$c_1$ 和 $c_2$（$1 \le r_1 \le r_2 \le n-2$ 且 $1 \le c_1 \le c_2 \le m-2$ )，对应于包括所有满足 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 的单元格 $(i,j)$ 的矩形区域。

此外，一个区域被认为是合法的，当且仅当对于该区域中的每个单元格 $(i,j)$，以下条件成立：对于与该区域相邻的、位于第 $i$ 行的两个单元格（单元格 $(i,c_1-1)$ 和 $(i,c_2+2)$），以及与该区域相邻的、位于第 $j$ 列的两个单元格（单元格 $(r_1-1)$ 和 $(r_2+2,j)$），单元格 $(i,j)$ 的海拔高度必须严格小于这四个单元格的海拔高度。

你的任务是帮助建筑师统计可建宫殿的合法区域的数量（也就是所对应区域为合法的 $r_1$，$r_2$，$c_1$ 和 $c_2$ 的数量）。

inputFormat:
第一行，两个整数 $n$ 和 $m$，表示网格的长和宽。

接下来 $n$ 行，第 $i$ 行 $m$ 个整数，为 $a_{i-1,0\dots m-1}$。

outputFormat: 一行，一个整数，表示合法区域的数量。


title: [POI2001] 和平委员会

description:
根据宪法，Byteland 民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。 此委员会必须满足下列条件：

- 每个党派都在委员会中恰有 $1$ 个代表。
- 如果 $2$ 个代表彼此厌恶，则他们不能都属于委员会。

每个党在议会中有 $2$ 个代表。代表从 $1$ 编号到 $2n$。 编号为 $2i-1$ 和   $2i$ 的代表属于第 $i$ 个党派。

任务：写一程序读入党派的数量和关系不友好的代表对，计算决定建立和平委员会是否可能，若行，则列出委员会的成员表。

inputFormat:
第一行有两个非负整数 $n,m$。他们各自表示：党派的数量 $n$ 和不友好的代表对 $m$。

接下来 $m$ 行，每行为一对整数 $a,b$，表示代表 $a$ 和 $b$ 互相厌恶。

outputFormat:
如果不能创立委员会，则输出信息 `NIE`。

若能够成立，则输出包括 $n$ 个从区间 $1$ 到 $2n$ 选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。

如果委员会能以多种方法形成，程序可以只输出它们的某一个。


title: [CQOI2008] 位统计

description:
给出 $N$ 个 $[0, 65535]$ 的整数，编程支持以下操作：

修改操作：```C d```，所有数增加 $d$。如果超过 $65535$，把结果模 $65536$。（$0\le d\le 65535$）

查询操作：```Q i```，统计有多少整数的第 $i$ 位非 $0$，换句话说，有多少个整数与 $2^i$ 的“按位与”操作值为正。（$0\le i\le 15$）

输出所有查询操作的统计值。

inputFormat:
第一行为两个正整数 $N$ 和 $M$，即整数的个数和操作的个数。

第二行包含 $N$ 个 $[0,65535]$ 的整数。

以下 $M$ 行为各操作，格式如题所述。

outputFormat: 输出所有 $Q$ 操作的统计值。


title: [SDOI2012] 任务安排

description:
机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$，因此序列的排列为 $1 , 2 , 3 \cdots n$。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和。

**注意，同一批任务将在同一时刻完成**。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。

请确定一个分组方案，使得总费用最小。

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

接下来 $n$ 行，每行有一对整数，分别为 $T_i$ 和 $C_i$，表示第 $i$ 个任务单独完成所需的时间是 $T_i$ 及其费用系数 $C_i$。

outputFormat: 一行，一个整数，表示最小的总费用。


title: 「SWTR-3」Password

background:
小 $\mathrm{A}$ 在茂密的森林里找到了一个宝箱。

宝箱设有密码锁，但小 $\mathrm{A}$ 不知道密码。

description:
宝箱的密码由 $n$ 位数字组成，如果将它们连在一起写，就可以看作是一个长度为 $n$ 的字符串。

小 $\mathrm{A}$ 想通过猜的方式试出密码。对于每一位数字，都会有一个集合 $s_i$，表示小 $\mathrm{A}$ 第 $i$ 位的尝试范围。

同时，小 $\mathrm{A}$ 已经试过了 $k$ 个密码组合 $d_1,d_2,\dots,d_k$，**这些密码不一定符合上文中的“尝试范围”**。

小 $\mathrm{A}$ 想知道他最多还需要尝试多少次才可以试出宝箱的密码，如果永远试不出输出 $\mathrm{-1}$。

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

第二行，一个长度为 $n$ 的字符串 $a$，表示宝箱的密码。

接下来 $n$ 行，每行以一个整数 $v_i$ 开头，表示 $s_i$ 的大小，接下来一个长度为 $v_i$ 的字符串 $s_i$，保证 $s_i$ 各位数字互不相同。

接下来 $k$ 行，每行一个**互不相同**的长度为 $n$ 的字符串 $d_i$，表示小 $\mathrm{A}$ 已经试过了哪些密码组合。

outputFormat: 输出小 $\mathrm{A}$ 最多还需要尝试多少次可以试出宝箱的密码，如果永远试不出，输出 $-1$。


title: 「SWTR-3」Game

background: 小 E 在玩一个数字游戏。

description:
小 E 有 $n$ 个正整数 $a_1,a_2,\dots,a_n$。他可以进行以下操作任意次：

选择一个数 $q$，和一个集合 $S=\{d_1,d_2,\dots,d_m\}$，使得 $a_{d_1},a_{d_2},\dots,a_{d_m}$ 能被 $q$ 整除，并将 $a_{d_1},a_{d_2},\dots,a_{d_m}$ 除以 $q$。

- $q$ 要满足可以写成 $p^z$ 的形式，其中 $p$ 为质数，$z$ 为正整数。

求最少需要进行多少次操作才能将这些数变为相等的数。

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

第二行，$n$ 个整数 $a_1,a_2,\dots,a_n$。

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


title: 「SWTR-3」Matrix

description:
小 E 有一个 $n \times m$ 的魔法矩阵，每个格子有激活和未激活两个状态。一开始，格子都是未激活的。

小 E 有一个魔法棒，可以使用 $k$ 次魔法。每次使用魔法时小 $\mathrm{E}$ 需选择一个魔法格子 $(x,y)$ 并改变第 $x$ 行和第 $y$ 列的所有魔法格子的状态。**$(x,y)$ 的状态会被改变两次。**

现在小 E 想知道，使用 $k$ 次魔法之后可以得到多少个不同的魔法矩阵。

- 两个魔法矩阵不同，当且仅当两个魔法矩阵中有一个对应格子的状态不同。

由于答案很大，请对 $998244353$ 取模。

inputFormat:
**本题包含多组测试数据。**

第一行，一个整数 $T$，测试数据的组数。

每一组测试数据由一行三个整数 $n,m,k$ 组成——矩阵的长，矩阵的宽，使用魔法的次数。

outputFormat: 对于每组测试数据，输出单独的一行整数，表示使用 $k$ 次魔法之后可以得到多少个不同的魔法矩阵。


title: 「SWTR-3」Golden Sword

background: 小 E 不幸在一场战斗中失去了他的金宝剑。

description:
制造一把金宝剑需要 $n$ 种原料，编号为 $1$ 到 $n$，编号为 $i$ 的原料的坚固值为 $a_i$。

炼金是很讲究放入原料的顺序的，因此小 E 必须**按照 $1$ 到 $n$ 的顺序**依次将这些原料放入炼金锅。

但是，炼金锅的容量非常有限，它**最多只能容纳 $w$ 个原料**。

所幸的是，**每放入一个原料之前**，小 E 可以从中取出一些原料，数量不能超过 $s$ 个。

- 我们定义第 $i$ 种原料的耐久度为：放入第 $i$ 种原料时锅内的原料总数（包括正在放入的原料） $\times\ a_i$，则宝剑的耐久度为**所有原料**的耐久度之和。

小 E 当然想让他的宝剑的耐久度尽可能得大，这样他就可以带着它进行更多的战斗，请求出耐久度的最大值。

注：这里的“放入第 $i$ 种原料时锅内的原料总数**包括正在放入锅中的原料**，详细信息请见样例。

inputFormat:
第一行，三个整数 $n,w,s$。

第二行，$n$ 个整数 $a_1,a_2,\dots,a_n$。

outputFormat: 一行一个整数，表示耐久度的最大值。

hint:
#### 「样例说明」

- **对于样例 1**，一种可行的**最优**方案为：
首先放进原料 1，此时锅内有 $1$ 种原料，耐久度为 $1\times a_1=1\times 1=1$。
再放进原料 2，此时锅内有 $2$ 种原料，耐久度为 $2\times a_2=2\times 3=6$。
再放进原料 3，此时锅内有 $3$ 种原料，耐久度为 $3\times a_3=3\times 2=6$。
取出原料 1，再放进原料 4，此时锅内有 $3$ 种原料，耐久度为 $3\times a_4=3\times 4=12$。
取出原料 4，再放进原料 5，此时锅内有 $3$ 种原料，耐久度为 $3\times a_5=3\times 5=15$。
最终答案为 $1+6+6+12+15=40$。
- **对于样例 2**，一种可行的**最优**方案为：
放进原料 1，耐久度为 $1\times 1=1$。
取出原料 1，放进原料 2，耐久度为 $1\times (-3)=-3$。
放进原料 3，耐久度为 $2\times (-2)=-4$。
放进原料 4，耐久度为 $3\times 4=12$。
取出原料 2，放进原料 5，耐久度为 $3\times 5=15$。
最终答案为 $1+(-3)+(-4)+12+15=21$。
- **对于样例 3**，一种可行的**最优**方案为：
  $a_1+2a_2+2a_3+3a_4+4a_5+3a_6+4a_7=17$。
- **对于样例 4**，一种可行的**最优**方案为：
$a_1+a_2+a_3+a_4+a_5=-15$。

#### 「数据范围与约定」

**本题使用捆绑测试。**

- Subtask #1（15 points）：$n\leq 10$。
- Subtask #2（5 points）：$n\leq 100$，$a_i\geq0$。
- Subtask #3（15 points）：$n\leq 300$。
- Subtask #4（15 points）：$s=w=n$。
- Subtask #5（5 points）：$a_i\geq 0$。
- Subtask #6（10 points）：$n\leq 2\times 10^3$。
- Subtask #7（10 points）：$s=1$。
- Subtask #8（25 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq s \leq w \leq n \leq 5\times 10^3$，$|a_i| \leq 10^9$。对于 Subtask $i$ 有 $|a_i|\leq 10^{i+1}$。

#### 「帮助/说明」

本题下发大样例，具体输入输出见 [**Big Sample**](https://pan.baidu.com/s/1erVDllDlvNlEShxh3U42gA) 中的 gold01-08.in/gold01-08.out。提取码：757d。
**文件名与 Subtask 编号一一对应。**

#### 「来源」

[Sweet Round 03 D](https://www.luogu.com.cn/contest/24755)。
idea & solution：ET2006。


title: 「SWTR-3」Plane Mirrors

background:
小 $\mathrm{A}$ 在学物理。

老师在讲“平面镜成像”这个物理现象。

但老师讲课太无聊，所以他就睡着了。

description:
小 $\mathrm{A}$ 梦见自己站在了一个平台上，在他的周围有一些平面镜，我们假定他的位置为 $(0,0)$。

他发现，每个平面镜都有一个初始不透明度，记做 $v_i$。

下文中，我们定义：

- 一个射线的“不透明度”为：该射线穿过的所有平面镜的初始不透明度之和。

- 一个平面镜的“视觉不透明度”为：所有**从 $(0,0)$ 发出**且**经过该平面镜**的射线的不透明度最大值。

小 $\mathrm{A}$ 突然发现自己能够控制这些平面镜，于是就有了下面这道题目。

小 $\mathrm{A}$ 需要你完成以下操作：

`1 x1 y1 x2 y2 v`：变出一个两端分别在 $(x_1,y_1),(x_2,y_2)$，初始不透明度为 $v$ 的平面镜。

`2 d`：摧毁第 $d$ 个变出来的平面镜，保证未被摧毁。

`3 x y`：设 $\mathrm{A=(0,0),B=(x,y)}$，询问射线 $\mathrm{AB}$ 的不透明度。

`4 d`：询问第 $d$ 个平面镜的视觉不透明度，如已被摧毁则输出 `oops!`。

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

接下来 $n$ 行，第 $i$ 行先是一个整数 $opt$，然后：

- 如果 $opt=1$，五个整数 $x_1,y_1,x_2,y_2,v$。

- 如果 $opt=3$，两个整数 $x,y$。

- 否则一个整数 $d$。

outputFormat: 对于每一个 $3,4$ 询问，输出一行答案。

hint:
---

### 样例解释

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

如图，蓝色代表射线，红色代表平面镜。

对于第 $1$ 次询问：可以看出射线只穿过了平面镜 $1$，答案为 $7$。

对于第 $2$ 次询问：可以看出射线只穿过了平面镜 $2$，答案为 $10$。

对于第 $3$ 次询问：可以看出射线穿过了平面镜 $1,2$，答案为 $7+10=17$。

对于第 $4$ 次询问，可以看出射线穿过了平面镜 $3$，答案为 $17$。

对于第 $5$ 次询问，可以看出穿过平面镜 $2$ 的不透明度最大的射线为 $(0,0)(2,2)$（射线不唯一），穿过了平面镜 $1,2$，答案为 $7+10=17$。

对于第 $6$ 次询问，可以看出穿过平面镜 $2$ 的不透明度最大的射线为 $(0,0)(2,2)$（射线不唯一），穿过了平面镜 $2$，答案为 $10$。

对于第 $7$ 次询问，因为平面镜 $1$ 已被摧毁，所以输出 `oops!`。

---

### 数据范围与约定

测试点编号|$n\leq$|特殊性质
:-:|:-:|:-:
$1-4$|$1000$|$x,y$ 绝对值小于 $10^3$ 且**没有 $4$ 询问**
$5-8$|$2\times 10^5$|所有 $y$ 相等
$9-12$|$2\times 10^5$|$x\ge 0$
$13-20$|$2\times 10^5$|无

对于 $100\%$ 的数据，有 $1\leq n\leq 2\times 10^5$，$1\leq v\leq 10^3$ 且 $0\leq |x|,|y|\leq 10^5$。

保证平面镜的总数不会超过 $10^5$。

保证所有平面镜不会穿过 $(0,0)$，但**不保证**平面镜会退化成一个点。

保证所有 $3$ 询问 $(x,y)\neq(0,0)$。

---

对于所有测试点，时间限制 $2\mathrm{s}$，空间限制 $128\mathrm{MB}$。


title: 「SWTR-3」Counting Trees

background:
一个风和日丽的早晨，小 $\mathrm{S}$ 带着他的好朋友小 $\mathrm{A}$ 在小树林里面数树。

看着满树林的树，小 $\mathrm{S}$ 灵感一闪，想到了一道题目。

---

$$\mathrm{Suddenly,\ Little\ S\ thought\ of\ a\ supercalifragilisticexpialidocious\ problem.}$$

$$\mathrm{He\ wanted\ Little\ A\ to\ answer\ it.}$$

description:
现在有 $n$ 个点，每个点有一个权值 $v_i$。

小 $\mathrm{S}$ 想要小 $\mathrm{A}$ 从中选一些点组成一个集合，设集合 $S=\{d_1,d_2,\dots,d_m\}(1\leq m\leq n)$。

当然，小 $\mathrm{A}$ 还需要保证这些点能形成一颗树，且 $d_i$ 的度数为 $v_{d_i}(i\in[1,m])$。

- 节点的度数：与它相邻的节点的个数。

小 $\mathrm{S}$ 想问小 $\mathrm{A}$ 有多少种满足条件的方案。

小 $\mathrm{A}$ 深知自己肯定不会这道题目，所以他就拿来问你了。

由于方案数可能很大，所以请对 $998244353$ 取模。

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

第二行，$n$ 个整数 $v_1,v_2,\dots,v_n$

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

hint:
---

### 样例说明

- 对于样例 $1$，在三个节点中任选两个即可，答案为 $C^{2}_{3}=3$。

- 对于样例 $2$，如图，共有 $8$ 种选择节点的方法。

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

---

### 数据范围与约定

**本题使用捆绑测试。**

| Subtask 编号 | $n\leq$ | 特殊性质 | 得分 |
| :-: | :-: | :-: | :-: |
| $1$ | $20$ | 无 | $11$ |
| $2$ | $50$ | 无 | $12$ |
| $3$ | $300$ | 无 | $10$ |
| $4$ | $2500$ | 无 | $17$ |
| $5$ | $4\times 10^4$ | 无 | $6$ |
| $6$ | $3\times 10^5$ | $v_i\leq 3$ | $8$ |
| $7$ | $3\times 10^5$ | 数据随机 | $7$ |
| $8$ | $5\times 10^5$ | 无 | $29$ |

对于 $100\%$ 的数据，$2 \leq n \leq 5 \times 10^5$，$\ 1 \leq v_i \leq n$。

---

$\mathrm{Subtask\ 7}$ 中“数据随机”指：对于所有 $v_i$，$\frac{1}{3}$ 的概率为 1，$\frac{2}{3}$ 的概率为 $[2,n]$ 中等概率选择一个数。

---

对于前 $4$ 个 $\mathrm{Subtask}$，时间限制 $1\mathrm{s}$。

对于第 $5$ 个 $\mathrm{Subtask}$，时间限制 $3\mathrm{s}$。

对于后 $3$ 个 $\mathrm{Subtask}$，时间限制 $6\mathrm{s}$。

对于所有测试点，空间限制 $256\mathrm{MB}$。


title: [CQOI2008] 传感器网络

description:
一个无线传感器网络由若干独立采集数据的设备和一个控制中心组成。每个设备必须把采集到的数据传到控制中心处理，但由于设备限制，并不是每台设备都可以与控制中心直接相连。为了解决这一问题，你将传感器网络设计成树状结构。树根为控制中心，而每台设备恰好有一个父亲节点（要么为控制中心，要么为另一台设备）。一台设备的儿子设备个数称为它的负载级别。所有设备（注意，控制中心不是设备）的负载级别的最大值称为网络的负载级别。

　　你的任务是让整个网络的负载级别尽量小。

inputFormat: 第一行包含一个整数 $N$，即设备的个数。第二行包含 $N$ 个字符，表示每台设备是否能直接连接到控制中心。以下 $N$ 行每行 $N$ 个字符，其中第 $i$ 行第 $j$ 个字符为 `Y` 当且仅当设备 $i$ 可以作为设备 $j$ 的儿子。如果设备 $i$ 可以作为设备 $j$ 的儿子，那么在任何合法的网络中，设备 $j$ 一定不会是设备 $i$ 的后代。换句话说，如果把这 $N$ 行看作一个有向图的邻接矩阵，该图不存在有向环。

outputFormat: 仅一行，包含 $N$ 个整数，即每个设备的父亲。设备按照输入顺序编号为 $0$ 至 $N-1$，控制中心用 $N$ 表示。如果有多组解，输出字典序最小解。


title: [CQOI2006] 移动棋子

description:
在一个 $n\times n$ 的棋盘上有 $n$ 枚棋子。每次可以把一枚棋子往上、下、左、右方向之一移动一格，最后排成一行、一列或者主、副对角线上（因此一共有 $2n+2$ 条可能的目标状态），要求移动次数最小。

棋盘上有一些位置是障碍，棋子在任何时候都不能经过。棋子的初始位置保证不在障碍物上。任两枚棋子不能在同时到达同一个格子。

inputFormat:
第一行包含两个整数 $n$，$m$，表示棋子的个数（它也是棋盘的边长）和障碍的个数。

以下 $n$ 行，每行两个整数 $x$ 和 $y$，表示第 $i$ 个棋子的坐标。（$1\le x,y\le n$）

以下 $m$ 行，每行给出一个障碍物的坐标。保证这 $n+m$ 个坐标两两不重合。

outputFormat: 输出仅包含一个整数，表示最小移动步数。如果无解，输出`-1`。

hint:
【样例解释】

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

【数据范围】

对于 $50\%$ 的数据，$n\le 15$，$m=0$；

对于 $100\%$ 的数据，$2\le n\le 50$，$0\le m\le 100$。


title: 二分图 /【模板】线段树分治

description:
神犇有一个 $n$ 个节点的图。

因为神犇是神犇，所以在 $k$ 时间内有 $m$ 条边会出现后消失。

神犇要求出每一时间段内这个图是否是二分图。

这么简单的问题神犇当然会做了，于是他想考考你。

原 BZOJ4025。

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

接下来 $m$ 行，每行四个整数 $x,y,l,r$，表示有一条连接 $x,y$ 的边在 $l$ 时刻出现 $r$ 时刻消失。

outputFormat: $k$ 行，第 $i$ 行一个字符串 `Yes` 或 `No`，表示在第 $i$ 时间段内这个图是否是二分图。

hint:
### 样例说明

$0$ 时刻，出现两条边 $(1,2)$ 和 $(2,3)$。

第 $1$ 时间段内，这个图是二分图，输出 `Yes`。

$1$ 时刻，出现一条边 $(1,3)$。

第 $2$ 时间段内，这个图不是二分图，输出 `No`。

$2$ 时刻，$(1,2)$ 和 $(1,3)$ 两条边消失。

第 $3$ 时间段内，只有一条边 $(2,3)$，这个图是二分图，输出 `Yes`。

### 数据范围

$n,k = 10^5$，$m = 2\times 10^5$。$1 \le x,y \le n$，$0 \le l \le r \le k$。

### 注意

本题设有 hack 数据（Subtask $2$），计 $0$ 分，但若没有通过 hack 数据则不算通过本题。


title: [SEERC2019] Max or Min

description:
Kevin 有 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，它们按**环形**排列。对于环上的数字，数字 $a_i$ 和 $a_{i+1} \ (1 \leq i < n)$ 是相邻的，且数字 $a_1$ 和 $a_n$ 是相邻的。因此，每个数字有恰好两个相邻的数字。

在 $1$ 分钟内，Kevin 可以将 $a_i$ 修改为这 $3$ 个数字中的最小值或最大值：$a_i$ 以及它的两个相邻数字。例如，如果 $a_i=5$ 且 $a_i$ 的两个相邻数字为 $3$ 和 $2$，Kevin 修改 $a_i$ 为最小值后，$a_i$ 会变为 $2$；如果 Kevin 修改 $a_i$ 为最大值，$a_i$ 仍是 $5$。

对于从 $1$ 到 $m$ 的每个整数 $x$，计算出让上述环上的数字都变为 $x$ 的最短时间。

inputFormat:
第一行包含两个整数 $n$ 和 $m \ (3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$，代表环上的数字个数和需要计算答案的 $x$ 的范围。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq m)$，代表环上的数字。

outputFormat: 输出 $m$ 个整数。第 $i$ 个整数为将环上的所有数字变为 $i$ 的最短时间的分钟数，如果无论如何都无法将环上的所有整数变为 $i$，则第 $i$ 个整数应输出 $-1$。

hint:
要让环上的所有整数都变为 $2$，Kevin 需要至少 $5$ 分钟。一种可行的修改方案为：

1. 将 $a_6$ 修改为它与相邻数字中的最小值，即修改为 $2$；
2. 将 $a_4$ 修改为它与相邻数字中的最大值，即修改为 $2$；
3. 将 $a_3$ 修改为它与相邻数字中的最大值，即修改为 $5$；
4. 将 $a_2$ 修改为它与相邻数字中的最小值，即修改为 $2$；
5. 将 $a_3$ 修改为它与相邻数字中的最小值，即修改为 $2$。


title: [SEERC2019] Level Up

description:
作为一个 MMORPG 粉，得知《魔兽世界：经典旧世》发布的 Steve 非常兴奋。他从发布的第一天就开始玩，现在离满级只差 $2$ 级了。当然，他现在没有刚开始玩那时那么有空，因此他想尽快升到满级。

升第一个等级需要 $s_1$ 经验值。只有当他获得了这么多经验后，才能升到下一级，而第二个等级又需要 $s_2$ 经验值来升级。

Steve 有一个有 $n$ 个任务的任务列表。他希望通过完成一些任务来升到满级。Steve 需要花 $t_i$ 分钟才能完成第 $i$ 个任务，这个任务会让他获得 $x_i$ 经验值。

当 Steve 完成了一个任务后可以升级了，超过升级所需的那部分经验值将会计入下一等级。当他升了一级之后，第 $i$ 个任务可获得的经验值会减少为 $y_i$，而完成任务的时间也会减为 $r_i$。

需要注意的是，Steve 完成了的任务**不能**重复接取，无论是否升级。

已知任务列表中的任务信息，帮助 Steve 找出一个完成任务的顺序，使得他升到满级所需的时间最短。

inputFormat:
第一行包含三个整数 $n, s_1, s_2 \ (1 \leq n, s_1, s_2 \leq 500)$，代表任务的数量、升第一级所需的经验值和升第二级所需的经验值。

接下来的 $n$ 行每行包含四个整数 $x_i, t_i, y_i, r_i \ (1 \leq y_i < x_i \leq 500, 1 \leq r_i < t_i \leq 10^9)$，代表第 $i$ 个任务获得的经验值、完成所需的时间、升一级之后获得的经验值和完成所需的时间。

outputFormat: 输出一个整数，代表 Steve 升到满级所需的最短时间的分钟数，如果无论如何都无法升到满级，输出 $-1$。


title: [SEERC2019] Cycle String?

description:
大法师给了 Alice 和 Bob 一个长度为 $2 \cdot n$ 的环形字符串，这个环形字符串中没有重复的长为 $n$ 的子串。在一个环形字符串中，字符 $s_{i+1}$ 在 $s_i$之后，而 $s_1$ 在 $s_{2n}$ 之后。

不幸的是，恶魔打乱了字符串中字符的顺序。帮助 Alice 和 Bob 将字符串还原成满足上述要求的原始字符串。

inputFormat: 第一行包含一个长度为 $2 \cdot n \ (2 \leq 2\cdot n \leq 1 \ 000 \ 000)$ 的字符串 $s$，字符串中只包含小写字母。

outputFormat:
如果能够将字符串还原成满足要求的字符串，则在第一行输出 `NO`；如果无法还原，则在第一行输出 `YES`。

如果有解，在第二行输出还原后的字符串。如果存在多解，输出任意一个即可。

samples: aa NO

hint:
第一个样例中，还原后的字符串中的子串分别为：`abbab`、`bbabc`、`babcb`、`abcbc`、`bcbcc`、`cbccb`、`bccba`、`ccbab`、`babba`。

注意到第一个样例的答案中并不含有重复的子串，但存在其他的答案也满足题目要求。因此答案不唯一，样例只提供了一种满足要求的输出。

第二个样例中，无法将字符串还原为满足要求的原始字符串。

第三个样例中，不需要做任何操作即满足要求。


title: [SEERC2019] Life Transfer

background: *注：「feli」是当地货币单位。*

description:
在大都市 Nekoresti 中，有 $n$ 个人已知年龄，第 $i$ 个人年龄为 $a_i$。现在他们享受着假期，所以他们决定去 Pisiev 游览一个著名的博物馆 Koshkseum。他们可以通过开车或骑摩托车去：

- 一辆**车**可以载 $k$ 个人（包括一个年龄不低于 $l_c$ 岁的司机和 $k-1$ 个乘客）。一辆车的租金为 $p_c$ feli。
- 一辆**摩托车**只能载 $1$ 个人（年龄不低于 $l_m$ 岁）。一辆摩托车的租金为 $p_m$ feli。

不幸的是，这些人不是很富裕，所以他们请求一名当地的大魔法师 Mewlin 来帮助他们。通过使用一种强大的魔法 Mucadabra，Mewlin 可以转移人们的年龄。形式化地说，他可以减少一个年龄为 $x$ 的人的年龄，同时增加一个年龄为 $y$ 的人的年龄同一数值（这两个人的年龄之和不变）。完成 $1$ 岁的年龄的转移的花费是 $t$ feli。由于魔法的限制，魔法不能将一个人的年龄改变超过 $d$（如果一个人的年龄为 $x$，改变后的年龄只能在 $[x-d, x+d]$ 区间内）。并且，年龄也不能低于 $1$ 岁。

帮助这些人花费最少的钱从 Nekoresti 到 Pisiev 去旅游吧。

inputFormat:
第一行包含两个整数 $n$ 和 $k \ (1 \leq n, k \leq 10^5)$，代表旅游的人数和一辆车的最大载客数。

第二行包含四个整数 $l_c, p_c, l_m$ 和 $p_m \ (1 \leq l_m < l_c \leq 10^5, 1 \leq p_m < p_c \leq 10^5)$，代表开车的最低年龄、一辆车的租金、骑摩托车的最低年龄、一辆摩托车的租金。

第三行包含两个整数 $t$ 和 $d \ (0 \leq t, d \leq 10^5)$，代表转移 $1$ 岁的年龄的花费和魔法的转移改变量限制。

第四行包含 $n$ 个整数 $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq 10^5)$，$a_i$ 代表第 $i$ 个人的年龄。

outputFormat: 输出一个数字，即让所有人到达目的地的最小花费。如果无解，输出 $-1$。


title: [SEERC2019] Game on a Tree

description:
Alice 和 Bob 在树上玩游戏。最初的时候，树上的所有节点都是白色的。

Alice 先手，她可以任选一个节点并在该点上放置一个标记，该点变为黑色。在这之后，玩家轮流进行游戏，每一回合中玩家可以将标记从所在点移动到该点的白色祖先节点或儿子节点中，并将移动到的点变为黑色。无法进行移动的玩家即输。

谁会赢得游戏呢？

在有根树上，节点 $v$ 的*祖先节点*是指从树根到节点 $v$ 的路径上的任意点。

在有根树上，节点 $v$ 的*儿子节点*是指满足节点 $v$ 在从树根到节点 $w$ 路径上的任意点 $w$。

规定树的树根为点 $1$。

inputFormat:
第一行包含一个整数 $n \ (1 \leq n \leq 100 \ 000)$，代表树的节点数。

接下来的 $n-1$ 行中，每一行包含两个整数 $u$ 和 $v \ (1 \leq u, v \leq n)$，代表树上的一条边 $(u, v)$。数据保证这些边会构成一棵树。

outputFormat: 输出一行，如果 Alice 赢得了游戏，则输出 `Alice`，否则输出 `Bob`。

hint:
第一组样例中，树的形态是 $4$ 个点的一条链，所以 Bob 总是可以把标记移到最后的白点上。

第二组样例中，Alice 的最佳策略是先把标记放在点 $3$ 上，然后 $3$ 会变为黑色。Bob 只能移动标记到点 $1$ 上。Alice 可以选择点 $4, 5, 6$ 或 $7$ 来移动。Bob 只能选择 $2$。Alice 选择 $2$ 的任一白色子节点，Bob 就无法移动了。


title: [SEERC2019] Projection

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

你是一个 TensorFlow 的死忠粉，因此，你想要从两个投影图形来还原出 TensorFlow 的图标。

假定你有一个 3D 空间，尺寸为 $n \times m \times h$，以及两个投影图形（一个 $n \times m$ 的矩阵和一个 $n \times h$ 的矩阵，矩阵里的元素都为 $0$ 或 $1$）。你需要计算出一些 $1 \times 1 \times 1$ 的小正方体的集合，使得这些正方体放入 3D 空间后构成的立体的正投影（光照立体正面在立体后侧形成的投影）和右投影（光照立体左面在立体右侧形成的投影）与题目给定的投影图形一致。如果无解，输出 $-1$。如果有解，你需要计算出两个满足条件的集合，一个包含的小正方体数量最少，另一个最多。假定正方体的摆放不受重力影响（即小正方体在 3D 空间中可以随意放置，悬空也不需要支撑）。规定矩阵中的 $1$ 代表有阴影遮住，$0$ 代表无阴影遮住。

如果有多解，你需要输出字典序最小的解。一个解 $a$ 字典序比解 $b$ 小，当且仅当对于两个解中第一对不相同的数字，$a$ 中的数字小于 $b$ 中的。

例如，解 $[(0, 0, 0), (1, 1, 1)]$ 比解 $[(1, 1, 1), (0, 0, 0)]$ 字典序更小。

inputFormat:
第一行包含三个整数 $n, m, h \ (1 \leq n,m,h \leq 100)$，代表 3D 空间的尺寸。

接下来的 $n$ 行中，每一行包含 $m$ 个字符 $0$ 或 $1$，其中 $1$ 代表有阴影遮住，$0$ 代表无阴影遮住。这 $n \times m$ 个字符描述了一个正投影。

接下来的 $n$ 行中，每一行包含 $h$ 个字符，格式同上。这 $n \times h$ 个字符描述了一个右投影。

outputFormat:
如果无解，仅在第一行输出 $-1$ 即可。

如果有解，第一行输出一个整数 $k_{max}$，代表满足题目要求的解中小正方体个数的最大值。

接下来 $k_{max}$ 行中每行输出三个整数 $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$，代表小正方体最多的解中字典序最小的解的 $k_{max}$ 个小正方体的放置位置。

接下来一行输出一个整数 $k_{min}$，代表满足题目要求的解中小正方体个数的最小值。

接下来 $k_{min}$ 行中每行输出三个整数 $x, y, z \ (0 \leq x < n, 0 \leq y < m, 0 \leq z < h)$，代表小正方体最少的解中字典序最小的解的 $k_{min}$ 个小正方体的放置位置。

hint:
一个放置在 $(x, y, z)$ 的小正方体会在正投影的 $(x, y)$ 位置产生一个有阴影遮住的区域，并在右投影的 $(x, z)$ 位置产生一个有阴影遮住的区域。

坐标从 $0$ 开始编号。