题解：AT_abc411_d [ABC411D] Conflict 2

题目大意

有一台服务器和

n

台个人电脑。服务器和每台个人电脑各有一个字符串，最初所有字符串都是空的。

给出了

q

个查询，每个查询都是以下格式之一：

1 p：用服务器的字符串替换个人电脑 $p$ 的字符串。
2 p s：在个人电脑 $p$ 的字符串的末尾添加字符串 $s$ 。
3 p:用个人电脑 $p$ 的字符串替换服务器的字符串。

按照给定的顺序处理所有查询后，找出服务器的最终字符串。

思路

直接模拟会超时，因为字符串的赋值操作是

\mathcal{O}(N)

的。

所以考虑通过建有向图的方式来维护题目的操作。为了方便，将服务器设置为

0

号个人电脑。

对于操作 $1、3$ ：修改该字符串上的结点的实际编号即可。
对于操作 $2$ ：用 $0$ 号个人电脑到结点的路径来表示字符串的拼接操作。

做法

对于操作 $1$ ：将个人电脑的结点的实际编号指向服务器结点（不创建新节点）。
对于操作 $2$ $2$ ：
1. 创建新的结点，用来存储追加的字符串。
2. 其父节点指向个人电脑的结点，并跟新当前结点。
对于操作 $3$ ：将服务器结点指向个人电脑的结点的实际编号（不创建新节点）。

详细见代码。

代码

CPP

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
const int N = 2e5 + 10;
int a[N], fa[N];
string s[N];

void dfs(int x) {
    if (!x) return;
    dfs(fa[x]);
    cout << s[x];
}

/*
维护一个图，用边来表示操作
a[x] -> 第x个字符串，对应哪个点
fa[num] -> 第num个点，是由哪个点转移过来的
s[num] -> 从 fa[num] 到 num  新增了哪个字符串
nw -> 根节点实际上是哪个点
*/

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q, num = 0, nw = 0;
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        int op, x;
        cin >> op >> x;
        if (op == 1)
            a[x] = nw;
        else if (op == 2) {
            num++;
            cin >> s[num];
            fa[num] = a[x];
            a[x] = num;
        } else
            nw = a[x];
    }
    dfs(nw);
    return 0;
}

题解：AT_abc411_d [ABC411D] Conflict 2

文章操作

题目大意

思路

做法

代码

相关推荐

评论

题解：AT_abc411_d [ABC411D] Conflict 2