一年一度的NOIP很快就要到了，那么，如何才能在NOIP中通过暴力破解样例来得分呢？请往下看
工具/原料
NOIP参赛资格
C++语言基础
骗分——与复杂度的较量
1、从本质上说，“程序优化”就是降邋冠判厩低时间复杂度3的过程。而“骗分”，则是降低编程复杂度的过程，更准确的说，是取得得分与编程时间的最优比值。有人会问，如果这道题根本不会做，连算法都没有，谈何“降低骀旬沃啭时间复杂度”？其实不然。对于任何问题，只要它是一个可解问题2，就一定可以通过枚举法来解决。即使是NPC问题，只要将所有可能的情况一一列举，都能在有限时间（不论它有多长）中解决。所以从理论上说，可解问题都有最低时间复杂度。但在实际编写程序时，我们不能让程序运行1年甚至更长，于是需要更为高效的算法。我们信息学竞赛学习如此众多的算法、优化技巧，说到底，就是在降低程序运行的时间复杂度，使得程序在规定时间内出解。正是基于这样的观点，本文的各种算法都关注了时间复杂度的衡量，而且不同于理论著作，更加注重实际运行时间的比较，因为理论复杂度不能说明一切问题，应试中的时限才是硬道理。要纠正一种错误的观念，“时间复杂度越低越好4”。有时为了降低一道题目的复杂度，耽误了其他题目解决的时间，得不偿失；这时不如放弃这道题目的进一步优化，争取得到50-60分，再去解决其他题目。这种策略尤其对于难题、高档次考试有效。另外，复杂度记号中的常数因子也是不可忽略的。例如搜索中剪枝本身的代价超过被剪掉的搜索代价，就不如不剪。这也提醒我们，养成良好的编程习惯，降低常数复杂度，也是“骗分”的重要手段。
2、在信息学竞赛中，“用空间换时间”是常用的策略。这里我们再提出一个观点：用运行时间换胆咣骜岱编程时间，用尽时限中的每个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级算法。所以，盲目优化时间复杂度不是可取的行为。运用这些时间，可以解决其他问题，得到更高的分数。我们的目的，就是找到“时间复杂度”与“编程复杂度”的平衡点。
3、在科学研究意义上，时间复杂度的常数优化并不是十分重要的2。但在信息学竞赛中，同样的翱务校肢复杂度为O(n2)的程序，对于一组n=5000的数据，有的可能常数为20，需要运行1000ms，有鹚兢尖睁的可能常数为5，需要运行500ms。这样，两个看似相同的算法，一个超时错误，一个正确得分。所以，很多同学有“常数优化不重要，关键在算法3”的看法，是不正确的。众所周知，好算法的设计不是人人都能完成，而常数优化的技巧可以在平时积累，注意训练，考试时就能习惯的写出高效的代码。在信息学竞赛中，常遇到程序运行超时的情况。然而，同一个程序设计思想，用不同算法，会有不同的运行效率；而即使是同样的算法，由于在代码的细节方面设计有所不同。执行起来效率也会有所不同。当遇到所需时间较长的问题时，一个常数级优化可能是AC的关键所在。下面通过实际测试1和理论分析，探索常数时间优化的方法策略。