做题的智慧

· · 算法·理论

前言

我前两天看了洛谷官方的 《提问的智慧》 和非官方的 《回答的智慧》 我突发奇想，决定施工一篇《做题的智慧》，文章仅个人观点，不喜勿喷 ，希望各位能够接受~

选择一个适合你的题目

想要通过做题来自我提升，就需要一道适合你的题目，我们分为以下两种情况讨论：

一.提升某种对某算法的编写能力

如果您想要提升某个对某算法的理解程度或者想要提升某种对某算法的编写能力，那么强烈推荐使用洛谷主题库的标签筛选功能，具体分为以下步骤：

  1. 来到洛谷主页，选择右边栏的“题库”来到题目列表。

  2. 点击“查找题目”区块的“筛选算法/来源/时间”。

  3. 你可以直接搜索想要的标签，或者用鼠标点击选择。

  4. 点击“确认”，题目区域的题目就会全部呈现涉及该算法的题目。

当然，有些算法涉及的题目很多，想要在这些题目里面选择合适的题目就需要选择合适的难度。

二.选择合适的难度

洛谷为用户分类了 “暂无评定”、“入门”、“普及-”、“普及/提高-”、“普及+/提高”、“提高+/省选-”、“省选/NOI-”、“NOI/NOI+/CTSC”八种难度参考，如果大家对这些分类没有概念，那么建议你从“入门”难度入手，如果觉得难度太简单，那么尝试更高的难度，如果觉得难度做起来不轻松、也不吃力，那么根据个人目标分为以下两种参考：

当然，随着做题数量的提升，个人适合的难度也会提升，作者强烈建议大家每隔一段时间评估适合自己的难度，随时做出调整。

在做题之前

准备物品

如同考试，想要做好一道题，需要准备好一些物品，这里给大家一些准备建议。

一个好的环境

如果你想高效、专注地做题，那么一个安静的环境再合适不过了。

你需要在一个很少有他人吵闹、环境噪音小的地方编程，这样不容易分心；除此之外，如果你在公共场合，建议佩戴耳机，不要播放任何声音，播放了也会影响编程专注。

如果您的专注力较差，或者有强迫症，可以先把屋内整理一下，有助于心平气和地写代码。

做好时间和心理准备

一般来说，用一个完整的时间段完成程序是对编写最友好的。

不是说不能做题中途休息，可以稍微放松，但是尽量不超过10分钟，为的是不打断思路，如果时间冲突，那么也尽量不要隔天（比如1月1日做，没做出来，3日再做）做，效果不佳，还要回想当时的思路。

其次，心理准备也很重要，如果中途题目没有解出来，有bug、bug很难找、思路需要推到重来、算法不会、程序超时等问题，一定不能着急，要心平气和的解决问题。

另外，要做好长时间编码的准备，休息起来要有度，不要忘了时间。

读题

不读题就AC的人，要么是直接抄题解，要么就是改洛谷源代码，如果你既不想作弊被处罚，又不想给洛谷带来麻烦、受到更严重的处罚，那么就请仔细读题！

快读

首先要学会快速快读，了解题目大概要领，心里有个框架，在进行精细读题。

快读要领有以下几个：

细读

光走马观花地看一遍题目大概肯定是不行的，我们还需要深入理解题目意思，这就需要细细地品味题目了，细读和快读完全相反。

细读要读剧情，剧情中可能有做题的关键，而且要仔细读整个题目，重点、不重点都要读，读不懂的地方一定要回去再读一遍，到懂为止。

另外，如果有题目中专业术语或者网梗的话一定要搜索明白意思再继续。

小提示：如果读题时感觉题目难度不当，一定要换题哦！

说明提示非常重要

重要在哪儿呢？我敢说，90\%的题目说明提示里都有线索！

最主要的线索就是“数据规模与约定”，在这里可以获得很多信息：怎么获得部分分、目标的时间复杂度、能不能切暴力、需要用到什么是算法、要不要高精度、要不要快读快写等等等等，所以一定要看！而且仔细看！

当然，说明提示里也有很多其他的提示内容，如果不看，有可能你写了一个下午的代码，就全部白费咯！

题意概述

读完题，你可以在大脑中思考一下这道题的本质是让我算什么，一定要想清楚，再开始做题！

do

请你拿好你的纸笔，好好理清脑中的逻辑，抛掉一切情绪，全身心投入到题目之中，启动超级大脑，开始思考做题思！

切入点

有的时候，拿到一道题，你很可能会不知所措，不知道用什么方法解决。那么我来告诉你，你不是没有方法，而是方法太多了！！！

你可能常常想出一种解决方案，然后觉得这个方案有太多缺点，然后想下一个方案。下一个方案的缺点又和第一个方案的缺点不同，接下来只得再找方案......结果你的方案越来越枯竭，每个方案都有缺点，这怎么办？然后你就开始放弃......

现在，我告诉你。不管第一种方案缺点有多少，就先用第一种方案做！就是用你读完题后想到的第一套方案把这道题做下来（哪怕是暴力），给自己出几个极简的数据（也可以用样例，但必须够简单），测一下，如果成功，就提交评测，如果得到了分数，这将对你是一个极大的鼓励，哪怕是5分。

行了，现在要准备拿满分了吗？别急！路还远着呢！

优化方案

优化代码的方案有很多，可见此篇最后的附1。

选择合适的方案是关键，这时候必须不能钻牛角尖，换个角度考虑问题一定要学会“空间换时间”（但也别换到超空间的程度）

大部分地方，优化都要遵循“能优就优”原则，但如果一个优化方法改动较大、复杂度变化不大、自己不确定，可以考虑其他办法代替这个优化策略。

另外，优化可以叠加，非常欢迎优化了这一点，再去优化那一点，而且要捡着时间复杂度高的循环优化，不能再一个 O(n^4) 的时间复杂度面前去救一个 O(n) 的“小弟弟”，意义属实不大。

如果你读完题，脑中真的一篇空白，那么我建议你先打大暴力，直接上循环，复杂度 O(n^{10}) 都没有问题，打完暴力再一步一步优化。

小提示：一定要记得改的时候一块儿改，不能改了这一处忘了那一处，改完之后通读程序。

优化和思路之间的选择

想优化思路时一定要严谨，严防bug。如果你因为这个优化思路不够快，而要踢除这个思路，卷土重来，那你可慢着！最好再想想能不能再优化这个思路。

总的来说，选择一个思路要谨慎，放弃一个思路也要谨慎。

算法选择

方案准备好了，接下来总该考虑算法了吧？yes！

一定要根据你的思路选择合适的算法，如果实在找不到，可以看一看题目讨论区有没有和你遇到一样问题的人，再看看下方回答者的留言，比如回答者说“这题要记忆化。”，你就可以马上学习一下记忆化的算法，也有助于你的编程。

debug

评测！呀！成群结队的WA，怎么办？没关系！

谨防手滑

先通读程序，看看有没有把 i 写成 j ，把 long long 写成 int ，看看有没有缩进没对齐，看看数组空间开小了没......手滑之处，往往是最容易犯得错误！这些是细节错误。

代码 & 思路

看看自己的思路和代码有没有对齐，这里就需要好好理解代码，把思路利得更清楚了。

可以使用“小鸭子”方法。这是一个很经典的方法，能够帮助你完成这一步，你可以假装旁边有一个小鸭子玩偶（或者真的拿过来一个），然后跟TA讲述这个代码的意思，中间如果你连自己都卡壳了，那肯定有问题咯！

模拟法

好了，你的思路没问题，那么现在，请代入一组数据，在草稿纸上模拟一下程序吧！如果你发现程序运行的某一步和你发现的不符，那么恭喜，你找到bug啦！

当然，我们可以让代码输出完成我们手算的操作，直接让电脑在运行途中输出每一步的结果，甚至可以制作一个很美观的表格，查看更清楚！

小提示：输出完了一定要记得注释掉这些调试代码哦！

另外，如果你的编译器有“调试”功能的话，也可以用，不过不推荐，毕竟考试的时候可没这么高级的东西！！！

底层

到上一步，大部分代码已经AC，留下的这一小部分可能就是计算机底层导致的问题了。

比如运算优先级、地址出错这些都是潜在因素，好好查！

收官

盘点

恭喜你AC了一题，感觉怎么样？盘点一下！把所有学到的技巧、算法、优化方法、思路切入点全部记到一个文档里，最后在记下这次做得好的地方和不好的地方，这对下次做题很有帮助哦！

update the target

最后，就是更新你的目标了，AC乐这道题，你一定成长了不少，赶紧把自己的目标更加向上抬一个台阶，让自己变得更强吧！！！

附录 优化方案10种

仅凭作者经验！

1.二分查找

复杂度：O(logn)

适用：排好序/有一定规律的线性结构查找某一元素位置

2.减少重复计算，记忆化

复杂度：无固定复杂度

适用：计算量大、操作数范围不大且重复计算多的算法，常见递归

3.预处理

3.1前缀和

复杂度：O(n) + O(1)

适用：操作数范围不大且经常遇到计算某一范围的结果时

3.2埃式筛法

复杂度：O(n \log \log n)

适用：判断质数、打质数表

4.下一步计算利用上一步结果

复杂度：无固定复杂度

适用：计算量大且上下计算有关联时

备注：如欧拉筛、约数个数、子串处理等，很多时候需要手算找规律

5.转换复杂度

复杂度：无固定复杂度

适用：当一段代码复杂度高但可以用两端复杂度低的代码代替时

6.空间换时间

复杂度：无固定复杂度

适用：数据量不大且复杂度高时

备注：前缀和也属于这一项，通常使用一个数组纪录另一个数组的数据所在的位置

7.使用合适的数据结构

复杂度：无固定复杂度

适用：当前数据结构有缺陷时

备注：常见arr换vector、arr/queue换list

8.选择合适的时机循环

复杂度：无固定复杂度

适用：有多种操作且每个操作都可以循环达到一个目的时

9.箱排序

复杂度：O(n)

适用：数据范围不大且要求快速时

10.数学方法

复杂度：无固定复杂度

适用：当操作数有数学规律时

最后，感谢阅读本篇blog，希望能帮助到大家！

此外，欢迎给本篇提建议，诚心谢谢大家！