Rating 1200

2137D 用出现次数替换

来源：Codeforces Round 1047 (Div. 3)-D. Replace with Occurrences

Tags: 构建算法

给定一个数组 $a$，令 $f(x)$ 表示值 $x$ 在数组 $a$ 中出现的次数。例如，当 $a=[1,2,3,1,4]$ 时，$f(1)=2$，$f(3)=1$。

你有一个大小为 $n$ 的数组 $b$。请判断是否存在一个大小为 $n$ 的数组 $a$，使得对于所有 $1 \leq i \leq n$，都有 $f(a_i)=b_i$。如果存在这样的数组，请构造它。

输入

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

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2\cdot 10^5$)。

第二行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$ ($1 \leq b_i \leq n$)。

保证所有测试用例的 $n$ 的总和不超过 $2\cdot 10^5$。

输出

对于每个测试用例，如果不存在有效的数组 $a$，则输出 $-1$。

否则，在新的一行输出包含 $n$ 个整数的数组 $a$。元素应满足 $1 \leq a_i \leq n$。

测试用例

输入

3
4
1 2 3 4
6
1 2 2 3 3 3
6
6 6 6 6 6 6

输出

-1
4 5 5 6 6 6
2 2 2 2 2 2

注意

在第一个测试用例中，可以证明没有数组满足要求。

在第二个测试用例中，$4$、$5$、$6$ 分别出现了 $1$、$2$、$3$ 次。因此，输出数组是正确的，因为 $f(4),f(5),f(5),f(6),f(6),f(6)$ 分别是 $1,2,2,3,3,3$。

2134C 更大的偶数

来源：Codeforces Round 1045 (Div. 2)-C. Even Larger

Tags: 暴力破解 贪心 实现

如果一个数组满足：对于每一个长度至少为 $2$ 的子数组 $^{\text{∗}}$ ，其中位于原数组偶数索引处的元素之和大于或等于位于奇数索引处的元素之和，则该数组被称为好的。数组索引从 $1$ 开始。

例如，数组 $[3,8,4,4]$ 和 $[2,3,1,4,2]$ 是好的。数组 $[0,2,4,1]$ 不是好的，因为在子数组 $[2,4,1]$ 中，原数组偶数索引处的元素是 $2$（索引 $2$）和 $1$（索引 $4$），而奇数索引处唯一的元素是 $4$（索引 $3$）。由于 $2 + 1 < 4$，条件不满足。

给定一个包含 $n$ 个非负整数的数组 $a_1,a_2,\ldots,a_n$。在一次操作中，你可以将数组中的任意元素减少 $1$，但所有元素必须保持非负。你的任务是找到使数组 $a$ 成为好数组所需的最少操作次数。可以证明，通过有限次操作可以使数组变成好的。

$^{\text{∗}}$ 如果数组 $b$ 可以通过从数组 $a$ 的开头删除若干个（可能为零或全部）元素以及从末尾删除若干个（可能为零或全部）元素得到，则称 $b$ 是 $a$ 的一个子数组。

输入

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

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) —— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$) —— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，在新的一行输出一个整数 —— 使数组 $a$ 成为好数组所需的最少操作次数。

测试用例

输入

8
4
3 8 4 4
4
0 2 3 5
2
3 1
5
2 3 1 4 2
4
0 2 4 1
5
3 1 4 5 1
11
3 0 5 4 4 5 3 0 3 4 1
12
410748345 10753674 975233308 193331255 893457280 279719251 704970985 412553354 801228787 44181004 1000000000 3829103

输出

0
1
2
0
3
6
14
4450984776

注意

在第一个测试用例中，数组 $a$ 已经是好的，所以答案是 $0$。以下是每个子数组的检查：

在第二个测试用例中，数组 $a$ 不是好的：

但是，如果我们在索引 $3$ 上执行一次操作，数组变为 $[0,2,2,5]$ 并且现在是好的：

因此，答案是 $1$。

2134B 加 0 或 K

来源：Codeforces Round 1045 (Div. 2)-B. Add 0 or K

Tags: 构造算法 数学 数论

给定一个包含 $n$ 个正整数的数组 $a_1, a_2, \ldots, a_n$ 和一个正整数 $k$。

在一次操作中，你可以给每个 $a_i$ 加上 $0$ 或 $k$，即选择另一个包含 $n$ 个整数的数组 $b_1, b_2, \ldots, b_n$，其中每个 $b_i$ 是 $0$ 或 $k$，并将 $a_i$ 更新为 $a_i + b_i$（$1 \le i \le n$）。注意，你可以为数组 $b$ 的每个元素选择不同的值。

你的任务是执行最多 $k$ 次这样的操作，使得 $\gcd(a_1, a_2, \ldots, a_n) > 1$ $^{\text{∗}}$。可以证明这总是可行的。

输出操作后的最终数组。你不需要输出操作本身。

$^{\text{∗}}$ $\gcd(a_1, a_2, \ldots, a_n)$ 表示 $a_1, a_2, \ldots, a_n$ 的最大公约数 (GCD)。

输入

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

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^5$, $1 \leq k \leq 10^9$) —— 分别是数组 $a$ 的长度和给定的常数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) —— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 的总和不超过 $10^5$。

输出

对于每个测试用例，在新的一行输出包含 $n$ 个整数的数组 —— 操作后的最终数组。输出中的整数应在 $1$ 到 $10^9 + k^2$ 的范围内。

如果有多个有效输出，你可以输出其中任何一个。

注意，你不需要最小化操作次数。

测试用例

输入

8
3 3
2 7 1
4 5
2 9 16 14
4 1
1 2 3 4
5 2
5 6 7 8 9
2 10
7 9
1 1000000000
1
1 371
1000000000
3 6
1 3 5

输出

8 10 10
7 14 21 14
2 2 4 4
9 6 9 12 9
77 99
1000000000000000001
1000000000
25 15 5

注意

在第一个测试用例中，输出 $[8,10,10]$ 是有效的，因为 $\gcd(8, 10, 10) = 2 > 1$，并且数组 $[2, 7, 1]$ 可以通过最多 $3$ 次操作转换为 $[8, 10, 10]$。一种可能的操作序列如下所示：

其他输出如 $[2, 10, 4]$、$[8, 16, 4]$ 和 $[5, 10, 10]$ 也被认为是有效的。

在第二个测试用例中，输出 $[7, 14, 21, 14]$ 是有效的，因为：

• $\gcd(7, 14, 21, 14) = 7 > 1$。
• 从 $[2, 9, 16, 14]$ 开始，应用 $b = [5, 5, 5, 0]$ 的操作得到 $[7, 14, 21, 14]$，所需操作次数不超过 $5$ 次。

2123D 二进制字符串对战

来源：Codeforces Round 1034 (Div. 3)-D. Binary String Battle

Tags: 构造算法 游戏 贪心

Alice 和 Bob 被给定一个长度为 $n$ 的二进制字符串 $s$，以及一个整数 $k$ ($1\leq k < n$)。

如果 Alice 能够将 $s$ 的所有字符变为零，则她获胜。如果 Alice 无法在有限步内获胜，则 Bob 获胜。

Alice 和 Bob 轮流行动，Alice 先手。

• 在 Alice 的回合，她可以选择 $s$ 中任意一个长度为 $k$ 的子序列$^{\text{∗}}$，然后将该子序列中的所有字符设置为零。
• 在 Bob 的回合，他可以选择 $s$ 中任意一个长度为 $k$ 的子串$^{\text{†}}$，然后将该子串中的所有字符设置为一。

注意，如果在游戏过程中的任何时刻（包括在 Alice 和 Bob 的回合之间）字符串全为零，则 Alice 获胜。

判断在双方都采取最优策略的情况下谁会获胜。

$^{\text{∗}}$ 字符串 $s$ 的一个子序列是 $s$ 中的一组字符。注意这些字符不必相邻。

$^{\text{†}}$ 字符串 $s$ 的一个子串是 $s$ 中一组连续的字符。注意这些字符必须相邻。

输入

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($2\leq n \leq 2\cdot 10^5$, $1\leq k < n$)。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 的总和不超过 $2\cdot 10^5$。

输出

对于每个测试用例，在一行中输出 "Alice"（如果 Alice 在最优策略下获胜）或 "Bob"（如果 Bob 在最优策略下获胜）。

你可以以任何大小写形式输出答案（大写或小写）。例如，字符串 "aLiCe"、"alice"、"ALICE" 和 "alICE" 都将被识别为 "Alice"。

测试用例

输入

6
5 2
11011
7 4
1011011
6 1
010000
4 1
1111
8 3
10110110
6 4
111111

输出

Bob
Alice
Alice
Bob
Bob
Alice

注意

在第三个样例中，Alice 可以选择由 $s_2$ 组成的子序列，将 $s$ 变为 $000000$。然后她立即获胜。

在第四个样例中，可以证明 Alice 无法保证在有限步内将 $s$ 变为 $0000$。

2118B 使其成为排列

来源：Codeforces Round 1030 (Div. 2)-B. Make it Permutation

Tags: 构造算法

存在一个大小为 $n \times n$ 的矩阵 $A$，其中对于所有 $1 \le i,j \le n$，有 $A_{i,j}=j$。

在一次操作中，你可以选择一行并反转该行中的任意一个子数组 $^{\text{∗}}$。

请找出一系列最多 $2n$ 次的操作，使得每一列都包含一个长度为 $n$ 的排列 $^{\text{†}}$。

可以证明这样的构造总是可能的。如果有多个解决方案，输出其中任意一个。

$^{\text{∗}}$ 如果数组 $a$ 可以通过从数组 $b$ 的开头删除零个或多个元素以及从末尾删除零个或多个元素得到，则称 $a$ 是 $b$ 的一个子数组。

$^{\text{†}}$ 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中出现了 $4$）。

输入

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

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 5000$) —— 表示矩阵的行数和列数。

保证所有测试用例的 $n$ 的总和不超过 $5000$。

输出

对于每个测试用例，在第一行打印一个整数 $k$ $(0 \le k \le 2n)$，表示你希望执行的操作次数。在接下来的行中，你应该打印这些操作。

要打印一个操作，请使用格式 "$i\;l\;r$" ($1 \leq l \leq r \leq n$ 且 $1 \leq i \leq n$)，这表示反转子数组 $A_{i, l}$, $A_{i, l+1}$, $\ldots$, $A_{i, r}$。

测试用例

输入

2
3
4

输出

4
2 1 3
2 2 3
3 1 2
3 2 3
5
2 1 4
3 1 3
3 2 4
4 3 4
4 1 2

注意

在第一个测试用例中，以下操作是一个有效的解决方案：

2113B 良好的开端

来源：Codeforces Round 1031 (Div. 2)-B. Good Start

Tags: 构造算法 数学

屋顶是一个大小为 $w \times h$ 的矩形，其左下角位于平面上的点 $(0, 0)$。你的团队需要用尺寸为 $a \times b$ 的相同屋顶板材完全覆盖这个屋顶，并满足以下条件：

• 板材不能旋转（即使是 $90^\circ$ 也不行）。
• 板材不能重叠（但可以在边缘处接触）。
• 板材可以超出矩形屋顶的边界。

你团队中的一个新手已经将两块这样的板材放置在屋顶上，使得这两块板材不重叠，并且每块都部分覆盖了屋顶。

你的任务是判断是否可以在不移除已放置的两块板材的情况下完全铺满屋顶。

输入

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

每个测试用例的第一行包含四个整数 $w$, $h$, $a$, 和 $b$ ($1 \le w, h, a, b \le 10^9$) —— 分别是屋顶的尺寸和屋顶板材的尺寸。

每个测试用例的第二行包含四个整数 $x_1$, $y_1$, $x_2$, 和 $y_2$ ($-a + 1 \le x_1, x_2 \le w - 1, -b + 1 \le y_1, y_2 \le h - 1$) —— 已放置屋顶板材的左下角坐标。保证这些板材不重叠。

输出

对于每个测试用例，如果可以在不移除已放置的两块板材的情况下完全铺满屋顶，则输出 "Yes"（不带引号），否则输出 "No"（不带引号）。

你可以以任何大小写形式输出答案（大写或小写）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 将被识别为肯定响应。

测试用例

输入

7
6 5 2 3
-1 -2 5 4
4 4 2 2
0 0 3 1
10 9 3 2
0 0 4 3
10 9 3 2
0 0 6 3
5 5 2 2
-1 -1 4 -1
5 5 2 2
-1 -1 2 3
7 8 2 4
0 0 0 5

输出

Yes
No
No
Yes
No
Yes
No

注意

在第一个测试用例中，可以按如下方式添加 $8$ 块屋顶板材：

在第二个测试用例中，无法完全铺满屋顶：

2092C 亚丝娜与仰慕者

来源：Codeforces Round 1014 (Div. 2)-C. Asuna and the Mosquitoes

Tags: 构造算法 贪心 数学

在亚丝娜生日时，她的 $n$ 位仰慕者每人送给她一座塔。第 $i$ 位仰慕者送的塔的高度为 $a_i$。

亚丝娜对收到的礼物的美观度评估为 $\max(a_1, a_2, \ldots, a_n)$。她可以执行任意次（包括零次）以下操作：

• 选择满足 $1 \le i \neq j \le n$ 的索引 $i$ 和 $j$，使得 $a_i + a_j$ 为奇数且 $a_i > 0$，然后将 $a_i$ 减少 $1$，将 $a_j$ 增加 $1$。

容易看出，在操作过程中塔的高度保持非负。

帮助亚丝娜找出在经过任意次操作后，礼物美观度的最大可能值！

输入

每个测试包含多个测试用例。输入数据的第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) —— 亚丝娜的仰慕者数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) —— 塔的高度。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数：亚丝娜能够达到的礼物美观度的最大值。

测试用例

输入

4
3
5 3 9
2
3 2
4
1 2 2 1
5
5 4 3 2 9

输出

9
5
5
21

注意

在第一个测试用例中，没有一对塔满足应用操作所需的条件，因此无法执行任何操作。在这种情况下，答案是 $\max(5, \ 3, \ 9) = 9$。

在第二个测试用例中，操作 $i = 2$ 和 $j = 1$ 可以应用两次。之后，数组变为：$a \ = \ [5, \ 0]$。因此，答案是 5。

在第三个测试用例中，可以应用以下操作序列：

1. 操作 $i=1$ 和 $j=2$。

   $[1, \ 2, \ 2, \ 1] \quad \rightarrow \quad [0, \ 3, \ 2, \ 1]$

2. 操作 $i=3$ 和 $j=2$。

   $[0, \ 3, \ 2, \ 1] \quad \rightarrow \quad [0, \ 4, \ 1, \ 1]$

3. 操作 $i=3$ 和 $j=2$。

   $[0, \ 4, \ 1, \ 1] \quad \rightarrow \quad [0, \ 5, \ 0, \ 1]$

$\max(0, \ 5, \ 0, \ 1) \ = \ 5$。

因此，答案是 5。

2072C 为储物库创建密钥已成为我的主要技能

来源：Codeforces Round 1006 (Div. 3)-C. Creating Keys for StORages Has Become My Main Skill

Tags: 位掩码 构造算法 贪心

Akito 仍然无处可住，而且小房间的价格到处都很高。因此，Akito 决定在一家银行找一份工作，担任储物库的钥匙创建员。

在这个奇幻的世界里，一切都不同。例如，代码为 $(n, x)$ 的储物库的钥匙是一个长度为 $n$ 的数组 $a$，满足：

• $a_1 \ | \ a_2 \ | \ a_3 \ | \ \ldots \ | \ a_n = x$，其中 $a \ | \ b$ 表示数字 $a$ 和 $b$ 的按位"或"运算。
• 在所有满足上述条件的数组中，$\text{MEX}(\{ a_1, a_2, a_3, \ldots, a_n \})$ $^{\text{∗}}$ 的值是最大的。

Akito 勤奋地工作了几个小时，但突然头痛起来。请替他工作一小时；对于给定的 $n$ 和 $x$，为代码 $(n, x)$ 的储物库创建任意一把钥匙。

$^{\text{∗}}$ $\text{MEX}(S)$ 是指最小的非负整数 $z$，使得 $z$ 不在集合 $S$ 中，并且所有 $0 \le y < z$ 都在集合 $S$ 中。

输入

第一行包含一个数字 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例仅一行，给出两个数字 $n$ 和 $x$ ($1 \le n \le 2 \cdot 10^5, 0 \le x < 2^{30}$) —— 分别是数组的长度和期望的按位"或"值。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出 $n$ 个整数 $a_i$ ($0 \le a_i < 2^{30}$) —— 满足所有条件的钥匙数组的元素。

如果有多个合适的数组，输出其中任意一个。

测试用例

输入

9
1 69
7 7
5 7
7 3
8 7
3 52
9 11
6 15
2 3

输出

69
6 0 3 4 1 2 5
4 1 3 0 2
0 1 2 3 2 1 0
7 0 6 1 5 2 4 3
0 52 0
0 1 8 3 0 9 11 2 10
4 0 3 8 1 2
0 3

2056C 回文子序列

来源：Codeforces Round 997 (Div. 2)-C. Palindromic Subsequences

Tags: 暴力破解 构造算法 数学

对于一个整数序列 $a = [a_1, a_2, \ldots, a_n]$，我们定义 $f(a)$ 为 $a$ 中最长的回文 $^{\text{†}}$ 子序列 $^{\text{∗}}$ 的长度。

令 $g(a)$ 表示长度为 $f(a)$ 的回文子序列的数量。换句话说，$g(a)$ 统计了 $a$ 中具有最大长度的回文子序列的数量。

给定一个整数 $n$，你的任务是找到任意一个满足以下条件的包含 $n$ 个整数的序列 $a$：

• 对于所有 $1 \le i \le n$，有 $1 \le a_i \le n$。
• $g(a) > n$

可以证明，在给定的约束下，这样的序列总是存在的。

$^{\text{∗}}$ 如果序列 $x$ 可以通过从序列 $y$ 中任意位置删除若干个（可能为零或全部）元素得到，则称 $x$ 是 $y$ 的一个子序列。

$^{\text{†}}$ 回文是指从左向右读和从右向左读都相同的序列。例如，$[1, 2, 1, 3, 1, 2, 1]$、$[5, 5, 5, 5]$ 和 $[4, 3, 3, 4]$ 是回文，而 $[1, 2]$ 和 $[2, 3, 3, 3, 3]$ 不是。

输入

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

每个测试用例的第一行包含一个整数 $n$ (${\color{red}{6}} \le n \le 100$) —— 序列的长度。

注意：没有关于所有测试用例 $n$ 的总和的约束。

输出

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示一个满足条件的数组。

如果有多个解决方案，你可以输出其中任意一个。

测试用例

输入

3
6
9
15

输出

1 1 2 3 1 2
7 3 3 7 5 3 7 7 3
15 8 8 8 15 5 8 1 15 5 8 15 15 15 8

注意

在第一个例子中，一个可能的解决方案是 $a = [1, 1, 2, 3, 1, 2]$。在这种情况下，$f(a) = 3$，因为最长的回文子序列长度为 $3$。有 $7$ 种方法可以选择长度为 $3$ 的回文子序列，如下所示：

1. $[a_1, a_2, a_5] = [1, 1, 1]$
2. $[a_1, a_3, a_5] = [1, 2, 1]$
3. $[a_1, a_4, a_5] = [1, 3, 1]$
4. $[a_2, a_3, a_5] = [1, 2, 1]$
5. $[a_2, a_4, a_5] = [1, 3, 1]$
6. $[a_3, a_4, a_6] = [2, 3, 2]$
7. $[a_3, a_5, a_6] = [2, 1, 2]$

因此，$g(a) = 7$，大于 $n = 6$。因此，$a = [1, 1, 2, 3, 1, 2]$ 是一个有效的解决方案。

在第二个例子中，一个可能的解决方案是 $a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$。在这种情况下，$f(a) = 5$。有 $24$ 种方法可以选择长度为 $5$ 的回文子序列。一些例子是 $[a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]$ 和 $[a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]$。因此，$g(a) = 24$，大于 $n = 9$。因此，$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$ 是一个有效的解决方案。

在第三个例子中，$f(a) = 7$ 且 $g(a) = 190$，大于 $n = 15$。

2041E 美丽数组

来源：2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)-E. Beautiful Array

Tags: 构造算法 数学

图片由 ChatGPT 4o 生成。

A-Ming 的生日快到了，他的朋友 A-May 决定送他一个整数数组作为礼物。A-Ming 有两个最喜欢的数字 $a$ 和 $b$，他认为一个数组是美丽的，当且仅当它的均值恰好等于 $a$，中位数恰好等于 $b$。请帮助 A-May 找到一个美丽的数组，让她的礼物能给 A-Ming 留下深刻印象。

数组的均值是其元素之和除以其长度。例如，数组 $[3, -1, 5, 5]$ 的均值是 $12 \div 4 = 3$。

数组的中位数是排序后位于中间的元素（如果长度为奇数），或者是排序后中间两个元素的均值（如果长度为偶数）。例如，$[1, 1, 2, 4, 8]$ 的中位数是 $2$，而 $[3, -1, 5, 5]$ 的中位数是 $(3 + 5) \div 2 = 4$。

注意，均值和中位数不一定四舍五入为整数。例如，数组 $[1, 2]$ 的均值是 $1.5$。

输入

仅一行，包含两个整数 $a$ 和 $b$。

• $-100 \leq a, b \leq 100$。
• 数组的长度必须在 $1$ 到 $1000$ 之间。
• 数组的元素必须是整数，且其绝对值不得超过 $10^6$。

输出

第一行输出数组的长度。

第二行输出数组的元素。

如果有多个解决方案，你可以输出任意一个。可以证明，在问题的约束下，总是存在解决方案。

测试用例

输入 1

3 4

输出 1

4
3 -1 5 5

输入 2

-100 -100

输出 2

1
-100

2003C 乌龟与好对

来源：Codeforces Round 968 (Div. 2)-C. Turtle and Good Pairs

Tags: 构造算法 贪心 排序

乌龟给你一个由小写拉丁字母组成的字符串 $s$。

乌龟认为一对整数 $(i, j)$ ($1 \le i < j \le n$) 是愉快对，当且仅当存在一个整数 $k$ 满足 $i \le k < j$，并且同时满足以下两个条件：

• $s_k \ne s_{k + 1}$；
• $s_k \ne s_i$ 或 $s_{k + 1} \ne s_j$。

此外，乌龟认为一对整数 $(i, j)$ ($1 \le i < j \le n$) 是好对，当且仅当 $s_i = s_j$ 或 $(i, j)$ 是一个愉快对。

乌龟想要重新排列字符串 $s$，使得好对的数目最大化。请帮助他！

输入

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

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) —— 字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出重新排列后的字符串 $s$，使得好对的数目最大化。如果有多个答案，输出其中任意一个。

测试用例

输入

5
3
abc
5
edddf
6
turtle
8
pppppppp
10
codeforces

输出

acb
ddedf
urtlet
pppppppp
codeforces

注意

在第一个测试用例中，在重新排列后的字符串中，$(1, 3)$ 是一个好对。可以看出，我们无法通过重新排列字符串使得好对的数目大于 $1$。bac 和 cab 也可以是答案。

在第二个测试用例中，在重新排列后的字符串中，$(1, 2)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 5)$ 都是好对。efddd 也可以是答案。

1983B 角落旋转

来源：Codeforces Round 956 (Div. 2) and ByteRace 2024-B. Corner Twist

Tags: 构造算法 贪心 实现 数学

给你两个数字网格 $a$ 和 $b$，都有 $n$ 行和 $m$ 列。网格中的所有值都是 $0$、$1$ 或 $2$。

你可以在 $a$ 上执行任意次以下操作：

• 在网格中选取任意一个长和宽都 $\ge 2$ 的子矩形。允许选择整个网格作为子矩形。
• 该子矩形有四个角。取所选子矩形的任意一对对角，将它们的值加 $1$ 后对 $3$ 取模。
• 对于未被选中的那对角，将它们的值加 $2$ 后对 $3$ 取模。

注意，该操作只改变所选子矩形角上的值。

是否可以通过应用上述操作任意次（包括零次）将网格 $a$ 转换为网格 $b$？

输入

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 250$)。

对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$，表示网格的行数和列数 ($2 \le n,m \le 500$)。

接下来的 $n$ 行，每行包含 $m$ 个字符 —— 第 $i$ 行的第 $j$ 个字符表示 $a_{i,j}$。

再接下来的 $n$ 行，每行包含 $m$ 个字符 —— 第 $i$ 行的第 $j$ 个字符表示 $b_{i,j}$ ($0 \le a_{i,j}, b_{i,j} \le 2$)。

保证所有测试用例的 $n$ 的总和以及所有测试用例的 $m$ 的总和不超过 $500$。

输出

对于每个测试用例，如果可以将网格 $a$ 转换为网格 $b$，则打印 "YES"（不带引号），否则打印 "NO"（不带引号）。

你可以以任何大小写形式输出答案（大写或小写）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 将被识别为肯定响应。

测试用例

输入

7
3 3
000
000
000
111
111
111
4 4
0000
0000
0000
0000
2100
1200
0012
0021
4 4
1020
1200
1210
0000
0000
1200
2200
0000
3 3
012
012
012
010
111
011
8 8
00000000
00000000
00000000
00000000
00000000
00000000
00000000
10000000
00000000
01200000
02010000
00102000
00020100
00001020
00000210
10000000
2 7
0000000
0000000
2220111
0111222
2 7
0000000
0100010
2220111
1210202

输出

YES
YES
YES
NO
YES
NO
YES

注意

在第一个测试用例中，网格 $a$ 可以通过以下方式转换为 $b$：

$\begin{matrix}\fbox{0} & 0 & \fbox{0}\\ 0 & 0 & 0\\ \fbox{0} & 0 & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ 0 & \fbox{0} & \fbox{0}\\ 2 & \fbox{0} & \fbox{1}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ \fbox{0} & \fbox{1} & 2\\ \fbox{2} & \fbox{2} & 2\end{matrix} \Rightarrow \begin{matrix}1 & \fbox{0} & \fbox{2}\\ 1 & 0 & 2\\ 1 & \fbox{0} & \fbox{2}\end{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & \fbox{0} & \fbox{2}\\ 1 & \fbox{2} & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix}$

这里，在每次操作中，用框突出显示的右上角和左下角的值加 $2$ 后对 $3$ 取模，而左上角和右下角的值加 $1$ 后对 $3$ 取模。

在第四个测试用例中，可以证明无法通过上述操作任意次将网格 $a$ 转换为网格 $b$。

1979C 投注盈利

来源：Codeforces Round 951 (Div. 2)-C. Earning on Bets

Tags: 二分查找 组合数学 构造算法 数论

你被邀请参与一个游戏。在这个游戏中，有 $n$ 种可能的结果，对于每一种结果，你必须下注一定数量的整数金币。如果第 $i$ 种结果获胜，你将获得在该结果上下注的金币数量乘以 $k_i$ 的回报。注意，恰好只有一种结果会获胜。

你的任务是确定如何分配金币，使得在任何一种结果获胜的情况下，你都能盈利。更正式地说，你在所有结果上下注的金币总数必须严格小于每一种可能获胜结果所获得的回报金币数。

输入

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

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 50$) —— 结果的数量。

每个测试用例的第二行包含 $n$ 个整数 $k_1,k_2,\ldots,k_n$ ($2 \le k_i \le 20$) —— 如果第 $i$ 种结果获胜，回报金币的乘数。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，如果无法按要求分配金币，则输出 $-1$。否则，输出 $n$ 个整数 $x_1, x_2,\ldots, x_n$ ($1 \le x_i \le 10^{9}$) —— 你在各个结果上的下注金额。

可以证明，如果存在解，则总存在满足这些约束的解。

如果有多个合适的解决方案，输出其中任意一个。

测试用例

输入

6
3
3 2 7
2
3 3
5
5 5 5 5 5
6
7 9 3 17 9 13
3
6 3 2
5
9 4 6 8 3

输出

27 41 12 
1 1 
-1
1989 1547 4641 819 1547 1071 
-1
8 18 12 9 24

注意

在第一个测试用例中，金币可以按如下方式分配：在第一个结果上下注 $27$ 枚金币，在第二个结果上下注 $41$ 枚金币，在第三个结果上下注 $12$ 枚金币。那么在所有结果上下注的金币总数为 $27 + 41 + 12 = 80$ 枚金币。如果第一个结果获胜，你将获得 $3 \cdot 27 = 81$ 枚金币的回报；如果第二个结果获胜，你将获得 $2 \cdot 41 = 82$ 枚金币的回报；如果第三个结果获胜，你将获得 $7 \cdot 12 = 84$ 枚金币的回报。所有这些值都严格大于 $80$。

在第二个测试用例中，一种方法是在每个结果上下注一枚金币。

1935B MAC 中的信息学

来源：Codeforces Round 932 (Div. 2)-B. Informatics in MAC

Tags: 构造算法

在硕士援助中心，Nyam-Nyam 收到了一份信息学的作业。

有一个长度为 $n$ 的数组 $a$，你需要将其分割成 $k > 1$ 个子段$^{\dagger}$，使得每个子段的 $\operatorname{MEX} ^{\ddagger}$ 都等于同一个整数。

请帮助 Nyam-Nyam 找到任何合适的分割方法，或者确定这种分割不存在。

$^{\dagger}$ 将数组分割成 $k$ 个子段定义为 $k$ 对整数 $(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$，满足 $l_i \le r_i$，并且对于每个 $1 \le j \le k - 1$，有 $l_{j + 1} = r_j + 1$，同时 $l_1 = 1$ 且 $r_k = n$。这些数对代表了各个子段本身。

$^{\ddagger}\operatorname{MEX}$ 是指不属于该数组的最小非负整数。

例如：

• 数组 $[2, 2, 1]$ 的 $\operatorname{MEX}$ 是 $0$，因为 $0$ 不在数组中。
• 数组 $[3, 1, 0, 1]$ 的 $\operatorname{MEX}$ 是 $2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。
• 数组 $[0, 3, 1, 2]$ 的 $\operatorname{MEX}$ 是 $4$，因为 $0$、$1$、$2$、$3$ 都在数组中，但 $4$ 不在。