Lời Giải Một Số Bài Toán Contest Khai Xuân 2026
posted on March 22, 2026, 4:04 p.m.Tam Giác Pháo Hoa
Cho dãy độ dài các que pháo, ta cần chọn 3 que để tạo thành tam giác và phân loại.
Điều kiện tạo tam giác với ~(a \le b \le c): a + b > c~
Điều kiện phân loại tam giác
- Tam giác nhọn: ~(a^2 + b^2 > c^2)~
- Tam giác vuông: ~(a^2 + b^2 = c^2)~
- Tam giác tù: ~(a^2 + b^2 < c^2)~
Như vậy, với các nhận xét trên ta chỉ cần sắp xếp mảng tăng dần. Tạo mảng ~b_i = a_i^2~, sau đấy ta sẽ for duyệt các cặp cạnh ~(i, j)~ với ~i < j~ và sẽ đi tìm cạnh ~k~ ~(j < k)~ còn lại:
- Với tam giác nhọn: tìm vị trí đầu tiên ~idx~ sao cho ~b[idx] \ge b[i] + b[j]~ các ~k \in (j+1, idx-1) ~ là tam giác nhọn
- Với tam giác vuông: ta chỉ cần xét có tồn tại ~k~ mà ~b[k] = b[i] + b[j]~
- Với tam giác tù: tìm vị trí đầu tiên ~idx1~ sao cho ~b[k] > b[i] + b[j]~ và vị trí đầu tiên ~idx2~ sao cho ~(a[k] \ge a[i] + a[j])~ các ~k \in (idx1, idx2 - 1)~ là tam giác tù
Để tìm ~k~ được nhanh chóng ta có thể dùng kỹ thuật tìm kiếm nhị phân.
Độ phức tạp của lời giải trên: ~O(NlogN)~
Code mẫu tham khảo: Link
Di Chuyển Quân Tượng
Quân Tượng chỉ di chuyển trên các đường chéo của bàn cờ.
Điều kiện để quân Tượng có thể đi từ ~(R_1, C_1)~ đến ~(R_2, C_2)~: ~2~ ô phải cùng màu, tức là: ~(R_1 + C_1) \% 2 = (R_2 + C_2) \% 2~
- Nếu không thỏa mãn → không thể đi → in ~-1~
- Nếu hai vị trí trùng nhau: ~(R_1 = R_2)~ và ~(C_1 = C_2)~ → không cần di chuyển → in ~0~
- Nếu hai ô nằm trên cùng một đường chéo: ~|R_1 - R_2| = |C_1 - C_2|~ → đi được trong ~1~ bước
- Nếu cùng màu nhưng không cùng đường chéo → luôn đi được trong ~2~ bước
Độ phức tạp của lời giải trên: ~O(1)~
Code mẫu tham khảo: Link
Tham Quan Khu Nhà Của BQ
Ta cần tìm đường đi ngắn nhất để đi qua tất cả các căn nhà (nhóm các ô 'X').
Bài toán gồm 3 bước chính:
- Gom các ô 'X' thành từng căn nhà
- Tính khoảng cách giữa các căn nhà
- Giải bài toán đi qua tất cả các căn nhà (bài toán TSP)
Bước 1: Gom nhóm các căn nhà
- Dùng DFS/BFS để gom các ô 'X' liên thông thành một nhóm
- Mỗi nhóm tương ứng với một căn nhà
- Gán id từ ~0 → N-1~
Bước 2: Tính khoảng cách giữa các căn nhà
Với mỗi căn nhà ~i~:
- Chạy BFS từ một ô bất kỳ của căn nhà ~i~
- Gọi ~dist[i][j]~ là khoảng cách ngắn nhất giữa căn nhà i và j
Bước 3: Quy hoạch động bitmask (TSP)
Gọi ~f[i][mask]~ là chi phí nhỏ nhất để:
- đã thăm các căn nhà trong ~mask~
- và hiện tại đang đứng ở căn nhà thứ ~i~
Trạng thái khởi tạo: ~f[i][1 << i] = 0~
Công thức chuyển trạng thái:
- Từ ~(i, mask)~ sang ~(j, mask | (1 << j))~: ~f[j][mask | (1 << j)] = \min(f[j][mask | (1 << j)],\ f[i][mask] + dist[i][j])~
Đáp án là: ~\min(f[i][(1 << N) - 1])~. Nếu không tồn tại đường đi nào → in ~-1~
Độ phức tạp
- Gom nhóm: ~O(R \cdot C)~
- BFS mỗi căn: ~O(N \cdot R \cdot C)~
- DP bitmask: ~O(N^2 \cdot 2^N)~
Code mẫu tham khảo: Link
Rút Bài Đầu Xuân
- Khoảng cách tối đa giữa ~2~ số nguyên tốt nhỏ hơn ~2 \cdot 10^9~ là không quá ~500~.
- XOR hoạt động theo từng bit độc lập
- Như vậy, giả sử bit thứ ~i~ của ~N~ đang bật ta chỉ việc tìm số nguyên tố ~p~ nhỏ nhất cũng có bit thứ ~i~ đang bật, khi XOR với số ~p~ thì ta chắc chắn sẽ bật được bit thứ ~i~ của ~N~. Thực hiện việc này từ bit thứ ~i~ lớn nhất XOR dần về các bit nhỏ nhất ta sẽ xây dựng lại được ~N~.
- Lưu ý, sẽ có trường hợp đặc biệt khi ~N = 1~, ta sẽ XOR cho ~2~ số nguyên tố là ~2~ và ~3~.
Độ phức tạp của lời giải trên:
- Tiền xử lý tìm các số nguyên tố ~p~ cho mỗi bit ~i~: ~O(30 * 500 * sqrt(N))~
- Với mỗi testcase: ~O(30)~
Code mẫu tham khảo: Link
Trang Trí Đèn Năm Mới
Gọi ~b[i][j]~ là tổng số ô bật trong hình vuông ~2 \times 2~ có góc trái trên tại ~(i, j)~. Tính chất quan trọng
- Khi đảo một hàng hoặc một cột:
- Trạng thái từng ô thay đổi
- Nhưng tính chẵn lẻ của ~b[i][j]~ không đổi
Với truy vấn ~(x1, y1, x2, y2)~: Nếu tồn tại ô ~b[i][j]~ lẻ với: ~x1 \le i < x2,\ y1 \le j < y2~ → Không thể biến toàn bộ thành bật → in ~NO~
Ngược lại, nếu tất cả ~b[i][j]~ đều chẵn, luôn có thể biến đổi được với ý tưởng:
- Dùng phép đảo hàng để chuẩn hóa cột đầu
- Sau đó các cột còn lại sẽ đồng nhất
- Dùng phép đảo cột để hoàn tất
Độ phức tạp của lời giải trên:
- Tiền xử lý: ~O(N \cdot M)~
- Mỗi truy vấn: ~O(1)~
Code mẫu tham khảo: Link
