N要素の配列には、1からNのインデックスが付けられます。すべての要素は不明で整数です。 A、B、Cの形式のクエリがある場合、Aは開始インデックス、Bは終了インデックス、CはAとBの間のすべての要素の合計です。配列のすべての要素を調べる。例:サブ配列の合計が指定された場合の配列要素の検索
N=4 1, 3, 0 2, 4, 4
これに対する1つの有効な解決策がある:
2, -3, 1, 6
制約:
1<=A<=B<=N, 2<=N<=65000, C<=1000000000
与えられた基準を満たす任意のソリューションが受け入れられ、十分なクエリを想定しているが、すべてを見つけるために与えられています要素。
1
A
答えて
2
これを解決する1つの方法は、問題を一連の連立方程式として扱うことです。それぞれの総和は、最大n個の変数の線形方程式を与えます。したがって、整数値を持つ方程式の解を見つけることができれば、すべて設定する必要があります。 K個の異なる制約を有するn個の変数の一連のガウス消去を使用
が期待にO(K )時間(すなわち、N = O(k)を仮定して)かかり(システムを想定良条件です)。そこから、整数解を見つけることは容易でなければならない。任意の1つの解ベクトルの共通分母を見つけ、それによって乗算するだけです。
希望すると便利です。
関連する問題
- 1. 整数配列内のサブ配列の合計を求める
- 2. 配列要素が挿入されている場合にのみ配列要素をプッシュする方法
- 3. チェックされた配列の要素が連続している場合--- javascriptの
- 4. 配列要素の積算合計の計算方法は?
- 5. 合計配列
- 6. jquery tmplネストされた配列のサブ要素にアクセスする
- 7. 配列索引付けの場合
- 8. 配列がある場合は配列
- 9. 配列の値の合計
- 10. JavaScriptの配列の合計
- 11. Pythonのlong(> 20millionの要素)配列の合計numpy
- 12. 異なる配列要素を受け取った場合、同じJSON配列が配列にあります
- 13. MongoDB $配列アイテムの合計
- 14. JavaScript配列の合計値?
- 15. 配列の合計数値
- 16. AngularJS配列の合計
- 17. 列のMySql合計要素
- 18. Javaで - 2つが同じ場合に配列の要素を合計する必要があります
- 19. 配列のループの場合
- 20. PHPネストされた配列の検索
- 21. MongoDBのネストされた配列検索
- 22. 配列の合計要素に同じキー?
- 23. JavaのLongStreamで配列要素を合計する
- 24. 配列がある場合
- 25. 検索結合配列by value
- 26. チェック配列が指定されたオブジェクト
- 27. 配列に含まれる配列のスカラー合計
- 28. 配列要素の配列要素をJavaで配列する
- 29. 配列結合配列に要素を追加する
- 30. レンダリング:配列を返す部分ApplicationControllerにで定義されたものの場合、文字列場合ApplicationHelper
この宿題はありますか?これまでに何を試しましたか? – MAK
これは宿題ではありません。私はこれらを線形方程式としてモデル化した後にCramerのルールを適用したいが、Nはそれを行うには高すぎる。 – schrodinger