题解：P10191 [USACO24FEB] Test Tubes S
elainya_stars
·
·
题解
P10191 [USACO24FEB] Test Tubes S 题解
这个就是大模拟小贪心，本来以为有多高级后来发现就是分类讨论。
题意
有 a_{1 \sim n} 和 b_{1 \sim n} 两个管，里面分布着 1 和 2 两种颜色。a_i 和 b_j 分别代表从 a 和 b 两个管底数 i 和 j 个颜色块的颜色。现有一个空杯 c，问你它们仨倒来倒去最终把 1 和 2 两种颜色分别装在 a 和 b 里的最少倒的次数，显然，c 最终需要为空。“倒”表示把某个管或杯顶相同颜色的那一组颜色块一起倒到另一个管或杯里的过程。（表达能力极弱）
:::info[样例 1 解释]
| | | | | | | | | | | |
|---| |---| | | |---| |---| | |
| 1 | | 1 | | | | 1 | | 2 | | |
|---| |---| | | |---| |---| | |
| 2 | | 1 | | | | 1 | | 2 | | |
|---| |---| | | |---| |---| | |
| 2 | | 2 | | | | 1 | | 2 | | |
|---| |---| | | |---| |---| | |
| 1 | | 2 | | | | 1 | | 2 | | |
└---┘ └---┘ └---┘ └---┘ └---┘ └---┘
a b c 最终变成 a b c
步骤：
```cpp
"1 2" : a="122"
b="22111"
c=""
"1 3" : a="1"
b="22111"
c="22"
"2 1" : a="1111"
b="22"
c="22"
"3 2" : a="1111"
b="2222"
c=""
```
:::
## 思路
首先，很容易发现每次“倒”的过程都是把顶上一串相同的颜色一起倒走，所以所有管和杯里的**相邻且相同**的颜色可以合并，也就是说，所有管和杯里的**相邻颜色始终不能相同，忽略重复**，每一个颜色都代表原来管和杯里相邻且相同的颜色块们。~~（啰嗦）~~
接下来处理每一步的“倒”。总共分为 $3$ 大步：终止条件，管的处理（管空+管顶相等），杯的处理（杯空+杯顶与另一个管顶相等），下面是详细步骤及思考方式。
:::info[$5$ 小步]
**1.终止条件：俩管都只有 $1$ 个颜色，且管顶不相等。**
这种相当于已经分好了，但是还需判一下杯是否为空，不是的话把杯里东西分给和杯顶颜色相同的那个管里就行了。这里处理完就结束了直接 `break;`。
**2.管空**
若另一个管只有 $1$ 个颜色了，把 $c$ 里的倒到那个空的管里直接结束了 `break;`。否则的话把不空的管顶倒到空管里是最优的，这个就不解释了。
**3.管顶相等**
把存的颜色多的那个管的管顶倒到另一个管顶让它俩合并，这个是最优的也不做解释。
先处理管再处理杯的原因：俩管顶相等只用1步合并，俩管顶都移杯里需要2步合并，而且就算移杯里更优一点，最后杯里的东西还得倒回管里，又会浪费几步。
**4.杯空**
~~不能让它闲着。~~ 哪个管存的颜色多就把这个管顶倒到杯里，给管顶下面颜色腾位置，不做解释。
**5.杯顶与某个管顶相等**
下意识是把杯顶倒到管里让它俩合并，但是仔细想想，把管顶倒到杯里合并更优。倒到杯里合并后杯中颜色并不会增多，而且还能给管顶下面的颜色腾位置，所以这个更优。
:::
然后就没了，建 $3$ 个栈然后模拟就行了。**$T$ 组数据注意清空。**
## Code
:::success[by elainya_stars]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(n) cerr<<#n<<":"<<n<<'\n'
const int N=1e6+5;
int t,n,p;
struct pii
{
int fr,to;
}ans[N];
int na; // ans下标
stack<int> a,b,c;
void clear()
{
while(!a.empty())
a.pop();
while(!b.empty())
b.pop();
while(!c.empty())
c.pop();
memset(ans,0,sizeof ans);
na=0;
}
void work()
{
cin>>n>>p;
clear();
for(int i=1,x;i<=n;i++)
{
scanf("%1lld",&x);
if(a.empty() || a.top()!=x) // 相邻不能重复，所有栈都忽略重复
a.push(x);
}
for(int i=1,x;i<=n;i++)
{
scanf("%1lld",&x);
if(b.empty() || b.top()!=x) // 同理
b.push(x);
}
while(1)
{
if(a.size()==1 && b.size()==1 && a.top()!=b.top())
{ // 1. 终止条件
if(c.empty())
break;
if(a.top()==c.top())
{
ans[++na]={3,1};
break;
}
if(b.top()==c.top())
{
ans[++na]={3,2};
break;
}
}
// 这里开始判管
else if(a.empty())
{ // 2. 管空
if(b.size()==1)
{
ans[++na]={3,1};
break;
}
// b顶给a最优，腾出b顶底下压着的东西
a.push(b.top());
b.pop();
ans[++na]={2,1};
}
else if(b.empty())
{
if(a.size()==1)
{
ans[++na]={3,2};
break;
}
// a顶给b最优，腾出a顶底下压着的东西
b.push(a.top());
a.pop();
ans[++na]={1,2};
}
else if(a.top()==b.top())
{ // 3. 管顶相等
// 一定先判俩管的顶不考虑杯
// 因为俩管顶相等只用1步合并
// 俩管顶都移杯里需要2步合并
if(a.size()>b.size())
a.pop(),ans[++na]={1,2};
// 这里b不用push因为颜色一样，栈里忽略重复
else
b.pop(),ans[++na]={2,1}; // 同理
}
// 这里开始判杯
else if(c.empty())
{ // 4. 杯空
if(a.size()>b.size())
{
c.push(a.top());
a.pop();
ans[++na]={1,3};
}
else
{
c.push(b.top());
b.pop();
ans[++na]={2,3};
}
}
else if(a.top()==c.top())
// 5. 杯顶等
a.pop(),ans[++na]={1,3};
else if(b.top()==c.top())
// 这俩判断不考虑顺序，因为只有两种颜色，不可能管杯颜色全相等
b.pop(),ans[++na]={2,3};
}
cout<<na<<'\n';
if(p>1)
for(int i=1;i<=na;i++)
cout<<ans[i].fr<<' '<<ans[i].to<<'\n';
}
signed main()
{
cin>>t;
while(t--)
work();
return (0.0);
}
```
:::
给我赞赞 qwq