Tin học THPT

Mọi người ơi, em năm nay mới lớp 10. Kỳ thi học sinh giỏi cấp trường hình như diễn ra vào khoảng đầu năm 2027, các thầy cô ở lớp dặn là từ thời gian này đến trước khi thi vào đội tuyển của trường là phải tự ôn luyện rồi mới được vào đội tuyển của trường rồi mới đi thi cấp thành phố luôn ( em nghe nói năm nay thành phố Hà Nội là gộp chung vòng cấp phường với vòng cấp thành phố chung với nhau ). Còn nếu những quy định về thi mà em chưa biết thì anh/chị chỉ bảo giúp em. Em đã có nền tảng Toán tốt sẵn rồi ạ, còn Tin năm nay là mới bắt đầu học từ đầu hè thôi.Vậy em cần học và ôn những kiến thức, bài tập và dạng bài tập như thế nào để trúng tuyển ạ, mục tiêu của em là ít nhất vào được vòng cấp thành phố. Em rất mong nhận được sự giúp đỡ và lời khuyên của các anh chị ạ. Em cảm ơn rất nhiều.

Bài gợi ý: 3U1D
Tóm tắt: Bạn cần quản lý một dãy số có độ dài thay đổi. Có bốn loại thao tác: gán tất cả phần tử trong đoạn \([L; R]\) bằng \(X\), cộng cấp số cộng \(X, 2X, \dots\) vào đoạn \([L; R]\), chèn một số \(X\) vào vị trí \(C\), và tính tổng các phần tử trong đoạn \([L; R]\).

Xét mảng ban đầu gồm \(4\) phần tử: \([10, 20, 30, 40]\). Khi thực hiện thao tác loại \(2\) trên đoạn \([2; 4]\) với \(X = 5\), ta cộng lần lượt \(5, 10, 15\) vào các vị trí này. Mảng trở thành \([10, 25, 40, 55]\). Nếu tiếp tục chèn số \(99\) vào vị trí \(3\), dãy bị đẩy sang phải thành \([10, 25, 99, 40, 55]\).

Vì có thao tác chèn phần tử, các chỉ số trong mảng liên tục thay đổi. Mảng tĩnh hay cây phân đoạn (Segment Tree) thông thường sẽ mất \(O(N)\) cho mỗi lần chèn do phải dời chỗ các phần tử phía sau. Với \(N, Q \le 10^5\), tổng số thao tác có thể lên tới \(10^{10}\) phép tính và gây quá thời gian. Vậy ta cần cấu trúc dữ liệu nào vừa chèn được phần tử ở giữa, vừa cập nhật đoạn nhanh?

Cấu trúc phù hợp ở đây là cây tìm kiếm nhị phân ngẫu nhiên theo chỉ số ẩn (Implicit Treap). Trong cây này, mỗi nút đại diện cho một phần tử của dãy. Vị trí của một phần tử trong dãy được xác định tự động qua kích thước cây con bên trái sz(left) + 1. Nhờ đó, thao tác chèn một nút mới chỉ cần cắt cây làm đôi rồi ghép lại với hàm split(root, C - 1, L, R) và merge.

Mỗi nút trong cây cần lưu các thông tin: kích thước cây con sz, giá trị tại nút val, tổng cây con sum, và hai giá trị lười (lazy tags) đại diện cho phép gán và phép cộng cấp số cộng. Khi một cây con kích thước \(S\) nhận một cấp số cộng có số hạng đầu \(A\) và công sai \(D\), lượng tổng tăng thêm được tính qua công thức \(A \times S + D \times \frac{S \times (S - 1)}{2}\).

Khi đẩy giá trị lười xuống (push_down), con bên trái nhận cấp số cộng bắt đầu từ \(A\). Nút hiện tại nhận giá trị \(A + sz(left) \times D\). Con bên phải sẽ nhận cấp số cộng mới bắt đầu từ \(A + (sz(left) + 1) \times D\) với cùng công sai \(D\).

Checklist cài đặt:

• Hàm split(t, k, l, r): tách \(k\) phần tử đầu tiên sang cây \(l\), phần còn lại sang cây \(r\).
• Hàm push_down(u): ưu tiên gán đè trước, sau đó mới cộng dồn cấp số cộng \((A, D)\) cho hai nút con.
• Với mỗi truy vấn trên đoạn \([L; R]\): dùng split tách cây thành ba phần có độ dài \(L-1\), \(R-L+1\) và phần đuôi. Cập nhật hoặc lấy kết quả tại gốc cây ở giữa, sau đó merge cả ba phần lại theo đúng thứ tự.

Bài tập tương tự:

• CSES - Cut and Paste | Cắt và dán: Luyện thao tác cắt và ghép cây con bằng Treap chỉ số ẩn.
• CSES - Reversals and Sums | Đảo ngược và tính tổng: Luyện kỹ thuật đẩy nhãn lười (lazy propagation) và tính tổng đoạn trên Treap.

Để bắt đầu, hãy viết hàm split và merge cơ bản, sau đó bổ sung hàm push_down để quản lý hai nhãn lazy_set và lazy_add.

Bài gợi ý: CSES - Knuth Division | Phép chia Knuth
Tóm tắt: Bạn có một dãy gồm \(N\) số nguyên. Ở mỗi bước, bạn chọn một đoạn liên tiếp và tách thành hai đoạn con nhỏ hơn, chi phí bằng tổng các số trong đoạn đó. Nhiệm vụ là tìm tổng chi phí nhỏ nhất để tách toàn bộ mảng thành từng phần tử đơn lẻ.

Thay vì nghĩ theo chiều tách mảng lớn, ta có thể lật ngược bài toán thành thao tác gộp các đoạn kề nhau. Chẳng hạn với mảng ba số \([2, 7, 3]\), nếu bạn gộp \(7\) và \(3\) trước thì tốn chi phí \(7 + 3 = 10\). Sau đó bạn gộp số \(2\) với đoạn \([7, 3]\) vừa tạo, chi phí tốn thêm \(2 + 10 = 12\). Tổng chi phí của cách làm này là \(10 + 12 = 22\).

Để tìm chi phí nhỏ nhất, ta dùng quy hoạch động (DP - phương pháp giải bài toán lớn thông qua kết quả của các bài toán con nhỏ hơn). Gọi \(dp[i][j]\) là chi phí nhỏ nhất để gộp các phần tử từ vị trí \(i\) đến \(j\). Ta thử mọi vị trí cắt \(k\) nằm giữa \(i\) và \(j-1\) để chia đoạn thành \([i, k]\) và \([k+1, j]\). Công thức chuyển trạng thái là \(dp[i][j] = \min_{i \le k < j} (dp[i][k] + dp[k+1][j]) + \text{sum}(i, j)\), trong đó \(\text{sum}(i, j)\) là tổng các phần tử từ \(i\) đến \(j\).

Với giới hạn \(N \le 5000\), nếu duyệt mọi cặp \((i, j)\) rồi duyệt tiếp \(k\) từ \(i\) đến \(j\), số phép tính sẽ lên tới khoảng \(5000^3 / 6 \approx 2 \times 10^{10}\) thao tác. Cách làm này chắc chắn sẽ chạy quá thời gian cho phép. Ta cần một cơ chế để thu hẹp phạm vi duyệt của điểm cắt \(k\).

Gọi \(opt[i][j]\) là vị trí \(k\) tối ưu giúp \(dp[i][j]\) đạt giá trị nhỏ nhất. Điểm mấu chốt của bài toán là tính đơn điệu của điểm cắt: vị trí tối ưu \(opt[i][j]\) luôn bị kẹp giữa \(opt[i][j-1]\) và \(opt[i+1][j]\). Kỹ thuật này được gọi là tối ưu hóa Knuth. Nhờ đó, ta chỉ cần duyệt \(k\) trong đoạn \([opt[i][j-1], opt[i+1][j]]\), giúp giảm tổng độ phức tạp toàn bài xuống chỉ còn khoảng \(N^2 / 2 \approx 1.25 \times 10^7\) phép tính.

Các bước cài đặt chính:

• Dùng mảng tiền tố để tính nhanh \(\text{sum}(i, j) = \text{pref}[j] - \text{pref}[i-1]\).
• Khởi tạo cơ sở \(dp[i][i] = 0\) và \(opt[i][i] = i\) với mọi \(i\) từ \(1\) đến \(N\).
• Lặp độ dài đoạn \(\text{len}\) từ \(2\) đến \(N\), chọn đầu mút trái \(i\) và xác định đầu mút phải \(j = i + \text{len} - 1\).
• Cho \(k\) chạy trong khoảng từ \(opt[i][j-1]\) đến \(opt[i+1][j]\) để tìm giá trị nhỏ nhất cho \(dp[i][j]\), đồng thời lưu lại vị trí tối ưu vào \(opt[i][j]\).

Bài tập tương tự:

• SEQPART (IOI'14): Luyện tập kỹ thuật tối ưu hóa quy hoạch động trên các đoạn số và tối ưu chia để trị [cite: 1].

Bạn hãy khai báo mảng long long dp[5005][5005], mảng int opt[5005][5005], khởi tạo mảng cộng dồn tiền tố và in ra kết quả tại dp[1][n].

Bài gợi ý: Tree Robber

Tóm tắt: Cho một cây \(N\) đỉnh có trọng số \(a_i\). Bạn cần xử lý \(Q\) truy vấn gồm cập nhật trọng số một đỉnh và tìm tổng trọng số lớn nhất của một tập đỉnh không kề nhau trên đường đi đơn giữa hai đỉnh \(u, v\).

Xét ví dụ từ đề bài với đường đi giữa đỉnh \(3\) và \(5\) qua các đỉnh \(3 \to 2 \to 4 \to 5\). Dãy giá trị tương ứng là \(5, 1, 2, 4\). Để không chọn hai đỉnh kề nhau, ta có thể chọn đỉnh \(3\) và đỉnh \(5\), thu được tổng là \(5 + 4 = 9\). Đây là bài toán quen thuộc: chọn các phần tử không liền kề trên một dãy để tổng đạt lớn nhất.

Nếu gọi \(dp[0]\) là tổng lớn nhất khi không chọn đỉnh hiện tại và \(dp[1]\) là khi có chọn đỉnh đó, ta có công thức chuyển:
\(dp_{mới}[0] = \max(dp_{cũ}[0], dp_{cũ}[1])\)
\(dp_{mới}[1] = dp_{cũ}[0] + a_x\)

Với \(Q \le 2 \times 10^5\), nếu mỗi truy vấn đều duyệt lại đường đi từ \(u\) đến \(v\) để tính DP thì sẽ mất quá nhiều thời gian. Ta cần cách gộp nhanh kết quả của nhiều đỉnh liên tiếp mà không phải duyệt từng đỉnh một.

Quan sát thấy phép chuyển DP trên có thể biểu diễn qua phép nhân ma trận với phép cộng thay bằng lấy \(\max\):
\(C_{i, j} = \max_k (A_{i, k} + B_{k, j})\)
Mỗi đỉnh \(x\) tương ứng một ma trận kích thước \(2 \times 2\) là \(M_x = \begin{bmatrix} 0 & a_x \\ 0 & -\infty \end{bmatrix}\). Phép nhân này có tính kết hợp, giúp ta gộp đoạn đường đi thành tích các ma trận.

Để xử lý đường đi trên cây, ta dùng kỹ thuật phân rã chuỗi nặng nhẹ (HLD) kết hợp cây phân đoạn (Segment Tree). Kỹ thuật HLD chia cây thành các đoạn thẳng trên mảng, còn cây phân đoạn quản lý tích ma trận của từng đoạn. Khi cập nhật 1 x y, ta chỉ cần gán lại ma trận tại vị trí của đỉnh \(x\) trên Segment Tree bằng hàm update(pos, M).

Các bước chính khi cài đặt:

• Dùng duyệt cây theo chiều sâu (DFS - thuật toán đi sâu xuống các nhánh của cây trước khi quay lui) để tính kích thước cây con và tạo chuỗi nặng HLD.
• Dựng cây phân đoạn lưu tích ma trận \(2 \times 2\) cho từng nút.
• Khi truy vấn 2 u v, tách đường đi thành hai phần: từ \(u\) lên tổ tiên chung gần nhất và từ tổ tiên chung xuống \(v\).
• Nhân dồn các ma trận theo đúng thứ tự từ \(u\) đến \(v\), bắt đầu từ vector \([0, -\infty]\).

Cuối cùng, lấy \(\max\) giữa \(dp[0]\), \(dp[1]\) và \(0\) để in ra đáp án cho mỗi truy vấn loại 2.