ABC216D 题解

## 题意 有 $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)