Educational Codeforces Round 43

スポンサーリンク

A. Minimum Binary Number

$0$ の個数が不変量.

B. Lara Croft and the New Game

周期的に $2$ 行戻ります.

C. Nested Segments

nest がないと仮定すると,L, R ともに昇順になるようにソートされます.L でソートして R が昇順になっていないところを見つかればその 2 つが解.そうでなければ解なしです.

D. Degree Set

最小次数が正の間は最大次数の点をすべての点に接続します.

E. Well played!

操作1は一ヶ所だけにやるとしてよいです.

F. Minimal k-covering

$k=1$ なら最小頂点被覆で,これは最大マッチングと等しいです.一般の $k$ の場合には,すべての頂点を $k$ 重にコピーした上で最小頂点被覆と言い換えられます.各頂点からの流量を 1 ずつ増やしてフローを差分更新するというのを反復します.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました