abc 395 题解整合

da_ke · 2025-03-01 22:22:40 · 题解

前言

人物介绍：

• fyy，即 \texttt{\color{#ff0000}{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 的坐标位置互换，达到 S_a'=S_b,S_b'=S_a 的效果。

代码是简单的。

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 的写法。

代码

終

本当の本当に終わり