Số bước tối thiểu cần thiết để biến tất cả các bit nhị phân thành một trạng thái

Question

Có một mảng các số nhị phân M và mỗi số trong số đó nằm trong trạng thái '0' hoặc '1'. Bạn có thể thực hiện một số bước trong việc thay đổi trạng thái của các số và trong mỗi bước bạn được phép thay đổi trạng thái của chính xác N số thứ tự. Căn cứ vào số M, N và các mảng với các thành viên tất nhiên, bạn muốn tính toán số lượng tối thiểu của các bước cần thiết để biến tất cả các số nhị phân thành một nhà nước - 1 hoặc 0.

---

Nếu M = 6 và N = 3 và mảng là 1 0 0 1 0 0, sau đó giải pháp sẽ là 2. Giải thích: Chúng ta có thể lật chúng để tất cả chúng là 1 trong hai bước: chúng ta lật từ chỉ số 2 đến 4 và chúng ta biến đổi mảng đến 111000, và sau đó lật ba (N) 0s tới 1.

Answer 1

Nếu tôi đã hiểu chính xác câu hỏi, một chút suy nghĩ sẽ thuyết phục bạn rằng ngay cả lập trình động cũng không cần thiết - giải pháp hoàn toàn không đáng kể.

Đây là câu hỏi như tôi hiểu nó: bạn đang đưa ra một mảng a [1] .. a [M] của 0s và 1s, và bạn được phép hoạt động của mẫu S _k, trong đó S _k có nghĩa là lật các phần tử N thành [k], [k + 1], ... a [k + N-1]. Điều này chỉ được xác định cho 1≤k≤M-N + 1, rõ ràng.

Bằng cách thực hiện một chuỗi các thao tác này S _k, bạn muốn tiếp cận trạng thái của tất cả 0 hoặc tất cả 1s. Chúng tôi sẽ giải quyết cho cả hai cách riêng biệt và lấy số nhỏ hơn. Vì vậy, giả sử chúng tôi muốn làm cho tất cả 0 (trường hợp khác, tất cả 1s, là đối xứng).

Các quan trọng ý tưởng là bạn sẽ không bao giờ muốn thực hiện bất kỳ hoạt động S _k nhiều hơn một lần (làm việc đó hai lần tương đương với không làm gì cả), và đó là thứ tự của các hoạt động không quan trọng. Vì vậy, câu hỏi là chỉ để xác định tập hợp con của các hoạt động bạn thực hiện, và điều này rất dễ dàng để xác định. Nhìn vào [1]. Nếu đó là 0, thì bạn biết bạn sẽ không thực hiện S . Khác, bạn biết bạn phải thực hiện S (vì đây là thao tác duy nhất sẽ lật [1]), do đó hãy thực hiện nó - thao tác này sẽ chuyển tất cả các bit từ [1] sang [N]. Bây giờ nhìn vào một [2] (sau khi hoạt động này). Tùy thuộc vào việc nó là 1 hay 0, bạn biết liệu bạn sẽ thực hiện S hay không. Và cứ thế - bạn có thể xác định có bao nhiêu thao tác (và cái nào) để thực hiện, trong thời gian tuyến tính.

Chỉnh sửa: Mã giả được thay thế bằng mã C++, vì có thẻ C++. Xin lỗi vì mã xấu xí; khi ở "chế độ cuộc thi" tôi hoàn nguyên về thói quen thi đấu. :-)

#include <iostream> 
using namespace std; 
const int INF = 20000000; 
#define FOR(i,n) for(int i=0,_n=n; i<_n; ++i) 

int flips(int a[], int M, int N, int want) { 
    int s[M]; FOR(i,M) s[i] = 0; 
    int sum=0, ans=0; 
    FOR(i,M) { 
    s[i] = (a[i]+sum)%2 != want; 
    sum += s[i] - (i>=N-1?s[i-N+1]:0); 
    ans += s[i]; 
    if(i>M-N and s[i]!=0) return INF; 
    } 
    return ans; 
} 

int main() { 
    int M = 6, N = 3; 
    int a[] = {1, 0, 0, 1, 0, 0}; 
    printf("Need %d flips to 0 and and %d flips to 1\n", 
     flips(a, M, N, 0), flips(a, M, N, 1)); 
} 

Answer 2

tôi mã hóa lên các thuật toán mà ShreevatsaR đề xuất, nhưng với việc cải thiện hàng đợi thêm để làm cho nó thời gian tuyến tính sản tại M.

int solve(vector<bool> bits, int N) 
{ 
    queue<int> flips; 
    int moves = 0; 

    for (int i = 0; i < bits.size(); ++i) 
    { 
    if (!flips.empty() && flips.front() <= i - N) 
     flips.pop(); 

    if ((bits[i]^(flips.size() % 2 == 0)) == 1) 
    { 
     if (i > bits.size() - N) 
     return -1; // IMPOSSIBLE 

     moves++; 
     flips.push(i); 
    } 
    } 

    return moves; 
} 

Chỉ cần chạy mà trên bản gốc và các đảo ngược bản gốc và lấy tối thiểu (nếu chúng không phải là -1). Nếu cả hai là -1 thì không thể.

Lưu ý rằng tôi chưa biên soạn hoặc kiểm tra mã đó, nhưng nó sẽ hoạt động.