PKU詰め合わせ 11/20

今日は問題解きまくった。気がついたらRecent Ranking1位になってた。
クソ問コンテストが開かれていたので早速全完してきた。

時間ないかもしれませんが解説しておきます。

1836:Alignment

最長増加部分列を左右でやる。その後、どこで分けるかで足し合わせる。
結局O(n^2)になる。たぶんもっと早くなる。

2479:Maximum sum

基本的には1836に近い。部分列の和の最大化のDPを左右でやる。最後足し合わせる。
後は足し合わせる。この処理は上の問題より楽なはず。

1056:IMMEDIATE DECODABILITY

Java使うと楽。StringのstartsWith使った。
C++でもたぶんやるだけ。

1454:Factorial Frequencies

JavaのBigInteger使ってからprintf使うだけ。
printf便利すぎる

以下4問がコンテストの問題

3982:序列

4項間漸化式の第99項を求める。
多倍長。BigIntegerやるだけ。

3981:字符串替換

全部のyouをweに変える。
区切って調べてweにしておしまい。

3980:取模运算

a%bを求める。
特に何もひっかけはない。普通にa%bを出力する。

3979:分数加減法

分数の足し算引き算をする。
通分して足したり引いたりしてから約分。
分母が1になるとき注意。

1804:Brainman

ソートしたい(隣同士を入れ替えることしかできない)けど、なるべく回数を少なくしたい。何回で出来るか。
普通にシミュレーションして、a[i]>a[i+1]のとき入れ替えてカウンタを1増やせばおk。

2739:Sum of Consecutive Prime Numbers

最初にa[i]=(最初(2)からi番目までの素数すべての和)を持っておくとコーディングが楽。後は引き算。O(20000までの素数の数^2)で通った

3191:The Moronic Cowmpouter

マイナス2進数。
PC甲子園の問題と同じ方針でいける。どうやらlong long使わないとREするらしい

2272:Bullseye

ダーツの点数計算。double怖くて信用できないけど普通にx*x+y*yするだけ。

37Submit 15ACでRecent1位はなんか過疎でしょうかね