十些做过的题

· · 个人记录

[Ynoi2002] Goedel Machine

题意：给一个数列，每次询问一个区间，求这个区间所有非空子集的最大公约数的乘积。n,q,a_i\le 10^5。

sol：

这题突破口在于：p\le\sqrt{w} \land p^k\le w 的 p^k 只有 O(\sqrt{w}) 种。证明是显然的，但性质却是不易想到的。

树上游戏

题意：一棵树，每个点有颜色，s(i,j) 表示 i 到 j 路径上的颜色数。对每个 i 求 \sum\limits_{j=1}^n s(i,j)。n\le 10^5。

sol：

统计所有树上路径对应贡献，应该想到点分治。

这题里，稍微推一推就能推出一个合理做法。

值得一提的是，这题有一个比较巧妙的 O(n) 做法。

考虑按颜色算贡献，枚举一个颜色 c。

把该颜色的点删掉后，剩下若干个连通块，对于每个点，应加上 n- 所在连通块大小。对于 col_u=c 的点，我们应该定义其所在连通块大小为 0。

我们考虑将贡献在连通块的顶点（最浅点）处处理，然后以树上差分的形式传递到连通块内所有点。这么做的原因是：若 u 不是根，且为顶点，那么枚举到的颜色必定是 col_{fa(u)}；且在顶点处计算连通块大小是容易的。

而对于根作为顶点的贡献特殊处理（假装根的父亲有所有颜色）。于是我们就能一遍 dfs 求出每个点作为顶点的连通块大小，一遍 dfs 差分传递下去了。

[JSOI2018] 战争

sol：模板闵可夫斯基和。stl 里有 double atan2(double y,double x)。值域是 (-\pi,\pi]。所以闵可夫斯基和的时候起点要选择凸包上 y 坐标最大中 x 坐标最小的点。

某模拟赛 T3 金属化

题意：前往顶点全局版。一棵树，初始每个点有一个棋子，经历了 m 次操作形如：所有棋子向 u 方向移动一格（在 u 则不动）。求最后每个棋子在哪。n,m\le 2\times 10^5。

sol：今天竟然做到了 3e5 的前往顶点，不知道正解是什么。这个是弱化版。

lxl 当时说的做法非常魔怔，就是分块映射，每一块建虚树，用双端队列维护虚树上每条边含有的棋子情况。单根号。我当时写过一个，但是不知道怎样实现“空白格”，就只有硬加入，导致空间也是 O(n\sqrt{n}) 的，再加上各种大常数，我当时写的那个时空都非常劣，又巨大难写。跑不过暴力来着。

你也可以把注意力放在“合并”的迅速上，考虑形式化刻画出来：

只看有棋子的点构成的虚树，可证明所有时刻叶子个数之和是 O(n) 的，因为若某一个时刻有 x 个叶子，那么下一时刻必定会有至少 x-2 个节点被合并。

如果我们能维护出虚树的形态（缩二度链），操作就可以暴力做了。直接做也是非常难做。不妨考虑维护静态的链。

树剖后，只考虑有棋子的重链，那么所有时刻重链个数之和为 O(n\log n)。每个重链维护一个平衡树就能处理棋子的流动了。双 log，很好写，常数小，空间线性。

某模拟赛 T1 重排

题意：给定由 12 组成的序列 a,b，每次可以交换 a_i,a_{i+1}，代价为 C+a_i+a_{i+1}，或交换 a_i,a_{i+2}，代价为 C+a_i+a_{i+1}+a_{i+2}，求 a 变成 b 的最小代价。

sol：形式化问题。集中关注困难。发现显然性质，然后解决。

某模拟赛 T1 最短路

题意：求一个错误的 floyd 算出的最短路矩阵。n\le 2000,m\le 3000。

sol：结论如果是递归的，也不要怕！看看能不能归纳出来。

某模拟赛 T3 欧拉

题意：给出一个无向图，如果一个边集的导出子图是欧拉图，那么该边集 S 的贡献是 |S|^2，否则为 0，求所有边集的贡献和。n,m\le 2\times 10^5。

sol：

考虑边集导出子图欧拉图计数：设 c 为连通块数，则答案为 2^{m-n+c}。因为任意选取一棵 dfs 森林，每个非树边的选择方案唯一确定了一组树边的选择方案。这种度数的问题可以想想 dfs 树上的自底向上确定。

那么贡献为 |S|^2，就变成枚举两个边，问有多少边集包含它们，且导出子图为欧拉图。首先若任意一者是割边则不行。否则考虑断开两边是否使得连通块加一，若不使得且两边不相同，贡献为 2^{m-2-n+c}，否则贡献为 2^{m-1-n+c}。

考虑判定断开两个边能否使连通块加一，这个问题可以给每个非树边赋一个随机值，然后其覆盖的树边都异或上这个值。能使连通块加一当且仅当两边哈希值相同。

[CQOI2018] 九连环

题意：n 连环最少需要几步解下？输出答案，不取模。n\le 10^5。

sol：

通过这题了解到了规则：记 n 位二进制 msk 表示每个环是否在上面。每次操作可以异或 1 或者 2\cdot lowbit(msk) 。

--- **[CF1067D Computer Game](https://www.luogu.com.cn/problem/CF1067D)** 题意：有 $n$ 个关卡，一次挑战成功的概率为 $p_i$，初始时的关卡通关收益为 $a_i$，每次挑战成功后可以指定一个关卡，升级它的收益为 $b_i$。求 $t$ 次操作的期望收益最大值。$n\le 10^5,\t\le 10^{10},1\le a_i<b_i\le 10^8$。 sol：最优化期望，我们一般要找出一个强策略。 这题里，升级是幌子，一旦获得升级机会，我们就会升级 $p_ib_i$ 最大的，然后此后一直选它，每轮获得 $c=p_ib_i$ 的期望收益。 考虑获得机会前的决策，设还剩 $t$ 步时的最大收益为 $f_t$： $$f_t=\min\limits_i\{(1-p_i)f_{t-1}+p_i(a_i+(t-1)c)\}$$ $$f_t=\min\limits_i\{p_i((t-1)c-f_{t-1})+p_ia_i\}+f_{t-1}$$ 我们的直觉是：步数多的时候倾向选 $p_i$ 大的，少的时候倾向选 $p_ia_i$ 大的。事实上也确实如此。 $(t-1)c-f_{t-1}$ 是单增的，因为一轮的期望收益不会超过 $c$。那么把对 $i$ 的决策看成一个横坐标上的最高直线，每条直线形如 $y=p_ix+p_ia_i$。 类似二分队列地维护出每个决策点的作用范围，在每个范围内矩乘转移即可。$O(n\log t)$ 但是被卡精度了。没有精度问题的提交貌似大多是双 log 的。 --- **[CF1672I PermutationForces](https://www.luogu.com.cn/problem/CF1672I)** 题意：给定一个排列 $p$，每次删除一个位置 $i$，然后右边的位置左移一格（下标减一），大于 $p_i$ 的数减一。求一个操作顺序，最小化所有 $n$ 次操作的 $\max|i-p_i|$。$n\le 5\times 10^5$。 sol： 容易想到把 $(i,p_i)$ 画在平面上，但是删除一个点的影响不一定是变优 or 变劣。 但有一个关键性质：设删除了 $x$，变劣的点总是变劣 1，并且这些点操作前一定满足 $|i-p_i|<|x-p_x|$。也就是说，如果确定了 $\max|i-p_i|$，那么每次可以随意操作一个合法点。 为了规避二分答案，考虑每次删除 $|i-p_i|$ 最小的点。 注意力还是不够集中，没能发现性质。做题的时候注意力集中啊！就能发现关心的只是 $\max$ 。 --- **[[IOI2021] 地牢游戏](https://www.luogu.com.cn/problem/P8522)** 题意：$n$ 个地牢，第 $i$ 个里住着血 $s_i$ 的怪物，进入时若能力值 $\ge s_i$，能力值增加 $s_i$ 并进入 $w_i(w_i>i)$；否则能力值增加 $p_i$ 并进入 $l_i$（不保证 $l_i>i$），一旦进入 $n$ 号地牢则游戏结束。$q$ 次询问在 $x$ 号地牢出生，初始能力值为 $z$ 的情况下最后能力值是多少。$n\le 4\times 10^5,q\le 5\times 10^4, s_i,p_i,z\le 10^7$。 sol：倍增值域分块的入门题。 战胜关系时刻变化很烦，我们考虑把能力值分成 $[2^w,2^{w+1})$ 的若干块。 对于 $s_i\le 2^w$，一定能战胜； 对于 $s_i>2^w$，战胜后一定进入下一块。 那么我们可以倍增地跳完“不能进入下一块”的步数，因为这部分步数中输赢已经确定了。 具体地，对每块维护 $to(i,j)$ 表示 $i$ 跳 $2^j$ 步到达的点之外，再维护两个值：$g(i,j),lim(i,j)$： 表示这 $2^j$ 步的收益（当成不能进入下一块）。 以及跳完 $2^j$ 步会进入下一块的最小能力值（即若在 $i$ 时能力值 $\ge lim(i,j)$，那么这 $2^j$ 步会进入下一块，不能跳）。 设步数为 $L$，其可以到达 $O(V)$，但是数据中比较小，这样做是 $O((n+q)\log V\log L)$，空间也是两个 log。很不优美。 我们考虑能不能换底，划分成 $[B^w,B^{w+1})$。 发现这时，吃到至多 $B-1$ 次 $s_i> B^w$ 就会进入下一块。 那么 $lim(i,j)$ 定义改成：这 $2^j$ 步至少能战胜一个 $s_i> B^w$ 的敌人的最小初始能力值。 然后每次跳完输赢确定的步数，这样就变成了 $O(n\log_BV\log L+qB\log_B \log L)$，非常优美。 --- **[[ARC179D] Portable Gate](https://atcoder.jp/contests/arc179/tasks/arc179_d)** 题意：你可以选择一个起点来遍历树，你有一个传送门，你可以传送到传送门所在节点，或者把传送门传送到你所在节点，或者平凡地走过一条边。只有走一条边消耗 1 的时间，传送不消耗时间。求遍历整棵树的最短时间。$n\le 3\times 10^5$。 sol：冷静地分析，才会发现我担心的不好处理的情况并不会发生。 题目形式很显然是典典树 dp。但是在这之前需要认真的考虑。 我担心的状况是会不会传到子树外面，然后再走进来这样之类的。 发现是不会的，因为可以调整为：第一次进来的时候把传送门放到子树的根（$u$），最后跳出去的那一步 换成 跳到 $u$ 再走上去。 于是我们发现走到子树 $u$ 的时候无非两种情况：“带着门”/“没带门”。 再形式化一点，可以把操作变成这仨：背着门走一步，不背门走一步，传送到门。 对于子树维护四个信息：(1) 不带门，要走回根；(2) 不带门，无需走回；(3) 带着门，门最后要在根；(4) 带着门，门最后不必在根。 对这个做换根 dp 即可。 --- **[CF1693D Decinc Dividing](https://www.luogu.com.cn/problem/CF1693D)** 题意：一段序列是“好的”，当且仅当它能划分成一个上升子序列和一个下降子序列。给一个排列，求“好的”字段的个数。$n\le 2\times 10^5$。 sol： 判定问题是简单的 dp：$f_{i,0/1}$ 表示末尾分在上升/下降 时 另一个末尾的最大/最小值。 双指针看似移动左端点不好更新，但是由于“好的”的限制非常强，一个神奇事情是 $f_{i,0/1}$ 都只有 $O(1)$ 个取值，又由于 dp 值关于左端点单调，所以暴力更新是线性的。 具体的，考虑最大的 $j$ 满足 $j<i,a_j>a_{j+1}$，那么 $f_{i,0}$ 只有可能是 $a_j,a_{j+1}$ 正负无穷这四种值。 另一种思路是发现充要条件：没有 3412，也没有 2143。 --- **[小 Y 和恐怖的奴隶主](https://www.luogu.com.cn/problem/P4007)** sol：矩乘板子。记录一下是因为收获一个卡常技巧：矩阵乘向量如果初始向量比较稀疏，那么跳过向量中的 0 可能有较好的优化效果。 --- **[某模拟赛 T3 序列](http://haoba.vip/d/Contest/p/P272)** 题意：给定一个序列，每次操作可以给一个 $a_i$ 减一，求最小操作次数使得序列交错。即 $\not\exists 1<l\le r<n$ 满足 $a_l\sim a_r$ 全相等 且 $(a_l-a_{l-1})(a_{r+1}-a_r)>0$。$n\le 5\times 10^5,a_i\le 10^9$。 sol：好题。 考虑把序列划分为若干个相等段，那么相邻的相等段就是一个在上一个在下。 最优策略肯定是：先把所有段都减到段内最小值（做成“相等”），然后在下面的段如果被左右的上面段限制，就再往下降一降。 我们发现贡献与段内最小值有关，所以我们可以在段内最小值的位置进行 dp。例如：$f_i$ 表示考虑了 $1\sim i$，钦定 $i$ 为一个上面段的段内最小值，从 $j$ 转移过来的时候考虑把 $(j,i]$ 整成“上下上”的最小代价，记为 $w(j,i)$。 $w(j,i)$ 可以通过分类讨论 $O(1)$ 求得，需要一个性质：下面段如果被左右的上面段限制，那么它的长度只能为 1（否则把两端划到上面段一定不劣）。 但是 $w$ 并不满足四边形不等式，一个优秀的直觉是：不满足决策单调性时，相等段不会太长，我们可以只转移前面 500 个，**同时**装作它是决策单调的，做一下二分队列。这样的做法貌似很难卡。 实际上，段的性质特别好，正解是对其性质进一步考察。 --- **[[AGC061F] Perfect Strings](https://www.luogu.com.cn/problem/AT_agc061_f)** 题意：一个 01 串是**好的**，当且仅当其 0 的个数是 $n$ 的倍数，1 的个数是 $m$ 的倍数。一个串是**完美的**，当且仅当它是**好的**，且它的所有字串都不是**好的**。给定 $n,m$，求**完美的**字符串的数量。$n,m\le 40$。 sol：比较具有启发意义的题。 考虑对判定条件进行一个好的转化： 在 $n\times m$ 个格点的循环网格图上向右向下走，不经过重复点，从 $(0,0)$ 出发走回 $(0,0)$ 的路径数。 一个比较好的处理 $(0,0)$ 的方法是：舍弃这个限制，改为从任意点出发，最后除以 $nm$。现在问题相当于：对于每个简单环，对答案都有环长的贡献。 考察简单环的形态，如果确定了有 $i$ 次从右边界会到左边，$j$ 次从下边界回到上边，那么环长就为 $im+jn$。同时我们要满足 $\gcd(i,j)=1$，否则会形成多个环。 且这时 左上边界 和 右下边界 都各有 $i+j$ 个“接口”，路径的形态一定是不交叉地让 左上接口 和 右下接口 顺次匹配。 如果枚举了接口，可以 LGV 求答案。但是不能枚举，我们就要寻求状态之间的等价性。 最基本的，我们至少要知道二元组 $(i,j)$，发现如果知道了 $(i,j)$ 对应的不相交路径组方案数，也就可以求答案了。 引入变元 $x,y$ 来刻画 $i,j$，额外建立边：$(-1,i)\to (0,i)$ 边权 $x$；$(m-1,i)\to (m,i)$ 边权 $1$；$(-1,i)\to (m,i)$ 边权 $1$（表示不用这个接口）。列上同理。 起点集就是左上边界，终点集就是右下边界，跑 LGV 后提取 $[x^iy^j]$，但要注意先抵消掉标号方式给 $[x^iy^j]$ 带来的 $(-1)^{\pi(p)}$。一个排列插入若干直接匹配逆序对奇偶性不变，所以标号时保证对面标号相同，那么 $\pi(p)$ 的奇偶性就可以由 $(i,j)$ 推出了。 提取 $[x^iy^j]$ 直接插值即可： $$f(x,y)=\sum val(i,j)\prod\limits_{k\neq i}\frac{x-k}{i-k}\prod\limits_{l\neq j}\frac{y-l}{j-l}$$ 构造原理和一维情况是相同的。也可以看成插值两次。这样是 $O(nm(n+m)^3)$。存在高贵的特征多项式的四方做法。 --- **[[ABC355G] Baseball](https://www.luogu.com.cn/problem/AT_abc355_g)** 题意：$1\sim n$ 中随机选一个 $y$，选中第 $i$ 个点的概率是 $p_i$。给定 $K$，你可以在 $1\sim n$ 中选择恰好 $K$ 个关键点，最小化 $y$ 到最近关键点的距离的期望。$K\le n\le 5\times 10^4

sol：划分段 dp，考虑能不能对段数 K wqs 二分，这么经典的处理方法竟然忘了！