Xin ý tưởng về thuật toán sinh xâu nhị phân độ dài N có chứa duy nhất dãy M số 0 liên tiếp

Em nghĩ là với mỗi lần tạo một dãy nhị phân xong thì bỏ vào một mảng, sau đó dùng biến đếm số lần xuất hiện liên tiếp của số 0, khi và chỉ khi dem=M thì mới in ra màn hình

Bài này dùng graph giải được. Nhưng trong thư viện <algorithms> c++ có hàm next_permutation, kết hợp với mảng string, nghiên cứu thử đi

Cách “trâu bò” nhất là lặp từ số lớn nhất có độ dài N đến 0, rồi kiểm tra xem có hợp lệ hay không.

bây giờ bạn hãy viết thuật toán sinh xâu nhị phân bình thường , nhưng trước khi in ra hãy kiểm tra điều kiện

int test()
{
int s=0; dem0=0;
for(int i=1;i<=n;i++)
{
if(x[i]==0) { dem0++;
if(dem0>=m) s++;
} else dem0=0;
}
if(s==1) return 1;
return 0;
}

Ý tưởng của mình:
Đặt dãy 0 liên tiếp = X
Từ đó rút gọn dãy thành abX
Sinh dãy ab sau đó chèn X vào.
Trước khi chèn thì kiểm tra xem các số kế bên có là 0 hay không. Nếu phải thì ko chèn, còn ko thì đâm đầu vô ‘3’

mình không có ý gì , nhưng cảm thấy cách của bạn phức tạp.

Cho hỏi giới hạn là bao nhiêu vậy? Giới hạn cực đại của M, N ấy

Nếu giới hạn cho phép thì có thể sử dụng QHĐ O(N*M), nhưng số cách có thể rất lớn (lúc đó thì xử lý số lớn hay là lấy mod thì tùy yêu cầu)
nếu ta phân tích ra thì có thể chia làm 3 đoạn XYZ, trong đó Y là đoạn độ dài M và chứa toàn số 0, Z và Y là 2 đoạn trái phải (nếu X, Z không rỗng thì kí tự cuối của X và đầu của Z phải là 1 (để ngắt đoạn Y)). Nhưng nếu để ý thì nếu reverse lại Z thì cũng sẽ giống như X
-> bài toán trở về là hỏi có bao nhiêu cách phân tích X sao cho chỉ chứa các dãy 0 liên tiếp độ dài < M.
Gọi F[i][j] là số cách chọn dãy nhị phân độ dài i và số kí tự 0 cuối cùng là j.
Đến kí tự thứ i+1 thì sẽ có 2 cách: chèn 0 hoặc 1
nếu chèn 1 -> F[i+1][0] (chèn 1 -> số kí tự 0 cuối cùng hiện tai là 0) bằng tổng F[i][0] -> F[i][m-1].
nếu chèn 0 -> F[i+1][j] = F[i][j-1] với j = 1 … m-1 (không thể có f[i][m] vì không được phép chèn m kí tự 0 liên tiếp).
Sau khi thực hiện bảng QHĐ thì ta thấy rằng số cách sinh dãy nhị phân độ dài là i, số kí tự 0 liên tiếp nhỏ hơn M và có kí tự cuối cùng = 1 chính là F[i][0].
vì độ dài Y là cố định và |X| + |Y| + |Z| = N --> |X| + |Z| = N - M. Từ đây ta chỉ cần duyệt theo độ dài của X (|X|) để thử chọn Z tương ứng.
với mỗi độ dài i, có thể chọn ra F[i][0] dãy nhị phân cho X và F[N-M-i][0] dãy nhị phân cho Z -> có F[i][0]*F[N-M-i][0] cách chọn
Tổng hết lại sẽ được kết quả cần tìm.
Chỉ vô tình thấy có người share trên fb và suy nghĩ nhanh nên có thể thuật toán chưa tối ưu, có thể rút gọn còn O(NlogN), O(NlogM) hay O(N) gì đó chẳng hạn. Nếu ai nghĩ ra rep lại cho mọi người cùng học hỏi nhé

Blockquote
Cách “trâu bò” nhất là lặp từ số lớn nhất có độ dài N đến 0, rồi kiểm tra xem có hợp lệ hay không.

Such a buffalow way