P7935 题解

ikunTLE · 2024-05-27 21:46:03 · 题解

题目传送门

对于表格第一行，每个整数只出现一次。所以我们可以用桶排序找到第二个序列和第三个序列中，哪个数字没有出现过出现，就删掉那个数字。但是由于连锁反应，会影响到后面的数字，所以将要删除的数字放入队列之中。只要队列没空这个数字删除，此过程一直持续。需要注意的是一列不要重复删，需要打标记。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[4][N],s[N],e[N],wei[N],ans;
bool vis[N];
queue<int> q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[1][i]),
        wei[a[1][i]]=i;
    for(int i=1;i<=n;++i)
        scanf("%d",&a[2][i]),
        e[a[2][i]]++;
    for(int i=1;i<=n;++i)
        scanf("%d",&a[3][i]),
        s[a[3][i]]++;
    for(int i=1;i<=n;++i){
        if(!e[i]||!s[i])
            q.push(i);
        while(!q.empty()){
            int del=wei[q.front()];
            if(vis[del]){
                q.pop();
                continue;
            }
            vis[del]=1;
            --e[a[2][del]];
            --s[a[3][del]];
            //确保不会重复删
            if(!e[a[2][del]])
                q.push(a[2][del]);
            if(!s[a[3][del]])
                q.push(a[3][del]);
            ans++;
            q.pop();
        }
    }
    printf("%d",ans);
    return 0;
}