Alldream提高组大纲

alldream

一.普及复习

• 热身练习: 简单模拟, dfs, bfs, 简单dp, 位运算简单技巧(sum_xor)
• 模拟类问题:P1003 铺地毯,P1067 多项式输出, P1540 机器翻译, P1056 排座椅, P1328 生活大爆炸版石头剪刀布, P1563 玩具谜题, P1023 税收与补贴问题, P1031 均分纸牌, P1042 乒乓球, P1086 花生采摘, P1098 字符串的展开
• 高精度计算(P1601, P2142, P1303, P1255, P1604)

二.常规知识点

• 堆和堆排序（优先队列）
• 贪心算法进阶: (直观&最好需要数学证明最优性-调整法)(P1090, P1181, P1208, P1223, P1094, P1803, P1031, P1080, P1080, P1158)(主要练习sort, struct, cmp, 优先队列)
• 搜索建模: DFS和BFS, 隐式图转化(搜索建模),
• 搜索优化: 剪枝优化(1.可行性优化 2.最优性优化 3.记忆化)(P1092 虫食算 P1731, 生日蛋糕 P3230比赛)
• 字符串初阶: (KMP(find))
• 图论基础: 图的概念与遍历, 拓扑排序, 欧拉回路
• 图论常用算法1: 并查集(tree), 生成树(kruskal, prim),
• 图论常用算法2: 图的最短路径，最短路变形(dj堆优化, spfa(Bellman Ford), floyd)
• 动态规划1: 记忆化搜索, DP经典模型（线性、背包、区间、树状）
• 区间数据结构: 树状数组, 线段树
• 搜索进阶: 迭代加深策略, 搜索顺序的选择
• 动态规划2: 优化(单调队列优化背包问题51nod-1158 全是1的最大子矩阵)(一切形式如f[i]=min/max(g[j]) 且需要满足条件a[i]>=a[j]或者a[i]<=a[j]形式的动态规划，都可以采用单调队列优化)(jcx)
• 二分答案进阶: (初阶在普及)借教室, 架设电话线, 关押罪犯, 聪明的质检员
• 图论问题建模: 一般问题对图论问题的转换，spfa引擎的dp
• 字符串进阶: (tire)
• 初等数论: 欧拉筛，中国剩余定理，同余，逆元，扩欧
• 组合数学: 常用组合数处理（杨辉，费马小定理，卢卡斯定理），容斥原理，二项式
• 考试技巧: 构造数据, 分段得分, 骗分

省选(各凭本事)

• 对拍
• 读入优化
• 可持久化线段树(主席树)
• 位运算 补码 反码
• 双向搜索, 启发式搜索A*(*)
• 动态规划3: 状态压缩，数位DP
• maxflow
• 二分图(hungary, maxflow)
• 强联通(tarjan)
• 倍增 && LCA问题
• 博弈论：nim游戏，sg函数 *
• 概率期望：随机算法（Monte-Carlo 暴力算概率） *
• 线性代数：矩阵快速幂，N元一次方程，高斯消元，(NTT, FFT)(jcx) *
• 滑动窗口（洛谷1090，洛谷1638，leetcode上的2sum、3sum)
• 差分约束系统
• Matrix-Tree定理
• 群论，burnside引理与Polya定理
• Baby step giant step
• 欧拉函数线性筛（积性函数，狄利克雷卷积）
• Dancing Links DLX
• 各种平衡树，Link-Cut Tree
• 分块，块状链表