Bài 4. Xóa xâu (HSG THPT TP. Hải Phòng 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT TP. Hải Phòng 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho xâu kí tự ~S~ có ~n~ kí tự chữ cái Latin viết in hoa ~'A' \ldots 'Z'~. Có ~q~ lệnh xóa kí tự, mỗi lệnh xóa thuộc một trong 2 loại sau đây:

• Loại 0: Xóa 1 kí tự đầu tiên (tính từ trái qua phải) có thứ tự từ điển nhỏ nhất của xâu còn lại.

• Loại 1: Xóa 1 kí tự đầu tiên (tính từ trái qua phải) có thứ tự từ điển lớn nhất của xâu còn lại.

Tìm xâu kí tự còn lại sau khi thực hiện tuần tự ~q~ lệnh xóa.

Dữ liệu vào

Gồm ba dòng:

  • Dòng 1: Chứa 2 số nguyên dương ~n, q (n \le 2 \times 10^5; q \le 10^5)~.
  • Dòng 2: Chứa xâu kí tự ~S~ chỉ có kí tự chữ cái Latin viết in hoa ~'A' \ldots 'Z'~.
  • Dòng 3: Chứa ~q~ số, mỗi số là 0 hoặc 1 tương ứng thể hiện loại lệnh xóa.

Kết quả

Một dòng duy nhất là xâu kí tự còn lại sau khi thực hiện tuần tự ~q~ lệnh xóa.

Ví dụ

Input 1

10 4
ADBAACDABC
0 1 1 0

Output 1

BACABC

Lần 1 (loại 0): ADBAACDABC → DBAACDABC (xóa ~A~ đầu tiên - nhỏ nhất). Lần 2 (loại 1): DBAACDABC → BAACDABC (xóa ~D~ đầu tiên - lớn nhất). Lần 3 (loại 1): BAACDABC → BAACABC (xóa ~D -~ lớn nhất). Lần 4 (loại 0): BAACABC → BACABC (xóa ~A~ đầu tiên - nhỏ nhất).

Ràng buộc

  • Subtask 1 (10% số điểm): ~q = 1~.
  • Subtask 2 (40% số điểm): ~n \le 10^4; q \le 10^3~.
  • Subtask 3 (50% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...