原则
数据点分治,在随机数据下大概率正确,运行效率足够。
技巧
当数据较小且可以调换序列顺序时可以运用随机化。
random_shuffle
从一个优秀的初态出发,可以更快地达到终态。
可以直接搜索其附近的点判断。
模拟退火。分部随机。
如果一道题需要搜索,那么搜的方法的选取就很重要了。
可以特判超时的点。
双向搜索。
可以用贪心优先拓展某些结点(BFS)
可以剪枝。
简化数据复杂度,去重或者对于某类有特殊性质的数据另用一种方法处理。
对于部分多峰函数,可以直接暴力判断二分/三分搜到的点附近的点解决。
分治时只关注有效点可以降低复杂度。
可以将错误的贪心和别的算法结合求解,比如尝试让贪心解更优。
预处理和排除不影响最终答案的数据可以降低题目复杂度