lizbaka的周记

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

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

——2019.01.20

1.14~1.20 图论周I

1. *「POJ1741」Tree->博客
   • 点分治
2. *「Luogu3806」点分治1->博客
   • 点分治
3. *「Luogu2634」[国家集训队]聪聪可可->博客※
   • 点分治
4. *「Luogu2495」[SDOI2011]消耗战->博客
   • 虚树
5. 「BZOJ1821」[JSOI2010] Group 部落划分->博客
   • 二分答案
   • 并查集
6. *「BZOJ1003」[ZJOI2006]物流运输->博客※
   • 最短路
   • DP
7. *「Luogu4430」小猴打架->博客※
   • 生成树
   • prufer编码，cayley公式
   • matrix-tree定理
8. 「BZOJ1232」 [Usaco2008Nov]安慰奶牛cheer
   • 最小生成树

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

不行啊（恼）

1.21~1.27 图论周II

这周还有冬令营
emmmmmm

还是立个flag吧，WC之前至少要搞定7个题
有质量那种

1. 「BZOJ1001」[BeiJing2006]狼抓兔子
   • 最小割
   • 平面图转对偶图->最短路
2. *「BZOJ1497」[NOI2006]最大获利（板）->博客
   • 最大权闭合子图->网络最大流
3. *「BZOJ1565」[NOI2009]植物大战僵尸->博客
   • Tarjan
   • 最大权闭合子图->网络最大流
4. *「Luogu3231」 [HNOI2013]消毒->博客※
   • 二分图匹配
   • 搜索
5. *「Luogu2762」太空飞行计划问题->博客※
   • 最大权闭合子图（输出方案）->网络最大流
6. *「BZOJ1061」 [Noi2008]志愿者招募经典※
   • 最小费用最大流
   • 关于这道题，这篇博客讲得很好，从想到使用网络流到模型构建，完整详细地呈现了思考过程，非常值得借鉴
7. *「Luogu3358」 最长k可重区间集问题
   • 最大权不相交路径->最大费用最大流
   • 有点像上面那道题
   • flag回收成功@2019.01.22
8. *「Luogu3355」 骑士共存问题
   • 最大点独立集->二分图最大匹配
   • 按奇偶性对此类棋盘黑白染色是很常用的操作
9. *「Luogu3357」 最长k可重线段集问题※
   • 最大权不相交路径->最大费用最大流
   • 跟7差不多，然而有斜率不存在的线段
   • 应用了拆点的技巧
10. *「Luogu3674」 小清新人渣的本愿
    - 莫队
    - bitset

1.28~2.17 IDLE

咕咕咕
其实是去搞文化课了

2.18~2.24 DP周I

1. *「Luogu4127」[AHOI2009]同类分布※
   • 数位DP
   • 对于一些范围较小的变化量可以采取外部枚举的方式其实就是不要怕电脑累
2. *「Luogu3413」SAC#1 - 萌数
   • 数位DP
   • 前导零处理真的恶心
3. *「Luogu1040」加分二叉树
   • 区间DP
   • 正难则反，以小区间合并到大区间为主要过程的区间DP一般采用递推形式，而以大区间划分为小区间为主要过程则可以采用记搜递归形式
4. *「Luogu3809」【模板】后缀排序
   • 后缀数组
5. *「Luogu4170」[CQOI2007]涂色※
   • 区间DP
6. *「Luogu3847」[TJOI2007]调整队形※
   • 区间DP
7. *「Luogu4317」花神的数论题->博客
   • 数位DP
8. *「Luogu2053」[SCOI2007]修车
   • 最小费用最大流
   • 应用了拆点的思想
9. *「Luogu2050」[NOI2012]美食节※
   • 最小费用最大流
   • 动态加边
   • 基本同8
10. 「Luogu4014」分配问题
    • 最小/大费用最大流
11. 「Luogu5020」货币系统
    • 完全背包
    • 嘶……我考场上是在干嘛啊
12. *「Luogu2938」股票市场Stock Market※
    • 完全背包
13. 「Luogu2851」[USACO06DEC]最少的硬币The Fewest Coins
    • 多重背包
    • 完全背包
14. *「Vijos1037」搭建双塔
    • 01背包
15. *「Luogu1489」猫狗大战
    • 01背包
16. 「Vijos1334」NASA的食物计划
    • 二维背包
17. *「Luogu2339」提交作业usaco
    • 区间DP
18. 「Luogu4158」[SCOI2009]粉刷匠->博客
    • 递推与DP
    • 分组背包
19. 「Luogu2889」[USACO07NOV]挤奶的时间Milking Time
    • 递推与DP
20. *「CodeVS2800」送外卖
    • 状压DP
    • 点名批评数据出锅
21. *「Luogu2622」关灯问题II
    • 状压
    • 最短路
22. *「Luogu1251」餐巾计划问题※
    • 线性规划网络优化->最小费用最大流
23. *「Luogu2604」[ZJOI2010]网络扩容
    • 最大流
    • 最小费用最大流
24. 「Luogu3977」[TJOI2015]棋盘
    • 状压DP
    • 矩阵快速幂（据说可以做到\(n\le 10^9\)，然而并不会做）其实原题朴素状压在极限复杂度下也是会爆的
    • 编号起始坑死我了
25. *「LuoguP3052」[USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper※
    • 状压DP

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

2.25~3.3 DP周II

1. *「Luogu4316」绿豆蛙的归宿
   • 期望DP
2. 「Luogu1365」WJMZBMR打osu! / Easy※
   • 期望DP
   • 「Luogu1654」OSU!的Easy版
   • 答案较难维护，变化量容易维护的典例
3. *「Luogu2473」[SCOI2008]奖励关
   • 期望DP
4. 「Luogu1291」[SHOI2002]百事世界杯之旅
   • 期望DP其实是个调和级数求和
   • 其实跟「POJ2096」Collecting Bugs思路挺像的
5. 「JoyOI1864」[Poetize I]守卫者的挑战
   • 概率
6. 「Luogu2986」[USACO10MAR]伟大的奶牛聚集Great Cow Gathering
   • 树形DP
   • 基于容斥思想的二次扫描换根法，在不定根树形DP中十分常用
7. 「Luogu2221」[HAOI2012]高速公路->博客※
   • 期望fake
   • 线段树real
8. 「Luogu3174」[HAOI2009]毛毛虫
   • 树形DP
9. 「Luogu1270」“访问”美术馆
   • 树形背包
10. 「Luogu3360」偷天换日
    • 树形背包
11. *「Luogu2607」[ZJOI2008]骑士
    • 树形基环树森林DP
12. ※*「Luogu3177」[HAOI2015]树上染色
    • 树形背包
    • 考虑边的贡献
13. *「Luogu4438」[HNOI/AHOI2018]道路※
    • 树形DP
14. *「Luogu2754」[CTSC1999]家园※
    • 网络流
    • 也是一种动态加边的思想
15. 「Luogu2891」 [USACO07OPEN]吃饭Dining
    • 网络流
16. 「Luogu1231」 教辅的组成
    • 网络流
17. 「Luogu3648」[APIO2014]序列分割
    • 递推与DP
    • 斜率优化
18. *「Luogu2331」[SCOI2005]最大子矩阵
    • 递推与DP
19. *「Luogu2501」[HAOI2006]数字序列
    • 递推与DP

3.4~3.10 数据结构周

% Data Structure Master GoldenPotato

1. *「Luogu2764」最小路径覆盖问题※
   • 最小路径覆盖->二分图最大匹配
   • 再一次的应用了拆点的思想
2. 「Luogu2765」魔术球问题※
   • 最小路径覆盖->二分图最大匹配
   • 动态加边
   • 拆点
3. *「Luogu2468」[SDOI2010]粟粟的书架
   • 二维前缀和
   • 主席树
   • 二分答案
4. *「Luogu2766」最长不下降子序列问题
   • 最多不相交路径->网络最大流
   • 还是拆点
5. *「Luogu2617」Dynamic Rankings
   • 带修主席树（树状数组套主席树）
6. *「Luogu3157」[CQOI2011]动态逆序对
   • 带修主席树
7. 「Luogu3168」[CQOI2015]任务查询系统
   • 差分
   • 主席树
8. 「Luogu3313」[SDOI2014]旅行
   • 树链剖分
   • 动态开点线段树
9. 「Luogu3567」[POI2014]KUR-Couriers
   • 主席树

lizbaka的周记

原文：https://www.cnblogs.com/lizbaka/p/10295272.html