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必须大于Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m+K} , 接着就是常见技巧，不考虑限制条件的方案数为Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\tbinom {n+m}{n}}}

考虑限制条件可以考虑零点相对于Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y=x+K+1} 的对称点，从那走到点Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (n,m)} 的方案就是所有的不合法方案，将Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y=x+K+1} 上方的路径翻转即可证明

F是个简单网络流，考虑每个piece选择一个Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i} 和一个Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_i} , 建立源点到每个行的边，行到每个Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle piece_l} , 每个Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle piece_l} 到每个Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle piece_r} , 每个Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle piece_r} 到列，每个列到汇点，流量均为1的图，跑最大流即可，跑个Ford-Fulkerson Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle O(EF)} 即可解决，E为边数，F为h, w, n的最小值，(是不是dinic的Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(E\sqrt{V})} 更合适啊

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

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

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