《骗分导论》

博客园同步

首先，骗分是一种必不可少的算法。

虽然不被列为一个正规算法，但是其精髓是所有 $\text{Oier}$ 都要掌握的。

有些人可能觉得骗分就是暴力，完全不是这样。

暴力是骗分的一部分，并且，暴力也是骗分的最高层次。

开篇你需要学会：

1. 随便输出一个随机数，或者答案很可能的值进行骗分。

2. 朴素简单的暴力，比方说线段树模板题的前 $60\%$ 的数据。

3. 小范围的打表。

并且，本部分不给出任何无意义，或本人觉得没有必要给出的代码。

本文 大部分 是 $\text{NOIP}$ 原题。所以请重视。

Case 1 高阶暴力

关于暴力，有这样一句名言：

NOIP2016提高，你只要会暴力，就能拿到 360 爆踩 1 等线。 —— cdcq

所以，暴力是很基础但也极其重要的算法，不是所有的人都完全掌握。

因为不是所有的题我们都能一眼秒杀正解，因此暴力不仅能拿稳部分分，还可以帮助我们找到一些性质。

比方说，采药.

你会发现，有 $30\%$ 的数据，你可以 $\text{dfs}$ 乱踩一番。

这是低阶的暴力：$30pts$.

但是，众所周知搜索可以用来记忆化，然后你写了记忆化。

然后你发现这可以用来 $\text{dp}$.

这是高阶的暴力：$100pts$.

一般来说，盲搜索都是记忆化过渡到 $\text{dp}$ 的。

再比方说，括号树.

考场上我被这题吊打，现在我来爆踩它！

首先我们机智的发现 链的性质，你用括号序列乱水，然后 $55pts$ 就到了。

再加上 $\text{Day1T1}$ 的 $100pts$，你就成功的爆踩了身边一群人。？？？

当然，暴力也可以嵌套一些算法。

比如 积木大赛

一看就是个弱智题，但是如果你一猜猜不到正解呢？

显然，根据贪心，每次把最小的那个搞到 $0$，其余的都减掉它的值；然后根据归并的原理，两边处理。

暴力是 $O(n^2)$ 的，瞬间 $70pts$.

但是，如果你会线段树，可以在 $n{\log }^{2}n$ 的时间解决，得到 $100pts$.

（一个 log 是归并的复杂度，一个 log 是线段树查询）

虽然不够优，但是满分是王道。

再比方说 玩具谜题.

这题还要暴力？

但是如果你取模写炸了，然后就可以用链表上大力搜索。

这样就可以得到 $80pts$. 接着你发现全朝向 和 全左数的性质，轻松拿到 $95pts$.

然后别人问你：怎么没满分？你说：正解写炸了。（？？？）

Case 2 打表

这里讲的，是高阶打表算法，绝不是那些垃圾的打表。

首先我们看一道题目 组合数问题.

如果你是个弱智，你就会强行回答。最多加个预处理阶乘逆元。那样的分数最高也只有 $70pts$.（似乎很高？）

但是，显然不需要这样做。注意到 $O(n\times m)$ 可以被实现，所以我们机智的预处理了杨辉三角的表。

对于每一组询问，$O(n)$ 解决。这样可以拿到 $95pts$.

当然如果你机智的用了前缀和优化，直接 $100pts$ 没悬念！

有时候，我们需要预处理一些表，才可以回答问题，否则就会直接去世。

比方说这道题目 半质数.

虽然看起来很水，但是我们来个加强：$T$ 组数据询问 $[n,m]$ 区间答案，并且 $T,n,m\le 5\times 10^6$.

其实也不难，关键是本质。

半质数可能有点复杂？那么我们先筛出质数，$O(n)$.

接着，用这些质数去筛半质数，经测试没有问题，$O(n)$ 级别，具体难计算，总之很快。

然后，对每个区间做前缀和，就可以 $O(1)$ 回答问题。

多么简单的打表题！

Case 3 寻找规律

比方说 栈 这道题目。

一看，$1\le n\le 18$，可以打表；那么表从何来？

我们只要打个弱智暴力，经过 $\text{10min}$ 的时间敲出所有答案。

然后解决问题。

有的时候规律真的很好用！

比方说有一道题，$F_i$ 表示斐波那契数列第 $i$ 项，$T$ 次询问求 ${\sum }_{i=1}^n{F}_i$ 的值。

$T,n\le 5\times 10^6$.

然后，你经过长期暴力打表发现一个规律：

$$\sum _{i=1}^n{F}_i=F_{n+2}-1$$

（实则该式子可推）然后成功解决。

Case 4 实战演练

最后一个经验： 如果不行就套数据结构板子！

比方说，$\text{NOIP2013}$ 普及组。

第一第二题还要骗分？直接 $200pts$.

第三题，你可以随便打个 $O(n^2)$ 暴力，得 $50pts$.

第四题，你打个朴素暴力，得 $50pts$.

然后你就成功得到了 $300pts$，碾压一等线！

普及组过了，那提高组呢？我们再来几套。

$\text{NOIP2016}$ 提高组。

第一题弱智题，第二题上面说了，$200pts$.

然后，蚯蚓 这道题目其实挺有意思。

首先你打 $O(n\times m)$ 暴力可以得 $35pts$.

如果你不想优化，那就这么地，也不错。

换教室 呢，你随便水个暴力，可以得到 $60$ ~ $80pts$.

你只要用快读、$\text{register}$，O2优化等利器，可以到 $80pts$.

（当然如果你发现了 $\text{Floyd}$ 可以直接 $100pts$）

愤怒的小鸟 其实是个爆搜裸题。

你只要随便写个 $\text{dp}$，就可以得到 $100pts$ 的高分。？？？

前五题你得了 $415pts$，这已经爆踩强省一等线高达 $45pts$ 左右！

怀着优雅的心情，看到最后一题。

首先，你打了个朴素暴力，把 $25pts$ 拿住了。

接着，你发现题目中的特殊性质很有意思，经过一番推导发现了性质，然后得了 $80pts$ ！！！

这里，就算你是个弱智 （？？？），也能得 $25pts$.

然后，你凭着朴素暴力成功拿下 $\text{NOIP2016}$ $440pts$ 的高分，爆踩一等线不说，还碾压了一群巨佬。

再比方 $\text{NOIP2019}$ 提高，本人亲身体验其毒瘤。

格雷码是个水题，括号树按照上面所说可以得 $55pts$.

但是个人都发现可以树形 $\text{dp}$，然后就 $100pts$ 了

怀着 $\text{AC}$ 两题的好成绩，我们已经踏入了一等线。

$\text{Day1T3}$ 竟然是全场最难，彻底把人的心情带坏。

而且，给的链还是乱序，实在丧心病狂！

首先你拿下 $10pts$ 的暴力，搞定链和菊花图，就可以弄到 $60pts$ ！

虽然这不太可能，那么我们且算你只得了 $10pts$.

愉快的到了 $\text{Day2}$，你发现第一题是个 $dp$.

但是你不会，所以拿下了暴力分 $64pts$ 就匆匆离开。

第二题，如果你会 $\text{dp}$ 那么就是 $36pts$ 至少；但是你只会暴力。

所以你只拿下了 $12pts$. 然后你大力剪枝，假设你剪枝的不太行，没有拿到 $24pts$，就是 $12pts$.

感觉 Day2 太坑

你懵逼了，不知道题目在说什么。（考场真实）

经过长时期读题，你打下了暴力，$O(n^2\times T)$，拿到了 $40pts$.

接着你发现可爱的链！得了 $55pts$.

到这里一般人可以结束了。但是你神奇地发现了完美二叉树的性质，并得到了 $75pts$.（什么 $T3$ 得分最高是个啥）

后面的你可以滚粗了。

$\text{Day1}210pts\text{Day2}151pts$.

一共 $361pts$，随随便便拿了个 $6$ 级，然后碾压巨佬，爆踩别人。

再比方说，$\text{NOIP2018}$.

前两题都是弱智题，乱切就能过掉。

货币系统题解

积木大赛 / 铺设道路题解（两题一模一样）

好吧，拿到 $200pts$ 的我们继续前进！

然后 $\text{Day1}$ 的防 $\text{AK}$ 来了：赛道修建

如果你想 $\text{AK Day1}$ 那么 戳这儿.

假设你只拿到了 $55pts$ 大众分。（就是直径、链和菊花图的部分分）。

旅行 是一道送分（指部分分），你注意到 $m=n-1$ ，然后 $60pts$ 到手滚粗 $\text{T2}$ 去了。

填数游戏 你只会 $n,m\le 8$ 的暴力打表，经过 $1.5h$ 得到表然后得了 $35pts$.

保卫王国 是道图论大题，随便水个暴力（随便指大概 $1.5h$ 吧）然后得了 $44pts$，然后就谔谔了。

然后你的总分是：

$100+100+55+60+35+44=394$，然后爆踩省一，吊打一群人！

不骗分，才是骗分的最高境界。——谚语

最后

以上就是简单水杯为你收集整理的《骗分导论》的全部内容，希望文章能够帮你解决《骗分导论》所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。