BreakFast: Protected "BreakFast:Lzw Silly Problem Practice" ([Edit=Protect from non-authors] (indefinite) [Move=Protect from non-authors] (indefinite))

2021-07-21T01:44:19Z

Protected "BreakFast:Lzw Silly Problem Practice" ([Edit=Protect from non-authors] (indefinite) [Move=Protect from non-authors] (indefinite))

← Older revision	Revision as of 01:44, 21 July 2021
(No difference)

BreakFast: add abc 205

2021-06-14T15:54:35Z

add abc 205

New page

<strong>lzwの傻逼题练习</strong>

记录sb题技巧练习

__TOC__

=== AtCoder Beginner Contest 205 ===

开了一场abc205

A是个小模拟

B是个一眼模拟

C是个一眼讨论

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

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

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

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

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

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

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

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

BreakFast:Lzw Silly Problem Practice - Revision history

BreakFast: Protected "BreakFast:Lzw Silly Problem Practice" ([Edit=Protect from non-authors] (indefinite) [Move=Protect from non-authors] (indefinite))

BreakFast: add abc 205