@typeof

如何“骗分”

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

前言

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

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

NOIP 的变化

部分分

很多时候,作为蒟蒻,是想不出解决 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;
}

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

代码级优化(常数优化)

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

组合

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

结语

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

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »