3 ABC411 C ~ E题解

ABC411 C~E 题解

又是赤石的一天

C

有个长度为 \(N\) 的序列，初始序列中每个数为0

每次操作给定 \(pos\) ，将 pos^1 ，然后输出序列中有多少段不连续的 1

用小样例模拟一下可得，设当前颜色为 \(b\) ，左边颜色为 \(a\) ，右边颜色为 \(c\) ，序列中不连续 1 的段数为 \(cnt\)

• \(a\ne b\ 且\ b \ne c\ \to\ cnt \verb|-=|1\)
• \(a = b\ 且\ b = c\ \to\ cnt \verb|+=|1\)

D

有一台服务器和 \(N\) 台 PC 。服务器和每台 PC 各持有一个字符串，最初所有字符串都是空的。PC 从 \(1 \sim N\) 编号

给出了 \(Q\) 个操作。每个操作都是以下格式之一：

• 1 p:用 服务器 的字符串替换 \(p\) 的字符串。
• 2 p s：在 \(p\) 字符串的末尾添加字符串 \(s\) 。
• 3 p:用 \(p\) 的字符串替换 服务器 的字符串。

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

一开始我想用 string 水过，但 T 飞了，因为 string 赋值操作的时间复杂度是 O(len) 的，后来查了查，发现 string 的很多操作都是 O(len) 的，以后要慎用

下面是正解

用链表来记录下每个 PC 的尾部字符串的编号，以及每个字符串的父串 (注意不能记录每个节点的子节点，这样在修改尾部时会丢失信息)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>using namespace std;const int N = 2e5 + 10;int n, m;
int f[N], p[N];
string s[N];int main () {scanf ("%d%d", &n, &m);memset (p, -1, sizeof p);int rt = 0, cnt = 0;for (int i = 1; i <= m; i++) {int op, x;cin >> op >> x;if (op == 1) {p[x] = p[rt];} else if (op == 2) {cin >> s[++cnt];if (p[x] == -1) {p[x] = cnt;f[cnt] = -1;} else {f[cnt] = p[x];p[x] = cnt;}} else {p[rt] = p[x];}}vector <string> ans;for (int i = p[rt]; i != -1; i = f[i]) {ans.push_back (s[i]);}for (int i = (int)ans.size() - 1; i >= 0; i--) {cout << ans[i];}cout << endl;return 0;
}