day4讲课

2017.10.31晚上
wyf讲课

清北学堂--刷题班

数据结构

必须掌握：队列（单调队列），栈（单调栈），并查集，倍增，st表

字符串

字符串模拟
字符串hash
字符串算法O(n),kmp，扩展kmp，manacher，最小表示法

图和树

重点
最短路：dijkstra(堆优化)，spfa，Floyd
最小生成树，最小生成树的各种性质，启发式合并
割点，割边，强联通分量（容易被遗漏）
（点/边双联通分量，点简单）

数学相关

每年都有，重点
gcd，exgcd
二项式定理，杨辉三角
筛法求素数，O(n),欧拉函数
快速幂，矩阵快速幂
费马小定理，逆元
概率期望，（特别是期望）

动态规划

状压dp，对位操作
区间dp（先枚举长度，再枚举端点）
树dp（有时涉及到dp套dp，bzoj 福建省选求树的重心）
DAG（有向无环图）上的dp（根据拓扑转移）

常见的动态规划优化技巧
前缀和优化，一维二维，
单调栈，单调队列优化
线段树，堆等高级数据结构优化
斜率优化（不太可能出现）

搜索

考试技巧

分配时间
不要在一道题上写不出，打暴力过
数据分治
每场考试中一般是第二题，比较简单？尽可能快的做
稍难一点，分档题

一道题想不出，常见的方法破局：
考虑贪心
单调性
先打暴力，优化
部分分设置异常

一些题目

ps：老师很想放在考试中的

和u相邻的点有k个
for (int i=1; i<=k; ++i)
    for (int j=i+1; i<=k; ++i)
        if (!edge[i][j]) //没有边
        {
            ans = max(abs,a[i]*a[j]);
            break;
        }