转载于 https://vijos.org/discuss/5343eb6c48c5fc86468b457d
本篇文章将原文做了一定修改,给读者带来更好的阅读体验
文章有亿点点长,请小心食用!
新 版 骗 分 导 论
$\text{THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD}$
蒟 蒻 的 宝 书
目录
第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章 C++的福利
6.1 快速排序
6.2 “如意金箍棒”
第7章 “宁为玉碎,不为瓦全”
第8章 实战演练
第9章 结语
第1章 绪论
在 $\text{Oier}$ 中,有一句话广为流传:
任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。
这就是著名的 $\text{lzn}$ 定理。然而,我们这些蒟蒻们,没有经过那么多历练,却要和大牛们同场竞技,我们该怎么以弱胜强呢?答案就是: 骗分
那么,骗分是什么呢?骗分就是用简单的程序(比标准算法简单很多,保证蒟蒻能轻松搞定的程序),尽可能多得骗取分数。
让我们走进这本《新版骗分导论》,来学习骗分的技巧,来挑战神牛吧!
第2章 从无解出发
2.1 无解情况
在很多题目中都有这句话:“若无解,请输出 $-1$ ”
看到这句话时,骗分的蒟蒻们就欣喜若狂,因为——数据中必定会有无解的情况!
那么,只要打出下面这个程序:
printf("-1");
就能得到 $10$ 分,甚至 $20$ 分,$30$ 分
举个例子:
$\text{NOIP2012}$ 第 $4$ 题,文化之旅
题目描述 $\text{Description}$
有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。
现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。
输入描述 $\text{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_{i,j}$ ,$a_{i,j} = 1$ 表示文化 $i$ 排斥外来文化 $j$($i$ 等于 $j$ 时表示排斥相同文化的外来人),$a_{i,j} = 0$ 表示不排斥(注意 $i$ 排斥 $j$ 并不保证 $j$ 一定也排斥 $i$)。
接下来的 $M$ 行,每行三个整数 $u,v,d$,每两个整数之间用一个空格隔开,表示国家 $u$ 与国家 $v$ 有一条距离为 $d$ 的可双向通行的道路(保证 $u$ 不等于 $v$,两个国家之间可能有多条道路)。
输出描述 $\text{Output Description}$
输出只有一行,一个整数,表示使者从起点国家到达终点国家最少需要走的距离数(如果无解则输出 $-1$)。
样例输入 $\text{Sample Input}$
输入样例 $1$
2 2 1 1 2
1 2
0 1
1 0
1 2 10
输入样例 $2$
2 2 1 1 2
1 2
0 1
0 0
1 2 10
样例输出 $\text{Sample Output}$
输出样例 $1$
-1
输出样例 $2$
10
数据范围及提示 $\text{Data Size and Hint}$
【输入输出样例 $1$ 说明】
由于到国家 $2$ 必须要经过国家 $1$,而国家 $2$ 的文明却排斥国家 $1$ 的文明,所以不可能到达国家 $2$。
【输入输出样例 $2$ 说明】
路线为 $1 -> 2$。
【数据范围】
对于 $20 \%$ 的数据,有 $2 \le N \le 8, K \le 5$;
对于 $30 \%$ 的数据,有 $2 \le N \le 10, K \le 5$;
对于 $50 \%$ 的数据,有 $2 \le N \le 20, K \le 8$;
对于 $70 \%$ 的数据,有 $2 \le N \le 100, K \le 10$;
对于 $100 \%$ 的数据,有 $2≤N≤100,1≤K≤100,1≤M≤N2,1≤ki≤K,1≤u,v≤N,1≤d≤1000,S≠T,1 ≤S, T≤N$。
这道题看起来很复杂,但其中有振奋人心的一句话“输出 $-1$”,蒟蒻们考试时就高兴坏了,随手打了个
printf("-1");
得 $10$ 分。
2.2 样例——白送的分数
每道题目的后面,都有一组“样例输入”和“样例输出”。它们的价值极大,不仅能初步帮你检验程序的对错(特别坑的样例除外),而且,如果你不会做这道题(这种情况蒟蒻们已经司空见惯了),你就可以直接输出样例!
例如美国的 $\text{USACO}$,它的题目有一个规则,就是第一组数据必须是样例。那么,只要你输出所有的样例,你就能得到 $100$ 分(满分 $1000$)!这是相当可观的分数了。
现在,你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句,你就能实现这些骗分方法。那么,如果你有一定的基础,请看下一章——我将教你怎样用简单方法骗取部分分数。
第3章 “艰苦朴素永不忘”
本章的标题来源于《学习雷锋好榜样》的一句歌词,但我不是想教导你们学习雷锋精神,而是学习骗分!
看到“朴素”两个字了吗?它们代表了一类算法,主要有模拟和 $\text{DFS}$ 。下面我就来介绍它们在骗分中的应用。
3.1 模拟
所谓模拟,就是用计算机程序来模拟实际的事件。例如 $\text{NOIP}2012$ 的“寻宝”,就是写一个程序来模拟小明上藏宝塔的动作。
较繁的模拟就不叫骗分了,我这里也不讨论这个问题。
模拟主要可以应用在骗高级数据结构题上的分,例如线段树。下面举一个例子来说明一下。
排 队($\text{USACO}2007~\text{January Silver}$)
【问题描述】
每天,农夫约翰的 $N (1 \le N \le 50000)$ 头奶牛总是按同一顺序排好队,有一天,约翰决定让一些牛玩一场飞盘游戏($\text{Ultimate Frisbee}$),他决定在队列里选择一群位置连续的奶牛进行比赛,为了避免比赛结果过于悬殊,要求挑出的奶牛身高不要相差太大。
约翰准备了 $Q (1 \le Q \le 200000)$ 组奶牛选择,并告诉你所有奶牛的身高 $H_i (1 \le H_i \le 10 ^ 6$ )。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。
注意:在最大的数据上,输入输出将占据大部分时间。
【输入】
第一行,两个用空格隔开的整数 $N$ 和 $Q$ 。
第二到第 $N + 1$ 行,每行一个整数,第 $i + 1$
行表示第 $i$ 头奶牛的身高 $H_i$
第 $N + 2$ 到第 $N + Q + 1$ 行,每行两个用空格隔开的整数 $A$ 和 $B$ ,表示选择从 $A$ 到 $B$ 的所有牛 $(1 \le A \le B \le N)$
【输出】
共 $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 j = a; j <= b; j ++ )
{
if (h[i] < min) min = h[i];
if (h[i] > max) max = h[i];
}
printf("%d\n", max - min);
}
程序简洁明了,并且能高效骗分。本程序得 $50$ 分。
3.2 万能钥匙—— $\text{DFS}$
$\text{DFS}$ 是图论中的重要算法,但我们看来,图论神马的都是浮云,关键就是如何骗分。下面引出本书的第 $2$ 条定理:
$\text{DFS}$ 是万能的。
这对于你的骗分是至关重要的。比如说,一些动态规划题,可以 $\text{DFS}$;数学题,可以 $\text{DFS}$;剪枝的题,更能 $\text{DFS}$。下面以一道省选题为例,解释一下 $\text{DFS}$ 骗分。
例题:$\text{NOIP}2003$,采药
题目描述 $\text{Description}$
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
输入描述 $\text{Input Description}$
输入第一行有两个整数 $T (1 \le T \le 1000)$ 和 $M (1 \le M \le 100)$,用一个空格隔开,$T$ 代表总共能够用来采药的时间,$M$ 代表山洞里的草药的数目。接下来的 $M$行 每行包括两个在 $1$ 到 $100$ 之间(包括 $1$ 和 $100$)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出描述 $\text{Output Description}$
输出包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
样例输入 $\text{Sample Input}$
70 3
71 100
69 1
1 2
样例输出 $\text{Sample Output}$
3
数据范围及提示 $\text{Data Size and Hint}$
对于 $30 \%$ 的数据,$M \le 10$;
对于全部的数据,$M \le 100$。
这题的方法很简单。我们瞄准 $30 \%$ 的数据来做,可以用 $\text{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 <bits/stdc++.h>
using namespace std;
int main()
{
srand(time(NULL)); //输出随机数前执行此语句
printf("%d", rand() % X); //输出一个0 ~ X - 1的随机整数。
return 0;
}
这种方法适用于输出一个整数(或判断是否)的题目中,答案的范围越小越好。让老天决定你的得分吧。
据说,在 $\text{NOIP2013}$ 中,有人最后一题不会,愤然打了个随机数,结果得了 $70$ 分啊!!
4.2 猜测答案
有些时候,问题的答案可能很有特点:对于大多数情况,答案是一样的。这时,骗分就该出手了。你需要做的,就是发掘出这个答案,然后直接输出。
有时,你需要运用第 $3$ 章中学到的知识,先写出朴素算法,然后造一些数据,可能就会发现规律。
例如,本班月赛中有一道题:
好好好 大骗特骗
写的确实好啊
前排资瓷!
可以的可以的
e,其实3.1例子用ST表也是能水过的
好活
+1
已收藏
NP