lizbaka的周记

省选之前有好多事情要做啊……

记录一下每周做过的一些题目和总结吧

——2019.01.20

---

1.14~1.20 图论周I

1. • 点分治
2. • 点分治
3. ※
   • 点分治
4. • 虚树
5. • 二分答案
   • 并查集
6. ※
   • 最短路
   • DP
7. ※
   • 生成树
   • prufer编码，cayley公式
   • matrix-tree定理
8. • 最小生成树

---

太混了，平均一天才一题多一点

不行啊（恼）

1.21~1.27 图论周II

这周还有冬令营

emmmmmm

还是立个flag吧，WC之前至少要搞定7个题

有质量那种

---

1. • 最小割
   • 平面图转对偶图->最短路
2. • 最大权闭合子图->网络最大流
3. • Tarjan
   • 最大权闭合子图->网络最大流
4. ※
   • 二分图匹配
   • 搜索
5. ※
   • 最大权闭合子图（输出方案）->网络最大流
6. ※
   • 最小费用最大流
   • 关于这道题，讲得很好，从想到使用网络流到模型构建，完整详细地呈现了思考过程，非常值得借鉴
7. • 最大权不相交路径->最大费用最大流
   • 有点像上面那道题
   • flag回收成功@2019.01.22
8. • 最大点独立集->二分图最大匹配
   • 按奇偶性对此类棋盘黑白染色是很常用的操作
9. ※
   • 最大权不相交路径->最大费用最大流
   • 跟7差不多，然而有斜率不存在的线段
   • 应用了拆点的技巧
10. - 莫队
    - bitset

1.28~2.17 IDLE

咕咕咕

其实是去搞文化课了

2.18~2.24 DP周I

1. ※
   • 数位DP
   • 对于一些范围较小的变化量可以采取外部枚举的方式其实就是不要怕电脑累
2. • 数位DP
   • 前导零处理真的恶心
3. • 区间DP
   • 正难则反，以小区间合并到大区间为主要过程的区间DP一般采用递推形式，而以大区间划分为小区间为主要过程则可以采用记搜递归形式
4. • 后缀数组
5. ※
   • 区间DP
6. ※
   • 区间DP
7. • 数位DP
8. • 最小费用最大流
   • 应用了拆点的思想
9. ※
   • 最小费用最大流
   • 动态加边
   • 基本同8
10. • 最小/大费用最大流
11. • 完全背包
    • 嘶……我考场上是在干嘛啊
12. ※
    • 完全背包
13. • 多重背包
    • 完全背包
14. • 01背包
15. • 01背包
16. • 二维背包
17. • 区间DP
18. • 递推与DP
    • 分组背包
19. • 递推与DP
20. • 状压DP
    • 点名批评数据出锅
21. • 状压
    • 最短路
22. ※
    • 线性规划网络优化->最小费用最大流
23. • 最大流
    • 最小费用最大流
24. • 状压DP
    • 矩阵快速幂（据说可以做到\(n\le 10^9\)，然而并不会做）其实原题朴素状压在极限复杂度下也是会爆的
    • 编号起始坑死我了
25. ※
    • 状压DP

---

我怎么感觉这个星期啥题都在写

2.25~3.3 DP周II

1. • 期望DP
2. ※
   • 期望DP
   • 的Easy版
   • 答案较难维护，变化量容易维护的典例
3. • 期望DP
4. • 期望DP其实是个调和级数求和
   • 其实跟思路挺像的
5. • 概率
6. • 树形DP
   • 基于容斥思想的二次扫描换根法，在不定根树形DP中十分常用
7. ※
   • 期望fake
   • 线段树real
8. • 树形DP
9. • 树形背包
10. • 树形背包
11. • 树形基环树森林DP
12. ※
    • 树形背包
    • 考虑边的贡献
13. ※
    • 树形DP
14. ※
    • 网络流
    • 也是一种动态加边的思想
15. • 网络流
16. • 网络流
17. • 递推与DP
    • 斜率优化
18. • 递推与DP
19. • 递推与DP

3.4~3.10 数据结构周

% Data Structure Master

---

1. ※
   • 最小路径覆盖->二分图最大匹配
   • 再一次的应用了拆点的思想
2. ※
   • 最小路径覆盖->二分图最大匹配
   • 动态加边
   • 拆点
3. • 二维前缀和
   • 主席树
   • 二分答案
4. • 最多不相交路径->网络最大流
   • 还是拆点
5. • 带修主席树（树状数组套主席树）
6. • 带修主席树
7. • 差分
   • 主席树
8. • 树链剖分
   • 动态开点线段树
9. • 主席树
10. • 二分图多重匹配->网络最大流
11. • LCT
12. • LCT
13. • LCT
14. ※
    • LCT
15. • Kruskal重构树
    • 主席树
16. • 平衡树
17. • splay
    • 打错一个字母调了大半天是什么体验
18. • 左偏树

3.11~3.17 数学周

1. • 莫比乌斯反演
2. • 莫比乌斯反演
3. • 莫比乌斯反演
   • 容斥
   • 跟上面那题很类似
   • 学不动了QAQ
4. • 博弈
   • 记忆化搜索
5. • 最小割
6. • 递推与DP

3.18~3.24 培训周I

1. • 二项式反演
2. • 哈希
   • 树状数组

3.19~3.31 培训周II

1. • 斯特林数
2. • 扩展中国剩余定理
3. • BSGS
4. • 扩展中国剩余定理

4.1~4.7 备战周I

1. • 指数型生成函数
2. • 生成函数
   • python
3. • NTT
4. • 指数型生成函数
5. • 多项式求逆
6. • cdq分治
   • 树状数组
7. • BSGS
8. • 左偏树
9. • 左偏树
   • 直接开花
10. • 虚树
11. ※
    • 后缀数组
12. ※
    • 后缀数组

4.8~4.12 备考周II

1. • 后缀自动机
2. • 后缀自动机
3. • 后缀自动机
4. • 后缀自动机
5. • 无源汇有上下界可行流
6. • 有源汇有上下界最大流
7. • 有源汇有上下界最小流
8. • 有源汇有上下界最小费用可行流