AT_abc368 补题报告

zhangjinxuan

前言

我感觉我写这些内容对自己有很大益处，尤其是考试补题，因为补题不仅仅是一个“能多几个 AC”的作用，还是一个吸取教训、总结、提升自己的一个重要途径。从某种意义上来说这是写给自己的。

每一场（方便公开）的比赛如果改完题目（达到能力上限）就会来总结。由于 lz 水平有限，所以一些帖子的学术性问题欢迎在本贴讨论指出错误。

---

比赛题目：https://atcoder.jp/contests/abc367/tasks，改完题了，真开心~

问题 C

你正在玩一个游戏。
有 $N$ 个敌人排成一排，最前面的 $i$ 个敌人的健康值是 $H_i$ 。
你将使用初始化为 $0$ 的变量 $T$ 重复以下操作，直到所有敌人的生命值都变为 $0$ 或更少。
- 将 $T$ 增加 $1$ 。然后，攻击最前方生命值大于等于 $1$ 的敌人。如果 $T$ 是 $3$ 的倍数，则敌人的生命值会减少 $3$ ；否则，生命值会减少 $1$ 。
当所有敌人的生命值变为 $0$ 或更少时，求 $T$ 的值。

为了方便起见，我们规定在每一次定点攻击之前，都规定 $T$ 必须在 $\mod 3$ 意义下必须是 $0$，当然如果在攻击的过程中敌人没了就没了。

然后就可以注意到，通过连续 $3$ 次的定点打击之后，$T$ 仍然等于 $0$，而且敌人就会在这个过程中减少 $5$ 的 HP，这种是可以直接用除法计算的。

剩下的敌人血量最多只有 $5$ 了，暴力模拟即可。

场切：https://atcoder.jp/contests/abc368/submissions/57043419

问题 D

有一棵树，你可以任意地删除点和点所连向的所有边，除了给定的 $k$ 个点，问在保证连通和的情况下，整个树最少的节点数量。

想象如果只有两个点的时候，显然就是两个点之间的路径，这一条路径显然就是他们的 lca 到这两个点需要保留。

然后三个点的时候，也就是三个点的 lca 到这三个点的路径需要保留。

因此在求出他们的 lca 之后，我们就一定知道那些点是一定要保留的，树上差分或者树链剖分即可。

场切：https://atcoder.jp/contests/abc368/submissions/57058019

问题 E

在 Atcoder 国家，有 $N$ 座城市，编号为 $1$ 至 $N$ ，有 $M$ 列火车，编号为 $1$ 至 $M$ 。列车 $i$ 在 $S_i$ 时刻从城市 $A_i$ 出发，在 $T_i$ 时刻到达城市 $B_i$ 。

给定一个正整数 $X_1$ ，求一个非负整数 $X_2,\ldots,X_M$ 的最小值 $X_2+\ldots+X_M$ ，以满足下列条件。

- 条件对于所有满足 $1 \leq i,j \leq M$ 的一对 $(i,j)$ ，若 $B_i=A_j$ 和 $T_i \leq S_j$ ，则 $T_i+X_i \leq S_j+X_j$ 。
    - 换句话说，对于任何一对原本可以换乘的列车，即使将每列列车 $i$ 的出发和到达时间延迟 $X_i$ ，也仍然可以换乘。

可以证明，这种将 $X_2,\ldots,X_M$ 设为 $X_2+\ldots+X_M$ 的最小值的方法是唯一的。

显然一个城市延迟的增加不会使得答案更优，因此贪心尽量最小的即可。

然后，可以把每一个路径拆分成两个部分，一个是到达，一个是出发，就可以直接按照他们的时间从小到达进行排序再处理。

再处理第 $i$ 个信息时候，如果是出发的信息，我们应该把之前所有的到达本节点的信息结合起来，取得最大值，这个最大值就是出发时间至少应该的值，减去本身出发时间就是需要延迟的之间。

然后你会发现时间复杂度是 $O(M^2)$ 的，但是发现求最大值是可以边求解边更新的，具体来说，如果当前的是到达的信息，就把对应车站记录的最大值通过当前的时间（加上本身延迟过后）更新即可。

赛后：https://atcoder.jp/contests/abc368/submissions/57113547

问题 F

两个人对 $N$ 个数字博弈，每次可以将一个数字变成其的真因子（假定 1 没有真因子），不能操作者输，问先手是否有必胜策略。

让我们把每一个数字做一个质因数分解，那么在将一个数字变成其的真因子的过程中，就是删除一些质因子的过程。

还是不理解就再抽象一下，一个数字对应这一堆石头，石头的数量就是质因子的数量，就会发现转换成了 Nim 游戏。

Nim 游戏中，先手当且仅当获胜，就是所有石头的数量在二进制异或下等于 0，这个与 SG 函数相关，此处仅为解题报告，故不展开。

场切：https://atcoder.jp/contests/abc368/submissions/57073953

问题 G

给你长度为 $N$ 的正整数序列 $A$ 和 $B$ 。按照给出的顺序，处理以下列形式给出的 $Q$ 个查询。每个查询属于以下三种类型之一。

- 类型 $1$ ：以 `1 i x` 的形式给出。将 $A_i$ 替换为 $x$ 。
- 类型 $2$ ：以 `2 i x` 的形式给出。用 $x$ 代替 $B_i$ 。
- 输入 $3$ ：以 `3 l r` 的形式给出。求解以下问题并打印答案。
    - 首先，设置 $v = 0$ .依次将 $i = l, l+1, ..., r$ 中的 $v$ 替换为 $v + A_i$ 或 $v \times B_i$ 。最后求出 $v$ 的最大可能值。

保证给定类型 $3$ 查询的答案最多为 $10^{18}$ 。

考虑一个经典假算，第一次操作必定为 $v=v+ A_i$，所以就直接从下一个开始。

因为在 $B=1$ 的时候，是毫无影响的，所以在当前的位置，只需要跳转到下一个 $B$ 不是 $1$ 的位置即可，在这中间，统统使用将 $v$ 替换为 $v=v+A_i$，变成其中的总和即可。

然后在这一个不是 $1$ 的位置，让 $v=\max(v+A_i, vB_i)$ 即可，重复上面的操作，直到跳过 $r$。

你会发现 $A$ 的单点修区间和很简单树状数组，跳转下一个是可以使用区间修改线段树维护的，具体来说，如果要把一个 $1$ 改成非 $1$，那么，在这个 $1$ 之前的 $1$ 到本身的下一个就是自己，本身到这个 $1$ 之后的 $1$ 的上一个还是自己，之所以维护上一个，是因为在修改过程中，需要涉及到“更改上一个的下一个”的操作，就和链表一样。

然后把非 $1$ 改成 $1$ 同理。

分析复杂度，注意到答案最多为 $10^{18}$，所以在每一次跳到非 $1$ 的过程中，答案一定会翻倍，这个翻倍增长的速度十分快，$60$ 次就会超过 $10^{18}$，所以最多会进行 $60$ 次跳转操作，然后每一次的跳转是 $O(\log n)$ 的，所以时间复杂度就是 $O(q \log n \log V_{ans})$。

十分考验假算能力，不会做都是因为假算能力不够。

赛后：https://atcoder.jp/contests/abc368/submissions/57113547

总结教训

线段树一定不要写成这个样子：

#define ls(p) (p << 1)
#define rs(p) (p << 1)

一定不要写成这个样子。

一定不要写成这个样子。

一定不要写成这个样子。

柿子饼同学

左孩子: 欸你谁啊

sfqxx

领个鱼币。

zhangjinxuan

sfqxx 发表于 2024-8-25 21:38
领个鱼币。

左儿子和右儿子同一个编号存储当然错误。

sfqxx

zhangjinxuan 发表于 2024-8-26 23:03
左儿子和右儿子同一个编号存储当然错误。