Solution Set of NFLS SImulations

标签：Set val int T2 Solution T1 SImulations 我们 ally

在 nfls 的最后一天，来记录一些似乎有意义的题吧。

没有原题（或者我忘了原题）的就简要写下题意，不放原题面了。

T2 (CF1329E Dreamoon Loves AA)
T1 (CF1184D2 Parallel Universes (Hard))
T3 (CF1434E A Convex Game)
T1 怪兽 (树上 Monster Hunting)
T2 切割
T3 导弹
T1 (CF1023G Pisces)
T2 (P9312 EGOI2021 Lanterns / 灯笼)
T3 (CF1662J Training Camp)
T2 (HDU6815 Funny String)
T1 冒泡排序
T3 (P8861 线段)
T1 最小割树 (HDU6350)
T2 (HDU6358 Innocence)
T3 高维碎块 (HDU6355)
T1 请你自重 (HDU6417)
T2 猜猜你的 (CF868G)
T2 自动化leetcode (Gym103104K)
T2 红心大战
T1 Path of Sunset
T2 夏影
T3 Planetarian
T2 直线距离
T2 雪豹失联 (CF500G New Year Running)
T3 寻找雪豹 (CF1621H Trains and Airplanes)
T2 sxnlmscp
T1 情商修炼手册
T3 数列
T2 取出排列
T3 序列 (P7722 [Ynoi2007] tmpq)
T2 棋盘
T1 颜色
T2 字符串
T2 原神怎么你了！(CF924F Minimal Subset Difference)

NOI2023 模拟赛 33

在 nfls 打的第一场模拟赛，这场正好与南大营时间撞上，所以打的人不多。而且可以看到在 nfls 进前 50% 是掉分的（

T1 T3 意义不大，写下 T2。

T2 (CF1329E Dreamoon Loves AA)

首先我们肯定不在乎具体的序列了，我们直接将每两个相邻的 \(\mathtt{A}\) 的距离直接写出来。发现，每次操作相当于把一个数分成两个加和与原来相等的数。

考虑什么时候一个 \([L, R]\) 合法。显然对于每一段，肯定是平均分更优，我们考虑每一段被分的次数，一定属于 \(\left[\left\lceil\dfrac{a_i}{R}\right\rceil - 1, \left\lfloor\dfrac{a_i}{L}\right\rfloor - 1\right]\) 这段区间。设一共有 \(m\) 个数，那么一个 \([L, R]\) 满足的条件就是：

\(\forall i \in [1, m], \left\lceil\dfrac{a_i}{R}\right\rceil \le \left\lfloor\dfrac{a_i}{L}\right\rfloor\)；
\(-m + \displaystyle \sum \left\lceil\dfrac{a_i}{R}\right\rceil \le k \le -m + \sum \left\lfloor\dfrac{a_i}{L}\right\rfloor\)。

容易发现，若我们要满足第二个条件，\(L\) 存在一个最大值，\(R\) 存在一个最小值，可以直接二分得出。我们记作 \(L_0, R_0\)。

若 \(L_0 \ge R_0\)，那么答案一定为 \(0\)，因为我们一定能够任意选择一个 \(x \in [R_0, L_0]\)，使得 \(L=R=x\) 成立。第二个条件显然成立，第一个条件由于 \(\left\lceil\dfrac{a_i}{R}\right\rceil \ge \left\lfloor\dfrac{a_i}{L}\right\rfloor\)，且根据第二个条件能得出 \(\displaystyle \sum \left\lceil\dfrac{a_i}{R}\right\rceil \le \sum \left\lfloor\dfrac{a_i}{L}\right\rfloor\)，所以可以得出 \(\left\lceil\dfrac{a_i}{R}\right\rceil = \left\lfloor\dfrac{a_i}{L}\right\rfloor\)，所以一定合法。
若 \(L_0 < R_0\)，那么一定有 \(\dfrac{a_i}{R} < \dfrac{a_i}{L}\)，则 \(\left\lceil\dfrac{a_i}{R}\right\rceil - \left\lfloor\dfrac{a_i}{L}\right\rfloor\) 最大也只可能是 \(1\)，而这是唯一一种不满足条件一的情况。那么假如我们现在有若干 \(\left\lceil\dfrac{a_i}{R}\right\rceil - \left\lfloor\dfrac{a_i}{L}\right\rfloor = 1\)，我们要对 \(L, R\) 进行一些调整，使它合法。我们容易计算出 \(R\) 增加多少，或 \(L\) 减少多少后，能够使得这个差 \(\le 0\)。那么我们现在相当于有了 \(m\) 条限制 \((x, y)\)，形如 \(L \le x\) 或 \(R \ge y\)。这个问题我们只需要排序后，枚举 \(L\) 的值，\(R\) 一维贪心选择即可。

T2 属实没看懂题解，官方题解啥都不证明，比较难蚌埠，遂咕之。

T1 (CF1184D2 Parallel Universes (Hard))

我们有一个非常暴力的 DP，设 \(f_{u, i}\) 表示当前有 \(u\) 个宇宙，当前所在宇宙在第 \(i\) 个，结束期望时间。转移容易写出来，发现带环，可以高斯消元解出，复杂度 \(O(m^6)\)。

考虑减少状态。显然注意到矩阵稀疏，考虑递推系数一类的东西简化方程。具体来讲，我们可以将每一个数表示为 \(f_{u, 2}\) 的线性组合，然后我们再根据 \(f_{u, 2}\) 的转移方程可以列出一个只与 \(f_{u, 2}\) 有关的方程组，直接解这个方程组即可，然后再把要求的 DP 值直接代入求值即可。复杂度 \(O(m^3)\)。

貌似很多人都叫这种方法为主元法？我不知道我在哪里听到的递推系数（

T3 (CF1434E A Convex Game)

我怎么这么多题都没有写题解啊。草。

首先我们肯定要求 SG 函数，要不然 \(n\) 个组合游戏博弈没啥好办法做。我们有一个暴力的 DP \(f_{n, i}\) 表示最后一个选择的是 \(a_n\)，上一个选择的数为 \(i\) 的 SG 值，容易枚举下一步选择哪个数做到 \(O(n^3)\) 转移，总的 SG 直就是从每个位置开始的 SG 值的 \(\mathrm{mex}\)，然后所有异或起来即可。

考虑优化。首先注意到一件事情，由于要求必须是凸的，那么实际上序列元素最多只有 \(O(\sqrt{n})\) 个。这意味着，SG 值的范围也仅有 \(O(\sqrt{n})\) 个。于是不难想到将 DP 一维与值域互换。我们记录 \(g_{n, x}\) 为最小的 \(i\) 使得 \(f_{n, i} \ge x\)，这样我们只对 \(g_{n, x}\) 进行转移。考虑什么情况下可以转移，对于三个数 \(i < j < k\)，必须满足 \(a_j - a_i < a_k - a_j\)，即 \(a_k > 2a_j - a_i\) 时才能转移，也就是说 \(f_{j, i}\) 仅能由 \(a_k > 2a_j - a_i\) 的 \(f_{k, j}\) 转移来。那么 \(f_{j, i} \ge x\) 相当于对于 \(y \in [0, x)\)，都必须存在一个 \(f_{k, j} = y\) 且 \(a_k > 2a_j - a_i\) 的 \(k\)。那么我们记 \(K_{j, y}\) 为最大的 \(k\) 满足 \(f_{k, j} = y\)，就有 \(g_{n, x}\) 等于最小的 \(i\) 满足 \(a_i > 2a_j - a_{\min_{y \in [0, x)} K_{j, k}}\)，我们只需要再维护出 \(K_{j, y}\) 即可。\(K_{j, y}\) 相当于每次对 \([g_{k, y}, g_{k, y + 1})\) 这段区间与 \(k\) 取 \(\max\)，那么我们需要支持区间 \(\max\)，单点查询，直接用线段树维护可以做到 \(O(n \sqrt{n} \log n)\)。显然 \(k\) 是单调递减的，所以实际上我们每次是覆盖所有没有被覆盖过的区间，直接拿并查集维护即可 \(O(n \sqrt{n} \ \alpha(n))\)。

把 T2 过了，T1 由于是 APIO2023 讲的题，但是我并没有去，所以成功的签到失败了（

T1 怪兽 (树上 Monster Hunting)

大致题意：你有一棵树，\([2, n]\) 的节点上都有一只怪物，它会对你造成 \(a_i\) 点伤害，你打败它后会回 \(b_i\) 点血。任意时刻血量不能为负数。你需要决定一个打怪物的顺序，使得你存活下来所需血量最少，输出这个血量。你不能经过一个没有被打败的怪兽去打另外一只怪兽。\(n \le 10^5\)。

首先如果没有树的限制，你是可以直接贪心的。对于两只怪兽，容易判断出先打哪只更优。我们根据此可以建立出一个全序关系。那么如果有树，我们倒着去考虑。如果某个节点当前是全序关系中最优的，那么假如这个节点的父亲节点被攻击后，它一定是下一个被攻击的。也就是说，它和父亲节点一定是一起被攻击的。那么我们就可以把两个节点合并在一起。这样，我们用并查集维护，每次将最优的与父亲合并，就能得到最后答案了。

T2 切割

大致题意：给你个字符串，每次询问其子串有多少种切割方式，使得两个串均为回文串。\(n \le 2 \times 10^5\)。

首先有一个经典结论，就是一个串的后缀回文串的长度可以被划分成 \(\log n\) 个等差数列。

那么我们可以直接对前缀与后缀找出这些等差数列，需要用到 PAM，然后每次求两个等差数列中加和等于 \(n\) 的有多少。这是一个二元不定方程的形式，直接 exgcd 求即可。

T3 导弹

大致题意：有 \(n\) 个点在数轴上，坐标分别为 \(a_i\)，你从第 \(k\) 个点开始，按某种顺序遍历 \(n\) 个点。你每单位时刻可以走一单位距离。最小化到达每个点的时刻之和。\(n \le 3 \times 10^5, m = \max a_i - \min a_i \le 10^6\)。

首先有一个最暴力的区间 DP，记录当前到达的最左、最右的点与当前的时刻，可以做到 \(O(n^3m)\) 转移。首先记录当前时刻是没有意义的，考虑费用提前计算，我们每走一步就直接将当前没有经过的所有点的贡献提前加上，然后就能做到 \(O(n^2)\) 了。

还能接着费用提前计算。我们先把当前点到每个点的距离全部加上，然后我们每次向右走 \(d\) 距离时，左边没有被经过的所有点的费用都增加了 \(2d\)，同理向右走时右边的所有点的距离也都增加了 \(2d\)。于是我们发现，此时向左走与向右走造成的贡献独立开了。那么我们就只需要记录 \(f_i, g_i\) 表示走到了左边第 \(i\) 个，右边第 \(i\) 个时的最小费用，转移类似于 \(f_i = \min\{g_j + 2(a_j - a_i) (n - j)\}\) 一类的东西，发现这个东西是可以斜率优化的，动态维护 \(f_i, g_i\) 的凸壳即可。这个转移的顺序可能比较怪，这是一个类似于最短路的东西，所以我们可以用 Dijkstra 的方法，每次找到左右最小的值进行转移即可。

这题不太想评价。题面写的非常诡异，而且题目难度排序也很诡异。

T1 (CF1023G Pisces)

你管这叫 T1？

首先我们可以根据鱼是否可以相互到达建出一个 DAG，具体来讲就是 \(x < y\) 当且仅当 \(\mathrm{dis}(x, y) < d_2 - d_1\)。那么，我们要求的其实是这个 DAG 的最小链覆盖，根据 Dilworth 定理可以变成求最长反链。

考虑利用树的性质，我们能够得出以下结论：一个集合 \(S\) 为反链，当且仅当：

对于当前根的所有子树 \(v\)，\(S \cap \mathrm{sub}(v)\) 为反链；
存在一个时刻 \(T\)，满足 \(S\) 中每个鱼 \((u, d)\)，都有 \(|T - d| < \mathrm{dis}(u, root)\)。（即每个点都不能到达根，也不能从根到达这个点）

充分性比较直接，由于每个子树内都是反链，那么只用考虑子树之间的关系，那么对于两个点 \(u, v\)，有 \(\mathrm{dis}(u, v) = \mathrm{dis}(u, root) + \mathrm{dis}(v, root) > |d_u - T| + |d_v - T| \ge |d_u - d_v|\)，那么说明这两个点不能互相到达。

必要性证明咕了，感性理解一下（

那么我们可以根据这个来 DP 了。我们设 \(f_{u, T}\) 表示以 \(u\) 为子树，所有点都不能到 \((u, T)\)，此时的反链最大多少。对于转移来说，每个子树之间是独立的，那么我们只需要考虑每个子树的贡献即可。先不考虑 \(v\) 上的鱼，那么我们距离根的距离增加了 \(l\)，时刻也就可以相应的增加 \(l\)，那么贡献就相当于 \(g_{v, T} = \max_{i\in[T - l, T+l]} f_{v, i}\)。此时考虑 \(v\) 上的鱼，它能加入的条件是 \(|T - d| < l\)，即 \(d \in (T - l, T + l)\)。发现这个东西恰好与上面的转移范围差一个 \(1\)，所以我们可以考虑先将上面转移一个 \(1\)，然后将 \(v\) 上的鱼加到对应点值上，然后再转移剩下的 \(l-1\)。

有个问题就是 \(T\) 不一定是整数，但是发现 \(T\) 只能是 0.5 的倍数，所以给 \(T\) 和所有边权都乘 \(2\) 即可。

然后考虑怎么优化这个转移过程。容易发现子树内的 DP 值的数量与子树大小有关系，不难想到维护连续段与树上启发式合并。但是直接维护连续段好像并不好处理 \(\max\) 的转移过程，我们考虑维护差分数组。这样，拓展 \(l\) 位相当于将所有正数向左移动，负数向右移动，若一正一负重叠之后会相互抵消。我们可以拿堆维护每相邻两个正负之间的距离，然后拿 map 维护值，拓展时只需要打标记，然后每次找到距离最小的看是不是相交了，就可以均摊 \(O(\log n)\) 了。