题目

Two Arrays

题目

给你两个长度为 $n$ 的数组 $a$ 和 $b$。你可以无限次地执行以下操作：

• 选一个整数 $i$，范围从 $1$ 到 $n$，然后交换 $a_i$​ 和 $b_i$。

设 $f(c)$ 是数组 $c$ 中不同数字的个数。求 $f(a)+f(b)$ 的最大值。同时输出执行完所有操作后的数组 $a$ 和 $b$。

输入

输入包含多组测试数据。第一行是测试组数 $t$($1\le t\le {10}^4$)。接下来是各组测试数据的描述。

每组测试数据第一行是一个整数 $n$ ($1\le n\le {10}^5$)，表示数组长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$​ ($1\le a_i\le 2n$)，表示数组 $a$ 的元素。

第三行包含 $n$ 个整数 $b_1,b_2,\dots ,b_n$​ ($1\le b_i\le 2n$)，表示数组 $b$ 的元素。

保证所有测试组的 $n$ 总和不超过 ${10}^5$。

输出

每组测试数据，第一行输出一个整数——$f(a)+f(b)$ 的最大值。

第二行输出 $n$ 个整数——执行操作后数组 $a$ 的元素。

第三行输出 $n$ 个整数——执行操作后数组 $b$ 的元素。

样例输入

3
5
1 2 4 4 4
1 3 3 5 2
7
2 2 4 4 5 5 5
1 3 3 2 1 6 6
7
12 3 3 4 5 6 4
1 2 13 8 10 13 7

样例输出

9
1 3 4 5 2 
1 2 3 4 4 
12
2 3 4 2 1 5 6 
1 2 3 4 5 6 5 
14
12 3 13 8 10 6 4 
1 2 3 4 5 13 7 

说明

第一组测试中，经过三次操作，分别选取 $i=2$、$i=4$ 和 $i=5$，最终得到 $a=[1,3,4,5,2]$ 和 $b=[1,2,3,4,4]$。此时 $f(a)+f(b)=5+4=9$。可以证明无法得到更大的答案。

第二组测试中，经过如下操作：$$f([2,3,4,2,1,5,6])+f([1,2,3,4,5,6,5])=6+6=12$$

---

Alone

题目

$\hspace{15pt}$小苯有一个 $n$ 行 $m$ 列，仅由整数 $0$ 和 $1$ 构成的 01 矩阵，其中 $0$ 表示白色格子，$1$ 表示黑色格子。
$\hspace{15pt}$他定义 01 矩阵中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格 $(i, j)$ 为“孤立点”，当且仅当：
$\hspace{23pt}\bullet\,$该格子是黑色的；
$\hspace{23pt}\bullet\,$在第 $i$ 行中，它是唯一的黑色格子；
$\hspace{23pt}\bullet\,$在第 $j$ 列中，它也是唯一的黑色格子。
$\hspace{15pt}$矩阵的孤立度定义为其中所有“孤立点”的个数。

$\hspace{15pt}$现在，小苯预先确定了 $k$ 个不同位置的格子必须是黑色。给定这 $k$ 个格子的位置 $(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$。
$\hspace{15pt}$小苯考虑所有满足以下条件的 $n \times m$ 的 01 矩阵，这些矩阵都包含所有预先确定的黑色格子，其余格子的颜色由小苯自由选择。在所有可能的矩阵中，他想知道这些矩阵的孤立度之和是多少。

$\hspace{15pt}$换句话说，对所有满足条件的矩阵，将每个矩阵的孤立度相加，求这个总和。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

输入

$\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 2 \times 10^4\right)$ 代表数据组数，每组测试数据描述如下：

$\hspace{15pt}$第一行输入三个整数 $n, m, k\left(1 \leqq n, m \leqq 10^9;\, 0 \leqq k \leqq \min(n \times m, 2 \times 10^5)\right)$，表示 01 矩阵的行数、列数和预先确定的黑色格子个数。
$\hspace{15pt}$此后 $k$ 行，第 $i$ 行输入两个整数 $x_i, y_i\left(1 \leqq x_i \leqq n;\, 1 \leqq y_i \leqq m\right)$，表示第 $i$i 个预先确定的黑色格子位置。保证这 $k$ 个格子两两不同。

$\hspace{15pt}$除此之外，保证单个测试文件的 $k$ 之和不超过 $3 \times 10^5$。

输出

      对于每一组测试数据，新起一行输出一个整数表示所有满足条件的矩阵的孤立度之和对 $998\,244\,353$ 取模的结果。

样例输入

2
2 2 0
2 2 1
1 1

样例输出

8
3

---

Not Equal

题目

$\hspace{15pt}$小苯有一个长度为 $n$n 的序列 $a_1, a_2, \dots, a_n$，序列中的每个元素都是正整数。

$\hspace{15pt}$小苯可以进行任意次操作（可以不操作），每次操作可以从以下两种形式中任选一种进行：
$\hspace{23pt}\bullet\,$选择序列中任意一个位置$i\left(1 \leqq i \leqq n\right)$，并将 $a_i$​ 变为 $a_i + 1$，该操作花费 $b_i$；
$\hspace{23pt}\bullet\,$选择序列中任意一个位置$i\left(1 \leqq i \leqq n\right)$，满足 $a_i > 1$，将 $a_i$ 变为 $a_i – 1$，该操作花费 $c_i$。

$\hspace{15pt}$小苯希望序列中相邻两个元素都不相同。你的任务就是求出，满足条件的最少花费。可以证明一定可以通过有限轮操作得到满足条件的序列。

输入

$\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1 \leqq T \leqq 10^4\right)$ 代表数据组数，每组测试数据描述如下：

$\hspace{15pt}$第一行输入一个整数 $n\left(1 \leqq n \leqq 2 \times 10^5\right)$，表示序列的长度。
$\hspace{15pt}$第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n\left(1 \leqq a_i \leqq 10^9\right)$，表示序列 $a$。
$\hspace{15pt}$第三行输入 $n$ 个正整数 $b_1, b_2, \dots, b_n\left(1 \leqq b_i \leqq 10^9\right)$，表示序列 $b$。
$\hspace{15pt}$第四行输入 $n$ 个正整数 $c_1, c_2, \dots, c_n\left(1 \leqq c_i \leqq 10^9\right)$，表示序列 $c$。

$\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$。

输出

$\hspace{15pt}$对于每一组测试数据，新起一行输出一个整数，表示满足条件的最小操作花费。

样例输入

2
4
1 3 3 4
1 2 1 2
1 2 3 2
3
10 1 10
1 1 1
1 1 1

样例输出

2
0

说明

      对于第一组测试数据，一种最优方案是将序列变为 $\{1,2,3,4\}$，花费为 $c_2=2$。

---

Palindromic Value

题目

$\hspace{15pt}$小苯有一个长度为 $n$ 的字符串 $s$，仅由小写字母组成。
$\hspace{15pt}$小苯可以将 $s$ 分割为若干个非空子串$^\texttt{[1]}$，要求每个子串都是回文串$^\texttt{[2]}$。
$\hspace{15pt}$定义一种分割方案的价值为：所有子串长度的平方和。更具体地，将 $s$ 表示为 $s = t_1 t_2 \cdots t_k$ 的一种写法，其中 $t_i$​ 为 $s$ 的非空连续子串，且每个 $t_i$ 都是回文串。分割方案的价值为 $\sum_{i=1}^k (|t_i|)^2$，其中 $|t_i|$ 表示 $t_i$ 的长度。

$\hspace{15pt}$记所有不同分割方案（分割点集合不同视为不同方案）的价值之和为答案。
$\hspace{15pt}$你的任务就是求出这个答案。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

【名词解释】
$\hspace{15pt}$子串$^\texttt{[1]}$：从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
$\hspace{15pt}$回文串$^\texttt{[2]}$：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。

输入

$\hspace{15pt}$每个测试文件包含多组测试数据。第一行输入一个整数 $T\left(1 \leqq T \leqq 100 \right)$ 代表数据组数，每组测试数据描述如下：

$\hspace{15pt}$第一行一个整数 $n\left(1 \leqq n \leqq 2 \times 10^3 \right)$。
$\hspace{15pt}$第二行一个长度为 $n$，仅由小写字母组成的字符串 $s$。

$\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^3$。

输出

$\hspace{15pt}$对于每一组测试数据，新起一行输出一个整数，表示所有回文分割方案的价值总和对 $998\,244\,353$ 取模的结果。

样例1输入

2
3
aba
2
ab

样例1输出

12
2

说明

$\hspace{15pt}$对于第一组测试数据，$s = \texttt{aba}$，有两种可行分割方案：
$\hspace{23pt}\bullet\,$拆分为 $\texttt{a}$、$\texttt{b}$、$\texttt{a}$，价值 $1^2 + 1^2 + 1^2 = 3$；
$\hspace{23pt}\bullet\,$保持原状，价值 $3^2 = 9$。

$\hspace{15pt}$对于第二组测试数据，$s = \texttt{ab}$，唯一可行方案为拆分为：
$\hspace{23pt}\bullet\,$$\texttt{a}$、$\texttt{b}$，价值 $1^2 + 1^2 = 2$。

样例2输入

1
4
aaaa

样例2输出

66

说明

$\hspace{15pt}$对于第一组测试数据，$s = \texttt{aaaa}$，任意子串均为回文串，所有分割方案对应将 $4$ 分拆为有序正整数和：
$\hspace{23pt}\bullet\,$$1+1+1+1$：价值 $1+1+1+1 = 4$；
$\hspace{23pt}\bullet\,$$1+1+2$：价值 $1+1+4 = 6$；
$\hspace{23pt}\bullet\,$$1+2+1$：价值 $1+4+1 = 6$；
$\hspace{23pt}\bullet\,$$2+1+1$：价值 $4+1+1 = 6$；
$\hspace{23pt}\bullet\,$$1+3$：价值 $1+9 = 10$；
$\hspace{23pt}\bullet\,$$3+1$：价值 $9+1 = 10$；
$\hspace{23pt}\bullet\,$$2+2$：价值 $4+4 = 8$；
$\hspace{23pt}\bullet\,$$4$：价值 $16$。
$\hspace{15pt}$总和为 $4+6+6+6+10+10+8+16 = 66$。

---

Find the Zero

题目

这是一个交互式题目。

给你一个整数 $n$。有一个长度为 $2n$ 的隐藏数组 $a$。数组中从 $1$ 到 $n$ 的每个整数 恰好出现一次，其余元素全都是 $0$。

你可以进行如下查询：

• 选择两个整数 $i$ 和 $j$（$1\le i,j\le 2n$，$i\mathrm{\ne }j$）。裁判会根据 $a_i=a_j$ 给出回答，如果成立则返回 $1$，否则返回 $0$。

请在不超过 $n+1$ 次查询内，找出任意一个满足 $a_k=0$ 的整数 $k$（$1\le k\le 2n$）。注意，交互者是 自适应的，也就是说隐藏数组 $a$ 可能会根据你的查询动态变化，但不会与之前的查询结果矛盾。

输入格式

每个测试包含多个测试用例。第一行是测试用例数量 $t$（$1\le t\le {10}^3$）。接下来是各个测试用例的描述。

每个测试用例第一行包含一个整数 $n$（$2\le n\le {10}^4$）。隐藏数组 $a$a 的长度是 $2n$。

保证所有测试用例中 $n$ 的总和不超过 ${10}^4$。

交互说明

发起查询时，输出一行格式如下：

• $? \ i \ j$（$1\le i,j\le 2n$，$i\mathrm{\ne }j$）

裁判的回应有：

• 如果 $a_i=a_j$，返回 $1$；
• 如果 $a_i\mathrm{\ne }{a}_j$​，返回 $0$；
• 如果查询无效或超过 $n+1$ 次查询限制，返回 $-1$。

报告答案时，输出一行格式：

• $! \ k$（$1\le k\le 2n$）

然后进入下一个测试用例，或者如果是最后一个测试用例则结束程序。

注意，报告答案不计入 $n+1$ 次查询限制。

交互者是 自适应的，隐藏数组 $a$ 可能会根据你的查询动态调整，但不会与之前的查询结果冲突。

每次输出查询后，别忘了换行并刷新输出缓冲区 ${}^{\text{∗}}$，否则会因为“空闲时间过长”被判定超时。如果在交互中读到 $-1$ 而非有效数据，程序必须立即退出，否则会被判“错误答案”。不退出可能导致程序继续读取关闭的输入流，产生不可预料的判决结果。

本题不支持 hack。

${}^{\text{∗}}$∗刷新输出的方法：

• C++ 中用 fflush(stdout) 或 cout.flush()；
• Python 中用 sys.stdout.flush()；
• 其他语言请参考对应文档。

样例

Inputcopy	Outputcopy
2 2 0 1 3 1 0 0	? 1 2 ? 3 1 ! 3 ? 5 6? 1 2 ? 3 1 ! 3 ? 5 6 ? 2 4 ? 1 3 ! 6

说明

第一个样例中，隐藏数组 $a$ 是 $[0,1,0,2]$：

• 第一次查询 $(i,j)=(1,2)$。因为 $a_1=0$，$a_2=1$，$a_1\mathrm{\ne }{a}_2$​，裁判返回 $0$。
• 第二次查询 $(i,j)=(3,1)$。因为 $a_3=0$，$a_1=0$，$a_3=a_1$，裁判返回 $1$。
• 程序报告 $k=3$ 作为答案。因为 $a_3=0$，答案正确。

第二个样例中，隐藏数组 $a$ 是 $[3,2,0,1,0,0]$：

• 第一次查询 $(i,j)=(5,6)$。因为 $a_5=0$，$a_6=0$，$a_5=a_6$​，裁判返回 $1$。
• 第二次查询 $(i,j)=(2,4)$。因为 $a_2=2$，$a_4=1$，$a_2\mathrm{\ne }{a}_4$，裁判返回 $0$。
• 第三次查询 $(i,j)=(1,3)$。因为 $a_1=3$，$a_3=0$，$a_1\mathrm{\ne }{a}_3$​，裁判返回 $0$。
• 程序报告 $k=6$ 作为答案。因为 $a_6=0$，答案正确。

---

Ghostfires

题目

OtterZ 决定用幽灵火打造一把武器。他收集了红色、绿色和蓝色的幽灵火若干。他想把这些幽灵火排成一排来制作武器。为了让武器更强大，OtterZ 希望用尽可能多的幽灵火，但如果排成的行中有两个同色幽灵火相邻，或者中间隔着恰好两个幽灵火，那武器就会失控。

具体来说，OtterZ 收集了 $r$ 个红色幽灵火，$g$ 个绿色幽灵火，和 $b$ 个蓝色幽灵火。他想构造一个字符串 $s$，由字符 ‘R’、’G’ 和 ‘B’ 组成，满足以下条件：

• 字符串 $s$ 中 ‘R’、’G’ 和 ‘B’ 的出现次数分别不超过 $r$、$g$ 和 $b$。
• 对所有 $1\le i\le \mathrm{\mid }s\mathrm{\mid }-1$，满足 $s_i\mathrm{\ne }{s}_{i+1}$。
• 对所有 $1\le i\le \mathrm{\mid }s\mathrm{\mid }-3$，满足 $s_i\mathrm{\ne }{s}_{i+3}$​。
• 字符串 $s$ 的长度尽可能长。

帮 OtterZ 构造这样一排幽灵火。虽然可能有多个方案，OtterZ 只要其中一个就行。

输入

输入包含多组测试数据。第一行是测试组数 $t$（$1\le t\le {10}^4$）。接下来是各组测试数据的描述。

每组测试数据只有一行，包含三个整数 $r$、$g$ 和 $b$（$0\le r,g,b\le {10}^6$，$r+g+b>0$），分别表示红色、绿色和蓝色幽灵火的数量。

保证所有测试组中 $r+g+b$ 的总和不超过 ${10}^6$。

输出

对于每组测试，输出一个字符串 $s$，由字符 ‘R’、’G’ 和 ‘B’ 组成，其中 $s_i$​ 是 ‘R’、’G’ 或 ‘B’，表示第 $i$ 个幽灵火的颜色。

如果有多个答案，输出任意一个即可。

样例

Inputcopy	Outputcopy
5 0 0 1 1 1 1 0 3 0 2 2 2 2 7 3	B RGB G GBRBRG GRGRGBGBGBG

说明

第一组测试中，”B” 是唯一合法的构造。

第二组测试中，”RGB”、”RBG”、”GRB”、”GRB”、”BRG” 和 “BGR” 都是正确答案。

第三组测试中，”GG” 和 “GGG” 都不合法，因为 $s_1=s_2$​。

---

A Trivial String Problem

题目

定义 $f(t)$ 为字符串 $t$ 能被拆分成的最大部分数，且每一部分都是 $t$ 的非空前缀。换句话说，$f(t)$ 是满足以下条件的最大正整数 $k$：

• 存在 $k$ 个字符串 $p_1,p_2,\dots ,p_k$，它们都是 $t$ 的前缀，且 $t=p_1+p_2+\dots +p_k$。这里 $+$ 表示字符串的拼接。

给你一个长度为 $n$ 的字符串 $s$，仅包含小写英文字母。记 $s[x\mathrm{.}\mathrm{.}y]$ 为字符串 $s$ 从第 $x$ 个字符到第 $y$ 个字符（包含两端）的子串。你需要回答 $q$ 个查询。第 $i$ 个查询给出两个整数 $l_i$​ 和 $r_i$​，你需要求出

$$\sum _{j=l_i}^{r_i}f(s[l_i\mathrm{.}\mathrm{.}j])\mathrm{.}$$

${}^{\text{∗}}$字符串 $a$ 是字符串 $b$ 的子串，意味着 $a$ 可以通过从 $b$ 的开头删去若干（可能是零个或全部）字符，再从结尾删去若干（可能是零个或全部）字符得到。

输入格式

每个测试包含多个测试用例。第一行是测试用例数量 $t$ ($1\le t\le {10}^3$)。接下来是各个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($1\le n\le {10}^6$, $1\le q\le 100$)。

第二行是长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。

接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$​ ($1\le l_i\le r_i\le n$)，表示第 $i$ 个查询。

保证所有测试用例中 $n$ 的总和不超过 ${10}^6$。

输出格式

对于每个查询，输出一个整数，表示对应表达式的值。

样例

Inputcopy	Outputcopy
6 1 1 a 1 1 5 2 aaaaa 1 5 2 4 6 2 abcdef 1 6 3 5 6 3 abaaba 1 6 1 3 2 6 7 3 abcabca 1 7 2 7 4 7 8 3 aababaac 1 8 2 8 3 7	1 15 6 6 3 14 4 7 12 9 5 13 14 7

说明

第一个测试用例中，$f(\mathtt{\text{a}})=1$。

第二个测试用例中，$f(\mathtt{\text{a}})+f(\mathtt{\text{aa}})+f(\mathtt{\text{aaa}})+f(\mathtt{\text{aaaa}})+f(\mathtt{\text{aaaaa}})=1+2+3+4+5=15$ 和 $f(\mathtt{\text{a}})+f(\mathtt{\text{aa}})+f(\mathtt{\text{aaa}})=1+2+3=6$。

第三个测试用例中，$f(\mathtt{\text{a}})+f(\mathtt{\text{ab}})+f(\mathtt{\text{abc}})+f(\mathtt{\text{abcd}})+f(\mathtt{\text{abcde}})+f(\mathtt{\text{abcdef}})=1+1+1+1+1+1=6$ 和 $f(\mathtt{\text{c}})+f(\mathtt{\text{cd}})+f(\mathtt{\text{cde}})=1+1+1=3$。