一些例子

清仓甩卖

1. 我们需要观察到最优策略可以被反悔贪心求出的性质。
2. 我们需要刻画反悔贪心涉及到的关键元素。做到这一步可以获得 $O(n^3)$ 或 $O(n^4)$ 的复杂度。
3. 我们需要化简组合式子，并做到 $O(n^2)$ 的复杂度。

1. 没有观察到 / 观察错误第一步性质。
2. 没有成功刻画 / 刻画错误第二步。
3. 没有化简成功第三步的式子。

员工招聘

1. 关键性质：一个人是否逃掉当天的面试，只在于之前不录取的人数。这使得我们可以按照不录取的人数划分阶段。
2. 设计 dp：设计 $f_{i,j,k}$ 表示目前是第 $i$ 天，不录取了 $j$ 个人，此时耐心 $\le j$ 的人中，有 $k$ 个已经被录取。
3. 规划转移：严格按照 $j$ 分层转移会获得 $O(n^5)$ 且 $80$ 分的好成绩，别问我怎么知道的。如果按照 $i$ 转移可以 $O(n^3)$。

树的价值

$O(n^3)$

使用延后贡献的思想。设计状态为 $f_{i,j,k}$ 表示树上第 $i$ 个点的子树内，填数使得这个子树中节点权值集合的 $\mathrm{mex}$ 等于 $j$，且还剩下 $k$ 个数没填写。子树 $i$ 的总答案。

对于转移，做树形背包，对子节点 $v$ 转移 $f_{i,\max(j1,j2),k1+k2} \leftarrow f_{i,j1,k1} + f_{v,j2,k2}$。其中 $\max(j1,j2)$ 需要 max 卷积支持。

$O(nm^2)$

考虑优化，我们定义一条边 $(i,v)$ 是实边，则这个点 $i$ 的 $j$ 由 $v$ 转移，其余边定义为虚边。

显然若确定了实边，类似树链剖分，实边形成了若干条链。考虑再次计算每一个点对答案的贡献，容易发现，这个点会存储一点“能量”，并且向上传递。

$i$ 一直向上跳，当其到达某一个点（它的祖先）之后可以选择“使用”这点能量，对这个点一直到第一次出现虚边的位置增加一条贡献。

容易发现 $i$ 到根的路径上最长的相邻两个虚边的距离（根和 $i$ 点特例）即为 $i$ 对答案的贡献。

如果直接设计 $f_{i,j,k}$ 为钦定 $i$ 点到根的路径上最长虚边距离为 $j$，当前 $i$ 向上的最近虚边的距离是 $k$，只考虑子树 $i$ 内的总答案。

仍然从下往上 dp，但是时间复杂度为 $O(nm^2)$。

状态优化

拆分 dp 状态为 $f_{i,j}$ 和 $g_{i,j}$。重新开始定义。

$f_{i,j}$ 为强制钦定 $i$ 点是我们剖分的链头，上方最长虚边距离为 $j$，$i$ 子树内答案。

$g_{i,j}$ 为 $i$ 点是一条链中的第 $j$ 个部分，认为 $i$ 点离上方最近虚边距离已经足够长（就是 $j$ 足够大），$i$ 子树内的答案。

$f_{i,j}$ 需要枚举 $i$ 子树内的其中一个点，其到 $i$ 距离为 $j$，记这个点为 $l$。$i$ 到 $l$ 的路径是实链。

则实链上点的其他儿子 $v$ 是虚边，这些儿子的答案由 $f_{v,j}$ 给出。

而 $l$ 点的贡献为 $g_{l,j}$。

此时理论枚举量已经得到 $O(nm)$。问题在于如何快速计算这么多权值的和。

从出题的角度看

难题的迷惑性

难题的复杂性

刻意构造

妙手偶得

二者兼备

一种分析

“探究”是什么

一种理想化的学习方式

描述 / 刻画是一种探究

推理是一种探究

如下

首先考虑怎么知道所有 $b_i$。我们作 $b$ 的前缀和 $s_i$。相当于知道 $s_1,s_2,...,s_n$ 就可以还原了。

则问 $[l,r]$ 可以知道 $s_r-s_{l-1}$。发现相当于知道 $s_r$ 就可以知道 $s_{l-1}$，反之亦然。

连一条双向边 $(r,l-1)$，显然我们是知道 $s_0$ 的，问题转化为 $0$ 可以到所有点，也就是图连通，最小的话就是图的最小生成树。

问题变成最小生成树，在 $(l,r)$ 之间连边代价是 $\gcd(a_{l+1},...,a_{r})$。

观察 / 实践是一种探究

联想是一种探究

猜测 / 实践是一种探究

与上述“难题”的关系

探究的缺点

怎么获得探究的动力

我出的几个题

星命定轨

天阶梦游

演剧