奇迹之流WonderfloW

Nothing Replaces Hard Work!

集训日志第五篇(解题常用方法的总结)

| Comments

集训的时光不知不觉,其实已经过去了一半了,十三天。 每天做一到二个题,总结、思考。看重的不是做出的题目是用的什么方法,看重的是怎么想到的这个做题的方法,思路是怎么来的。那么今天顺势总结下思考问题的一些方法。

题目做的多了,就会自然而然的产生一些经验,比如看到数据的范围,就能想到最终的解法是什么复杂度的,然后根据复杂度,就可以套一些模型,一些常用的算法。 再根据常用的方法的多种应用,思考针对该题的解决方案。 这是很常见的一种方法,我喜欢称之为“经验教训”法。

面对一个问题,先从小规模着手,如果这个问题的数据非常小,从1个、2个、3个、、这样以此类推的往多处叠加,那么这个问题的解法会不会思考出来。要知道,如果能找到一种递推的方法,那么无论是logN的转移还是N的扫描都是计算机可以承受的。这种方法叫“以小见大”法。类似的方法就是极限法,就是当问题在平时由于参数的原因让人眼花缭乱的时候,我们不妨把这些都极限化,以此来获得一些有用的提示。

面对一份需求,仔细阅读里面的需求报告,把问题的描述揣摩清楚,深刻发掘问题的本质,或者说从问题本身描述的模型中抽离出一些性质。也是解决问题的一种方法。之前看《编程之美》,发现里面大量的告诫:一定要理解清楚题目描述的意思,我们做程序就是为了让使用者满意,但是如果连使用者的意图都不搞清楚的话,根本就谈不上出一个好的作品。这种方法可以称为“观察”法。

还有一种比较好的方法,就是“联想法”了。遇到一个问题,联想到自己之前遇到过的一些问题,用类似的方法解决。这个其实跟第一种也是类似的,但是又有所区别。

逆向思维,有的时候正难则反,如果正面去解决问题很困难,那么我就反着来。就像求最大流==最小割。

分治、分解(分层、分模块),把大规模的问题化解为一个个小规模的问题,是计算机里极为常用的一种方法。这种思路的本质是:通过合并减少问题数量,通过拆分减少问题间的联系,从而能做到“批量”、“宏观”地解决问题。
危险是,有时候底层细节并不能简单地忽略,但分层会造成一种“可以忽略底层”的假象。比如网络中每层都可能存在安全问题,并不容易“封”住不暴露给上层。

缓存思想,通俗的说,就是预处理。或者用空间换时间。很多宅男都喜欢一次性买很多吃的,然后可以减少去超市的次数。(在这上面,ZYZ绝对是个典型啊!)这其实就是一个缓存思想。 缓存的本质是:在能够预测未来使用的前提下,预先存储一些处理结果提供快速访问,从而做到用空间换时间或缓解瓶颈。 而缓存从逻辑上就会存在数据陈旧的问题,比如电话本里的号码可能已经停机了。

化简、近似求解,有时候一个精确的值可能需要花费的代价太大,那么我们就求解近似值,这方面,模拟脱火算法绝对是个典型。而有时瞎搞也能有意想不到的好处~

简洁的美。记得刚学计算机程序的时候就知道了程序界有名的“KISS”原则,keep it simple and stupid。我觉得解决问题也是这样,有时一个问题不能想的太复杂。同样的,在编码的时候,如果时间效率允许的话,能用STL,还是尽量用STL库为好。

这大概就是我的一个初步的总结,知乎上的有一篇文章《哪些你熟知的重要知识或方法,业外人士却常常因不了解而陷入困境?》写的很好,有兴趣的话可以花半个小时阅读一下。

最后不得不说的就是:注重细节。bug有的时候,就是出在小地方上的!!