4

数字の積が偶数である 2 つの数字 L と R (両方とも含まれる) の間の数字の数を見つける方法は? ブルートフォース以外にどうやってそれを行うことができますか？

dp[0][0]=4;
dp[0][1]=5;
for(int l=1;l<=9;l++)
{
    dp[l][0]=0;
    dp[l][1]=0;
    dp[l][0]+=(dp[l-1][0])*10;
    dp[l][0]+=dp[l-1][1]*5;
    dp[l][1]+=dp[l-1][1]*5;          
}

これは私が作ったブルート フォース チェッカーです。より効率的なソリューションを開発しようとしています。

bool f(ll n)
{
  ll p=1;
  if(n==0)
  return true;
  while(n)
  {
     p*=n%10;
     n/=10;
     if(p%2==0) return true;
     p=1;
  }
  if(p%2) return false;
  else
  return true;
}
ll brute(ll l,ll r)
{
   if(l>r) swap(l,r);
    ll cnt=0;
   for(ll  i=l;i<=r;i++)
   {
      if(f(i))
      {
         cnt++;
      }
   }

return cnt;

}

dp[l-1][0]長さ l の偶数商品数の店舗数 これで問題は解決しますか?

4

2 に答える 2

3

ブルート フォースは、非常に無駄の多いアプローチです。もっとうまくやることができます。

（書式設定についてお詫び申し上げます。内容が十分に明確であることを願っています。）

まず、問題を単純化しましょう。

EvenProductNumbersBetween(RangeStart, RangeEnd) = NumbersBetween(RangeEnd - RangeStart) - AllOddDigitNumbersBetween(RangeStart, RangeEnd)

NumbersBetween(RangeStart, RangeEnd) = (RangeEnd - RangeStart) + 1

AllOddDigitNumbersBetween(RangeStart, RangeEnd) = AllOddDigitNumbersUpTo(RangeEnd) - AllOddDigitNumbersUpTo(RangeStart-1)

いよいよ本題に入ります: AllOddDigitNumbersUpTo(RangeEnd) の計算

まず、単純なケースを考えてみましょう:

(RangeEnd が正であると仮定します)

RangeEnd が 1 桁の場合 (つまり < 10)、

AllOddDigitNumbersUpTo(RangeEnd) = Floor((RangeEnd+1)/2)

E.g.:
AllOddDigitNumbersUpTo(0) = {} = 0
AllOddDigitNumbersUpTo(1) = {1} = 1
AllOddDigitNumbersUpTo(2) = {1} = 1
AllOddDigitNumbersUpTo(3) = {1,3} = 2
AllOddDigitNumbersUpTo(4) = {1,3} = 2
AllOddDigitNumbersUpTo(5) = {1,3,5} = 3
AllOddDigitNumbersUpTo(6) = {1,3,5} = 3
AllOddDigitNumbersUpTo(7) = {1,3,5,7} = 4
AllOddDigitNumbersUpTo(8) = {1,3,5,7} = 4
AllOddDigitNumbersUpTo(9) = {1,3,5,7,9} = 5

RangeEnd が特定の桁数の任意の数値である場合、

各桁には選択肢として 5 つの奇数のいずれかが含まれている必要があることを考慮してください (先頭のゼロは長さを短くするため、除外されます)。したがって、これを直接計算するのは簡単です。

AllOddDigitNumbersOfLength(NumberLength) = 5^NumberLength

E.g.:
AllOddDigitNumbersOfLength(1) = {1, 3, 5, 7, 9} = 5
AllOddDigitNumbersOfLength(2) = {1, 3, 5, 7, 9} * {1, 3, 5, 7, 9} = 5*5 = 25
AllOddDigitNumbersOfLength(3) = 5*5*5 = 125
...

それ以外の場合は、RangeEnd を分割します。

RangeEnd = (FirstDigit * 10^PowerOfFirstDigit) + Remainder

AllOddDigitNumbersUpTo(RangeEnd) = AllOddDigitNumbersUpTo(FirstDigit) * AllOddDigitNumbersOfLength(PowerOfFirstDigit-1) + AllOddDigitNumbersUpTo(Remainder)

残念ながら、先頭にゼロがある複雑なケースがあります。(以前のバージョンの回答でこの問題を指摘してくれた @AndyProwl に感謝します!) Reminder がゼロで始まる場合、最後に AllOddDigitNumbersUpTo(Remainder) 項を追加しないでください。私たちが作ろうとするすべての小さな数でも製品。

E.g.:

AllOddDigitNumbersUpTo(6300193) =
= AllOddDigitNumbersUpTo(6*(10^7) + 300193)
= AllOddDigitNumbersUpTo(6) * AllOddDigitNumbersOfLength(7-1) + AllOddDigitNumbersUpTo(300193)
= 3 * 5^6 + AllOddDigitNumbersUpTo(300193)
= Trivial * Trivial + LogarithmicallySmallerCase

AllOddDigitNumbersUpTo(300193) =
= AllOddDigitNumbersUpTo(3*(10^6) + 00193)
= AllOddDigitNumbersUpTo(3) * AllOddDigitNumbersOfLength(6-1)
= 2 * 5^5
= Trivial * Trivial
于 2013-01-24T20:52:39.597 に答える