가능한 모든 K 연산 후 주어진 이진 문자열에서 설정된 비트 수의 평균-C++-php.cn

가능한 모든 K 연산 후 주어진 이진 문자열에서 설정된 비트 수의 평균

WBOY

풀어 주다： 2023-08-25 12:29:06

앞으로

655명이 탐색했습니다.

가능한 모든 K 연산 후 주어진 이진 문자열에서 설정된 비트 수의 평균

이 문제에서는 주어진 문자열에 대해 선택된 K 연산을 모두 수행한 후 설정된 비트 수의 평균을 구해야 합니다.

무차별 대입 방법을 사용하여 문제를 해결할 수 있지만, 무차별 대입 방법의 시간 복잡도를 극복하기 위해 확률 원리를 사용하겠습니다.

문제 설명 - 정수 N, K개의 양의 정수를 포함하는 배열 arr[], 설정된 비트만 포함하는 길이 N의 이진 문자열이 제공됩니다. 가능한 모든 K 연산을 수행한 후 설정된 비트 수의 평균을 찾아야 합니다. i번째 연산에서는 주어진 문자열의 arr[i] 비트를 뒤집을 수 있습니다.

예

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

출력– 1

Description – 초기 바이너리 문자열은 11입니다.

첫 번째 단계에서는 첫 번째 문자를 뒤집을 수 있으며 문자열은 01이 됩니다.

두 번째 작업에서는 두 비트를 뒤집어야 합니다. 그러면 문자열은 10이 됩니다.

두 번째 선택은 첫 번째 단계에서 두 번째 문자를 뒤집어서 시작할 수 있으며 문자열은 10이 됩니다.

현재 연산의 두 번째 단계에서는 임의의 2비트를 뒤집어야 하며 문자열은 01이 될 수 있습니다.

그래서 두 가지 선택이 있습니다. 최종 문자열은 01 또는 10이 될 수 있습니다.

총 선택 항목 = 2, 최종 문자열의 총 설정 비트 = 2, ans = 2/2 = 1.

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

출력– 1.6667

설명 – 초기 문자열은 111입니다.

첫 번째 작업에서는 문자 2개를 뒤집을 수 있습니다. 따라서 문자열은 001, 100, 010이 될 수 있습니다.
두 번째 작업에서는 첫 번째 작업의 결과 문자열에서 2비트를 뒤집을 수 있습니다.

001의 두 비트를 뒤집으면 111, 010, 100이 됩니다.
100의 두 자리 숫자를 뒤집으면 010, 111, 001이 나옵니다.
010의 두 비트를 뒤집으면 100, 001, 111이 나옵니다.

그래서 마지막 작업에서 총 9개의 서로 다른 문자열을 얻었습니다.

9개 문자열의 총 설정 자릿수=15, 총 연산 수=9, 답변=15/9=1.6667

방법 1

여기에서는 확률의 원리를 이용하여 이 문제를 해결해 보겠습니다. i-1 연산을 수행한 후 설정된 비트의 평균값을 p, 설정되지 않은 비트의 평균값을 q라고 가정합니다. i번째 작업에서 설정된 비트와 설정되지 않은 비트의 평균을 계산해야 합니다.

따라서 p의 업데이트된 값은 p + 새로운 설정 비트의 평균 수 - 새로운 off 비트의 평균 수일 수 있습니다.

알고리즘

처음에 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 값을 업데이트하면 반전된 비트가 평균적으로 설정된 비트에 추가되고 평균적으로 설정된 비트가 Unset 비트로 반전됩니다.
Q 값을 업데이트하세요.
P 값을 반환합니다.