1/8 PKU

1313 Booklet Printing

冊子を印刷するとき、各紙に印刷すべきページ番号を出力せよ。

やるだけ

1583 Choose Your Words Carefully

与えられた文章において一番多く出てくる語を頼む

Trie書くだけ

3510 A Tale from the Dark Side of the Moon

規則に従って入力文字列を置き換えろ

やるだけ

2444 Partition a Matrix

数字の入った表がある。これを2本の線分で3つの部分にぶった切る。2本の線分は表の縦の辺か横の辺に平行でなくてはならないが、互いに平行であってはいけない。3つの部分の数字の和を求め、それらをX,Y,Zとするとき、|X-Y|+|Y-Z|+|Z-X|を最小化せよ。

左上から和をとると、ある長方形領域の和がO(1)で求まる。あとは全部の線分の引き方を試すだけ。2本の線分が平行である場合を考慮しないとなぜかWAになるので注意。

2288 Islands and Bridges

いくつか島があって、島には重みがついている。島同士は橋で結ばれている。今、すべての島を通るハミルトン路について、その重みを次のように計算する。1.各島の重みの合計＋2.各辺において、結ぶ2つの島の重みの積の合計＋3.3つの経路上連続する島について、互いに結ばれているなら、その3つの島の重みの積の合計。これを最大化するとき、その重みと、それを達成する経路の数を求めよ（ひっくり返して同じになるものは同一視する）。

dp[i][j][k]…2個前にi、1個前にjを訪れ、訪れた場所はkにビットとしてある　ときの今までの最高の点数　としてビットDP。最後に経路の数を2で割る。N=1のとき経路は1通りしかないので注意。

1859 The Perfect Symmetry

N個の点が与えられて、それらの点対称の中心を求めよ。

点対称の中心としてあり得る点は、すべての点の座標を平均するとわかる。その点を中心として点対称か調べる。