黑马程序员技术交流社区

标题: 【上海校区】浅谈乱搞+暴力 [打印本页]
作者: 梦缠绕的时候    时间: 2018-10-31 09:28
标题: 【上海校区】浅谈乱搞+暴力
暴力
先说最基本的暴力。

这个世界上只有两种算啊，暴力和优化暴力。最出名的优化暴力就是分块和莫队。

分块思想
其实最常用的就是一般的分块。当然还有整除分块，一个在静态情况下，如果需要修改其实也是可以支持的但确实比较麻烦orz

整除分块这个事情还是看beautiful_cxw的博客

其实就是乱搞+数学变形，但是其实，无中生有的玄学优化。

莫队是基于分块的一种优化暴力，针对离线算法。能够接近O(nn−−√) O(n\sqrt n)O(n
n
​       
)的解决区间类型的问题。

当然有些数据出出来会卡线性排序的莫队，所以改变莫队的排序方式就能够很好的解决这些问题（保持左端点块顺序，右端点改变方式）

之前的大佬说个，人是活的，数据是死的，出题人是懒的，有些数据要用你不会的数据结构来搞，乱搞莫队大概能够搞过很多数据吧orz

其实除了莫队这样子的乱搞暴力学优化，还有一些玄学操作

剪枝
比如剪枝就分可行性剪枝，最优性剪枝等等，这些在搜索当中非常常用，最极限的就是洛谷的小木棍加强版，把剪枝发挥到极限

搜索还有一种A* 搜索，但不巧我水平较低，真的不会，只是听说过…但A* 的随机化玄学搜索能够优化时间。是个很不错的算法。

hash
然后对于字符串的暴力，由于字符串难的题真的非常建模（后缀数组还不会的孩子请面壁），一些题目就干脆直接暴力hash，这个世界上大概还真的没有hash解决不了的字符串题，如果有，就用双hash，联赛范围内大概还没有能够卡掉双hash的数据（出题人非常的懒，但双hash很有可能会TLE）。

打表
暴力不知道包不包括打表，有些题还真的是打表题，NOIP有真言“打表出省一”不是瞎吹的，打表找规律是OIer们对数据本身的敏感程度的考验orz，而且对你推不出的一些数论规律，打表显然要节省很多时间。

有时候可以优化一些暴力来搞一搞，大力出奇迹嘛。

然后能够优化的时间空间一定要保证打对的情况下使劲优化（你说快读快写没用？），滚动数组啥的都要掏出来。

乱搞
先声明，乱搞不是瞎搞，是有针对性的时间（空间）的非正确性或者局部正确的玄学优化

随机
随机的其实还有很多乱搞操作。也有很多高端算法用的就是随机（比如Miller-Robin），在实战dfs的时候就有一种BOGO算法复杂度是O(玄学) O(玄学)O(玄学)，大致意思自己百度猴子算法，类似于猴子定理吧…然后在随机取模的时候优化一下对于一些范围较小的数据就可以卡过了。

包括在图论当中的SPFA队列当中的随机取点（当然如果出现这样子的情况就会用到dijstra）。

然后在随机当中非常常用的就是卡时输出，这个有些情况下还真的贼有用！卡时怎么搞就去百度一下…

然后有些dp神优化的题大概也能够利用玄学随机找出最优（局部）转移状态来乱搞。（但估计没什么卵用）

dp贪心
显然，dp贪心是错的，但是有些数据你在找不到正确解法或者很难优化（你不会斜率/四边形不等式/单调队列），然而数据非常大，O(n2) O(n^2)O(n
2
)的算法显然过不了，那么对于大数据就可以用贪心来解决骗分，小数据还是用正解。贪心是在保证已有分数的基础上瞎搞的结果。

分类讨论
这个其实比较常用，也不能算是真的乱搞，但是是保证乱搞的分数是增长的必备技能。小数据暴力就可以过那为什么不用暴力，大数据就交给乱搞嘛！当然如果分类过多就有可能出现内存不足的情况（内部开内存真的比较…orz）

玄学二分查找
其实这个和模拟退火比较像，但是其实不需要像模拟退火这样子有个随机的点，只需要缩小二分范围，默认最优解在当前二分范围（有可能不在这个范围内）内并且保持单峰（有可能不是单峰，双峰或者平底锅，那你可以打个三分啥的乱搞，提高可能），就可以二分判断正确性了orz

分解质因数
这个其实比较骚的，因为在数论里大部分算法都是基于唯一质数分解定理的，而且分解质因数真的很好打，这个随便乱搞其实能够解决很多正确算法的中档数据。然后会发现有的数特别大不知道是不是素数（欧拉筛不出来），那就当他是大素数就可以了嘛！管他呢！

假设既定成立结论
这个是没有办法的办法。有些题（比如一些二元组的题或者序列的题），你真的想不出正解，那就猜这个结论，然后举反例来hack。如果你想出一个可能正确你举不出反例又找不到证明方式的那就照着打吧（还是针对你没有把握的那一档数据，小的保留暴力），说不定就蒙对了或者骗到分了。

STL
这个东西就比较有意思了。vector玄学暴力开数组，能开多大开多大，能骗点分骗点分，queue和priority_queue这种就要用得好了。bitset暴力压缩。只要CCF的评测集不是特别慢（如果开O2那就无所谓了），大概还是能够水一把过去的。

（欢迎随时补充！）
---------------------
作者：朝阳的二愣子
来源：CSDN
原文：https://blog.csdn.net/qq_42037034/article/details/83513778
版权声明：本文为博主原创文章，转载请附上博文链接！

作者: 不二晨    时间: 2018-10-31 14:26
作者: 魔都黑马少年梦    时间: 2018-11-1 16:11
作者: 魔都黑马少年梦    时间: 2018-11-8 17:06




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2