6、省选＋NOI-第六部分 技巧与思想_2020.08.27.pdf

【个人网络整理】NOIP / 省选 /NOI 知识点汇总

https://blog.csdn.net/txl199106/article/details/71504478

加*号是选学，加粗为重点，重要值排序不分先后

１.基础算法

贪心、枚举、分治、二分、倍增、*构造、高精、模拟

2.图论

图

*分数规划

树

树上倍增（LCA）

树的直径、树的重心

dfs 序

*树链剖分

3.数论

gcd、lcm

埃氏筛法

exgcd，求解同余方程、逆元

线段树、树状数组

字典树

*分块

4.动态规划

背包 DP、树形 DP、记忆化搜索、递推

区间 DP、序列 DP

*DP 优化（不涉及斜率优化、四边形不等式等等）

5.搜索

暴搜（dfs、bfs）

搜索的剪枝

启发式搜索（A*）

迭代加深搜索、* IDA*

*随机化搜索

6.其他算法

脑洞的正确使用方法

*状态压缩

网络流（dinic，SAP，ISAP 选一个，费用流写 EK 就行。*zkw 费用流），二分图

点分治，边分治，*动态点分治

树链剖分，动态树，树分块

虚树，*prufer 编码

２.数据结构

带权并查集

Splay（作为平衡树和维护区间），Treap，替罪羊树

*舞蹈链，*二进制分组，*左偏树，*超哥线段树，*后缀平衡树，*fhqTreap

3.字符串相关算法及数据结构

hash（自然溢出，双 hash）

kmp，AC 自动机，trie

后缀数组

manacher，最小表示法

*后缀自动机，*回文自动机，*后缀树

4.数学

线性筛，积性函数，容斥原理，莫比乌斯反演

exgcd，费马小定理，Lucas 定理，高中排列组合

高斯消元，概率与期望相关

中国剩余定理，BSGS，欧拉定理

矩阵乘法

单纯形法解线性规划

FFT

线性代数（行列式）

*Simpson 积分，高中求导与积分

*群论

*二维计算几何相关，*三维计算几何相关

6.搜索

模拟退火，爬山算法，*随机增量法

7.动态规划

Huffman 树，2-sat，*朱刘算法

说真的，计算几何要么全场不会，要么全场 AK。所以尽量花时间在别的地方吧。

第六部分 技巧与思想

1. 分块

分块入门

https://blog.csdn.net/qq_41997978/article/details/90233064

分块算法总结

https://blog.csdn.net/qq_36976937/article/details/82559736

数列分块入门（2019.8.15 训练）

https://blog.csdn.net/ljw_study_in_CSDN/article/details/99671908

https://blog.csdn.net/weixin_44266988/article/details/89199984

https://blog.csdn.net/qq_39670434/article/details/79510851

https://www.bilibili.com/video/BV1ms411t7xu?from=search&seid=7561110948472326096

P46 第七章 查找-分块查找

2.莫队算法

https://www.cnblogs.com/WAMonster/p/10118934.html

莫队算法

https://blog.csdn.net/sdz20172133/article/details/88242260

莫队算法总结

https://blog.csdn.net/bz_xyz/article/details/107861455