abc395 题解整合

Posted on In , ,

文章同载：https://www.luogu.com.cn/article/qd3i9xfj

前言

人物介绍：

  • fyy，即 fp0cy1tz6mn4rd_。
  • da_ke，即 。
  • 「珂愛的我」，即 。

A

ke_ai_de_wo

B

珂愛的我按照形式化题意模拟，不然容易错。

ke_ai_de_wo

C

对于以 \(i\) 结尾的子序列，其开头必然是与 \(A_i\) 相同的最后一个数。对所有情况取最优。

ke_ai_de_wo

D

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

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

随后，她进行 \(Q\) 次操作，操作分为 \(2\) 类

  1. 将 \(a\) 号 da_ke 放入 \(b\) 号笼子
  2. 将 \(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\)：
    • 保证 da_ke 本身的位置不变（解题的关键）。
    • 只交换笼子本身达到效果。
    • 更新笼子本身的位置。

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

记笼子 \(i\) 的坐标位置为 \(S_i\)，坐标位置 \(i\) 的笼子为 \(E_i\)，编号为 \(i\) 的 da_ke 目前被关在坐标位置为 \(H_i\) 的笼子里。

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

代码是简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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 记录

E

fyy 行驶在小溪上，路线可以看作有向图。每条边的边权为 \(1\)。

因为「逆水行舟，不进则退」，fyy 要么沿着边的方向前进，要么逆着边的方向前进。顺、逆之间的转换需要代价 \(X\)。

fyy 想知道从 \(1\) 到 \(N\) 的最短代价是多少。

发现顺着和逆着似乎有着隔阂。这便是「层」。

  • 将每个点 \(i\) 拆成两个点 \(i,i+N\)。
    • 将 \((i,i+N),(i+N,i)\) 连接，边权皆为 \(X\)。
  • 对于每个原来的边 \((u,v)\)：
    • 连接 \((u,v)\) 和 \((v+N,u+N)\)。这里体现顺、逆。

然后 Dijkstra 跑最短路即可。时间复杂度取决于 Dijkstra 的写法。

代码

終

本当の本当に終わり