Đề thi tin học a quốc gia

Đề thi ngày 1: PDF.

Link nộp bài: VOI2020. Các bạn cần vào group: VNOI - Vietnam Olympiad in Informatics ở codeforces trước nếu không vào được link contest.

Với các bài, nếu đề quá dài mình sẽ tóm tắt lại đại ý trước khi đi vào lời giải. Mình sẽ chủ yếu đi vào lời giải cho sub cuối cùng, nhưng sẽ nói sơ qua các cách vét điểm.

Bài 1: BONUS

Lời giải

Với \[k\] khá nhỏ, ta hoàn toàn có thể backtrack cách chọn, độ phức tạp: \[O[5^k]\]. Cách code có thể đơn giản như sau:

//hàm calc[l, r, k] trả về giá trị tối ưu khi ta xử lý đoạn con [l, r] và còn lại k lượt chọn. Kết quả là calc[1, n, k] //hàm cost[x, y] trả về giá trị khi chọn cặp 2 lá bài x và y, đơn giản nó là abs[a[x] - a[y]] long long calc[int l, int r, int k] { if [l > r] { if [k == 0] return 0; //vì đề yêu cầu chọn ĐÚNG k cặp, nên nếu vẫn còn cách chọn thì trạng thái này không thỏa mãn //do đó ta return 1 giá trị cực bé để không bao giờ lấy kết quả này. return -INF; } long long best = -INF; if [l + 1