骗分导论 CSP、NOIP、蓝桥杯、PAT、USACO等竞赛的算法骗分技巧 轻松省三_蓝桥杯骗分

骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证新手能轻松搞定的程序），尽可能多得骗取分数。这个主要是因为CSP、NOIP、蓝桥杯、PAT 等竞赛的 OI赛制 决定的，只比对输出结果。

打油诗：

数学上来先打表，贪心只能过样例。
ＤＰ一般看规律，模拟只会猜题意。
图论强行套模板，组合数学靠运气。
分治做得像枚举，计算几何瞎暴力。
数据结构干瞪眼，数论只会ＧＣＤ。
递归递推伤不起，搜索茫然ＴＬＥ。

骗分过样例，暴力出奇迹
暴搜挂着机，打表出省一
数学先打表，DP看运气
穷举TLE，递推UKE
模拟 MLE，贪心还CE
N方过百万，暴力踩标算
肥修赛大象，只是代码短
想要骗到分，就要有方法
图论背模板，数论背公式
动规背方程，高精背代码
如果都没背，干脆输样例

掰开讲：

1、 若无解，请输出-1

在很多题目中都有这句话：“若无解，请输出-1.”。

printf("-1");

2、 样例——白送的分数

每道题目的后面，都有一组“样例输入”和“样例输出”。它们的价值极大，不仅能初步帮你检验程序的对错，而且，如果你不会做这道题，你就可以直接输出样例！

例如USACO，它的题目有一个规则，第一组数据必须是样例。那么，只要你输出所有的样例，你就能得到100分（满分1000）！这是相当可观的分数了。

只要你会基本的输入输出语句，你就能实现这些骗分方法。

3、模拟

所谓模拟，就是用计算机程序来模拟实际的事件。例如NOIP2012的“寻宝”，就是写一个程序来模拟小明上藏宝塔的动作。

模拟主要可以应用在骗高级数据结构题上的分，例如线段树。

排  队(USACO 2007 January Silver)
 
【问题描述】
每天，农夫约翰的N（1≤N≤50000）头奶牛总是按同一顺序排好队，有一天，约翰决定让一些牛玩一场飞盘游戏（Ultimate Frisbee），他决定在队列里选择一群位置连续的奶牛进行比赛，为了避免比赛结果过于悬殊，要求挑出的奶牛身高不要相差太大。
约翰准备了Q（1≤Q≤200000）组奶牛选择，并告诉你所有奶牛的身高Hi（1≤  Hi ≤106）。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。
注意：在最大的数据上，输入输出将占据大部分时间。
【输入】
第一行，两个用空格隔开的整数N和Q。
第2到第N+1行，每行一个整数，第i+1行表示第i头奶牛的身高Hi
第N+2到第N+Q+1行，每行两个用空格隔开的整数A和B，表示选择从A到B的所有牛（1 ≤ A ≤ B ≤ 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 i=a;i<=b;i++)
    {
        if(h[i]<min)min=h[i];
        if(h[i]>max)max=h[i];
    }
    printf(“%d\n”,max-min);
}

4、万能钥匙——DFS

DFS是图论中的重要算法，骗分导论定理：DFS是万能的

比如说，

一些动态规划题，可以DFS；

数学题，可以DFS；

剪枝的题，更能DFS。

例题：NOIP2003，采药
题目描述 Description
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
 
输入描述：
输入第一行有两个整数T（1<=T<=1000）和M（1<=M<=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
 
输出描述：
输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入：
70 3
71 100
69 1
1 2
样例输出：
3
数据范围及提示
对于30%的数据，M<=10；
对于全部的数据，M<=100。

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);
}

骗分代码如上：

5、猜想—输出随机数

#include<stdlib.h>
#include<time.h>
//以上两个头文件必须加
srand(time(NULL));
//输出随机数前执行此语句
printf(“%d”,rand()%X);
//输出一个0~X-1的随机整数。

这种方法适用于输出一个整数（或判断是否）的题目中，答案的范围越小越好。

据说，在NOIP2013中，有人最后一题不会，愤然打了个随机数，结果得了 70 分。

6、猜测答案

有些时候，问题的答案可能很有特点：对于大多数情况，答案是一样的。这时，就该骗分了。

发掘出这个答案，然后直接输出。

需要运用《骗分导论》第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
 
【样例范围】
对于80%的数据，N≤100。
对于100%的数据，N≤1000，N,Q≤M≤2000 。

问题来了，那么多座桥，炸一座就破坏岛屿的联系，可能性微乎其微（除非特别设计数据）。骗分策略就出来了：对于所有询问，输出 yes. 此算法得 80 分。

7、 小数据杀手—打表

NOIP2003 栈
 
题目描述
 
栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。
栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙
宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。
 
现在可以进行两种操作，
 
1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）
 
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）
 
使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由1 2 3生成序列2 3 1的过程。（原始状态如上图所示） 。
 
你的程序将对给定的n，计算并输出由操作数序列1，2，…，n经过操作可能得到的输出序列的总数。
 
输入描述
输入文件只含一个整数n（1≤n≤18）
 
输出描述
输出文件只有一行，即可能输出序列的总数目
 
样例输入
3
样例输出
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]);

在OI考试中最后难的题数据最后的几个，他们往往不会创造新的数据，此时就可以直接输出最后几个数据了。