新《骗分导论》
Ferdina_zcjb · · 个人记录
我又来不务正业了！！
如题，我们就可以看出这其实没什么用，但为了竞赛的得分最高刑性，这其实也是大多蒟蒻会学且必学的方法。
至于什么是——“骗分导论”，那就是逝世，首先是骗分，我给出了以下定义：
真香定律中说道，做出超范围的事总会遭受他人打脸，所以，骗分也是有坏处的。
骗分，顾名思义，不会写的题骗几分，积小成多，很可能骗分的蒟蒻就比认真做题 的蒟蒻高出几分。
综上，骗分导论就是研究骗分的导论（似乎啥都没说）。
要达到骗分我们要怎么做呢？？？
1.青铜：打表，最实用的骗分:
打表是性价比比较高的骗分技巧。在赛场上的最后时刻，选择打表准没错。
1）样例——白送分
很多时候，样例是做题时的帮手，他可以帮助判断你的代码是否有明显错误，也同 样可以用来骗分。美国比赛USACO当中，样例必须是第一个测试数据。
2）数学时间
有时候，关于数学的题目，且数据范围小，就直接把所有情况动手算出来，if-else直接输出。让我们来看一道例题
在这，许多的蒟蒻都不会栈，只好骗分，那么这题怎么骗分呢？ 我们定睛一看：n≤18n≤18！！！wc，真是的，这也太小了吧！ 所以我们直接掐指一算就算出来了。
int s[18] = {1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};
cin>>n;
cout<<s[a-1];
这样，我们就AC了。
3）打表的结论
打表实际上代码量有时较多，但是思考比较少，属于性价比较高的一种骗分方法。（认真）
3.白银：无解最好玩
接下来的这一章是所有蒟蒻最喜欢的：无解。话不多说，先来上例题：P1078文化之旅这是非常好的一个利用无解骗分的题目，对蒟蒻们来说，这道绿题有点难，但是请看他的最后一句话：
一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出−1）看见没有！无解输出-1！ 所以只要输出-1就可以得到10分，甚至20，30，45分！！！怎么样，是不是很神奇！！！！！！！！
4.黄金：小学数学找规律
本节讲的规律不是正当的算法规律，而是数据的特点。
先来一道例题如果不看题目，你会发现，这么一个算式，怎么算啊！
没事，你要用到找规律。
我们可以看到给了一组样例，好嘛，找不了规律。
那么这就要考验数学了，只需要用纸和笔算出来一两组小数据的结果，就能很容易发现这是斐波那契数列了。
其实就这么简单。
别看找规律麻烦，真正要用到它的时候就能派上大用场！
当然，找规律是所有的骗分技巧中最不实用的一种方法，他只能在合适的时候用，
例如斐波那契数列这道题就适用，文化之旅就不好用了。所以一定要谨慎地使用找规律。
某些题目会给你很多样例，你就可以观察他们的特点了。有时，数据中的某一个 （或几个）数，能通过简单的关系直接算出答案。
只要你找到了规律，在很多情况下你都能得到可观的分数。
5.铂金：千能的模拟
本章我们要进入算法了。
请蒟蒻中的蒟蒻自行退出。（其实留下来也行）
模拟是一种朴素算法，他在骗分里却很实用。
他主要是骗一些高级数据结构的分，最常见的就是线段树。
那么我们就来看一道不在洛谷上的有技术含量但是能用模拟骗分的USACO线段树题目。
Description
每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.
Input
* 第一行: N 和 Q. * 第2..N+1行: 第i+1行是第i头牛的身高.
* 第N+2..N+Q+1行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从A到B的所有牛.
Output
*第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0这道题一瞅就很难，我们蒟蒻不能硬啃。
我们来看看这道题怎么骗分。
找规律找不了，没有无解操作。
难道只能打表吗？
然而我们发现，这题是个线段树题，所以我们可以用模拟来骗分！
所以，我们只需要写一个程序，模拟程序。分也就骗到了：
for(int i = 1;i <= q;++i){
scanf("%d%d",&a,&b);
int nim = a;int max = b
for(int j = x;j <= y;++j){
if(h[j]<min)min=h[j];
if(h[j]>max)max=h[j];
}
printf("%d\n",max-min)
}搞定了！那么我们这章就到这儿了.
6.钻石：爆搜，最强的骗分技巧
欢迎来到爆搜这章。
爆搜，顾名思义，暴力枚举和搜索。
1）暴力枚举
暴力枚举不用说，三连击是一道很好的练习题。
那我们怎样用暴力枚举骗分呢？这块就不上代码了，累了
首先我们要清楚，暴力枚举只有在有思路的时候用。
暴力枚举一般用来骗什么分呢？有三种。
1.搜索
2.DP
3.但自己不明白这题怎么做，但有思路时所有的题有思路不会写的时候，不用想那些类似贪心、dp这类高级算法，用暴力直接求得分，有时间再钻研。
2）万能DFS
搜索里有DFS和BFS，但是BFS不适合骗分。
DFS是搜索中的重要算法，包括着回溯，但我们看来，图论神马的都是浮云，关键就是如何骗分。
DFS对于骗分是至关重要的。比如说，一些dp，可以DFS；数论，可以DFS；剪枝的题，更能DFS。下面有一道dp例题看到没！30%是10以内的！ 我们的DFS就要瞄准这里。->
void DFS(int a , int b){
if(a==n){
if(b>ans){
return;
}
}
DFS(a+1,b+w[i]);
DFS(a+1,b);
}这里，这一章就结束了。
7.王者：我命由天
1）随机数
如果你觉得你的人品很好，可以试试这一招——输出随机数。 先看一下代码：
#include<bits/stdc++.h>
int main(){
srand(time(NULL));
printf("%d\n",rand()%X);
}这种方法适用于输出一个整数（或判断是否）的题目中，答案的范围越小越好。让老天爷决定你的得分吧。 据说，在NOIP2013中，有人最后一题不会，愤然打了个随机数，结果得了70分啊!!
2)蒙的基本对
先看一道例题 发现：只有jolly和notjolly两种，而满足条件的几率很小，那我们就直接输出notjolly就行了啊！
像这样：
#include<bits/stdc++.h>
int main(){
std::cout<<"Not jolly";
return 0;
}那么这一章就到此结束了。
8.天神：贪心的合并
1）贪心算法
dp——动态规划，是一种很难的算法。你做了1000道dp，第1001道还是不会。
考场上遇到dp我们要怎么做呢？
首先需要做的就是：贪心。
在这里声明：不要害怕没过样例，直接去测试就好了。
利用贪心，谁最大就用谁，最多能得到30分。
2）合并
我们已经学了很多骗分方法，但他们中的大多效率并不高，一般能骗10~20分。这不
能满足我们的骗分要求。
然而，我们可以合并骗分的程序。举个最简单的例子，有些含有无解情况的题目，
它们同样有样例。我们可以写这个程序：
if(样例)
std::cout<<(还是样例)；
else
std::cout<<"-1";
return 0;这样也许能变10分为20分，甚至更多。
当然，合并骗分方法时要注意，不要重复骗同一种情况，或漏考虑一些情况。
大量能骗分的问题都能用此法，大家可以试试用新方法骗文化之旅
3)*C++党的福利——STL库
快速排序是一个经典算法，也是C++党的经典福利。他们有这样的代码：
#include<bits/stdc++.h>
sort(s,s+a);就这么简单，完成了P党一大堆代码干的事情。
C++里还有一种东西，叫vector容器。它可以随着元素的数量而改变大小。它其实就是数组，却比数组强得多。 以下是vector的简介：
（1）可将容器中元素翻转、复制元素、找到元素值对应的位置
（2）迭代器可以按照不同的方式遍历容器
（3）可在容器的末尾增加或删除元素
（4）可在任意位置插入数据 与数组相比，容器在自动处理容量的大小时会消耗更多的内存，但能很好的调整存储空间大小。
9.上帝：报复性心理——死循环
至此，我已介绍完了我所知的骗分方法。如果上面的方法都不奏效，我也无能为
力。但是，我还有最后一招——
有句古话说：“宁为玉碎，不为瓦全”。我们蒟蒻也应有这样的精神。骗不到分，
就报复一下，卡评测以泄愤吧！ 卡评测主要有两种方法：一是死循环，故意超
时；二是进入终端，卡住编译器。 先介绍下第一种。代码很简单，请看：
while(1)
&&
for(;;)就是这短短一句话，就能卡住评测机长达10s，20s，甚至更多！
对于测试点多、时 限长的题目，这是个不错的方法。
10.实战演练
下面我们来做一些习题，练习骗分技巧。
我们来一起分析一下NOIP2013普及组的试题吧
第一道题
第二道题
第1题，太弱了，蒟蒻都能做，不用骗，得100分。
第2题，数据很大，但是可以直接输入一个数，输出它mod 10000的值。得10分。
11.感悟
骗分是蒟蒻的有力武器，可以在比赛中骗得大量分数。
相信大家在这个博客中收获了很多，希望本帖子能帮助你多得一些分。
但是，最后我还是要对所有参加NOIP/NOI的勇士说一句（其实不是我说的）：