笔试技巧：学会根据数据范围猜知识点

一般1s 时间限制的题目，时间复杂度能跑到 1e8 左右（ python 和 java 会少一些，所以建议大家使用c/c++ 做笔试题）。

n 范围 20 以内：

O(n*2^n)

状压搜索 /dfs 暴搜

n 范围 200 以内：

O(n^3)

三维 dp

n 范围 3000 以内：

O(n^2)

二维 dp 背包 枚举 二维前缀和等

n 范围 1e5 以内：

O(n√n)

暴力求因子等

n 范围 1e6 以内：

O(nlogn)

二分答案 使用各种 stl 并查集 欧拉筛等

n 范围 1e7 以内：

O(n)

双指针 线性 dp 差 分 / 前缀和

n 范围 1e14 以内：

O(√n)

求约数和 约数个数

贪心指每一步都做出当前最优的选择。一般解决的问题有如下特点：局部最优能导致全局最优。

请注意，贪心并不是万能的！

有n个物品。每个物品有价值v[i]，以及重量w[i]。

现在取总重量不超过m的物品，问取的物品价值最大是多少？（背包问题）

策略1：按照价值降序排列，每次取价值最高的。

策略2 ：按照重量升序排列，每次取重量最轻的。

策略3 ：按照价值/重量（即单位价值）降序排列，每次取单位价值最高的。

顾名思义，用for循环枚举所有情况。

借助n进制的性质进行枚举。

适合场景：共有n个物品，每个物品有m种状态，枚举所有物品的所有状态，复杂度为O(m^n)。

二进制状压枚举的写法：

经典问题：给定n个数a1、a2……an，每个数可选可不选，列举所有可能的方案。