题解 P7935

· · 题解

一句话题意：

一个排列和两个序列我简称三个序列。

给定一个排列，两个序列，在 1 \sim n 范围，每次操作可以删除三个序列里的同一位置的数，求最少删几次可以使得三个序列元素相等(排序之后)。

其实这题目首先一看到就应该要考虑排列的性质即：每个元素仅仅出现一次。

我们发现这个性质很有利，只要我们寻找出两个序列里面不存在的数，在排列里面删除即可，然后发现删除的那个位置，在另外两个序列里面也有删除就这样继续。

至于为什么正确，其实也挺显然的。

考虑当前的三个序列必然数量相同，在数量相同的前提下，有一个是排列，那么如果另外两个序列有了相同的数，必然它没有另外一个数。

那么这样删下去肯定会使得其变为只出现一次或者不出现。

具体的实现可以考虑用队列做。

当然这是一个拓扑的结构，我没有很深入的探究。

均摊意义下复杂度 O(n)。

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=1e5+5;
queue <int> q;
int n,a[INF],b[INF],c[INF],f[INF],f1[INF],f2[INF],vis[INF],ans;
signed main()
{
        scanf("%d",&n);
        for (int i=1; i<=n; i++) scanf("%d",&a[i]),f2[a[i]]=i;
        for (int i=1; i<=n; i++) scanf("%d",&b[i]);
        for (int i=1; i<=n; i++) scanf("%d",&c[i]);
        for (int i=1; i<=n; i++) {f[b[i]]++; f1[c[i]]++;}
        for (int i=1; i<=n; i++)
                if (f[i]==0 || f1[i]==0)
                        q.push(i);
        while (q.size()) {
                int xx=q.front(); q.pop();
                if (vis[f2[xx]]) continue;
                vis[f2[xx]]=1;
                f[b[f2[xx]]]--;
                f1[c[f2[xx]]]--;
                if (f[b[f2[xx]]]==0)
                        q.push(b[f2[xx]]);
                if (f1[c[f2[xx]]]==0)
                        q.push(c[f2[xx]]);
                ans++;
        }
        cout<<ans<<"\n";
        return 0;
}

如有问题，还请指出。