10/28 PKU

ひさしぶりにPKU

3600 Subimage Recognition

あるビット行列から、いくつかの行、列を取り去って、目標のビット行列にできるか判定せよ。

取り去る列を決め打ちして、行についてマッチングできるか判定。O(RC*2^C)ぐらい。ただ、900MSかかったためどう考えても作為解じゃない

3107 Godfather

n人のマフィアがいて、それぞれの関係は木構造上になっている。誰がリーダーかわからないから、「取り除いたときに、残る最大の繋がっている部分が最も小さくなるようなマフィア」をGodfatherと呼ぶことにする。Godfatherを全員出力せよ。

根を適当に決めて木DPやるだけ。隣接表現にvectorを使ったらTLEしたから自前でlist組んだら通った。