【知识点】关于综合
zhzkiller
·
·
个人记录
综合知识点
upding......
算法思路
多组查询
· 考虑如何利用已知信息避免重复查询。
· 考虑各种预处理，例如前缀和。
以小见大
· 考虑特殊情况，并考虑以此为基础继续转移。
模拟优化
· 考虑高维复杂度算法，并考虑尽可能优化。
题面信息
· 数据规模：
O(\log n):\ge10^8\text{，包括各种快速幂、数论等}
O(n):10^6\text{，包括线性 dp、单调队列、单调栈等}
O(n\log n):10^5\text{，包括各种基础树形数据结构等}
O(n\log^2n):10^5\text{，包括各种高阶树形数据结构等}
O(n^2):10^3\text{，包括大多数 dp 等}
O(n^3):200-300\text{，基本只有高维 dp}
O(n^4):50-70\text{，一定是 dp}
O(2^n):10-20\text{，包括爆搜、状态压缩 dp、各种二进制等}
O(n!):\le10\text{，一定是爆搜}
· 特殊信息：
\text{各种二}:\text{二进制拆分、二分图等}
\text{图论 + k 条路优化}:\text{分层图}
\text{n 次以内无解}:\text{迭代加深搜索}
last upd:2023/10/04