1/28 PKU - Algorithmer’s note

王様の誕生日にお祝いを始めて、コインがK回目に表を返すまで何日でも続ける。i日目には2i-1の金額を使う。日数と費用の期待値を求めよ。

式を立てて計算する

閉路のない有向グラフにおいて、すべての辺を被覆するために必要な経路の最小数を求めよ。経路は互いに接触してもかまわない。

a->bの経路が存在するならa->bの辺を張るということをした上で、Air Raidと同じ事をする。

D次元の直方体の形をしたギフトと、たくさんの箱がある。ギフトをできるだけ多くの箱の中に入れ子状に入れたい。ある箱/ギフトは、他の箱の中に入るためには、中のものの座標をうまく並び替えたとき、すべての座標について外の箱の座標よりも小さいという条件が必要である。何箱に入れ子にできるか。

箱が入るという条件は座標をソートすれば何も問題がない。ソートした上で、ある座標に注目すると、入れ子になっていくうちに外の箱の大きさは単調増加であるため、その座標の大きさでソートしてかまわない。あとはDP

N個の街がある。最初全部孤立している。街同士をつなぐクエリ、街を孤立させるクエリ、街同士がつながっているか判定するクエリが飛んでくる。街は孤立しても、他の街の接続関係は変わらない。これらを処理せよ。

union find。街が孤立したときには、その街に対応する頂点を別に用意し、そこを使って計算しなおす。

長い整数Nと、小さい整数Kが与えられる。Nの桁をいくつか変更して、Kの倍数を作れ。複数あるときは、変更する桁の数を最小化せよ。それでも複数あるときは、答えを最小化せよ。

dp[位置][剰余][変更桁の数]でDP。変更桁はKの桁数より大きくはならないことは自明。しかし通らなかったのでループを展開した http://ideone.com/lxJHZ

木の最小頂点被覆を求めよ。

木DP。