12/23 PKU

Algorithm PKU

1185 炮兵阵地

中国語が読めないが、フィーリングと図から察するに、「フィールド上のPとなっている点に兵士をできるだけ多く置け。但し、兵士の上下左右２マスには他の兵士がいてはいけない」ということになるだろう。

DP。M箇所それぞれについて、あと何行そのマスが使えないかを覚えておいてビットDPまがいのことをする。DP部分をできるだけ簡略化する高速化をして通る。

4011 Automated Telephone Exchange

0 <= i, j <= 99のとき、N=i+jとなる(i, j)の組の数を求めよ。

やるだけ

4012 Black Square

M*Nのグリッド上に、S*Sの正方形の部分を黒く塗った。そのうち1行だけが位置を特定されて与えられた時、正方形の位置を特定できるか求めよ。

やるだけ。与えられた行がすべて白い場合もあることに注意。

4014 Dice

N個のサイコロの各面に数字を書く。数字は1〜M(Mはサイコロの面の数の総和)を1回ずつ使う。サイコロをすべて同時に振った時、出た目の和の期待値が最大になるような数字の書き方と、その時の期待値を求めよ。

ソートしてやるだけ

1281 MANAGER

数字をキューにpushしたりpopしたりする。popはマネージャーによって大きい数字からpopしたり小さい数字からpopしたりする。あるpopの回数のときのpopされた数を答えよ。

やるだけ。setを使うと簡単。

2142 The Balance

天秤と、質量がAとBの分銅を使って、質量Dを量り取る方法を求めよ。方法の中で、「Aの個数+Bの個数」が最小になるものを求め、それが同じ場合は「分銅の重さの和」が最小になるものを求めよ。

やるだけで通る