hogloidのブログ

へなちょこ

PKU

PKU 3517 And Then There Was One

PKU

id:kyuridenamidaのところ(http://d.hatena.ne.jp/kyuridenamida/20110724/1311503122)にはシミュレーションでは間に合わないとか書いてありましたが間に合いました(漸化式とか知らない無知) ただ、普通にシミュレーションするんじゃなくて多少工夫しま…

3250 BadHairDay

PKU

(id:Respect2Dさんの方が圧倒的に頭がいい解法です) なぜかsegtree解法しか思いつかなかった。最初はO(Nlog^2n)でやろうと思ったけど TLEで死亡しそうだったので多少工夫 もし左のノードみてあったらそれをすぐ返してしまえーというだけの話だけど struct …

PKU3092 Non-divisible 2-3 Power Sums

PKU

数N( 2^a*3^bの和で表せ。ただし2^a*3^bのどれかがどれかで割りきれてはいけない 探索します。メモ化しなくてもOKです まず、nが2で割りきれるとき、すべての2^a*3^bのaはa>=1なので、 n/2の場合に帰結できます。 nが2で割りきれないとき、2^a*3^bのうち一つ…

PKU 2951 Cake cutting

PKU

w*hのケーキをm個の長方形に分割。 w,h,m まあDPやるだけです 3分探索を入れてかっこつけましたが普通に3分探索しなくても通ると思います (実は毎回計算しててTLEだったので無理やり3探いれましたごめんなさい) int main(){ REP(i,21) REP(j,21) REP(k,21)…

2831 Can we build this one?

PKU

http://poj.org/problem?id=2831 N村を結ぶM辺があり、最小全域木を作る そのとき、ある辺のコストがCならその辺は最小全域木に選ばれうるか、という クエリを処理する問題 id:semiexpさんの http://d.hatena.ne.jp/semiexp/20110107/1294381308 こちらの方…

PKU 2796 Feel Good

PKU

http://poj.org/problem?id=2796 N要素があって、その中の連続した要素の、 もっとも少ない数*その要素の合計 がもっとも大きいものを求める。ヒストグラムのアレです。 幅がありますが累積和でおk。 オーバーフローやすべての要素が0のときに注意。 typede…

PKU 2611 Gas Station Numbers

PKU

http://poj.org/problem?id=2611 今ある数字の札を使った次に大きい価格を求めます。 25、96 は変換可能まぁやるだけ 下の桁からみていって、今の桁の数より大きい数に変更できるなら、 その数に変更 後は残った数を小さくなるように置いていく int main(){ …

PKU 3262 Protecting the Flowers

PKU

TopCoderでこれ+ナップザックな問題と昔当たったので簡単 ある牛A、Bがいて、それ以外の残りの牛の破壊量/minuteをDとおくと、 破壊量はそれぞれ Aー>Bの順に処理すると Aの時間*(D+Bの破壊量)+Bの時間*D Bー>Aの順に処理すると Bの時間*(D+Aの破壊量…

PKU 1850 Code

PKU

昔やってみて集中力が持たなくてやめたのをもう一回やってみたら意外とすっきりかけました 使った文字+残りの文字数 で作ることができるすべての文字列の数を求める関数を作ります。 便宜上文字数0のとき1を返します。 int befsize(int n,int usedword){ if…

PKU 2443 Set Operation

PKU

なんか苦戦したので書きます C(i)( 数はすべて10000以下最初はソートしようかな、とか思ったけどソートすらTLEになりそう 数が1万以下なので普通に配列にもつ O(CN+QN)でいいかな?ー>TLE 数が1万以下だからあらかじめ求めておいた方が良さそう bitset初め…

PKU 1548 Robots

PKU

http://poj.org/problem?id=1548 解いてるとき日本語で解説されたソースコードがなくて困ったので書きますまず、最初は0,0の場所にいます。 もし0行目にゴミがあるなら、一番右にあるゴミまで取ります(そこまで行かなければまたそのゴミを取りにいかなけれ…

PKU 1297-supermarket

PKU

苦労したけど割と綺麗なコードも書けたし載せます最初は普通にDPやってMLEー> メモリを2回分だけとるようにしたけどTLEー> cinをscanfにしたけどWAー> printfのフォーマットを直してAC scanfはdouble型を受けとるときlfだけどprintfはfなんですね これで5…