题解：P10191 [USACO24FEB] Test Tubes S
zcq_qwq
·
·
题解
说在前面
码农题目，思路是简单的，就是有点废手。
在只能交 3 次的且只有 2.5h 时间的考场上我居然过了大模拟题目，我太强了。
前置芝士：贪心、一个清醒的大脑、一对敏锐的眼睛和十根勤劳的手指大模拟。
注意：
- 该文章篇幅较长，给出了详细的证明和算法步骤，可自行选择观看。
- 题目是有问题的，“输入保证两个字符串均包含至少一个 1 和一个 2”，而样例三与题目描述矛盾。题目一开始提到的“输入保证两种颜色的液体至少各有一个单位”符合样例三，故我认为，第一句话应该把“均”字改成“总共”。
- 该题解中所有的思路的构建与证明都基于“输入保证两种颜色的液体至少各有一个单位”这句话之上，请务必牢记在心。
题目分析
思路是比较好想的。
:::info[思路]{open}
建立在贪心之上，我们尽可能多合并能合并的颜色。
- 指定一个烧杯中唯一可能出现的颜色，令其为 x。
- 分别查看两个试管，如果最顶层存在 x，将其倒入烧杯，每次倾倒花费代价 1。
- 否则，将颜色多的试管的顶层倒入另一个试管中，花费代价 1。
- 在两个试管内的颜色的段数至少有一个大于 1 的情况下，重复步骤 2、3，否则，分类讨论：
- 如果烧杯是空的，直接退出，此时必定分拣完成。
- 否则，讨论两试管液体存在性及颜色。
- 若试管 1 和试管 2 均为非空。
- 若两试管内颜色相同，则将试管 1 的液体倒入试管 2，最后将试管 3 的倒入试管 1，花费代价 2。
- 否则，检查哪个试管的剩下的颜色为 x，将烧杯中的颜色倒入该试管，花费代价 1。
- 若仅有试管 1 非空。
- 若仅有试管 2 非空。
- 将 x 换一个数，重复上述过程，答案取两次代价的最小值。
:::
由于这个算法是我们凭直觉搞出来的，所以这里给出证明。
:::info[算法思路的证明]{open}
先证总体思路：
- 引理 1：一次操作最多合并两段颜色成一段。
- 证明：一次操作只能将一个试管（烧杯）中的液体的某一个段倒入另一个试管（烧杯），故最多只能合并两段颜色成为一段。
- 引理 2：我们需要尽可能地多合并相同的颜色。
- 证明：考虑终止态一定是两个试管内分别有一段颜色且两烧杯内颜色段数不同，总段数为 2，从题目描述得初始态段数一定不小于 2，由引理 1，颜色段数单调不增，因此为了加速该过程，我们需要尽可能合并。
故总体思路正确。
再证退出循环前的思路：
- 引理 3：步骤 3 能减少颜色段数并且保证了一定能到达步骤 4。
- 证明：此时两试管顶部的颜色一定与 x 不同且两试管顶部颜色相同。采用反证法，将数量小的倒入数量大的，考虑以下情况：x = 1，试管一内部：[2，试管二内部：[21212。一次操作后，试管一：[，试管二：[2121。两次操作后，试管一：[，试管二：[212。此时理应进行操作 3，由于试管一为空，无法进行，因此条件永远无法达成，循环永远无法退出。而如果数量大的倒入数量小的，就能在减少颜色段数的同时避免该情况。
- 引理 4：操作过程中至多有一次不减少颜色段数。
- 证明：在操作时，如果是第一次将 x 放入烧杯，那么颜色段数不会减少，否则如果是放入烧杯的操作，那么颜色段必然减少 1。如果是两试管相互倒液体的操作，由引理 3，颜色段也会减少 1。
- 引理 5：最优方案严格满足引理 4。
- 证明：在倾倒过程中，可能会存在两试管顶部异色的情况，此时如果不放入烧杯中，一定无法再次减少颜色段数，违背了引理 2，因此只能将这一段放入烧杯，如果这是第一次此类操作，那么颜色段不变，结合引理 4，最多只有一次操作不影响颜色段数量，因而最优。
- 引理 6：满足两个烧杯中的颜色段数全部小于等于 1 的情况后退出是最优的。
- 证明：在满足该情况前，至少有一个烧杯存在大于 1 个连续段，所以最少还要进行一次操作 2 或操作 3。
故退出循环前的思路正确。
最后证明退出循环后的思路。
- 引理 7：若烧杯为空可以直接终止操作。
- 证明：有题目描述至少存在两种颜色，那么只有一个试管非空或两个试管均为空的情况将不可能存在；若两个试管均非空，则一定不是同种颜色，自动达成终止态，直接退出。
- 引理 8：若烧杯非空最多进行两次操作且最优。
- 证明：对于仅有一个试管非空的情况，此时试管内颜色一定不为 x，直接将烧杯中的液体倒入另一试管，达成终止态，花费代价 1；若两个试管非空，如果颜色相同，一定不能从烧杯直接倒，因此先合并两个试管内的液体，再从烧杯直接倒，花费代价 2；若两个试管颜色不同，可以直接合并烧杯和一个试管，花费代价 1。同时，不可能存在两个试管同时为空的情况。在引理 6的条件下，这一步一定最优。
故退出循环后的思路正确。
综上，该算法思路全部正确。
:::
:::warning[注意事项]
1. $P = 1$ 只能输出一个数字即最小代价。
2. 类似于样例 $3$ 的情况代码无法处理，需要特殊判断。
:::
:::success[AC 代码]
~~长达 3.71KB 的代码。~~
```cpp
#include <bits/stdc++.h>
#define PII pair<int, int>
#define fir first
#define sec second
using namespace std;
namespace zcq_qwq {
const int N = 1e5 + 5, inf = 0x3f3f3f3f;
int t, n, mn = inf, res[3];
deque<PII> q[4], p[4];
vector<PII> ans[3];
void merge(int x, PII v) { // 把 v 这个东西放到 q[x] 里面
if (q[x].empty()) q[x].push_back(v);
else if (q[x].back().fir == v.fir) q[x].back().sec += v.sec;
else q[x].push_back(v);
}
bool check() {return q[1].size() <= 1 && q[2].size() <= 1;}
void clear() {for (int i = 1; i <= 3; i++) q[i].clear(); ans[1].clear(), ans[2].clear(), res[1] = res[2] = 0;}
void big_question(int x) { // 确定 q[3] 里面存的是啥颜色
for (int i = 1; i <= 3; i++) {p[i] = q[i];}
int sum = 0;
while (!check()) {
if (!q[1].empty() && q[1].back().fir == x) {
merge(3, q[1].back()), q[1].pop_back(), sum++;
ans[x].push_back({1, 3});
} else if (!q[2].empty() && q[2].back().fir == x) {
merge(3, q[2].back()), q[2].pop_back(), sum++;
ans[x].push_back({2, 3});
} else {
int tmp = max(q[1].size(), q[2].size());
if (tmp == q[1].size()) {
merge(2, q[1].back()), q[1].pop_back(), sum++;
ans[x].push_back({1, 2});
} else {
merge(1, q[2].back()), q[2].pop_back(), sum++;
ans[x].push_back({2, 1});
}
}
}
// 接下来是大分讨
if (!q[1].empty() && !q[2].empty() && !q[3].empty()) {
if (q[1].back().fir == q[2].back().fir) {
ans[x].push_back({1, 2}), ans[x].push_back({3, 1}), sum += 2;
} else {
if (q[1].back().fir == x) {
ans[x].push_back({3, 1}), sum++;
} else {
ans[x].push_back({3, 2}), sum++;
}
}
} else if (!q[1].empty() && !q[3].empty()) {
ans[x].push_back({3, 2}), sum++;
} else if (!q[2].empty() && !q[3].empty()) {
ans[x].push_back({3, 1}), sum++;
}
res[x] = sum;
mn = min(mn, sum);
for (int i = 1; i <= 3; i++) {q[i] = p[i];}
}
void solve() {
mn = inf;
clear();
int P;
cin >> n >> P;
for (int i = 1; i <= n; i++) {
char c; int x;
cin >> c; x = c - '0';
PII t = {x, 1};
merge(1, t);
}
for (int i = 1; i <= n; i++) {
char c; int x;
cin >> c; x = c - '0';
PII t = {x, 1};
merge(2, t);
}
if (q[1].size() == 1 && q[2].size() == 2) {
if (q[1].back().fir == q[2].back().fir) {
cout << "1\n2 1" << endl;
return;
}
} else if (q[1].size() == 2 && q[2].size() == 1) {
if (q[1].back().fir == q[2].back().fir) {
cout << "1\n1 2" << endl;
return;
}
}
big_question(1), big_question(2);
cout << mn << endl;
if (P == 1) return;
if (mn == res[1]) {
for (auto i : ans[1]) cout << i.fir << " " << i.sec << endl;
} else {
for (auto i : ans[2]) cout << i.fir << " " << i.sec << endl;
}
}
void main() {
cin >> t;
while (t--) {
solve();
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
zcq_qwq::main();
return 0;
}
/*
这个东西显然是策略的问题，只要策略对了即可
看起来是这样的策略：每次遇到指定颜色段，就放到烧杯里，这样烧杯里面一定是一种颜色的。
最后再把烧杯里面的倒回来
由于我们指定的哪一个颜色放到烧杯里面可能对答案有影响，所以我们跑两次取最小值。
接下来只需要思考如何判断可以直接倒了。
如果两边烧杯的段数同时 <= 1，就可以直接倒。
*/
```
:::
## 说在后面
若代码、思路讲解有误，欢迎提出！