1/25 PKU

3691 DNA repair

悪いDNA列のリストが与えられる。もう一つ与えられるDNA列を編集して、悪いDNAを含まないようにしたい。最低何箇所編集する必要があるか。

Aho-Corasickで有限オートマトンを構築した後DP

3697 USTC campus network

コンピュータがたくさんあって、どの２台も直接双方向のリンクでつながれている。今、いくつかのコンピュータの間のリンクが切れた。サーバーとリンクをたどって到達できるコンピュータの数を求めよ。

まだ到達できてないノードのリストと、それぞれのノードについて直接移動できないノードのリストを線形リストで持っておいた上でBFS。