攻破难题的过程

· · 算法·理论

发现前两篇文章太胡扯了，写出来没啥用。于是写点实在的。

下文说的难题不一定很难。

一些例子

举一下 CSP/NOIP2025 的例子：

清仓甩卖

  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) 的 dp：

::::success[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 卷积支持。

::::

可以获得 48 分。

接下来是一个可以想到的钦定思想：

::::success[O(nm^2)] 考虑优化，我们定义一条边 (i,v) 是实边，则这个点 i 的 j 由 v 转移，其余边定义为虚边。

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

容易发现 $i$ 到根的路径上最长的相邻两个虚边的距离（根和 $i$ 点特例）即为 $i$ 对答案的贡献。 如果直接设计 $f_{i,j,k}$ 为钦定 $i$ 点到根的路径上最长虚边距离为 $j$，当前 $i$ 向上的最近虚边的距离是 $k$，只考虑子树 $i$ 内的总答案。 仍然从下往上 dp，但是时间复杂度为 $O(nm^2)$。 :::: 可以获得 $76$ 分。 接着是一个状态优化： ::::success[状态优化] 拆分 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)$。问题在于如何快速计算这么多权值的和。 :::: 后面使用长链剖分优化或者直接树状数组就可以通过了。 # 从出题的角度看 ## 难题的迷惑性 解题像走迷宫。如果凭借直觉就能探索到正确的路，那么这一步就无法坑害做题人。 ## 难题的复杂性 解题像走迷宫。如果路上没有难以推导，需要耐心才能跨过的障碍，那么只需要灵光一闪就如顺水行舟般做完整个题了。 ## 刻意构造 出题人会寻找难以想到的转化，然后编一个题出来，把已有的模型做巧妙的转化。 这种转化一般是一个 trick。 ## 妙手偶得 出题人通过各种手段从头开始编一个题出来，然后自行探究。 ## 二者兼备 可能出题人编的题不好 / 不可做，然后再通过刻意构造的方式修改？ 出题人通过探究自己的题目，为其加强 / 推广？ ## 一种分析 （我写完了才看到这个） [LCA 的博客](https://www.luogu.com.cn/article/iddgejd7)中：题目强度的向度。 但是我是还没退役的（希望不是快退役的）OI 选手，所以对我来讲，“冷度”和“科技度”并不是很重要。 # “探究”是什么 ## 一种理想化的学习方式 一种目标不是为了完成任务的学习方式。 探究不指向直接的积累，如：“看到什么，就要想到什么”这种套路。 探究的重点在于，研究模型并且尝试加以推广。 很多题目都是在探究中被出出来的。 探究的动力来源于对未知的好奇，也正因如此，它比较理想化。 对题目的兴趣因人而异，这也于“天赋”有关，当然我不是天赋哥，所以这里说的“探究”比较理想化。 接下来说的东西和“做题 / 比赛方法”有重叠。 ## 描述 / 刻画是一种探究 描述 / 刻画你所要探究的问题。 字面意义上讲，给你的问题画一幅画。 有很多描述的方式，比如用数学语言描述你的问题。 让我被数学语言所震撼的两个题解，[集合](https://www.luogu.com.cn/problem/solution/P13275)和[绝对防御](https://www.luogu.com.cn/problem/solution/P13276)。 把要解决的问题清楚的讲出来也是一种简单的描述。 用简单的模型把问题更好的讲出来是一种描述 / 刻画。 [双序列拓展](https://www.luogu.com.cn/problem/P9870)把题目刻画了在网格上移动的问题。 网络流题目也是建模思想。 ## 推理是一种探究 数学公式的推式子，或者是一些纯粹的把戏，都是推理的体现。 推理无处不在，而且也有很多很直觉，很简单的推理。 [我的这篇题解有很多简单的推理](https://www.luogu.com.cn/article/netrwqtc)。 ::::success[如下] 首先考虑怎么知道所有 $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})$。 ::::: 文化课学习中最常用的思考方式也是推理。 ## 观察 / 实践是一种探究 观察可以发现性质。性质可以简化 / 弱化我们的问题。 [树的遍历](https://www.luogu.com.cn/problem/P11363)运用了“可以生成某一棵树的根节点是一条链”这一性质。这基本是通过观察得到的。 这可能和实践有很大的重叠。但是观察重点在于直接看出性质是啥，猜测 / 实践主要是一个动态过程（边猜测边验证） ## 联想是一种探究 [回响形态](https://www.luogu.com.cn/problem/P14830)中，原题可以转化成回文串计数问题，使用马拉车解决。 结合一下文化课学习。函数大题中，构造一个我们需要的函数需要对其进行联想。 这种问题不仅需要**刻画**，而且需要把刻画后的问题与另一个已知可做的问题联想在一起。 ## 猜测 / 实践是一种探究 对模型进行实践（手玩或者是模拟算法，打表）可以帮助我们进行观察。 这是探究的一种很常规的表现方法。 猜测辅助实践。猜测的方向和个人经验相关，猜测和联想又有很大关系。 ## 与上述“难题”的关系 对症下药。 对于“刻意的”题目，注重联想。 对于“adhoc”题目，注重寻找性质。 对于“构造”题目，注重实践。 难以理解的问题，进行刻画。 ## 探究的缺点 探究法太激进，人脑可能会出错，接下来对两种情况进行修正。 失败陷阱：之前讨论过，你所知道的一条思维道路失败不一定是真的失败。 成功陷阱：之前讨论过，你所知道的一条思维道路成功不一定是真的成功。（也就是想假了） ## 怎么获得探究的动力 我刚才又开始胡扯了，那么怎么获得探究的动力呢？ 不知道啊，感觉我这几天状态都不是很好，比赛在一直爆零，有没有人帮我增强一下动力 /ll。 纸上谈兵没有意义，更重要的是落实实践，可是最近模拟赛的难题都很难理解，那些过去的题又不知道怎么去改了。 可能我需要休息一下。 至少我还有一年，或者说，只剩一年了吧。。。 # 我出的几个题 如果直接说明的说服力不足，我决定举出我自己出的几个自我感觉良好的题的例子。 ## 星命定轨 [题目链接](https://www.luogu.com.cn/problem/P14481)。 这个题可能刻意度比较大，有点引导做题人做不出来这个题的趋势才让这个题黑了。。。其实没那么难。 关键在两个性质。这些性质可以通过**猜测 / 实践**或者是**观察**发现。具体可以直接去看题解，我就不剧透了。 ## 天阶梦游 [题目链接](https://www.luogu.com.cn/problem/P14482)。 这个题难度比较大。第一步就要用到**刻画**成数学语言的手法。后面更是连续的使用刻画和猜测。具体还是看题解吧不剧透。 ## 演剧 [题目链接](https://www.luogu.com.cn/problem/P13309)。 这是很显然的手模题！通过猜测 / 实践就可以做出来了。需要一点耐心和注意力。