問題タブ [rmq]

BIT の仕組みを知っています。しかし、ビットを使用して完全な範囲内の最小/最大要素を見つけることができるか、より具体的には、すべての更新プロセスが完了した後に最小 (または最大) 値を見つけることができるかどうか疑問に思っていました。これはセグメント ツリーを使用して非常にうまく達成できることはわかっていますが、BIT を使用して同じことを行うことは可能ですか?

ありがとう。

PS: 完全な BIT をトラバースし、各インデックスの値を計算する明白な方法を知っています。より効率的/最適化された方法を探しています。

O(n)時間で配列をデカルトツリーに変換する方法を知っています

1. http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_constructionおよび
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#RMQから LCA へ

ただし、少なくともデカルト ツリーのすべてのノードに左右のポインターを関連付ける必要があるため、必要なメモリ量が多すぎます (定数)。

これらの定数を（うまくいけば1に）減らすために行われた作業に私をリンクできますか？

デモ テストを行ったところ、結果スコアは 62 でした。私のコードは、最高スコア 100 を達成するには効率的ではないと思います。たとえば、文字列はs="ACGTTAGTAC". s[p,q]部分文字列から効率的に最小文字を見つけます。同じsであるが異なる[p,q]. 実際、この問題は Range Minimum Query ( RMQ ) と呼ばれ、問題を解決できるアルゴリズムは複数あります。しかし、それらを理解してこの特定のインスタンスに適用するのは困難です。誰でもコードを修正する方法をアドバイスできますか?

著作権の問題により、質問全体はここにコピーされません。このリンクから完全な詳細を読むことができますhttps://codility.com/demo/results/demoHSB3XQ-R24/ .

データ構造コースでテストを受けましたが、質問の 1 つは次のとおりでした。

o(1) の複雑さで配列内の 2 つの数値の間の最小値を与える範囲最小クエリで維持される n サイズの配列があるとします。もちろん、配列はさまざまなオプションの動的計画法を使用して RMQ に応答するように準備された o(n) でした。問題は、配列内の 1 つのオブジェクト (数値) を変更した場合、o(1) で RMQ を見つけることができるようにするために行った準備をどのように変更すればよいか、そしてそれにはどのような複雑さが必要かということです。

答えは、o(n) で新しい RMQ を作成することではありません。それより小さくする必要があります。

この問題は宿題ではありません。理解するためにテストをやりたいだけです。

前もって感謝します。

RMQ の使用を開始しようとしていますが、アプリの作成中にこのエラーが発生します。gem をインストールしてからプロジェクトを作成する手順に従いました。必要なものはどこから入手すればよいrmq-templateですか？

どうすればいいですか？

Codechef March Long Contestの Question GCD ConditionでWA を取得しています。 私が何を間違えたか、またはコードが間違った答えを生成するテストケースを教えてください。

質問へのリンク

すべての素数に RMQ(Range maximum Query) を使用しました

まず、次のような構造に変換しました:-

入力例:- 10 6 20 15 8

(b[i]--> i の因数のインデックスを格納)

b[2]--> 1,2,3,5
b[3]--> 2,4
b [5]--> 1,3,4


RMQ を実装すると、次のようになります。

(cc[i][j][k] は、b[i][j] と b[i][j+(2^k)-1] の間の最大要素のインデックスを格納します)

cc[2][0]-- >1,2,3,5
cc[2][1]-->1,3,3
cc[2][2]-->3

cc[3][0]-->2,4
cc[3][1]-->4

cc[5][0]-->1,3,4
cc[5][1]-->3

マイコード

テーブルの各セルにトグル ボタンを作成しようとしています。押すと画像が変わり、もう一度押すと画​​像が変わります -- トグル。

クラスではUIButton、状態が表示されませんselected。

クリックごとに状態を変更できるように、UIButton を使用してトグル ボタンを作成する方法を探しています。

これが私がrubymotion今使っている方法ですrmq