Title Solution CP Basic 2022 ✅

PHẦN I. XỬ LÝ MẢNG 1. ALTERSEQ - DONE - KHÁNH Vì chúng ta cần tìm dãy con đảo dấu liên tiếp dài nhất ⇔ tích hai số liên tiếp luôn âm. Để check được hết đoạn con, ta gọi thêm phần tử a[n+1]=0 để làm cái chốt. Khi kiểm tra các đoạn con, gặp chốt sẽ thoát chương trình cũng như không bỏ sót đoạn con nào. Ta bắt đầu với 1 biến đếm =1, một biến ans để tìm độ dài lớn nhất và cnt để đếm số đoạn con có độ dài là ans. - Nếu a[i]*a[i+1] < 0 thì đếm ++ - Nếu a[i]*a[i+1] >= 0: + nếu đếm > ans: ans = đếm, cnt = 1; nếu đếm = ans: cnt++; + reset đếm = 1 In ra kết quả cnt và ans 2. PRIMESEQ - DONE - KHÁNH Check các số nguyên tố. Để check được hết đoạn con, ta gọi thêm phần tử a[n+1]=0 để làm cái chốt. Khi kiểm tra các đoạn con, gặp chốt sẽ thoát chương trình cũng như không bỏ sót đoạn con nào. Ta bắt đầu với 1 biến đếm =0, một biết ans để tìm độ dài lớn nhất và cnt để đếm số đoạn con có độ dài là ans. - Nếu a[i] là số nguyên tố thì đếm ++ - Nếu a[i] không phải số nguyên tố: + nếu đếm > ans: ans = đếm, cnt = 1 else đếm == ans : cnt++; + reset đếm = 0 In ra kết quả cnt và ans 3. MAXISEQ - DONE - NGÁT Đọc dữ liệu tìm max(a); - Tìm quy luật các số thuộc dãy u: là các số có tổng các số tự nhiên liên tiếp từ 1. Kiểm tra trong O(1) Công thức kiểm tra xem 1 số có phải là tổng các số tự nhiên từ 1 hay không: Lấy số đó nhân 8 + 1 rồi kiểm tra xem có phải số chính phương không. VD: 6. 6x8+1=49 là số chính phương -> thỏa mãn - Gọi 1 biến l = 0 để tìm độ dài dãy con, một biết kq để tìm max độ dài. Duyệt mảng a, nếu a[i] thỏa mãn đề bài thì l++. Nếu không thì kq=max(kq, l) và l trở về bằng 0. Lưu ý: Làm như trên thì ta chỉ chốt lại độ dài của một dãy khi gặp một số không thuộc dãy phía đằng sau. Vậy nếu dãy con dài nhất là dãy chứa phần tử thứ n thì sẽ kết quả sẽ không được so sánh với độ dài dãy. Đến đây, điều ta cần làm là sau khi vòng for kết thúc, so sánh l với kq một lần nữa để lấy ra số lớn nhất.
- Đưa ra đáp án là kq 4. PRIMESEQ2 - DONE - KHÁNH Giống PRIMESEQ nhưng sử dụng sàng nguyên tố để kiểm tra số nguyên tố. 5. TRIPLE - DONE - NGÁT Sub 1: O(n3 ) Duyệt 3 vòng FOR để tìm lần lượt các giá trị i, j, k thỏa mãn. Sub 2: O(nlogn) Xét phần tử trung gian i (thoả mãn a[i] % X = 0, 1 < i < n), đếm xem có bao nhiêu phần tử bên trái có giá trị bằng a[i]/X và bao nhiêu phần tử bên phải có giá trị bằng a[i] * X. Sử dụng hai map để lưu số lần xuất hiện của mỗi giá trị ở bên trái và số phần tử bên phải phần tử trung gian (vừa xét vừa cập nhật các phần tử của hai map, map trái thì thêm phần tử a[i], map phải thì bỏ phần tử a[i+1]) Lưu ý, vì i chạy bắt đầu từ 2, nên ban đầu map trái sẽ chứa phần tử a[1], map phải sẽ chứa các phần tử a[3], a[4],..,a[n] 6. QUAD - DONE - KHÁNH Sub1: Độ phức tạp là O(n4 ) -Với mỗi phần tử i, ta thử tất cả các cách kết hợp có thể của 3 phần tử và so sánh tổng thu được với A[i]. Nếu được thì tăng biến dem lên 1. Sub2: Độ phức tạp là O(n3 ) Vì các giá trị trong mảng A là nhỏ nên ta có thể xây dựng một mảng P cho biết có tồn tại một giá trị xác định trong mảng trước vị trí hiện tại i hay không. Cụ thể hơn, P [x] = 1 nếu có một giá trị x trong mảng A trước vị trí i còn không thì P [x] = 0. Như vậy, thay vì thử mọi sự kết hợp có thể có của ba phần tử trước i, ta thử mọi cặp có thể có vị trí (j, k) nhỏ hơn i và xét xem có một giá trị A [i] - A [j] - A [k] trong mảng trước i không? Sau khi xử lý vị trí i, ta đặt P [A [i]] = 1. Do đó độ phức tạp của thuật toán trên là O(N3). Sub3: Độ phức tạp là O(n2 log) Thay vì xét nếu có một giá trị A [i] - A [j] - A [k] cho mỗi cặp (j, k) trong mảng trước i, ta có thể yêu cầu mọi vị trí j nếu có một cặp giá trị trước i như vậy mà tổng của chúng bằng A [i] - A [j]. Mảng P cho biết tổng của hai số nhỏ là cũng là một số nhỏ. Sau khi xử lý vị trí i, đối với mỗi cặp (i, j) với j ≤ i, ta gán P [A [i] + A [j]] = 1. Vì giá trị của một cặp số trong mảng A có thể âm. Trong C ++ ta có thể sử dụng map thay cho mảng P. Vì vậy, độ phức tạp thời gian cho thuật toán này là O (n2 log). Sub 4: Độ phức tạp là O(n2 ) Thay vì dùng map, ta nhận thấy giới hạn của A[i] nằm trong khoảng [-105 ;105 ] nên tổng cặp số bất kỳ sẽ nằm trong khoảng [-2.105 ; 2.105 ]. Vậy chỉ cần tịnh tiến tất cả các giá trị của các
cặp lên một lượng là 2.105 thì tổng các cặp sẽ nằm trong khoảng [0; 4.105 ], đủ nhỏ để khai báo một mảng đánh dấu. 7. EQUASEQ - DONE - NGÁT Gọi tổng cả dãy số là total. Vì bắt buộc phải chia toàn bộ phần tử của dãy vào các nhóm, ta thực hiện một vòng for i với ý nghĩa: Nhóm thứ nhất sẽ bao gồm các phần tử từ 1 tới i, gọi tổng của nhóm này là t. Với mỗi vị trí i ta sẽ kiểm tra xem total % t == 0 hay không?, nếu có thì dãy thứ nhất mới là dãy thoả mãn, ta thực hiện tìm các dãy tiếp theo có tổng bằng t: - Tạo biến t2 = 0 để lưu tổng của nhóm hiện tại, cnt = 1 để lưu số lượng nhóm đã chia được. - Thực hiện chạy một vòng for j = i + 1 -> n + t2 += a[j] + Nếu t2 > t => Không tạo được nhóm có tổng bằng t, break; + Nếu t2 == t => Thêm 1 nhóm có tổng bằng t: reset t2=0, cnt ++; - Sau khi for, kiểm tra xem cnt = total / t hay không, nếu có thì ta có cách chia. 8. TREELINE - DONE - NGÁT Thực hiện lặp cho đến khi dãy tạo được là một dãy tăng dần (cho đến khi không thể chặt được cây nào nữa) - Tuy nhiên thao tác xoá một phần tử trong mảng có độ phức tạp rất lớn, vì vậy thay vì dùng mảng, ta sử dụng cấu trúc dữ liệu Link-list để thao tác này có độ phức tạp O(1) 9. ARISEQ - DONE - KHÁNH Ý tưởng: Chúng ta sẽ duyệt mọi vị trí (i,j) với j< i (for i ngược từ n về 1) để chọn ra 2 phần tử cuối cùng của dãy cấp số cộng, sau đó tìm tiếp các phần tử của dãy đứng trước vị trí j trong dãy. Gọi 1 biến ans=0 và ans_d để luôn cập nhật kết quả. - gọi một biến count = 2( vì ta đã xác định được 2 số cuối a[j] và a[i]) - gọi công sai d=a[i]-a[j] - để tìm các số đứng trc a[j] với công sai d, ta thêm 1 vòng for để tìm với công thức a[k] == a[j] - d * (count - 1). Nếu đúng thì count++ - Nếu không thỏa mãn, nếu count > ans || count == ans and d > ans_d: + ans = count + ans_d = dhttps://ideone.com/SQfT5q - In ra ans và ans_d theo yêu cầu đề bài - Code: SQfT5q - Online IDE & Debugging Tool - Ideone.com 10. DIVSEQ - DONE - NGÁT Ta có thể tạo trước mảng a để lưu các số thỏa mãn yêu cầu đề bài. Vì N <= 5x10^6 nên ta thấy số chia lớn nhất là 3200.
Tạo 1 vector a để lưu Code mẫu: a.pb(++cnt); for (int i = 2; i <= 3200; i++) { int temnetflix.com/clearcookiesp = 1; cnt = (cnt/i + 1)*i; a.pb(cnt); while (temp < i) { cnt += i; a.pb(cnt); temp++; } cnt++; } Kết quả gọi ra số a[n-1] 11. MOVETREE - DONE - NGÁT Duyệt tất cả các ô trên bảng a, nếu là cây thì kt theo hàng ngang, hàng dọc có là cùng loại cây. Nếu cùng loại cây có số lượng > t thì dùng mảng b đánh dấu các cây này là 1. Kiểm tra lại tất cả các vị trí mảng a và mảng b nếu a[i][j]>0 &&b[i][j]==0=>dem++; PHẦN II. BÀI TẬP TOÁN HỌC 12. CPRIME - DONE - NGÁT Nhận thấy n <= 2 * 10 , hay số chữ số của n có tối đa 10 chữ số. 9 Ta tạo tất cả các dãy liên tiếp các chữ số từ n. Với mỗi số được tạo, kiểm tra xem đó có phải là số nguyên tố hay không. ĐPT: O( n) 13. LPRIME - DONE - AN Ý tưởng: dùng sàng nguyên tố. Sau khi có mảng các số nguyên tố, có thể xét x có phải số nguyên tố hay không trong O(1). ĐPT: O(nlogn) 14. SPRIME - DONE - AN Ý tưởng: Dễ thấy số nguyên tố đặc biệt là bình phương của 1 số nguyên tố. Bước 1: Sàng nguyên tố Bước 2: Kiểm tra xem với mỗi a[i], căn bậc 2 của nó có là số nguyên tố hay không ĐPT: O(nlogn)