← 返回题目列表

AtCoder · agc076_b

B. 分割和反转

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

给你一个整数序列 X=(X_1,X_2,\cdots,X_N) 长度 N 组成 0 和 1.

您可以执行以下操作零次或多次:

  • 对每个元素进行分类 X 进组 A 或群组 B。 然后,对于每个组,反转其包含的元素的顺序。 更正式地说,如果一个组中包含的元素是 X_{i_1},X_{i_2},\cdots,X_{i_s} (i_1<i_2<\cdots<i_s),那么对于所有 1 \leq j \leq s,同时替换 X_{i_j} 与 X_{i_{s+1-j}}.

你的目标是 X 非减少。 找出实现目标所需的最少操作数以及执行操作的方式。 可以证明,在该问题的约束下,总存在解。

解决 T 一个输入的情况。

约束

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 0 \leq X_i \leq 1
  • 总和 N 超过 T 例最多 250000.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个测试用例均按以下格式给出:

N
X_1 X_2 \cdots X_N

输出

对于每种情况,按以下格式输出:

k
s_1
s_2
\vdots
s_k

在这里, k 是所需的最少操作数,并且 s_i 是一个字符串,表示 i-第次操作。 s_i 是一个长度为的字符串 N 组成 A 和 B,以及 j- 第一个字符 s_i 代表所属组 X_j 被分配在 i第次操作。 如果有多个解决方案,您可以输出其中任何一个。


示例输入 1

2
4
0 1 0 1
5
0 0 1 1 1

示例输出 1

2
AABA
BBBB
0

对于第一个测试用例,可以通过如下两个操作来实现目标,这是最少的操作数:

  • 第一次操作:使用 s_1=AABA。自从 (X_1,X_2,X_4) 在组中 A,颠倒它们的顺序,导致 (X_1,X_2,X_4)=(1,1,0)。 同样,由于 (X_3) 已在群组中 B,颠倒它们的顺序,导致 (X_3)=(0)。 因此,总体上我们得到 X=(1,1,0,0).

  • 第二次操作:使用 s_2=BBBB。自从 () 在组中 A,颠倒它们的顺序,导致 ()=()。 同样,由于 (X_1,X_2,X_3,X_4) 在组中 B,颠倒它们的顺序,导致 (X_1,X_2,X_3,X_4)=(0,0,1,1)。 因此,总体上我们得到 X=(0,0,1,1).

对于第二个测试用例,可以通过执行零次操作来实现目标。