1/23 PKU - Algorithmer’s note

2224 Missing Piece 2001

15パズルみたいなやつを解くだけの問題。手数の上限が与えられていて、その手数以内で解けるか判定する。

反復深化やるだけ

2353 Ministry

あなたはある文書に大臣の署名を書いて欲しい。大臣のお役所の承認を得るなら、署名してもらえる。署名は、「お役所の一番下の階の局」、「下の階の局が署名した局」、「隣の局が署名した局」でもらえる。一番上の階で署名してもらえれば勝ち。署名を要求するときには金をとられる。一番安く承認を得る方法を出力せよ。

Dijkstraやるだけ

2984 A New Joseph Problem

J(N)を、「N人を時計回りに並べて、1番目の人の場所から、『2人目』を順に取り除いていったとき、最後に残る人の番号」と定義する。Jを何回も適用すると不動点になる。Kに対して、Jをたくさん適用して得られる不動点の値を求めよ。

J(1)=1、J(2x)=2J(x)-1、J(2x+1)=2J(x)+1と表せる。J(x)=yのとき、xの2進数における"1"の個数とyの2進数のおける"1"の個数は同じであることがわかり、さらにJ(x)=xならxは2^n-1の形で書けるので、ビット数数えて(1<<ビット数)-1を出力するだけ。
Kは10^10000とか書いてある。BigIntegerゲー。BigIntegerはbitCountとかshiftLeftとか便利な関数が多い

1637 Sightseeing tour

ある都市にはいくつかの交差点があり、それらを結ぶ道がある。道は一方通行だったり双方向だったりする。ある交差点からすべての道を通って、最初の交差点に戻る経路が存在するか？

最大流に還元して解く。