分数: 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).
对于第二个测试用例,可以通过执行零次操作来实现目标。