Dãy nhị phân 2
Đề bài
Hệ nhị phân (hay hệ đếm cơ số hai) là một hệ đếm dùng hai ký tự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Hai ký tự đó thường là 0 và 1; chúng thường được dùng để biểu đạt hai giá trị hiệu điện thế tương ứng (có hiệu điện thế, hoặc hiệu điện thế cao là 1 và không có, hoặc thấp là 0). Do có ưu điểm tính toán đơn giản, dễ dàng thực hiện về mặt vật lý, chẳng hạn như trên các mạch điện tử, hệ nhị phân trở thành một phần kiến tạo căn bản trong các máy tính đương thời.
Trong bài tập này bạn được cho một số nguyên dương $n$, bạn cần tìm và in ra danh sách các dãy nhị phân có độ dài đúng $n$ thoả mãn điều kiện cụm "01" xuất hiện không quá 1 lần trong dãy nhị phân này.
Dữ liệu vào:
- Gồm một dòng chứa số nguyên dương $n$.
Kết quả:
- Dòng đầu tiên ghi một số nguyên dương $m$ là số lượng dãy nhị phân tìm được.
- Mỗi dòng tiếp theo in một dãy nhị phân độ dài $n$ tìm được. Các dãy nhị phân in tăng dần theo thứ tự từ điển.
Ràng buộc: $1 \le n \le 100$.
38
000
001
010
011
100
101
110
111Lời mở đầu
Thoạt nhìn bài này giống hệt Dãy nhị phân 1, nhưng $n$ lên tới 100: không đời nào duyệt nổi $2^{100}$ dãy. Điều cứu ta là số dãy thoả mãn lại rất ít (với $n = 100$ chỉ có $166\,751$ dãy). Vậy phải dùng quay lui có cắt nhánh – chỉ đi vào những nhánh còn có thể thành dãy hợp lệ. Khác với Dãy nhị phân 3 (chỉ cần nhìn ký tự ngay trước), ở đây ta phải nhớ thêm một thông tin: đã có bao nhiêu cụm 01. Bảng so sánh 3 bài dãy nhị phân trong contest:
| Bài | Điều kiện của dãy | In số lượng? | Giới hạn | Số dãy cần in | Điểm mấu chốt |
|---|---|---|---|---|---|
| Dãy nhị phân 1 | Không có – in tất cả $2^n$ dãy | Không | $1 \le n \le 20$ (test thật tới 24) | $2^n$ | Thuần quay lui, không cắt nhánh; khó ở chỗ in nhanh hàng trăm MB |
| Dãy nhị phân 2 (bài này) | Cụm 01 xuất hiện không quá 1 lần | Có (dòng đầu) | $1 \le n \le 100$ | $(n+1) + \binom{n+1}{3}$ | Bắt buộc cắt nhánh (không thể duyệt $2^{100}$); cần nhớ số cụm 01 đã có |
| Dãy nhị phân 3 | Không có hai số 1 đứng cạnh nhau | Có (dòng đầu) | $1 \le n \le 25$ | Fibonacci $F_{n+2}$ | Cắt nhánh chỉ cần nhìn ký tự ngay trước; sinh hết rồi lọc vẫn kịp trong C++ |
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, mỗi test một số $n$: test 1 là $n = 3$ (test đề), test 2 là $n = 2$, test 3 là $n = 1$, các test 4 – 100 có $n$ đúng bằng số thứ tự test. Đúng ràng buộc đề. Test lớn nhất ($n = 100$) phải in $166\,751$ dãy, khoảng 17 MB:
| Test | $n$ | Số dãy lớn nhất | File output lớn nhất |
|---|---|---|---|
| 1 – 20 | 1 … 20 | 1.351 | 29,7 KB |
| 21 – 100 | 21 … 100 | 166.751 | 17,0 MB |
Đề không chia subtask; mình chia 2 mức để thấy rõ khi nào cách "sinh hết" còn dùng được:
| Mức | Điều kiện | Các test | Cách 1 C++ sinh hết rồi lọc | Cách 1 Python | Cách 2 C++ cắt nhánh | Cách 2 Python |
|---|---|---|---|---|---|---|
| 1 | $n \le 20$ | 1 – 20 | 20/20 | 19/20 | 20/20 | 20/20 |
| 2 | $21 \le n \le 100$ | 21 – 100 | 3/80 | 0/80 | 80/80 | 70/80 |
Ý tưởngMang theo số cụm "01" khi đi xuống cây
Cụm 01 mới chỉ xuất hiện khi ta đặt 1 ngay sau một 0. Vậy khi gọi đệ quy, ta truyền thêm tham số $d$ = số cụm 01 đã có trong phần đã điền:
Try(i, d): thử $c$ = 0 rồi 1. Tính $nd = d + 1$ nếu ($i > 0$, $s_{i-1} = $ 0, $c = $ 1), ngược lại $nd = d$. Nếu $nd > 1$ thì cắt nhánh (bỏ qua $c$); ngược lại đặt $s_i = c$ và gọi Try(i + 1, nd). Đủ $n$ ký tự thì dãy chắc chắn hợp lệ.Không có nhánh nào "đi vào ngõ cụt": ở bất kỳ nút nào ta cũng luôn đặt được 0 (không bao giờ tạo thêm 01). Vì vậy số nút của cây chỉ cỡ $n \times$ (số dãy kết quả) – rất nhỏ.
Có bao nhiêu dãy? Dãy có không quá một cụm 01 luôn có dạng $1\dots1\,0\dots0\,1\dots1\,0\dots0$ (mỗi khối có thể rỗng). Không có cụm 01 nào: dạng $1\dots1\,0\dots0$, có $n+1$ dãy. Đúng một cụm: chọn 3 "điểm cắt" khác nhau trong $n+1$ khe để chia ra 4 khối (khối 0 thứ nhất và khối 1 thứ hai không rỗng), có $\binom{n+1}{3}$ dãy. Tổng: $m = (n+1) + \binom{n+1}{3}$; với $n = 3$ là $4 + 4 = 8$ (đúng test đề: cả 8 dãy đều hợp lệ vì cần ít nhất 4 ký tự mới có 2 cụm 01), với $n = 100$ là $101 + 166\,650 = 166\,751$.
Em nhập $n$, chọn có cắt nhánh (1) hoặc sinh hết rồi lọc (0), rồi bấm Tiếp. Với $n = 4$, dãy duy nhất bị loại là 0101:
Cách 1Sinh hết $2^n$ dãy rồi lọc
Đi hết cây đầy đủ, đủ $n$ ký tự thì gọi ok() đếm số cụm 01. Vì phải in số lượng trước nên các dãy hợp lệ được gom vào xâu res, cuối cùng in cnt rồi in res.
Kết quả chạy thật: bản C++ đúng 23/100 test (tới $n = 23$), quá thời gian ở test 24–100. Bản Python đúng 19/100 test, TLE ở test 20–100. Đúng như dự đoán: $2^n$ tăng quá nhanh.
Cách 2Quay lui có cắt nhánh
int nd = d + (i > 0 && s[i - 1] == '0' && c == '1');: biểu thức logic trong C++ có giá trị 0 hoặc 1, cộng thẳng vàodđược. Điều kiệni > 0đứng trước để không đọcs[-1].if(nd > 1) continue;: cắt nhánh – không gán, không gọi đệ quy.- $d$ là tham số của hàm nên khi quay lui nó tự trở về giá trị cũ, không cần "trả lại" như biến toàn cục.
- Không biết trước số lượng (trừ khi dùng công thức ở trên) nên vẫn gom vào
res; 17 MB là chấp nhận được.
Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất chỉ 0,071 giây. Full điểm! 🎉 Bản Python đúng 90/100 test, quá thời gian nhẹ (1,1 – 1,5 giây) ở test 91–100: với $n \ge 91$ cây có khoảng 15 triệu nút, mỗi nút là một lời gọi hàm Python – hơi nặng so với giới hạn 1 giây.
01) làm tham số đệ quy để biết khi nào phải cắt – kỹ thuật này sẽ gặp lại ở rất nhiều bài quay lui khó hơn.
Nhận xét
Đăng nhận xét