07

CF1515E Phoenix and Computers

DP

考虑最终答案一定是手动开一段+空一个+手动开一段+空一个。

然后考虑怎么计算手动开 $N$ 个的方案数。

考虑可以以中间任意一个为起点。开始放置。

最终答案手动开 $n$ 个的方案数为 $2^{n-1}$ 。

最终总的方案数再加一层DP即可。

CF797E Array Queries

根号分治

考虑根号分治。因为每次增长幅度与 $k$ 相关。一般情况下考虑

对于 $k < \sqrt{n}$ 的进行预处理

对于 $k > \sqrt{n}$ 的进行暴力。

最终复杂度为 $O(n\sqrt{n})$

ARC066E Addition and Subtraction Hard

DP

考虑题目转化。

可以转化为负数可以将后面的一段数反转。但当前数不反转。

很容易的想到使用dp求解。

定义 $f_{i,j}$ 表示 前 $i$ 个 中有 $j$ 个左括号（类似的东西）。这样一般的dp的复杂度为 $O(n^2)$

但是考虑 $n$ 较大，观察题目性质，我们发现当 $j$ 在较大时没有影响。可以直接优化。这样以来 dp 复杂度降至 $O(n)$

P4363 一双木棋 chess

轮廓线DP

考虑轮廓线DP。

主要是可以考虑定义 $f_{i}$ 表示当前局面距离答案最大值。

可以将答案转化为 $f_s$ 。

另外是这种 $dp$ 通常来说记忆化搜索来做。可以变得更加好写。

然后使用记忆化搜索。保证复杂度在 $2^{n+m}$ 以内。

模拟赛#1T4 子段mex值计数

mex

首先是范围的一个提醒。考虑 $2*10^6$ 也是可以带 $1\log$ 的。

这道题可以考虑转化。

定义一个 $seq$ 。对于 $seq(r, x)$ 表示以 $r$ 为右界，$\DeclareMathOperator{\mex}{mex}\displaystyle{ \mex_{l, r} a_i \geq x}$ 的最大的 $l$

我们考虑 $x$ 每次增大，$seq_r$ 的数组是不严格单调递减的。

另一个性质是，整个 $seq$ 数组时刻保持不严格单调递增。

所以我们可以用线段树维护整个 $seq$ 数组。在每次 $x$ 变大时的变化。

对于一次变化我们可以把所有 $a_i = x$ 的坐标都拿出来 $q_1, q_2, q_3, ...$

对于 $q_1$ 前面的数可以直接设为 $0$ 。对于 $> q_i$ 且 $<q_{i+1}$ 的设为 $q_{i}$ 剩下的就是线段树只要维护一个最大值和一个和即可以在 $O(n\log n)$ 复杂度内解决求和 & 求upper_bound问题。（由于递增）

CF1260D A Game with Traps

二分答案 #策略

不难发现可以二分答案。（吸取之前教训）

然后我们考虑怎么走是最优的。（也就是这道题重点部分）

我们发现带多少人就决定了需要清除哪些陷阱。

我们可以发现。对于陷阱的 $l_i$ ~ $r_i$ 这些点必然需要要花 $3$ 次。因为首先要先到达 $r_i$ 1次 然后返回一次 然后还需要带着部队走一次。我们发现对于所有陷阱的 $l_i$ ~ $r_i$ 都需要这么计算。那我们最终维护一个差分即可。

这道题告诉我们：很多东西可以考虑结果时的贡献，而不太考虑其中的过程。

模拟赛#2 T3 str

策略

可以看成开头删一段 结尾删一段。考虑两个数组是单调的。所以可以维护双指针来完成。

模拟赛#2 T2 stock

矩阵加速 #容斥原理 #DP

不难得到与 $T$ 相关的 $dp$ 式子。我们考虑时间为 $O(Tn)$

当 $T$ 很大时，不难想到矩阵加速。就可以统计。

但是矩阵加速时的状态比较多, $k = 2^c*n*2$ 但是矩阵乘法复杂度是 $O(k^3)$ 的。所以考虑怎么优化状态。

这个时候我们需要考虑到 容斥原理。我们发现可以限制条件：每次要求不采集某些点。这样得到的答案就是所有保证不采集某些点的答案。通过容斥原理可以得到所有的不符合条件的方案数。将所有方案数减掉不符合的即为符合的。这样每次的 $k$ 就变成 $2*n$ 了。

容斥原理的性质：降低复杂度，增加条件。

在本题中的体现是缩小状态数量，增加次数。

P4099 [HEOI2013] SAO

树形DP

主要是考虑转移。本题要考虑转移

$f_{u, i}$ 表示当前 $u$ 点有 $i$ 个

08

P9493 「SFCOI-3」进行一个列的排

mex

还是一个mex的题。这道题有一个关键的需要猜测的性质。就是说我们每一次加一个新的数只会考虑加在前面，或者加在后面，否则就是不合法的。而L的条件可以转化成，只要当前左边有 $L_i$ 个或者右边有 $L_i$ 个即可。

完成这一步性质之后，就是一个dp问题了。

复杂度为 $O(Tn^2)$

P6772 美食家

矩阵加速

很标准的矩阵加速。但是我们考虑要分成 $k + 1$ 段，但是矩阵乘法带一个 $k^3$ 。

但是考虑其中有很多相同的只是每次 $[]^k$ 中的 $k$ 不同。再加上我们向量乘以矩阵是 $n^2$ 的。所以我们可以考虑对矩阵在一开始进行预处理。使得查询的复杂度降到 $O(k * \log k * n^2)$ 预处理复杂度是 $O(\log k * n^3)$ 最终加在一起符合题目要求。

虽然说可能看起来还是比较大，但是由于矩阵常数很小。所以可以过。

CF1849E Max to the Right of Min

笛卡尔树

第一道笛卡尔树。意识到笛卡尔树时可以在树上和数列上交互着看。

本题做法是（我们可以考虑一边）

考虑根左边这些数（在数组上）时考虑右边有哪些是符合条件的。我们发现是对于 [root, x) x 是第一个小于左边 [left, root] 这些点的最小值的是当前点的答案。

考虑其实 [root, x) 相当于左边这些点中最小值右侧的第一个小于当前值的数和 r 取 min 。

最终我们可以通过单调栈初始化这一过程。

然后本题中另一个问题是任意一颗二叉树在任意形态下，在仅仅便利左右子树中小的那一颗时 总的复杂度时不会超过

T(n) = T(n / 2) + T(n / 2) + n ，与 O(nlog n) 同阶。

CF1580B Mathematics Curriculum

笛卡尔树 #DP

我们考虑题目转化，即生成一颗大小为 n 二叉树。要求在深度为 m 处有 k 个点。

那么我们对于这样的要求生成二叉树的计数DP题我们可以考虑定义子树大小。然后我们分别来看子树结构，以及子树内部的分配问题。我们发现我们可以考虑到只需要关心到左侧我们子树个数，右侧子树个数即可。然后其中任意选数到左侧，然后选数到右侧。

另外我们有限制，所以我们也需要关心深度 j, 然后关心在深度为 m 处有 k 个点怎么处理。

定义即为 $f_{i,j,k}$ $i$ 表示大小，$j$ 是深度， $k$ 是指带第 $m$ 层的节点个数。

最后比较逆天的是这题复杂度 $O(n^5)$ 需要一些比较高明的卡常。

卡常地址

CF1051F The Shortest Statement

最段路 #图 #树

是一个类似于树的东西。其实看到这个范围的时候就应该有敏感了把这个提炼一个树。然后考虑的。

我们可以考虑建一个生成树，然后剩下来最多 42 个点。我们考虑可以对每个点都跑一遍单源最短路。这样我们可以考虑做树上的最短路和这些最短路中找一个即 $dis_{s, u} + dis_{s, v}$ 。 既可以算出 $u -> v$ 的必定经过这个点的最短路。

这道题还有一个思考是 如果要考虑到图上的问题，我们一般、通常要考虑转化到树 / 拓扑排序。转化到树一般有一些性质：

• 缩点 / 缩边
• 考虑生成树
• 最短路树

最后是需要熟练dijkstra的写法，警钟敲烂。

模拟赛T3 lcm

lcm

一个经典lcm问题。具体要了解到一些性质。（基本上就是卡常技巧）

观察一些性质。

P2934 [USACO09JAN] Safe Travel G

最短路树

考虑最短路树之后。如果说不走最后一条边，说明必然走过一条非树边。然后每次子树内的点可以更新到其父亲。但是其父亲不能在两个非树边点的lca的上方（含）。原因是到u的时候一定会经过最后一条边。

权值计算 （x, y, i） 表示非树边 x,y 则有 $dis_x+dis_y+dis_{x, y} - dis_{i}$

所以可以按照前面那个 $dis_x+dis_y+dis_{x, y}$ 排序。然后挨个更新即可。可以通过路经压缩来保证每个点只会被更新一次。保证复杂度的正确性。

具体实现比较乐子。可以用dfs做 $O(n\log n)-O(1)$ 做。但是人足够脑瘫。抄这部分实现都抄错。

Acwing 290 坏掉的机器人

DP #DP套高斯消元 #高斯消元

考虑DP。但是由于每个点可以从左侧或者右侧来。有后效性。所以我们考虑

但是我们考虑到上下没有后效性。

具体上来说本题消元复杂度可以从 $O(n^3)$ 降到 $O(n)$ 原因是观察系数的矩阵，我们发现矩阵每行只有 $2$ ~ $3$ 项。可以省掉一个 $n$ 然后每次只消 $2$ 个也可以省掉一维。所以可以实现 $O(nm)$ 复杂度。

而且我们要考虑第二次扫的时候的顺序。具体问题可以翻错误的第二个for的顺序的提交记录重新思考。

09

9月份不知道在做什么！！！！警钟敲烂。

[ARC083E] Bichrome Tree

树

一道很好的树的题。主要是提醒我们可以通过观察一些特殊的树来转化整个题目。
通常情况下可以考虑从链 / 菊花图入手。

我们发现考虑链时可以考虑这样一种贪心：每个点就相当于从子节点处中选择一个离当前点最近的并且小于当前点的。最终将它改编成当前点的Xi。如果两个值都大于了Xi,就是IMPOSSIBLE。

然后我们发现了之后回到一般的树上考虑。我们发现对于每个点而言。一定存在两个值: Xi 和 一个值 k。发现每次凑到当前点的时候 k 越小越好。然后每次相当于从子树中选Xv, k中的一个。但是另一个的总和不超过 Xu。并同时希望另一个取得更小。

所以就转化成了一个01背包问题。但是是必然是一个作为重量一个作为权值。可以互相更改。