资讯详情

一道题目的思考，可以看作一个 DFS 的过程。我们需要找到一个「合法」的优解。

合法，是能解决问题；优解，指这个解法从开想到 AC 的整体难度低。

看了些大佬的文章，感觉很有启发。

这，是模拟退火。

发散

很少有人，在遇到题的那一刻思路就是清晰的。在读完题之后，我们的大脑一般是混沌的。

这一般是发散时刻，我们可以想到很多东西，不管是不是对的，这些东西大部分被我们立即排除。

可能，稍微接受一些解，多花一些时间确定思路，可以增加找到正解的概率。确定出几个备选方向，记下来，一个个想。

数据范围是这个阶段的关键。

逼近

可能在学习 OI 早期阶段，我们凭借大脑里的 trick 和思路快速确定题目解法，这是显然的爬山，完全取决于你的知识树。

可是当随着单步思路变难，思维链变长，完全取决知识树的思考会带来限制，我们需要退火。

增大对一个想法的接受度，可以增加我们找到答案的概率。甚至在有些情况下，对一些看似毫无关系的算法硬套都能发现解法，OI 圈里把这个叫做“生吃”。这个东西需要非常好的状态和耐心，以至于你真的可以严格执行「列出所有可能，依次思考」。

促进转化的发生

有的时候，我们可能以为我们到达叶子了，但是其实还可以往下：

• 极端情况或许可以帮上忙，找特殊值分析。

• 转化题意：放到一个模型上（笛卡尔树，坐标 + 莫队）等等。或者尝试描述题目。

• 反过来：记补集的数量/退背包/去除贡献。

• 将所有约束规约到一个点上。

• “本末倒置”，在这种链状思考里，它允许我们 meet in the middle，同时指引目前的方向。

• 优化，优化。

• 松弛条件。用容斥啥的做。

• 手玩找性质。

收敛

有时在思考，总会发现自己的思路可能和正解差一张纸。我们需要练习思维的收敛。

你发现我们有两种不同的方法，每种都差了些：为什么不合并到一起呢？

或者，我们用形式化的语言，描述这些问题。这时就要求思维清晰了。