BreakFast:Lzw Silly Problem Practice

lzwの傻逼题练习

记录sb题技巧练习

AtCoder Beginner Contest 205

开了一场abc205

A是个小模拟

B是个一眼模拟

C是个一眼讨论

D是个小模拟，没开longlong Wa了一发，得注意下数据范围，这种模拟其实一眼不好证明，当能感觉大体上对，这种讨论要多做啊

E是个组合数学常见技巧，考虑放一个white为在x轴走一步，放一个black就是在y轴走一步，放到二维来看，题目给的$w_{i}<b_{i}+K$就变成了二维平面的线性规划

然后看图得n必须大于$m+K$, 接着就是常见技巧，不考虑限制条件的方案数为${\tbinom {n+m}{n}}$

考虑限制条件可以考虑零点相对于$y=x+K+1$的对称点，从那走到点$(n,m)$的方案就是所有的不合法方案，将$y=x+K+1$上方的路径翻转即可证明

F是个简单网络流，考虑每个piece选择一个$r_{i}$ 和一个$c_{i}$, 建立源点到每个行的边，行到每个$piece_{l}$, 每个$piece_{l}$到每个$piece_{r}$, 每个$piece_{r}$到列，每个列到汇点，流量均为1的图，跑最大流即可，跑个Ford-Fulkerson $O(EF)$即可解决，E为边数，F为h, w, n的最小值，(是不是dinic的$O(E{\sqrt {V}})$ 更合适啊

感觉也是个sb套路啊，赛时在想什么爆搜（

傻逼题得赛时想得到啊，赛时自己就成shite了

整理整理预留推进的板子，现在的板子太难抄了，