Test Tubes

题目描述

Bessie 最近开始学习化学。目前，她有两种不同颜色 $1$ 和 $2$ 的液体，它们彼此不能很好地混合。 她有两支容量无限的试管，每支试管中都装有 $N$（$1 \leq N \leq 10^5$）单位的这两种颜色液体的某种混合物。由于这些液体不会混合，它们静置后会分成不同颜色的分层。 因此，这两支试管可以看作字符串 $f_1f_2\ldots f_N$ 和 $s_1s_2\ldots s_N$，其中 $f_i$ 表示第一支试管中距离底部 $i$ 个单位处的液体颜色，$s_i$ 表示第二支试管中距离底部 $i$ 个单位处的液体颜色。保证至少有一个单位的每种颜色液体。 Bessie 想将这些液体分离，使得每支试管只包含一种颜色的所有单位液体。她有第三个容量无限的空烧杯来帮助完成任务。 当 Bessie 进行一次“倒液”（pour）时，她会把某个试管或烧杯顶部所有颜色为 $i$ 的液体一次性倒入另一个容器中。 请确定将所有液体分离到两支试管中的最少倒液次数，以及完成分离所需的一系列操作。最终哪支试管装哪种颜色都无所谓，但烧杯必须为空。 共有 $T$（$1 \leq T \leq 10$）个测试用例，每个测试用例带有一个参数 $P$。 设将液体分离并最终回到原来的两支试管所需的最少倒液次数为 $M$。 如果 $P=1$，只输出 $M$ 也可得分。 如果 $P=2$，输出一个整数 $A$，满足 $M \leq A \leq M+5$，并接着输出 $A$ 行，构造一个用 $A$ 次操作完成的解。每行包含来源容器与目标容器（$1$、$2$，或 $3$ 表示烧杯）。在操作前来源容器必须非空，且不允许把液体倒入自身。 如果 $P=3$，输出 $M$，并接着输出一个恰好用 $M$ 次操作的合法构造。

输入格式

第一行包含 $T$，表示测试用例数量。对于每个测试用例： 下一行包含 $N$ 和 $P$，表示每支试管初始装到的单位数，以及查询类型。 接下来一行包含 $f_1f_2f_3\ldots f_N$，表示第一支试管。$f_i \in \{ 1,2 \}$，且 $f_1$ 表示试管底部。 随后一行包含 $s_1s_2s_3\ldots s_N$，表示第二支试管。$s_i \in \{ 1,2 \}$，且 $s_1$ 表示试管底部。 保证两条输入字符串整体中至少出现一个 $1$ 和一个 $2$。

输出格式

对于每个测试用例，输出一个数表示将试管中的液体分离所需的最少倒液次数。根据查询类型，你可能还需要输出一个合法的操作构造。

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

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

提示

在前三个测试用例中，将试管分离所需的最少倒液次数是 $4$。我们可以看到如下操作如何分离试管： 初始状态： 1: 1221 2: 2211 3: 执行操作 "1 2" 后： 1: 122 2: 22111 3: 执行操作 "1 3" 后： 1: 1 2: 22111 3: 22 执行操作 "2 1" 后： 1: 1111 2: 22 3: 22 执行操作 "3 2" 后： 1: 1111 2: 2222 3: 在最后一个测试用例中，最少倒液次数是 $5$。但是由于 $P=2$，给出的 $6$ 步构造也是有效的，因为它距离最优答案不超过 $5$ 次倒液。 评分（SCORING）： 输入 2-6：$P = 1$ 输入 7-11：$P=2$ 输入 12-21：无额外限制。 另外，除样例外，保证所有输入的 $T=10$。 题目署名：Suhas Nagar

标签: USACO|2024|Silver

来源

USACO|2024|Silver