Độ khó: Khó (4/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Thầy Sơn có ~N~ học sinh đứng thành một hàng, học sinh thứ ~i~ (tính từ đầu hàng) có điểm năng lực ~a_i~. Thầy muốn chia cả hàng thành một số nhóm, mỗi nhóm gồm các học sinh đứng liên tiếp trong hàng, mỗi học sinh thuộc đúng một nhóm (không được đổi chỗ học sinh).

Mỗi nhóm cần một phòng học riêng nên tốn chi phí cố định ~C~. Ngoài ra, nhóm càng chênh lệch thì càng khó dạy: một nhóm có điểm lớn nhất là ~\max~ và điểm nhỏ nhất là ~\min~ tốn thêm chi phí ~\max - \min~. Như vậy chi phí của một nhóm là ~C + (\max - \min)~, và chi phí của cách chia là tổng chi phí các nhóm.

Hãy giúp thầy Sơn tìm cách chia có tổng chi phí nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~C~ ~(1 \le N \le 2 \times 10^5;\ 0 \le C \le 10^9)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(0 \le a_i \le 10^9)~.

Kết quả

Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N \le 5000~.
• Subtask 2 (~20\%~ số điểm): ~a_1 \le a_2 \le \dots \le a_N~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

5 3
1 5 1 2 8

Sample Output 1

10

Sample Input 2

9 5
1 3 2 20 21 20 5 4 6

Sample Output 2

20

Giải thích

• Ví dụ 1: chia thành ~[1, 5, 1, 2]~ và ~[8]~, chi phí ~(3 + 4) + (3 + 0) = 10~. Nếu để mỗi bạn một nhóm thì tốn ~5 \times 3 = 15~.
• Ví dụ 2: chia thành ~[1, 3, 2]~, ~[20, 21, 20]~, ~[5, 4, 6]~, chi phí ~(5 + 2) + (5 + 1) + (5 + 2) = 20~.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).

Độ khó: Khó (4/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Khu công nghệ có ~N~ trạm, đánh số từ ~1~ đến ~N~, được nối với nhau bằng ~N - 1~ tuyến cáp hai chiều sao cho giữa hai trạm bất kì luôn có đúng một đường đi (mạng có dạng cây). Tuyến cáp thứ ~i~ nối hai trạm ~u_i, v_i~ và có độ dài ~w_i~.

Ban đầu mọi trạm đều tắt. Thầy Sơn lần lượt thực hiện ~Q~ thao tác, mỗi thao tác cho một trạm ~x~: nếu trạm ~x~ đang tắt thì bật lên, nếu đang bật thì tắt đi.

Sau mỗi thao tác, các trạm đang bật cần trao đổi dữ liệu được với nhau. Thầy Sơn chỉ thuê một số tuyến cáp sao cho chỉ đi trên các tuyến đã thuê vẫn từ trạm đang bật bất kì tới được mọi trạm đang bật khác (được phép đi qua các trạm đang tắt). Hãy cho biết tổng độ dài nhỏ nhất của các tuyến cáp cần thuê. Nếu có không quá một trạm đang bật thì đáp án là ~0~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 2 \times 10^5)~.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 1 \le w_i \le 10^9)~ mô tả một tuyến cáp.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~ ~(1 \le x \le N)~ là trạm được bật/tắt.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là tổng độ dài nhỏ nhất của các tuyến cáp cần thuê sau thao tác thứ ~i~.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N, Q \le 2000~.
• Subtask 2 (~20\%~ số điểm): mỗi tuyến cáp nối hai trạm có số hiệu liên tiếp, tức là ~|u_i - v_i| = 1~ (mạng là một đường thẳng ~1 - 2 - \dots - N~).
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

5 7
1 2 3
1 3 2
3 4 4
3 5 1
2
4
5
1
4
2
3

Sample Output 1

0
9
10
10
6
3
3

Giải thích

Sau các thao tác, tập trạm đang bật lần lượt là ~\{2\}~, ~\{2, 4\}~, ~\{2, 4, 5\}~, ~\{1, 2, 4, 5\}~, ~\{1, 2, 5\}~, ~\{1, 5\}~, ~\{1, 3, 5\}~.

• Với ~\{2, 4\}~: thuê các tuyến ~2 - 1~, ~1 - 3~, ~3 - 4~, tổng ~3 + 2 + 4 = 9~.
• Với ~\{2, 4, 5\}~: thuê thêm tuyến ~3 - 5~, tổng ~10~. Bật thêm trạm ~1~ không cần thuê thêm tuyến nào.
• Với ~\{1, 2, 5\}~: các tuyến ~2 - 1~, ~1 - 3~, ~3 - 5~, tổng ~3 + 2 + 1 = 6~.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).

Độ khó: Khó (4/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Dọc một con sông có ~N~ làng, đánh số từ ~1~ đến ~N~ theo chiều nước chảy. Làng thứ ~i~ ở vị trí ~x_i~ (tính theo km từ đầu nguồn, ~x_1 < x_2 < \dots < x_N~) và sau vụ mùa có ~g_i~ tấn lúa.

Thầy Sơn cần xây không quá ~K~ kho lúa, mỗi kho đặt tại một làng, trong đó bắt buộc có một kho ở làng ~N~ (cửa sông). Thuyền chở lúa chỉ đi xuôi dòng, nên lúa của mỗi làng được chở tới kho gần nhất ở phía hạ lưu (kho tại chính làng đó hoặc kho đầu tiên nằm sau làng đó). Chở một tấn lúa đi ~1~ km tốn chi phí ~1~, nên lúa của làng ~i~ chở tới kho ở làng ~j~ ~(j \ge i)~ tốn ~g_i \times (x_j - x_i)~.

Hãy chọn vị trí các kho để tổng chi phí chở lúa của cả ~N~ làng là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~x_1, x_2, \dots, x_N~ ~(0 \le x_1 < x_2 < \dots < x_N \le 10^9)~.
• Dòng thứ ba chứa ~N~ số nguyên ~g_1, g_2, \dots, g_N~ ~(1 \le g_i \le 1000)~.

Kết quả

Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 300~.
• Subtask 2 (~30\%~ số điểm): ~K \le 20~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

5 2
0 2 3 7 10
3 1 2 2 5

Sample Output 1

16

Sample Input 2

6 3
1 4 5 9 12 20
2 2 1 5 1 3

Sample Output 2

18

Giải thích

• Ví dụ 1: đặt kho ở làng ~3~ (vị trí ~3~) và làng ~5~. Làng ~1, 2, 3~ chở về kho ở vị trí ~3~ tốn ~3 \times 3 + 1 \times 1 + 0 = 10~; làng ~4~ chở về làng ~5~ tốn ~2 \times 3 = 6~. Tổng ~16~.
• Ví dụ 2: đặt kho ở các làng ~2, 4, 6~ (vị trí ~4, 9, 20~): chi phí ~2 \times 3 + 1 \times 4 + 1 \times 8 = 18~.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).

Độ khó: Khó (4/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Mùa nước nổi về trên một vùng đồng bằng có ~N~ xã, đánh số từ ~1~ đến ~N~, nối với nhau bởi ~M~ con đường đất hai chiều. Con đường thứ ~i~ nối hai xã ~u_i, v_i~ và có cao độ ~h_i~. Khi mực nước là ~x~, những con đường có cao độ ~h_i \ge x~ vẫn còn đi được, những con đường có ~h_i < x~ thì bị ngập.

Mỗi xã nổi tiếng với đúng một loại đặc sản, xã thứ ~i~ có đặc sản loại ~c_i~ (nhiều xã có thể có cùng loại đặc sản).

Thầy Sơn muốn đi thu mua đặc sản để làm quà cho học trò. Thầy có ~Q~ câu hỏi, mỗi câu hỏi dạng: "Nếu thầy đang ở xã ~v~ và mực nước là ~x~, thì bằng cách chỉ đi trên các con đường chưa bị ngập, thầy có thể thu mua được bao nhiêu loại đặc sản khác nhau?" (kể cả đặc sản của chính xã ~v~; thầy được đi qua một xã hay một con đường nhiều lần).

Để tránh việc dự đoán trước, các câu hỏi có thể được mã hóa: tham số ~T~ cho biết điều này.

• Nếu ~T = 0~: câu hỏi thứ ~j~ cho trực tiếp hai số ~v, x~.
• Nếu ~T = 1~: câu hỏi thứ ~j~ cho hai số ~a, b~, khi đó ~v = a \oplus last~ và ~x = b \oplus last~, trong đó ~\oplus~ là phép XOR bit, ~last~ là đáp án của câu hỏi ngay trước đó (với câu hỏi đầu tiên, ~last = 0~).

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên ~N, M, Q, T~ ~(1 \le N \le 10^5;\ 0 \le M \le 2 \times 10^5;\ 1 \le Q \le 10^5;\ T \in \{0, 1\})~.
• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, \dots, c_N~ ~(1 \le c_i \le N)~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, h_i~ ~(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 1 \le h_i \le 10^9)~. Giữa hai xã có thể có nhiều con đường.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một câu hỏi như trên. Dữ liệu đảm bảo sau khi giải mã luôn có ~1 \le v \le N~ và ~1 \le x \le 10^9~.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~j~ là đáp án của câu hỏi thứ ~j~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N, M, Q \le 2000~.
• Subtask 2 (~30\%~ số điểm): ~T = 0~.
• Subtask 3 (~50\%~ số điểm): ~T = 1~, không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

6 6 4 0
1 2 1 3 2 3
1 2 5
2 3 3
3 4 7
4 5 2
5 6 6
1 3 4
1 4
5 3
4 8
6 2

Sample Output 1

3
2
1
3

Sample Input 2

6 6 4 1
1 2 1 3 2 3
1 2 5
2 3 3
3 4 7
4 5 2
5 6 6
1 3 4
1 4
6 0
6 10
7 3

Sample Output 2

3
2
1
3

Giải thích

• Ví dụ 1 (đặc sản loại ~1, 2, 3~ lần lượt là lúa, cá, sen):
  • Câu ~1~: mực nước ~4~, từ xã ~1~ đi được các xã ~1, 2, 3, 4~ (đường ~2 - 3~ cao độ ~3~ và đường ~4 - 5~ cao độ ~2~ đã ngập) nên mua được ~3~ loại.
  • Câu ~2~: mực nước ~3~, từ xã ~5~ chỉ đi được xã ~6~, mua được ~2~ loại.
  • Câu ~3~: mực nước ~8~, mọi đường đều ngập, chỉ mua được đặc sản của xã ~4~.
  • Câu ~4~: mực nước ~2~, đi được tất cả các xã, mua được ~3~ loại.
• Ví dụ 2 là ví dụ 1 sau khi mã hóa. Chẳng hạn câu thứ hai cho ~a = 6, b = 0~, đáp án câu trước là ~3~ nên ~v = 6 \oplus 3 = 5~, ~x = 0 \oplus 3 = 3~. Lưu ý các số ~a, b~ trong dữ liệu có thể nằm ngoài đoạn ~[1, N]~ hoặc bằng ~0~.

Nguồn: Đề tự luyện HSG Tin học quốc gia do thầy Nguyễn Việt Nam Sơn biên soạn (đề tự soạn).