题解：AT_abc395_d [ABC395D] Pigeon Swap

fyy 是一个珂愛的女孩子，有一天她购得 $N$ 只珂愛的 da_ke。

她初始将编号 $i$ 的 da_ke 放置在 $i$ 号笼子里。

随后，她进行 $Q$ 次操作，操作分为 $2$ 类

将 $a$ 号 da_ke 放入 $b$ 号笼子

将 $a$ 号笼子和 $b$ 号笼子里的所有 da_ke 互换。

fyy 可以在任意时刻问妳某个 da_ke 在哪个笼子里。

fyy 非常喜欢 da_ke，于是她买了很多只，于是妳要使用一种非常高效的算法来回答她的问题。

「珂愛的我」（下简记为我）想到，对于操作

1

是容易的，经常刷题的朋友都知道，对于操作

2

不容易单个处理，必须整体处理。

对于操作

2

，我想到将笼子

a

和笼子

b

整体交换。但这将导致

a

和

b

的位置改变，da_ke 的位置也将改变，如何处理呢？

问题过于抽象，为了更加形象（笔者赛时也是这么想的），我将问题形象化。

将笼子和 da_ke 一起放在数轴上。为了语言描述，我常用「da_ke 本身」和「笼子本身」这两个短语。

对于所有操作 $1$ ，我们只需挪动 da_ke 本身的位置即可。
对于所有操作 $2$ $2$ ：
- 保证 da_ke 本身的位置不变（解题的关键）。
- 只交换笼子本身达到效果。
- 更新笼子本身的位置。

以上是一些感性认识，我们现在将其转换为形式化语言。

记笼子

i

的坐标位置为

S_i

，坐标位置

i

的笼子为

E_i

，编号为

i

的 da_ke 目前被关在坐标位置为 $H_i$ 的笼子里。

对于操作 $1$ ， $H_a \leftarrow S_b$ 。
对于操作 $2$ $2$ ：
- $a$ 的位置将被 $b$ 占用， $b$ 同理，于是有 $E_{S_a}\leftarrow b,E_{S_b}\leftarrow a$ 。
- 将 $a,b$ 的坐标位置互换，达到 $S_a'=S_b,S_b'=S_a$ 的效果。

代码是简单的。

CPP

int main()
{
    int N,Q;
    cin>>N>>Q;
    vector<int> st(N+1),ed(N+1),home(N+1); // st 为某个巢的坐标位置，ed 为某个坐标位置的巢。 
    rep(i,1,N) st[i]=i,ed[i]=i,home[i]=i;
    rep(i,1,Q)
    {
        int o;
        cin>>o;
        // 操作时应保证，鸽子是不动的。
        if(o==1)
        {
            int a,b;
            cin>>a>>b;
            home[a]=st[b];
        }
        /*
        .....a.....b....
        .....b.....a....
        */
        if(o==2)
        {
            int a,b;
            cin>>a>>b;
            ed[st[a]]=b,ed[st[b]]=a;
            swap(st[a],st[b]);
        }
        if(o==3)
        {
            int a;
            cin>>a;
            cout<<ed[home[a]]<<endl;
        }
    }
}

// 路虽远行则将至，事虽难做则必成。

AC 记录

题解：AT_abc395_d [ABC395D] Pigeon Swap

文章操作

相关推荐

评论

题解：AT_abc395_d [ABC395D] Pigeon Swap