骗分导论
kevin1616
·
2023-08-02 12:07:44
·
生活·游记
\huge\texttt{骗 分 导 论}
\sf{Introduction\ to\ Cheating\ Scores}
\color{red}\texttt{蒟 蒻 的 宝 书}
目 录
前言
第1章 基础
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**1.2 样例输出**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**1.3 随机输出**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**1.4 猜测答案**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**1.5 数据规律**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**1.6 打表输出**
## 第2章 暴力
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**2.1 简单模拟**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**2.2 搜索算法**
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $**2.2.1 DFS**
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $**2.2.2 BFS**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**2.3 贪心算法**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**2.4 map容器**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**2.5 时间函数**
## 第3章 联系
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**3.1 联系算法**
$\ \ \ \ \ \ \ \ \ \ \ \ \ $**3.2 联系方法**
## 结语
$$\huge\texttt{骗 分 导 论}$$
$$\sf{Introduction\ to\ Cheating\ Scores}$$
$$\color{red}\texttt{蒟 蒻 的 宝 书}$$
***
## 前言
在OIer中，有一句话广为流传：“$\color{red}\texttt{任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。}$”
这就是著名的 lzn 定理。然而，我们这些蒟蒻们，没有经过那么多历练，却要和大牛们同场竞技，我们该怎么以弱胜强呢？答案就是：**骗分**。
那么，骗分是什么呢？骗分就是用较为简单的程序，尽可能多的骗取题目分数。
让我们走进这篇《骗分导论》，来学习骗分的技巧，来挑战大牛乃至于神牛吧！
## 第1章 基础
### 1.1 无解情况
在很多题目中都有这句话：“ 若无解，请输出 ```Impossible!```。”
看到这句话时，骗分的蒟蒻们就欣喜若狂，因为——数据中必定会有无解的情况！那么，只要打出下面这句话：
```cpp
cout << "Impossible!";
```
就能得到一些分数，普遍是 $\le20$ 分。
### 1.2 样例输出
每道题目的后面，都有一组样例。它们的价值极大，不仅能**初步**帮你检验程序的对错，而且，如果你不会做这道题，你就可以直接输出样例！
例如美国的 USACO，它的题目有一个规则，就是第一组数据必须是样例。那么，只要你输出所有的样例，你就能得到 100 分（满分 1000）！这是相当可观的分数了。
分数普遍是 $\le10$ 分。
### 1.3 随机输出
如果你觉得这一题的数据范围小且你的运气不错，可以试试这一招——输出随机数。
先看一下代码：
```cpp
#include
using namespace std;
int p;
int main(){
srand(time(0));
cout << rand() % (p + 1) << endl;
return 0;
}
```
这种方法适用于判断是否的题目中。你的得分是不定的，在可能性越小的情况下，分数**平均值**会越高。
### 1.4 猜测答案
有些时候，问题的答案可能很有特点：对于大多数情况，答案是一样的。这时，骗分就该出手了。你需要做的，就是发掘出这个答案，然后直接输出。
有时，你需要运用第2章中学到的知识，先写出朴素算法，然后造一些数据，可能就会发现规律。
此处向 $\color{red}\texttt{不可以，总司令}$ 致敬！
### 1.5 数据规律
某些题目会给你很多样例，你就可以观察他们的特点了。有时，数据中的某一个或几个数，能通过简单的关系直接算出答案。
只要你找到了规律，在很多情况下你都能得到可观的分数。
这样的题目大多出现在NOI或更高等级的比赛中。
### 1.6 打表输出
$\color{red}\texttt{表不能乱打，但还是很有用的。}
类似 N \le 18、len(s) \le 9、deep \le 4 等等，都是可以打表的。
#include
using namespace std;
int a[n + 1]={0所对应的答案,1所对应的答案,2所对应的答案…,n所对应的答案};
int n;
int main(){
cin >> n;
cout << a[n];
}
普遍是 100 分。
\text{学到这一章，你已掌握了基本骗分技巧。让我们走进更加复杂的骗分章节——暴力。}
第2章 暴力
2.1 简单模拟
模拟还有一个名字——暴力。所以简单来说，暴力就是完全按照题目要求做出的最自然的思路。
分数普遍是 10\sim30 分。
2.2 搜索算法
搜索是一个对于骗分至关重要的方法。比如说，一些动态规划题，可以搜索；数学题，可以搜索。
分数普遍是 20\sim50 分。
2.2.1 DFS
DFS，全称深度优先搜索。顾名思义，深度，就是一种可能一种可能遍历。普遍是：
void dfs(int step,int sum){
if(step > 搜索范围) return;
if(sum == 正确答案){
minn = min(minn,step);//因为有可能还有更优答案。
return;
}
dfs(step + 1,操作后的结果);
}
2.2.2 BFS
BFS，全称广度优先搜索。顾名思义，广度，就是一层一层遍历。普遍是：
#include
#include
#include
using namespace std;
void bfs(){
queue
step[100005];
q.push(起始);
step[起始] = 0;
while(!q.empty()){
int tmp = q.front();
if(tmp == 答案){
cout << step[tmp] << endl;
return;
}
q.pop();
if(一种条件 <= 答案){
q.push(一种条件);
step[一种条件] = step[tmp] + 1;
}
if(另一种条件 <= 答案){
q.push(另一种条件);
step[另一种条件] = step[tmp] + 1;
}
}
cout << -1 << endl;
return;
}
2.3 贪心算法
给你一堆纸币，让你挑一张，相信你一定会挑面值最大的。其实，这就是贪心算法。
贪心算法是个复杂的问题，但你不用管那么多。我们只关心贪心中的骗分。给你一个问题，让你从一些东西中选出一些，你就可以使用贪心的方法，尽量挑好的。
2.4 map容器
同样是钱的问题，有 8 张 1 元，9 张 5 元，12 张 10 元，18 张 20 元，2 张 50 元。问你有 18 张的是几元？快速的，你可以得出是 10 元。
map 容器可以将你所给予他的映射给出答案。他也算是一种数组。
有一些卡数组的题目，你可以尝试 map，有些水题可以捡漏哦！
2.5 时间函数
打暴力难免会出现一个问题：TLE。这时，计算机计算答案了很久，但是还没输出就超时了，这种浪费现象很常见。于是可以用 clock 函数缓解问题。它应用在求最大最小的时候。clock 会返回现在运行了多少毫毫秒，也就是一毫秒的千分之一。我们以时限为 1s 为例。
for(int i = 1;i <= n && clock <= 900000;i++){
//暴力
}
这时，所有大样例大概会在 900ms~1s 之间结束。一般是暴力分 +10\sim30，有时甚至可以 AC。记住一点，千万不要在求和的时候用，否则会半江红。
\text{学完这一章，你已经基本掌握了骗分技巧及方法。没有接触过更复杂的算法的人看到这一章，即可结束了。下一章，}
\text{将开启新世界的大门——联系。}
第3章 联系
3.1 联系算法
为什么把算法单独列一个表出来，因为各种各样的算法是有祖先的。
暴力求和→前缀和→差分→离散化
暴力排序→sort→priority\_queue/map
暴力数组→离散化→vector
暴力查询→pair数组→vector→unordered\_map
暴力搜索→DFS→BFS→map/vector
这些都是常见的算法祖先。可以看到，暴力都是基层的方法。如果想多拿分，可以试试往右进行优化。
3.2 联系方法
在做题中，很多时候会发现题目中有多个骗分点。此时可以进行联系性骗分。
if(第一个骗分点){
//暴力
}
else if(第二个骗分点){
//打表
}
else if(第三个骗分点){
//输出NO
}
else{
//输出Impossible!
}
结语
骗分是蒟蒻的有力武器，可以在比赛中骗得大量分数。相信大家在这本书中收获了很多，希望本书能帮助你多得一些分。如同上一章所说，骗分技巧却没有点到即止，还有更加多的骗分方法都没有指出，但是也就先到这里了。
但是，最后我还是要说一句：
\color{red}\texttt{不骗分，是骗分的最高境界。}
\color{purple}\texttt{Thanks for your reading.}
\color{purple}\texttt{Have a good day!}