题解：AT_abc395_d [ABC395D] Pigeon Swap

题目大意

有标有

1, 2, \ldots, N

的

N

只鸽子和标有

1, 2, \ldots, N

的

N

个鸟巢。

最初，鸽子

i (1\leq i\leq N)

位于鸟巢

i

中。

你将对这些鸽子执行

Q

次操作。

有三种类型的操作：

操作 $1$ ：你将得到整数 $a$ 和 $b(1\leq a\leq N, 1\leq b \leq N)$ 。将 $a$ 号鸽子移至 $b$ 号鸟巢。
操作 $2$ ：你将得到整数 $a$ 和 $b (1 \leq a \leq b \leq N)$ 。将鸟巢 $a$ 中的所有鸽子与鸟巢 $b$ 中的所有鸽子交换。
操作 $3$ ：你将得到一个整数 $a(1\leq a \leq N)$ 。输出鸽子 $a$ 目前所在巢穴的编号。

按操作顺序打印每个操作

3

的结果。

题解

思路

首先我们很容易想到通过一个数组 in 来记录每只鸽子所在的鸟巢，这样子对于每个操作

1

，我们只需要将 in[a] 的值设为 b 即可。

但是如果只使用这么一个 in 数组，对于操作

2

，我们就需要遍历每一个在

a

巢和

b

巢的鸽子，但对于如此大的数据，这样显然会超时。

所以我们可以考虑将他们巢的编号交换，这样就可以将时间优化到

\Theta(n)

了。

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

CPP

在这里，第

4

个操作将

4

号鸟巢和

5

号鸟巢交换。

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

$act_{i}$ 表示 $i$ 个存储空间记录了 $act_{i}$ 号鸟巢；
$to\_act_{i}$ 表 $i$ 号鸟巢所在的存储空间。

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

CPP

对于这组数据：

存储空间编号	$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

的代码：

CPP

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

理解了上面的思路之后，操作

1

和操作

3

的代码就很好实现了，这里就不赘述了。

代码

CPP

#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;
}

题解：AT_abc395_d [ABC395D] Pigeon Swap

文章操作

题目大意

题解

思路

第 $1$ 次操作

第 $2$ 次操作

代码

相关推荐

评论

题解：AT_abc395_d [ABC395D] Pigeon Swap

文章操作

题目大意

题解

思路

第 111 次操作

第 222 次操作

代码

相关推荐

评论

第 $1$ 次操作

第 $2$ 次操作