在一个链状的供电系统上，包含 $$$10^9 + 1$$$ 个节点，节点分别编号为 $$$0$$$ 到 $$$10^9$$$。
现在部分节点处于「工作异常」状态。工程师经过排查，发现 $$$[X, Y]$$$ 区间（$$$X \leq Y$$$）内的所有节点都有电，而这之外的其他节点都没有电。
一户居民位于节点 $$$Z$$$，他想知道他家目前是否有电。请你编写程序，根据给定的 $$$X, Y, Z$$$，判断该居民家是否有电。
仅一行，包含三个整数 $$$X, Y, Z$$$（$$$0 \le X \le Y \le 10^9$$$，$$$0 \le Z \le 10^9$$$），含义如题面所述。
如果该居民家有电，输出 $$$\mathtt{YES}$$$；否则输出 $$$\mathtt{NO}$$$。
1 5 4
YES
1 5 5
YES
12 34 5
NO
0 1 0
YES
样例 1 中，居民在 $$$4$$$，从 $$$1$$$ 到 $$$5$$$ 的节点都有电，包括 $$$4$$$，输出 $$$\mathtt{YES}$$$。
在软件开发中，版本号通常由「主版本号」（Major）、「次版本号」（Minor）和「修订号」（Patch）组成，通常记为 $$$X.Y.Z$$$。
比较两个版本号的大小时，遵循以下规则：
- 首先比较「主版本号」，「主版本号」较大的版本号更大；
- 如果「主版本号」相同，则比较「次版本号」，「次版本号」较大的版本号更大；
- 如果「次版本号」也相同，则比较「修订号」，「修订号」较大的版本号更大。
- 如果「修订号」也相同，则我们认为两个版本号一样大。
现在给定两个版本号，请你比较它们的大小。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^4$$$），表示测试用例的数量。对于每组测试用例：
- 第一行包含三个整数 $$$X_1, Y_1, Z_1$$$ ($$$0 \le X_1, Y_1, Z_1 \le 2 \times 10^9$$$)，表示第一个版本号的主、次、修订号。
- 第二行包含三个整数 $$$X_2, Y_2, Z_2$$$ ($$$0 \le X_2, Y_2, Z_2 \le 2 \times 10^9$$$)，表示第二个版本号的主、次、修订号。
对于每组测试用例：
- 如果第一个版本号更大，输出 $$$\mathtt{ \gt }$$$（"大于"符号，ascii 码 62）；
- 如果第二个版本号更大，输出 $$$\mathtt{ \lt }$$$（"小于"符号，ascii 码 60）；
- 如果两个版本号一样大，输出 $$$\mathtt{=}$$$（"等于"符号，ascii 码 61）。
41 0 00 9 91 2 31 2 32 1 02 1 110 20 3010 20 29
>=<>
小 i 来到了一个神秘的圆圈王国。圆圈王国里的人使用一种奇妙的三进制数字，其基本数位使用的是 $$$\mathtt{0oO}$$$ 这三个字符。具体的：
- 使用 $$$\mathtt{0}$$$（数字 $$$0$$$）代表数字 $$$0$$$；
- 使用 $$$\mathtt{o}$$$（小写字母 $$$\mathrm{o}$$$）代表数字 $$$1$$$；
- 使用 $$$\mathtt{O}$$$（大写字母 $$$\mathrm{O}$$$）代表数字 $$$2$$$。
他们的书写顺序与常规数字相反：位权低的位写在左边，位权高的位写在右边。同时，每两个相邻数位之间使用符号 $$$\mathtt{.}$$$（"点"符号，ascii 码 46）进行分隔。
例如，十进制数 $$$11$$$ 转换为通常的三进制是 $$$(102)_3$$$（即 $$$11 = 1 \times 3^2 + 0 \times 3^1 + 2 \times 3^0$$$），但在圆圈王国中，位权低者在左，所以顺序变为 $$$2 0 1$$$，替换为对应字符后就是 $$$\mathtt{O.0.o}$$$。
小 i 希望你帮他编写一个程序，将给定的十进制非负整数转换为这种奇妙的三进制表示形式。
仅一行，包含一个非负整数 $$$N$$$（$$$0 \leq N \leq 10^9$$$），表示待转换的十进制数字。
输出一个字符串，表示 $$$N$$$ 在圆圈王国中的奇妙三进制表示。
5
O.o
11
O.0.o
0
0
114514
o.O.0.O.0.0.o.o.O.O.o
对于非负整数 $$$x$$$，我们定义 or-shift 变换 $$$f(x)$$$ 为 $$$x$$$ 和 $$$2 x$$$ 的按位或$$$^{\text{∗}}$$$，即： $$$$$$ f(x) = x \mathbin{|} (2 x) $$$$$$
给定一个非负整数 $$$y$$$，请你判断是否存在一个非负整数 $$$x$$$，使得 $$$f(x) = y$$$。
如果存在，输出任意一个满足要求的 $$$x$$$；否则，输出 $$$-1$$$。
$$$^{\text{∗}}$$$按位或（bitwise OR）是一种二进制按位运算，记作 $$$a \mathbin{|} b$$$。它对两个无符号整数对应二进制位分别进行逻辑或运算：若某一位上至少有一个数位为 $$$1$$$，则结果的该位为 $$$1$$$；否则为 $$$0$$$。例如 $$$ 5 \mathbin{|} 3 =(0101)_2 \mathbin{|} (0011)_2 =(0111)_2 =7 $$$。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^4$$$），表示测试用例的数量。对于每组测试用例：
- 仅一行，包含一个非负整数 $$$y$$$（$$$0 \leq y \lt 2^{60}$$$）。
对于每组测试用例：
- 如果存在满足要求的 $$$x$$$，输出一行，包含一个非负整数 $$$x$$$；
- 否则，输出 $$$-1$$$。
如果存在多个满足要求的 $$$x$$$，你可以输出其中任意一个。
8015191819191574711451442865612801152921504606846975
058108117297-12000000000576460752303423487
猪猪学院的魔法师小猪正在研究一种有趣的陷阱魔法。
这个陷阱魔法会困住 $$$n$$$ 只小猪，并让它们排成一排。这 $$$n$$$ 只小猪分别编号为 $$$1$$$ 到 $$$n$$$。
初始时，编号为 $$$i$$$ 的小猪的「不能动数」为 $$$a_i$$$，并且 $$$a_1,a_2,\ldots,a_n$$$ 恰好构成一个长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$。
初始时，魔法师小猪需要向陷阱中注入魔力，注入的魔力值是一个非负整数 $$$x$$$：
随后，魔法师小猪可以进行任意多次以下操作：
- 选择一个区间 $$$[l,r]$$$（$$$1\le l\le r\le n$$$），需要满足当前区间内的小猪的「不能动数」的最大值和最小值的差不超过 $$$x$$$，即： $$$$$$ \max \limits_{l \leq i \leq r} a_i - \min \limits_{l \leq i \leq r} a_i \leq x $$$$$$
- 随后，将这个区间内的小猪的「不能动数」任意重排。也就是说，可以任意改变这个区间内小猪的「不能动数」的相对顺序。
如果从左到右看，小猪们的「不能动数」严格递增，那么陷阱就会被破解。
为了深入研究这个陷阱魔法的效果，小猪们想知道：对于给定的场面，至少需要注入多少点魔力，才能破解陷阱？
$$$^{\text{∗}}$$$如果一个长度为 $$$k$$$ 的整数序列 $$$[c_1, c_2, \ldots, c_k]$$$ 满足：$$$1$$$ 到 $$$k$$$ 中的每个整数（包括 $$$1$$$ 和 $$$k$$$）都恰好在序列中出现一次，那么我们称序列 $$$c$$$ 是一个长度为 $$$k$$$ 的排列。例如 $$$[1, 2, 3]$$$、$$$[1, 5, 3, 2, 4]$$$ 都是排列，而 $$$[1, 1, 4]$$$ 不是。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^5$$$），表示测试用例的数量。对于每组测试用例：
- 第一行一个整数 $$$n$$$（$$$1\le n\le 10^5$$$），表示小猪的数量。
- 第二行 $$$n$$$ 个整数 $$$a_1,a_2,\ldots,a_n$$$（$$$1 \leq a_i \leq n$$$），表示初始时刻每只小猪的「不能动数」。
- 数据保证 $$$[a_1, a_2, \ldots, a_n]$$$ 构成一个排列。
保证所有测试用例的 $$$n$$$ 的总和不超过 $$$10^5$$$。
对于每组测试用例：
- 输出一行一个整数，表示破解陷阱所需的最小魔力值 $$$x$$$。
251 2 3 4 562 5 1 6 3 4
04
对于第一组测试用例，初始队列为 $$$[1,2,3,4,5]$$$。因为小猪们的「不能动数」已经严格递增，因此不需要操作。注入 $$$x = 0$$$ 的魔力即可。
对于第二组测试用例，初始队列为 $$$[2,5,1,6,3,4]$$$，注入 $$$x = 4$$$ 的魔力，并依次进行操作：
- $$$[\underline{\color{blue}{2,5,1}},6,3,4] \to [\underline{\color{blue}{1,2,5}},6,3,4]$$$；
- $$$[1,2,\underline{\color{blue}{5,6,3,4}}] \to [1,2,\underline{\color{blue}{3,4,5,6}}]$$$；
可以证明，当 $$$x \lt 4$$$ 时无法破解陷阱，所以第二组测试用例的答案为 $$$4$$$。
某实验室研制出了一种特殊染料，只有三种基础颜色：
- $$$\mathtt{R}$$$（红色）
- $$$\mathtt{G}$$$（绿色）
- $$$\mathtt{B}$$$（蓝色）
这些染料具有特殊性质：
- 如果一个位置为空白（记为 $$$\mathtt{N}$$$），刷上颜色 $$$c$$$，则变为颜色 $$$c$$$；
- 如果一个位置已经是颜色 $$$c$$$，再刷一次颜色 $$$c$$$，则颜色不会发生变化；
- 如果一个位置已经是另一种颜色，则会与新颜色发生反应，变成第三种颜色。
具体反应规则如下表：
| 原颜色 | 新颜色 | 结果 |
| $$$\mathtt{R}$$$ | $$$\mathtt{G}$$$ | $$$\mathtt{B}$$$ |
| $$$\mathtt{G}$$$ | $$$\mathtt{R}$$$ | $$$\mathtt{B}$$$ |
| $$$\mathtt{G}$$$ | $$$\mathtt{B}$$$ | $$$\mathtt{R}$$$ |
| $$$\mathtt{B}$$$ | $$$\mathtt{G}$$$ | $$$\mathtt{R}$$$ |
| $$$\mathtt{B}$$$ | $$$\mathtt{R}$$$ | $$$\mathtt{G}$$$ |
| $$$\mathtt{R}$$$ | $$$\mathtt{B}$$$ | $$$\mathtt{G}$$$ |
给定一个长度为 $$$n$$$ 的目标序列，由 $$$\mathtt{R}$$$、$$$\mathtt{G}$$$、$$$\mathtt{B}$$$ 三种颜色以及空白（$$$\mathtt{N}$$$）组成。
初始时，你有一个长度同样为 $$$n$$$ 的初始序列，所有位置均为空白（$$$\mathtt{N}$$$）。
每次操作，你可以选定一个连续区间 $$$[l, r]$$$ 和一种颜色 $$$c \in \{\mathtt{R}, \mathtt{G}, \mathtt{B}\}$$$，随后将区间内的所有位置同时刷上颜色 $$$c$$$。
请你计算将初始序列变成目标序列所需的最少操作次数。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 1000$$$），表示测试用例的数量。对于每组测试用例：
- 第一行一个整数 $$$n$$$（$$$1 \le n \le 2 \times 10^5$$$），表示序列长度；
- 第二行一个长度为 $$$n$$$ 的字符串 $$$s$$$，表示目标序列。字符串仅包含字符 $$$\mathtt{R}$$$、$$$\mathtt{G}$$$、$$$\mathtt{B}$$$、$$$\mathtt{N}$$$。
保证所有测试用例的 $$$n$$$ 的总和不超过 $$$2 \times 10^5$$$。
对于每组测试用例：输出一行一个整数，表示最少操作次数。
35RBRNR6RRGGBB1N
320
对于第一组测试用例，依次进行三次操作即可：
- $$$\mathtt{\underline{NNN}NN} \xrightarrow{\mathtt{{\color{red}{R}}}} \mathtt{\underline{{\color{red}{R}}{\color{red}{R}}{\color{red}{R}}}NN}$$$；
- $$$\mathtt{{\color{red}{R}}\underline{{\color{red}{R}}}{\color{red}{R}}NN} \xrightarrow{\mathtt{{\color{green}{G}}}} \mathtt{{\color{red}{R}}\underline{{\color{blue}{B}}}{\color{red}{R}}NN}$$$；
- $$$\mathtt{{\color{red}{R}}{\color{blue}{B}}{\color{red}{R}}N\underline{N}} \xrightarrow{\mathtt{{\color{red}{R}}}} \mathtt{{\color{red}{R}}{\color{blue}{B}}{\color{red}{R}}N\underline{{\color{red}{R}}}}$$$；
可以证明，无法在 $$$2$$$ 次操作内完成，故最少操作次数为 $$$3$$$。
给定两个正整数 $$$n$$$ 和 $$$k$$$。你的目标是找到一个长度为 $$$n$$$ 的正整数序列 $$$[a_1, a_2, \ldots, a_n]$$$，满足：
- $$$a$$$ 中的元素严格递增，即对任意 $$$i,j\in \{ 1,\dots,n \}$$$，若 $$$i \lt j$$$，则有 $$$a_i \lt a_j$$$ 成立；
- $$$a$$$ 中所有元素都介于 $$$1$$$ 到 $$$n^2 \cdot k$$$ 之间，即对任意 $$$i \in \{ 1,\dots,n \}$$$，有 $$$ 1 \leq a_i \leq n^2 \cdot k $$$ 成立；
- $$$a$$$ 中所有元素的倒数之和等于 $$$k$$$ 的倒数，即 $$$\sum\limits_{1 \leq i \leq n} \frac{1}{a_i} = \frac{1}{k} $$$；
请你判断是否存在满足要求的正整数序列。如果存在，输出任意一个满足要求的正整数序列。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^6$$$），表示测试用例的数量。对于每组测试用例：
- 仅一行，包含两个正整数 $$$n$$$ 和 $$$k$$$（$$$ 1\leq n, k\leq 10^6 $$$）。
保证所有测试用例的 $$$n$$$ 的总和不超过 $$$10^6$$$，$$$k$$$ 的总和也不超过 $$$10^6$$$。
对于每组测试用例：
- 如果不存在满足要求的序列，输出 $$$\mathtt{NO}$$$。
- 否则，首先输出一行，包含一个 $$$\mathtt{YES}$$$；接下来输出一行，包含 $$$ n $$$ 个正整数 $$$a_1, a_2,\ldots,a_n$$$，用空格分隔，表示你的答案。
如果存在多个满足要求的答案，你可以输出其中任意一个。
71 12 13 42 55 16 42 114514
YES1NOYES6 20 30NOYES3 4 5 6 20YES5 70 80 120 126 144YES171771 343542
有一个 $$$n$$$ 行 $$$m$$$ 列的棋盘，在开始时，棋盘上每一个格子都是空的。
你有足够多的棋子可以放置在棋盘上（当然，每一个格子最多只能放置一个棋子），且需要满足：
- 第 $$$i$$$ 行（$$$1 \leq i \leq n$$$）的棋子加起来恰好有 $$$a_i$$$ 个；
- 第 $$$i$$$ 列（$$$1 \leq i \leq m$$$）的棋子加起来恰好有 $$$b_i$$$ 个；
请你判断是否存在满足要求的放置方案。如果存在，输出任意一种满足要求的方案。
第一行两个正整数 $$$n$$$ 和 $$$m$$$（$$$1 \le n, m \le 10^6$$$ 且 $$$n \times m \le 10^6$$$），表示棋盘的尺寸。
第二行 $$$n$$$ 个非负整数 $$$a_1, a_2, \ldots, a_n$$$（$$$0 \leq a_i \leq m$$$）；
第三行 $$$m$$$ 个非负整数 $$$b_1, b_2, \ldots, b_m$$$（$$$0 \leq b_i \leq n$$$）；
如果不存在满足要求的方案，仅输出一行，包含一个 $$$\mathtt{NO}$$$。
否则，首先在第一行输出 $$$\mathtt{YES}$$$；接下来的 $$$n$$$ 行，每行包含 $$$m$$$ 个字符，第 $$$i$$$ 行的第 $$$j$$$ 个字符（$$$1 \leq i \leq n$$$ 且 $$$1 \leq j \leq m$$$）表示放置完成的棋盘中 $$$i$$$ 行 $$$j$$$ 列的格子的状态。具体的：
- 用 $$$\mathtt{.}$$$（"点"符号，ascii 码 46）表示当前格子是空的；
- 用 $$$\mathtt{\#}$$$（"井号"符号，ascii 码 35）表示当前格子放置了一个棋子；
若存在多种可行的放置方案，任意输出一种即可。
4 31 3 2 13 1 3
YES ..# ### #.# #..
猪猪学院的魔法师小猪们正在制作一把强大的元素法杖。
为了制作这把法杖，他们准备了许多魔法晶体。每块魔法晶体都有一个元素强度，且元素强度均为正整数。
这些魔法晶体共有 $$$k$$$ 种不同的元素强度。其中，元素强度为 $$$v_i$$$ 的魔法晶体有 $$$c_i$$$ 块。
魔法师小猪们需要不断融合魔法晶体，直到最后只剩下一块魔法晶体。
每次融合时，可以选择两块当前存在的魔法晶体。若它们的元素强度分别为 $$$x,y$$$，那么融合后会得到一块元素强度为 $$$x+y$$$ 的新的魔法晶体，同时消耗数量为 $$$f(x, y)$$$ 的魔力值。
这里 $$$f(x, y)$$$ 表示最大的满足 $$$3^e$$$ 能够整除$$$^{\text{∗}}$$$ $$$\dbinom{x+y}{x}$$$$$$^{\text{†}}$$$ 的非负整数 $$$e$$$。即：
$$$$$$ f(x, y) = \max\left\{ e\in\mathbb Z_{\ge 0} : 3^e\mid \dbinom{x+y}{x} \right\} $$$$$$
最终，所有魔法晶体都会被融合成唯一一块魔法晶体，并镶嵌到元素法杖上。
容易发现，最后得到的魔法晶体的元素强度总是所有初始魔法晶体的元素强度之和。因此，无论魔法师小猪们如何安排融合顺序，最终这块魔法晶体的元素强度都是确定的。
小猪们想知道，如果合理安排融合顺序，将所有魔法晶体融合成一块，总计至少需要消耗多少魔力值。
给定所有初始魔法晶体的信息，请你求出这个最小总魔力值。
$$$^{\text{∗}}$$$对于整数 $$$a$$$ 和 $$$b$$$，如果 $$$a$$$ 是 $$$b$$$ 的倍数，即存在一个整数 $$$k$$$，使得 $$$a = k b$$$，则我们称 $$$b$$$ 能整除 $$$a$$$，记作 $$$b \mid a$$$。
$$$^{\text{†}}$$$对于整数 $$$0\le b\le a$$$，$$$\dbinom{a}{b}$$$ 表示从 $$$a$$$ 个不同元素中选出 $$$b$$$ 个元素的方案数。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 100$$$），表示测试用例的数量。对于每组测试用例：
- 第一行一个整数 $$$k$$$（$$$1\le k\le 10^5$$$），表示不同元素强度的种数。
- 接下来 $$$k$$$ 行，每行包含两个整数 $$$v_i,c_i$$$（$$$1\le v_i,c_i\le 10^{18}$$$），表示元素强度为 $$$v_i$$$ 的魔法晶体有 $$$c_i$$$ 块。
- 数据保证 $$$\sum_{i=1}^{k} v_i c_i \le 10^{18}$$$，并且 $$$v_1,v_2,\ldots,v_k$$$ 两两不同。
保证所有测试用例的 $$$k$$$ 的总和不超过 $$$10^5$$$。
对于每组测试用例：输出一行一个整数，表示所需的最小总魔力值。
可以证明，在本题数据范围内，答案可以用 64 位有符号整数存储。
421 22 122 17 1110 111 10
1204
本题陷阱魔法的基本规则与题目陷阱魔法I中完全相同，不再重复说明。
猪猪学院的魔法师小猪们继续研究这种有趣的陷阱魔法。
现在，小猪们发现了这个陷阱魔法的一个漏洞：强大的大魔法师猪可以在注入魔力之前，先从陷阱中强行拉出若干只小猪。被拉出的小猪会离开队列，剩下的小猪保持原来的相对顺序形成新的队列。
作为限制，被拉出的小猪的「不能动数」之和不能超过 $$$B$$$。
如果没有剩下小猪，或者只剩下一只小猪，也认为陷阱已经被破解。
现在，小猪们想要知道：在给定初始场面和移除限制 $$$B$$$ 的情况下，通过合适的策略，最少需要注入多少点魔力，才能破解陷阱？
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^5$$$），表示测试用例的数量。对于每组测试用例：
- 第一行两个整数 $$$n$$$ 和 $$$B$$$（$$$1\le n\le 10^5$$$ 且 $$$0 \leq B \leq \frac{n (n+1)}{2}$$$），分别表示小猪的数量和可以移除的「不能动数」总和上限。
- 第二行 $$$n$$$ 个整数 $$$a_1,a_2,\ldots,a_n$$$（$$$1 \leq a_i \leq n$$$），表示初始时刻每只小猪的「不能动数」。
- 数据保证 $$$[a_1, a_2, \ldots, a_n]$$$ 构成一个排列。
保证所有测试用例的 $$$n$$$ 的总和不超过 $$$10^5$$$。
对于每组测试用例：输出一行一个整数，表示破解陷阱所需的最小魔力值 $$$x$$$。
35 01 2 3 4 56 22 5 1 6 3 45 55 1 2 3 4
030
对于第一组测试用例，初始队列为 $$$[1,2,3,4,5]$$$，因为「不能动数」已经严格递增，因此无需移除小猪，也无需注入魔力，答案为 $$$0$$$。
对于第二组测试用例，初始队列为 $$$[2,5,1,6,3,4]$$$，可以移除的小猪的「不能动数」上限为 $$$2$$$；
最优方案是将「不能动数」为 $$$1$$$ 的小猪移除，随后队列变为 $$$[2,5,6,3,4]$$$。注入 $$$x = 3$$$ 的魔力，并依次进行操作：
- $$$[2,5,\underline{\color{blue}{6,3,4}}] \to [2,5,\underline{\color{blue}{3,4,6}}]$$$；
- $$$[2,\underline{\color{blue}{5,3,4}},6] \to [2,\underline{\color{blue}{3,4,5}},6]$$$；
可以证明，不存在更优方案，因此答案为 $$$3$$$。