AtCoder Beginner Contest 216 D - Pair of Balls

题目大意
有n种颜色,m个圆柱体,每一种颜色都有2个小球,小球放在这m个圆柱体里面,每次只能取走圆柱体最上面的相同颜色的小球,问能不能取走所有的小球
思路
把这m个圆柱体看做m个队列,分别遍历这m个队列,当第二次遇到同一颜色的小球时,把这两个小球拿走, 看最后还有没有小球在圆柱体面,如果有,那么就不能取走
vis[i] = 1:小球之前出现过
mp[i] = a:第i个小球之前出现过的位置在第a个圆柱体最上面
空间复杂度稍稍有一点大,还是可以过

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int N = 2e5 + 10;
int n, m;
unordered_map<int, int=""> mp;
vector<queue<int>> q(N);
bool vis[N];
void dfs(int i)
{
    //mp.count(q[pos].front())
    int pos = mp[q[i].front()];
    q[pos].pop();
    q[i].pop();
    while(!q[pos].empty() && vis[q[pos].front()])
    {
        dfs(pos);
    }
    if(!q[pos].empty())
    {
        vis[q[pos].front()] = 1;
        mp[q[pos].front()] = pos;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        for (int j = 1; j <= x; j++)
        {
            int t;
            cin >> t;
            q[i].push(t);
        }
    }
    for(int i = 1; i <= m; i++)
    {
        while(!q[i].empty() && vis[q[i].front()])
        {
            dfs(i);
        }
        if(!q[i].empty()) //记录栈顶元素时记得不要越界了
        {
            vis[q[i].front()] = 1;
            mp[q[i].front()] = i;
        }
    }
    /*
2 2
2
1 2
2
1 2
    */
    int flag = 0;
    for (int i = 1; i <= m; i++)
    {
        if (!q[i].empty())
        {
            flag = 1;
            break;
        }
    }
    if (flag)
        puts("No");
    else
        puts("Yes");
}
```</queue<int></int,></queue></vector></string></algorithm></unordered_map></cstring></iostream>
上一篇:AtCoder Beginner Contest 214


下一篇:AtCoder Beginner Contest 166 (A~E)