《骗分导论》是在 OI 界占有重要地位的文章。谨以此文向作者表示敬意。

前言

lzn定理： 任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。

但是，很多时候，我们作为蒟蒻，刷题不多，水平不高，却要和大牛们同场竞技。我们如何在能力范围内，尽量多拿分呢？答案是骗分。骗分就是用比正解简单得多的程序，尽量地得到分数。

NOIP 的变化

• 测试点增加。NOIP 2018 除 Day1 T1 之外的所有题目均有 20 或 25 个测试点。
• 存在原题。每年都会下放至少一道 NOI 题目，而 NOIp 2018 更是出了 2 道原题。
• (2018 年)更换了评测机，处理器更换为 i7-7800k ，评测时间也相应地缩短了。

部分分

很多时候，作为蒟蒻，是想不出解决 100% 数据的算法的，而 NOIp 有部分分。通常，一道题的不同测试点会有不同的数据范围。这时，可以退而求其次，去取得部分分。通常，能拿得部分分的算法，思路比正解简单得多。例如， dfs 、枚举、模拟在数据范围不大时威力相当大。在数据范围允许的情况下，尽量使用最简单的算法，这样，可以减小思维负担和调试难度。如 NOIp 1999 拦截导弹，数据范围只有 1000，要求输出最长不上升子序列，O(n^2) 的算法就可通过所有测试点，就不要使用复杂的 O(n log n) 的算法。同时，一些题目（尤其样例较多的题目），会有一部分数据是特化情形，有较简单的算法去解决。这时，不要放弃，试着写出特化情形的代码，就有可能多得分。

骗分过样例，暴力出奇迹

一些方法

“找规律”

当题目要求输出f(x)的值时，x相当大，可以直接根据题意进行模拟，寻找答案中的规律。

贪心

贪心，即每次决策都取当前最优解，虽然对很多题来说未必正确，但是如果使用得当，不仅代码简单，也能得到一些分数。

打表

打表，就是把预先算好的答案存储在程序中，非常适合于数据范围不大的题目，尤其是在可以得到正确答案，但是一定严重超时的时候使用。表可以手打（极少情况），或者使用其它程序生成。但是，NOIp 中适合打表的题通常并不多。

当上面的方法都不奏效时

即使使用了上述方法，作为蒟蒻的我们也很可能有一些题毫无头绪。

样例

基本上，每道题都会附带样例。如果确实不会做，就输出样例，也许能拿到一个点的分。

听天由命

输出随机数，让上天决定得分。适合输出范围不大的题目。用srand(time(NULL))或者栈上的未初始化数据初始化随机数发生器，然后输出rand()%X，X是输出范围。

宁为瓦碎，不为玉全

当确确实实没有任何办法时，不如把程序变成 100% cpu bound 类型，下面是代码：

#include <stdio.h>
int main(void）
{
    while (1); //100% cpu bound
    return 0;
}

它可以占住评测机若干秒，对时限大，测试点多的题目效果更明显。

代码级优化（常数优化）

信息学竞赛并不是数学竞赛，除了思路与逻辑的正确性以外，还要求代码的效率不能太低，有时出题人会卡常数，使一些算法渐进复杂度足够低，但实际执行效率不高的实现在一些测试点上无法得分。这部分的细节会博主会用另一篇文章详细解释。

组合

实践中，单独使用一种方法经常并不能完全覆盖题目的所有情况。这时，需要组合以上的多种方法。例如，小测试点使用保证正解但渐进复杂度大的朴素算法，

结语

不骗分，是骗分的最高境界 ——《骗分导论》