新版骗分导论

THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD

蒟 蒻 的 宝 书

目录

第一章 诸论

第二章 从无解出发

2.1 无解情况

2.2 样例——白送的分数

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

3.1 模拟

3.2 万能钥匙——DFS

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

4.1 听天由命

4.2 猜测答案

4.3 寻找规律

4.4 小数据杀手——打表

第五章 做贪心的人

5.1 贪心的算法

5.2 贪心的得分

第六章 C++的福利——STL

6.1 快速排序

6.2 “如意金箍棒”

第七章 “宁为玉碎，不为瓦全”

第八章 实战演练

第九章 结语

第一章 诸论

在 OIer 中，有一句话广为流传： 任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。 这就是著名的 lzn 定理。然而，我们这些蒟蒻们，没有经过那么多历练，却要和大牛们同场竞技，我们该怎么以弱胜强呢？答案就是： 骗分。

那么，骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证蒟蒻能轻松搞定的程序），尽可能多得骗取分数。 让我们走进这本 《新版骗分导论》，来学习骗分的技巧，挑战神牛吧！

第二章 从无解出发

2.1 无解情况

在很多题目中都有这句话：“若无解，请输出 -1.” 看到这句话时，骗分的蒟蒻们就欣喜若狂，因为——数据中必定会有无解的 情况！那么，只要打出下面这个程序： printf("-1"); 就能得到 10 分，甚至 20 分，30 分！

例 NOIP2012 普及组 文化之旅

这道题看起来很复杂，但其中有振奋人心的一句话“输出 -1”，我考试时就高兴坏了 （当时我才初一，水平太烂） ，随手打了个 printf("-1");，得 10 分。

更好的例子 CSP-S 2022 星战

全输出NO拿45分

“同志，你只是一直在回答‘不可以’吗？你到底有没有好好判断形势？现在是关乎国家危亡的时刻……”

“总司令，您知道我不太聪明，没找到快速而正确地计算出结果的办法，但是据某项统计，我一直回答‘NO’的话，在一次战役中判断完全正确的概率是45%。”

“那……”

“不可以，总司令”

2.2 样例——白送的分数

每道题目的后面，都有一组 “样例输入” 和 “样例输出” 。它们的价值极大，不仅能初步帮你检验程序的对错（特别坑的样例除外），而且，如果你不会做这道题（这种情况蒟蒻们已经司空见惯了），你就可以直接输出样例！ 例如美国的 USACO，它的题目有一个规则，就是第一组数据必须是样例。那么，只要你输出所有的样例，你就能得到 100 分（满分 1000 分）！这是相当可观的分数了。

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

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

本章的标题来源于《学习雷锋好榜样》的一句歌词，但我不是想教导你们学习雷锋精神，而是学习骗分！

看到“朴素”两个字了吗？它们代表了一类算法，下面我就来介绍它们在骗分中的应用。

3.1 模拟

所谓模拟，就是用计算机程序来模拟实际的事件。例如 NOIP2012 普及组 寻宝，就是写一个程序来模拟小明上藏宝塔的动作。

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

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

USACO07JAN Balanced Lineup G

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

附模拟程序：

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]

if(h[i]>max)max=h[i];

}

printf(“%d\n”,max-min);

}

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

3.2 万能密钥——DFS

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

这对于你的骗分是至关重要的。比如说，一些动态规划题，可以 DFS；数学题，可以 DFS；剪枝的题，更能 DFS。下面以一道省选题为例，解释一下 DFS 骗分。

例题： NOIP2005 普及组 采药

这题的方法很简单。我们瞄准 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);

}

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

4.1 听天由命

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

先看一下代码：

#include

#include

#include

//和必不可少

using namespace std;

int random(int start,int end) //随机数函数

{

end++;

int res=start+(end-start)*rand()/(RAND_MAX + 1.0);

return res;

}

int main()

{

srand(unsigned(time(0))); //利用时间确定随机数种子

for(int i=1;i<=1000;i++)

printf("%d\n",random(1,100)); //重复一千次输出 1~100 之间的任意数

return 0;

}

有关随机数的具体叙述，可以自行百度

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

据说，在 NOIP2013 中，有人最后一题不会，愤然打了个随机数，结果得了 70 分啊!!

4.2 猜测答案

有些时候，问题的答案可能很有特点：对于大多数情况，答案是一样的。这时，骗分就该出手了。你需要做的，就是发掘出这个答案，然后直接输出。

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

例如，本班月赛中有一道题：

U480179 【新版骗分导论 - 修订版】炸毁计划

你发现问题了吗？那么多座桥，炸一座就破坏岛屿的联系，可能性微乎其微（除非特别设计数据）。那么，我们的骗分策略就出来了：对于所有询问，输出 yes。果然，此算法效果不错，得 80 分。

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

4.3 寻找规律

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

某些题目会给你很多样例，你就可以观察他们的特点了。有时，数据中的某一个（或几个）数，能通过简单的关系直接算出答案。

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

这样的题目大多出现在 NOI 或更高等级的比赛中，本人蒟蒻一个，就不举例了。传说某人去省选时专门琢磨数据的规律，结果有一题得了 30 分。

4.4 小数据杀手——打表

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

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

先看一个例子：NOIP2003 栈

这题看似复杂，但数据范围太小，\(n \le 18\)。所以，骗分程序就好写了：

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]);

测试结果不言而喻，AC 了。

学完这一章，你已基本掌握了骗分技巧。下面的内容涉及一点算法知识，难度有所增加。蒟蒻中的蒟蒻可以止步于此了。

第五章 做贪心的人

5.1 贪心的算法

给你一堆纸币，让你挑一张，相信你一定会挑面值最大的。其实，这就是贪心算法。

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

举个例子：这是我们的市队选拔的一道题。

U480191 【新版骗分导论 - 修订版】有趣的问题

这题让人望而生畏，但我们有贪心的手段。每个二元组的 \(a\) 值是乘到答案中的，所以 \(a\) 越大越好，那么只要选择出最小的 \(k\) 个去掉即可。代码就不写了，因为这个涉及到下一章的内容：排序。

此代码得 20 分。

5.2 贪心的得分

我们已经学了很多骗分方法，但他们中的大多效率并不高，一般能骗 10∼20 分。这不能满足我们的贪心。

然而，我们可以合成骗分的程序。举个最简单的例子，有些含有无解情况的题目，

它们同样有样例。我们可以写这个程序

if(是样例) printf(样例);

else printf(“-1”);

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

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

大量能骗分的问题都能用此法，大家可以试试用新方法骗 2.1 中的例子NOIP2012普及组 文化之旅

第六章 C++的福利——STL

请P党们跳过本章，这不是你们的福利！重复，这不是你们的福利！

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

6.1 快速排序

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

#include//这是必须的

sort(A,A+n);//对一个下标从0开始存储，长度为n的数组升序排序

就这么简单，完成了 P 党一大堆代码干的事情。

6.2 "如意金箍棒"

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

下面看看它的几种操作：

vector V;//定义

V.push_back(x);//末尾增加一个元素x

V.pop_back();//末尾删除一个元素

V.size();//返回容器中的元素个数

//它同样可以使用下标（如 V[n] ）访问。（从0开始）

第七章 "宁为玉碎，不为瓦全"

至此，我已介绍完了我所知的骗分方法。如果上面的方法都不奏效，我也无能为力。但是，我还有最后一招——

有句古话说：“宁为玉碎，不为瓦全”。我们蒟蒻也应有这样的精神。骗不到分，就报复一下，卡评测以泄愤吧！ 卡评测主要有两种方法：

利用死循环，故意超时；

进入终端，卡住编译器。

先介绍下第一种。代码很简单，请看：

while(1);

就是这短短一句话，就能卡住评测机长达 10s，20s，甚至更多！对于测试点多、时限长的题目，这是个不错的方法。

第二种方法也很简单，但危害性较大，建议不要在重要比赛中使用，否则可能让你追悔莫及。它就是：

#include //windows系统中使用

#include //Linux系统中使用

它非常强大，可以卡住评测系统，使其永远停止不了编译你的程序 。唯一的解除方法是，工作人员强行关机，重启，重测。当然，我不保证他们不会气愤地把你的成绩变成 0 分。请慎用此方法。

!> 太危险了，别搞！

第八章 实战演练

下面我们来做一些习题，练习骗分技巧。

我们来一起分析一下 NOIP2013 普及组的试题吧。

NOIP2013 普及组 计数问题

第 1 题，太弱了，不用骗，得 100 分。

NOIP2013 普及组 表达式求值

第 2 题，数据很大，但是可以直接输入一个数，输出它 \(\mod{10000}\)的值。得 10 分。

NOIP2013 普及组 小朋友的数字

第 3 题，是一道非常基础的 DP，但对于不知 DP 为何物的蒟蒻来说，就使用暴力算法（即 DFS）。得 20 分。

NOIP2013 普及组 车站分级

第 4 题，我们可以寻找一下数据的规律，你会发现，在所有样例中， \(M\)值即为答案。所以直接输出 \(M\)，得 10 分。

这样下来，一共得 140 分，比一等分数线还高 20 分！ 你的信心一定会得到鼓舞的。这就是骗分的神奇。

第九章 结语

骗分是蒟蒻的有力武器，可以在比赛中骗得大量分数。相信大家在这本书中收获了很多，希望本书能帮助你多得一些分。但是，最后我还是要说一句：

不骗分，是骗分的最高境界。