ABC216D 题解
Jerrlee✅
2022-10-23 15:47:58
## 题意
有 $m$ 个栈,栈里面的小球有 $n$ 种颜色,每种颜色各有 $2$ 个,共 $2n$ 个小球。
每次可以取出栈顶 $2$ 个颜色相同的小球,问能不能把小球取完。
能取完输出 `Yes`,否则输出 `No`。
$n,m \leq 2 \times 10^5$。
## 思路
因为栈顶两个小球颜色相同才能取,所以我们关注的是栈顶小球的颜色。
所以只需要维护当前栈顶的颜色的集合,每次删去一对,如果互不相同就是无解。
当然这题建图判其是否有环也是可以的。
## 代码
我代码的思路就是用队列(`queue`)维护上文所说集合,栈顶两个小球颜色相同就推入队列中,后面模拟跑这个队列,每次取出上面的小球,然后更改栈顶小球颜色情况,如果栈顶两个小球颜色依然相同继续推入队列中,如此反复,最后如果能取出 $2n$ 个小球则说明取完。
如果具体代码实现不清楚的,可以看看如下我写的代码。
```cpp
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N,M;
queue<int>P[2<<17];
vector<int>ids[2<<17];
main()
{
cin>>N>>M;
queue<int>Q;
for(int i=0;i<M;i++)
{
int k;cin>>k;
for(int j=0;j<k;j++)
{
int a;cin>>a;
P[i].push(a);
}
int f=P[i].front();
ids[f].push_back(i);
if(ids[f].size()==2)Q.push(f);//栈顶两小球颜色相同则推入队列中
}
int cnt=0;
while(!Q.empty())
{
int u=Q.front();Q.pop();
cnt++;
for(int i:ids[u])
{
P[i].pop();
if(!P[i].empty())
{
int f=P[i].front();
ids[f].push_back(i);
if(ids[f].size()==2)Q.push(f);//栈顶两小球颜色相同则推入队列中
}
}
}
cout<<(cnt<N?"No":"Yes");//如果能取出 2n 个小球则说明取完
}
```
[AC 记录](https://www.luogu.com.cn/record/91185358)