在 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)
在 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)\) 了。
T2 (P9312 EGOI2021 Lanterns / 灯笼)
T3 (CF1662J Training Camp)
这场 T1 恶心到我了,我手推的大 \(\sum\) 式子,然后结果题解说直接插值即可,乐(
T2 T3 都没改,所以这场咕了。
爆炸场,T1 我 \(10^6\) 跑平衡树,正解是线性
标签:Set,val,int,T2,Solution,T1,SImulations,我们,ally From: https://www.cnblogs.com/apjifengc/p/17546527.html