考点整理

Ruby_Z · 2019-09-02 07:24:48 · 个人记录

考点整理

附比较好的考点整理blog

题目名称以及涉及知识点

部分考点

注意事项

放个题库

BZOJ离线题库

1.数据结构

• 链表

• 栈 单调栈

• 队列 单调队列

• 堆

• 并查集 带权并查集（种类并查集）

• hash表

• Trie树

• 线段树

• 树状数组

2.图论

1.最短路

• Floyed

• Dijkstra

• Bellman-Ford

• SPFA它死了

• SPFA判负环

2.最小生成树

• Kruskal

• Prim

3.LCA

• 倍增

• Tarjan离线

4.Tarjan判断强连通分量 缩点 求割点

5.拓扑排序

欧拉回路

6.差分约束

7.二分图

二分图匹配

二分图染色

8.树链剖分blog

9.2-SAT

10.二进制优化建图

11.线段树优化建图

3.DP

专门讲DP分类的blog

• 背包DP

• 线性DP

• 区间DP

• 树形DP

• 数位DP

• 状压DP

• 概率（期望）DP

• 优化

1.二进制优化

2.单调队列优化

3.斜率优化

4.四边形不等式优化

5.高级数据结构优化

4.搜索

• BFS 双向BFS 01BFS 灌水法

• DFS

• 记忆化搜索

• A* 不会看讲解

还有其他讲解

• IDA*

（貌似比A* 更好实现）

5.数学 小学奥数

数学讲的超详细的大佬代码短

1.高精度 高精模

2.判断素数

• 判断 n 能否整除2和从2到 sqrt （n）的奇数

• 根据孪生素数的性质推出比五大的素数一定是6k两侧的数讲解

• 埃拉托斯特尼筛

• 线性筛（欧拉筛）

3.排列组合

4.快速幂

5.欧几里得和扩展欧几里得

6.乘法逆元

7.矩阵乘法

8.费马小定理

9.高斯消元

10.欧拉函数

11.概率 期望

6.字符串

• KMP

• Trie

• manacher

• string的用法及cstring中有用的函数

• 后缀数组

7.STL

• queue

• stack

• priority_queue

• deque

• bitsetbitset浅谈

• pair

• map

• vector

• set multiset

一些好用的东东

• sort

• lower_bound

• upper_bound

• next_permutation

• prev_permutation

8.技巧

tips

bugs

• 大模拟 挺重要的 基本每年noip都考

• 对拍

• 二分 三分

• 尺取法

• 前缀和 差分

• 离散化

• double四舍五入

• 限定精度找答案

• 重载运算符

• 爆搜 模拟退火 扫五十

• 骗分骗分技巧