「骗分导论（复制过来的）」

骗分导论（复制过来的）

板块灌水区
楼主Shine__star
当前回复2
已保存回复2
发布时间2024/10/10 14:03
上次更新2024/10/10 14:36:19

被骇客银狼阻止的越权访问保存失败

骗分导论（复制过来的）

Shine__star楼主2024/10/10 14:03

\Huge{\text{$新 版 骗 分 导 论$}}

\texttt{$THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD$}

\texttt{蒟 蒻 的 宝 书}

[TOC]

第1章绪论

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

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

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

骗分

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

第2章从无解出发

2.1 无解情况

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

printf("-1");

就能得到10分，甚至20分，30分！
举个例子： NOIP2012第4题，文化之旅
这道题看起来很复杂，但其中有振奋人心的一句话“输出-1”，我考试时就高兴坏了（当时我才初一，水平太烂），随手打了个printf("-1");,得10分。

2.2 样例——白送的分数

每道题目的后面，都有一组“样例输入”和“样例输出”。它们的价值极大，不仅能初步帮你检验程序的对错（特别坑的样例除外），而且，如果你不会做这道题（这种情况蒟蒻们已经司空见惯了），你就可以直接输出样例！
例如美国的USACO，它的题目有一个规则，就是第一组数据必须是样例。那么，只要你输出所有的样例，你就能得到100分（满分1000）！这是相当可观的分数了。
现在，你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句，你就能实现这些骗分方法。那么，如果你有一定的基础，请看下一章——我将教你怎样用简单方法骗取部分分数。

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

本章的标题来源于《学习雷锋好榜样》的一句歌词，但我不是想教导你们学习雷锋精神，而是学习骗分！
看到“朴素”两个字了吗？它们代表了一类算法，主要有模拟和DFS。下面我就来介绍它们在骗分中的应用。

3.1 模拟

所谓模拟，就是用计算机程序来模拟实际的事件。例如NOIP2012的“寻宝”，就是写一个程序来模拟小明上藏宝塔的动作。
较繁的模拟就不叫骗分了，我这里也不讨论这个问题。
模拟主要可以应用在骗高级数据结构题上的分，例如线段树。下面举一个例子来说明一下: 排队(USACO 2007 January Silver)
对于这个例子，大牛们可以写个线段树，而我们蒟蒻，就模拟吧。
附模拟程序：

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骗分。
例题：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章骗分的关键——猜想

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$ 座桥 $(A_i,B_i)$ 表示第 $i$ 座桥连接了 $A_i$ 与 $B_i$ 这两座城市。
现在，敌人的炸药只能炸毁其中一座桥，请问在仅仅炸毁这一座桥的情况下，能否保证所有岛屿安全，都能联通起来。
现在给出 $Q$ 个询问 $C_i$ ，其中 $C_i$ 表示桥梁编号，桥梁的编号按照输入顺序编号。每个询问表示在仅仅炸毁第 $C_i$ 座桥的情况下能否保证所有岛屿安全。如果可以，在输出文件当中，对应输入顺序输出yes，否则输出no（输出为半角英文单词，区分大小写，默认为小写，不含任何小写符号，每行输出一个空格，忽略文末空格）。

【输入格式】
第一行三个整数 $N$ ， $M$ ， $Q$ ，分别表示岛屿的个数，桥梁的个数和询问的个数。
第二行到第 $M+1$ 行每行两个整数。第 $i+1$ 行有两个整数 $A_i,B_i$ 表示这个桥梁的属性。
第 $M+2$ 行有 $Q$ 个整数 $C_i$ 表示查询。

【输出格式】
$Q$ 行，表示查询结果。

【样例】
destroy.in

2 1 1
1 2
1

destroy.out

no

【样例范围】
对于 $80\%$ 的数据， $N\le100$ 。
对于 $100\%$ 的数据， $N\le1000$ ， $N,Q\le M\le2000$ 。

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

4.3 寻找规律

首先声明：本节讲的规律不是正当的算法规律，而是数据的特点。
某些题目会给你很多样例，你就可以观察他们的特点了。有时，数据中的某一个（或几个）数，能通过简单的关系直接算出答案。
只要你找到了规律，在很多情况下你都能得到可观的分数。
这样的题目大多出现在NOI或更高等级的比赛中，本人蒟蒻一个，就不举例了。传说某人去省选时专门琢磨数据的规律，结果有一题得了30分。

4.4 小数据杀手——打表

我认识一个人，他在某老师家上C语言家教，老师每讲一题，他都喊一句：“打表行吗？”
他真的是打表的忠实粉丝。表虽然不能乱打，但还是很有用的。
先看一个例子：NOIP2003 栈
这题看似复杂，但数据范围太小， $N\le18$ 。所以，骗分程序就好写了：

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 贪心的算法

给你一堆纸币，让你挑一张，相信你一定会挑面值最大的。其实，这就是贪心算法。
贪心算法是个复杂的问题，但你不用管那么多。我们只关心骗分。给你一个问题，让你从一些东西中选出一些，你就可以使用贪心的方法，尽量挑好的。
举个例子：这是我们的市队选拔的一道题。

题目: 有趣的问题

【问题描述】
2013 年的NOIP 结束后， Smart 发现自己又被题目碾压了，心里非常地不爽，于是暗下决心疯狂地刷数学题目，做到天昏地暗、废寝忘食，准备在今年的中考中大展身手。
有一天，他在做题时发现了一个有趣的问题：

给定 $n$ 个二元组 ${(ai, bi)}_{i}$ ，记函数：

y=100\times \Sigma(ai)/\Sigma(bi);

将函数 $y$ 的值四舍五入取整。
现将 $n$ 个二元组去掉其中的 $k$ 个计算一个新的 $y$ 值（也四舍五入取整），均能满足： $y \le z$ ，求出最小的 $z$ 值。Smart 想让你帮他一起找出最小的 $z$ 值。

【输入格式】
输入包含多组测试数据。每组测试数据第一行两个整数： $n$ 和 $k$ ；
第二行为 $n$ 个数： $a_1~a_2 ~\cdots~ a_n$ ；
第三行为 $n$ 个数： $b_1 b_2 \cdots b_n$ 。
输入数据当 $n$ 、 $k$ 均为 $0$ 时结束。

【输出格式】
对于每组测试数据输出一行，即找出的最小的 $z$ 值。
注意：**为避免精度四舍五入出现误差，测试点保证每个函数值与最终结果的差值至少为 $0.001$ 。 **

【样例】
math.in

math. out

83
100

【数据范围】
对于 $40\%$ 的数据： $n\le20$ ；
对于 $70\%$ 的数据： $n\le1000$ ；
对于 $100\%$ 的数据： $n\le10000$ ， $a_i,b_i$ 都在int 范围内。

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

5.2 贪心地得分

我们已经学了很多骗分方法，但他们中的大多效率并不高，一般能骗10~20分。这不能满足我们的贪心。
然而，我们可以合成骗分的程序。举个最简单的例子，有些含有无解情况的题目，它们同样有样例。我们可以写这个程序:

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

这样也许能变10分为20分，甚至更多。
当然，合并骗分方法时要注意，不要重复骗同一种情况，或漏考虑一些情况。
大量能骗分的问题都能用此法，大家可以试试用新方法骗2.1中的例子“文化之旅”。

第6章 C++的福利

（请P党们跳过本章，这不是你们的福利）
在C++中，有一个好东西，名唤STL，被万千OIer们所崇拜，所喜爱。下面让我们走进STL。

6.1 快速排序

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

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

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

6.2 “如意金箍棒”

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

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

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

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

至此，我已介绍完了我所知的骗分方法。如果上面的方法都不奏效，我也无能为力。但是，我还有最后一招——有句古话说：“宁为玉碎，不为瓦全”。我们蒟蒻也应有这样的精神。骗不到分，就报复一下，卡评测以泄愤吧！
卡评测主要有两种方法：一是死循环，故意超时；二是进入终端，卡住编译器。
先介绍下第一种。代码很简单，请看：

while(1);

就是这短短一句话，就能卡住评测机长达10s，20s，甚至更多！对于测试点多、时限长的题目，这是个不错的方法。第二种方法也很简单，但危害性较大，建议不要在重要比赛中使用，否则可能让你追悔莫及。它就是：

#include<con> //（windows系统中使用）
#include</dev/console> //（Linux系统中使用）

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

第8章实战演练

下面我们来做一些习题，练习骗分技巧。
我们来一起分析一下NOIP2013普及组的试题吧。

记数问题（NOIP普及组2013第一题）(count.cpp/c/pas)
表达式求值（noip2013普及组第二题）(expr.cpp/c/pas)
小朋友的数字（noip2013普及组第三题）(number.cpp/c/pas)
车站分级（NOIP普及组2013第四题）(level.cpp/c/pas)

[ ] 第1题，太弱了，不用骗，得100分。
[ ] 第2题，数据很大，但是可以直接输入一个数，输出它mod 10000的值。得10分。
[ ] 第3题，是一道非常基础的DP，但对于不知DP为何物的蒟蒻来说，就使用暴力算法（即DFS）。得20分。
[ ] 第4题，我们可以寻找一下数据的规律，你会发现，在所有样例中，M值即为答案。所以直接输出M，得10分。
这样下来，一共得140分，比一等分数线还高20分！你的信心一定会得到鼓舞的。这就是骗分的神奇。

第9章结语

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

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

不理解?

点此回到顶部.

2024/10/10 14:03

第1章 绪论

第2章 从无解出发