title: [ROI 2018] Robomarathon

background: 译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T3. [Робомарафон](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf) ([Robomarathon](https://codeforces.com/gym/102154/problem/D))。

description:
有 $N$ 名机器人选手参加马拉松，选手的编号分别为 $1\ldots N$。跑道包含 $N$ 条分道，编号分别为 $1\ldots N$。每位选手占据一条分道，$i$ 号选手（简称 $i$ 号）占据编号为 $i$ 的分道（简称 $i$ 道）。每条分道从起点到终点的路程均相同。已知 $i$ 号跑完全程需要 $a_i$ 秒。

每条分道的起始点有一个发令喇叭，不过不是播声音的。裁判皮了一下，把有些分道上的发令喇叭关掉了。

时辰一到，所有开着的发令喇叭会同时发出起跑信号（下文简称发炮）。如果 $i$ 道上发炮，$i$ 号会立即起跑。

发令信号的传递速度为每秒钟 $1$ 道。举个例子，如果有且只有四道上发炮，那么一秒后三号和五号会收到信号并立即起跑；两秒后二号和六号会收到信号并立即起跑。假设 $i$ 号在第 $x_i$ 秒起跑，则他会在第 $f_i = a_i + x_i$ 秒冲线。

我们按照冲线顺序给选手排名。比如，如果 $n=3$， $f_1= f_2= 4$，$f_3= 5$, 那么一号和二号并列第一，三号屈居第三。

可见，选手的排名取决于发令喇叭的开关状态。请求出每位选手的最好名次或最差名次。

inputFormat:
第一行：$n$，$p$。

接下来一行 $n$ 个数，表示 $a_1$，$a_2 \ldots a_n$。

outputFormat:
如果 $p=1$，输出最好名次。

如果 $p=2$， 输出最差名次。


title: [ROI 2018] Addition without carry

type: P

background: 译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T4. [Сложение без переносов ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf)([Addition without carry](https://codeforces.com/gym/102154/problem/A))。

description:
对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\mathtt{OR}$ 和，那么我们称之为「美丽的集合」。

给出 $a_1\ldots a_n$, 存在一个由数列 $b_1\ldots b_n$ 组成的「美丽的集合」，且满足：

$\forall i=1\ldots n$， $b_i\geq a_i$, 且
$\sum b_i$ 最小。

试求出新数列的 $\sum b_i$。

为了简便起见，我们给出的 $a_i$ 均为二进制形式，你的答案也应是二进制形式。

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

接下来 $n$ 行，一行一个二进制数 $a_i$。

outputFormat: 输出得出的二进制的 $\sum b_i$。

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

（在二进制下）$a_i$ 的位数不超过 $3 \times 10^5$，并且所有 $a_i$ 的位数之和不超过 $3\times 10^5$。

由于原题子任务及数据过多，在此仅挑选部分进行评测。


title: [ROI 2018] Quick sort

background:
译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T2. [Быстрая сортировка
](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf)([Quick sort](http://codeforces.com/gym/102154/problem/C))。

description:
给一个包含 $n$ 个元素的排列 $[a_1,a_2,\ldots,a_n]$。
定义操作 $S(l,r),$ 表示：将数列的片段 $[a_l,a_{l+1},\ldots,a_r]$ 重排成 $[a_{l+1},a_{l+3},\ldots,a_l,a_{l+2},\ldots]$。
举个例子：$[2, 4, 1, 5, 3, 6, 7, 8]\xrightarrow{S(2,6)} [2, 1, 3, 4, 5, 6, 7, 8]$， 其中子串 $[4, 1, 5, 3, 6]$ 被重排成了 $[1, 3, 4, 5, 6]$。
给定一个排列，试求经过多少次操作能使排列变成递增顺序，并输出任意一组方案，$不$要求方案的操作次数最少，但要求操作次数 $\leq 15000$。

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

第二行 $n$ 个数，表示排列 $a$。

outputFormat:
第一行一个整数 $k$，表示你的操作次数。 需要满足 $0 \leq k \leq 15000$。
接下来 $k$ 行，你需要按照操作顺序描述你的操作。对于每一步操作，输出两个数 $L$, $R$，表示你对片段 $a_L,a_{L+1},\ldots, a_R$ 执行了一次操作。 需满足 $1 \leq L \leq R \le n$。
注意，你**不**需要最小化。你只需保证 $0 \le k \leq 15000$ 即可。保证存在这样的 $k$。


title: [POI2020] Gang Biciaków / 布茨帮

background: **题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Gang Biciaków](https://sio2.mimuw.edu.pl/c/oi28-1/p/gan/)。**

description:
Bajtazar 在一家货运公司工作，他目前的工作是将建筑材料从 Bajtocji 的首都运输到附近城镇的商店。在 Bajtocji，有 $n$ 座城市（编号从 $1$ 到 $n$），这些城市通过 $n-1$ 条道路相互连接。每条道路上都有一个加油站。

Bajtazar 一天的工作是这样的：他从首都（编号为 $1$ 的城市）出发，沿着最短路径到达城市 $x$，再原路返回。

Bajtazara 的儿子 Bitek 非常喜欢加油站里卖的玩具狗。玩具狗一共有 $m$ 种（编号从 $1$ 到 $m$），但每个加油站只提供一种玩具狗，因此收集玩具狗并非一件轻松的事情。

现在给出 Bajtazara 每天前往的目的地，他想要知道他的儿子这天能够获得多少种玩具狗。麻烦的是，每个加油站里售卖的玩具狗的种类会发生变化，你能帮助他解决这个难题吗？

inputFormat:
输入第一行三个整数 $n,m,z$，分别代表 Bajtocji 的城市数，玩具狗的种类数，查询的次数。

接下来 $n-1$ 行，第 $i$ 行三个整数 $a_i,b_i,c_i$，代表第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$（$1 \leq a_i,b_i \leq n$），该道路上的加油站售卖的玩具狗种类为 $c_i$（$1 \leq c_i \leq m$）。

接下来 $z$ 行，每行描述一个询问或修改操作，格式如下：

- 询问操作：$\texttt{Z}\ x$ 表示 Bajtazara 想要知道，从首都出发到城市 $x$（$2 \leq x \leq n$），能收集到多少种玩具狗。
- 修改操作：$\texttt{B}\ i\ c$ 表示将第 $i$ 条道路上加油站售卖的玩具狗的类型改为 $c$（$1 \leq c \leq m$，注意如果该加油站本来就售卖 $c$ 类型玩具狗，执行该操作后将不会有任何影响）。

outputFormat: 对于每个 $\texttt{Z}$ 操作，输出一行一个整数，代表这一天 Bajtazara 的儿子能获得的玩具狗的种类数。

hint:
【样例解释1】：

![pp5XLWV.png](https://s1.ax1x.com/2023/04/05/pp5XLWV.png)

注意该样例中存在一次修改操作，使得第二条道路上的加油站售卖的玩具狗的种类从 $2$ 变成了 $1$。

【数据范围】：

所有测试点均满足：$2 \leq n \leq 10^5$，$1 \leq m,z \leq 1.5 \times 10^5$，且至少存在一个 $\texttt{Z}$ 操作。

| 子任务编号 | 约束| 分值|
|:-:|:-:| :-: |
| $1$| $n,m,z \leq 100$| $7$  |
| $2$| $n,z \leq 2 \times 10^3$| $9$  |
|$3$ | 只有 $\texttt{Z}$ 类型操作| $9 $  |
| $4$| $m \leq 15$|$15$|
|$5$|道路 $i$ 连接城市 $i$ 和城市 $i+1$| $11$ |
| $6$ | 刚开始时，每个加油站售卖的玩具狗类型都是 $1$，在后续的 $\texttt{B}$ 类型操作中，玩具狗的类型会被更改为除 $1$ 之外的任意类型 | $13$ |
| $7$| 无附加约束| $36$ |


title: 「GMOI R2-T2」猫耳小（加强版）

background:
**本题与 [原题](https://www.luogu.com.cn/problem/P9199) 的区别在于数据范围和输出格式。在这一版本中，$n\le 10^6$，值域为 $10^9$，你需要给出构造。**

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

description:
小 R 是一个可爱的猫耳女孩子，她喜欢研究数列的 $\operatorname{mex}\text{*}$。

现在她有一个长度为 $n$ 的数列 $a$。她讨厌整数 $k$，因此她希望修改数列 $a$ 的若干个元素为任意**自然数**，使得 $a$ 的任意**连续非空子串**的 $\operatorname{mex}$ 都不等于 $k$。

请你求出最少需要修改多少个元素，并给出方案。

$\text{*}$ 本题中，数列的 $\operatorname{mex}$ 被定义为数列中最小未出现的**自然数**，例如：

- $\operatorname{mex}\{1,2,3\}=0$，因为 $0$ 是自然数。
- $\operatorname{mex}\{0,1,3\}=2$。
- $\operatorname{mex}\{0,1,2\}=3$。

inputFormat:
第一行两个整数 $n,k$，表示数列长度和小 R 讨厌的数。

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$，表示这个数列的第 $i$ 项。

outputFormat:
第一行一个整数，表示最少需要修改的元素个数。

第二行 $n$ 个整数，表示修改后的数列。你需要保证修改后的数列的每个数在 $[0,10^9]\cap\Z$ 的范围内。

hint:
**样例解释**

一种方案是将 $\{1,0,1,3,0\}$ 改为 $\{1,1,1,3,2\}$，共改动两个元素。

可以证明不存在更优的方案。

---

**评分方式**

本题采用自定义校验器（Special Judge）进行评测。

对于每个测试点，如果你的最小步数正确，可以得到 $30\%$ 的分数。在此基础上，如果方案也正确，可以得到满分。

请注意：即使你不会给出方案，也请按照输出格式在第二行输出 $n$ 个整数。

---

**本题采用捆绑测试，数据无梯度。**

对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\le k,a_i\le 10^9$。

本题读写量较大，建议使用效率较高的读写方式。


title: [语言月赛202304] 扶苏与 0

type: B

description:
一扶苏一认为，有一些数字中，有零的影子。

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

如图，在数字 $2,6,9,0$ 中有一个零的影子，而在数字 $8$ 中有两个零的影子。

给出一个数，求其中零的影子的个数。

inputFormat: 输入一行一个整数 $X$。

outputFormat: 输出一行一个整数，为你的答案。


title: 「KDOI-06-S」签到题

background: 你正在追番，突然家长进来了，于是你假装在写一道数据结构题。

description:
定义一个长度为 $m$ 的数组 $v$ 是合法的，当且仅当经过若干次以下操作可以使 $v$ 中的所有元素相等：

* 选择四个整数 $a,b,c,d$（$1\leq a\leq b\leq m$，$1\leq c\leq d\leq m$）满足 $b-a+1=d-c+1$，且 $v_a\operatorname{~or~}v_{a+1}\operatorname{~or~}\cdots\operatorname{~or~}v_b=v_c\operatorname{~or~}v_{c+1}\operatorname{~or~}\cdots\operatorname{~or~}v_d$，其中 $\operatorname{or}$ 表示按位或运算。接下来，将区间 $[a,b]$ 的数**复制下来再覆盖**到区间 $[c,d]$。**注意：区间 $\bm{[a,b]}$ 和 $\bm{[c,d]}$ 可能会相交。**

给出一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$ 以及 $q$ 次询问，每次询问给定两个正整数 $l,r$，你需要回答区间 $[l,r]$ 内的最长合法子区间的长度。

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

**本题含有多组测试数据。**

输入的第一行包含两个整数 $T,id$，表示数据组数和测试点编号（样例的测试点编号为 $0$）。

对于每组测试数据数据，第一行两个正整数 $n,q$，表示序列长度与询问次数。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示序列 $a$ 中每个元素的值。

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

outputFormat:
输出到标准输出。

对于每组测试数据的每次询问，输出一行一个整数，表示区间 $[l,r]$ 内的最长合法子区间的长度。


title: 「DBOI」Round 1 未完成的约定

background:
>  _生活快得停不下来_\
_璀璨的也最终衰败_\
_他感到负荷已过载_\
_车窗外_\
_天上大朵云彩_\
_追随他的速度跑得飞快_\
_不由自主比赛_\
——《笨小孩的道歉信》

不管多少个日夜，为你一直唱。

description:
$m^3$ 可以表示为 $m$ 个连续奇数的和 $(m \geqslant 1)$：
$$
1^3 = 1\\
2^3 = 3 + 5\\
3^3 = 7 + 9 + 11\\
4^3 = 13 + 15 + 17 + 19\\
5^3 = 21 + 23 + 25 + 27 + 29\\
\cdots\cdots
$$

在左昂对奇数的狂热崇拜的影响下，苏信好写出来的歌只会是奇数长度。显然歌曲的长度不能是负数。

对于一首长度为 $x$ 的歌，它的悦耳值 $f(x)$ 满足将 $f(x)^3$ 按照上面的规律表示出来后，$x$ 是其中的一个加数。例如 $f(21) = 5, f(11) = 3,f(3) = 2$。

第二天，左昂前来参观，发现苏信好只写出来了一首歌，鄙夷不已。苏信好怒从心起，写出了以 $1\sim k$ 内所有长度为奇数的歌。

现在左昂想要知道苏信好所有歌的悦耳值之和，以预估他的狂热崇拜的效果。即：给定一个正奇数 $k(1\leqslant k< 2^{64})$，求 $s = \sum\limits_{i = 1}^{\frac{k + 1}{2}} f(2\times i - 1)$，即 $f(1) + f(3) + f(5) + \cdots +f(k)$。

由于苏信好实在太生气，写出来的歌的悦耳值可能十分之大，你只需要输出 $s\bmod{10^9 + 7}$ 的结果。

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

inputFormat:
为避免输入量过大，你需要使用下面的方式读入，因此请将这段代码复制到你的代码中。**下列程序与此题做法无关，请仔细阅读示例代码中的注释。**

```cpp
namespace Mker {
	typedef unsigned long long ull;
	ull SA, SB, SC, p = -1;
	int base;
	void init(){scanf("%llu%llu%llu%d", &SA, &SB, &SC, &base); p = p << (65 - base) >> (65 - base);}
	ull rand() {
		ull now = SC; now += !(now & 1);
	    SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
	    ull t = SA;
		return SA = SB, SB = SC, SC ^= t ^ SA, (now & p) + p + 1;
	}
}
```
先读入一个数 $T$，表示数据组数，然后你**需要调用** `Mker::init()`。这个函数将输入四个数 $SA,SB,SC,base$，表示对于这组数据，$k<2^{base}$。

接下来，对于每一组询问，你应当令 $k$ 的值即为 `Mker::rand()`。

示例代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
int T;

namespace Mker {
	typedef unsigned long long ull;
	ull SA, SB, SC, p = -1;
	int base;
	void init(){scanf("%llu%llu%llu%d", &SA, &SB, &SC, &base); p = p << (65 - base) >> (65 - base);}
	ull rand() {
		ull now = SC; now += !(now & 1);
	    SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
	    ull t = SA;
		return SA = SB, SB = SC, SC ^= t ^ SA, (now & p) + p + 1;
	}
}

int main() {
	scanf("%d", &T); Mker::init(); // 不要忘记 init
//	cout << Mker::base << endl; 你可以通过这种方式输出得到 base 的值
	while (T--) {
		unsigned long long k = Mker::rand(); // 通过这种方式，获得一次询问的 k
		if (k == 1) puts("1");
		else if (k == 17) puts("26");
		else puts("I AK IOI");

//		cout << k << endl; 你可以通过这种方式输出得到真实的 k 以调试代码
	}
	return 0;
}
```

outputFormat: $T$ 行，每行一个数 $s\bmod{10^9 + 7}$，其中 $s$ 表示苏信好的歌的悦耳值之和。


title: [语言月赛 202402] 酒

background: 在卷王开发的游戏里，出现了三个李白。他们到了一家小店一起喝酒。

description:
一小桶酒含有酒 $x$ 升，一大桶酒含有酒 $y$ 升。

编号为 $1$ 的李白先喝了 $a$ 小桶酒，然后喝了 $b$ 大桶酒。
编号为 $2$ 的李白喝了 $c$ 大桶酒。
编号为 $3$ 的李白喝了 $d$ 大桶酒，还喝了 $e$ 升酒。

请问哪个李白喝的酒最多？

inputFormat: 输入共一行七个浮点数 $a, b, c, d, e, x, y$。

outputFormat:
输出一行一个整数和一个浮点数，分别表示喝酒喝的最多的李白**编号**以及对应编号的李白**喝的酒的量**（单位为升，答案保留两位小数），输出的两个数字中间用一个空格隔开。

若有多个李白喝的酒一样多，那么输出编号最小的。

hint:
### 样例 1 解释

第一个李白喝了 $1\times 10 + 2\times 20= 50$ 升酒；第二个李白喝了 $3\times 20= 60$ 升酒；第三个李白喝了  $4\times 20+5= 85$ 升酒。第三个李白喝的酒最多，因此输出 `3 85.00`。

### 数据规模与约定

- 对于 $50\%$ 的数据，$0 < a, b, c, d, e, x, y \leq 10^3$。
- 对于 $100\%$ 的数据，$0 < a, b, c, d, e, x, y \leq 10^7$。

保证读入的浮点数小数点后位数不超过 $4$ 位。

由于小店允许存酒，因此李白们可以不完整喝完某些桶酒（喝一半，喝四分之三桶，喝 $\frac{1}{3.14 \cdots}$ 桶都是可以的），因此 $a, b, c, d$ 也有可能为小数。


title: 「DROI」Round 2 划分

background: 与其编写苍白无力的背景，不如出更有质量的题。

description:
给定长度为 $n$ 的序列 $A$。

定义序列 $A$ 的某个子段 $[L,R]$ 的权值为:

$$ \sum_{i=L}^{R}[\vert A_i - A_L \vert是完全平方数] \times \sum_{i=L}^{R}[\vert A_R - A_i \vert是完全平方数]$$

现在你需要将序列 $A$ **不重不漏**地划分成若干个子段，使得对于 $\forall i \in [1,n]$，长度为 $i$ 的子段有 $c_i$ 个。

在此基础上，求一种划分方案使所有子段权值和最大，输出这个最大值即可。特殊地，若不存在任意一种划分方案，则输出 `-1`。

**对题意不清楚的，可见下方说明提示。**

inputFormat:
首先输入一个整数 $n$，表示序列 $A$ 的长度。

然后输入一行 $n$ 个数，其中第 $i$ 个数表示 $A_i$。

最后再输入一行 $n$ 个数，其中第 $i$ 个数表示 $c_i$。

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

hint:
#### 样例解释
对于样例一，一种最优划分是分别在第二、三个数后面将序列断开。

对于样例二，一种最优划分是分别在第三、四、五、八个数后面将序列断开。

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

#### 数据范围

**「本题采用捆绑测试」**

- $\operatorname{Subtask} 1(10\%)$：$n \leq 20$。

- $\operatorname{Subtask} 2(20\%)$：$n \leq 50,\sum_{i=1}^{n}c_i \leq 20$。

- $\operatorname{Subtask} 3(20\%)$：$n \leq 50,\forall i>5,c_i=0$。

- $\operatorname{Subtask} 4(50\%)$：无特殊限制。

对于 $100\%$ 的数据：$0 \leq c_i\leq n \leq 120,1 \leq a_i \leq 10^4$。

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

#### 说明提示

- 我们规定，$0$ 是完全平方数。

- $[P]=1$ 当且仅当 $P$ 是真命题，否则 $[P]=0$。


title: [ZSHOI-R1] 有效打击

background: 打腻了原版的 Boss，FyFive 决定做一个 Hollow Knight Mod Boss，名字叫“成功冠军”。

description:
和原本的失败冠军类似，成功冠军也有一个不能回魂的大盔甲。但是成功冠军更难的地方在于：它的盔甲需要以特定的打击方式才能造成伤害，可以造成伤害的打击序列被称作“有效打击”。

作为 Mod Boss 的设计者，FyFive 设置了一个可以造成有效打击的“标准序列”。为了降低操作难度，当打击顺序与标准序列“相似”时，即可造成有效打击。在这里“相似”的定义是，对于一个打击序列，将所有相同打击的连续段的长度同时进行放缩，可以得到另一个序列，则称这两个序列是“相似”的。

例如：
- ``112244`` 和 ``111222444`` 是相似的，
- ``111333`` 和 ``13`` 也是相似的，
- ``226`` 和 ``226`` 也是相似的，
- ``33889`` 和 ``33388899`` 则不是相似的。

由于 Boss 还处在调整标准序列的阶段，所以 FyFive 将 Boss 的血量调到了无穷大，但这样他就没办法通过比较初始血量和最终血量来计算他的打击序列在当前标准序列下能造成多少次有效打击，所以请万能的你来帮帮 FyFive 吧！

**注意**：对于可能出现的同时造成多次有效打击的情况，会造成多次有效打击，比如当打击序列为 ``11`` 时，若标准序列为 ``1``，则这个打击序列会造成 $3$ 次有效打击，因为第一个 ``1`` 和第二个 ``1`` 均与标准序列相似，同时 ``11`` 也与标准序列相似。若标准序列为 ``11``则也有 $3$ 次有效打击。若标准序列为 ``12``，则不会造成有效打击。同理，当打击序列为 ``6666``，标准序列为 ``66`` 时，则一共会造成 $10$ 次有效打击。

#### 形式化的，
>定义：若序列 $\Alpha$ 为
> $$\underbrace{AA...A}_{a_1个}\underbrace{BB...B}_{a_2个}\underbrace{CC...C}_{a_3个}...$$
> 序列 $\Beta$ 为
> $$\underbrace{AA...A}_{b_1个}\underbrace{BB...B}_{b_2个}\underbrace{CC...C}_{b_3个}...$$
> 其中 $A,B,C,a_1,a_2,a_3,...,b_1,b_2,b_3,...\in N_+$。
>
> 若有 $\frac{a_1}{b_1}=\frac{a_2}{b_2}=\frac{a_3}{b_3}=...=k\ , k>0$，则称 $\Alpha$ 与 $\Beta$ 互为相似序列。
>
> 特别的，长度为 $0$ 的序列不与任何序列成相似序列。
>
> 不难证明此定义下序列间的相似具有传递性。

求给定的序列 $A$ 中有多少个子串与给定序列 $B$ 互为相似序列。

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

第二行 $n$ 个整数，表示打击序列 $A$，数之间用空格隔开。

第三行 $m$ 个整数，表示标准序列 $B$，数之间用空格隔开。

outputFormat: 一行一个正整数，表示造成的有效打击总数。


title: 「EZEC-14」浴眼盯真

background: 验题人提示：本题数据在 windows 下生成，即换行符为 ``\r\n``。

description:
dXqwq 定义一个字符串四元组 $(a,b,c,d)$ 是“浴眼盯真”的，当且仅当：

- $a,b$ 的首字母均为 $\texttt{y}$。
- $c$ 恰好等于 $\texttt{ding}$。
- $d$ 恰好等于 $\texttt{zhen}$。

给定四个用空格分隔的字符串 $a,b,c,d$，保证其只包含小写英文字母，你需要判断 $(a,b,c,d)$ 是否是“浴眼盯真”的。

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

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

接下来 $T$ 行，每行输入四个用空格分隔的字符串 $a,b,c,d$。

outputFormat:
对于每组数据输出一行。

如果 $(a,b,c,d)$ 是“浴眼盯真”的，输出 ``Yes``，否则输出 ``No``。

samples:
5
yi yan ding zhen
yu yan ding zhen
zheng tai ding zhen
yin yang guai qi
you xiu su zhi

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

前两组测试数据满足全部要求。

第三，五组测试数据不满足第一条要求。

第四，五组测试数据不满足第二，三条要求。

**【数据范围】**

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

- Subtask 1（50 pts）：保证输入的所有字符串长度均为 $4$。
- Subtask 2（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\leq T\leq 100$，每个字符串长度不超过 $10$。

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


title: Happybob's Magic (UBC001F)

description:
Happybob 正在游戏里研究一排灯，总共 $2^n$ 个，编号为 $0\sim 2^n-1$。Happybob 有两个技能。

一技能（按下 `B` 释放）释放一次，所有的灯亮变成灭，灭变成亮。

二技能（按下 `D` 释放）就厉害了，每释放一次，假设释放前的所有亮着的灯的编号组成的集合是 $X$，那么对于 $X$ 的**所有 $2^{|X|}$ 个子集（包含空集）** $Y$，Happybob 会把第 $\bigoplus(Y)$ 盏灯点亮。这里的 $|X|$ 表示 $X$ 集合的大小，$\bigoplus(Y)$ 表示将集合 $Y$ 的所有元素进行二进制按位异或得到的结果。特别地，$\bigoplus(\varnothing) = 0$。

现在有一个 `B`，`D` 构成的施法序列 $S(|S|=m)$（意义如上），一个灯的初始状态序列（第 $0$ 个版本）$a_0,a_1,\cdots,a_{2^n-1}$，以及一个变量 $vid=0$。Happybob 有 $q$ 次询问，每次询问可能是：

1. `1 v l r`：将 $vid$ 加 $1$，对第 $v$ 个版本依次执行 $S_l$ 到 $S_r$ 的施法操作，将结果存入第 $vid$ 个版本中，并问第 $vid$ 个版本中有多少盏灯是亮的。
2. `2 v k`：问第 $v$ 个版本的第 $k$ 盏灯是不是亮的。是输出 $1$，否则输出 $0$。
3. `3 v k`：设第 $v$ 个版本是从第 $v'$ 个版本执行了 $t$ 次施法操作变过来的，问有多少次施法操作之后，第 $k$ 盏灯是亮的（原来是亮的不算）。

对于第三种询问，这里的 $v'$ 和 $t$ 具体定义如下：假设进行某一次第一种询问后 $vid = v$，则 $v'$ 等于那一次询问给定的 $v$，$t$ 即那一次询问给定的操作序列 $S_{l\cdots r}$ 的长度。

保证 $0\le v\le vid$（如果是第一个操作，则是加 $1$ 前的 $vid$；如果是第三个操作，还保证 $v>0$）。

inputFormat:
第 $1$ 行，$3$ 个整数 $n,m,q$；

第 $2$ 行，$2^n$ 个整数 $a_0,a_1,\cdots,a_{2^n-1}$；

第 $3$ 行，$1$ 个字符串 $S$（下标从 $1$ 开始），对于每个满足 $1\le i\le m$ 的整数 $i$，如果 $S_i$ 是 `B`，那么表示 Happybob 释放了一次一技能，否则他释放了一次二技能；

接下来 $q$ 行，每行 $3$ 个或 $4$ 个非负整数，表示一个询问。

outputFormat: $q$ 行，第 $i$ 行一个整数，表示第 $i$ 个询问的结果。


title: 夕阳西下几时回

background: 随着夕阳从山间落下，最后一丝余晖逐渐暗淡；美丽的晚霞，终究还是化作一片黑夜。在这番景象中，一阵又一阵的乡愁涌上心头；远离家乡的游子，就算不是病死他乡，又何时能回还？

description:
夕阳可以被视作由 $n$ 种不同颜色组成的一副图，其中第 $i$ 种的颜色为 $a_i$，满足 $a$ 是长度为 $n$ 的排列。

定义一个排列的乡愁度为：

+ 对于所有 $1\le i\le n$，记 $b_i=\gcd(a_i,a_{i+1})$。特别地，我们认为 $a_{n+1}=a_1$。
+ 排列 $a$ 的乡愁度为序列 $b$ 中**不同**元素的个数。

求是否有一个长度为 $n$，乡愁度为 $k$ 的排列 $p$。若有解，请输出任意一个排列。

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

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

对于每组测试数据，一行两个整数 $n,k$。

outputFormat:
对于每组测试数据：

- 如果不存在这样的排列，输出一行一个字符串 `No`；
- 否则，输出一行一个字符串 `Yes`，然后输出一行 $n$ 个正整数 $p_1,p_2,\dots,p_n$，表示你找到的排列。

校验器忽略字符串大小写，例如，`YES`，`yEs`，`yes` 都会被视作答案存在。

hint:
**【提示】**

一个长度为 $n$ 的排列是一个满足 $1$ 到 $n$ 中的所有正整数恰好出现 $1$ 次的数组。例如，$[3,1,2]$ 是一个长度为 $3$ 的排列，而 $[5,5,1,2,3]$ 不是一个排列。

**【样例 1 解释】**

- 对于第一组数据，$b=[1,1,1,1,1,1,1]$，故 $p$ 的乡愁度为 $1$。
- 对于第二组数据，可以证明不存在这样的序列。
- 对于第三组数据，$b=[1,1,3,3,1,1,2,1,5,2,1]$，包含 $4$ 个不同的元素 — $1,2,3$ 和 $5$，故 $p$ 的乡愁度为 $4$。

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

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

-  Subtask 1（4 points）：$n\le 9$，$\sum n\le 100$。
-  Subtask 2（5 points）：$k=1$。
-  Subtask 3（13 points）：$\sum n\le 200$。
-  Subtask 4（30 points）：对于所有测试数据，保证有解。
-  Subtask 5（48 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$3\le n\le 3\times 10^5$，$1\le k\le n$，$\sum n \le 6\times 10^5$。


title: [语言月赛202304] 扶苏与 1

background:
扶苏在 ICPC2022 EC Final 的比赛里，开局不到五分钟，就读假了一道题，把一道数位 DP 开成了简单签到，狠狠地演了队友一把。

为了不让读假了的题被浪费，所以这道题出现在了这里。

description:
扶苏给了你一个数字 $x$，你需要给她一个数字 $y$，使得在列竖式计算 $x + y$ 时，能恰好产生 $k$ 个进位。

你给出的 $y$ 的**长度**不能超过 $10^4$。

**进位**的含义是：在进行竖式加法运算时，如果位于同一列上的数字之和（加上低位向上可能存在的进位）比 $9$ 大，则在结果的这一列上只保留这个和的个位数字，同时称这一位向它的高位产生了一个**进位**。

下图是一个竖式加法的例子，结果中标红的两位都向上产生了进位。

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

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

第一行为一个整数 $T$，代表测试数据组数。
接下来 $T$ 组数据，每组数据只有两行，每行一个整数。
第一行的整数表示 $x$。
第二行的整数表示 $k$。

outputFormat:
**本题采用 special judge 进行判题**。

对每组数据，输出一行一个整数，表示你给出的 $y$。

如果有多个满足要求的 $y$，你可以输出任何一个。但是必须保证如下三条限制：
- $y$ 是正整数。
- $y$ 不含前导 $0$。
- $y$ 的长度不超过 $10^4$。

特别的，如果这样的 $y$ 不存在，请你输出一行一个 $\texttt{-1}$。

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

- 对 $30\%$ 的数据，保证 $x < 10$，$k = 1$。
- 对 $70\%$ 的数据，保证 $x < 10^6$。
- 对 $100\%$ 的数据，保证 $0 \leq x < 10^{(10^3)}$，$1 \leq T \leq 5000$，$1 \leq k \leq 1+\log_{10}\max(1,x)$。输入的 $x$ 不含前导 $0$。

### 提示

输入的 $x$ 可能会很大。如果说 $x < 10^t$，则输入 $x$ 的**长度**不会超过 $t$。数据规模中式子 $k \leq 1 + \log_{10}\max(1,x) $ 的含义是：$k$ 不会超过 $x$ 的长度。


title: 「QMSOI R1」 转转楼梯

background: 题目描述就是最好的题目背景（）。

description:
同学们每天都要做操，而做操会经过转转楼梯。

转转楼梯有 $n+1$ 阶楼梯，对于第 $i(1\le i\le n+1)$ 阶转转楼梯，其有一个转转值 $a_i$ 且 $a_i\in\{0,1\}$，特别的，$a_{n+1}=0$。

对于一阶转转楼梯，如果其下一阶楼梯的转转值与之相同（即 $a_{i+1}=a_i$）那么我们可以直接走下去，耗费一秒。否则我们需要耗费一秒转一圈以改变目前这阶楼梯的转转值为 $1-a_i$。然后再耗费一秒走下去。

我们需要做 $k$ 天课间操。每天要从第 $1$ 阶楼梯走到第 $n+1$ 阶楼梯。

请求出这 $k$ 天同学们经过转转楼梯的总时间。

inputFormat:
输入共 $2$ 行。

第一行两个数 $n$ 和 $k$。

第二行 $n$ 个整数，第 $i(1\leq i\leq n)$ 个数代表 $a_i$。

outputFormat: 一行一个整数，代表这 $k$ 天我们一共会花费多少时间在转转楼梯上。


title: [语言月赛202304] 移植柳树

background: HG 在上学的路上无聊的走着，看着这马路边的一排柳树，他的脑子里突然冒出了个奇怪的问题……

description:
假设总共有 $n$ 棵柳树，每一棵间隔都为 $x$。

现在他需要对这些树做一些操作，使得在「这 $n$ 棵树的起点不变」的同时，任意两棵树的间隔都为 $y$（$y > x$）。

他被允许做的操作如下；

1. 移除树木：直接删除某个位置的树木。
2. 移植树木：将一个位置的树木移到另一个位置上。

增加树木（凭空生成一棵树木）是不允许的。如果对「起点不变」这个概念有疑惑，可以参照「样例解释」中的图例。

显然操作是需要体力的，HG 想要让尽可能多的树维持原状。现在 HG 想知道，为了达成「任意两棵树的间隔都为 $y$」这个目标，他最多可以让多少棵树保持在原来的位置。

请你帮帮他吧！

inputFormat: 输入共一行三个整数 $n, x, y$，依次表示柳树的数量，未调整前每棵的间隔，想要达成的每棵的间隔。

outputFormat: 输出共一行一个整数，表示为了达成「任意两棵树的间隔都为 $y$」的目标，他最多可以让多少棵树保持在原来的位置。

hint:
### 样例 1 解释

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

图中的方块代表树。第一行为调整前，第二行为调整后的情况。标出的三个绿色的方块是不需要移动的树，除此之外其他树都需要移动或者删除。

### 数据规模与约定

对于 $10\%$ 的数据，保证 $n \leq 10$，$x = 1$，$y = 2$。
对于 $20\%$ 的数据，保证 $n \leq 10^3$，且 $y$ 是 $x$ 的倍数。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^6$，$1 \leq x < y \leq 10^6$。


title: [语言月赛202304] 洛谷评测机模拟器

background: 现在假装你是洛谷评测机。这一天，洛谷同时进行了 PION 自测、SCP 自测、ION 自测等等比赛。成千上万的评测落到了你的身上！

description:
现在已经知道你有 $n$ 个相同性能的评测节点，它们被分别标号为 $1, 2, \cdots, n$。一个评测节点在同一时间只能处理一个评测任务。

在某一时刻，$m$ 个评测任务同时涌入了你。我们将这些任务分别标号为 $1, 2, \cdots, m$。这些评测任务需要的评测时间分别为 $t _ 1 , t _ 2, \cdots, t _ m$。每个评测任务**需要且仅需要一个**评测节点来运行，因此你会按照如下方式按照 $1 \sim m$ 的顺序依次将这些评测任务分配到评测节点上：

对于某个耗时 $t _ i$ 的评测任务，你需要找到目前**累积评测时间**最小的评测节点将任务放入。如果有多个评测节点**累积评测时间**相同且最小，则找一个**标号最小**的节点将任务放入。

> 「累积评测时间」定义：假设对于某个评测节点，其被分配了 $a _ 1, a _ 2, \cdots, a _ k$ 共 $k$ 个任务。那么这个评测节点的「累积评测时间」就是 $t _ {a _ 1} + t _ {a _ 2} + \cdots + t _ {a _ k}$。显然的，如果某个评测节点从未被分配过这 $m$ 个任务中的任何一个，那么这个评测节点的「累积评测时间」是 $0$。

现在，你需要统计出，你的这 $n$ 个评测节点分别接受了哪一些评测任务。

inputFormat:
输入共两行。

第一行为两个整数 $n, m$，代表评测节点数量和评测任务数量。
第二行为 $m$ 个整数 $t _ 1, t _ 2, \cdots, t _ m$，依次代表这 $m$ 个评测任务的所需时间。

outputFormat:
输出共 $n$ 行，每行若干个整数，两两之间以一个空格隔开。

对于第 $i$ 行，输出第 $i$ 个评测节点接受的评测任务编号从小到大排序后的结果。如果第 $i$ 个评测节点没有被分配任务，那么输出一行一个 $0$。


title: [入门赛 #11] 洛谷评测机模拟器 (Hard Version)

background:
**本题与 Easy Version 题意完全相同，不同的地方在于数据范围。**

现在假装你是洛谷评测机。这一天，洛谷同时进行了 PION 自测、SCP 自测、ION 自测等等比赛。成千上万的评测落到了你的身上！

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

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 5 \times 10 ^ 5$，$0 \leq t _ i \leq 10 ^ 9$。


title: [入门赛 #11] 移植柳树 (Hard Version)

background:
**本题与 Easy Version 题意完全相同，不同的地方仅在于数据范围和单个测试点内含有的测试组数量。**

HG 在上学的路上无聊的走着，看着这马路边的一排柳树，他的脑子里突然冒出了个奇怪的问题……

description:
假设总共有 $n$ 棵柳树，每一棵间隔都为 $x$。

现在他需要对这些树做一些操作，使得在「这 $n$ 棵树的起点不变」的同时，任意两棵树的间隔都为 $y$（$y > x$）。

他被允许做的操作如下；

- 移植树木：将一个位置的树木移到另一个位置上。

如果对「起点不变」这个概念有疑惑，可以参照「样例解释」中的图例。

显然操作是需要体力的，HG 想要让尽可能多的树维持原状。现在 HG 想知道，为了达成「任意两棵树的间隔都为 $y$」这个目标，他最多可以让多少棵树保持在原来的位置。

请你帮帮他吧！

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

输入共 $T + 1$ 行。

第一行为一个整数 $T$，代表测试数据组数。
接下来 $T$ 行，每行三个整数 $n, x, y$，依次表示柳树的数量，未调整前每棵的间隔，想要达成的每棵的间隔。

outputFormat: 输出共 $T$ 行，每行一个整数，表示对于对应的输入数据，为了达成「任意两棵树的间隔都为 $y$」的目标， HG 最多可以让多少棵树保持在原来的位置。

hint:
### 样例 1 解释

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

图中的方块代表树。第一行为调整前，第二行为调整后的情况。标出的三个绿色的方块是不需要移动的树，除此之外其他树都需要移动。

### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq T \leq 10 ^ 5$，$1 \leq n \leq 10 ^ {18}$，$1 \leq x < y \leq 10 ^ 9$。


title: [语言月赛202304] 冠军

description:
某校举行足球比赛，将从 $16$ 强中决出冠军。

以下是 $\dfrac{1}{8}$ 决赛的对阵图：

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

在蓝色方框中的数字代表场序数，队伍依次用字母 $\texttt{A} \sim \texttt{P}$ 编号，规定一场比赛字母更靠前的队伍为主场队伍，更靠后的队伍为客场队伍。比分用 `p-q` 的形式给出，$p$ 为主队的进球数，$q$ 为客队的进球数。进球更多的队伍晋级下一轮比赛。

例如，对于场序 $1$ 和 $2$，若比分分别为 $1-2$，$4-3$，则 B 队 和 C 队将晋级下一轮比赛，他们将在场序 $9$ 碰面，且 B 队为主队。

现在，按照场序顺序给出 $15$ 场比赛的比分，问冠军是哪一队？

inputFormat: 输入 $15$ 行，第 $i$ 行为场序 $i$ 的比分，保证比赛没有平局。

outputFormat: 输出一行一个字符，代表冠军队。

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

对于 $30\%$ 的数据，$p,q \in \{0,1\}$；
对于 $100\%$ 的数据，$0 \le p,q \le 100$。

### 提示

你可以通过下面的代码读入本题中两个整数用横线连线的格式。

```cpp
scanf("%d-%d", &p, &q);
```


title: [语言月赛202304] 排名

description:
ICPC 比赛中，决定两个队排名的是通过题目数和罚时。

比较两个队排名先后的具体步骤如下：

- 首先比较两个队通过题目数。若不同，则通过数更多者排名更靠前。
- 若两队通过题目数相同，比较两个队罚时。若不同，则罚时更小者排名更靠前。
- 若通过题目数与罚时均相同，则两队排名相同。**本题保证不存在这种情况。**

现在给出两个队伍的通过数和罚时，你需要判断哪个队伍排名更靠前。

inputFormat:
输入共两行。

输入的第一行为两个整数 $A_1,P_1$，分别代表第一个队的通过数和罚时。

输入的第二行为两个整数 $A_2,P_2$，分别代表第二个队的通过数与罚时。

outputFormat:
输出一行一个字符串。

若第一个队排名更靠前，输出 `"\n"`（包含引号）。

若第二个队排名更靠前，输出 `"\t"`（包含引号）。

**提示：**

输出一个 `"` 的方式为 `cout << "\"";`

输出一个 `\` 的方式为 `cout << "\\";`


title: [NAPC-#1] Stage1 - Simple

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

description:
### 【简要题意】
给定 $n,m,k,S$，请构造长度为 $n$ 的整数序列 $a$ 使得：
- $0\leqslant a_i\leqslant m,\forall i\in[1,n]$（即序列 $a$ 内的每个元素均不小于 $0$ 且不大于 $m$）。
- $|a_i-a_{i-1}|\leqslant k,\forall i\in(1,n]$（即序列 $a$ 内的每两个相邻元素之差的绝对值均不大于 $k$）。
- $(\sum_{i=1}^n a_i ) = S$（即序列 $a$ 内的所有元素的和为 $S$）。

**保证有解。**

### 【原始题意】

前面忘了，但是~~你随 kid 穿越到了 ic~~（I wanna be the Creator），来到了一个关卡编辑器面前。该地图宽为 $n$，高为 $(m+1)$，是你不能修改的；里面还有 $S$ 个 $1\times1$ 大小的未摆放的砖。现在你需要帮 kid 摆好这一面，也就是说，将这 $S$ 个砖摆放好，使得他可以通过。有以下要求：

1. ~~砖是有重力的~~，所以**一块砖只能摆放在下边界上或者另一块砖上**。同一横纵坐标不能摆放多块砖。
2. 你至少要给 kid 留一条缝来通过，所以每一列你最高只能放 $m$ 块砖（地图高度为 $m+1$）。但是注意，ic 关卡下边界没有伤害，某一列是可以不放砖块的。
3. kid 的跳跃能力和~~从高处坠落而不受伤的能力~~是有限的，这用一个非负整数 $k$ 来描述：相邻两列摆放的砖的数量之差的绝对值不能超过 $k$，否则该关卡对 kid 来说就是无解的。_（但是注意：该条对第一列高度没有要求，kid 出生点就在第一列。）_
4. 你要把所有 $S$ 块砖都摆进去，不多不少。

Creator 不会为难你，因此一定有一种关卡符合上述所有规则。

为了输出方便，你只需要给出第 $i$ 列有多少砖块（记为 $a_i$），输出 $a$ 序列即可。容易证明，一个合法的 $a$ 序列和一个合法关卡是一一对应的。

inputFormat: 仅一行 $4$ 个非负整数 $n,m,k,S$。

outputFormat: 输出一行 $n$ 个非负整数表示你构造的序列 $a$。如果有多种可能的序列，输出任意一个符合题意的序列即可。**保证至少有一个序列满足题目要求。**

hint:
### 【数据范围】

该题共有 $10$ 个测试点，每个测试点等分。

- 对于 $20\%$ 的数据，$S=n\cdot m$。
- 对于 $20\%$ 的数据，$k=0$。
- 对于 $20\%$ 的数据，$k=10^9$。

对于 $100\%$ 的数据，$1\leqslant n,m\leqslant 10^5$，$0\leqslant k\leqslant 10^9$，$0\leqslant S\leqslant n\cdot m$。

### 【提示】
> 古之有数，其名为 $S$。$S$ 之大，一个 `int` （可能）装不下。

### 【样例解释 #1】
样例输出对应关卡如下。

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

注意可能有多种合法关卡均符合条件。


title: [NAPC-#1] Stage2 - Darkness

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

description:
有 $n$ 支军队分布在各地，可以看作在一个平面直角坐标系内。他们都受 kid 的统一指挥，kid 共发出 $m$ 条命令。

命令有如下几种：

- `1 p q` 表示把**每支**军队的位置从 $(x_i,y_i)$ 移到 $(x_i+p,y_i+q)$。
- `2 i`，表示**第 $i$ 支军队**的位置对直线 $y=x$ 作轴对称变换（即交换 $x_i$ 与 $y_i$ 的值）。
- `3 i`，表示查询第 $i$ 支军队现在所处的位置（即输出此时的 $x_i$ 与 $y_i$）。

**请注意 `1` 与 `2` 命令的操作对象不同，前者为全体军队，后者为单支军队。**

本来 kid 可以直接拿望远镜看的，但是天太黑了，只能拜托你编写一个程序告诉他了。

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

接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$ 表示第 $i$ 支军队的初始位置 $(x_i,y_i)=(a_i,b_i)$。

接下来 $m$ 行，每行两到三个整数，表示 kid 发出的一条命令。具体地，对于每条命令，先有一个正整数 $op$ 表示命令类型；

- 如果 $op=1$，那么后面有两个整数 $p,q$，表示把**每支**军队的位置从 $(x_i,y_i)$ 移到 $(x_i+p,y_i+q)$。
- 如果 $op=2$，那么后面有一个正整数 $i$，表示**第 $i$ 支军队**的位置对 $y=x$ 做轴对称变换。
- 如果 $op=3$，那么后面有一个正整数 $i$，表示查询第 $i$ 支军队现在所处的位置。

outputFormat: 对于每次 kid 发出的一条 `3` 命令，输出一行两个整数 $x_i,y_i$ 表示第 $i$ 支军队现在所处的位置。


title: [NAPC-#1] Stage3 - Jump Refreshers

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

description:
**注意本题中 kid 的移动方式与 iw 游戏中不同（）。**

kid 面前有一个无穷大的竖直二维平面。坐标系 $x$ 轴正方向为从左到右，$y$ 轴正方向为从下到上。

地图（该平面）内有 $n$ 个**位置互不相同**的**可以无限重复使用**的跳跃球。当 kid 正好位于某跳跃球位置时，他可以让 shift 键按下，然后他会瞬间上升 $d$ 格（此期间不能左右移动）。他每秒往下坠落 $1$ 格，同时每秒 kid 可以选择：向左或向右移动 1 格，或者不移动。当 kid 不在跳跃球上时他不能起跳。

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

上图是一个例子，蓝色区域表示 kid 在跳跃球（箭头）处起跳（$d=2$）后可以达到的区域。**kid 每秒时的横纵坐标只能是整数，即：我们认为他不能达到非整点位置。**

现在，kid 把存档放在了第 $c$ 个跳跃球处（即起点是第 $c$ 个跳跃球处；此时可以立即起跳）。定义 kid 的得分为他经过（即在某处起跳：显然起跳之后可以回到原位置）的**不同**跳跃球的个数。kid 想知道他可以最多获得多少得分（**不需要**（但可以）**回到起点**），请你告诉他吧。

再次提醒：**跳跃球可以无限重复使用，即 kid 可以在某个跳跃球上无限起跳。**

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

第一行仅两个整数 $T,id$ 表示测试数据的数量和测试点编号。特别地，样例的 $id=0$。

对于每组测试数据：

第一行三个正整数 $n,d,c$ 含义如上所述。

后 $n$ 行每行两个正整数 $x_i,y_i$ 表示第 $i$ 个跳跃球的位置。

outputFormat: 对于每组测试数据输出一行一个正整数表示最大得分。

hint:
### 【数据范围】

**本题采用捆绑测试。**
$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c|c}
\textbf{Subtask} & id= & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1& 1\sim3,36 & n\leqslant10,T\leqslant10 & 10 \r
\textsf2& 4\sim7 & \sum n\leqslant200 & 15 \r
\textsf3& 8\sim13 & \mathbf A & 25 \r
\textsf4& 14\sim18 & \mathbf B & 10 \r
\textsf5& 19\sim35 & - & 40 \r
\end{array}
$$
其中 $\sum n$ 表示单测试点内所有 $n$ 的总和。

$id=1\sim3,36$ 表示 $id\in\{1,2,3,36\}$。
- 特殊性质 $\mathbf A$：保证对于任意不同跳跃球 $u,v$，如果 kid 理论上能从 $u$ 跳到 $v$（理论上：不考虑 kid 能否从起点到达 $u$ 的问题，下同），那么他理论上**一定不可以**从 $v$ 跳到 $u$。
- 特殊性质 $\mathbf B$：保证对于任意跳跃球 $u,v$，如果 kid 理论上能从 $u$ 跳到 $v$，那么他理论上**一定可以**从 $v$ 跳到 $u$。

注意上面的“从 $u$ 跳到 $v$"不一定非得一跳到位。比如样例 #1-2 中可以从第 $3$ 个跳到第 $5$ 个：$3\to2\to4\to5$。

对于 $100\%$ 的数据，$1\leqslant T\leqslant 1000$，$1\leqslant n\leqslant 3000$，$\sum n\leqslant 3000$，$1\leqslant d\leqslant 10^9$，$1\leqslant c\leqslant n$，$1\leqslant x_i,y_i\leqslant10^6$，$(x_i,y_i)$ 互不相同。

---
#### 【样例解释 #1-1】
![](https://cdn.luogu.com.cn/upload/image_hosting/zpc7sm2i.png)

$d=2$，容易发现离开初始位置就上不去了。所以 kid 要么往左边碰第 $2$ 个跳跃球，得分为 $2$；要么往右边跳，经过第 $3$ 和第 $4$ 个跳跃球，得分为 $3$。
#### 【样例解释 #1-2】
![](https://cdn.luogu.com.cn/upload/image_hosting/q8ks8qb4.png)

$d=3$，kid 可以先往下走一圈（$4\to3\to2\to4$）跳回起点，然后往右去碰第 $5$ 个球。左上角的第 $1$ 个跳跃球是碰不到的。
#### 【样例解释 #1-3】
![](https://cdn.luogu.com.cn/upload/image_hosting/akghkpe9.png)

通过最上面那个球是可以跳到右边的。
#### 【样例解释 #1-4】
![](https://cdn.luogu.com.cn/upload/image_hosting/50smzomm.png)

有 的 人 。


title: [NAPC-#1] Stage4 - Needle

background:
> ![](https://cdn.luogu.com.cn/upload/image_hosting/jiio1vp7.png)
>
> — s10

description:
平面上有 $n$ 个**位置互不相同**的刺。刺有上下左右这 $4$ 种朝向。

定义一个【阴间刺】（其实就是削过的 sf 刺）为满足以下条件的有序刺**对** $(s_1,s_2,s_3)$：
- $s_1$ 朝右，$s_2$ 朝左，$s_3$ 朝上。
- $x(s_1)<x(s_2)\leqslant x(s_3)$。
- $y(s_2)>y(s_1)>y(s_3)$。
- $x(s_2)-x(s_1)\leqslant d$。

其中 $x(s)$ 和 $y(s)$ 分别表示刺 $s$ 的横坐标和纵坐标；$d$ 为 kid 的宽度，在单组测试点中为常量。

坐标系 $x$ 轴正方向为从左到右，$y$ 轴正方向为从下到上。

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

上图是 $d\geqslant 2$ 时两个阴间刺的例子。~~虽然第二个刺型中 s3 对 kid 的跳跃没有影响/oh~~

给出 $n$ 个刺的位置和朝向，请你告诉 kid 有多少（他跳不过去的）阴间刺。

显然朝下的刺在本题内是没有意义的。

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

第一行仅两个正整数 $T,id$ 表示测试数据的数量和测试点编号。特别地，样例的 $id=0$。

对于每组测试点，第一行输入两个正整数 $n,d$，表示刺的数量和 kid 的宽度，接下来 $n$ 行每行两个整数 $x,y$ 和一个字符 $c$ 表示一个刺的位置和朝向：`U` 代表朝上，`D` 代表朝下，`L` 代表朝左，`R` 代表朝右。

outputFormat: 对于每组测试点，输出一行一个正整数表示阴间刺的数量。

samples:
见附件中的 s4/ex.in
见附件中的 s4/ex.out

hint:
### 【数据范围】

**本题采用捆绑测试。**
$$
\def\r{\cr\hline}
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c}
\textbf{Subtask} & id= & {\sum n\leqslant} & \textbf{Other Constraints} & \textbf{Score}\r
\textsf1 & 1\sim 7 & 3\times10^4 & n\leqslant 30 & 10 \r
\textsf2 & 31\sim45 & 10^4 & - & 25 \r
\textsf3 & 8\sim10,16\sim17 & 10^5 & d=10^9 & 20 \r
\textsf4 & 18\sim20 & 3\times10^5 & d=1 & 10 \r
\textsf5 & 11\sim15,21\sim30 & 3\times10^5 & - & 35 \r
\end{array}
$$

其中 $\sum n$ 表示单测试点内所有 $n$ 的总和。

对于 $100\%$ 的数据，$1\leqslant T\leqslant 2\times10^3$，$1\leqslant n\leqslant 3\times10^5$，$\sum n\leqslant 3\times10^5$，$1\leqslant d\leqslant 10^9$，$1\leqslant x,y\leqslant 10^9$，$(x,y)$ 互不相同，$c\in\{\texttt U, \texttt D, \texttt L, \texttt R \}$。

#### 【提示】

$\textbf{Sub}{\textsf2}$ 的 $O(n^2\log n)$ 做法和 $O(n^2)$ 做法都可以想想，可能都有些提示性……？qwq

### 【样例 #1-1 & #1-2 解释】

见【题目描述】中**两**幅图。

注意 #1-2 中 $d=1$，所以 kid 可以简单地钻缝过去，不算阴间。

### 【样例 #1-3 解释】

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

$4$ 个阴间刺分别为：$\Big((1,3),(2,4),(2,1)\Big),\Big((1,2),(2,4),(2,1)\Big),\Big((1,2),(2,3),(2,1)\Big),\Big((1,3),(2,4),(3,2)\Big)$
即 $(5,6,1),(2,6,1),(2,4,1),(5,6,3)$（数字代表刺的下标：$i$ 代表第 $i$ 个刺）。

### 【样例 #1-4 解释】

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

$6$ 个阴间刺分别为 $(2,1,7),(4,1,7),(4,3,6),(4,3,7),(4,3,8),(5,3,8)$。

【样例 #2】见附件，该样例除 $id=0$ 外满足 $\text{Subtask }\textsf1$ 的所有限制。


title: [NAPC-#1] Stage5 - Conveyors

background:
>![](https://cdn.luogu.com.cn/upload/image_hosting/4wcng8qe.png)
>
>— rs8

description:
### 【简要题意】

给定一棵 $n$ 个节点的无根树以及树上的 $k$ 个关键节点，边有边权（即边的长度）。$q$ 次询问，每次给出 $s,t$，问从 $s$ 到 $t$ 且经过至少一次**每个**关键节点的路径的最短长度。

### 【原始题意】

在某一面 kid 又遇到了往返跑关卡。Really popular apparently.

关卡给 kid 留下的空间形状是一棵无向带权树，边权即边的长度。这棵树有 $n$ 个节点，其中有 $k$ 个点上各**恰**有一个发光小球，kid 经过有小球的点（称为关键点）时就可以收集小球。kid 从 $s$ 点出发，当他收集到全部 $k$ 个小球时，传送门就会在 $t$ 点出现。

想速通的 kid 想知道他从 $s$ 点出发收集到全部 $k$ 个小球并进入位于 $t$ 点的传送门所需要走的最小时间（其实也就是路径长度，因为 kid 的速度恒定）。

但是 Geezer 很狡猾，塔内这一面被复制成了 $q$ 层，每层的 $s$ 和 $t$ 还可能有变动。kid 慌了，忙找到你求助。

inputFormat:
第一行三个正整数 $n, q, k$，表示树的节点个数，询问次数和关键节点个数。

接下来 $n-1$ 行，每行三个正整数 $u, v, w$，表示树中存在边 $(u, v)$，边权为 $w$。保证输入构成一棵树。

接下来一行 $k$ 个两两不同的正整数，表示关键节点的编号。

接下来 $q$ 行，每行两个正整数 $s, t$，表示一次询问。

outputFormat:
对于每次询问输出一行一个非负整数，表示此次询问的最短合法路径长度。

注意，合法路径可以不经过任何边，此时路径长为 $0$。

hint:
### 【数据范围】

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

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c|c}
\textbf{Subtask} & \text{测试点编号} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1&1\sim14 & n\leqslant15,\mathbf R& 18 \r
\textsf2&15\sim20 & q=1 & 18 \r
\textsf3&46\sim48 & s=t,k=n & 6 \r
\textsf4&21\sim25 & k=n & 18 \r
\textsf5&26\sim30 & \mathbf A & 18 \r
\textsf6&31\sim45 & - & 22 \r
\end{array}
$$
友情提醒：$\text{Subtask }\textsf1$ 并没有限制 $q$ 的范围。

- 特殊性质 $\mathbf R$：保证树随机生成（对于 $i\ge2$，在 $[1,i)$ 内随机选择一个点和 $i$ 连边，边权在一固定区间内均匀随机生成）。
- 特殊性质 $\mathbf A$：定义 $f(x)$ 表示存在 $i,j\in[1,n]$（可能 $i=j$） 且 $i,j$ 均为关键点，使得 $x$ 在 $i$ 到 $j$ 的最短路径上；那么对每次询问保证 $f(s)$ 和 $f(t)$ 均成立。

对于 $100\%$ 的数据，$1\leqslant n\leqslant 10^5$，$1\leqslant q\leqslant 10^5$，$1\leqslant k\leqslant n$，$1\leqslant w\leqslant 10^4$，$1\leqslant u,v,s,t\leqslant n$。

### 【样例解释 #1】
![](https://cdn.luogu.com.cn/upload/image_hosting/3hvr33bz.png)

图中加粗节点表示关键点。

对于每组询问，以下为一种最优路径（最优路径可能有多条）：
1. $2\to1\to3$。
2. $2\to1\to3\to1$。
3. $7\to1\to2\to1\to3\to1$。
4. $4\to3\to1\to2\to1\to3\to5$。
5. $6\to2\to1\to3\to1\to2\to6$。


title: [语言月赛202304] 写大作业

description:
扶苏为了写计算理论大作业已经 $36$ 小时没有合眼了。

为了能快点睡觉，扶苏找到了 $n$ 份文献，第 $i$ 份文献是一个字符串 $s_i$，她打算把这些文献组合起来。

具体来说，一共有两种操作：

- `1 x y`：把文献 $s_x$ 整体拼接到 $s_y$ 的后面，然后删除 $s_x$。
- `2 x y`：查询 $s_x$ 和 $s_y$ 是否**相似**。

我们保证在 `1 x y` 操作出现后，字符串 $s_x$ **不会**出现在接下来的任何操作中。这就是说，操作 $1$ 至多有 $n-1$ 次。

**相似**的定义是：对两个字符串 $s_x$ 和 $s_y$，如果存在一种重新排列 $s_x$ 的方法，使得重排后的 $s_x$ 和 $s_y$ 相等，则称 $s_x$ 和 $s_y$ **相似**。

例如，假设 $s_1 = \texttt{ab}, s_2 = \texttt{cd}, s_3 = \texttt{abcd}$，则执行 `1 1 2` 后，$s_1$ 被删除，$s_2 = \texttt{cdab}, s_3 = \texttt{abcd}$；继续执行 `2 2 3` 后，因为可以把 $s_2$ 重排为 $\texttt{abcd}$，所以 $s_2$ 和 $s_3$ 相似。

注意，操作 $2$ 不会对字符串做出实际修改。

inputFormat:
第一行是两个整数，分别表示文献的数量 $n$ 和操作的数量 $q$。
接下来 $n$ 行，每行一个字符串，第 $i$ 行的字符串表示 $s_i$。
接下来 $q$ 行，每行三个整数 $op, x, y$，其含义见『题目描述』。

outputFormat: 对个操作 $2$，输出一行一个字符串。如果 $s_x$ 和 $s_y$ 相似，则输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

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

- 对 $30\%$ 的数据，保证 $n = 2$，$q = 1$。
- 对 $60\%$ 的数据，保证 $n \leq 6$，$q \leq 6$，$|s_i| \leq 6$。
- 对 $100\%$ 的数据，保证 $2 \leq n \leq 10^5$，$1 \leq q \leq 10^6$，$1 \leq o \leq 2$，$1 \leq x, y \leq n$，且输入字符串的总长度不超过 $10^6$，输入字符串仅含小写英文字母，且不是空串。


title: [入门赛 #11] 写大作业 (Hard Version)

background: **本题与 Easy Version 的区别在于：输入的是数列而不是字符串，输入输出格式不同，数据规模不同**。

description:
扶苏为了写计算理论大作业已经 $36$ 小时没有合眼了。

为了能快点睡觉，扶苏找到了 $n$ 份文献，第 $i$ 份文献是一数列 $a_i$，她打算把这些文献组合起来。

具体来说，一共有两种操作：

- `1 x y`：把文献 $a_x$ 整体拼接到 $a_y$ 的后面，然后删除 $a_x$。
- `2 x y`：查询 $a_x$ 和 $a_y$ 是否**相似**。

我们保证在 `1 x y` 操作出现后，数列 $a_x$ **不会**出现在接下来的任何操作中。这就是说，操作 $1$ 至多有 $n-1$ 次。

**相似**的定义是：对两个数列 $a_x$ 和 $a_y$，如果存在一种重新排列 $a_x$ 的方法，使得重排后的 $a_x$ 和 $a_y$ 相等，则称 $a_x$ 和 $a_y$ **相似**。

例如，假设 $a_1 = 1,2$, $a_2 = 3,4$，$a_3 = 1,2,3,4$，则执行 `1 1 2` 后，$a_1$ 被删除，$a_2 = 3,4,1,2$，$s_3 = 1,2,3,4$；继续执行 `2 2 3` 后，因为可以把 $a_2$ 重排为 $1,2,3,4$，所以 $a_2$ 和 $a_3$ 相似。

注意，操作 $2$ 不会对数列做出实际修改。

inputFormat:
第一行是两个整数，分别表示文献的数量 $n$ 和操作的数量 $q$。
接下来 $n$ 行，每行描述一个数列。第 $i$ 行描述 $a_i$：
每行第一个数是 $m_i$，表示数列 $a_i$ 的长度，接下来有 $m_i$ 个数，描述数列 $a_i$。
接下来 $q$ 行，每行三个整数 $op, x, y$，其含义见『题目描述』。

outputFormat:
为了避免输出过大，请你输出一行一个整数，表示所有答案为**两数列相似**的询问的**操作编号**的按位异或和。

操作的编号从 $1$ 开始，两种操作均会令编号增加 $1$。你可以参考样例解释来理解输出格式。

hint:
### 样例解释

共有五次操作，它们的编号和回答情况如下：
| 编号 | 操作 | 回答 |
| :-: | :-: | :-: |
| $1$ | `1 1 2` | 不是查询操作|
| $2$ | `2 2 3` | 相似 |
| $3$ | `2 3 4` | 不相似 |
| $4$ | `2 2 4` | 不相似 |
| $5$ | `2 2 3` | 相似 |

可以看到，回答为**两数列相似**的询问的操作编号为 $2$ 和 $5$。它们的按位异或和是 $7$。故输出为 $7$。

### 数据规模与约定

对全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq q \leq 5 \times 10^6$，$1 \leq m_i \leq 10^5$，$\sum_{i = 1}^n m_i \leq 5 \times 10^5$。数列里的元素都是不超过 $10^9$ 的非负整数。

数据保证数列元素的生成方式是：对一个数列，限定一个该数列元素大小的上界 $k$，然后在 $[0, k]$ 内均匀随机地生成 $m_i$ 个整数作为数列 $a_i$。注意，$k$ 不一定是 $10^9$。


title: [语言月赛202304] Matrix

background:
Matrix 是电影《黑客帝国》的英文名称，同样也是英文名词「矩阵」。

这是一道 **hack 题**。在此类型的题目中，你将得到**一个**问题和**一个**解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于这一问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

---
**提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言。**

description:
以下给出这道题目的叙述：

假设你处在一个 $N \times N$ 的矩阵中。矩阵左上角坐标为 $(1, 1)$，右下角坐标为 $(N, N)$。矩阵中的每个位置 $(i, j)$ 都有两个权值 $a _ {i, j}$，$b _ {i, j}$。

我们定义两点 $(x _ 1, y _ 1)$，$(x _ 2, y _ 2)$ 之间的「距离」为曼哈顿距离，即「距离」$ = |x _ 1 - x _ 2| + |y _ 1 - y _ 2|$。

我们定义你获胜，当且仅当你处在一个位置 $(x _ 0, y _ 0)$，满足这个位置与 $(N, N)$ 间的「距离」小于等于 $2$。

初始时你处在矩阵的左上角$(1, 1)$，且你手头有无限个金币。在矩阵中的每个坐标处，你可以无限次地进行如下两种操作：（假设目前你所在的坐标是 $(i, j)$）

- 花费 $a _ {i, j}$ 个金币，向右移动一格（列坐标 $j$ 增加 $1$）。
- 花费 $b _ {i, j}$ 个金币，向下移动一格（行坐标 $i$ 增加 $1$）。

现在你想要知道，为了获胜，你至少需要花费多少金币。

inputFormat:
输入共 $2N + 1$ 行。

第一行为一个整数 $N$，代表矩阵的大小。
第二行至第 $N + 1$ 行，每行 $N$ 个整数，其中第 $i + 1$ 行第 $j$ 个整数代表 $a _ {i, j}$。
第 $N + 2$ 行至第 $2N + 1$ 行，每行 $N$ 个整数，其中第 $N + i + 1$ 行第 $j$ 个整数代表 $b _ {i, j}$。

outputFormat: 输出一行一个整数，代表为了获胜需要花费的最小硬币数量。

hint:
### 样例组与实际输入的说明

如果你直接采用『提交答案』的方式，请将输入数据命名为 `1.in`，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器应当**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对这一问题的样例说明。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有行末空格和文末回车。
2. 数据中所有的数字都应为整数。
3. $1 \leq N \leq 2 \times 10 ^ 3$，$1 \leq a _ i, b _ i \leq 100$。

### 目标代码

你需要 hack 如下的代码：

```cpp
#include <bits/stdc++.h>
using namespace std;

int a[2005][2005], b[2005][2005];
int f[2005][2005], n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &b[i][j]);
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            f[i][j] = 1000000000;
    f[1][1] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (i == 1 && j == 1)
				continue;
			f[i][j] = min(f[i][j], f[i - 1][j] + b[i - 1][j]);
			f[i][j] = min(f[i][j], f[i][j - 1] + a[i][j - 1]);
        }
    int ans = 1000000000;
    ans = min(ans, f[n - 2][n]);
    ans = min(ans, f[n][n - 2]);
    ans = min(ans, f[n - 1][n - 1]);
    printf("%d\n", ans);
    return 0;
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

### 判分说明

本题共一个测试点，对应唯一一个问题，hack 成功则对应测试点返回 accepted。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 Unaccepted 的结果。

#### 超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

#### 结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和**完全正确的输出**，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

#### 未定义行为判定

我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

### 样例程序

如果你使用『提交答案』功能，请务必保证打开压缩包后能且仅能**直接**看到一个 `.in` 文件。这就是说，文件结构必须是：

```plain
ans.zip
 |---1.in
```

这一个文件不应该被额外的文件夹包含，即文件结构不能是：

```plain
ans.zip
 |---ans(folder)
      |---1.in
```

### 关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。


title: [语言月赛202304] 你的牌太多了

description:
笨蛋扶苏和坏蛋小 F 在打一种很新的牌。

初始时，扶苏和小 F 手中各有 $n$ 张牌。每张牌有一个花色 $f$ 和一个点数 $p$。在本题中，花色是不超过 $m$ 的正整数，点数是不超过 $r$ 的正整数。

打牌共会进行 $n$ 轮，每轮扶苏会从手中选择一张牌打出。小 F 会从当前手牌中，选择与扶苏本轮打出的牌**花色相同**且点数**大于**扶苏打出的牌中点数最小的一张打出。如果这样的牌不存在，那么小 F 不会接牌（也就是不会出牌）。

注意，无论小 F 打出什么牌，本轮都立即结束，扶苏不会继续接牌，而是会开启下一轮出牌。

给出扶苏的出牌顺序，请你求出小 F 最终手里剩了几张牌。

inputFormat:
第一行是三个整数，表示一个人的手牌数 $n$，花色的上界 $m$ 和点数的上界 $r$。
第二行有 $n$ 个整数，第 $i$ 个整数表示扶苏第 $i$ 张牌的花色 $f1_i$。
第三行有 $n$ 个整数，第 $i$ 个整数表示扶苏第 $i$ 张牌的点数 $p1_i$。
第四行有 $n$ 个整数，第 $i$ 个整数表示小 F 第 $i$ 张牌的花色 $f2_i$。
第五行有 $n$ 个整数，第 $i$ 个整数表示小 F 第 $i$ 张牌的点数 $p2_i$。
第六行是一个长度为 $n$ 的排列，描述扶苏的出牌情况。第 $i$ 个整数 $p_i$ 表示扶苏第 $i$ 轮出了第 $p_i$ 张牌。

outputFormat: 输出一行一个整数，表示坏蛋小 F 结束时手里剩余的牌数。

hint:
### 样例 1 解释

小 F 花色为 $1$ 且点数也为 $1$ 的牌管不住任何牌。其余牌都被打出去了。

### 数据规模与约定

- 对于 $10\%$ 的数据，$r = 1$；
- 对于 $20\%$ 的数据，$n = 1$；
- 对于 $50\%$ 的数据，$m = 1$；
- 对于 $100\%$ 的数据，$1 \leq n,m,r \leq 100$，$1 \leq f1_i, f2_i \leq m$，$1 \leq p1_i, p2_i \leq r$。$1 \leq p_i \leq n$，$p$ 是长度为 $n$ 的排列。


title: [入门赛 #11] [yLOI2021] 扶苏与 1 (Hard Version)

background:
**本题与 Easy Version 的区别是：$x$ 的范围不同，$y$ 的长度限制不同**。

**请注意 Easy Version 和 Hard Version 不是严格的包含关系。**

扶苏在 ICPC2022 EC Final 的比赛里，开局不到五分钟，就读假了一道题，把一道数位 DP 开成了简单签到，狠狠地演了队友一把。

为了不让读假了的题被浪费，所以这道题出现在了这里。

description:
扶苏给了你一个数字 $x$，你需要给她一个数字 $y$，使得在列竖式计算 $x + y$ 时，能恰好产生 $k$ 个进位。

**你给出的 $y$ 的长度不能超过 $x$ 的长度。**（注意，这条要求与 Easy Version 不同）

**进位**的含义是：在进行竖式加法运算时，如果位于同一列上的数字之和（加上低位向上可能存在的进位）比 $9$ 大，则在结果的这一列上只保留这个和的个位数字，同时称这一位向它的高位产生了一个**进位**。

下图是一个竖式加法的例子，结果中标红的两位都向上产生了进位。

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

outputFormat:
**本题采用 special judge 进行判题**。

对每组数据，输出一行一个整数，表示你给出的 $y$。

如果有多个满足要求的 $y$，你可以输出任何一个。但是必须保证如下三条限制：
- $y$ 是正整数。
- $y$ 不含前导 $0$。
- $y$ 的长度不超过 $x$ 的长度。

特别的，如果这样的 $y$ 不存在，请你输出一行一个 $\texttt{-1}$。

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

对全部的测试点，保证 $0 \leq x < 10^{(10^4)}$，$1 \leq T \leq 5000$，$1 \leq k \leq 1+\log_{10}\max(1,x)$。输入的 $x$ 不含前导 $0$。

### 提示

输入的 $x$ 可能会很大。如果说 $x < 10^t$，则输入 $x$ 的**长度**不会超过 $t$。数据规模中式子 $k \leq 1 + \log_{10}\max(1,x) $ 的含义是：$k$ 不会超过 $x$ 的长度。


title: 「EZEC-14」众数 II

background: dXqwq 是一个不可爱的男孩子。他在 NOI2022 中的众数一题定义了 $10^6$ 个 ``std::deque`` 并成功 MLE。

description:
给定一个长度为 $n$ 的序列 $a$，我们通过以下方式构造序列 $b$：

- 初始时 $b$ 为空序列。
- 对于 $i=1,2,\cdots,n$，我们依次向 $b$ 的尾部插入 $1,2,\cdots,a_i$。

dXqwq 定义一个序列的**最小众数**为所有出现次数最大的数的最小值。例如 $[1,1,4,5,1,4]$ 的最小众数为 $1$，而 $[1,14,5,14,19,19,8,10]$ 的最小众数为 $14$。

你需要求出 $b$ 的每个子区间的**最小众数**的和。由于答案可能很大，你只需要输出它对 $998244353$ 取模后的值。

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

第二行输入 $n$ 个整数 $a_i$。

outputFormat: 输出一个整数，代表 $b$ 的每个子区间的最小众数的和对 $998244353$ 取模的值。

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

在第一个样例中，$b=[1,1,2,1,2,3]$。

有 $15$ 个区间的最小众数为 $1$，$5$ 个区间的最小众数为 $2$，$1$ 个区间的最小众数为 $3$，因此答案为 $15\times 1+5\times 2+1\times 3=28$。

**【提示】**

开 $10^6$ 个 ``std::deque`` 在空间限制为 512MB 时一定会 MLE。

**【数据范围】**

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

- Subtask 1（10 pts）：$\sum a_i\leq 100$。
- Subtask 2（20 pts）：$\sum a_i\leq 10^3$。
- Subtask 3（20 pts）：$\sum a_i\leq 10^6$。
- Subtask 4（10 pts）：$n\leq 2$。
- Subtask 5（20 pts）：$n\leq 10^3$。
- Subtask 6（10 pts）：$a_i\leq 2$。
- Subtask 7（10 pts）：无特殊限制。

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


title: [信息与未来 2019] 幸运素数

description:
素数，又称质数，是指除 $1$ 和其自身之外，没有其他约数的正整数。例如 $2,3,5,13$ 都是素数，而 $4,9,12,18$ 则不是。特别地，规定 $1$ 不是素数（因此自然数的质因数分解就是唯一的）。

如果一个数本身是素数，并且把最低位删除后得到的数仍是素数、再把最低位删除后得到的数仍是素数……如此往复，直到得到一个一位素数，我们就称它是“幸运素数”。以 $233$ 为例：
- $233$ 本身是素数；
- $23=\lfloor\dfrac{233}{10}\rfloor$ 是素数；
- $2=\lfloor\dfrac{23}{10}\rfloor$ 是素数。

因此 $233$ 是“幸运”素数。而 $211$ 则不是幸运素数：虽然 $211$ 是素数，但 $21$ 不是素数。请编程求出一定范围内的所有幸运数字。

inputFormat: 输入一行两个用空格分隔的正整数 $m,n$，表示我们希望求幸运素数的范围。

outputFormat: 从小到大输出 $m,m+1,m+2,\cdots,n$ 中所有的幸运素数，每行输出一个。

hint:
对于 $100\%$ 的测试数据，有 $1\le m\le n\le 9999$。
> 本题原始满分为 $15\text{pts}$。


title: [信息与未来 2019] 粉刷矩形

description:
在一个 $n\times m$ 的矩形上进行粉刷工作（初始时，矩形的格子无色），每次选择一个起点和一个方向，将连续的格子刷成同样的颜色，直到碰到矩形边界后停止；已经有颜色的格子中的颜色将会被覆盖，例如下图展示了依次在 $(1,2),(2,3),(2,2),(3,5)$ 格子进行向右、向上、向下、向左粉刷后每个格子的颜色。

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

请你编程模拟粉刷矩形的过程，并输出每个格子的颜色。

inputFormat:
输入第一行三个整数 $n,m,k$ 表示矩形的大小是 $n\times m$、共有 $k$ 次粉刷操作。
接下来 $k$ 行，每行都是空格分隔的两个整数和两个字符，分别表示粉刷起点的行号、列号、粉刷的颜色（用小写字母表示）、粉刷的方向（$\text{R, U, L, D}$ 分别表示向右、向上、向左、向下）。

outputFormat: 输出 $n$ 行，每行 $m$ 个字符（字符之间无空格），表示粉刷后每个格子的颜色。无色的格子输出 `.`。

hint:
对于 $100\%$ 的测试数据，有 $1\le n,m,k\le50$。
> 本题原始满分为 $15\text{pts}$。


title: [信息与未来 2019] 新斐波那契数列

description:
给定正整数 $a(a\ge1)$，新斐波那契数列 $f_a$ 按如下方式定义：
- $f_a(1) = 1$；
- $f_a(2) = a$；
- $f_a(n) = f_a(n − 1) + f_a(n − 2)\ (n > 2)$。

例如，给定 $a = 4$，有 $f_4(1) = 1, f_4(2) = 4, f_4(3) = 5, f_4(4) = 9, f_4(5) = 14, \cdots$ 现在已知新斐波那契数列中的一项 $x$，但并不知道 $n$ 和 $a$ 的值是多少。请你求出所有可能的 $n,a(n\ge2)$ 满足 $f_a(n) = x$。

inputFormat:
你需要在一个测试数据中处理多个新斐波那契数列问题。输入第一行 $T$ 表示问题的数量。

接下来 $T$ 行， 每行一个整数：待求解的 $x$。

outputFormat: 对于每个新斐波那契数列问题，按照 $n$ 从小到大的顺序，输出所有可能的 $n,a$ 满足 $f_a(n) = x$。每行输出一对 $n$ 和 $a$，由一个空格分隔。

hint:
对于 $60\%$ 的测试数据，有 $1\le x\le10^6$。

对于 $100\%$ 的测试数据，有 $2\le x\le10^9,1\le T\le20$。
> 本题原始满分为 $15\text{pts}$。


title: [信息与未来 2019] 堆栈计算机

description:
有一种新型的堆栈计算机，计算机的内存是一个初始为空的数列，计算机支持三种操作：
- $\tt 1$ - 将整数 $1$ 放入数列的尾部。任意时刻都可执行此操作。
- $\tt dup$ - 将数列尾部的数字复制一份，放入数列尾部。只有数列非空时才能执行此操作。
- $\tt add$ - 取出（并删除）数列尾部的两个数字，相加后放回数列的尾部。只有数列中至少有两个数字时才能执行此操作。

给定一个正整数，你需要输出一个长度不超过 $200$ 的程序（操作的序列），它在执行结束后，恰好得到一个长度为 $1$ 的数列，并且数列中的数字恰好为 $n$。下图展示了一个最终得到 $8$ 的程序。

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

inputFormat: 输入一行一个正整数 $n$，表示希望输出的数字。

outputFormat: 输出一个若干行（不超过 $200$ 行，否则判为不正确）的满足上述要求的程序。如有多种方案，输出任意一种即可。注意 $\tt dup$ 和 $\tt add$ 均为小写。

hint:
对于 $60\%$ 的测试数据，有 $1\le n\le10^4$。

对于 $100\%$ 的测试数据，有 $1\le n\le10^9$。
> 本题原始满分为 $15\text{pts}$。


title: [信息与未来 2019] 鸡兔同笼

description:
有三种动物被关在笼子里，它们分别是：
- 鸡，每只鸡有一个头、两只脚；
- 三脚猫，每只三脚猫有一个头，三只脚；
- 兔子，每只兔子有一个头，四只脚。

现在知道笼子中一共有 $x$ 个头、$y$ 只脚，但这个信息并不足以推导出鸡、兔和三脚猫的准确数量。这时候就需要编程来帮忙了——请你求出笼子里分别至少、至多有几只兔子。

inputFormat:
你需要在一个测试数据中处理多个鸡兔同笼问题。输入第一行 $T$ 表示问题的数量。

接下来 $T$ 行，每行两个用空格分隔的正整数 $x,y$，表示头和脚的数量。

outputFormat: 对于每个问题，输出一行两个空格分开的整数，表示笼子里至少和至多有几只兔子。输入数据保证每个问题至少有一种鸡、三脚猫和兔子的合法组合。

hint:
对于 $50\%$ 的测试数据，有 $1\le x\le 10^6$。

对于 $100\%$ 的测试数据，有 $1\le x\le10^9,1\le T\le20$。
> 本题原始满分为 $20\text{pts}$。


title: [信息与未来 2019] 方格覆盖

description:
给定一个 $n\times n$ 的矩形，其中从左上角开始，对角线上连续的 $k$ 个格子中有障碍物。你可以把若干 $1\times2$ 的小矩形放置到该大矩形中，要求是放置的两个小矩形不能占据相同的格子，且不能碰到障碍物。例如下图是 $n=4,k=2$ 的例子，我们放置了 $6$ 个 $1\times2$ 的小矩形。

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

给定 $n,k$，请你输出一个方案，使得放置的 $1\times2$ 小矩形尽可能多。可以证明，$n=4,k=2$ 时，至多只能放置 $6$ 个小矩形。

inputFormat: 输入一行两个用空格分隔的正整数 $n,k$，表示矩形的大小和障碍物的数量。

outputFormat: 输出 $n$ 行，每行 $n$ 个整数（用任意数量的空格分隔）。放置的小矩形分别用 $1,2,\cdots$ 编号。不放置小矩形的格子输出 $0$。如有多种最优方案（放置最多数量的小矩形），输出任意一种即可。

hint:
对于 $50\%$ 的测试数据，有 $1\le k\le n\le10$。

对于 $100\%$ 的测试数据，有 $1\le k\le n\le50$。
> 本题原始满分为 $20\text{pts}$。


title: 「Cfz Round 1」Wqs Game

background: 『博』和『奕』喜欢博弈，尤其喜欢 wqs 带权博弈。

description:
wqs 带权博弈在一个数列 $\{a_i\}$ 上进行，对应有一个 $01$ 串 $\{b_i\}$。

1. 若 $b_i=0$，则 $a_i$ 这个数字是属于『博』的；
2. 若 $b_i=1$，则 $a_i$ 这个数字是属于『奕』的。

游戏规则是，每次给定一个区间 $[l,r]$，从 $a_l$ 到 $a_r$，拥有这个数的人**依次**决定选该数或者不选，两个人都会采用**最优策略**。

因为『博』很强大，她会让着『奕』，于是博弈的规则是，如果最后两个人选的数**按位异或和不为零**，则『奕』获胜，否则『博』获胜。

注意每个人**能看到**对方的选数情况，可以选**多个**数（只要这个数是自己的），最后计算两个人选数的总**异或**和。

对于任意区间 $[l,r]$，若『奕』获胜，则 $w(l,r)=1$，否则 $w(l,r)=0$。

每次查询 $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ 的值，对 $2^{32}$ 取模。

由于输入输出量过大，对于 $tp\ne 0$ 的测试点，选手需要自行生成数列 $a_i$ 和询问区间 $[L,R]$，并用特殊方式输出答案。

注意正解**不依赖**特殊的输入输出方式。

inputFormat:
第一行三个正整数 $n,q,tp$，表示数列长度，天数以及每天局数，以及读入方式。

第二行一个长度为 $n$ 的字符串，表示 $01$ 串 $\{b_i\}$；

若 $tp=0$，则第三行 $n$ 个正整数，表示数列 $\{a_i\}$，接下来 $q$ 行，每行两个正整数 $L,R$，表示询问  $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ 对 $2^{32}$ 取模的值。

否则，令 `Sd` 初值为 $tp$，`Cnt` 初值为 $0$，先使用函数 `GetA` 依次生成 $a_i$，再使用函数 `GetLR` 依次生成 $L,R$，具体方式以代码形式后附。

outputFormat:
若 $tp=0$ 则输出 $q$ 行，每行一个正整数，表示该询问的答案。

否则，令 $ans_i$ 为第 $i$ 次询问的答案，你需要输出 $(ans_i\times i)\bmod 2^{32}$ 的**按位异或和**。


title: 异或积

background:
$\texttt{id: 4d7e}$

小 H 在课堂上学习了异或运算。

对于两个非负整数 $x,y$，它们的**异或**是指，将它们作为二进制数，对二进制表示中的每一位进行如下运算得到的结果：

- $x$ 和 $y$ 的这一位上不同时，结果的这一位为 $1$；
- $x$ 和 $y$ 的这一位上相同时，结果的这一位为 $0$。

$x$ 和 $y$ 的异或被记为 $x \operatorname{xor} y$ 或 $x \oplus y$。

在 C++ 中，你可以用 `x ^ y` 得到 $x$ 与 $y$ 的异或值。

另外，若干个数的异或称之为**异或和**。

description:
小 H 还了解到，一个长度为 $n$ 的数列 $a$ 的**异或积**是一个等长的数列 $b$，其中 $b_i$ 等于数列 $a$ 中除了 $a_i$ 以外其他元素的异或和，即

$$b_i = \bigoplus \limits_{j = 1}^{n} [j\ne i] a_j$$

例如，数列 $\{1, 2, 3, 4\}$ 的异或积为 $\{5, 6, 7, 0\}$。

**异或积变换**是指将一个数列用它的异或积替换的过程，由于异或积变换之后数列长度不变，所以异或积变换可以连续进行多次。

现在，小 H 有一个长度为 $n$ 的数列 $a$，他想请你帮他计算出 $a$ 经过 $k$ 次异或积变换之后得到的序列。

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

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

对于每一组测试数据：

第一行两个整数 $n,k$。

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

outputFormat:
对于每一组测试数据：

一行 $n$ 个整数，表示数列 $a$ 经过 $k$ 次异或积变换之后得到的数列。

samples:
见附件中的 samples/xor3.in
见附件中的 samples/xor3.ans


title: 「RiOI-03」变换，反演

background: 为了题目要求，我们对积性函数进行重定义：**不保证 $f(1)=1$**。

description:
**这是一道非传统题。**

给定一个**积性函数** $f(d)$。对于每一个测试点，我们会在附件中给出 $g(n)=\sum_{d|n}f(d)$ 的其中 $k$ 项 $\bmod\ 998244353$ 的值，这部分也会在输入中出现。接着，对于每一个测试点，有 $t$ 组数据。对于每组数据，输入 $d$，请输出 $f(d)\bmod998244353$ 的值。

inputFormat:
第一行为 $k$，接下来每一行会有两个正整数，分别为 $d$ 与 $g(d)$。

之后输入两个数 $t,id$，分别表示数据组数与数据点编号。对于每组数据，输入一个正整数 $n$。

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


title: [信息与未来 2021] 幸运数字

description:
如果⼀个正整数 $n$ 在五进制、七进制、九进制的表⽰下都没有数字 $0$，我们就称 $n$ 是幸运数字。例如：

- $(987)_{10}=(12422)_5=(2610)_7=(1316)_9$，因此 $n=987$ 不是幸运数字。

- $(988)_{10}=(12423)_5=(2611)_7=(1317)_9$，因此 $n=988$ 是幸运数字。

写程序求出 $a,a+1,a+2,\cdots,b$ 之间⼀共有多少个幸运数字。

inputFormat: 输入一行两个正整数 $a$ 和 $b$。

outputFormat: 输出一行，表示 $a,a+1,a+2,\cdots,b$ 中幸运数字的个数。

hint:
对于 $40\%$ 的数据，$1\leq a \leq b \leq 10^3$。

对于 $100\%$ 的数据，$1\leq a \leq b \leq 10^6$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2021] 摩尔斯电码

background: 早期的电报机只能表达两种状态：电路导通和电路断开。电路导通时喇叭可以发声；断开时则不发声。如何⽤这样的机器来传递⼈类能理解的信号呢？聪明的你⼀定想到了——时间的长短可以表达不同的含义（例如长代表 $\tt{1}$、短代表 $\tt{0}$），然后再把 $\tt{01}$ 的⼆进制序列对应到字符就可以啦。

description:
摩尔斯电码就是这样⼀种早期的数字通信协议，它通过喇叭发声长短来表示不同的英文字母：

1. 点（半角点号 `.`），喇叭响 $1$ 单位时间，读作“滴”（$\tt dit$）；
1. 划（半角减号 `-`），喇叭响 $3$ 单位时间，读作“嗒”（$\tt dah$）；
1. 字符/单词间的停顿，字符停顿 $3$ 单位时间，单词停顿 $7$ 单位时间。

下图列出了摩尔斯电码和英文字母之间的对应：

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

例如，大家可以试试把 `... --- ...` 对照上面的表格翻译成英⽂（空格代表字符的分割）。没错，这就是著名的 “$\tt SOS$” 紧急求救信号。现在，你需要写⼀个程序把收到的摩尔斯电码翻译回英文字符。

inputFormat:
输⼊数据的第一行是⼀个整数 $n$，代表共有 $n$ 个需要解码的英文字母。

输⼊数据的第二行包含 $n$ 个摩尔斯电码点/划组成的字符串（字符串之间用一个空格隔开），每个字符串仅包含若干半角减号 `-` 和半角点号 `.`，且保证能翻译为 $26$ 个英文字母中的⼀个。

outputFormat: 输出一行，为摩尔斯电码解码后得到的字符串。

hint:
解释：`The quick brown fox jumps over the lazy dog` 是⼀个经典的包含了所有 $26$ 个字母的句子。~~此外请注意因为文本宽度限制，样例第二行中的摩尔斯电码产生了断行。在实际的输入数据中，所有的摩尔斯电码均在同一行。~~

>@[_YXJS_](/user/516346)：划掉部分为原题面所加，在迁移至洛谷时已修复样例。

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

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2021] 括号序列

description: 你得到了一个仅包含左圆括号 `(` 和右圆括号 `)` 的字符串，但其中的括号并不配对。为了使这个字符串变得更好看，你希望在字符串中插⼊尽可能少的圆括号（可以在任意位置插⼊任意数量的括号，但已有的括号不能改变），使修改后的字符串括号配对。

inputFormat: 输⼊一行一个字符串，为括号未全部配对的圆括号序列。

outputFormat: 输出一行，为插⼊圆括号后配对的字符串。如有多种长度最短的方案，输出任意⼀个即可。

hint:
对于 $60\%$ 数据，输⼊字符串长度不超过 $10$。

对于 $100\%$ 的数据，输⼊字符串长度不超过 $10^3$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2021] 文本分类

background: “分类” 是人工智能中很重要的一项任务，例如区分视频中的⼀帧图像是否存在异常事件、辨别图片中是否有待检索的目标、划分音频中词语的分界位置等。

description:
虽然属于“人工智能”的范畴，但分类问题也可以简单理解成是一个计算机函数 $f$，它输⼊一系列数据（例如代表图片颜色的二维数组、代表⽂本的字符串等），$f(x)$ 返回 $0$ 或 $1$，其中 $1$ 则代表 $x$ 具有某种特征，属于这⼀分类。

今天，⼤家要挑战一项文本的分类任务：识别一个单词序列是由英文书写的，还是由汉语拼音书写的。以下分别是两段文字，是用汉语拼音和英文书写的，你能正确地分类吗？

1. While a number of definitions of artificial intelligence (AI) have surfaced over the last few decades, John McCarthy offers the following definition in this 2004 paper, " It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable."

1. Ren gong zhi neng shi yan jiu、kai fa yong yu mo ni、yan shen he kuo zhan ren.de zhi neng de li lun、fang fa ji ying yong xi tong de yi men xin de ji shu ke xue.

inputFormat:
输⼊数据的第一行是你需要分类文本的任务数量 $T$。

接下来 $T$ 行，每⾏描述了⼀个文本分类任务，首先是整数 $n$ 表示单词的个数，接下来 $n$ 个空格分隔的、仅由小写字母 $\tt{a}\sim \tt{z}$ 组成的字符串代表了⼀段待分类的文本。输⼊保证每个单词（对中⽂来说是每个字）之间都有一个空格。

outputFormat: 为每个分类任务输出一行，如果待分类的文本是拼音书写的，输出 `Pinyin`，如是英文书写的，输出 `English`（注意 `Pinyin` 和 `English` 的大小写）。

samples:
2
14 zhe ge ti mu qi shi bi ni xiang xiang de yao jian dan
6 this problem has a simple solution

hint:
对于 $100\%$ 的数据，满足 $1\leq T\leq 10,10^3\leq n\leq 10^4$ 并且文本都来自真实、易于人类阅读的文本。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2021] 掷骰子

background:
骰子是一个正六面体（立方体），每一面上有圆点表示的数字（圆点的数量表示数字的大小）。一个普通的骰子的六个面上分别有 $1\sim 6$ 这 $6$ 个不同的数字：

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

description:
但是今天你得到了一个特殊的骰子，虽然每个面上的数字依然是 $1\sim 6$ 之间的一个，但不同面上的数字却可能重复。为了还原骰子上的数字，你使用摄像头从不同角度拍摄了多张骰子的照片（骰⼦可能在空间中任意翻转）。但限于摄像头的角度，你拍摄的每张照⽚都只能拍到骰子的三个面。

你需要根据摄像头拍摄到的多张照片，推断出骰子每个面上可能的数字。

inputFormat:
输⼊数据的第一行为一个整数 $n$，代表摄像头拍摄的次数。

接下来 $n$ 行，每行三个整数 $x,y,z(1\leq x,y,z\leq 6)$，代表⼀次摄像机拍摄到骰子三个面上的数字，如下图所示：

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

输⼊数据保证所有的 $x,y,z$ 都是从同⼀个骰⼦拍摄得到的。

outputFormat: 输出一行两个整数（中间用⼀个空格隔开），分别表示满足摄像头拍摄到结果的骰子上数字和的最⼩值和最大值。

hint:
### 样例解释
#### 样例 $1$
我们知道骰子上至少有三个 $1$、两个 $2$。剩下的数字可能是 $1$ 也可能是 $6$。

#### 样例 $2$
这是一个“普通”的骰⼦，$1\sim 6$ 这些数字恰好出现⼀次。

对于 $20\%$ 的数据，$0\le n\leq 1$。

对于 $100\%$ 的数据，$0\leq n\leq 20$。

>本题原始满分为 $20\text{pts}$。


title: [信息与未来 2021] 三角魔方

description:
有一个三角形的魔方，初始时，三角形中按行依次填有 $\tt{A}\sim \tt{P}$ 这 $16$ 个字母。魔方每次可以选
择某个下图箭头所示的方向进行⼀次“旋转”操作。

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

共有 $3$ 种合法的“旋转”方向，分别对应图中左上（红色箭头）、左下（蓝色箭头）、正右（绿色箭头）三个方向，分别记做 $\tt U$、$\tt D$ 和 $\tt R$。

每次“旋转”操作选择该方向上含有一、三、五或七个字母的一行（或列），分别记做 `1`、`3`、`5`、`7`。 将不同的方向和行（或列）组合得到十二种合法的“旋转”操作，例如 `U1`、`D7`、`R3`。

“旋转”操作会将该行/列的所有字母向对应箭头方向循环移动一格，第一个字母变成第二个字母、第二个字母变成第三个字母……最后一个字母变成第一个字母，以此类推，例如：

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

如果我们将三角形魔方写成“字母三角形”的形式，那么初始状态就是：

```
   A
  BCD
 EFGHI
JKLMNOP
```

如果对初始状态进行两次 `U5` 旋转，将会得到：

```
   A
  GCD
 EMNHI
JKLBFOP
```

现在，你得到了一个魔方旋转机器人，它可以输入⼀个操作序列，然后将这个操作序列重复 $a^b$（$a$ 的 $b$ 次方，即 $a\times a\times \dots\times a$，共 $b$ 个 $a$ 相乘）次。但让机器人旋转魔方实在太耗时了。你能预测出从初始状态开始，执行完机器人的动作后魔方的状态吗？

inputFormat:
第一行输⼊一个字符串，代表了一个操作序列。

第二行输⼊两个整数 $a,b$，代表机器⼈会将操作序列重复 $a^b$ 次。

outputFormat: 输出 $16$ 个字符，为操作序列重复后的魔方的状态，按行依次输出所有字母，例如初始状态输出 `ABCDEFGHIJKLMNOP`。

hint:
对于 $50\%$ 的数据，$b=1$。

对于 $100\%$ 的数据，$1\leq a,b\leq 10^3$。操作序列中“旋转”操作的数量不超过 $100$。

>本题原始满分为 $20\text{pts}$。


title: [CEOI 2013] 有轨电车 / Tram

background:
翻译自 [CEOI 2013 Day 1](https://ceoi2013.hsin.hr/tasks/tasks_day1.pdf)。

在萨格勒布运营的电车的座位就像一个 $n$ 行 $2$ 列的网格，两个座位之间的距离，是相应网格正方形中心之间的欧几里得距离（直线距离）。

大多数乘客在使用公共交通工具时会社恐，也就是说，当乘客进入电车时，会选择一个没有人坐的座位，并且该座位与最近的座位的距离尽可能大。如果有多个这样的座位，他们总是会选择一个行号较小的座位（因为这样他不需要走太远）。如果仍然有多个这种座位，他们会选择列号较小（即列号为 $1$）的座位。乘客选择座位后，会一直坐在那里，直到他离开电车。如果电车是空的，进入的乘客将始终选择第 $1$ 排第 $1$ 列的座位。

description:
给定一系列事件，每个事件都是乘客进入或离开电车。你需要输出这位乘客进入时他会坐在哪里。电车一开始是空的。

输入中有 $m$ 个事件，按事件发生的顺序编号为 $1$ 到 $m$。有两种事件：`E` 类事件表示乘客进入有轨电车，而 `L` 类事件则表示乘客离开有轨电车。对于类型为 `L` 的事件，还给出了一个整数 $p$，它表示在该事件中离开的乘客是在**事件** $p$ 中进入的乘客。

测试数据确保每当乘客试图进入电车时，电车中至少有一个空位。

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

接下来 $m$ 行，其中第 $i$ 行表示事件 $i$ 的内容，首先输入一个字符 `E` 或 `L`，当字符是 `L` 时再输入一个数 $p_i$，保证事件 $p_i$ 的类型一定是 `E`。

outputFormat: 输出中的行数应等于输入中 `E` 类事件的数量。对于第 $i$ 个类型为 `E` 的事件，在第 $i$ 行上输出该乘客选择的座位号 $r,c$（行和列），中间用一个空格隔开。


title: [CEOI 2013] 停车场 / Splot

background:
翻译自 [CEOI 2013 Day 1](https://ceoi2013.hsin.hr/tasks/tasks_day1.pdf)。

亚得里亚海沿岸和岛屿都有各种形状和大小的美丽沙滩。然而，许多沙滩无法通过汽车到达。为了满足不断增长的需求，沿海附近的一片巨大空地被改建成停车场。

由于参与设计的所有建筑师都具有电气工程背景，想着怎么着自己学过的专业也得用上，于是停车场的布局就类似于在设计电路时常用的串并联图。

停车场由停车位和连接它们的双向道路组成。每条道路连接两个不同的停车位，每一对停车位之间最多只能通过一条道路连接。每个停车位在任何时刻最多只能停放一辆汽车。其他车辆不能通过被占用的停车位行驶。

![](https://cdn.luogu.com.cn/upload/image_hosting/j207s329.png)
$$\text{图 1：构建停车图的规则，对应下面的三点}$$

串并联停车场（也称为 splot，下文称为停车图）是一种由称为源点和终点的两个特定停车位构成的停车场，它是通过使用串并联组合规则从单个停车位构建而成的。每个停车图可以通过编码来指定其结构和停放车辆的位置，编码是一个描述其结构的字符序列。有效的停车图及其编码按照以下递归方式定义：

1. 只包含一个停车位且没有道路的停车场是一个有效的停车图。这个单个停车位既是停车图的源点也是终点。如果停车位为空，则该停车图的编码为小写字母 `o`，如果停车位被汽车占用，则编码为小写字母`x`。
   - ![](https://cdn.luogu.com.cn/upload/image_hosting/x6vficzn.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

2. 如果 $G_1$ 和 $G_2$ 是两个有效的停车图，它们的串联组合 $G$ 也是一个停车图。串联组合是通过在 $G_1$ 的终点和 $G_2$ 的源点之间添加一条道路来获得的。新获得的停车图 $G$ 的源点是 $G_1$ 的源点，而终点是 $G_2$ 的终点。如果 $E_1$ 和 $E_2$ 分别是停车图 $G_1$ 和 $G_2$ 的编码，则 $G$ 的编码为 `SE1E2#`。换句话说，编码是通过连接大写字母 `S`、组成它的停车图的编码和井号 `#` 获得的。
   - ![](https://cdn.luogu.com.cn/upload/image_hosting/bzrozfho.png?x-oss-process=image/resize,m_lfit,h_340,w_450)

3. 如果 $G_1$ 和 $G_2$ 是两个有效的停车图，它们的并联组合 $G$ 也是一个有效的停车图。并联组合是通过添加两个新的停车位 $s$ 和 $t$，添加从 $s$ 到 $G_1$ 和 $G_2$ 的源之间的道路，以及从 $t$ 到 $G_1$ 和 $G_2$ 的终端之间的道路得到的。新获得的停车图G的源是新添加的停车位 $s$，而 $G$ 的终端是新添加的停车位 $t$。如果 $E_1$ 和 $E_2$ 分别是停车图 $G_1$ 和 $G_2$ 的编码，而 $E_s$ 和 $E_t$ 是源 $s$ 和终端 $t$ 的编码（如果相应的空间为空，则为小写字母 `o`，否则为小写字母 `x`），则 $G$ 的编码为 `PEs|E1E2|Et#`。换句话说，编码是通过连接大写字母 `P`，源停车位的编码，竖线符号 `|`，被组合的停车图的编码，另一个竖线符号 `|`，终端停车位的编码，最后是井号 `#` 得到的。
   - ![](https://cdn.luogu.com.cn/upload/image_hosting/czj2m8t8.png?x-oss-process=image/resize,m_lfit,h_340,w_450)

![](https://cdn.luogu.com.cn/upload/image_hosting/6gyst5bp.png)
$$\text{图2：与下面第一个测试示例对应的停车图}$$

例如，上图中给出的停车图的编码是 `Po|Px|Sxo#Soo#|o#Soo#|o#`（译者注：`{Po|[Px|(Sxo#)(Soo#)|o#](Soo#)|o#}`）。请注意，停车图 $G$ 的编码中小写字母（`o` 或 `x`）的数量始终与 $G$ 中的停车位数量相同，并且停车图中的停车位与其编码中的小写字母之间存在一一对应关系。停车场只有一个出口，它就在整个停车图的**源停车位**。如果车辆可以通过一些道路和空的停车位到达源停车位，即它可以离开这个停车图，则我们称该车辆未被阻挡。例如，在上面的停车图中，两辆车都没有被阻挡，但是如果我们将一辆车停在停车图的终端（最右边的节点）上，则其中一辆车将被阻挡。允许将车停在停车图的源停车位上（但是如果这样做，停车图中的所有其他车辆都将被阻挡）。

description:
停车场的运营商希望以一种方式安排进站的车辆，让图中没有车辆被阻挡。

编写一个程序，计算可以停放在给定停车场的最大汽车总数，（**包括已经在那里的汽车**），使它没有任何汽车被阻挡，也不会移动任何已经在那里的车。此外，程序应该**找到一种方法**来安排停车图中最大数量的汽车。

inputFormat: 输入一行，包含一个至少 $1$ 个、最多 $10$ 万个字符的序列，表示给定的 splot 的编码。序列中只会出现大写字母 `P` 和 `S`，小写字母 `o` 和 `x`，以及字符 `#`（`ASCII 35`）和 `|`（`ASCII 124`）。根据上面的规则，输入将是一个 splot 的编码。输入保证已经在停车场的汽车都不会被阻挡。

outputFormat:
输出应包含 $2$ 行。第一行应该包含一个整数 $m$，表示可以停放在 splot 中的最大汽车数量。

第二行应该包含一个字符序列，表示最终将车停放进 splot 的最佳方案。该序列应恰好包含 $m$ 个字母 `x`，并且是通过将原来的一些字母 `o` 替换为 `x` 得来的。

可能有多个最佳安排，程序可以输出其中的任何一个。

hint:
样例解释见题目描述最后一趴。

如果输出不正确或不完整，但第一行输出（最大汽车数量）是正确的，你将获得相应测试点 $80\%$ 的分数。

在 $30\%$ 的测试点中，splot 中的停车位总数最多为 $20$ 个。

在另外 $40\%$ 的测试点中，splot 为空，即输入不包含字母 `x`。

对于 $100\%$ 的数据，给定的 splot 的编码最多包含 $10$ 万个字符。

SPJ 提供者：@[cff_0102](https://www.luogu.com.cn/user/542457) 。


title: [CEOI 2013] 千岛之国 / Adritic

background:
翻译自 [CEOI 2013 Day 2](https://ceoi2013.hsin.hr/tasks/tasks_day2.pdf)。

“千岛之国”是克罗地亚旅游业在二十世纪九十年代中期的官方口号。虽然这个口号实际上不准确（克罗地亚的岛屿数量略多于 $1000$ 个），但“跳岛旅游”（从一个岛屿航行到另一个岛屿）是一个受欢迎的夏季活动。亚得里亚海的地图是由组成 $2500$ 行和 $2500$ 列的单位正方形组成的网格。行编号从北到南为 $1$ 到 $2500$，而列编号从西到东为 $1$ 到 $2500$。海中有 $N$ 个岛屿，编号为 $1$ 到 $N$，每个岛屿都位于网格的某个单位正方形内。岛屿 $K$ 的位置由相应的网格方格的坐标确定——其行号 $R_K$ 和列号 $C_K$。没有两个岛屿的位置相同。

由于风和海流的影响，只有当岛屿 $B$ 对于 $A$ 来说位于大致的西北或东南方向时才能直接从一个岛屿航行到另一个岛屿。更准确地说，只有在 $R_A < R_B$ 和 $C_A < C_B$ 都成立，或 $R_A > R_B$ 和 $C_A > C_B$ 都成立时，才可以从岛屿 $A$ “跳”到岛屿 $B$。请注意，两个岛屿之间的距离或其他岛屿的存在并不影响从一个岛屿跳到另一个岛屿的可能性。如果无法直接从 $A$ 跳到 $B$，则可能通过其他岛屿使用一些“跳跃”序列从 $A$ 到 $B$ 进行航行。从 $A$ 到 $B$ 的航行距离定义为从 $A$ 到 $B$ 所需的最少“跳跃”次数。

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

例如，在上面的图中，从位于第 $2$ 行第 $3$ 列的岛屿开始，我们可以跳到另外四个岛屿，而剩下的两个岛屿的航行距离为两个跳跃次数。

description:
一次帆船大会正在计划，组织者正在考虑每个岛屿作为大会的可能场地。在考虑候选岛屿时，他们想知道：如果每个其他岛屿都派出一艘帆船，为了使所有帆船都到达候选岛屿，需要的最小跳数是多少，或者等效地说，从所有其他岛屿到候选岛屿的航行距离之和是多少。

编写一个程序，对于给定 $N$ 个岛屿的位置，对于每个岛屿 $K$，计算所有其他岛屿到岛屿 $K$ 的航行距离之和。测试数据保证，对于所有岛屿 $A$ 和 $B$，可以使用一些跳跃序列从 $A$ 到 $B$ 航行。

inputFormat: 第一行包含一个整数 $N$（$1\le N\le250000$），表示岛屿的数量。接下来的 $N$ 行包含岛屿的位置。每个位置用一对整数表示，它们介于 $1$ 和 $2500$ 之间（包括 $1$ 和 $2500$），分别表示行和列号。

outputFormat: 输出应包含 $N$ 行。对于每个岛屿，按照它们在输入中给出的顺序，输出从所有其他岛屿到该岛屿的航行距离之和，每个岛屿输出一行。


title: 「EZEC-14」终点

background:
~~出题人怎么还没鸟加这首歌啊。~~

于 2023.8.5 拿下。

description:
**这是一道交互题。**

dXqwq 有一棵 $n$ 个点的无根树，结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。

您可以选择两个整数 $1\leq u,v\leq n$，并输出 `? u v` 进行询问。

对于每次询问，如果 $u,v$ 的路径中点在一个结点上，交互库返回该点的编号，否则返回 ``0``。

请通过不超过 $147154$ 次询问，得到这棵树的结构。

保证树的形态是提前确定的，即**交互库不自适应。**

### 交互方式

输入测试点所在子任务编号 $id$ 和树的大小 $n$ 以开始交互。

交互过程中，您可以进行题目描述中的询问。

对于每次询问，如果你提供的 $u,v$ 不合法或者超出询问次数上限，交互库会返回 ``-1``，否则交互库将会返回一个非负整数，含义见「题目描述」。

当你读取到 ``-1`` 后应立刻退出程序，在此之后交互库的行为未定义。

在您确定答案后，请先输出 `!`，然后接下来 $n-1$ 行依次输出两个整数 ``u[i] v[i]`` 代表树的每条边，最后退出程序。你可以以任意顺序输出这些边。

在您输出一行后，请清空缓冲区：

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 其它语言请自行查阅文档。

inputFormat: 见「交互方式」。

outputFormat: 见「交互方式」。

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

-  Subtask 1（10 pts）：$n \leq 10$，树满足性质 A。
-  Subtask 2（10 pts）：保证存在一个点度数为 $n-1$。
-  Subtask 3（10 pts）：保证所有点度数 $\leq 2$。
-  Subtask 4（10 pts）：$n \leq 500$，树满足性质 A。
-  Subtask 5（20 pts）：$n \leq 500$。
-  Subtask 6（20 pts）：树满足性质 A。
-  Subtask 7（20 pts）：无特殊限制。

性质 A：对于 $i=2,3,\cdots,n$ 存在整数 $1\leq j<i$ 满足有一条边连接 $i,j$。

对于 $100\%$ 的数据，$2 \leq n \leq 10^4$。

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


title: [CEOI 2013] 灌水 / Watering

background:
upd on 2023/11/01: 本题部分分已修复。

翻译自 [CEOI 2013 Day 2](https://ceoi2013.hsin.hr/tasks/tasks_day2.pdf)。

Sara 是一位专注的农民，拥有一块大的长方形土地。她的土地被分成网格状的若干个单元格，共有 $5\times R$ 行和 $5\times C$ 列。此外，每隔五行有一道横向的围栏，每隔五列有一道纵向的围栏。这些围栏将土地划分成了 $R\times C$ 个大小为 $5\times5$ 的区域，称为田地。

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

这块农田两个最常见的问题是鸟害和旱灾。为了对抗鸟害，有些田地安置了稻草人。稻草人（如果有的话）占据一个单元格，每个 $5\times5$ 的田地最多只能有一个稻草人。

在干旱期，可能会持续数月时间，Sara 使用洒水器来浇灌她的庄稼。每个洒水器都有三个喷嘴：一个主喷嘴和两个侧喷嘴。它正好占据三个单元格，并浇灌所有这些单元格。侧喷嘴总是占据紧邻主喷嘴（上、下、左或右）的两个单元格。因此，单个洒水器可以浇灌到的三个单元格如图所示：

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

Sara 要在未被稻草人占据的每个单元格上恰好放置一个洒水器。含有稻草人的单元格不能包含洒水器喷嘴。此外，喷嘴不能放置在 Sara 的土地之外。被单个洒水器浇灌的三个单元格不一定属于同一 $5\times5$ 领域：它们也可以属于相邻的领域。在这种情况下，Sara 必须在两个由同一洒水器浇灌的相邻领域之间的栅栏上钻一个洞。

description:
**这是一个提交答案题。您将获得 $10$ 个输入文件，只需提交相应的输出文件即可。您可以从附件里的 `watering.in.zip` 中下载输入文件。**

提交一个可行的浇灌方案，使得它满足所有的要求。

如果存在多个解决方案，可以提交任何一个。

inputFormat:
输入的第一行包含一对整数 $R$ 和 $C$（$1≤R,C≤100$），它们表示 Sara 的土地的大小。

接下来的 $6\times R-1$ 行，每行包含一个长度为 $6\times C-1$ 的字符序列。它们代表 Sara 的田地和它们之间的围栏。即使围栏实际上是无限薄的，它也用字符表示。

一个单元格用一个字符表示。点字符 `.` 表示空单元格，而 `#` 字符表示稻草人。垂直围栏用 `|` 字符表示，水平围栏用 `-` 字符表示。交叉点用 `+` 字符表示。

outputFormat:
输出文件应该包含采用与输入文件相同格式的文本表示具有有效喷水器排列的字段。栅栏中的每个孔应该由下划线字符 `_` 表示。输入文件中的所有空单元格（点）都应替换为小写字母 `a` - `z` ，以满足以下规则：

1. 由同一喷水器浇灌的任何三个单元格都由相同的字母表示，即使它们不全部在同一个 $5\times5$ 的农田中。
2. 如果同一块田中相邻的两个单元格由不同的喷水器浇灌，则它们必须用不同的字母表示。
3. 如果不同农田中的两个相邻单元格由不同的喷水器浇灌，并且它们之间有一个栅栏孔，则它们必须用不同的字母表示（但是这样钻孔的意义何在）。
4. 允许将属于不同农田的相邻单元格表示为相同的字母，只要满足所有先前的规则。

samples:
aaacc|dxxxa
bbbce|dyyya
ddd#e|dzzza
ccbae|fccbb
cbbaa|ffcdb
-----+---_-
ssrrr|tttdd
saaax_xxeee
yxbbb|zdaaa
yxccc|zdbbb
yxddd|zdccc

hint:
每个测试点的分值为 $10$ 分。如果输出方案无效，该测试点将获得零分。如果方案有效，则将按以下方式进行评分：
- 如果栅栏上的孔的数量不超过 $R\times C$，则得分为 $10$ 分。
- 否则，得分为 $5$ 分。

在 $10$ 个测试输入中的 $4$ 个中，每个田地都有一个稻草人。

SPJ 提供者：@[cff_0102](https://www.luogu.com.cn/user/542457) 。注：附件中的文件请用记事本/写字板打开。


title: 「DROI」Round 2  进制与操作

background: 与其编写苍白无力的背景，不如出更有质量的题。

description:
定义数 $x$ 在 $B$ 进制下的一次操作为以下两种操作中的任意一种：

- 令 $x \rightarrow \lfloor \dfrac{x}{B} \rfloor$。

- 令 $x \rightarrow x \times B + t $。其中 $t \in [0,B-1]$。

现给定长度为 $n$ 的序列 $A$。$m$ 次询问，每次询问形如：

- `l r B` 表示询问将序列 $A$ 中下标在 $[l,r]$ 之内的数在 $B$ 进制下操作，至少多少次才能将所有数变为相同（注：每次操作是对**一个数**进行操作）。

**询问间相互独立，即操作不会真的进行。**

inputFormat:
第一个两个整数，分别表示 $n,m$。

第二行一行 $n$ 个数，表示序列 $A$。

接下来 $m$ 行，每行三个数，分别表示这次询问的 $l,r,B$。

outputFormat: 输出共 $m$ 行，其中第 $i$ 行表示第 $i$ 次询问的答案。

hint:
### 样例解释

对于样例一，五次询问分别将区间内所有数变为 $3$、$4$、$8$、$4$、$6$ 是一种最优操作。

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

### 数据范围

**「本题采用捆绑测试」**

- $\operatorname{Subtask} 1(10\%)$：$n,m \leq 1000$。

- $\operatorname{Subtask} 2(20\%)$：保证所有询问 $B=2$。

- $\operatorname{Subtask} 3(40\%)$：$n,m \leq 3 \times 10^4$。

- $\operatorname{Subtask} 4(30\%)$：无特殊限制。

对于 $100\%$ 的数据：$1 \leq n,m \leq 10^5$，$2 \leq A_i,B \leq 10^8$。


title: 糖果

description:
三年级七班共有 $n$ 名同学。体育课开始，他们从左到右站成了一排，准备进行报数分组。

体育老师口袋里有很多袋装的糖果（一个袋子里有很多糖果），他准备在分组的过程中顺便将这些袋装糖果分给同学们。

具体地，在从左到右报数的过程中，每报数 $k$ 名同学，体育老师就会将这 $k$ 名同学划为一组，同时给予这 $k$ 名同学中的最后一名一袋糖果，让这最后一名同学来负责分发给组内的同学。也就是说，体育老师会依次给从左到右第 $k,2k,\cdots$ 名同学一袋糖果。

恰巧，三年级六班的同学听到了三年级七班发糖果的消息，于是他们打算混入队伍的末尾（即队伍最右侧），企图白嫖到一袋糖果。

三年级六班的同学想知道，他们**至少**需要向队伍末尾混入多少人。

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

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

hint:
### 样例 1 解释

此时每 $3$ 人分一组。三年级六班只需要向队伍中混入 $2$ 名同学，就可以和原来三年级七班的最后 $1$ 名同学一同凑成一组。

由于混入的这 $2$ 名同学在队伍的末尾，因此这一组中的最后一名同学一定是隔壁班的同学，因此隔壁班的同学可以白嫖到一袋糖果。

### 样例 2 解释

此时每 $4$ 人分一组。三年级七班的所有同学都已经分好了组，因此三年级六班需要完整地向队伍中混入 $4$ 名同学凑成一组，才能白嫖到一袋糖果。

### 数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 10 ^ {9}$，$2 \leq k \leq 10 ^ 9$。

| 测试点编号 | $n$ | $k$ |
| :-----------: | :-----------: | :-----------: |
| $1 \sim 2$ | $\leq 10$ | $= 2$ |
| $3 \sim 5$ | $\leq 10$ | $\leq 10$ |
| $6 \sim 10$ | $\leq 1000$ | $\leq 1000$ |
| $11 \sim 14$ | $\leq 10 ^ 9$ | $= 2$ |
| $15 \sim 20$ | $\leq 10 ^ 9$ | $\leq 10 ^ 9$ |


title: [POI2020] Gra platformowa / 平台游戏

background: **题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Gra platformowa](https://sio2.mimuw.edu.pl/c/oi28-1/p/gra/)。**

description:
Bajtazar 正在他的新电脑上玩游戏。

在这个游戏里，有 $n$ 层平台，自上而下分别编号为 $1$ 至 $n$，玩家需要在这些平台之间移动。每层平台的长度为 $X$，因此可以用数对 $(i,x)$ 描述玩家当前的位置，其中 $i$ 表示玩家在第几层平台，$x$ 表示玩家在当前平台的位置（最左端为 $1$，最右端为 $X$）。

玩家从某个平台的最左端开始，游戏的目标是到达任意一个平台的最右端，且玩家只能向右移动。为了增大难度，在平台的一些地方会有洞，这种情况下，玩家可以选择跳跃操作，直接跳过这个洞，也可以通过该洞前往上面或下面的平台，保证不存在两个在水平方向上或竖直方向上相邻的洞。

更具体地说，假如玩家当前的位置为 $(i,x)$，玩家可以执行如下几种操作：

- $\texttt{F}$ 操作：当 $(i,x+1)$ 没有洞时，玩家将会移动到 $(i,x+1)$；否则，玩家将会移动到 $(i+1,x+1)$。
- $\texttt{A}$ 操作：当 $(i,x+1)$ 有洞时，玩家将会移动到 $(i,x+2)$。
- $\texttt{B}$ 操作：当 $(i-1,x)$ 有洞时，玩家将会移动到 $(i-1,x+1)$。

现在 Bajtazar 希望执行最少的跳跃操作（即 $\texttt{A}$ 操作和 $\texttt{B}$ 操作）完成游戏。你能帮他完成这个任务吗？

inputFormat:
输入第一行三个整数 $n,X,z$，表示一共有 $n$ 层平台，每层平台的长度为 $X$，询问的次数为 $z$。

接下来 $n$ 行，第 $i$ 行描述第 $i$ 层平台的信息。每行开头一个整数 $k_i$，表示该层平台有 $k_i$ 个洞。接下来 $k_i$ 个递增的整数，给出该层每个洞的位置。数据保证任何一个平台的最左端和最右端不存在洞，且不存在两个在水平方向上或竖直方向上相邻的洞。

接下来 $z$ 行，每行包含一个整数 $p_j$，表示在第 $j$ 组询问中，玩家需要从第 $p_j$ 层平台的最左端出发。

outputFormat: 对于第 $j$ 组询问，请在第 $j$ 行输出一个整数，表示从 $(p_j,1)$ 出发，抵达任意一个平台的最右端需要执行的 $\texttt{A}$ 操作和 $\texttt{B}$ 操作的最小次数。

hint:
【样例解释1】：

![pp5jnwd.png](https://s1.ax1x.com/2023/04/05/pp5jnwd.png)

上图给出了样例 $1$ 的第一个询问对应的最优方案：玩家先执行两次 $\texttt{F}$ 操作到达 $(3,3)$，再执行一次 $\texttt{B}$ 操作到达 $(2,4)$，再执行五次 $\texttt{F}$ 操作到达 $(3,9)$。

对于第二个询问，最优方案是执行一次 $\texttt{F}$ 操作，再执行一次 $\texttt{A}$ 操作，最后执行五次 $\texttt{F}$ 操作。

对于第三个询问，最优方案是连续执行八次 $\texttt{F}$ 操作。

【数据范围】：

所有测试点均满足：$1 \leq n \leq 10^5$，$1 \leq X \leq 10^9$，$1 \leq z \leq 10^5$，$\sum k\le 2\times 10^6$。

| 子任务编号 | 约束 | 分值 |
| :-: | :-: | :-: |
|$0$|样例|$0$|
| $1$| $z \leq 5$，$n\times X \leq 10^6$ | $30$ |
| $2$| $z \leq 5$| $50$ |
|$3$| 无附加约束|$20$|


title: 「NnOI R1-T4」下楼

background:
引入一个简单的问题作为铺垫。

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

假如你现在站在一栋高为 $200m$ 的楼上，人的大小忽略不计。

楼的 $100m$ 和 $200m$ 处分别突出一根无限长的钢管，人默认可以安全地站在上面。

你的手中有一把剪刀和一条长为 $150m$ 且极细的绳子，你可以打死结，不能打活结，且结的大小忽略不计。问你怎么安全下到地面。

解法：

$150m$ 长的绳子不足以让我们直接下去，所以必然需要借助第二根钢管。于是我们考虑将绳子弄成这样子：

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

即将绳子剪成 $50m$ 和 $100m$ 两段，$50m$ 长的绳子的末端打一个小环，然后将 $100m$ 长的绳子穿入小环并首尾连接。这样就凑出了 $100m$ 的绳子。

把 $50m$ 绳子的另一端系在第一根钢管上，借助它下到第二根钢管，用剪刀剪断环，抽出 $100m$ 长的绳子，即可顺利下到地面。我们称这种方法为“环套”法。

以下是整个过程示意图。

![](https://s1.ax1x.com/2023/06/01/p9zy3qI.jpg)

注意：图中的圆圈代表绳两端系着的小环，实际大小忽略不计。

“环套法”中，我们把绳子分为两部分：环和链。其中环可以回收利用。

在接下来的题目场景中，我们默认只有“环套法”和“简化的环套法”两种方式可用。其中“简化的环套法”为环的长度为 $0$ 或链的长度为 $0$。

（感谢 huzheng20 提供的图 Orz）

description:
在一栋楼上有 $n$ 个钢管，其中第 $i$ 个钢管高度为 $h_i$，权值为 $v_i$，你处在最高的某个钢管上，手中有一把剪刀和一条绳子，要求所经过的钢管权值必须组成单调**不减**序列。

某些钢管的高度可能相同，这意味着你在这个高度可以选择不同权值的钢管落脚。

你的绳子的初始长度必须为**正整数**，但你可以在使用环套法后回收得到一根非整数长度的绳子。

问最少需要多长的绳子才能下到地面。

inputFormat:
第一行一个正整数 $n$，表示钢管个数。

接下来 $n$ 行，每行两个正整数 $h_i,v_i$，表示第 $i$ 个钢管的高度和权值。

outputFormat: 一行一个正整数表示最少需要多长的绳子。

hint:
**本题开启捆绑测试**。

对于 $10\%$ 的数据，保证从高到低来看，钢管权值组成单调**不增**序列。

对于另外 $10\%$ 的数据，保证 $n\le 10^4$。

对于另外 $40\%$ 的数据，保证 $n\le 10^5$ 且不存在下标 $i,j$ 满足 $h_i=h_j$ 或 $v_i=v_j$。

对于所有数据，保证 $1\le n\le 5\times 10^5$，$1\le h,v\le 10^{18}$。


title: 『STA - R2』Gtrimee

description:
令满足如下条件的儿子有序的无标号有根树数量为 $w_k(n)$：
- 点数 $n_0\in[1,n]$。
- 所有深度为 $k$ 的点都不是叶子。

给定固定正整数 $k$，多次给定正整数 $n$，求 $w_k(n)\bmod 998244353$ 的值。

此处一个点的深度定义为它到根的唯一简单路径的长度，比如根的深度就是 $0$。

inputFormat:
**本题有多组询问。**

第一行一个正整数 $id$ 表示 Subtask 编号。

第二行两个正整数 $q,k$，其中 $q$ 表示询问次数。

后 $q$ 行，每行一个正整数 $n$，描述一组询问。

outputFormat: $q$ 行，每行对应一个 $w_k(n)\bmod 998244353$。

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

$k=2$，树上恰有 $5$ 个点时的所有方案：

![](https://cdn.luogu.com.cn/upload/image_hosting/pwgn6z92.png)
### 数据范围
**本题采用捆绑测试。**
$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline\hline
\textbf{Subtask} & \bm{n}\le & \textbf{分值} & \textbf{特殊性质}\\\hline
\textsf{1} & 5 & 5  \\\hline
\textsf{2} & 10^2 & 20\\\hline
\textsf{3} & 2\times10^5 & 35 & k=1\\\hline
\textsf{4} & 2\times10^5 & 40\\\hline\hline
\end{array}
$$

对于全部数据，$1\le n,q,k\le 2\times10^5$。


title: 「RiOI-03」网格

background:
2022 年某次集训讲课，课件中出现了一道以 MLE 真名首字母严格顺序作为输入变量的题目。MLE 就想在自己的题目里用 [vectorwyx](https://www.luogu.com.cn/user/238408) 的首字母当输入变量，于是就有了这道题。

可惜如今 [vectorwyx](https://www.luogu.com.cn/user/238408) 已经退役了，人生有梦，各自精彩。

description:
**请仔细阅读本题数据范围。**

给定一个 $n\times n$ 的正方形网格，一共有 $n$ 行，$n$ 列，初始时所有网格均为红色。有 $n$ 组询问，每次询问会把一整行或一整列的颜色全部染成红色或白色，每次询问后输出所有红色网格的周长，而且询问之间不独立。

inputFormat:
第一行为一个正整数 $n$；

接下来的 $n$ 行，每行三个正整数 $w,y,x$。$w$ 表示颜色，$w=1$ 表示染成红色，$w=0$ 表示染成白色。$y$ 表示行或列，$y=1$ 表示把第 $x$ 行全部染色，$y=0$ 表示把第 $x$ 列全部染色。

outputFormat: 一共有 $n$ 行，每行一个整数，表示每次修改后的红色部分周长。


title: 「DBOI」Round 1 三班不一般

background:
HQ 是传奇颜值中学的一位尽职尽责的后勤部教师，同时也是宿舍的管理成员，负责管理开关灯。

对于他来说，最令人厌烦的的就是极不一般的三班的一群猴子乱玩自己宿舍和别人宿舍的灯，但是却没法当场发现并抓捕始作俑者。

description:
HQ 需要管理 $n$ 个宿舍的灯，第 $i$ 个宿舍的同学因为有着传奇颜值而十分挑剔，只能忍受亮度为 $[l_i,r_i]$ 的灯。每个宿舍的灯的亮度可以在对应的可忍受范围内肆意调节。

今天陈添润决定成为总司令，对所有宿舍的灯进行调节，为了防止被 HQ 当场抓捕，他不能让 HQ 发觉宿舍的灯太过刺眼，当连续 $a$ 个宿舍的灯亮都大于 $b$ 的时候，宿舍的灯就刺眼了。$\color{white}\text{不可以，总司令}$

因此，帮助陈添润数一数一共有多少灯泡调节方案能满足宿舍不刺眼，答案对 $998244353$ 取模。

inputFormat:
第一行是三个正整数 $n,a,b$，含义如题所示。

下面一共 $n$ 行，每行两个正整数，第 $i$ 行的两个正整数分别表示 $l_i,r_i$。

outputFormat: 一行一个整数，表示答案，对 $998244353$ 取模。


title: [CEOI 2013] 新宝岛 / Treasure

background:
翻译自 [CEOI 2013 Day 1](https://ceoi2013.hsin.hr/tasks/tasks_day1.pdf)。

**这是一道 IO 交互题。**

一次地震过后，亚得里亚海出现了一座新岛。在岛上发现了一个特殊装置，名叫“神谕”。尽管没有说明手册，但考古学家和计算机专家的队伍成功地理解了它的行为。

神谕提供了一些有关该岛宝藏位置的信息。该岛被分为一个 $N$ 行 $N$ 列的网格，其中行和列都从 $1$ 到 $N$ 编号。网格中的一些单元格包含宝藏。神谕只会回答以下形式的问题：“给定网格中的一个矩形，在这个矩形中，有多少个单元格包含宝藏？”

**尽管神谕可以回答所有大小的矩形问题，但发现请求的信息越具体（矩形越小），神谕在回答时消耗的能量越多**。更精确地说，如果一个矩形包含 $S$ 个单元格，则神谕将使用 $1 + N \times N - S$ 个单位的能量来回答。

description:
编写一个程序，通过与神谕交互的方式，确定该岛上所有含有宝藏的单元格的位置。我们不希望在此过程中使用过多的能量，能量使用越少越好。但是也不要求使用的能量数量是最小的，具体得分规则见最后的“说明/提示”。

这是一个交互式任务。您的程序使用标准输出向神谕提问，并通过读取标准输入来获得答案。

- 在程序开始时，它应该读取一个整数 $N$（$2 \leq N \leq 100$），表示网格的大小。
- 要向神谕提问，您的程序应输出一行包含 $4$ 个整数 $R_1$、$C_1$、$R_2$ 和 $C_2$，它们之间由空格分隔，使得 $1 \leq R_1 \leq R_2 \leq N$ 和 $1 \leq C_1 \leq C_2 \leq N$ 成立。如果条件不成立或行格式不正确，则您的程序在该测试运行中将得零分。
- 神谕将响应一个包含单个整数的行 - 包含宝藏的矩形中提供的单元格数。更确切地说，是 $R_1 \leq R \leq R_2$ 且 $C_1 \leq C \leq C_2$ 且位于行 $R$、列 $C$ 的单元格包含宝藏的单元格数（$R$，$C$）。
- 当程序完成提问（已经确定所有宝藏的位置）后，它应在新的一行上输出 `END`。然后，再输出 $N$ 行，每行包含 $N$ 个 `0` 或 `1` 字符的字符串。第 $R$ 行中的第 $C$ 个字符是 `1`，如果该行中列 $C$ 的单元格中有宝藏，则为 `0`，如果没有，则为 `1`。行从顶部到底部编号为 $1$ 到 $N$，列从左到右编号。一旦您的程序输出解决方案，程序的执行将会自动终止。

为了与评分器正确交互，需要在每个问题和写出解决方案后**刷新标准输出**，这是交互题的惯例。

在每个测试运行中，可以假定神谕必然正确回答问题，并且在交互之前宝藏的位置是确定的。换句话说，答案不会取决于程序先前问的问题（不会根据你问的问题来改变答案），它在每个测试点都是固定的。

inputFormat: 该任务是一个交互式任务。要成功完成任务，需要编写一个程序以最大化降低向神谕提问的次数和使用的能量。在程序开始时，输入岛屿的大小 $N$。

outputFormat: 通过输出行号和列号的方式向神谕询问包含宝藏的单元格数量。每当程序获得答案后，就要输出 `END`，然后将宝藏位置汇总并输出。最终得分将由程序使用的能量数量确定。具体评分标准在题目的最后面，具体格式可见输入输出的一组样例。

hint:
[样例解释](https://www.luogu.com.cn/paste/tpzc0qdt)

每个测试用例得分为 $10$ 分。如果程序的输出不正确，则该测试用例得零分。否则，根据神谕使用的总能量单位 $K$ 来确定分数。

具体而言:
- 如果 $K ≤ \frac{7}{16} N^4 + N^2$，则得 $10$ 分。
- 否则，如果 $K ≤ \frac{7}{16} N^4 + 2N^3$，则得 $8$ 分。
- 否则，如果 $K ≤ \frac{3}{4} N^4$，则得 $4$ 分。
- 否则，如果 $K ≤ N^4$，则得 $1$ 分。
- 否则，得 $0$ 分。

此外，在至少占总分 $40\%$ 的测试数据中，$N$ 将最多为 $20$。

总而言之，**花费的能量越少，你的得分就越高**。

交互库/SPJ 提供者：@[Sprague_Garundy](https://www.luogu.com.cn/user/764746) 。


title: [语言月赛202305] 独行

background:
> ### 独行
>
> 独乘木舟去，
> 心愁神难怡。
> 佳人千里外，
> 思绪终不渝。

zyl 于 2023 年 3 月 28 日写下，并赠予他心仪的那个女孩。

description:
zyl 是一名初三的 OIer。

zyl 在自己的家乡没有学习 OI 的时间与契机，一天他收到了其它学校的邀请，为了追梦，他同意了，并选择乘船前往。

不过只有 zyl 一个人去那里，在路上，他总是会特别思念在教室里的那个她。

zyl 于 $2023$ 年 $4$ 月 $1$ 日的凌晨 $00:00$ 出发前往距离家乡 $S\text{ m}$ 的目的地，他乘船向目的地行驶的速度是 $v_{0}\text{ m/s}$ 。他在路上会不间断的思念起她，每次都会调转船头，希望能回去和她一起相处。他一共思念了 $n(1\le n \le 100)$ 次，第 $i$ 次思念是在他行驶了 $T_{i}$ 秒后开始的。

在第一次，他思念了 $t_{1}$ 秒，并以 $v_{1}\text{ m/s}$ 的速度向家乡行驶。之后的每一次， zyl 的思绪会比上一次更加深，速度比上一次**增加** $v_{2}\text{ m/s}$，时间比上一次**增加** $t_{2}$ 秒。

但是，如果 zyl 已经抵达目的地了，他就只会站在那不动，望着家乡的方向……每次思念结束后， zyl 又会以最初的速度向目的地继续行驶。一旦到达目的地，他就会停下。

如果他在思念的过程中回到了家乡，他会花思念剩下的时间与她下一盘棋，因为在之前，他们最喜欢一起做的事就是下棋了。

（然而在现实生活中，他每时每刻都在想她。）

他没有带表，想知道自己是在哪一天的哪一秒到达目的地的。由于他还要赶着上课，在 $2023$ 年 $4$ 月 $30$ 日 $23:59:59$ 之前，他一定会到达目的地。

inputFormat:
共 $3$ 行

第一行 $6$ 个整数 $S$，$v_{0}$，$v_{1}$，$t_{1}$，$v_{2}$，$t_{2}$，用空格隔开。含义如题所示。

第二行 $1$ 个整数 $n$。

第三行 $n$ 个整数，第 $i$ 个为 $T_{i}$。用空格隔开。

outputFormat:
共 $1$ 行一个字符串，必须以 `202304xxatxx:xx:xx` 的形式。其中 `x` 就是对应的时间对应的字符。注意，如果是日，时，分或秒是个位数，前面要补上一个 `0`。

如果到达的时间不是整数秒，则**向上取整**。例如在 $1.1$ 秒到达，则记为 $2$ 秒。

hint:
输入的所有数据都是整数。

对于 $40\%$ 的数据，$ v_{2}=t_{2}=0$；

对于另外 $20\%$ 的数据 $n=1$;

对于 $100\%$ 的数据，$1\leqslant n \leqslant 100$，$1\leqslant S \leqslant 2\times10^{9}$，$1\leqslant v_{0} \leqslant S$，$1\leqslant v_{1},t_{1} \leqslant 500$，$0\leqslant v_{2},t_{2} \leqslant 50$，$0\leqslant T_{i} \leqslant 20080626$，保证 $T$ 单调递增，且保证不会有两次思念的时间重叠，保证到达时间一定是在四月份。数据并不保证到达目的地后 zyl 就不会想她了。

>在最后想对学弟学妹们说，学习编程的道路十分漫长，人生的道路亦是如此。在这漫长的道路上，你们一定会碰到一些在你们心中特别重要的人。有时候，你们不得不与这些人离别。请你们千万要珍惜与重要的人相处的每一天，不要等到离别的时候才后悔当初没有好好珍惜。永远怀揣理想，不为青春留遗憾！
>
>—— zyl


title: [语言月赛202305] 计算阶乘

background:
相信你已经知道**阶乘**的定义：

$$n! = n \times (n - 1) \times (n - 2) \times \dots 1$$

现在，我们给出**双阶乘**的定义：

当 $n$ 为奇数时，
$$n!! = n \times (n - 2) \times (n - 4) \times \dots \times 1$$

当 $n$ 为偶数时，

$$n!! = n \times (n - 2) \times (n - 4) \times \dots \times 2$$

特别的，$0!! = 1$。

例如，$5!! = 5 \times 3 \times 1 = 15$，$6!! = 6 \times 4 \times 2 = 48$。

description: 给定整数 $n$，请你求出 $2 \times \dfrac{n!}{n!!}$ 的值。

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

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

对每组数据，输入只有一行一个整数表示给定的 $n$。

outputFormat: 对每组数据，输出一行一个整数表示 $2 \times \dfrac{n!}{n!!}$ 的值。


title: [语言月赛202305] 你的牌太多了 2

background: 相信你对笨蛋扶苏和坏蛋小 F 打牌的[故事](https://www.luogu.com.cn/problem/B3745)记忆犹新。这次，她们又在打一种很新的牌。

description:
初始时，扶苏和小 F 手中各有 $n$ 张牌。每张牌有一个花色 $f$ 和一个点数 $p$。在本题中，花色是不超过 $m$ 的正整数，点数是不超过 $r$ 的正整数。

我们定义『一轮出牌』是指从某人开始出牌，双方轮流按规则打出手中的手牌，直到一方打不出符合要求的手牌结束。

在一轮出牌中，第一个出牌的人会打出**点数最小**的那张手牌。如果有多张手牌点数最小，则打出**点数最小且花色最小的那张手牌**。然后双方轮流出牌，规则是打出手中**花色与对方刚才打出的牌相同且点数大于对方的刚才打出的牌的点数中，点数最小的那张牌**。如果这样的牌不存在，那么本轮游戏结束，且下一轮由**对方**先出牌（即，本轮最后一手出牌的人下一轮先出）。

现在，给出双方的手牌和第一轮出牌的人，请你求出谁先打完手里的牌。

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

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

第一行是四个整数，表示一个人的手牌数 $n$，花色的上界 $m$ ，点数的上界 $r$ 和第一轮出牌的人 $s$。$s = 1$ 表示扶苏先出牌，$s = 2$ 表示小 F 先出牌。
第二行有 $n$ 个整数，第 $i$ 个整数表示扶苏第 $i$ 张牌的花色 $f1_i$。
第三行有 $n$ 个整数，第 $i$ 个整数表示扶苏第 $i$ 张牌的点数 $p1_i$。
第四行有 $n$ 个整数，第 $i$ 个整数表示小 F 第 $i$ 张牌的花色 $f2_i$。
第五行有 $n$ 个整数，第 $i$ 个整数表示小 F 第 $i$ 张牌的点数 $p2_i$。

outputFormat: 对每组数据，输出一行一个字符串。如果扶苏先打完手里的牌，请输出 `FS wins!`；如果小 F 先打完手里的牌，请输出 `FR wins!`。

hint:
## 数据规模与约定

- 对于 $10\%$ 的数据，$r = 1$；
- 对于 $20\%$ 的数据，$n = 1$；
- 对于 $50\%$ 的数据，$m = 1$；
- 对于 $100\%$ 的数据，$1 \leq T \leq 10$，$1 \leq n,m,r \leq 100$，$1 \leq s \leq 2$，$1 \leq f1_i, f2_i \leq m$，$1 \leq p1_i, p2_i \leq r$。


title: 『XYGOI round1』一棵树

background: java 今天带了一棵树到出题组，然后被不讲理的 MX 占为己有了。

description:
于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。

定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。

MX 想知道这棵树所有路径的权值之和，即 $\sum\limits_{x=1}^n\sum\limits_{y=1}^nw(x,y)$ 为多少。

答案可能很大，对 $998244353$ 取模。

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

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

第三行 $n-1$ 个正整数，第 $i$ 个数 $p_i$ 表示节点 $p_i$ 与节点 $i+1$ 之间有边。保证 $1\le p_i\le i$。

outputFormat: 一行一个整数，表示答案。答案对 $998244353$ 取模。


title: [AGM 2023 资格赛] 建设计划

description:
一组工程师正在计划建造一座新工厂。为了使他们的工厂可靠，他们希望以恒定且可靠的单位每秒速率创建各种物品。他们可以使用不同的机器来制作这些材料。每个机器都有自己的速度，影响制作过程。每种材料都有自己的制作配方，必须在特定的机器执行。

您将获得每个机器的描述以及您需要的每种材料和中间材料的配方。你也会得到一份材料清单，你必须以一定的速度生产，这样你的工厂是可靠的。

我们认为一种机器配置是最优的，当且仅当如果从配置中移除任意一台机器，至少有一种材料的生产速率小于所需的速率。

你需要找到一种最优的配置。

inputFormat:
输入的第一行将包含一个整数 $M(1≤M≤100)$，表示我们拥有的机器类型的数量。在接下来的 $M$ 行中，每一行都有一个字符串 $n(1≤|n|≤30)$ 和一个数字 $s(0.01≤s≤100)$，表示一台机器的名称和速度。

下面一行输入将包含一个整数 $N(1≤N≤100)$，表示配方的数量。

接下来输入 $n$ 组配方。对于每组配方，在配方的第一行，字符串 $p(1≤|p|≤30)$ 表示要制作的材料的名称，字符串 $l(1≤|l|≤30)$ 表示制作过程中使用的机器名称，数字 $t(0.01≤t≤100)$ 表示以正常速度制作材料所需的时间(以秒为单位)。在下一行中，有一个数字 $k(0≤k≤15)$，表示生产当前这个材料过程中所需另外材料的种类数。下面的 $k$ 行中，每一行包含一个字符串 $n(1≤|n|≤30)$ ，表示所需材料的名称，一个整数 $c(1≤c≤10)$，表示所需的相应材料的单位数。

下一行将包含一个整数 $Q(1≤Q≤100)$，表示需求的数量。

下面的每一条 $Q$ 行都包含一个字符串 $m(1≤|m|≤30)$，表示需要这个需求下生产的材料的名称，以及一个整数 $c(1≤c≤10)$，表示每秒需要生产的该材料的单位数。

$s$ 和 $t$ 都是有两个小数点的浮点数。保证存在最优配置。保证最优解中每种材料的生产速率不超过每秒 $10^9$个单位，每种材料都可以使用独特的配方制作。并且保证配方的需求关系不存在环。

outputFormat: 总共 $n$ 行，在第 $n$ 行，输出 $p_i,l_i,r_i$，其中 $r_i$ 表示用来执行第 $i$ 个配方的机器数量。

samples:
3
assembler 0.50
furnace 0.50
mining_well 0.55
6
iron_plate furnace 3.20
1
iron_ore 1
copper_plate furnace 3.20
1
copper_ore 1
iron_ore mining_well 1.00
0
copper_ore mining_well 1.00
0
copper_cable assembler 0.50
1
copper_plate 1
electronic_circuit assembler 0.50
2
iron_plate 1
copper_cable 3
1
electronic_circuit 10

samples:
iron_plate furnace 64
copper_plate furnace 192
iron_ore mining_well 19
copper_ore mining_well 55
copper_cable assembler 30
electronic_circuit assembler 10

samples:
3
assembler 0.50
furnace 0.50
mining_well 0.55
4
iron_plate furnace 3.20
1
iron_ore 1
iron_ore mining_well 1.00
0
iron_gear assembler 0.50
1
iron_plate 2
transport_belt assembler 0.50
2
iron_plate 1
iron_gear 1
1
transport_belt 7

samples:
iron_plate furnace 135
iron_ore mining_well 39
iron_gear assembler 7
transport_belt assembler 7


title: [AGM 2023 资格赛] DrahSort

description:
给定一个长度为 $N$ 的序列 $A$，接下来进行 $Q$ 次询问。

- 每次询问 $[l,r]\ (l\leq r)$，输出：如果对这个区间进行冒泡排序，那么交换的相邻两个数的乘积的最大值。

inputFormat:
输入的第一行将包含一个整数 $N(1≤N≤2\times 10^5)$，表示数组的元素个数。

第二行输入将包含 $N$ 个整数 $(0≤A[i]≤10^9,1≤i≤N)$，即数组的元素。

第三行输入将包含一个整数 $Q(1≤Q≤2\times10^5)$，表示操作次数。

下面的每 $Q$ 行都包含一个题目中描述的询问。

outputFormat: $Q$ 行，对每一次询问输出答案。


title: [AGM 2023 资格赛] 麦田

description:
最近，你从你的曾曾祖父那里继承了一块地。这块地是一个矩形，有 $N$ 行 $M$ 列。你想继续你的高曾祖父的遗产，并开始种植两种植物：小麦和向日葵。

在田地的每个格子里，你可以放两种植物种子中的一种。在细胞 $(i,j)$ 种植小麦可以获得 $A[i][j]$ 欧元，而在同一细胞 $(i,j)$ 种植向日葵可以获得 $B[i][j]$ 欧元。

不幸的是，你很快就会发现，如果你在相邻的细胞中种植不同类型的植物，它们的根会缠在一起，这需要你花一大笔钱来修复。

你现在急切地想知道，如果你在每个细胞中只种植两种植物种子中的一种，你能获得的最大金钱是多少。

inputFormat:
输入的第一行包含两个整数 $N(1≤N≤70)$ 和 $M(1≤M≤70)$，表示行数和列数。

接下来的 $N$ 行包含 $M$ 个整数 $(1≤A[i][j]≤10^5)$。

接下来的 $N$ 行包含 $M$ 个整数 $(1≤B[i][j]≤10^5)$。

接下来的 $N$ 行将包含 $M−1$ 个整数 $(1≤C_1[i][j]≤10^5)$，表示在细胞 $(i,j)$ 和 $(i,j+1)$ 中播种不同种子的损失。

接下来的 $N-1$ 行将包含 $M$ 个整数 $(1≤C_2[i][j]≤10^5)$，表示在细胞 $(i,j)$ 和 $(i+1,j)$ 中播种不同种子的损失。

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


title: [AGM 2023 资格赛] 反转

description:
给定长度为 $N$ 的序列 $a$ 满足每个数都小于 $2^K$。你需要执行恰好 $P$ 次操作，每次操作是把其中一个数的某一个二进制位反转。最终你需要使得

$$\sum_i\sum_j a_i\oplus a_j(i<j)$$

最大，其中 $\oplus$ 为按位异或运算。

inputFormat:
第一行包含整数 $N、K、P$，保证 $1≤N≤10^5,1≤K≤30,1≤P≤N\times K$。

下一行包含 $N$ 个整数，即序列 $a$。对于所有 $1≤i≤N$，保证 $0≤a_i<2^K$。

outputFormat:
$P$ 行，每行包含两个整数 $i$ 和 $j$，满足 $1≤i≤N, 0≤j<K$，表示数字 $a_i$ 的第 $j$ 位反转。即 $a_i\leftarrow a_i \oplus 2^j$。

**你可以多次反转同一个位。如果有多个使总和最大化的解输出任意一个即可。**


title: [AGM 2023 资格赛] 另一个游戏

description:
Charlie 和 Dan 在 $N$ 堆从左到右从 $1$ 到 $N$ 编号的石子堆上玩游戏。每一堆都有正数个石头。

两人轮流执行操作。Charlie 先手。

每回合，玩家从最左边的非空堆中取出正数个石头，并将它们移到相邻的右边的石头堆中。如果在该玩家的回合中，唯一的非空堆是第 $N$ 堆，该玩家将输掉游戏。

如果双方都以最优策略玩这场游戏，谁会赢得这场游戏?

inputFormat:
输入的第一行将包含整数 $N(2≤N≤10^3)$，即堆数。

下一行包含 $N$ 个整数 $v_1,v_2,v_3,...,v_n(1≤v_i≤10^9)$ 表示每堆石子的数量。

outputFormat: 输出获得胜利的玩家的名字。


title: [AGM 2023 资格赛] IPs

background: Mike 刚在当地的互联网服务提供商 DNS 找到了一份实习工作。他们知道 Mike 对 IPs 很熟悉，所以请他为他们的客户实现一个支持一些操作的管理系统。其中一些操作是特定于客户端的，而另一些是特定于 DNS(公司) 的。Mike 其实对 IPs 不太了解，所以他向你寻求帮助。

description:
IPs 的取值范围是 $0$ 到 $10^9$，所有客户端最初都可以使用。有 $N$ 个国家（编号从 $0$ 到 $N−1$）。每个国家都有自己的 ip 集，形式上可以表示成若干个区间的并集。

有 $M$ 个客户端（编号从 $0$ 到 $M−1$）需要 Mike 帮助，有 $Q$ 个操作，有以下形式:

1.将一个国家列入所有客户端的黑名单。将一个国家列入黑名单，将阻止该国家及其与其合并的国家对应的所有 ip。

2.将所有客户端的 ip 段 $[X,Y]$ 加入黑名单。

3.为特定客户端将某个国家及其与其合并的国家列入黑名单。

4.将特定客户端的 ip 段 $[X,Y]$ 加入黑名单。

5.为特定客户端将某个国家及其与其合并的国家列入白名单。将一个国家加入白名单，将该国家及其合并国家对应的所有 ip 都加入白名单。请注意，白名单的优先级高于此客户端的任何先前或将来的黑名单。也就是说如果一个 ip 在某个客户端被列入白名单，那么永远不会被适用与接下来以及之前的所有黑名单操作。

6.为特定客户端将 ip 段 $[X,Y]$ 列入白名单。请注意，白名单的优先级高于此客户端的任何先前或将来的黑名单。也就是说如果一个 ip 在某个客户端被列入白名单，那么永远不会被适用与接下来以及之前的所有黑名单操作。

7.国家 $X$ 和 $Y$ 合并在一起。

8.查询某个客户端在 ip 段 $[X, Y]$ 内可以访问多少个 ip ？

inputFormat:
第一行三个数 $N,M,Q$。保证 $1\leq N\leq 10^4,1\leq M\leq 10,1\leq Q\leq 10^5$。

接下来 $N$ 行，每行第一个数 $N_i$ 表示第 $i$ 个国家的 ip 集由 $N_i$ 个区间的并集。接下来 $2\times N_i$ 个数，表示每个区间，这些数在 $0$ 到 $10^9$ 之间。保证 $\sum N_i\leq 10^5$。

接下来 $Q$ 行，每行第一个数表示操作的种类，接下来对于每种操作输入对应的参数：

1：$countryIdx$，保证 $0≤countryIdx<N$。

2：$X, Y$，保证 $0≤X≤Y≤10^9$。

3：$clientIdx, countryIdx$，保证 $0≤clientIdx<M, 0≤countryIdx<N$。

4：$clientIdx,X, Y$，保证 $0≤clientIdx<M, 0≤X≤Y≤10^9$。

5：$clientIdx, countryIdx$，保证 $0≤clientIdx<M, 0≤countryIdx<N$。

6：$clientIdx,X, Y$，保证 $0≤clientIdx<M, 0≤X≤Y≤10^9$。

7：$countryIdx1, countryIdx2$，保证 $0≤countryIdx1<N, 0≤countryIdx2<N$。

8：$clientIdx,X,Y$，保证 $0≤clientIdx<M, 0≤X≤Y≤10^9$。

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


title: [AGM 2023 资格赛] Monty Hall

description:
Monty Hall 是一个节目主持人，这一天，他决定推出一个新游戏。

总共有 $n$ 扇门围成一个圈，玩家现在站在第 1 扇门前，每个回合玩家会执行以下操作：选择一个数 $i$，花费 $C_i$ 的代价选择往右移动 $i$ 步，然后玩家打开他所在位置的门。特别地，保证 $C_i\geq C_{i+1}(1\leq i<n)$。

玩家想知道打开所有的门最少需要花费多少代价。

inputFormat:
第一行一个整数 $N(1\leq N\leq 10^5)$。

接下来 $N$ 个整数表示 $C_i(1\leq C_i\leq 10^5)$。

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


title: [AGM 2023 资格赛] Nădlac

description:
在草原上，一群绵羊排成一队。这些绵羊的毛共有 $7$ 种颜色，按照你对颜色喜欢的程度排列分别是：

$$
red>orange>yellow>green>blue>indigo>violet$$

接下来会发生以下三种事件：

1：有若干个绵羊依次排到了队尾。

2：给定一个颜色序列 $T$，找到目前的绵羊序列中，所有本质不同的子串中按照喜欢程度写成数字（比如 red 是 $7$,violet 是 $1$），字典序小于等于 $T$ 中字典序最大的一个子串。

3：给定一个颜色集合 $C$，求目前的绵羊序列中，本质不同的只由 C 中的颜色组成的子串的长度的和。

inputFormat:
输入的第一行将包含一个整数 $Q (1≤Q≤500)$，表示发生的事件数。

接下来的 $Q$ 行每行先输入一个数表示事件的种类，然后：

1：输入绵羊序列 $S(1≤|S|≤10^5)$。 保证 $∑|S|≤10^5$。

2：输入颜色序列 $T(1≤|T|≤10^5)$。

3：输入颜色集合 $C(1≤|C|≤7)$。

其中每个颜色由单词的第一个字母的大写形式表示。

outputFormat: 对每个事件 2 与事件 3 输出答案。


title: [AGM 2023 资格赛] 回文

description:
定义一个关于一个字符串 $x$ 的函数 $f(x)$ 如下：

- 如果 $x$ 长度为 $1$，$f(x)=1$。
- 如果 $x$ 不是回文串，$f(x)=0$。
- 如果 $x$ 是回文串，那么假设 $y$ 是 $x$ 的前 $\frac{|x|+1}{2}$ 个字符组成的字符串 $f(x)=f(y)+1$。

给你一个字符串 $s$ 与一个数 $k$，求它每个非空子串中 $f$ 等于 $1\sim k$ 的分别有多少个。

inputFormat:
第一行两个数 $N(1\leq N\leq 10^5)$，$k(1\leq k\leq 30)$。

接下来一行一个长度为 $N$ 的字符串 $s$。保证由小写字母组成。

outputFormat: 对于 $1\sim k$ 的每个数输出答案。


title: [AGM 2023 资格赛] 棋子游戏

description:
Alice 和 Bob 在一个 $1\times N$ 的矩阵上玩游戏。

有 $M$ 个棋子放在不同的格子上，棋子具有各种各样的颜色。

每回合选手可以挑选一个棋子，并将这个棋子与后面的跟他不同颜色的棋子（下一个同色棋子之前的棋子）一起往左移动正数距离，移动过程中不能跨过或者重叠前面的那个格子。Alice 先手，谁不能移谁就输了。

接下来有 $Q$ 次操作，每次操作有以下形式：

1：在 $pos$ 位置上放置一个颜色为 $col$ 的棋子。

2：删除位置 $pos$ 上的棋子。

每次操作后输出当前局面的赢家是谁。

inputFormat:
第一行输入两个数 $N,M(1\leq N\leq 10^9,1\leq M\leq 10^5)$。

接下来输入 $M$ 行，每行两个数 $pos(1\leq pos\leq n),col(1\leq col\leq 5)$ 表示初始 $pos$ 位置上有一个 $col$ 颜色的棋子。

接下来输入 $Q$ 行，每行两或三个数 $opt(1\leq opt\leq 2)$ 表示操作种类，$pos(1\leq pos\leq n)$。若 $opt=1$ 则还要读入 $col(1\leq col\leq 5)$。

outputFormat: $Q$ 行，每行输出 Alice 或者 Bob。


title: [PA 2022] Palindrom

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda próbna [Palindrom](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/pal/)**

Bytie 参加了计算机俱乐部，因此知道了什么是回文串。回文串是从左向右读和从右向左读一样的单词。比如 `oko`，`kajak`，`kobyłamamałybok` 和 `ababbaba` 都是回文串，但是 `kajaki`，`zoo`，`alamakota` 和 `abaababa` 都不是回文串。

他迅速打开了笔记本并写下了一个只包含 `a` 和 `b` 两个字母的单词。然而在回忆了一会儿后，他想起这个单词不一定是一个回文串，因此他决定修改一下！在一秒内，它可以选择两个相邻的字母并交换他们的位置。他是否可以通过有限次操作（或者什么也不做）把这个字符串变成一个回文串？如果可以的话，最少要多少秒才可以？请帮他写一个程序计算这个最小时间。

inputFormat: 输入一行一个字符串，表示 Bytie 所写的单词。这个字符串仅包含 `a` 和 `b` 两种字母。

outputFormat: 输出一行一个整数，如果可以通过有限次操作将这个字符串变为回文串，输出最小时间，否则输出 $-1$。

hint:
对于 $100\%$ 的数据，满足：

字符串长度不超过 $2 \times 10^5$。


title: [PA 2022] Wielki Zderzacz Termionów

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 1 [Wielki Zderzacz Termionów](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/wzt/)**

Albert Bynstein 教授发现了一种新的基本粒子：热离子。如果他的实验成功，就可以在他的帮助下修建一个发电站，这样就可以解决 Byteland 的能源问题了。

这些粒子有三种类型，用红色，绿色和蓝色表示。这个名称与粒子实际的颜色或者光的波长无关，只是 Bynstein 教授用这些颜色的马克笔标记这些粒子。

红色和绿色的热离子可以发生反应，但只与另一个相同颜色的粒子发生反应。当两个红色热离子碰撞时，产生一个绿色热离子，并释放 $1$ 字节焦耳的能量。如果两个绿色热离子发生碰撞，就会产生一个红色热离子，同时释放 $1$ 字节焦耳的能量。

蓝色热离子不与其他热离子反应，但是它们是不稳定的。产生蓝热离子 $72$ 小时后，它会随机变成红热离子或绿热离子中的一个，变成任何离子都不会释放能量。

教授正在准备一个受控的实验反应。为此，他在实验室里准备了排成一排的 $n$ 个热离子。几天后，他打算把这些离子带到目前正在首都地下建造的大型热离子对撞机。到那时，所有的蓝色热离子都将变成红色或绿色热离子。

在对撞实验中，教授想进行一连串的反应，以产生 $n-1$ 字节焦耳的能量，并最后只留下一个热离子。每次反应可以选择相邻的两个热离子。所产生的热离子与左边和右边的热离子相邻，并能与它们发生进一步的反应。

问题是，当所有的蓝色热离子都发生变化时，有多大概率存在一个可行的反应序列。

你的任务是计算蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去。

此外，教授还会在他的实验室里对热离子的位置进行改变，每次都把一个热离子换成另一个（也许不会改变其类型）。在每一次这样的变化之后，也要计算出结果。

inputFormat:
第一行包含两个整数 $n$ 和 $q$ 分别表示热离子个数和改变次数。

第二行一个长为 $n$ 的字符串，表示初始时热离子的排列情况。字符串只包含 `C`，`Z` 和 `N` 三种字符，分别表示红色，绿色和蓝色热离子。左起第 $k$ 个字符表示第 $k$ 个热离子的颜色。

接下来 $q$ 行表示对上述字符串的修改。每行包含一个数字 $k_i$ 和一个字符（`C`，`Z` 和 `N` 之一）。表示第 $i$ 步中，教授将第 $k_i$ 个粒子换成了这个字符所表示的新粒子。

outputFormat:
输出 $q+1$ 行，第 $i+1$ 行输出一个整数，表示经过前 $i$ 个修改后的答案。

输出蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去，生成 $n-1$ 字节焦耳能量。

hint:
对于 $100\%$ 的数据，满足：

$1\le n\le 2 \times 10 ^ 5, 0\le q\le 10 ^ 5, 1\le k_i\le n$。


title: [PA 2022] Ornitolog 2

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 1 [Ornitolog 2](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/orn/)**

交替鹡鸰（*Motacilla alterna*）是鹡鸰属的一种鸟类。它因其独特的鸟鸣而与众不同，这种鸟的鸟鸣中，连续的音高交替地增加和减少。例如，如果我们用整数来表示音高，那么，鸟鸣可以是 $[2, 1, 3]$ 和 $[4, 5, -6, -5]$，但不能是 $[1, 2, 3, 2]$ 或 $[6, 5, 5, 4]$。为了记录这种迷人的生物，鸟类学家 Byteasar 将他的录音笔留在森林中数天。他现在想知道录到的声音是否与鹡鸰的鸟鸣相似。

写一个程序，给定音高序列，确定最少将音高序列中多少个整数改成 $[-10^9,10^9]$ 区间内的任意整数，才能使得这个序列成为交替鹡鸰鸟鸣的音高序列。

inputFormat:
第一行一个整数 $n$，表示这个音高序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示这个音高序列。

outputFormat: 输出最少要修改多少整数才能使这个序列成为交替鹡鸰鸟鸣的音高序列。


title: [PA 2022] Liczenie punktów

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 1 [Liczenie punktów](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/pun/)**

PA 的裁判们已经厌倦了不断计算所有提交代码的得分。请帮助他们实现这一过程的自动化。

对于每道题，一次提交可以得 $0$ 到 $10$ 分。一道题中有 $n$ 组测试数据，其中 $n$ 可以被 $10$ 整除。如果这个代码可以通过前 $\frac{n}{10}$ 组数据，那么会得一分，如果代码可以通过接下来的 $\frac{n}{10}$ 组数据，就会再得一分。一次提交可以因为全部通过了一个测试点内所有 $\frac{n}{10}$ 组数据而独立地获得一分。如果在一个测试点内的某组数据出现错误，那么这次提交就拿不到这个测试点的分数。

注意：

1. 为了简单，我们假设每个测试点中都有相同组的测试数据，但是实际的算法竞赛中并不是这样。
2. 任何你写过的代码都可能拿来妨碍你（宇航员笑话）。

inputFormat:
第一行一个整数 $n$，其中 $n$ 是 $10$ 的倍数，表示测试数据组数。

接下来一行长度为 $n$ 的字符串，字符串中仅包含 `T` 和 `N` 两种字符，表示测试点的通过情况。其中 `T` 表示该测试点通过，`N` 表示该测试点未通过。

outputFormat: 输出一行一个整数，表示该提交的得分。


title: [PA 2022] Muzyka pop 2

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 2 [Muzyka pop 2](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/muz/)**

你可能还记得，Matthew 喜欢流行音乐。他刚刚编好一首新歌，就差给这首歌谱一个结尾了。

Matthew 想让这个结尾包含一些非空的音符，这些音符用其响度表示，响度是一个正整数。Matthew 可以使用任何响度的音符，但结尾的任务是逐渐淡出整首歌——出于这个原因，结尾的音符响度必须形成一个严格递减的序列。

你可能知道或记得，流行音乐中好的节拍是很重要的。这次 Matthew 发现响度为 $x$ 的音符的节拍值为 $x$ 的二进制形式中 $1$ 的个数。考虑这首歌的剩余部分，他想让这个结尾所有音符的节拍值之和恰好为 $n$。

帮他找到这个正确的音符响度序列。可以证明总存在至少一个满足条件的序列，因此你的任务是输出字典序最小的序列。

注：如果对于两个数字序列 $A$ 和 $B$，在两序列第一个不同的位置，$A$ 序列中这个位置包含的整数比 $B$ 序列的小，我们称数字序列 $A$ 的字典序比 $B$ 的字典序小。如果不存在这个位置，则称更短的那个数字序列字典序更小。例如，序列 $[1, 10000000]$ 的字典序小于序列 $[2,2]$，序列 $[4, 2, 20, 30, 40]$ 的字典序小于 $[4, 2, 100, 1]$，并且序列 $[5,4,3,2]$ 的字典序小于序列 $[5,4,3,2,1]$。

inputFormat: 输入一行一个整数 $n$，表示要求的序列中音符的节拍值之和。

outputFormat:
输出第一行包含一个整数 $k$，表示找到的这个序列的长度。

第二行包含 $k$ 个正整数，表示找到的这个序列。这个序列应该是字典序最小且严格递减的，并且这些正整数的二进制表示中 $1$ 的个数和应恰好是 $n$。


title: [PA 2022] Podwyżki

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 2 [Podwyżki](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/pod/)**

对于 Bytecorp 来说，2022 年是艰难的一年。商业决策失误，再加上不景气的市场状况，意味着公司无力为员工涨薪。为了准备应对员工提出的不舒服的问题，人资部门发明了一种方法来证明员工不值得涨薪。

根据一个雇员在连续几天内产生的总收益，可以将一年（在 Byteotia，一年不一定是 365 天）划分为若干区间，这将表明该雇员工作不投入。更确切地说，人资部门希望将收入序列划分为 $k$ 个连续区间，使得序列中的每个元素都恰好属于一个区间。如果**不可能**从每个区间选择一个元素，使所选元素形成严格的升序，那么这种划分是正确的。

Bytecorp 的未来在你手上。写一个程序读入某个雇员产生的收益序列和一个整数 $k$，并根据人资部门的要求把序列分成 $k$ 段，或者判断无法分成这样的 $k$ 段。

inputFormat:
输入的第一行包含两个整数 $n,k$，表示序列长度和要分成的段数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示收益序列。

outputFormat:
如果这个序列不能按如上方法分割，输出一行一个字符串 `NIE`。

否则输出两行，第一行一个字符串 `TAK`，第二行输出 $k-1$ 个整数 $v_1,\ldots,v_{k-1}$，表示正确的划分中除最后一个区间外，每个连续区间的右端点，最后一个区间的右端点一定是 $n$。

如果有多个正确答案，可以输出任意一个。


title: [PA 2022] Mędrcy

description:
### 警告：滥用本题卡评测者将被封号。

**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 3 [Mędrcy](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/med/)**

几个世纪以来，神奇的 Bitoland 一直是 $n$ 个贤者和 $m$ 条咒语的家园。根据古老的魔法法则，每条咒语恰好被 $n-2$ 个贤者知道。所有的贤者都知道每条咒语都被他们中的一些确定的人所知，但他们不知道到底有多少条咒语存在。每个贤者，对于他所知道的每一条咒语，都清楚地知道其他哪些贤者知道它。然而，贤者不知道存在多少他不知道的咒语。特别的，一个贤者可能不知道任何咒语——在这种情况下，他不知道是否存在咒语（但他仍然知道，如果存在咒语，则正好有 $n-2$ 个贤者会知道它们）。

贤者每天中午都会在 Stumegabyte 森林里聚会，但他们在那里不会互相交流，他们只是各自问候对方并进行冥想，晚上他们都回到自己的小屋。贤者除了在见面时看到对方之外，并没有其他任何方式的交流。他们这样做是因为他们害怕约束他们的古老传统，其中规定，如果一个贤者发现有他不知道的咒语，他必须在当天午夜神不知鬼不觉地离开这里，并且永远不能回到 Bitoland。

有一天，一个流浪者来到了 Bitoland。在观察了几天这些贤者之后，他决定去见他们，在那里他不明智地对所有贤者宣布：「我已经注意到，你们中至少有一个贤者知道至少一条咒语！」

流浪者将在 Bitoland 再停留 $k$ 天（最多一个月），每天观察聚会情况，但不会再多说什么。在这段时间里，会不会有一天，一些贤者不会在聚会上出现？

我们假设贤者的推断是完美的，也就是说，如果他们中的任何一个人能够从流浪者宣布的内容和他们所掌握的关于咒语的信息中推断出什么，那么现实情况一定是这样的，并且他们会这么做。

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

对于每个测试点，第一行包含三个整数 $n,m,k$，分别表示贤者人数，咒语个数和流浪者会观察会议的天数。贤者从 $1$ 到 $n$ 编号。

接下来 $m$ 行，每行两个整数 $a_i,b_i\ $，表示除了贤者 $a_i$ 和 $b_i$ 之外其他所有贤者都知道这条咒语。

outputFormat: 对于每组数据，如果接下来 $k$ 天的每一天，所有贤者都会来参加聚会，则输出一行 $-1$。否则输出两行。第一行包含两个整数 $d$ 和 $c$，其中 $d$ 表示有贤者没来聚会的最早的一次，$c$ 表示这一次没来聚会的贤者个数。第二行包含 $c$ 个整数，表示没来聚会的贤者编号，按从小到大的顺序输出。

hint:
对于 $100\%$ 的数据，满足：

$3\le n,1\le m,1\le k\le 30, 1\le a_i<b_i\le n$,

一组数据中所有测试点的 $n$ 之和不超过 $10 ^ 3$，所有 $m$ 之和不超过 $3 \times 10 ^ 3$。


title: [蓝桥杯 2023 省 A] 填空问题

description:
## A. 幸运数

小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 $2314$ 是一个幸运数字，因为它有 $4$ 个数位，并且 $2+3=1+4$。现在请你帮他计算从 $1$ 至 $100000000$ 之间共有多少个不同的幸运数字。

## B. 有奖问答

小蓝正在参与一个现场问答的节目。活动中一共有 $30$ 道题目，每题只有答对和答错两种情况，每答对一题得 $10$ 分，答错一题分数归零。

小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 $100$ 分，所以到达 $100$ 分时小蓝会直接停止答题。

已知小蓝最终实际获得了 $70$ 分对应的奖项，请问小蓝所有可能的答题情况有多少种？

inputFormat:
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

您可以通过提交答案文件的方式进行提交。你需要将你的答案放在 `1.out` 和 `2.out` 中，其中 `1.out` 对应 A 题的答案，`2.out` 对应 B 题的答案。

输入文件包含一个字符，代表题目编号（`A` 或 `B`），你需要输出对应的答案。

以下模板供参考：

```cpp
#include<bits/stdc++.h>
using namespace std;

char pid;
int main() {
    cin >> pid;
    if(pid == 'A')
        puts("Answer for Problem A");
    else
        puts("Answer for Problem B");
    return 0;
}
```

hint: 第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 A-B


title: [蓝桥杯 2023 省 A] 平方差

description: 给定 $L,R$，问 $L \leq x \leq R$ 中有多少个数 $x$ 满足存在整数 $y,z$ 使得 $x=y^2-z^2$。

inputFormat: 输入一行包含两个整数 $L,R$，用一个空格分隔。

outputFormat: 输出一行包含一个整数满足题目给定条件的 $x$ 的数量。


title: [蓝桥杯 2023 省 A] 更小的数

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

小蓝有一个长度均为 $n$ 且仅由数字字符 $0 \sim 9$ 组成的字符串，下标从 $0$ 到 $n-1$，你可以将其视作是一个具有 $n$ 位的十进制数字 $num$，小蓝可以从 $num$ 中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 $num_{new}$ 满足条件 $num_{new}<num$，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 $num$ 中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是 $0$，这是合法的。

inputFormat: 输入一行包含一个长度为 $n$ 的字符串表示 $num$（仅包含数字字符 $0 \sim 9$），从左至右下标依次为 $0 \sim n-1$。

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

hint:
#### 【样例说明】

一共有 $8$ 种不同的方案：

1. 所选择的子串下标为 $0\sim1$，反转后的 $num_{new} = 120102 < 210102$；
2. 所选择的子串下标为 $0\sim2$，反转后的 $num_{new} =  012102 < 210102$；
3. 所选择的子串下标为 $0\sim3$，反转后的 $num_{new} =  101202 < 210102$；
4. 所选择的子串下标为 $0\sim4$，反转后的 $num_{new} =  010122 < 210102$；
5. 所选择的子串下标为 $0\sim5$，反转后的 $num_{new} =  201012 < 210102$；
6. 所选择的子串下标为 $1\sim2$，反转后的 $num_{new} =  201102 < 210102$；
7. 所选择的子串下标为 $1\sim4$，反转后的 $num_{new} =  201012 < 210102$；
8. 所选择的子串下标为 $3\sim4$，反转后的 $num_{new} =  210012 < 210102$。

#### 【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \le n \le 100$；

对于 $40\%$ 的评测用例，$1 \le n \le 1000$；

对于所有评测用例，$1 \le n \le 5000$。


title: [蓝桥杯 2023 省 A] 颜色平衡树

description:
给定一棵树，结点由 $1$ 至 $n$ 编号，其中结点 $1$ 是树根。树的每个点有一个颜色 $C_i$。

如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。

求出这棵树中有多少个子树是颜色平衡树。

inputFormat:
输入的第一行包含一个整数 $n$，表示树的结点数。

接下来 $n$ 行，每行包含两个整数 $C_i,F_i$，用一个空格分隔，表示第 $i$ 个结点的颜色和父亲结点编号。

特别地，输入数据保证 $F_1$ 为 $0$，也即 $1$ 号点没有父亲结点。保证输入数据是一棵树。

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

hint:
#### 【样例说明】

编号为 $1,3,5,6$ 的 $4$ 个结点对应的子树为颜色平衡树。

#### 【评测用例规模与约定】

对于 $30 \%$ 的评测用例，$n \leq 200$，$C_i \leq 200$；

对于 $60 \%$ 的评测用例，$n \leq 5000$，$C_i \leq 5000$；

对于所有评测用例，$1 \leq n \leq 200000$，$1 \leq C_i \leq 200000$，$0 \leq F_i<i$。


title: [蓝桥杯 2023 省 A] 买瓜

description:
小蓝正在一个瓜摊上买瓜。瓜摊上共有 $n$ 个瓜，每个瓜的重量为 $A_i$。小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为 $m$。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 $m$ 的瓜。如果无论怎样小蓝都无法得到总重恰好为 $m$ 的瓜，请输出 $-1$。

inputFormat:
输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。

第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。

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

hint:
#### 【评测用例规模与约定】

对于 $20 \%$ 的评测用例，$n \leq 10$;

对于 $60 \%$ 的评测用例，$n \leq 20$;

对于所有评测用例，$1 \leq n \leq 30$，$1 \leq A_i \leq 10^9$，$1 \leq m \leq 10^9$。


title: [蓝桥杯 2023 省 A] 网络稳定性

description:
有一个局域网，由 $n$ 个设备和 $m$ 条物理连接组成，第 $i$ 条连接的稳定性为 $w_i$。

对于从设备 $A$ 到设备 $B$ 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。

我们记设备 $A$ 到设备 $B$ 之间通信的稳定性为 $A$ 至 $B$ 的所有可行路径的稳定性中最高的那一条。

给定局域网中的设备的物理连接情况，求出若干组设备 $x_i$ 和 $y_i$ 之间的通信稳定性。如果两台设备之间不存在任何路径，请输出 $-1$。

inputFormat:
输入的第一行包含三个整数 $n,m,q$，分别表示设备数、物理连接数和询问数。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，分别表示 $u_i$ 和 $v_i$ 之间有一条稳定性为 $w_i$ 的物理连接。

接下来 $q$ 行，每行包含两个整数 $x_i,y_i$，表示查询 $x_i$ 和 $y_i$ 之间的通信稳定性。

outputFormat: 输出 $q$ 行，每行包含一个整数依次表示每个询问的答案。

hint:
【评测用例规模与约定】

对于 $30 \%$ 的评测用例，$n,q \leq 500$，$m \leq 1000$；

对于 $60 \%$ 的评测用例，$n,q \leq 5000$，$m \leq 10000$；

对于所有评测用例，$2 \leq n,q \leq 10^5$，$1 \leq m \leq 3 \times 10^5$，$1 \leq u_i,v_i,x_i,y_i \leq n$，$
1 \leq w_i \leq 10^6$，$u_i \neq v_i$，$x_i \neq y_i$。


title: [蓝桥杯 2023 省 A] 异或和之和

description: 给定一个数组 $A_i$，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 $1 \leq L \leq R \leq n$ 的 $L,R$，求出数组中第 $L$ 至第 $R$ 个元素的异或和。然后输出每组 $L,R$ 得到的结果加起来的值。

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

第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔。

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

hint:
#### 【评测用例规模与约定】

对于 $30 \%$ 的评测用例，$n \leq 300$；

对于 $60 \%$ 的评测用例，$n \leq 5000$;

对于所有评测用例，$1 \leq n \leq 10^5$，$0 \leq A_i \leq 2^{20}$。


title: [蓝桥杯 2023 省 A] 像素放置

description:
小蓝最近迷上了一款名为《像素放置》的游戏，游戏在一个 $n \times m$ 的网格棋盘上进行，棋盘含有 $n$ 行，每行包含 $m$ 个方格。玩家的任务就是需要对这 $n \times m$ 个方格进行像素填充，填充颜色只有黑色或白色两种。有些方格中会出现一个整数数字 $x(0 \leq x \leq 9)$，这表示当前方格加上周围八个方向上相邻的方格（分别是上方、下方、左方、右方、左上方、右上方、左下方、右下方）共九个方格内有且仅有 $x$ 个方格需要用黑色填充。

玩家需要在满足所有数字约束下对网格进行像素填充，请你帮助小蓝来完成。题目保证所有数据都有解并且解是唯一的。

inputFormat:
输入的第一行包含两个整数 $n,m$，用一个空格分隔，表示棋盘大小。

接下来 $n$ 行，每行包含 $m$ 个字符，表示棋盘布局。字符可能是数字 $0 \sim 9$，这表示网格上的数字；字符还有可能是下划线（$\text{ASCII}$ 码为 $95$），表示一个不带有数字的普通网格。

outputFormat: 输出 $n$ 行，每行包含 $m$ 个字符，表示答案。如果网格填充白色则用字符 $0$ 表示，如果网格填充黑色则用字符 $1$ 表示。

hint:
#### 【样例说明】

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

上图左是样例数据对应的棋盘布局，上图右是此局游戏的解。例如第 $3$ 行第 $1$ 列处的方格中有一个数字 $3$，它周围有且仅有 $3$ 个格子被黑色填充，分别是第 $3$ 行第 $2$ 列、第 $4$ 行第 $1$ 列和第 $4$ 行第 $2$ 列的方格。

#### 【评测用例规模与约定】

对于 $50 \%$ 的评测用例，$1 \leq n,m \leq 5$；

对于所有评测用例，$1 \leq n,m \leq 10$。


title: [AGM 2023 资格赛] 海盗

description:
海盗们处于一个 $N$ 行 $M$ 列的矩形海域。

接下来有会有 $B$ 个炸弹，每个炸弹轰炸的范围是一个矩形。

海盗们有 $S$ 艘船，船要么是一行若干列的，要么是若干行一列的。你需要对每艘船输出：

`MISS` 船没有被炸弹覆盖到；

`HIT` 船被炸弹覆盖到，但没有完全覆盖；

`SUNK` 船被炸弹完全覆盖；

inputFormat:
第一行两个正整数 $N,M(1\leq N,M\leq 10^5)$。

接下来一行一个数 $B(1\leq B\leq 2\times 10^5)$。

接下来 $B$ 行每行四个正整数 $x1,y1,x2,y2(1\leq x1\leq x2\leq N,1\leq y1\leq y2\leq M)$，表示炸弹覆盖范围。

接下来一行一个数 $S(1\leq S\leq 2\times 10^5)$。

接下来 $S$ 行每行四个正整数 $opt,c,l,r$，若 $opt=1$ 则表示第 $i$ 艘船是由第 $c$ 行的第 $l$ 到 $r$ 列组成，否则若 $opt=2$ 则表示第 $c$ 列的第 $l$ 到 $r$ 行。

**船与船之间或炸弹与炸弹之间可能相交。**

outputFormat: $S$ 行，对每艘船输出答案。


title: [AGM 2023 资格赛] YsaeSort

description:
给定一个长度为 $N$ 的序列 $A$，接下来进行 $Q$ 次操作：

* $1\ l\ r(1\leq l\leq r\leq N)$ 表示对 $[l,r]$ 这个区间排序。

* $2\ l\ r(1\leq l\leq r\leq N)$ 查询：如果对这个区间进行冒泡排序，那么交换的相邻两个数的乘积的最大值。

保证 $1$ 操作排序的区间两两不交或包含。

inputFormat:
输入的第一行将包含一个整数 $N(1≤N≤5\times 10^4)$，表示数组的元素个数。

第二行输入将包含 $N$ 个整数 $(0≤A[i]≤10^9,1≤i≤N)$，即数组的元素。

第三行输入将包含一个整数 $Q(1≤Q≤5\times10^4)$，表示操作次数。

下面的每 $Q$ 行都包含一个题目中描述的询问。

outputFormat: $Q$ 行，对每一次询问输出答案。


title: [蓝桥杯 2023 省 A] 翻转硬币

description:
给定 $n$ 个按顺序摆好的硬币，一开始只有第 $1$ 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 $i$ 并将所有满足 $j \bmod i=0$ 的位置 $j$ 的硬币翻转。

求最少需要多少次操作可以让所有硬币都朝上。

inputFormat: 输入一行包含一个整数 $n$。

outputFormat: 输出一行包含一个整数表示最少需要的操作次数。

hint:
#### 【评测用例规模与约定】

对于 $30 \%$ 的评测用例，$n \leq 5 \times 10^6$；

对于 $70 \%$ 的评测用例，$n \leq 10^9$；

对于所有评测用例，$1 \leq n \leq 10^{18}$。


title: [蓝桥杯 2023 省 B] 冶炼金属

description:
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 $V$，$V$ 是一个正整数，这意味着消耗 $V$ 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 $V$ 时，无法继续冶炼。

现在给出了 $N$ 条冶炼记录，每条记录中包含两个整数 $A$ 和 $B$，这表示本次投入了 $A$ 个普通金属 O，最终冶炼出了 $B$ 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 $N$ 条冶炼记录，请你推测出转换率 $V$ 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

inputFormat:
第一行一个整数 $N$，表示冶炼记录的数目。

接下来输入 $N$ 行，每行两个整数 $A,B$，含义如题目所述。

outputFormat: 输出两个整数，分别表示 $V$ 可能的最小值和最大值，中间用空格分开。

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

当 $V=20$ 时，有：$\left\lfloor\frac{75}{20}\right\rfloor=3,\left\lfloor\frac{53}{20}\right\rfloor=2,\left\lfloor\frac{59}{20}\right\rfloor=2$，可以看到符合所有冶炼记录。

当 $V=25$ 时，有：$\left\lfloor\frac{75}{25}\right\rfloor=3,\left\lfloor\frac{53}{25}\right\rfloor=2,\left\lfloor\frac{59}{25}\right\rfloor=2$，可以看到符合所有冶炼记录。

且再也找不到比 $20$ 更小或者比 $25$ 更大的符合条件的 $V$ 值了。

**【评测用例规模与约定】**

对于 $30 \%$ 的评测用例，$1 \leq N \leq 10^{2}$。

对于 $60 \%$ 的评测用例，$1 \leq N \leq 10^{3}$。

对于 $100 \%$ 的评测用例，$1 \leq N \leq 10^{4}$，$1 \leq B \leq A \leq 10^{9}$。

蓝桥杯 2023 省赛 B 组 C 题。


title: [蓝桥杯 2023 省 B] 飞机降落

description:
$N$ 架飞机准备降落到某个只有一条跑道的机场。其中第 $i$ 架飞机在 $T_{i}$ 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 $D_{i}$ 个单位时间，即它最早可以于 $T_{i}$ 时刻开始降落，最晩可以于 $T_{i}+D_{i}$ 时刻开始降落。降落过程需要 $L_{i}$ 个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断 $N$ 架飞机是否可以全部安全降落。

inputFormat:
输入包含多组数据。

第一行包含一个整数 $T$，代表测试数据的组数。

对于每组数据，第一行包含一个整数 $N$。

以下 $N$ 行，每行包含三个整数 $T_{i},D_{i},L_{i}$。

outputFormat: 对于每组数据，输出 `YES` 或者 `NO`，代表是否可以全部安全降落。

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

对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

**【评测用例规模与约定】**

对于 $30 \%$ 的数据，$N \leq 2$。

对于 $100 \%$ 的数据，$1 \leq T \leq 10$，$1 \leq N \leq 10$，$0 \leq T_{i},D_{i},L_{i} \leq 10^{5}$。

蓝桥杯 2023 省赛 B 组 D 题。


title: [蓝桥杯 2023 省 B] 接龙数列

description:
对于一个长度为 $K$ 的整数数列：$A_{1},A_{2},\ldots,A_{K}$，我们称之为接龙数列当且仅当 $A_{i}$ 的首位数字恰好等于 $A_{i-1}$ 的末位数字（$2 \leq i \leq K$）。

例如 $12,23,35,56,61,11$ 是接龙数列；$12,23,34,56$ 不是接龙数列，因为 $56$ 的首位数字不等于 $34$ 的末位数字。所有长度为 $1$ 的整数数列都是接龙数列。

现在给定一个长度为 $N$ 的数列 $A_{1},A_{2},\ldots,A_{N}$，请你计算最少从中删除多少 个数，可以使剩下的序列是接龙序列？

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

第二行包含 $N$ 个整数 $A_{1},A_{2},\ldots,A_{N}$。

outputFormat: 一个整数代表答案。

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

删除 $22$，剩余 $11,121,12,2023$ 是接龙数列。

**【评测用例规模与约定】**

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

对于 $50 \%$ 的数据，$1 \leq N \leq 10^4$。

对于 $100 \%$ 的数据，$1 \leq N \leq 10^{5}$，$1 \leq A_{i} \leq 10^{9}$。所有 $A_{i}$ 保证不包含前导 0。

蓝桥杯 2023 省赛 B 组 E 题。


title: [PA 2022] Drybling Bajtessiego

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 3 [Drybling Bajtessiego](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/baj/)**

Bytessi 因是世界足坛最好的锋线（和球员）而广为人知。为了即将到来的世界杯，他编制了一份 $n$ 种运球方式的清单，其中每次运球可以用一串字母 `L` 和 `P` 来描述，表示他用左脚和右脚触球的顺序。

如果一个球员用左脚和右脚触球次数相等，我们就称这种运球方式是**平衡的**。此外，如果对于给定的这种运球方式，如果任意一个初始部分（前缀），满足左脚触球次数不少于右脚触球次数，就称这种运球方式是**左利脚的**。由于 Bytessi 是左利脚，他认为如果一种运球方式即平衡又左利脚，那么这种运球方式是**极佳的**。

世界杯是一个特殊的比赛，世界上最好的球员都会来参赛。出于这个原因，Bytessi 需要准备更多的运球方式。他决定使用一种简单的方式把运球方式增加到 $n^2$ 种——对于初始列表中每一对运球方式（可以相同），新的运球方式用这两种运球方式直接相连来描述。换句话说，他会先使用第一种运球方式运球，然后接着用第二种运球方式运球。

在激烈的比赛中，很容易忘记一些本应进行的触球，所以 Bytessi 最后的运球方式将是他最初想的运球方式的一个非空的子序列。换句话说，最后的运球方式将通过删除他想进行的运球方式中的一些（也许没有，但不是全部）字母来得到。其余字母的顺序必须保持不变。

最终采用的运球方式将是极佳的，如果这样的话 Bytessi 会非常高兴。他现在想知道，对于新清单中的每一种运球方式，他可以意外地进行多少种可能的极佳运球方式。由于这个数字可能非常大，Bytessi 只需要知道将这个数字除以 $10^9+7$ 的余数。请帮 Bytessi 解决这个问题。

注意：Bytessi 感兴趣的是其原始运球方式的子序列可以得到多少种不同的极佳运球，而不是从原始运球的描述中划掉字母而得到极佳运球的方法的数量。

inputFormat:
第一行一个整数 $n$，表示 Bytessi 准备的运球方式种数。

接下来 $n$ 行描述 Bytessi 的运球方式。第 $i$ 行包含一个由 `L` 和 `P` 组成的非空串，描述第 $i$ 种运球方式。

outputFormat: 输出 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个整数表示如果把第 $i$ 种和第 $j$ 种运球方式相连，新的运球方式中有多少子序列是极佳的，结果对 $10^9+7$ 取模。

hint:
对于 $100\%$ 的数据，满足：

$1\le n\le 600$，

每种运球方式的长度不超过 $600$。


title: [PA 2022] Fotografia

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 3 [Fotografia](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/fot/)**

字节科技学校（*Bajtockiej Szkoły Technicznej*, BST）的毕业生们聚集在学校前面的广场上拍摄纪念照。他们排成一排，其位置从左到右编号为 $1$ 至 $n$，其中 $n$ 是今年毕业生的人数。

摄影师决定重新安排这些人的位置，让他们按身高升序排列。最矮的人在最左边，最高的人在最右边。幸运的是，今年的毕业生中没有任意两人身高相同。

为了避免混乱，安排位置将按一定方式进行。在一次操作中，摄影师将喊出一串位置编号。在这些位置上的人将按所喊到的顺序出列并走到广场中间。然后，摄影师将重复同样的数字列表。广场中间的人将他们出列顺序的**逆序**，依次回到摄影师所喊出的位置。

我们希望用尽可能少的操作将所有毕业生按身高的升序排列。你的工作是规划重新安排的方案，并告诉摄影师在第几次操作让哪些毕业生出列。

inputFormat:
第一行一个整数 $n$，表示毕业生人数。

接下来 $n$ 行是一个整数序列 $h_1,h_2,\ldots,h_n$，每行一个整数，表示站成一排的人的身高。所有身高两两不同。

outputFormat:
输出第一行包含一个整数 $r$，表示把所有人按身高升序排列所用的最少操作次数。

接下来 $2r$ 行包含对这些操作的描述。描述第一行包含一个整数 $p_i\ ()$，表示这一轮出列的人数，第二行 $p_i$ 个整数，表示按输出顺序喊出人的位置编号。在一次操作中喊出的人不能重复。

如果有多种操作次数最少的方案，输出任意一种即可。

hint:
对于 $100\%$ 的数据，满足：

$1\le n\le 3 \times 10 ^ 3, 1\le h_i\le 3 \times 10 ^ 3, 1\le p_i\le n$。


title: [PA 2022] Miny

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Miny](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/min/)**

给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗地雷不超过其爆炸半径的地雷都会爆炸。我们定义两个点之间的距离是这两个点之间简单路径上边的长度和。对于每颗地雷，如果手动引爆它，确定有多少地雷会爆炸。注意对于每颗地雷，我们认为手动引爆它与手动引爆其他地雷互相独立。

inputFormat:
第一行包含一个整数 $n$，表示树的节点数（也是地雷个数）。树节点编号是从 $1$ 到 $n$ 的整数。

第二行 $n$ 个整数 $r_1,r_2,\ldots,r_n$，第 $i$ 个整数为位于节点 $i$ 的地雷的爆炸半径。

接下来 $n-1$ 行，每行三个整数 $a_i,b_i,c_i$，表示一条长 $c_i$ 的边连接节点 $a_i$ 和 $b_i$。

保证输入可以正确表示一棵树。

outputFormat:
对于 $100\%$ 的数据，满足：

输出一行 $n$ 个整数，第 $i$ 个整数表示如果我们手动引爆在节点 $i$ 上的地雷，有多少地雷会爆炸。


title: [PA 2022] Płótno

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Płótno](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/plo/)**

由于圣诞节，Bytie 从父母那里得到了一块大画布，画布被分成 $2n$ 个方格，排列成两行 $n$ 列的矩形。为了方便在上面画画，这块画布被包在在一个很低很宽的圆柱体的侧面上，这样，画布的第一列就与最后一列相邻。如果画布上的两个方格有一条公共边，则认为它们是相邻的。即它们要么在同一列，要么在同一行的相邻列。

数学上，我们可以用一个有序数对 $(y,x)$ 表示画布上的每个方格，其中 $1\le y\le 2,1\le x\le n$。两个方格 $(y_1,x_1)$ 和 $(y_2,x_2)$ 相邻，如果满足：

- 它们在同一行，即 $y_1=y_2$，并且列相邻，即 $x_1+1\equiv x_2 \pmod n$ 或 $x_2+1\equiv x_1\pmod n$，或者
- 它们在同一列，即 $x_1=x_2$。

Bytie 一到画布前，就把 $2n$ 个方格的每一个都画成了**不同**的颜色。为简单起见，我们用 $1$ 到 $2n$ 的整数来表示颜色。

每个看到这个孩子的劳动成果的人都对这么小的孩子能够创造出如此宏伟的作品而感到非常惊讶。这甚至吸引了著名的艺术评论家 Bytona Bitego。他决定亲眼看看是什么让人们如此着迷，他将用自己特别准备的方法评估他的画，其方法如下：

我们选择一个特定的颜色区间 $[l, r]$，然后只考虑颜色在这个区间内的方格。我们称这个颜色区间的好奇值等于这些方格形成的连通区域的数量。如果存在一连串颜色在 $[l, r]$ 中的相邻方格使得两个颜色在 $[l,r]$ 的方格连通，那么这两个方格就在一个区域内。

Bytona Bitego 想知道对于每个 $v\in \{1,2,\ldots,k\}$，有多少区间的好奇值为 $v$。你的任务就是回答他的问题。

inputFormat:
第一行包含两个整数 $n,k$，分别表示画布的宽度和 Bajtona Bitego 想知道的最大好奇值。

第二行包含 $n$ 个整数，表示画布第一行方格的颜色。从左到右按列编号递增顺序给出。

类似地，第三行包含 $n$ 个整数，表示画布第二行方格的颜色，顺序与第一行相同。

第二行和第三行的数字合起来形成了一个 $1$ 到 $2n$ 的整数排列。

outputFormat: 输出一行 $k$ 个整数，第 $v$ 个整数表示有多少个区间的好奇值为 $v$。


title: [PA 2022] Łamigłówka

description:
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Łamigłówka](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/lam/)**

Byteasar 在玩拼图。它是一个由单元格组成的 $n\times m$ 大小的矩形。每个单元格可能是空的，也可能包含一个黑色或白色的方块。

在每次操作中，这个玩具可以向平行于矩形边的四个方向之一倾斜。然后所有的方块会朝那个方向滑动到最远可以所处的位置，而不超出矩形范围或重叠。

Byteasar 倾斜了多次，请给出倾斜最后一次后整个拼图的状态。

inputFormat:
第一行两个整数 $n,m$，表示这个矩形的大小。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，表示初始状态。字符串中仅包含三种字符：`.` 表示这个单元格是空的，`B` 表示这个单元格中有一个白色方块，`C` 表示这个单元格中有一个黑色方块。

接下来一行一个整数 $k$，表示 Byteasar 倾斜的次数。

最后一行包含一个长为 $k$ 的字符串，表示 Byteasar 每次的倾斜方向。字符串中仅包含 `G`，`D`，`L`，`P` 四种字符，分别表示向上，向下，向左和向右倾斜。

outputFormat: 输出这个玩具的最终状态，输出格式与输入的初始状态格式相同，输出 $n$ 行，每行一个长度为 $m$ 的字符串，字符串中仅包含 `.`，`B`，`C` 三种字符。

hint:
对于 $100\%$ 的数据，满足：

$1\le n,m\le 500, 1\le k\le 5 \times 10 ^ 5$。