可能なすべての K 操作後の、特定のバイナリ文字列内の設定ビット数の平均

この問題では、指定された文字列に対して選択された K 個の操作をすべて実行した後、設定されたビット数の平均を見つける必要があります。

問題を解決するために総当たり法を使用することもできますが、総当たり法の時間計算量を克服するために確率原理を使用します。

問題文 - 整数 N、K 個の正の整数を含む配列 arr[]、および設定されたビットのみを含む長さ N のバイナリ文字列が与えられます。可能なすべての K 操作を実行した後、設定されたビット数の平均を見つける必要があります。 i 番目の操作では、指定された文字列内の任意の arr[i] ビットを反転できます。

＃＃＃例＃＃＃

入力

– N = 2、arr[] = {1, 2}

出力

– 1

説明

– 初期のバイナリ文字列は 11 です。

最初のステップでは、最初の文字を反転すると、文字列は 01 になります。
2 番目の操作では、任意の 2 ビットを反転する必要があります。したがって、文字列は 10 になります。

2 番目の選択は、最初のステップの 2 番目の文字を反転することで開始でき、文字列は 10 になります。
現在の操作の 2 番目のステップでは、任意の 2 ビットを反転する必要があり、文字列は 01 にすることができます。

したがって、選択肢は 2 つあり、最後の文字列は 01 または 10 になります。

選択の合計 = 2、最終文字列のセット ビットの合計 = 2、ans = 2/2 = 1。

入力

– N = 3、arr[] = {2, 2}

出力

– 1.6667

説明

– 初期文字列は 111 です。

最初の操作では、任意の 2 文字を反転できます。したがって、文字列は 001、100、010 になります。
2 番目の操作では、最初の操作で得られた文字列の 2 ビットを反転できます。
001 の任意の 2 ビットを反転すると、111、010、100 が得られます。
100 の任意の 2 桁を反転すると、010、111、001 が得られます。
010 の任意の 2 ビットを反転すると、100、001、111 が得られます。

つまり、最後の操作では、合計 9 つの異なる文字列が得られました。

9文字列の設定桁数の合計=15、演算の合計数=9、答え=15/9=1.6667

方法 1

ここでは、確率の原理を使用してこの問題を解決します。 i-1 回の演算を実行した後、設定されたビットの平均値が p、未設定のビットの平均値が q であるとします。 i 番目の操作では、設定されたビットと未設定のビットの平均を計算する必要があります。

したがって、p の更新された値は、p の新しい設定ビットの平均、つまり新しい閉じられたビットの平均になります。

＃＃＃アルゴリズム＃＃＃

最初に N 個のセット ビットがあるため P を N に初期化し、最初に 0 個のセット ビットがあるため Q を 0 に初期化します。

• 操作配列を走査します。

• P 値と Q 値を使用して prev_p と prev_q を初期化します。

• prev_p - prev_p * arr[i] / N prev_q * arr[i] / N を使用して P 値を更新します。これにより、反転されたビットが設定されたビットに平均化され、設定されたビットが設定されていないビットに反転されます

• Q値を更新します。

• P 値を返します。

• Example

  の中国語訳は次のとおりです:
Example

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(K)、K は配列の長さです。

スペースの複雑さ - 余分なスペースを使用していないため、O(1)。

このチュートリアルでは、K 個の演算の考えられるすべての選択肢を実行した後、平均設定ビットを見つける方法を学びました。単一選択では、配列で指定されたすべての操作を実行する必要があります。

以上が可能なすべての K 操作後の、特定のバイナリ文字列内の設定ビット数の平均の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。