7月22日のPKU

PKU

今日：6問
今日までの合計：41問

PKU 1300 Door Man

問題

PKU 1300

部屋がn個あり、部屋と部屋をつなぐドアがいくつかある。部屋mから出発して、開いているドアを全て閉めて部屋0へ到達したい。ただし、既にしまっているドアは開けず、開いているドアは一度だけしか閉めないような経路をとりたい。そのような経路が存在するか求める問題。

解法

オイラーグラフ、準オイラーグラフ。

PKU 1301 The Umbrella Problem: 2054

問題

PKU 1301

問題を説明する気力がない。

解法

DFSするだけ。

PKU 1204 Word Puzzles

問題

PKU 1204

L x Cの長方形に英大文字が敷き詰められている。この中からW個の単語を探したい。単語は8方向のうちどれかの向きに存在する。このとき、W個の単語の位置と向きを求める問題。同じ単語が複数箇所に現れる場合はどこでもよい。

解法

trie

PKU 1757 Binary Search

問題

PKU 1757

N要素の配列に対してi番目の要素を二分探索で探すとき、比較の回数がちょうどL回になるようなNをすべて求める問題。

解法

Nの範囲が小さいのでやるだけ。

PKU 2211 Photograph

問題

PKU 2211

1..nの中からk個選んだものの順列を考える。そういった順列がひとつ与えられるので、与えられた順列が辞書順で何番目のものか求める問題。

解法

計算する。

PKU 1599 Station Balance

問題

PKU 1599

S個のもの(それぞれ重さが異なる)をC個のグループに分けて、不安定さがもっとも少なくなるようにする。ただし、1つのグループには2個までしか属せない。また、不安定さとはグループの重さと、全てのグループの重さの平均値との差の総和とする。不安定さがもっとも少なくなるときの分け方を求める問題。 1 <= C <= 5, 1 <= S <= 2C

解法

はいはい全探索全探索