「Summary」2023-07-03 做题记录

*3000+

2023-07-03

CF1458D

从操作的限制入手，要求是“连续子串必须包含同样数量的字符 0 与 1”。
将 $0$ 换成 $-1$，然后记录前缀和，并建图，对于每一个 $i$，都建一条 $s_i \rightarrow s_{i + 1}$ 的边，如果 $[l, r]$ 这一段能够操作，那么 $sum_{l - 1} = sum_{r}$。
之后的方法就很妙了，如果我们对 $[l, r]$ 操作，那么 $sum_{l \dots r}$ 会发生改变，似乎没办法维护，但是观察性质可以《发现》：如果说操作前前缀和变化的顺序是从前往后，那么操作之后前缀和的变化是从后往前。
把这个放到图上去，相当于把 $[l, r]$ 这一段里面的所有边都反向。于是现在得到的问题就变成了求一条字典序最短的欧拉通路，贪心很显然。

CF827F

拿到题的第一时间注意到了不能原地停留，而每条边有出现的时间区间，马上想到可以反复横跳。
于是要分奇偶讨论，对于每个点记录 $f_{u, 0 / 1}$ 表示最晚能够在 $u$ 的时间，因为每条边有特定的通过时间，考虑以 $l_i$ 升序排序，去掉时间这一维度。那么 $f_{u, 0 / 1}$ 一定是由时间更小的边走过来的，在当前边出现的时候是一定能走的。
对于有一些目前还不能走的边 $f_{u, 0 / 1} < l$，可以把它挂在 $u$ 这个点上面，直到 $f_{u, 0 / 1} \ge l$ 之后再将它放到边集里面去。因为每条边最多会被塞到边集里面两次，所以复杂度是 $\Theta(m \log m)$ 的。

CF1307F

不难想到要把点的询问挂到对于它最优的休息点上去，于是预处理每个休息点能够辐射到的范围，发现有一些休息点能够互相覆盖，希望将他们塞到一个并查集里面去。
那么有了第一步，从每个休息点出发走 $\frac{k}{2}$ 步，记录每个点最近的休息点，并将能够互相走到的点塞入一个并查集中。
说得有点抽象，代码如下

inline void spread() {
  for (int u : sp) que.push(mp(u, 0)), pre[u] = u;
  while (!que.empty()) {
    pii now = que.front(); que.pop(); int u = now.first;
    if (now.second >= k >> 1) continue;
    for (int v : G[u]) {
      if (!pre[v]) pre[v] = pre[u], que.push(mp(v, now.second + 1)), dsu.unionset(v, pre[u]);
      else dsu.unionset(pre[v], pre[u]);
    }
  }
}

然后考虑回答每一个询问，对于二元组 $(u, v)$，若 $\mathrm{dist}(u, v) \le k$ 那么可以直接走到，否则需要经过休息站。于是从 $u$ 往 $\mathrm{lca}(u, v)$ 跳 $\frac{k}{2}$ 步到 $x$，从 $v$ 往 $\mathrm{lca}(u, v)$ 跳 $\frac{k}{2}$ 步到 $y$。如果 $x,y$ 能够互通，那么 $u, v$ 能够互通。
接下来论证这个方法的正确性，即是论证 $x$ 能走到的有用的休息站集合和 $u$ 能走到的有用的休息站集合等价，只需要想，如果有一个休息站 $p$，$u$ 能走到，$x$ 不能走到，这就意味着 $\mathrm{dist}(p, x) > k,\mathrm{dist}(p, u) \le k$，因为 $\mathrm{dist}(u, x) = \mathrm{dist}(p, x) = \mathrm{dist}(p, u) = \frac{k}{2} \Rightarrow \mathrm{dist}(p, u) > \frac{k}{2}$，所以先走到 $p$ 再走到 $x$ 只会更劣，同理 $v, y$ 也能得出一样的结论。

这里有一些小细节需要注意，为了避免小数距离，可以将 $k$ 乘一倍，在边之间塞虚点；如果往上跳的时候 $\mathrm{dist}\left(u, \mathrm{lca}(u, v)\right) < \frac{k}{2}$，相当于让 $v$ 往上面跳 $\mathrm{dist}(u, v) - \frac{k}{2}$ 步。

CF1556G

删除不是很好实现，首先时光倒流，转换成添加操作。

第一步很难，需要把数放到线段树结构上去做。
可以发现一棵子树内都是联通的，于是可以用这棵子树的根节点代表整棵子树进行操作。

在线段树上记录每个点被删除的时间，可以直接打标记实现，然后遍历每一个不是“叶节点”的点，将其内部暴力连边，若该边连接了 $u,v$ 两个点，那么该边出现的时间是 $\min(\mathrm{rm}(u), \mathrm{rm}(v))$，并将它加入此时间的边集里。
处理询问时，倒序往前把删掉的边塞入并查集，每次查询只需要问能代表 $a_i, b_i$ 的节点是否联通即可。

P3238 道路堵塞

目前没有人类会做，但是这里有一个比较高效的 spfa 暴力。
一个结论，删掉 $\mathrm{sp}(x)$ 后最短路的构成应该是

$$ \begin{aligned} \mathrm{sp}(1), \mathrm{sp}(2), \mathrm{sp}(3), \dots \mathrm{sp}(x - 1), pos_1, pos_2, pos_3, \dots, pos_l, \mathrm{sp}(x + 1), \dots, \mathrm{sp}(L) \end{aligned} $$

于是首先把最短路上的所有边都 ban 掉，然后从前往后依次加边，统计答案是把走到的钦定最短路上的点的距离加上它到 $n$ 的距离。
注意到有问题，有可能答案没有绕过断边，打时间戳标记即可。