20150726 填坑日记

三中内填坑：

1. 组合数递推什么的 C(m,n)=C(m,n-1)+C(m-1,n-1)。填了个大坑，以前没认真听课QAQ

2. 裸题过河卒

3. 缺角正方形摆放车统计，分上下部分，枚举上部分放几个即可，O(n)

4. 3d立体图统计表面积：先把上下搞定，然后左右用高度差来统计即可。O(n^2)

===夏令营07.16神题===

1. 求必经之路，枚举点，删点，BFS看能否到达终点，若不能则为必经点。O(nm)

2. 求生成树，使得生成树中最大边和最小边差最小。模仿kruskal，最小边固定，移动最大边来使得差最小即可。O(nlogn)，像尺取。

3. 虫洞，大概意思就是说有一些点和一些边，要你求S-T的最短路，每个点在白点或黑点变化，白/黑有不同的边权，每秒变白/黑，可以停留最多1s，求最短路。大概就是拆个点，每个点拆成白和黑，然后spfa跑一跑就可以了，O(kn)~O(n^2)，数据n<=8000，所以被菊花图卡n^2也无所谓。或者bf或dijk或dij+heap也可以。

===bzoj神题===

1001: 平面图最大流，转化最短路，可见周冬论文。