1

私はこの演習に問題があります:

AからBまでの範囲 と、 ;で部分文字列を1 <= A,B <= 10^18
表す整数が与えられます。指定された部分文字列のいずれかを 含む A ,B ( AとBを含む) の 間の範囲内の可能な数値の総数を返します。Ni1 <= i <= 1000

入力

A, B, i 
N1
N2
...
Ni

例えば ​​：

簡単な入力

10 22 2 
1 
10

簡単な出力

11

説明: 10 から 22 の範囲には次の数字が含まれ10* 11* 12* 13* 14* 15* 16* 17* 18* 19* 20 21* 22ます。部分文字列 10 または 1 のいずれかを含む有効な数字は (*) でマークされています

範囲内の可能な数の総数をどのように計算できますか?

4

1 に答える 1

1

まず、Aho-Corasick 自動化と動的プログラミングについて知る必要があります。

[A,B] の範囲の問題を[1,B] - [1,A-1] の2 つの問題に分割します。

次の動的計画法の構築。

DP[position][is_equal_to_A][which_node_in_automation];
  • 位置は数値の長さを意味します
  • is_equal_to_Aは、A のプレフィックスと等しいかどうかを意味します

次に、現在の番号の最後の番号を列挙します。

于 2015-12-18T14:09:10.037 に答える