2

この問題を解決するために使用できる高速なアルゴリズムを探しています。A と B の整数 ([0,10^18] の範囲) を指定し、N (N<=1000) の数値部分文字列のリストを指定します。目標は、N 個の部分文字列のいずれかを含む範囲 [A,B] 内のすべての数値をカウントすることです。常に A<=B であり、数値部分文字列も [0,10^18] の範囲の整数です。

例 1: A=10、B=22 の場合、N=2 部分文字列={1,10} を指定した場合。カウントは = 11 になります。数を数えます: 10->19 と 21.

例 2: A=175、B=201、および N=3 substrings={55,0,200} を指定した場合。カウントは = 4 になります。数を数えます: 180、190、200、201。

簡単な方法は、範囲 [A,B] 内の各整数を次々に分析することですが、範囲が非常に大きくなる可能性があるため (10^18 整数まで)、解決策ではありません。

問題の複雑さを軽減するために私が最初にしたことの 1 つは、「別の部分文字列が含まれていない」ように、N 個の部分文字列の元のリストからいくつかの役に立たない部分文字列を削除することです。例: {1,10} は {1} になり、{55,0,200} は {55,0} になります。これは最終的なカウントを変更しません。

次に、範囲 [A,B] 内の 1 つの部分文字列のカウントを取得できると仮定しても、このカウントをリストの他の部分文字列のカウントと合計することはできません。一度。

問題を解決して必要な数を取得するためのアイデアはありますか?

4

1 に答える 1

1

組み合わせの問題だと思います。

  1. A と B の間の数字の可能な桁数を計算します。たとえば、2 ～ 2000 の間では、桁数は 1、2、3、または 4 のいずれかになります。1 桁の場合、2 より大きい数字と 4 桁の数字を計算する必要があります。 、2000 未満の数、つまり 1 から始まる数を計算する必要があります。

  2. 桁数が k で、部分文字列 234 を含む数字を見つけると言わなければならない場合、その部分文字列を配置する場所を (k-2 通りに) 選択し、残りのすべての可能な数字 (i 10 ^ (k-3) 通りに考えてください)。もちろん、先行ゼロなどを割引する必要があります。

  3. すべての部分文字列に対してこれを繰り返します。

  4. ここで、複数の部分文字列を含むものを減算する必要があります。部分文字列のすべての組み合わせについて上記の手順を繰り返し、計算値から減算します。

于 2013-09-29T16:29:54.653 に答える