如何高效地骗分


前言

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

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

请一定坚定信仰!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.

使用广泛度:※※

期望骗分:※※


样例大法好

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

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

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

期望骗分:-


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

3 条评论

vanilla · 2017年11月12日 7:11 下午

%%%,早看到我考试就用上了

fzj · 2017年11月10日 3:38 下午

kb把骗分当娱乐,%%%

konnyakuxzy · 2017年11月9日 10:21 下午

Orz这怎么能是【娱乐向】呢?
明明应该是【算法】吧?
好吧,kb是检验真理的唯一标准。
(发现自己出现频率有点高。害怕.jpg)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *