Xin chúc mừng các bạn đã hoàn thành contest này. Và xin lỗi các bạn về độ khó của contest lần này. Sau đây là top 5 của contest.
-
a519QuangLD
-
A519Quy BackTracking
-
a218Khalpa
-
A518 Hưng Backtrack
-
HMĐ
Đây là lời giải của contest.
A - LN
Ý tưởng : Ami
Testing : Cuom1999
Ta có thể giải bằng cách chạy lần lượt các phần tử trong xâu và đếm x là số lượng chữ cái L hiện tại. Khi gặp kí tự N, chúng ta sẽ thêm x vào kết quả hiện tại.
B - SAMEMAT
Ý tưởng : Ami
Testing : Cuom1999
Có nhiều cách làm bài này. Cách giải tốt nhất trong mọi trường hợp là chuyển 2 mảng 2 chiều thành 2 mảng 1 chiều. Sắp xếp 2 mảng một chiều lại theo thứ tự tăng dần và lần lượt so sánh 2 phần tử cùng vị trí của 2 mảng. Nếu có 2 phần tử khác nhau thì kết quả là “NO", ngược lại kết quả là “YES"
C - LINE
Ý tưởng : Ami
Testing : Cuom1999
Ta chỉ đơn thuần duyệt vét cạn cho bài toán này. Duyệt từ L đến R và lưu mảng cnt[x] là số lần xuất hiện của phần tử x trong đoạn con này. Mỗi lần cập nhật x, ta sẽ đồng thời cập nhật lại giá trị max. Sau khi duyệt xong đoạn L và R, ta sẽ cập nhật lại mảng cnt bằng 0 để cho các truy vấn sau. Lưu ý rằng, để cập nhật giá trị cnt bằng 0, ta chỉ cần duyệt lại đoạn L đến R và gán cnt[a[i]] = 0.
D - MAXDIV
Ý tưởng : Ami
Testing : Cuom1999
Đầu tiên, ta có mảng cnt[x] là số lần xuất hiện của x trong mảng và div[x] là số bội số của x trong mảng. Dùng thuật toán sàng nguyên tố, ta có thể biết được số i là ước của các số nào. Giả sử số i là ước của số r, ta sẽ thêm cnt[r] vào div[i] và cập nhật lại giá trị của max.
E - MTHNUM
Ý tưởng : Ami
Testing : Cuom1999
Ta có thể dựng cây phân đoạn trên mảng này, mỗi nút sẽ lưu tất cả các giá trị trong đoạn này theo thứ tự tăng dần. Với mỗi truy vấn L đến R, ta chỉ đơn giản duyệt các nút tạo nên đoạn này. Với mỗi nút, ta sẽ dùng thuật toán tìm kiếm nhị phân để tìm ra có bao nhiêu số bé hơn K trong đoạn này và cộng tất cả các giá trị này của các nút để tìm ra kết quả bài toán.
F - LOVEPATH
Ý tưởng : Ami
Testing : Cuom1999
Đầu tiên, xét thuật toán quy hoạch động. Gọi F[i][j] là số cách di chuyển từ ô khởi đầu đến ô (i,j). Ta có công thức
F[i][j] = F[i-1][j-1] + F[i][j-1] + F[i+1][j-1];
Công thức trên viết lại thành
F[i][j] = 0 * F[1][j-1] + 0 * F[2][j-1] + … + F[i-1][j-1] + F[i][j-1] + F[i+1][j-1] + …. + 0 * F[n][j-1].
Từ đó, ta có thể nghĩ ra một thuật toán nhân ma trận đơn giản. Tạo một ma trận A số_hàng * số_hàng. A[i][j] = 1 nếu từ ô (j , a) có thể đi đến ô (i , a), ngược lại thì A[i][j] bằng 0. Tạo một ma trận B số_hàng * 1. B[i][1] là số cách đi từ ô khởi đầu đến ô (i , j). Vấn đề còn lại, chỉ là nhân ma trận để tìm ra kết quả bài toán.
