AT_abc395_d

前言

https://blog.csdn.net/ArmeriaLeap/article/details/145954559

在谎言中迷茫，试图躲避瓶颈。可惜细节太多，浪费五发罚时。一个绿名用户，被出题人卡住。八十六分钟多，才看见一抹绿。

本题解

\LaTeX

格式可能不太美观，以内容为主。

题目大意

有一群鸽子和它们的窝，三种操作，你要在第三种的时候输出一个数。题面很简单，没有太多的文字游戏，自行阅读吧。这篇题解不提供题目翻译。

思路

想一想暴力，为什么会超时？正解需要对哪里进行优化？

观察第二种操作，发现它太吃操作了，是这道题的时间复杂度瓶颈。本文将介绍一种时间复杂度为

O(Q)

的做法。对于第二种操作，显然不能暴力模拟——为了不超时，我们绝对不能交换鸽子！作为口是心非的 OIer，让我们充分发扬人类智慧：做个记号，下面算答案的时候注意一下即可。

具体地，我们要维护三个数组：

a_i表示第i只鸽子在哪个窝里；\\ b_i表示“第i个窝”里的鸟儿实际上被换到了哪个窝；\\ c_i表示第i个窝现在用谁表示。

有点绕，好好理解一下。~~毕竟我调了近一个小时，这肯定不是什么简单的东西。~~

现在来说一下三种操作的实现。

第一种操作——单只鸽子 $x$ 搬到 $y$ ：a[x]=c[y];
第二种操作—— $x$ 和 $y$ 两个窝集体交换：swap(b[c[x]],b[c[y]]); swap(c[x],c[y]);
第三种操作——输出 $x$ 在哪里：cout << b[a[x]] << endl;

代码实现

Submission #63299010

CPP

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n, q;
int a[1000010];
int b[1000010];
int c[1000010];

int main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		a[i] = b[i] = c[i] = i;
	while (q--)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y;
			cin >> x >> y;
			a[x] = c[y];
		}
		else if (op == 2)
		{
			int x, y;
			cin >> x >> y; 
			int cx = c[x];
			int cy = c[y];
			b[cx] = y; c[y] = cx;
			b[cy] = x; c[x] = cy;
		}
		else
		{
			int x; cin >> x;
			cout << b[a[x]] << endl;
		}
	}
	return 0;
}

文章操作

前言

题目大意

思路

代码实现

相关推荐

评论

AT_abc395_d