关于暴力做法
暴力,非常直白的就是直接硬做,不管他循环有多大,不管他数据量有多大。你要记住的一个事情就是,暴力只面向小数据,但是必定能得到正确解(前提当然是你没写错)甚至你需要进行对拍的时候你也得先写一个暴力出来才能方便对拍。
但是也因此,为了尽可能的偷分,暴力里要做尽可能的比较常数级别的优化,不要小看了这些常数级优化,说不准就能帮你多拿下一个边界上的数据点。在这里也可以大概的概括一些常见的优化思路:
剪枝
不该做的事情就要立刻停手,既然能通过当前条件推断出后续步骤已经不对,那就不要浪费无用功,每一次计算都是在消耗我们宝贵的暴力时间。甚至有些简单题就是考你如何有效剪枝,防止他搜太多直接TLE了。
各类快速运算
就算你不明白题目原本要什么算法,你也应该至少掌握一些常规的快速计算法。例如位运算,快速幂。尤其是位运算,别小看了位运算的效率。例如我现在写有:x = x/2;
,在做暴力的时候不如直接改写为x = x>>1;
,你可能会说,这两个的最终结果都一样,何必呢?问题在于除法的单次计算效率真不如直接单次位运算快,属于常数级别的优化手段,在一些比较边界的数据条件会有玄学效应
让你有可能过掉一个数据点。
STL
STL永远是你的好帮手,你永远不能忽视STL的作用,它能在你对算法一无所知的情况下仍然帮你实现功能。STL作为C++选手最强大的优势,该利用就好好利用。在这里列举一些常用的STL
sort(); //排序
next_permutation(); //列举全排列
vector<> ; //自动扩容的数组
queue<> ; //队列
stack<> ; //栈
priority_queue<> ; //优先队列,会自动帮你排序,本质是个堆
map< , > ; //映射,帮你自动做映射
hash_map< , > ; //哈希表,如果你不想自己构建的话,和map有点类似,但是速度比map还快
暂时想到这些,等以后想起来还有什么再做补充
标签:指南,map,运算,STL,C++,优化,暴力 From: https://www.cnblogs.com/ComputerEngine/p/18090298