きままにものづくり

日々の気付いたことなんかを書いてます。

2013-10-08から1日間の記事一覧

POJ 3264 : Balanced Lineup

問題 要素数N()の数列が与えれる。[a,b]区間の最大値と最小値の差分を求めなさい。 解法 セグメント木を使う。最大値を保持する配列と最小値を保持する配列の2つを持つ。 計算量 更新: クエリ: コード

POJ 2886 : Who Gets the Most Candies?

問題 N()人の名前と値が与えられる。初めにK番目の人(1から始まる)からスタートし、選ばれた人は抜ける。抜ける際に、p番目の人はpの約数だけ飴がもらえる。次の人は、その人の値分だけ時計回りした番号の人になる。マイナスの場合は逆回転となる。飴の最大…

POJ 2155 : Matrix

問題 N*N()の配列が与えられる。各要素は、1か0しか値をとることができない。ふたつのクエリに対する処理を実行せよ。 (x,y)の要素が1なのか0なのか求めよ (x1,y1,x2,y2)の範囲をフリップせよ 解法 二次元のBITを使い、範囲操作をするために4つの二次元BITを…