骗分导论 | 小鹿包的文档库

THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD

蒟蒻的宝书

第 1 章绪论

在 Oier 中,有一句话广为流传：

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

然而,我们这些蒟蒻们,没有经过那么多历练,却要和大牛们同场竞技,我们该怎么以弱胜强呢？答案就是：

骗分

那么,骗分是什么呢？骗分就是用简单的程序(比标准算法简单很多,保证蒟蒻能轻松搞定的程序),尽可能多得骗取分数。

骗分的操作对于 ACM 赛制并没有作用,一般作用于 OI 赛制中

无论是 NOIP 还是 CSP 等比赛，骗分以及暴力都是极其有效的一种手段，尤其在你对题目所使用的算法不甚熟悉甚至于完全不能理解题意的时候，这往往能为你带来很多的分数。没有人知道你的程序是什么样的，所以你就算骗到了分也不会有人说你无耻，更何况这是极其常见的办法

第 2 章从无解出发

2.1 无解情况

在很多题目中都有这句话：若无解,请输出-1

看到这句话时,骗分的蒟蒻们就欣喜若狂,因为——数据中必定会有无解的情况！那么,只要打出下面这个程序：

1	printf("-1");

就能得到 10 分,甚至 20 分,30 分！

举个例子：

NOIP2012 第 4 题,文化之旅

题目描述 Description

有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。

现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。

输入描述 Input Description

第一行为五个整数 $N,K,M,S,T$ ,每两个整数之间用一个空格隔开,依次代表国家个数(国家编号为 $1$ 到 $N$ ),文化种数(文化编号为 $1$ 到 $K$ ),道路的条数,以及起点和终点的编号(保证 $S$ 不等于 $T$ )；

第二行为 N 个整数,每两个整数之间用一个空格隔开,其中第 $i$ 个数 $C_i$ ,表示国家 $i$ 的文化为 $C_i$ 。

接下来的 $K$ 行,每行 $K$ 个整数,每两个整数之间用一个空格隔开,记第 $i$ 行的第 $j$ 个数为 $a_{ij}$ , $a_{ij}=1$ 表示文化 $i$ 排斥外来文化 $j$ ( $i$ 等于 $j$ 时表示排斥相同文化的外来人), $a_{ij}=0$ 表示不排斥(注意 $i$ 排斥 $j$ 并不保证 $j$ 一定也排斥 $i$ )。

接下来的 $M$ 行,每行三个整数 $u,v,d$ ,每两个整数之间用一个空格隔开,表示国家 $u$ 与国家 $v$ 有一条距离为 $d$ 的可双向通行的道路(保证 $u$ 不等于 $v$ ,两个国家之间可能有多条道路)。

输出描述 Output Description

输出只有一行,一个整数,表示使者从起点国家到达终点国家最少需要走的距离数(如果无解则输出-1)。

这道题看起来很复杂,但其中有振奋人心的一句话输出-1,随手打个 printf("-1"); ,得 $10$ 分。

2.2 样例——白送的分数

每道题目的后面,都有一组"样例输入"和"样例输出"。它们的价值极大,不仅能初步帮你检验程序的对错(特别坑的样例除外),而且,如果你不会做这道题(这种情况蒟蒻们已经司空见惯了),你就可以直接输出样例！

例如美国的USACO,它的题目有一个规则,就是第一组数据必须是样例。那么,只要你输出所有的样例,你就能得到 $100$ 分(满分 $1000$ )！这是相当可观的分数了。

现在,你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句,你就能实现这些骗分方法。那么,如果你有一定的基础,请看下一章——我将教你怎样用简单方法骗取部分分数。

第 3 章 “艰苦朴素永不忘”

本章的标题来源于《学习雷锋好榜样》的一句歌词

看到"朴素"两个字了吗？它们代表了一类算法,主要有模拟和 DFS。下面我就来介绍它们在骗分中的应用。

3.1 模拟

所谓模拟,就是用计算机程序来模拟实际的事件

例如 NOIP2012 的"寻宝",就是写一个程序来模拟小明上藏宝塔的动作。

较繁的模拟就不叫骗分了,我这里也不讨论这个问题。

模拟主要可以应用在骗高级数据结构题上的分,例如线段树。下面举一个例子来说明一下。

排队(USACO 2007 January Silver)

题目描述 Description

每天,农夫约翰的 $N(1≤N≤50000)$ 头奶牛总是按同一顺序排好队,有一天,约翰决定让一些牛玩一场飞盘游戏,他决定在队列里选择一群位置连续的奶牛进行比赛,为了避免比赛结果过于悬殊,要求挑出的奶牛身高不要相差太大

约翰准备了 $Q(1≤Q≤200000)$ 组奶牛选择,并告诉你所有奶牛的身高 $H_i(1≤H_i≤10^6)$ 。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。

注意：在最大的数据上,输入输出将占据大部分时间

对于这个例子,大牛们可以写个线段树,而我们蒟蒻,就模拟吧。

附模拟程序:

for (int i = 1; i <= q; i++)
{
    scanf("%d %d", &a, &b);
    int min = INT_MAX, max = INT_MIN;
    for (int i = a; i <= b; i++)
    {
        if (h[i] < min)
            min = h[i];
        if (h[i] > max)
            max = h[i];
    }
    printf("% d\n", max - min);
}

程序简洁明了,并且能高效骗分。本程序得 $50$ 分。

3.2 万能钥匙——DFS

DFS 是图论中的重要算法,但我们看来,图论神马的都是浮云,关键就是如何骗分。下面引出本书的第 2 条定理：DFS 是万能的

这对于你的骗分是至关重要的。比如说,一些动态规划题,可以 DFS；数学题,可以 DFS；剪枝的题,更能 DFS。

DFS，即深度优先搜索，常常被称为暴力，其核心思想是将所有可能全部遍历一遍，以递归形式出现，但是容易导致超时
具体的操作逻辑如下：从一个顶点 $V_0$ 开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，反复进行上述过程，从另一条路开始走到底，这样就可以较为有序地遍历所有的节点，这种尽量往深处走的概念即是深度优先的概念。
这样可以按顺序遍历所有的点，时间复杂度较高，这样的搜索可以通过剪枝优化，从而使重复的搜索减少。

搜索是算法的基础，往往编写难度低且容易查错。
暴力搜索可以帮助我们拿到一些正解难度较高题目的部分分。
暴力普适性强用处广，通过暴力获得骗分亦是考场上不错的选择。

OI 界有句话叫做"暴力打满"，即一次比赛拿到所有的暴力的分，考虑到在 NOIP/CSP 中暴力分较多，况且常数优化和暴力的一些剪枝也可以拿到更多分

但是暴力也要找准方向，纯粹的枚举是愚蠢的，我们要根据题目状况设定特定的暴力策略

下面以一道 01 背包(动态规划)的题来解释一下 DFS 骗分

NOIP2003,采药

题目描述 Description

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是辰辰,你能完成这个任务吗？

输入描述 Input Description

输入第一行有两个整数 $T(1<=T<=1000)$ 和 $M(1<=M<=100)$ ,用一个空格隔开, $T$ 代表总共能够用来采药的时间, $M$ 代表山洞里的草药的数目。接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间(包括 $1$ 和 $100$ )的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出描述 Output Description

输出包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

数据范围及提示 Data Size & Hint

对于 $30\%$ 的数据, $M<=10$

对于全部的数据, $M<=100$

这题骗分的方法很简单。我们瞄准 $20\%$ 的数据来做,可以用 DFS 枚举方案,然后模拟计算出最优解。附一个大致的代码：

void DFS(int d, int c)
{
    if (d == n)
    {
        if (c > ans)
            ans = c;
        return;
    }
    DFS(d + 1, c + w[i]);
    DFS(d + 1, c);
}

3.3 另一把钥匙——BFS

有的时候，一些走迷宫之类的题目使用 DFS 算法很容易超时或者爆栈，所以我们可以换一种暴力的方式，即广度优先搜索，算法思路如下

我们首先访问顶点 $v_i$ ，然后访问 $v_i$ 的所有未被访问的邻接点 $w_1,w_2,\ldots,w_k$ ,依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问。

这时候我们需要利用队列来保证我们访问节点的顺序，此时我们的效率比深搜大大提高，原因是我们能够省去很多的重复步骤，程序架构如下

void bfs()
{
    定义队列 q;
    q.push(初始状态);
    while (队不空)
    {
        x(y) = 队头状态信息;
        出队;
        if (下一步可行)
            下一步;
    }
}

3.4 剪枝/记忆化搜索

本节需要一定的算法素养，看不懂就多练吧
常言道：记搜+剪枝可以解决一切问题

记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会大大降低算法的执行效率。

记忆化搜索

而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算用到的时候直接取出结果，避免重复运算，因此极大的提高了算法的效率。

剪枝

可行性剪枝：当目前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判断不可行，直接返回
排除等效冗余：当几个子树具有完全相同的效果的时候，只选择其中一个搜索。
最优性剪枝：在我们用搜索方法解决最优化问题的时候的一种常用剪枝。当搜索还未结束时，记录的状态已经比当前保存的最优解更劣，那么此方案一定无效，停止搜索并回溯即可。
顺序剪枝：普遍来讲，搜索的顺序是不固定的，对一个问题来说，算法可以进入搜索树的任意的一个子节点。

但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。

此剪枝一定优先按照题目要求！

第 4 章骗分的关键——猜想

4.1 听天由命

如果你觉得你的人品很好,可以试试这一招——输出随机数。

先看一下代码：

#include <stdlib.h>
#include <time.h>
//以上两个头文件必须加

srand(time(NULL));         //输出随机数前执行此语句
printf("%d",rand()%X); //输出一个 0~X-1 的随机整数。

这种方法适用于输出一个整数(或判断是否)的题目中,答案的范围越小越好。让老天决定你的得分吧。

据说,在 NOIP2013 中,有欧皇最后一题不会打了个随机数,结果得了 70 分啊!!

4.2 猜测答案

有些时候,问题的答案可能很有特点：对于大多数情况,答案是一样的。

这时,骗分就该出手了。

你需要做的,就是发掘出这个答案,然后直接输出。

有时,你需要运用第 3 章中学到的知识,先写出朴素算法,然后造一些数据,可能就会发现规律。

炸毁计划

题目描述 Description

皇军侵占了通往招远的黄金要道。为了保护渤海通道的安全,使得黄金能够顺利地运送到敌后战略总指挥地延安,从而购买战需武器,所以我们要通过你的程序确定这条战略走廊是否安全。

已知我们有 $N$ 座小岛,只有使得每一个小岛都能与其他任意一个小岛联通才能保证走廊的安全。每个小岛之间只能通过若干双向联通的桥保持联系,已知有 $M$ 座桥 $(A_i,B_i)$ 表示第 $i$ 座桥连接了 $A_i$ 与 $B_i$ 这两座城市。

现在,敌人的只能炸毁其中一座桥,请问在仅仅炸毁这一座桥的情况下,能否保证所有岛屿安全,都能联通起来。

现在给出 $Q$ 个询问 $C_i$ ,其中 $C_i$ 表示桥梁编号,桥梁的编号按照输入顺序编号。每个询问表示在仅仅炸毁第 $C_i$ 座桥的情况下能否保证所有岛屿安全。如果可以,在输出文件当中,对应输入顺序输出yes,否则输出no

你发现问题了吗？那么多座桥,炸一座就破坏岛屿的联系,可能性微乎其微(除非特别设计数据)

那么,我们的骗分策略就出来了：对于所有询问,输出 yes .果然,此算法效果不错,得 $80$ 分。

现在知道猜测答案的厉害了吧？

4.3 寻找规律

首先声明：本节讲的规律不是正当的算法规律,而是数据的特点

某些题目会给你很多样例,你就可以观察他们的特点了

有时,数据中的某一个(或几个)数,能通过简单的关系直接算出答案

只要你找到了规律,在很多情况下你都能得到可观的分数

这样的题目大多出现在 NOI 或更高等级的比赛中,本人蒟蒻一个,就不举例了

4.4 小数据杀手——打表

我认识一个人,他在某老师家上 C 语言家教,老师每讲一题,他都喊一句：“打表行吗？”

他真的是打表的忠实粉丝。表虽然不能乱打,但还是很有用的。

先看一个例子：

NOIP2003 栈

题目描述 Description

栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。

一个操作数序列,从 $1,2$ ,一直到 $n$ ,栈 A 的深度大于 $n$ 。

现在可以进行两种操作,

将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作)
将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作)

使用这两种操作,由一个操作数序列就可以得到一系列的输出序列

你的程序将对给定的 $n$ ,计算并输出由操作数序列 $1,2,…,n$ 经过操作可能得到的输出序列的总数。

这题看似复杂,但数据范围太小,N<=18。所以,骗分程序就好写了：

1
2
3

int a[18] = {1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700}
scanf("%d", &n);
printf("%d", ans[n - 1]);

学完这一章,你已基本掌握了骗分技巧。

下面的内容涉及一点算法知识,难度有所增加。蒟蒻中的蒟蒻可以止步于此了。

第 5 章做贪心的人

5.1 贪心的算法

若不能展望出最优的未来，那不如贪心的做个精致的利己主义者。

贪心的原理

贪心算法的核心就是一个字：贪。总是做出当前看来最优的选择，因此可知，贪心算法不从整体去考虑，它做出的选择也是局部最优选择，从而达到全局优化选择。我们只关注目前的利益，从而达到利益最大化，尽管贪心算法不一定能得到最优解，面对相当数量的一部分问题，我们是可以得到正确的答案的。

从问题的某一个初始解，一步步推论，保证每一步都是最为优化的，出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当接下来的任意一步都无法达到最优时，贪心算法结束。

贪心算法的弊病

不能保证求得的最后解是最佳的；
不能用来求最大或最小解问题；
只能求满足某些约束条件的可行解的范围。

贪心算法是个复杂的问题,但你不用管那么多。我们只关心骗分。给你一个问题,让你从一些东西中选出一些,你就可以使用贪心的方法,尽量挑好的。

有趣的问题

题目描述 Description

2013 年的 NOIP 结束后, Smart 发现自己又被题目碾压了,心里非常地不爽,于是

暗下决心疯狂地刷数学题目,做到天昏地暗、废寝忘食,准备在今年的中考中大展身手。

有一天,他在做题时发现了一个有趣的问题：

给定 n 个二元组 $(a_i, b_i) i)$ ,记函数：

$y=100 \frac{\sigma(a_i)}{\sigma(b_i)}$

将函数 $y$ 的值四舍五入取整。

现将 $n$ 个二元组去掉其中的 $k$ 个计算一个新的 $y$ 值(也四舍五入取整),均能满足： $y<=z$ ,求出最小的 $z$ 值。Smart 想让你帮他一起找出最小的 $z$ 值。

【输入格式】

输入包含多组测试数据。每组测试数据

第一行两个整数： $n$ 和 $k$

第二行为 $n$ 个数: $a_1,a_2,\ldots,a_n$

第三行为； $n$ 个数: $b_1,b_2\ldots,b_n$

输入数据当 $n,k$ 均为 $0$ 时结束。

这题让人望而生畏,但我们有贪心的手段。

每个二元组的 $a$ 值是乘到答案中的,所以 $a$ 越大越好,那么只要选择出最小的 $k$ 个去掉即可。

代码就不写了,因为这个涉及到下一章的内容：排序

此代码得 $20$ 分

5.2 贪心地得分

我们已经学了很多骗分方法,但他们中的大多效率并不高,一般能骗 10~20 分。

这不能满足我们的贪心。

然而,我们可以合成骗分的程序。

举个最简单的例子,有些含有无解情况的题目,它们同样有样例。我们可以写这个程序

if(是样例)
    printf(样例);
else
    printf("-1");

这样也许能变 10 分为 20 分,甚至更多。

当然,合并骗分方法时要注意,不要重复骗同一种情况,或漏考虑一些情况。

大量能骗分的问题都能用此法,大家可以试试用新方法骗 2.1 中的例子"文化之旅"。

第 6 章 C++的福利

在 C++中,有一个好东西,名唤 STL,被万千 Oier 们所崇拜,所喜爱。下面让我们走进 STL。

6.1 快速排序

快速排序是一个经典算法,也是 C++党的经典福利。他们有这样的代码：

1 2	#include <algorithm> //这是必须的 sort(A, A + n); //对一个下标从 0 开始存储,长度为 n 的数组升序排序

6.2 “如意金箍棒”

C++里有一种东西,叫 vector 容器。它好比如意金箍棒,可以随着元素的数量而改变大小。它其实就是数组,却比数组强得多。

下面看看它的几种操作：

vector<int> V;  //定义
V.push_back(x); //末尾增加一个元素 x
V.pop_back();   //末尾删除一个元素
V.size();       //返回容器中的元素个数

它同样可以使用下标访问。(从 0 开始)

第 7 章结语

骗分是蒟蒻的有力武器,可以在比赛中骗得大量分数。相信大家在这本书中收获了很多,希望本书能帮助你多得一些分。

但是,最后我还是要说一句：

不骗分,是骗分的最高境界

第 1 章 绪论

第 2 章 从无解出发

2.1 无解情况

NOIP2012 第 4 题,文化之旅

2.2 样例——白送的分数

第 3 章 “艰苦朴素永不忘”

3.1 模拟

排队(USACO 2007 January Silver)

3.2 万能钥匙——DFS

NOIP2003,采药

3.3 另一把钥匙——BFS

3.4 剪枝/记忆化搜索

记忆化搜索

剪枝

第 4 章 骗分的关键——猜想

4.1 听天由命

4.2 猜测答案

炸毁计划

4.3 寻找规律

4.4 小数据杀手——打表

NOIP2003 栈

第 5 章 做贪心的人

5.1 贪心的算法

贪心的原理

贪心算法的弊病

有趣的问题

5.2 贪心地得分

第 6 章 C++的福利

6.1 快速排序

6.2 “如意金箍棒”

第 7 章 结语

第 1 章绪论

第 2 章从无解出发

第 4 章骗分的关键——猜想

第 5 章做贪心的人

第 7 章结语