NOIP如何暴力得分

NOIP如何暴力得分

一年一度的NOIP很快就要到了，那么，如何才能在NOIP中通过暴力破解样例来得分呢？请往下看

从本质上说，“程序优化”就是降低时间复杂度3的过程。而“骗分”，则是降低编程复杂度的过程，更准确的说，是取得得分与编程时间的最优比值。

有人会问，如果这道题根本不会做，连算法都没有，谈何“降低时间复杂度”？其实不然。对于任何问题，只要它是一个可解问题2，就一定可以通过枚举法来解决。即使是 NPC问题，只要将所有可能的情况一一列举，都能在有限时间（不论它有多长）中解决。所以从理论上说，可解问题都有最低时间复杂度。

但在实际编写程序时，我们不能让程序运行 1 年甚至更长，于是需要更为高效的算法。

我们信息学竞赛学习如此众多的算法、优化技巧，说到底，就是在降低程序运行的时间复杂度，使得程序在规定时间内出解。正是基于这样的观点，本文的各种算法都关注了时间复杂度的衡量，而且不同于理论著作，更加注重实际运行时间的比较，因为理论复杂度不能说明一切问题，应试中的时限才是硬道理。

要纠正一种错误的观念，“时间复杂度越低越好4”。有时为了降低一道题目的复杂度，耽误了其他题目解决的时间，得不偿失；这时不如放弃这道题目的进一步优化，争取得到50-60 分，再去解决其他题目。这种策略尤其对于难题、高档次考试有效。另外，复杂度记号中的常数因子也是不可忽略的。例如搜索中剪枝本身的代价超过被剪掉的搜索代价，就不如不剪。这也提醒我们，养成良好的编程习惯，降低常数复杂度，也是“骗分”的重要手段。

在信息学竞赛中，“用空间换时间”是常用的策略。这里我们再提出一个观点：用运行时间换编程时间，用尽时限中的每个 CPU 指令。

考虑一个问题：有 O(nlogn)7的 A 算法但需要 200 行代码，而有 O(n2)的 B 算法只需要70 行代码，而对于 60%的数据，n<1000；对于 100%的数据，n<100000. 我们需要做出一个决策。采用 A 算法，至少得 60 分，可能用掉 40 分钟；采用 B 算法，100 分到手，可能用掉 100 分钟。对于不同类型的比赛，我们应有不同的决策。对于 NOIP 这种其他题目较为简单、这样的试题是压轴题的情况，可以先做其他简单试题，最后视剩下时间长短选择算法；

而对于 NOI 这种“难题集萃”类型的试题，如果其他试题没有思路，可以用较长的时间完全解决该题；否则两道 60 分的题胜过一道 100 分的题。

当然，算法的选择还与选手的竞赛目标8有关。期望拿到 NOIP 一等奖或 NOI 银牌的选手可能希望尽量多得分，实力也不是很强，能得一分算一分，这样应选择 60 分的算法，以“保险”为基础；期望进入省队或国家集训队的选手必须发挥出色，编程水平较高，这样应选择 100 分的算法，拉大与其他选手的差距。

总而言之，算法的选择与“得失”的衡量有关，这样本文所述的“用运行时间换编程时间”就是正确的。例如 NOIP1999 第四题“拦截导弹”，要求输出最长不升子序列。这道题有 O(n2)的动态规划算法，也有 O(nlogn)的基于二分搜索的算法。但原题 n<=1000，就没有必要使用较为复杂且调试困难、容易出错的 log 级算法。所以，盲目优化时间复杂度不是可取的行为。运用这些时间，可以解决其他问题，得到更高的分数。我们的目的，就是找到“时间复杂度”与“编程复杂度”的平衡点。

在科学研究意义上，时间复杂度的常数优化并不是十分重要的2。但在信息学竞赛中，同样的复杂度为 O(n2)的程序，对于一组 n=5000 的数据，有的可能常数为 20，需要运行1000ms，有的可能常数为 5，需要运行 500ms。这样，两个看似相同的算法，一个超时错误，一个正确得分。所以，很多同学有“常数优化不重要，关键在算法3”的看法，是不正确的。众所周知，好算法的设计不是人人都能完成，而常数优化的技巧可以在平时积累，注意训练，考试时就能习惯的写出高效的代码。在信息学竞赛中，常遇到程序运行超时的情况。然而，同一个程序设计思想，用不同算法，会有不同的运行效率；而即使是同样的算法，由于在代码的细节方面设计有所不同。执行起来效率也会有所不同。当遇到所需时间较长的问题时，一个常数级优化可能是 AC 的关键所在。下面通过实际测试1和理论分析，探索常数时间优化的方法策略。