题解：AT_abc395_d [ABC395D] Pigeon Swap

· · 题解

AT_abc395_d [ABC395D] Pigeon Swap 题目链接

题目大意

有标有 1, 2, \ldots, N 的 N 只鸽子和标有 1, 2, \ldots, N 的 N 个鸟巢。

最初，鸽子 i (1\leq i\leq N) 位于鸟巢 i 中。

你将对这些鸽子执行 Q 次操作。

有三种类型的操作：

按操作顺序打印每个操作 3 的结果。

题解

思路

首先我们很容易想到通过一个数组 in 来记录每只鸽子所在的鸟巢，这样子对于每个操作 1，我们只需要将 in[a] 的值设为 b 即可。

但是如果只使用这么一个 in 数组，对于操作 2，我们就需要遍历每一个在 a 巢和 b 巢的鸽子，但对于如此大的数据，这样显然会超时。

所以我们可以考虑将他们巢的编号交换，这样就可以将时间优化到 \Theta(n) 了。

具体的，我们可以通过样例来看：

6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2

在这里，第 4 个操作将 4 号鸟巢和 5 号鸟巢交换。

我们将定义以下两个数组：

这么说可能有点抽象，我们结合例子来讲解：

6 2
2 4 5
2 4 6
3 6

对于这组数据：

存储空间编号 1 2 3 4 5 6
初始值 1 2 3 4 5 6
第 1 次操作（实际上对应的鸟巢编号） 1 2 3 5 4 6
第 2 次操作 1 2 3 6 4 5
第 3 次操作 1 2 3 6 4 5

所以最后应该输出 4，因为 6 号鸽子在鸟巢 4 里面。

第 1 次操作

我们需要交换 4 号巢和 5 号巢，所以现在 4 号存储空间应该存着 5 号巢。相同地，5 号存储空间存着 4 号巢：

act_{4}=5, act_{5}=4

接下来更新 to\_act 数组。现在 4 号巢被存在了 5 号存储空间，5 号巢被存在了 4 号存储空间：

to\_act_{4}=5, to\_act_{5}=4

第 2 次操作

现在我们需要交换 4 号巢和 6 号巢。此时 4 号巢的数据被存在了 to\_act_{4}=5 号存储空间，所以我们实际上需要交换的是 5 号存储空间和 6 号存储空间。

那么这时 5 号存储空间存储的就是 6 号巢的数据，6 号存储空间存储的就是 4 号巢的数据：

act_{to\_act_{4}}=6, act_{to\_act_{6}}=4

也就等同于：

act_{5}=6, act_{6}=4

接下来，4 号巢的存储空间和 6 号巢的存储空间交换：

to\_act_{4}=6, to\_act{6}=5

上面的过程比较绕，建议多看几遍。

所以我们就可以很轻松地得到操作 2 的代码：

scanf("%d%d",&y,&z);
act[to_act[y]]=z;
act[to_act[z]]=y;
swap(to_act[y],to_act[z]);

理解了上面的思路之后，操作 1 和操作 3 的代码就很好实现了，这里就不赘述了。

代码

#include<bits/stdc++.h>
using namespace std;
int in[1000010],act[1000010],to_act[1000010],n,q,x,y,z,tmp;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) in[i]=act[i]=to_act[i]=i;//注意初始化
    while(q--){
        scanf("%d",&x);
        if(x==1){
            scanf("%d%d",&y,&z);
            in[y]=to_act[z];
        }else if(x==2){
            scanf("%d%d",&y,&z);
            act[to_act[y]]=z;
            act[to_act[z]]=y;
            swap(to_act[y],to_act[z]);
        }else{
            scanf("%d",&y);
            printf("%d\n",act[in[y]]);
        }
    }
    return 0;
}