Hướng dẫn giải của Trò Chơi Bài (Platinum)

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Trò Chơi Bài Hai Luật

Hướng tiếp cận

Bài toán yêu cầu tìm điểm tối đa khi người A có thể đổi từ "bài cao thắng" sang "bài thấp thắng" đúng một lần ở bất kỳ vòng nào.

Gọi điểm đổi luật là sau vòng $i$ (với $0 \leq i \leq N$ , $i = 0$ nghĩa là đổi luật ngay từ đầu). Khi đó:

$N$ vòng đầu (vòng 1 đến $i$ ): luật "bài cao thắng".
$N - i$ vòng sau (vòng $i + 1$ đến $N$ ): luật "bài thấp thắng".

Đáp án = ${max}_{0 \leq i \leq N} (prefix [i] + suffix [i])$

trong đó:

$prefix [i]$ = số điểm tối đa người A giành được trong $i$ vòng đầu với luật "bài cao thắng", dùng $i$ lá bài cao nhất của mình.
$suffix [i]$ = số điểm tối đa người A giành được trong $N - i$ vòng cuối với luật "bài thấp thắng", dùng $N - i$ lá bài thấp nhất của mình.

Nhận xét quan trọng

Phân chia bài tối ưu: Trong đoạn "bài cao thắng", người A nên dùng $i$ lá bài lớn nhất; trong đoạn "bài thấp thắng", nên dùng $N - i$ lá bài nhỏ nhất. Đây là vì không có lý gì dùng một lá bài nhỏ để cố đánh bại ở đoạn cao-thắng khi đã có bài lớn hơn.
Tính prefix: Với $i$ vòng đầu (người B đánh $a_{1}, a_{2}, \dots, a_{i}$ ) và $i$ lá bài lớn nhất của người A, dùng chiến lược tham lam: dùng lá bài nhỏ nhất lớn hơn lá của B (nếu có).
Tính suffix: Với $N - i$ vòng cuối (người B đánh $a_{i + 1}, \dots, a_{N}$ theo thứ tự ngược) và $N - i$ lá bài nhỏ nhất của người A (theo thứ tự ngược), dùng chiến lược đối xứng.

Thuật toán

Để tính $prefix []$ và $suffix []$ hiệu quả, ta dùng Segment Tree trên không gian lá bài $[1 . .2 N]$ .

Cấu trúc nút Segment Tree:

covers: số lá bài của người A trong đoạn này chưa được sử dụng (lá bài có thể "che" bài của B).
coverables: số lá bài của người B trong đoạn này chưa được "che".
points: số điểm đã ghi nhận trong đoạn này.

Kết hợp hai nút (trái $x$ , phải $y$ ):

ep = min(x.coverables, y.covers)   // bài B phía trái được che bởi bài A phía phải
points = x.points + y.points + ep
covers = x.covers + y.covers - ep
coverables = x.coverables + y.coverables - ep

Tính prefix[i]:

Lấy $i$ lá bài lớn nhất của người A (đây là những lá bài không thuộc dãy B, theo thứ tự giảm dần).
Với $j = 1, 2, \dots, N$ : chèn lá bài $B [j]$ vào vị trí tương ứng trong segment tree (gắn coverables = 1), đồng thời chèn lá bài lớn thứ $j$ của người A (gắn covers = 1). Sau mỗi bước, $prefix [j] = root.points$ .

Tính suffix[i]: Làm tương tự nhưng theo chiều ngược (vòng cuối trước, luật thấp thắng). Đổi biến: thay mỗi lá bài $v$ bằng $2 N + 1 - v$ để quy về bài "thấp thắng" thành "cao thắng". Dùng lá bài nhỏ nhất của người A, xử lý từ vòng $N$ ngược về $1$ .

Kết quả: ${max}_{i = 0}^{N} (prefix [i] + suffix [N - i])$

Độ phức tạp

Thời gian: $O (N \log N)$ — mỗi thao tác chèn vào segment tree mất $O (\log N)$ , thực hiện $O (N)$ lần cho cả prefix và suffix.
Bộ nhớ: $O (N)$ .

Bình luận

Không có bình luận tại thời điểm này.