Test Tubes (USACO Silver 2024 February)
两个试管和一个烧杯之间倒液体，试管容量，烧杯没有容量限制。怎样把两种分层的液体彻底分开到两个试管中。
首先，相邻的同色液体可以合并，不影响结果，所以试管内容规一化成相间的1,2的串。
然后我们发现并没有特别清晰的思路，但是比较容易想到有一系列直观的操作可以试，那我们就大胆通过实验来尝试吧。我们反复使用以下四个策略：
- 如果两个试管中顶部液体相同，那先合并这两个相同液体到高度低的试管中。
- 如果有一个试管是空的，而且另一个试管顶部液体不是烧杯中的液体，那把另一个试管顶部的液体倒入这个试管中。
- 如果两个试管中液体数量都，那么我们基本大功告成了（如果烧杯中有液体，需要转到相同颜色的试管或者空试管中）。
- 向烧杯中倒入与其中颜色相同的液体，如果烧杯是空的，就选择高度高的试管顶部的颜色。
最后一步为什么需要选择高度高的？考虑以下情况：
2
1 2 1
如果将颜色2倒入烧杯，则需要5次操作（1->3, 2->1, 2->3, 1->2, 3->1），而如果将颜色1倒入烧杯，则只需要3次操作（2->3, 2->1, 3->1）。所以我们认为选择高度高的是更优的。
当然这不是一个严谨的证明，但以上四条策略就可以通过测试了。
这个题总体就是一个偏尝试的题目，用直观的思路以及举例反复尝试找到解法，似乎是出题人的初衷（官方题解也并没有给出特别优美的解法）。但这个在考场上要全部试出来还是比较难的，因为认为有蓝题难度。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,p,m;
char s1[100005], s2[100005];
vector<int> ts[2];
vector<pi> ans;
int beaker;
void dedup(vector<int> &t, char *s) {
t.clear();
for (int i = 0; i < n; i++) {
if (i == 0 || t[t.size()-1] != s[i]-'1')
t.push_back(s[i]-'1');
}
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &p);
scanf("%s", s1);
scanf("%s", s2);
// dedup the colors
dedup(ts[0], s1);
dedup(ts[1], s2);
beaker = -1;
ans.clear();
while (1) {
// merge the same color to the lower tube
if (!ts[0].empty() && !ts[1].empty() && ts[0].back() == ts[1].back()) {
if (ts[0].size() > ts[1].size()) {
ts[0].pop_back();
ans.push_back({1, 2});
} else {
ts[1].pop_back();
ans.push_back({2, 1});
}
continue;
}
// move to an empty tube
if (ts[0].empty() && ts[1].size() > 1 && ts[1].back() != beaker ||
ts[1].empty() && ts[0].size() > 1 && ts[0].back() != beaker) {
int i = ts[0].empty() ? 0 : 1;
ts[i].push_back(ts[1-i].back());
ts[1-i].pop_back();
ans.push_back({(1-i)+1, i+1});
}
// done if both have <= 1, move beaker liquid back if necessary
if (ts[0].size() <= 1 && ts[1].size() <= 1) {
if (beaker != -1) {
int i = (ts[0].empty() || ts[0].back() == beaker) ? 0 : 1;
ans.push_back({3, i+1});
}
break;
}
// move liquid from tube to beaker
int i;
if (beaker == -1)
i = ts[0].size() > ts[1].size() ? 0 : 1;
else
i = ts[0].back() == beaker ? 0 : 1;
beaker = ts[i].back();
ts[i].pop_back();
ans.push_back({i+1, 3});
}
printf("%d\n", ans.size());
if (p > 1) {
for (auto &a: ans)
printf("%d %d\n", a.first, a.second);
}
}
return 0;
}