Rating 1100

2138A 蛋糕分配

来源：Codeforces Round 1048 (Div. 1)-A. Cake Assignment

Tags: 位掩码 构造算法 贪心

Chocola 和 Vanilla 喜欢蛋糕。今天，一家蛋糕店的经理给了她们总共 $2^{k+1}$ 个蛋糕。蛋糕被平均分配，因此她们最初每人收到了 $2^k$ 个蛋糕。

然而，Chocola 和 Vanilla 现在想要重新分配蛋糕，使得 Chocola 最终恰好拥有 $x$ 个蛋糕，而 Vanilla 获得剩下的 $2^{k+1}-x$ 个蛋糕。

在一步操作中，她们可以恰好执行以下两种操作之一：

1. Chocola 将她的一半蛋糕给 Vanilla。此操作仅在 Chocola 当前拥有偶数个蛋糕时允许执行。
2. Vanilla 将她的一半蛋糕给 Chocola。此操作仅在 Vanilla 当前拥有偶数个蛋糕时允许执行。

你的任务是确定达到目标分配所需的最少步数，并输出达到该最小值的任何有效操作序列。

可以证明，在给定的约束条件下，总是存在一个有效的解决方案，并且所需的最少步数最多为 $120$。

输入

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

每个测试用例的第一行包含两个整数 $k$ 和 $x$ ($1 \le k \le 60$, $1 \le x \le 2^{k+1}-1$) —— 每个人最初收到了 $2^k$ 个蛋糕，$x$ 是重新分配后 Chocola 应该拥有的蛋糕数量。

输出

对于每个测试用例，输出一个整数 $n$ ($0\le n\le 120$)，表示她们相应地重新分配蛋糕所需的最少步数。

在下一行，输出 $n$ 个整数 $o_1, o_2, \ldots, o_n$ ($o_i = \mathtt{1}$ 或 $o_i = \mathtt{2}$)，其中 $o_i = \mathtt{1}$ 表示在第 $i$ 步中，Chocola 将她的一半蛋糕给了 Vanilla（操作 1），$o_i = \mathtt{2}$ 表示 Vanilla 将她的一半蛋糕给了 Chocola（操作 2）。

测试用例

输入

4
2 3
2 4
3 7
2 5

输出

2
2 1 
0

3
2 2 1 
2
1 2 

注意

在第一个测试用例中，她们可以通过以下步骤使得 Chocola 恰好拥有 $x = 3$ 个蛋糕，Vanilla 恰好拥有 $2 ^ {k + 1} - x = 5$ 个蛋糕。我们使用 $\{a, b\}$ 表示 Chocola 当前有 $a$ 个蛋糕，Vanilla 当前有 $b$ 个蛋糕。

在第二个测试用例中，Chocola 已经恰好拥有 $x = 4$ 个蛋糕，Vanilla 已经恰好拥有 $2 ^ {k + 1} - x = 4$ 个蛋糕，因此不需要任何操作。

在第三个测试用例中，她们可以通过以下步骤使得 Chocola 恰好拥有 $x = 7$ 个蛋糕，Vanilla 恰好拥有 $2 ^ {k + 1} - x = 9$ 个蛋糕。

2137C 最大偶数和

来源：Codeforces Round 1047 (Div. 3)-C. Maximum Even Sum

Tags: 暴力破解 贪心 实现 数学

给定两个整数 $a$ 和 $b$。你需要执行以下操作：

首先，选择一个整数 $k$，使得 $b$ 能被 $k$ 整除。然后，同时将 $a$ 乘以 $k$，并将 $b$ 除以 $k$。

找出 $a+b$ 可能的最大偶数值。如果无法使 $a+b$ 为偶数，则输出 $-1$。

输入

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

每个测试用例的第一行包含两个整数 $a$ 和 $b$ ($1 \leq a,b \leq a\cdot b \leq 10^{18})$。

输出

对于每个测试用例，在新的一行输出 $a+b$ 的最大偶数值。

测试用例

输入

7
8 1
1 8
7 7
2 6
9 16
1 6
4 6

输出

-1
6
50
8
74
-1
14

注意

在第一个测试用例中，可以证明 $a+b$ 不可能为偶数。

在第二个测试用例中，最优的 $k$ 是 $2$。和为 $2+4=6$。

2130B 无路径

来源：Codeforces Round 1040 (Div. 2)-B. Pathless

Tags: 构造算法

有一个数组 $a_1, a_2, \ldots, a_n$，由值 $0$、$1$ 和 $2$ 组成，以及一个整数 $s$。保证 $a_1, a_2, \ldots, a_n$ 至少包含一个 $0$、一个 $1$ 和一个 $2$。

Alice 想从索引 $1$ 出发，向右或向左移动长度为 $1$ 的步长，最终到达索引 $n$。在 Alice 移动的过程中，她计算所访问位置的值之和，并希望这个和恰好等于 $s$。

形式化地说，Alice 希望找到一个索引序列 $[i_1, i_2, \ldots, i_m]$，使得：

• $i_1 = 1$，$i_m = n$。
• 对所有 $1 \le j \le m$，有 $1 \leq i_j \leq n$。
• 对所有 $1 \leq j < m$，有 $|i_{j} - i_{j+1}| = 1$。
• $a_{i_1} + a_{i_2} + \ldots + a_{i_m} = s$。

然而，Bob 想要重新排列 $a_1, a_2, \ldots, a_n$ 来阻止 Alice 达成她的目标。请判断是否可能重新排列 $a_1, a_2, \ldots, a_n$，使得 Alice 无法找到她的目标序列（即使 Alice 足够聪明）。如果可能，你还需要输出重排后的数组 $a_1, a_2, \ldots, a_n$。

输入

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

每个测试用例的第一行包含两个整数 $n$ 和 $s$ ($3 \le n \le 50$, $0 \le s \le 1000$)。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 2$)。

保证 $a$ 至少包含一个 $0$、一个 $1$ 和一个 $2$。

输出

对于每个测试用例，如果可能通过重新排列 $a$ 使得 Alice 无法找到她的目标序列，则输出 $n$ 个整数 —— 即 $a$ 的这样一种重排。否则，输出 $-1$。

测试用例

输入

6
3 2
0 1 2
3 3
0 1 2
3 6
0 1 2
3 4
0 1 2
3 10
0 1 2
5 1000
2 0 1 1 2

输出

0 1 2
-1
-1
0 2 1 
-1
-1

注意

在第一个测试用例中，$a$ 的任何重排都可以阻止 Alice 达成她的目标。

在第二个测试用例中，无论怎样重排 $a$，Alice 总能找到序列 $[1,2,3]$ 作为她的目标序列。

在第三个测试用例中，不存在 $a$ 的重排可以阻止 Alice 达成她的目标。例如，对于 $a=[0,2,1]$，Alice 可以找到序列 $[1,2,3,2,3]$ 作为她的目标序列。

2125C 统计好数字

来源：Educational Codeforces Round 181 (Rated for Div. 2)-C. Count Good Numbers

Tags：位掩码 组合数学 数学 数论

质数是指恰好有两个正因数（$1$ 和它自身）的正整数。前几个质数是 $2, 3, 5, 7, 11, \dots$。

一个正整数的质因数分解是将其表示为质数的乘积。例如：

• $111$ 的质因数分解是 $3 \cdot 37$；
• $43$ 的质因数分解是 $43$；
• $12$ 的质因数分解是 $2 \cdot 2 \cdot 3$。

对于每个正整数，其质因数分解是唯一的（如果不考虑乘积中质数的顺序）。

我们称一个正整数为好的，如果其质因数分解中所有质数都至少由两个数字组成。例如：

• $343 = 7 \cdot 7 \cdot 7$ 不是好的（因为 7 是单位数）；
• $111 = 3 \cdot 37$ 不是好的（因为 3 是单位数）；
• $1111 = 11 \cdot 101$ 是好的；
• $43 = 43$ 是好的。

你需要计算从 $l$ 到 $r$（包含端点）范围内好整数的数量。

输入

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

每个测试用例占一行，包含两个整数 $l$ 和 $r$ ($2 \le l \le r \le 10^{18}$)。

输出

对于每个测试用例，输出一个整数 —— 从 $l$ 到 $r$ 范围内好整数的数量。

测试用例

输入

4
2 100
2 1000
13 37
2 1000000000000000000

输出

21
227
7
228571428571428570

2111B 斐波那契立方体

来源：Educational Codeforces Round 179 (Rated for Div. 2)-B. Fibonacci Cubes

Tags: 暴力破解 动态规划 实现 数学

有 $n$ 个斐波那契立方体，其中第 $i$ 个立方体的边长等于 $f_{i}$，这里 $f_{i}$ 是第 $i$ 个斐波那契数。

在这个问题中，斐波那契数的定义如下：

• $f_{1} = 1$
• $f_{2} = 2$
• 对于 $i > 2$，$f_{i} = f_{i - 1} + f_{i - 2}$

还有 $m$ 个空盒子，其中第 $i$ 个盒子的宽度为 $w_{i}$，长度为 $l_{i}$，高度为 $h_{i}$。

对于这 $m$ 个盒子中的每一个，你需要判断是否所有的立方体都能放入该盒子中。立方体必须按照以下规则放入盒子：

• 立方体只能堆叠在盒子中，且立方体的边必须与盒子的边平行；
• 每个立方体必须放置在盒子的底部或其他立方体的顶部，并且该立方体下方的所有空间必须被占满；
• 较大的立方体不能放置在较小的立方体之上。

输入

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

每个测试用例的第一行有两个整数 $n$ 和 $m$ ($2 \le n \le 10, 1 \le m \le 2 \cdot 10^{5}$) —— 分别是立方体的数量和空盒子的数量。

每个测试用例接下来的 $m$ 行，每行包含 $3$ 个整数 $w_{i}$, $l_{i}$ 和 $h_{i}$ ($1 \le w_{i}, l_{i}, h_{i} \le 150$) —— 第 $i$ 个盒子的尺寸。

输入附加约束：

• 所有测试用例的 $m$ 的总和不超过 $2 \cdot 10^{5}$。

输出

对于每个测试用例，输出一个长度为 $m$ 的字符串，其中第 $i$ 个字符等于 "1" 表示所有 $n$ 个立方体可以放入第 $i$ 个盒子；否则，第 $i$ 个字符等于 "0"。

测试用例

输入

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

输出

0010
100101

注意

在第一个测试用例中，只有一个盒子是合适的。立方体可以按如下方式放入其中：

2104C 卡牌游戏

来源：Educational Codeforces Round 178 (Rated for Div. 2)-C. Card Game

Tags: 暴力破解 构造算法 游戏 贪心 数学

Alice 和 Bob 正在玩一个游戏。他们拥有编号从 $1$ 到 $n$ 的 $n$ 张卡牌。在游戏开始时，这些卡牌中的一部分发给 Alice，其余的发给了 Bob。

当且仅当 $i > j$ 时，编号为 $i$ 的卡牌击败编号为 $j$ 的卡牌，但有一个例外：卡牌 $1$ 击败卡牌 $n$。

只要每个玩家至少拥有一张卡牌，游戏就会继续。在每一回合中，会发生以下事件：

1. Alice 从她的手牌中选择一张卡牌，正面朝上放在桌面上；
2. Bob 在看到 Alice 的卡牌后，从他自己的手牌中选择一张卡牌，正面朝上放在桌面上；
3. 如果 Alice 的卡牌击败了 Bob 的卡牌，则两张卡牌都由 Alice 收取。否则，两张卡牌都由 Bob 收取。

玩家可以使用他们在之前回合中收取的卡牌。

在回合开始时没有卡牌的玩家输掉游戏。假设双方都采取最优策略，判断谁会获胜。

输入

第一行包含一个整数 $t$ ($1 \le t \le 5000$) —— 测试用例的数量。

每个测试用例包含两行：

• 第一行包含一个整数 $n$ ($2 \le n \le 50$) —— 卡牌的数量；
• 第二行包含 $n$ 个字符，每个字符是 A 或 B。如果第 $i$ 个字符是 A，则编号为 $i$ 的卡牌最初发给 Alice；否则，它发给 Bob。

输入的附加约束：在每个测试用例中，至少有一张卡牌最初发给 Alice，并且至少有一张卡牌最初发给 Bob。

输出

对于每个测试用例，如果 Alice 在最优策略下获胜，则输出 Alice；如果 Bob 获胜，则输出 Bob。可以证明，如果双方都采取最优策略，游戏必定会在有限回合内结束，并且有一方获胜。

测试用例

输入

8
2
AB
2
BA
4
ABAB
4
BABA
3
BAA
5
AAAAB
5
BAAAB
6
BBBAAA

输出

Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice

注意

在第一个测试用例中，Alice 只有一张卡牌，Bob 也只有一张卡牌。由于 Alice 的卡牌击败了 Bob 的卡牌，她在第一回合后获胜。

在第二个测试用例中，Alice 只有一张卡牌，Bob 也只有一张卡牌。由于 Bob 的卡牌击败了 Alice 的卡牌，他在第一回合后获胜。

在第三个测试用例中，有两种可能的游戏场景：

• 如果 Alice 在第一回合打出卡牌 $1$，Bob 可以用卡牌 $2$ 回应并收取两张卡牌。然后，Alice 必须在第二回合打出卡牌 $3$，而 Bob 将用卡牌 $4$ 回应。于是，他获胜；
• 如果 Alice 在第一回合打出卡牌 $3$，Bob 可以用卡牌 $4$ 回应并收取两张卡牌。然后，Alice 必须打出卡牌 $1$，而 Bob 可以用卡牌 $2$ 或卡牌 $3$ 回应。于是，他获胜。

在第四个测试用例中，有两种可能的游戏场景：

• 如果 Alice 在第一回合打出卡牌 $2$，Bob 可以用卡牌 $3$ 回应并收取两张卡牌。然后，Alice 必须在第二回合打出卡牌 $4$，而 Bob 将用卡牌 $1$ 回应。于是，他获胜；
• 如果 Alice 在第一回合打出卡牌 $4$，Bob 可以用卡牌 $1$ 回应并收取两张卡牌。然后，Alice 必须打出卡牌 $2$，而 Bob 可以用卡牌 $3$ 或卡牌 $4$ 回应。于是，他获胜。

2094D 咚咚萨胡尔

来源：Codeforces Round 1017 (Div. 4)-D. Tung Tung Sahur

Tags: 贪心 字符串 双指针

你面前有两个鼓：一个左鼓和一个右鼓。敲击左鼓可以记录为 "L"，敲击右鼓可以记录为 "R"。

统治这个世界的神秘力量变幻莫测：有时，一次敲击只发出一声响，有时却发出两声响。因此，敲击左鼓可能听起来是 "L" 或 "LL"，敲击右鼓可能听起来是 "R" 或 "RR"。

敲击的序列记录在字符串 $p$ 中，而听到的声音记录在字符串 $s$ 中。给定 $p$ 和 $s$，判断字符串 $s$ 是否可能是由字符串 $p$ 所记录的敲击产生的结果。

例如，如果 $p=$"LR"，那么敲击的结果可能是字符串 "LR"、"LRR"、"LLR" 和 "LLRR" 中的任何一个，但字符串 "LLLR" 或 "LRL" 则不可能。

输入

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

每个测试用例的第一行包含字符串 $p$ ($1 \le |p| \le 2 \cdot 10^5$)，该字符串仅由字符 "R" 和 "L" 组成，其中 $|p|$ 表示字符串 $p$ 的长度。

每个测试用例的第二行包含字符串 $s$ ($1 \le |p| \le |s| \le 2 \cdot 10^5$)，该字符串仅由字符 "R" 和 "L" 组成。

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

输出

对于每组输入数据，如果 $s$ 可能是听到的声音，则输出 "YES"，否则输出 "NO"。你可以以任意大小写输出。

测试用例

输入

5
R
RR
LRLR
LRLR
LR
LLLR
LLLLLRL
LLLLRRLL
LLRLRLRRL
LLLRLRRLLRRRL

输出

YES
YES
NO
NO
YES

2032B 中位数

来源：Codeforces Round 983 (Div. 2)-B. Medians

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

给定一个数组 $a = [1, 2, \ldots, n]$，其中 $n$ 是奇数，以及一个整数 $k$。

你的任务是选择一个奇数正整数 $m$，并将 $a$ 分割成 $m$ 个子数组$^{\dagger}$ $b_1, b_2, \ldots, b_m$，使得：

• 数组 $a$ 的每个元素恰好属于一个子数组。
• 对于所有 $1 \le i \le m$，$|b_i|$ 是奇数，即每个子数组的长度是奇数。
• $\operatorname{median}([\operatorname{median}(b_1), \operatorname{median}(b_2), \ldots, \operatorname{median}(b_m)]) = k$，即所有子数组中位数组成的数组的中位数$^{\ddagger}$ 必须等于 $k$。$\operatorname{median}(c)$ 表示数组 $c$ 的中位数。

$^{\dagger}$ 长度为 $n$ 的数组 $a$ 的一个子数组是指对于某些满足 $1 \le l \le r \le n$ 的整数，形如 $[a_l, a_{l + 1}, \ldots, a_r]$ 的数组。

$^{\ddagger}$ 一个奇数长度数组的中位数是指将数组按非递减顺序排序后位于中间的元素。例如：$\operatorname{median}([1,2,5,4,3]) = 3$，$\operatorname{median}([3,2,1]) = 2$，$\operatorname{median}([2,1,2,1,2,2,2]) = 2$。

输入

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

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n < 2 \cdot 10^5$, $n$ 是奇数) —— 分别是数组 $a$ 的长度和所有子数组中位数组成的数组的期望中位数。

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

输出

对于每个测试用例：

• 如果没有合适的分割方法，则在一行中输出 $-1$。
• 否则，在第一行输出一个奇数整数 $m$ ($1 \le m \le n$)，在第二行输出 $m$ 个不同的整数 $p_1, p_2 , p_3 , \ldots, p_m$ ($1 = p_1 < p_2 < p_3 < \ldots < p_m \le n$) —— 表示每个子数组的左边界。

详细来说，对于一个有效的答案 $[p_1, p_2, \ldots, p_m]$：

• $b_1 = \left[ a_{p_1}, a_{p_1 + 1}, \ldots, a_{p_2 - 1} \right]$
• $b_2 = \left[ a_{p_2}, a_{p_2 + 1}, \ldots, a_{p_3 - 1} \right]$
• $\ldots$
• $b_m = \left[ a_{p_m}, a_{p_m + 1}, \ldots, a_n \right]$.

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

测试用例

输入

4
1 1
3 2
3 3
15 8

输出

1
1
3
1 2 3
-1
5
1 4 7 10 13

注意

在第一个测试用例中，给定的分割有 $m = 1$ 且 $b_1 = [1]$。显然，$\operatorname{median}([\operatorname{median}([1])]) = \operatorname{median}([1]) = 1$。

在第二个测试用例中，给定的分割有 $m = 3$ 且：

• $b_1 = [1]$
• $b_2 = [2]$
• $b_3 = [3]$

因此，$\operatorname{median}([\operatorname{median}([1]), \operatorname{median}([2]), \operatorname{median}([3])]) = \operatorname{median}([1, 2, 3]) = 2$。

在第三个测试用例中，对于 $k = 3$ 没有有效的分割方法。

在第四个测试用例中，给定的分割有 $m = 5$ 且：

• $b_1 = [1, 2, 3]$
• $b_2 = [4, 5, 6]$
• $b_3 = [7, 8, 9]$
• $b_4 = [10, 11, 12]$
• $b_5 = [13, 14, 15]$

因此，$\operatorname{median}([\operatorname{median}([1, 2, 3]), \operatorname{median}([4, 5, 6]), \operatorname{median}([7, 8, 9]), \operatorname{median}([10, 11, 12]), \operatorname{median}([13, 14, 15])]) = \operatorname{median}([2, 5, 8, 11, 14]) = 8$。

2030C 真正的对决

来源：Codeforces Round 979 (Div. 2)-C. A TRUE Battle

Tags: 暴力破解 游戏 贪心

Alice 和 Bob 正在玩一个游戏。有一个包含 $n$ 个布尔值的列表，每个布尔值要么为真要么为假，以一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ 给出（其中 $\texttt{1}$ 代表真，$\texttt{0}$ 代表假）。最初，这些布尔值之间没有运算符。

Alice 和 Bob 将轮流在布尔值之间放置 and 或 or 运算符，Alice 先手。因此，由于有 $n$ 个布尔值，游戏将进行 $n-1$ 轮。Alice 的目标是让最终的语句计算结果为真，而 Bob 的目标是让它为假。给定布尔值列表，判断如果双方都采取最优策略，Alice 是否会获胜。

为了计算最终表达式的结果，重复执行以下步骤，直到语句只剩下一个真或假值：

• 如果语句中包含 and 运算符，则任意选择一个，并用其计算后的结果替换其周围的子表达式。
• 否则，语句中包含 or 运算符。任意选择一个，并用其计算后的结果替换其周围的子表达式。

例如，表达式 true or false and false 的计算过程为 true or (false and false) $=$ true or false $=$ true。可以证明任何复合语句的结果都是唯一的。

$^{\text{∗}}$ 二进制字符串是指仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成的字符串。

输入

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

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

第二行包含一个长度为 $n$ 的二进制字符串，由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成 —— 表示布尔值列表。

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

输出

对于每个测试用例，如果 Alice 获胜，则输出 "YES"（不带引号），否则输出 "NO"（不带引号）。

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

测试用例

输入

5
2
11
3
010
12
101111111100
10
0111111011
8
01000010

输出

YES
NO
YES
YES
NO

注意

在第一个测试用例中，Alice 可以在两个布尔值之间放置 and。由于没有其他位置可以放置运算符，游戏结束，Alice 获胜，因为 true and true 的结果是 true。

在第二个测试用例中，Alice 可以在中间的 true 和左边的 false 之间放置 or。Bob 可以在中间的 true 和右边的 false 之间放置 and。语句 false or true and false 的结果是 false。

请注意，这些示例可能不是 Alice 或 Bob 的最佳策略。

2029B 替换

来源：Refact.ai Match 1 (Codeforces Round 985)-B. Replacement

Tags: 构造算法 游戏 字符串

你有一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$，Iris 给了你另一个长度为 $n-1$ 的二进制字符串 $r$。

Iris 将和你玩一个游戏。在游戏中，你将对 $s$ 执行 $n-1$ 次操作。在第 $i$ 次操作中 ($1 \le i \le n-1$)：

• 首先，你选择一个索引 $k$，满足 $1\le k\le |s| - 1$ 且 $s_{k} \neq s_{k+1}$。如果无法选择这样的索引，你就输了；
• 然后，你将 $s_ks_{k+1}$ 替换为 $r_i$。注意，这会使 $s$ 的长度减少 $1$。

如果所有 $n-1$ 次操作都成功执行，你就赢了。

判断你是否有可能赢得这个游戏。

$^{\text{∗}}$ 二进制字符串是指每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

输入

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

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

第二行包含长度为 $n$ 的二进制字符串 $s$ ($s_i=\mathtt{0}$ 或 $\mathtt{1}$)。

第三行包含长度为 $n-1$ 的二进制字符串 $r$ ($r_i=\mathtt{0}$ 或 $\mathtt{1}$)。

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

输出

对于每个测试用例，如果你能赢得游戏，则打印 "YES"（不带引号），否则打印 "NO"（不带引号）。

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

测试用例

输入

6
2
11
0
2
01
1
4
1101
001
6
111110
10000
6
010010
11010
8
10010010
0010010

输出

NO
YES
YES
NO
YES
NO

注意

在第一个测试用例中，你无法执行第一个操作。因此，你输了游戏。

在第二个测试用例中，你可以在唯一的操作中选择 $k=1$，之后 $s$ 变为 $\mathtt{1}$。因此，你赢了游戏。

在第三个测试用例中，你可以执行以下操作：$\mathtt{1}\underline{\mathtt{10}}\mathtt{1}\xrightarrow{r_1=\mathtt{0}} \mathtt{1}\underline{\mathtt{01}} \xrightarrow{r_2=\mathtt{0}} \underline{\mathtt{10}} \xrightarrow{r_3=\mathtt{1}} \mathtt{1}$。

1997C 偶数位置

来源：Educational Codeforces Round 168 (Rated for Div. 2)-C. Even Positions

Tags: 构造算法 数据结构 贪心

Monocarp 有一个长度为 $n$（$n$ 为偶数）的正则括号序列 $s$。他甚至想出了自己计算其代价的方法。

他知道在正则括号序列（RBS）中，每个开括号都与对应的闭括号配对。因此，他决定将 RBS 的代价计算为所有对应括号对之间距离的总和。

例如，我们来看 RBS (()())。它有三对括号：

• (__)__：位置 $1$ 和 $4$ 的括号之间的距离为 $4 - 1 = 3$；
• _()___：距离为 $3 - 2 = 1$；
• ____()：距离为 $6 - 5 = 1$。

因此 (()()) 的代价是 $3 + 1 + 1 = 5$。

不幸的是，由于数据损坏，Monocarp 丢失了所有奇数位置 $s_1, s_3, \dots, s_{n-1}$ 上的字符。只有偶数位置（$s_2, s_4, \dots, s_{n}$）的字符保留了下来。例如，(()()) 变成了 _(_)_)。

Monocarp 希望通过在奇数位置放置括号来恢复他的 RBS。但由于恢复的 RBS 可能不唯一，他想要选择代价最小的一个。这对 Monocarp 一个人来说太难了，你能帮助他吗？

提醒：正则括号序列是一个仅由括号组成的字符串，使得该序列在插入数字 1 和加号 + 后能构成一个合法的数学表达式。例如，()、(()) 或 (()())() 是 RBS，而 )、()( 或 ())(() 不是。

输入

第一行包含一个整数 $t$ ($1 \le t \le 5000$) —— 测试用例的数量。接下来是 $t$ 个测试用例。

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

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，其中所有奇数位置的字符都是 '_'，所有偶数位置的字符都是 '(' 或 ')'。

附加约束：

• $s$ 可以恢复为至少一个正则括号序列；
• 所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数 —— 通过将 $s$ 中的 '_' 替换为括号所能得到的最小代价。

测试用例

输入

4
6
_(_)_)
2
_)
8
_)_)_)_)
8
_(_)_(_)

输出

5
1
4
8

注意

在第一个测试用例中，最优方案是使 $s$ 等于 (()())。$s$ 的代价将等于 $3 + 1 + 1 = 5$。

在第二个测试用例中，唯一的选择是使 $s$ 等于 ()，代价为 $1$。

在第三个测试用例中，唯一可能的 RBS 是 ()()()()，代价为 $1 + 1 + 1 + 1 = 4$。

在第四个测试用例中，最优方案是使 $s$ 等于 (())(())，代价为 $3 + 1 + 3 + 1 = 8$。

1994B 趣味游戏

来源：Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)-B. Fun Game

Tags: 位掩码 构造算法 贪心 数学

Vova 非常喜欢 异或（XOR） 操作（记为 $\oplus$）。最近，在他准备睡觉时，他想出了一个有趣的游戏。

在游戏开始时，Vova 选择两个长度为 $n$ 的二进制序列 $s$ 和 $t$，并将它们交给 Vanya。二进制序列是指仅由数字 $0$ 和 $1$ 组成的序列。Vanya 可以选择整数 $l, r$，满足 $1 \leq l \leq r \leq n$，并对于所有 $l \leq i \leq r$ 同时 将 $s_i$ 替换为 $s_i \oplus s_{i - l + 1}$，其中 $s_i$ 是序列 $s$ 的第 $i$ 个元素。

为了使游戏有趣，必须存在获胜的可能性。如果 Vanya 能够通过无限次操作从序列 $s$ 得到序列 $t$，则他获胜。请判断对于序列 $s$ 和 $t$ 来说，这个游戏是否会是有趣的。

输入

每个测试包含多个测试用例。第一行包含一个整数 $q$ ($1 \le q \le 10^{4}$) —— 测试用例的数量。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) —— 序列 $s$ 和 $t$ 的长度。

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

每个测试用例的第三行包含一个长度为 $n$ 的二进制序列 $t$。

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

输出

对于每个测试用例，如果游戏会是有趣的，则输出 "Yes"，否则输出 "No"。

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

测试用例

输入

6
1
0
1
7
0110100
0110100
9
100101010
101111110
4
0011
1011
4
0100
0001
8
10110111
01100000

输出

NO
YES
YES
NO
YES
YES

注意

在第一个测试用例中，Vanya 无法改变序列 $s$，因为唯一可能的操作是选择 $l = r = 1$。

在第二个测试用例中，序列 $s$ 和 $t$ 已经相等。

在第三个测试用例中，Vanya 可以按如下方式操作：

1. 选择 $l = 3$ 和 $r = 5$，然后 $s$ 将变为 $\mathtt{101101010}$。
2. 选择 $l = 5$ 和 $r = 6$，然后 $s$ 将变为 $\mathtt{101111010}$。
3. 选择 $l = 7$ 和 $r = 7$，然后 $s$ 将变为 $\mathtt{101111110}$。

1993B 奇偶性与和

来源：Codeforces Round 963 (Div. 2)-B. Parity and Sum

Tags: 构造算法 贪心

给定一个包含 $n$ 个正整数的数组 $a$。

在一次操作中，你可以选择任意一对索引 $(i, j)$，使得 $a_i$ 和 $a_j$ 具有不同的奇偶性，然后将较小的那个数替换为它们的和。更正式地说：

• 如果 $a_i < a_j$，则将 $a_i$ 替换为 $a_i + a_j$；
• 否则，将 $a_j$ 替换为 $a_i + a_j$。

找出使数组中所有元素具有相同奇偶性所需的最少操作次数。

输入

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

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

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

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

输出

对于每个测试用例，输出一个整数 —— 所需的最少操作次数。

测试用例

输入

7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000

输出

0
0
2
4
3
3
3

注意

在第一个测试用例中，所有整数已经具有相同的奇偶性。因此，不需要任何操作。

在第三个测试用例中，我们可以执行两次操作 $(1, 2)$ 和 $(1, 3)$。数组 $a$ 的变化如下：$a = [{\color{red}2}, {\color{red}3}, 4] \longrightarrow [{\color{red}5}, 3, {\color{red}4}] \longrightarrow [5, 3, 9]$。

在第四个测试用例中，一个最优操作序列的例子是 $(1, 2)$、$(1, 3)$、$(1, 4)$ 和 $(1, 4)$。数组 $a$ 的变化如下：$a = [{\color{red}3}, {\color{red}2}, 2, 8] \longrightarrow [{\color{red}3}, 5, {\color{red}2}, 8] \longrightarrow [{\color{red}}3, 5, 5, {\color{red}8}] \longrightarrow [{\color{red}{11}}, 5, 5, {\color{red}8}] \longrightarrow [11, 5, 5, 19]$。

1986C 更新查询

来源：Codeforces Round 954 (Div. 3)-C. Update Queries

Tags: 数据结构 贪心 排序

考虑以下简单问题。给定一个长度为 $n$、由小写拉丁字母组成的字符串 $s$，一个长度为 $m$ 的索引数组 $ind$（$1 \leq ind_i \leq n$），以及一个长度为 $m$、由小写拉丁字母组成的字符串 $c$。然后，你按顺序执行更新操作，即在第 $i$ 次操作中，你将 $s_{ind_i}$ 设置为 $c_i$。注意，你需要从第一个到最后一个执行所有 $m$ 次操作。

当然，如果你改变数组 $ind$ 中索引的顺序和/或字符串 $c$ 中字母的顺序，你可以得到不同的结果。找出在 $m$ 次更新操作后可以得到的字典序最小的字符串 $s$，前提是你可以任意重新排列数组 $ind$ 中的索引和字符串 $c$ 中的字母。

字符串 $a$ 字典序小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的前缀，但 $a \neq b$；
• 在 $a$ 和 $b$ 第一个不同的位置上，字符串 $a$ 中的字符在字母表中比字符串 $b$ 中的对应字符靠前。

输入

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

每组输入数据的第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 10^5$) —— 分别是字符串 $s$ 的长度和更新的次数。

每组输入数据的第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

每组输入数据的第三行包含 $m$ 个整数 $ind_1, ind_2, \ldots, ind_m$ ($1 \leq ind_i \leq n$) —— 索引数组 $ind$。

每组输入数据的第四行包含一个长度为 $m$ 的字符串 $c$，由小写拉丁字母组成。

保证所有输入数据的 $n$ 的总和不超过 $2 \cdot 10^5$。同样，所有输入数据的 $m$ 的总和也不超过 $2 \cdot 10^5$。

输出

对于每组输入数据，输出在可以任意重新排列数组 $ind$ 中的索引和字符串 $c$ 中的字母的情况下，经过 $m$ 次更新操作后可以得到的字典序最小的字符串 $s$。

测试用例

输入

4
1 2
a
1 1
cb
4 4
meow
1 2 1 4
zcwz
7 4
abacaba
1 3 5 7
damn
7 10
traktor
7 6 5 4 3 2 1 6 4 2
codeforces

输出

b
cwoz
abdcmegabytesn
ccdeefo

注意

在第一组输入数据中，你可以保持数组 $ind$ 和字符串 $c$ 不变，并简单地按该顺序执行所有操作。

在第二组输入数据中，你可以设置数组 $ind = [1, 1, 4, 2]$ 和 $c =$ "zczw"。那么字符串 $s$ 将按如下方式变化：$meow \rightarrow zeow \rightarrow ceow \rightarrow ceoz \rightarrow cwoz$。

在第三组输入数据中，你可以保持数组 $ind$ 不变，并设置 $c =$ "admn"。那么字符串 $s$ 将按如下方式变化：$abacaba \rightarrow abacaba \rightarrow abdcaba \rightarrow abdcmegabytesa \rightarrow abdcmegabytesn$。

1976B 增加/减少/复制

来源：Educational Codeforces Round 166 (Rated for Div. 2)-B. Increase/Decrease/Copy

Tags: 贪心 实现

给定两个整数数组：长度为 $n$ 的数组 $a$ 和长度为 $n+1$ 的数组 $b$。

你可以按任意顺序多次执行以下操作：

• 选择数组 $a$ 中的任意元素并将其增加 $1$；
• 选择数组 $a$ 中的任意元素并将其减少 $1$；
• 选择数组 $a$ 中的任意元素，复制它并将副本附加到数组 $a$ 的末尾。

你的任务是计算将数组 $a$ 转换为数组 $b$ 所需的最少操作次数（可能为零）。可以证明，在问题的约束下，这总是可行的。

输入

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

每个测试用例包含三行：

• 第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)；
• 第三行包含 $n + 1$ 个整数 $b_1, b_2, \dots, b_{n + 1}$ ($1 \le b_i \le 10^9$)。

输入的附加约束：所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数 —— 将数组 $a$ 转换为数组 $b$ 所需的最少操作次数（可能为零）。

测试用例

输入

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

输出

3
1
8

注意

在第一个例子中，你可以按以下方式将 $a$ 转换为 $b$：$[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]$。