Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

ABC216D 题解

posted on 2022-10-23 15:47:58 | under 题解 |

题意

有 $m$ 个栈,栈里面的小球有 $n$ 种颜色,每种颜色各有 $2$ 个,共 $2n$ 个小球。

每次可以取出栈顶 $2$ 个颜色相同的小球,问能不能把小球取完。

能取完输出 Yes,否则输出 No

$n,m \leq 2 \times 10^5$。

思路

因为栈顶两个小球颜色相同才能取,所以我们关注的是栈顶小球的颜色。

所以只需要维护当前栈顶的颜色的集合,每次删去一对,如果互不相同就是无解。

当然这题建图判其是否有环也是可以的。

代码

我代码的思路就是用队列(queue)维护上文所说集合,栈顶两个小球颜色相同就推入队列中,后面模拟跑这个队列,每次取出上面的小球,然后更改栈顶小球颜色情况,如果栈顶两个小球颜色依然相同继续推入队列中,如此反复,最后如果能取出 $2n$ 个小球则说明取完。

如果具体代码实现不清楚的,可以看看如下我写的代码。

#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 记录