AtCoderBeginnerContestAT_abc395_dABC395DPigeonSwap题解

前言

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

本题解 LaTeX \LaTeX LATE​X 格式可能不太美观，以内容为主。

题目大意

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

思路

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

观察第二种操作，发现它太吃操作了，是这道题的时间复杂度瓶颈。本文将介绍一种时间复杂度为 O ( Q ) O(Q) O(Q) 的做法。对于第二种操作，显然不能暴力模拟——为了不超时，我们绝对不能交换鸽子！作为口是心非的 OIer，让我们充分发扬人类智慧：做个记号，下面算答案的时候注意一下即可。

具体地，我们要维护三个数组： a i 表示第 i 只鸽子在哪个窝里； b i 表示“第 i 个窝”里的鸟儿实际上被换到了哪个窝； c i 表示第 i 个窝现在用谁表示。 a_i表示第i只鸽子在哪个窝里；\\ b_i表示“第i个窝”里的鸟儿实际上被换到了哪个窝；\\ c_i表示第i个窝现在用谁表示。 ai​表示第i只鸽子在哪个窝里；bi​表示“第i个窝”里的鸟儿实际上被换到了哪个窝；ci​表示第i个窝现在用谁表示。 有点绕，好好理解一下。毕竟我调了近一个小时，这肯定不是什么简单的东西。

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

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

Submission #63299010

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