Title Solution CP Advanced 2023 ✅

PHẦN I. BACKTRACK Lý thuyết Backtrack: https://codedream.edu.vn/backtrack-thuat-toan-quay-lui-duyet/ https://codedream.edu.vn/backtrack-duyet-chia-doi-tap-hop/ 1. KDIGIT - ĐẠT - DONE - đã xong Để tạo ra các số nhỏ hơn hoặc bằng N, ta đổi N sang dạng nhị phân. Gọi L là số lượng chữ số trong N( dưới dạng nhị phân)y => Số nhị phân ta cần xây dựng phải có độ dài là L, thảo mãn điều kiện là nó phải bé hơn N và có đúng k số 1. Để xây dựng các số thì ta có thể dùng backtrack(val, cnt, l) trong đó + val là giá trị của số ta đang dựng + cnt là số lượng chữ số 1 trong đó + l là độ dài của dãy nhị phân đó Với mỗi lần backtrack, ta sẽ thêm số 1 hoặc số 0 đằng sau val cho tới khi val dưới dạng nhị phân có đủ L chữ số (hay l == L) - Có rất nhiều cách để ta có thể thêm số 1 hoặc số 0 vào đằng sau val. + Cách 1: Nếu thêm số 0 vào đằng sau val thì ta sẽ lấy val = val*2 Nếu thêm số 1 vào đằng sau val thì ta sẽ lấy val = val*2+1 + Cách 2: Ngoài cách trên ra thì ta thao tác bit trong C++ Nếu thêm số 0 vào đằng sau val thì ta sẽ có val = val << 1 (dịch bit sang phải 1 đơn vị) Nếu thêm số 1 vào đằng sau val thì ta sẽ có val = (val << 1) | 1; Khi đó, nếu cnt == k thì ta sẽ ans++; * Chúng ta có thể cải thiện độ phức tạp của thuật toán hơn nữa bằng cách nếu khi trong val có cnt > k trong khi l < L thì ta có thể return luôn vì khi đó dù ta có thêm số nào vào sau val thì số lượng số 1 trong val luôn luôn lớn hơn k. 2. LSET - ĐẠT - DONE - đã xong
Để liệt kê tất cả các tập hợp khác rỗng các số từ 1 đến n theo thứ tự từ điển, ý tưởng của bài là ta sẽ in từng số từ 1 đến n. Tuy nhiên để in ra tất cả các dãy thì ta sẽ cần dùng backtrack để xem nên in số nào và bỏ qua những số nào Ví dụ với n = 6 thì khi ta in ra dãy 1 5 6 tức là ta quyết định in ra các số 1, 5, 6 và bỏ qua các số 2, 3, 4 Ta có thể xây dựng hàm backtrack như sau backtrack(i) trong đó + pos là số mà ta đang xét đến -> Ta sẽ gọi backtrack(1) để in ra các tập hợp Nếu mà i > n thì ta sẽ return luôn (chữ số trong tập hợp phải bé hơn n) Với mỗi lần backtrack(i), ta sẽ chia thành 2 trường hợp là in ra i hoặc bỏ qua i. + Nếu bỏ qua i thì ta sẽ gọi tiếp hàm backtrack(i+1) luôn. + Nếu in ra i thì ta sẽ cout << i << “ “ rồi mới gọi hàm backtrack(i+1) 3. LCOMB - DONE -Kiên123 - đã xong -Tổ hợp chập k của n là những tập hợp chứa k phần tử từ khoảng 1 -> n nên để liệt kê tất cả các tập hợp chứa k phần tử từ khoảng 1 -> n. Tuy nhiên để in ra tất cả các tổ hợp chập k của n thì ta sẽ cần dùng backtrack để xem nên chọn số nào và bỏ qua những số nào. -Ta sẽ backtrack 0 1 để xem số nào là số dc chọn và số nào là số k dc chọn. -Mỗi lần backtrack(x) ta sẽ có 2 TH là chọn x và k chọn x. + Nếu chọn x ta sẽ cout << x << ‘ ‘ xong gọi backtrack(x+1). + Nếu k chọn thì ta sẽ gọi backtrack(x + 1) luôn. -Nếu x > n thì ta sẽ return và cout << endl luôn. 4. LSUM - DONE - Kiên123 - đã xong -Đề bài bắt ta phân tích n thành tổng các số nguyên nhỏ hơn n theo thứ tự từ điển -> ta phải in theo thứ tự từ bé đến lớn => số tiếp theo sẽ > số đằng trước. -Do đó ta có thể backtrack 2 biến là vị trí và tổng còn lại - backtrack(pos, sum). -Mỗi lần backtrack(x, sum) ta sẽ có nhiều cách chọn số ở vị trí x : từ a[x - 1] -> sum do a[x] >= a[x - 1] từ nxet ở trên.(a[i] là số dc điền ở vị trí i) -Nếu chọn gtri y ở vị trí x thì sum sẽ dc cập nhật = sum - y và ta sẽ gọi backtrack(x + 1, sum - y); -Các số dc chọn sẽ cho vào 1 vector xong in ra kqua.
5. LEXP1 - DONE - Kiên123 - đã xong -Ở bài này họ bắt ta phải điền dấu + hoặc - vào trước các số ở trong xâu s và cũng có thể k chọn số đó => ta sẽ backtrack 0 1 2: + 0 nghĩa là ko chọn số đó. + 1 nghĩa là đặt dấu - vào trc số đó. + 2 nghĩa là đặt dấu + vào trc số đó. -Ta sẽ cbi trc 1 mảng a[i] nghĩa là đặt dấu gì vào trước vị trí i. -Ta sẽ gọi 1 biến sum = 0 để lấy kqua sau mỗi lần backtrack (khi mà pos > s.size() thì ta sẽ lấy kqua): -Ta sẽ for i lại từ 0 -> s,size() -1 : + Nếu a[i] = 0 ta sẽ bỏ qua vì 0 là ko chọn. + Nếu a[i] = 1 -> sum -= gtri ở vị trí i trong xâu s. + Nếu a[i] = 2 -> sum += gtri ở vị trí i trong xâu s. -Và cuối cùng nếu sum == M thì biến kqua của ta sẽ tăng lên 1. 6. LEXP2 - ĐẠT - DONE - đã xong Để tìm kết quả A lớn nhất mà không vượt qua M cho trước, ta có thể dùng backtrack để thay các dấu vào giữa các phần tử a[i]. * Tuy nhiên ta cần lưu ý rằng mặc dù thay các dấu vào nhưng ta vẫn cần phải thực hiện phép tính với thao tác là nhân chia trước cộng trừ sau. Vì vậy ta sẽ dùng 2 biến, 1 biến tính tổng và 1 biến tính tích. Ta gọi hàm backtrack (i, sum, p) với ý nghĩa là: + i là chỉ số i khi ta xét đến phần tử a[i] (hay còn gọi là điền dấu gì vào trước a[i]). + p là phép tính nhân (hoặc chia) các phần tử đến a[i] + sum là tổng các số phân tử đến a[i] (không bao gồm p) Do có 4 dấu là cộng, trừ, nhân, chia nên ta sẽ gọi hàm backtrack 4 lần. - Với dấu cộng hoặc dấu trừ thì ta sẽ gọi hàm backtrack đơn giản như sau: + Với dấu cộng, ta sẽ backtrack (i + 1, sum + p, a[i]) + Với dấu trừ, ta sẽ backtrack (i + 1, sum + p, - a[i])
*Cái p là cái ta tính ở trước nên dù có dùng dấu cộng hay dấu trừ thì ta vẫn phải sum+p, thứ duy nhất khác biệt là dấu của a[i]. - Còn với dấu nhân hoặc dấu chia, trước hết thì ta không thể điền dấu này vào trước số a[1] nên ta cần phải thêm điều kiện để điền dấu này là (i > 1) - Với dấu nhân, ta sẽ backtrack (i + 1, sum, p * a[i]) - Với dấu nhân, ta sẽ backtrack (i + 1, sum, p / a[i]) Khi ta xét hết n phần tử thì khi đó ta sẽ so sánh xem sum < M hay không, nếu có thì ans++ và nếu không thì return. Lưu ý là nếu p > 0 thì ta phải sum += p trước khi so sánh. 7. SINMAX - DONE -Kiên123 - đã xong -Bài này ta chỉ cần backtrack 0 1 : + 0 nghĩa là ko chọn. + 1 nghĩa là có chọn. -Ta sẽ cbi trước 1 mảng a[i] nghĩa là có chọn số ở vị trí i hay ko. -Mỗi lần gọi Backtrack(i) ta sẽ có 2 lựa chọn: +Nếu chọn ta sẽ gán a[i] = 1. +Ngược lại ta sẽ gán a[i] = 0. -Khi mà i > n thì ta sẽ for it từ 1 -> n để tính lại sum mà backtrack chọn được: + Nếu a[it] = 1 sum += gtri ở vị trí it. + Ngược lại thì bỏ qua. -Nếu sin(sum) > sin(kqua) thì ta sẽ gán kqua = sum. 8. SELECT1 - ĐẠT - DONE - đã xong Nhận xét: Để chọn N số sao cho chúng có tổng lớn nhất và không phần tử nào có cùng hàng hoặc cùng cột. Suy ra với mỗi hàng, ta xem sẽ lấy cột nào của hàng đó. Vậy, ta có thể hiểu đây là một bài toán sinh hoán vị với ý nghĩa: