第一章---------简单骗分                  ------------ 1
第二章---------简单搜索                  ------------ 4
第三章---------动态规划与贪心入门        ------------ 6
第四章---------简单图论                  ------------ 10
第一章作者——askl123
骗分入门：
相信各位学弟学妹已经对OI有所了解了，那么初级骗分这种概念肯定也在第
一次NOIP（或在其他地方）有用到过吧！但是为了整个“书”的完整性，还是简单介绍一下骗分这种东西，那么开始：[已经了解者可以翻页左转]
例1：
（NOIP2011统计单词数）其中题目省略，请看输出描述最后一句话：“则直接
输出一个整数-1”。这时我[们]心中默默地笑了，随手打出一段程序，深藏功与名！
BEGIN
Writeln(‘-1);
End;
[BEGIN大写是笔者的习惯，求轻喷]
相比这种最初级的骗分方法已经无法满♂足大家的需求了……那么就来第二发吧！！
例2：
（noip2012国王游戏）恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。
首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各
写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，所
有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣
前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一
个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍
的最前面。
那么现在假设我们不知道到底该怎么做这题（显然当时我确实毫无头绪），那
我又不想交个空程序，只是想简单的初级骗分！那我们怎么骗呢（虽然我没骗
到……）？我当时的想法是特例，也就是假设题目给的顺序恰好为得出正确答案时的顺序，这样再来计算最大值就可以进行初级骗分了！！（虽然这个题我没骗到分，但用这个方法在以前还是骗到过的，所以简单介绍一下，大家喜闻乐见一下就好了）
例3：
打表！！
[例题什么的就不用了吧]
打表这种事是大家的常用手段，精髓的打表往往可以弥补算法上的漏洞！而且各种奇葩数学题的部分分往往也可以用打表一笑而过233。
可能这部分初级骗分我讲的不大好，选的例题也不好，但是还请大家见谅……即使大家已经熟知了这些题的算法，我感觉这种初级骗分的东西在学校考试中还是经常能用到的233
那么初级骗分就到此为止了。
进击的骗分&我的复杂度果然有问题：
[又是我的部分了，我也这一不知道会被放在哪里]
首先介绍一个概念：时间复杂度。简单来说就是算法的执行时间，即是
[这里实在不知道怎么打出来了……请见谅]，但是这样的求和是在太繁琐了，我们想要知道的只是最终的大概时间复杂度而已，那么我们就可以
1.将常数省略：通俗来讲就是for循环中的操作数量不计。
2.对于n^3+n^2 这个式子中可以将n^2忽略不计，同理n相对于n^2克忽
略。
3.对了log函数：底数是无所谓的，因为底数影响的只是常数时间。
4.另注明：log是个神奇的东西，是二分产生了它！！也就是说二分是极
为重要的！
那么在大概了解了时间复杂度的估算方法之后，就再说一下1s内神机（钢哥机器不算你懂的！）的运算水平
[上图引用于神队长平神的PPT
那么现在我们就可以通过数据范围来估算我们的正解算法的时间复杂度，从而更接近于正解的思路！
另外对于空间复杂度这种东西就不必多讲了吧，相信钢哥一定在开课初期对这方面做了很深♂度的讲解了（好吧我又无节操了是吧）。但是还有一个友情提示：
VAR
a:array[0..1000,0..1000] of longint;
BEGIN
writeln(sizeof(a));
end;
这个小程序就可以得出空间大小了，至于除个1024再/个1024的方法也就不
必多讲了吧！
好复杂度讲完之后就开始正题：进击的骗分吧！！
相比大家对于数据范围这4个字都不陌生吧！来个例子吧
【数据范围】
对于20%的数据，2≤n≤10；
对于40%的数据，2 ≤n≤50，0<w <10^5；
对于60%的数据，2 ≤n≤1000，0<w <10^6；
对于80%的数据，2 ≤n≤10,000；
对于100%的数据，2≤m≤n≤50,000，0<w <10^9。
那么看着这些我们要遐♀想一些什么呢？看着100%的数据努力思想算法，经过1h
的头脑风暴后犹豫着是放弃还是继续？可能大家都不会有这种情况吧[我希望是这样的！]我认为30min（因人而异吧）还想不到正解的时候就该采用骗分策略了吧！这里
的骗分当然不是指简单的writeln（’0’）那么简单了，而是要看着80%和60%的数据范围发起猛攻！真正的大型比赛600分（noip）100分与80分的差距又能有多少？！！
所以这部分进击的骗分的主旨便是：退一步海阔天空，80分何尝不丈夫(各位
学妹不要在意这些细节)，60分又差到哪去！只要这道题我不会100%算法，但我又没
暴零，那便是骗分成功！
[另外离线省个log，二分技巧，双向搜索，剪枝，贪心，随机化，启发式搜索，常数优化之类的复杂度优化我就不多说了，大家在以后的竞赛生活都会慢慢理解的！！]
但是我觉得如果你执着于20%的数据，那就有点说不过去了。。。基本上20%数据
那种都是考试最后30min啥都不会了，最后再写上去的东西……[虽然很多时候我20
分都拿不到T_T]
进击的骗分策略到这里就结束了，感觉我还是没实质性教会大家一些什么东西
T_T，但是这些技巧一定要在一次次考试中不断学习！只有掌握了这种真正的骗分技巧，方能在大赛中临危不乱！
真·骗分
好吧，我又来了！这次话题来得大一点，其实生活无处骗分啊！数学中的特值，英语，语文中的概率蒙选项，物理多选揣测出题人心理……生活中有好多都是在骗分罢了！但是说起来是骗分，实际上又何尝是“骗”呢？能得分就是硬道理啊！所以，放
心大胆地去尝试各种“骗”分技巧吧，这样把一道题的各种时间复杂度的方法都考虑
一下，想必会对你的OI生涯有益的！
第二章作者——ZZY
搜索
搜索，顾名思义，就是一种把所有可能情况都搜一遍，最优解的做法。显然，
没有比这再高的时间复杂度了，所以除非数据范围是n≤30或者数据极水，搜索是不
会让你AC一道题的。不过千万不要小看它，因为这是刚哥讲过的第二高级的算法…
（第一是DP….）当你想不出其他解法或者时间不够了，写个搜索骗骗分吧。
搜索主要分为深度优先搜索（DFS）和宽度优先搜索（BFS），还有启发式搜索、
记忆化搜索、双向搜索等等。
先来介绍比较简单的，深度优先搜索。深搜简单来说就是从一个地方出发，这个
地方可能有很多条路可走，咱先一条道走到黑，走到死胡同发现你也没到目的地，那
怎么办？当然不是撞墙，而是回到上一个路口，走下一条路，这样到最后我们会把所
有可能的路都走一遍（撞无数次墙）。我们以下面这个图为例：
其实深搜的顺序并不唯一，所以假设我们从a出发，要到h，那么我们先走a-b-e，发现没路了但是没有到h，那么我们回到b，发现没有没走过的路了，于是我们回到a，再走a-c-f-h，到h了，如果我们要求的是a到h有几种走法，那么我们到h
后也要后退，看看有没有别的路。这时重复上述过程即可。
在这个过程中，我们发现，深搜最重要的几点：一是设定后退的条件，即明确撞
墙和到目的地的情况并用代码写出来，二是不能走重复的路。
实现深搜最主要靠的是递归。我们从一个点出发，到一个点后就要从该点开始
寻，相当于以该点为起点再一次深搜，所以我们写一个过程然后不停调用自身就可
以了。
个人认为一个深搜的procedure主要分这几部分：边界条件，搜索，（若符合条件，标记，调用），恢复标记。我们以下面这道题为例。
【例1】给出一个n, 请输出n的所有全排列。
如：输入：3
输出：1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
我写的程序如下：
var a:array[1..20]of integer;
f:array[1..11]of boolean;
n:integer;
procedure go(x:longint);
但是你没有
var i:integer;
begin
if x>n then begin
for i:=1to n do
write(a[i],' ');
exit;
end;
for i:=1to n do
begin
if not f[i]then
begin
a[x]:=i;
f[i]:=true;
go(x+1);
f[i]:=false;
end;
end;
end;
begin
readln(n);
fillchar(f,sizeof(f),false);
go(1);