如何高效地骗分

---

前言

要知道，对于一道不会做的题，不交程序是最为愚蠢的行为。

现在列举一些实用的骗分技巧，这里的骗分不包括搜索，模拟之类的暴力算法，而是真正的 “骗”。

请一定坚定信仰！niconiconi！

---

随机化大法好

随机，是一种优秀的骗分技巧，for 一个 example。

求一个长度为 n 的序列去掉其中一段长度为 l 的序列后，剩下的最长不下降子序列长度。

$n \leq 10^5,l \leq n$

正解应该是 dp+线段树维护，在此不予赘述。考场上 xzy 大神拿了 70 分，他是怎么骗的呢？

一般的骗分导论可能止步于让你暴力搜索拿个 50 分，不够！

随机 rand 一个序列的左端点，用哈希维护使得这个值不会重复，然后删去长度为 l 的序列求最长不下降子序列。预先算好可以接受的时间复杂度即可。虽然理论上答案范围非常大以至于骗分成功可能性较小，然而在随机一些数据后我们会发现，对于纯随机数据，删去不同地方的子序列得到的答案差异并不是很大，所以可以骗很高的分（前提是你脸好）。

使用环境: 从众多选择中选一个，进行计算最优解类问题。可以使用随机选取的方式。

使用广泛度:※※

期望骗分:※※※※

---

贪心大法好

贪心，是一种优秀的骗分技巧，for 一个 example。

原题：uva12170

输入正整数 d 和 n 个正整数 $h_1,h_2,h_3…h_n$, 可以修改除了 $h_1$和 $h_n$的其他数，要求修改后相邻两个数的差的绝对值不超过 d，且修改费用最小。设 $h_i$修改后为 $h_i’$, 那么修改费用为，$\sum |h_i-h_i’|$，无解输出-1

数据范围：$n \leq 100,d \leq 10^9$

正解应该是一个非常困难的 dp，在此不予赘述。考场上 xzy 大神拿了 80 分，他是怎么骗的呢？

一般的骗分导论可能止步于让你拿到输出-1 的那 10 分，不够！

首先正着来一遍，然后反着来一遍，如果下一个不用修改就不修改，否则修改成与当前正好相差 $d$且修改费用最小的数。

使用环境: 可以做局部决策以至于最优解的时候

使用广泛度:※※※

期望骗分:※※※※※

---

打表大法好

打表，是一种优秀的骗分技巧，for 一个 example

国际象棋中骑士的移动规则和中国象棋中的马是类似的, 它先沿着一个方向移动两格, 再沿着与刚才移动方向垂直的方向移动一格。路径上的棋子并不会影响骑士的移动, 但是如果一个骑士走到了一个放有棋子的格子, 它就会攻击那个棋子。现在有一个 n*n 的棋盘, 有 k 个骑士需要被摆到棋盘上去。那么使所有骑士互不攻击的摆放方式一共有多少种呢?

7≤n≤8, 时限 5s，空间 128MB

正解应该是一个卡空间的状态压缩 dp，本蒟蒻就因为空间爆 0 了，在此不予赘述。考场上 xzy 大神拿了 100 分，他是怎么骗的呢？

由于 n 的范围非常小！你还 d 个什么 p 啊！打表啊！！！

当然打表不能瞎打，比如说先算一下你的程序跑 1h 这个表能够打多大，免得有时候强制停止程序整个表都不见了。对于表比较大的情况，不要想着打完后还复制粘贴什么的，直接用打表程序打一个新的程序出来！！！

使用环境: 数据范围较小的时候

使用广泛度:※※※

期望骗分:※※※※※

---

瞎搞大法好

瞎搞，是一种优秀的骗分技巧，for 一个 example。

bzoj4813 小 Q 的棋盘

正解应该是树形 dp 或者瞎搞, 在此不予赘述。考场上 boshi 大神拿了 100 分，他是怎么骗的呢？

首先找出树上最长链，如果走不完最长链，就是步数。走完整棵树，就是 n。否则就是 (步数-最长链)/2+最长链。事实上这个解法可以证明，但考场上谁有心思证明，还不就是瞎搞。

使用环境: 人类的第六感告诉你可以瞎搞的时候。

使用广泛度:※※※※

期望骗分:※※※

---

估答案大法好

猜测，是一种优秀的骗分技巧，for 一个 example。

bzoj1088 扫雷

正解应该是搜索或者记忆化搜索或者 dp，在此不予赘述。

分析发现，如果随机一组数据，完全不可能的情况是比较常见的，不过出题人肯定会严格限制这种数据的数量。无解也很好判断，贪心地扫一遍即可，剩下的情况输出”1”，可以拿 60 分。

如果你知道正解，其实答案只有可能是 0,1,2.

使用广泛度:※※

期望骗分:※※

---

样例大法好

样例，是一种优秀的骗分技巧。

使用环境: 当你走投无路的时候。

使用广泛度:※※※※※※

期望骗分:-