目录
第 1 章 绪论
第 2 章 从无解出发
- 2.1 无解情况
- 2.2 样例——白送的分数
第 3 章 “艰苦朴素永不忘”
- 3.1 模拟
- 3.2 万能钥匙—— DFS
第 4 章 骗分的关键——猜想
- 4.1 听天由命
- 4.2 猜测答案
- 4.3 寻找规律
- 4.4 小数据杀手——打表
第 5 章 做贪心的人
- 5.1 贪心的算法
- 5.2 贪心地得分
第 6 章 “宁为玉碎，不为瓦全”
第 7 章 结语
第 1 章 绪论
在 OIer 中，有一句话广为流传：
任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。
然而，我们这些蒟蒻们，没有经过那么多历练，却要和大牛们同场竞技，我们该怎么以弱胜强呢？
答案就是**：骗分**。
那么，骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证蒟蒻能轻松搞定的程序），尽可能多得骗取分数。让我们走进这本《新版骗分导论》，来学习骗分的技巧，来挑战神牛吧！
第 2 章 从无解出发
2.1 无解情况
在很多题目中都有这句话：
若无解，请输出 。
看到这句话时，骗分的蒟蒻们就欣喜若狂，因为——数据中必定会有无解的情况！那么，只要打出下面这个程序： printf(“-1”);，就能得到 10 分，甚至 20 分，30 分！
举个例子：NOIP2012 第 4 题 文化之旅。
这道题看起来很复杂，但其中有振奋人心的一句话“输出 ”。随手打个 printf(“-1”); ，得 分。
2.2 样例——白送的分数
每道题目的后面，都有一组“样例输入”和“样例输出”。它们的价值极大，不仅能初步帮你检验程序的对错（特别坑的样例除外），而且，如果你不会做这道题（这种情况蒟蒻们已经司空见惯了），你就可以直接输出样例！
例如美国的 USACO，它的题目有一个规则，就是第一组数据必须是样例。那么，只要你输出所有的样例，你就能得到 100 分（满分 1000）！这是相当可观的分数了。
现在，你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句，你就能实现这些骗分方法。那么，如果你有一定的基础，请看下一章——我将教你怎样用简单方法骗取部分分数。
第 3 章 “艰苦朴素永不忘”
本章的标题来源于《学习雷锋好榜样》的一句歌词，但我不是想教导你们学习雷锋精神，而是学习骗分！
看到“朴素”两个字了吗？它们代表了一类算法，主要有模拟和 DFS。下面我就来介绍它们在骗分中的应用。
3.1 模拟
所谓模拟，就是用计算机程序来模拟实际的事件。例如 NOIP2012 的“寻宝”，就是写一个程序来模拟小明上藏宝塔的动作。
较繁的模拟就不叫骗分了，我这里也不讨论这个问题。
模拟主要可以应用在骗高级数据结构题上的分，例如线段树。下面举一个例子来说明一下。
排队(USACO 2007 January Silver)
【问题描述】
每天，农夫约翰的头奶牛总是按同一顺序排好队，有一天，约翰决定让一些牛玩一场飞盘游戏（Ultimate Frisbee），他决定在队列里选择一群位置连续的奶牛进行比赛，为了避免比赛结果过于悬殊，要求挑出的奶牛身高不要相差太大。
约翰准备了组奶牛选择，并告诉你所有奶牛的身高。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。
注意：在最大的数据上，输入输出将占据大部分时间。
【输入】
第一行，两个用空格隔开的整数和。
第2到第N+1行，每行一个整数，第i+1行表示第i头奶牛的身高Hi
第N+2到第N+Q+1行，每行两个用空格隔开的整数A和B，表示选择从A到B的所有牛
【输出】
共Q行，每行一个整数，代表每个询问的答案。
输入样例
6 3
1
7
3
4
2
5
1 5
4 6
2 2
输出样例
6
3
0
对于这个例子，大牛们可以写个线段树，而我们蒟蒻，就模拟吧。
附模拟程序：
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骗分。
例题：
采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有22个整数T(1 \le T \le 1000)T(1≤T≤1000)和M(1 \le M \le 100)M(1≤M≤100)，用一个空格隔开，TT代表总共能够用来采药的时间，MM代表山洞里的草药的数目。
接下来的MM行每行包括两个在11到100100之间（包括11和100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
11个整数，表示在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1
70 3
71 100
69 1
1 2
输出 #1
3
说明/提示
对于的数据，；
对于全部的数据，。
这题的方法很简单。我们瞄准 的数据来做，可以用 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 章 骗分的关键——猜想
4.1 听天由命
如果你觉得你的人品很好，可以试试这一招——输出随机数。
先看一下代码：
#include<stdlib.h>
#include<time.h>
//以上两个头文件必须加
srand(time(NULL));
//输出随机数前执行此语句
printf(“%d”,rand()%X);
//输出一个0~X-1的随机整数。
这种方法适用于输出一个整数（或判断是否）的题目中，答案的范围越小越好。让老天决定你的得分吧。
据说，在 NOIP2013 中，有人最后一题不会，愤然打了个随机数，结果得了 70 分啊！！
4.2 猜测答案
有些时候，问题的答案可能很有特点：对于大多数情况，答案是一样的。这时，骗分就该出手了。你需要做的，就是发掘出这个答案，然后直接输出。
有时，你需要运用第3章中学到的知识，先写出朴素算法，然后造一些数据，可能就会发现规律。
例如，有一道题：
炸毁计划
【问题描述】
皇军侵占了通往招远的黄金要道。为了保护渤海通道的安全，使得黄金能够顺利地运送到敌后战略总指挥地延安，从而购买战需武器，所以我们要通过你的程序确定这条战略走廊是否安全。
已知我们有N座小岛，只有使得每一个小岛都能与其他任意一个小岛联通才能保证走廊的安全。每个小岛之间只能通过若干双向联通的桥保持联系，已知有M座桥(Ai,Bi)表示第i座桥连接了Ai与Bi这两座城市。
现在，敌人的炸药只能炸毁其中一座桥，请问在仅仅炸毁这一座桥的情况下，能否保证所有岛屿安全，都能联通起来。
现在给出Q个询问Ci，其中Ci表示桥梁编号，桥梁的编号按照输入顺序编号。每个询问表示在仅仅炸毁第Ci座桥的情况下能否保证所有岛屿安全。如果可以，在输出文件当中，对应输入顺序输出yes，否则输出no（输出为半角英文单词，区分大小写，默认为小写，不含任何小写符号，每行输出一个空格，忽略文末空格）。
【输入格式】
第一行 三个整数N，M，Q，分别表示岛屿的个数，桥梁的个数和询问的个数。
第二行到第M+1行 每行两个整数。第i+1行有两个整数Ai Bi表示这个桥梁的属性。
第M+2行 有Q个整数Ci表示查询。
【输出格式】
Q行，表示查询结果。
【输入样例】
2 1 1
1 2
1
【输出样例】
no
【样例范围】
对于的数据，。
对于的数据，， 。
你发现问题了吗？那么多座桥，炸一座就破坏岛屿的联系，可能性微乎其微（除非特别设计数据）。那么，我们的骗分策略就出来了：对于所有询问，输出 yes。果然，此算法效果不错，得 80 分。
更新：再来个例子：
不可以，总司令——星战
P8819 CSP-S 2022 星战 。2022 CSP-S 第三题。
你发现问题了吗？那么多个虫洞，随机摧毁、修复就满足题目的要求，可能性微乎其微（除非特别设计数据，可惜 CCF 用脚造数据）。那么，我们的骗分策略就出来了：对于所有询问，输出 NO。果然，此算法效果不错，得 45 分。
现在知道猜测答案的厉害了吧？
4.3 寻找规律
首先声明：本节讲的规律不是正当的算法规律，而是数据的特点。
某些题目会给你很多样例，你就可以观察他们的特点了。有时，数据中的某一个（或几个）数，能通过简单的关系直接算出答案。
只要你找到了规律，在很多情况下你都能得到可观的分数。
这样的题目大多出现在 NOI 或更高等级的比赛中。传说某人去省选时专门琢磨数据的规律，结果有一题得了 30 分。
4.4 小数据杀手——打表
表虽然不能乱打，但还是很有用的。
先看一个例子：
栈
题目背景
栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。
栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。
题目描述
宁宁考虑的是这样一个问题：一个操作数序列，1,2,…,n，栈A的深度大于n。
现在可以进行两种操作，
- 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）
- 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）
使用这两种操作，由一个操作数序列就可以得到一系列的输出序列。
你的程序将对给定的n，计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数
输出格式
输出文件只有1行，即可能输出序列的总数目
输入输出样例
输入 #1
3
输出 #1
5
这题看似复杂，但数据范围太小，。所以，骗分程序就好写了：
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 章 做贪心的人
5.1 贪心的算法
给你一堆纸币，让你挑一张，相信你一定会挑面值最大的。其实，这就是贪心算法。
贪心算法是个复杂的问题，但你不用管那么多。我们只关心骗分。给你一个问题，让你从一些东西中选出一些，你就可以使用贪心的方法，尽量挑好的。
5.2 贪心地得分
我们已经学了很多骗分方法，但他们中的大多效率并不高，一般能骗 分。这不能满足我们的贪心。
然而，我们可以合成骗分的程序。举个最简单的例子，有些含有无解情况的题目，它们同样有样例。
我们可以写这个程序：
if(是样例)
printf(样例);
else
printf(“-1”);
这样也许能变 10 分为 20 分，甚至更多。
当然，合并骗分方法时要注意，不要重复骗同一种情况，或漏考虑一些情况。
大量能骗分的问题都能用此法，大家可以试试用新方法骗 2.1 中的例子“文化之旅”。
第 6 章 “宁为玉碎，不为瓦全”
至此，我已介绍完了我所知的骗分方法。如果上面的方法都不奏效，我也无能为力。
但是，我还有最后一招——有句古话说：“宁为玉碎，不为瓦全”。我们蒟蒻也应有这样的精神。骗不到分，就报复一下，卡评测以泄愤吧！
卡评测主要有两种方法：一是死循环，故意超时；二是进入终端，卡住编译器。
先介绍下第一种。代码很简单，请看：while(1); 。就是这短短一句话，就能卡住评测机长达 10s，20s，甚至更多！对于测试点多、时限长的题目，这是个不错的方法。
第二种方法也很简单，但危害性较大，建议不要在重要比赛中使用，否则可能让你追悔莫及。它就是：#include <con>（Windows 系统中使用）或 #include </dev/console> （Linux 系统中使用）。
它非常强大，可以卡住评测系统，使其永远停止不了编译你的程序。唯一的解除方法是，工作人员强行关机，重启，重测。当然，我不保证他们不会气愤地把你的成绩变成 0 分。请慎用此方法。
第 7 章 结语
分析一下 NOIP2013 普及组的试题：
- 第 1 题，太弱了，不用骗，得 100 分。
- 第 2 题，数据很大，但是可以直接输入一个数，输出它 的值。得 10 分。
- 第 3 题，是一道非常基础的 DP，但对于不知 DP 为何物的蒟蒻来说，就使用暴力算法（即 DFS）。得 20 分。
- 第 4 题，我们可以寻找一下数据的规律，你会发现，在所有样例中，M 值即为答案。所以直接输出 M，得10分。
这样下来，一共得 140 分！你的信心一定会得到鼓舞的。这就是骗分的神奇。
骗分是蒟蒻的有力武器，可以在比赛中骗得大量分数。相信大家在这本书中收获了很多，希望本书能帮助你多得一些分。
但是，最后我还是要说一句：不骗分，是骗分的最高境界。
本文作者：Yurchiu,Internet
本文链接：https://yz-hs.github.io/e78bf8b9bee6/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
