ỨNG DỤNG STACK ĐỂ GIẢI MỘT SỐ BÀI TOÁN ÔN THI HSG

Việc bồi dưỡng học sinh giỏi tin học, tạo nguồn sinh viên giỏi và đáp ứng yêu cầu
đào tạo nhân lực chất lượng cao của xã hội là một việc cực kỳ cấp bách trong giai đoạn
hiện nay. Vì vậy cùng với các trường chuyên trong vùng chúng tôi luôn trăn trở làm thế
nào để nâng cao chất lượng dạy tin học nhất là đối với chương trình chuyên. Điều đó
thôi thúc đội ngũ giáo viên chuyên phải tìm tòi, nghiên cứu và sáng tạo.
Trong chương trình ôn luyện và bồi dưỡng học sinh giỏi, vấn đề sử dụng cấu trúc
dữ liệu đặc biệt để giải các bài là một trong những vấn đề rất hay nhưng cũng rất khó.
Hiện nay, phổ biến rất nhiều loại cấu trúc dữ liệu khác nhau như:
- STACK – ngăn xếp
- QUEUE – hàng đợi
- HASH TABLE – bảng băm
- HEAP – Đống
- BINARY SEARCH TREE – Cây tìm kiếm nhị phân
- SEGMENT TREE – Cây phân đoạn (thường gọi là INTERVAL TREE)
- BINARY INDEXED TREE – Cây nhị phân được lập chỉ mục
-…
Trong bài viết này, tôi không có ý định sử dụng hết các cấu trúc dữ liệu đặc biệt
trên để giải các bài toán, mà chỉ đi sâu vào một cấu trúc dữ liệu đơn giản nhưng nếu biết
sử dụng nó thì sẽ giải quyết rất hiệu quả một số bài toán – Cấu trú dữ liệu STACK.
Về định nghĩa và các thao tác sử dụng của STACK thì ai cũng biết tôi không trình
bày lại, trong bài viết này tôi sẽ trình bày giải một số bài toán có liên quan tới việc sử
dụng cấu trúc dữ liệu đặc biệt này.
1


Bài 1. Chiến trường Ô qua – Nguồn bài: vn.spoj.com
Lại nói về Lục Vân Tiên, sau khi vượt qua vòng loại để trở thành Tráng Sỹ, anh
đã gặp được Đôrêmon và được chú mèo máy cho đi quá giang về thế kỷ 19. Trở lại quê
hương sau nhiều năm xa cách, với tấm bằng Tráng Sỹ hạng 1 do Liên Đoàn Type Thuật


2
4
3431
4
1213

913
414

 Hướng dẫn thuật toán:
Xin tóm tắt lại đề bài như sau:
Trong tất cả các đoạn phần tử liên tiếp, hãy chọn ra đoạn [i … j] sao cho tích:
min{A[i],…,A[j]} * (j – i + 1) đạt giá trị lớn nhất.
- Với đặc điểm của bài toán, rõ ràng với phần tử A[i] ta sẽ phải tìm hai chỉ số j và k
(trong đó A[j] phía trước A[i] và A[k] phía sau A[i]) sao cho A[j] gần với A[i] nhất
và A[j] < A[i], A[k] gần với A[i] nhất và A[k] < A[i]. Từ đó cập nhật giá trị lớn
nhất vơi A[i] * (k – j – 1).
- Để tìm A[j] ta có thể duyệt từ A[i] ngược về 1, để tìm A[k] ta sẽ duyệt từ A[i] tiếp
tục đến N, tuy nhiên cách này sẽ bị lỗi quá thời gian. Ta có thể sử dụng STACK để
làm giảm thời gian tìm kiếm A[j] và A[k]:
+ Gọi L[i] là chỉ số của phần tử A[L[i]] sao cho L[i] < i và L[i] gần với i nhất để
A[L[i]]


Hãy giúp anh ấy cưa được tấm biển lớn nhất có thể.
Input
• Dòng thứ nhất: ghi số nguyên N - số tấm ván.
• N dòng tiếp theo: mô tả độ cao của các tấm ván theo thứ tự trái sang phải sau
khi đã dán lại.
Output
• Một số nguyên duy nhất là độ dài cạnh của tấm biển lớn nhất có thể cưa được.
Giới hạn
•
•
•
•

Độ cao của các tấm ván là các số nguyên dương không vượt quá 109.
1 ≤ N ≤ 106.
60% số test có 1 ≤ N ≤ 2000.
80% số test có 1 ≤ N ≤ 105.

Ví dụ:
Input
7
5243314

Output
9

Giải thích: Hình dưới đây minh họa phương án tối ưu.


* Hướng dẫn thuật toán:
Xét một mái nhà có độ cao các phần như hình dưới:
11
7
3
6

15
8

13

5

1
2

10

4

9

6

12
14

16


được
• Dòng 3: Ghi chỉ số hàng và chỉ số cột của ô ở góc dưới phải của hình chữ nhật
tìm được
Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu
cách.
Ví dụ:

* Hướng dẫn thuật toán.
Cách giải tương tự cách giải của bài 1 – “Chiến trường Ô qua”
Bài 5. Xếp hàng
Có tất cả N người xếp hàng. Hai người A và B sẽ nhìn thấy nhau nếu giữa 2 người
không có người nào cao hơn người A hoặc B.
Bạn hãy xác định số cặp người có thể nhìn thấy nhau.
Dữ liệu:
• Dòng 1: Một số nguyên duy nhất N (1≤N≤500.000) là số người đứng xếp hàng.
• Dòng 2..N+1: Mỗi dòng là chiều cao của một người đứng xếp hàng theo thứ tự từ
đầu hàng tới cuối hàng. Chiều cao một người không quá 231.

8


Kết quả:
• Một số nguyên duy nhất là số cặp người xếp hàng có thể nhìn thấy nhau.
Ví dụ:
Input
7
2
4
1
2

Người ở vị trí thứ 6 có thể nhìn thấy người ở vị trí thứ 2,4,5,7.

-

Người ở vị trí thứ 7 có thể nhìn thấy người ở vị trí thứ 6

=> Có tất cả 10 cặp người có thể nhìn thấy nhau.
* Hướng dẫn thuật toán
Xét người ở vị trí i, giả sử cần xét xem người thứ i sẽ nhìn thấy những ai phía trước.
Xét người ở vị trí j < i:
- Nếu j là người cao hơn tất cả những người đứng trước j => người i sẽ không nhìn thấy
những người trước j.

9


- Nếu j không cao hơn tất cả những người đứng trước j => sẽ tồn tại người đứng trước j
và cao nhất từ vị trí 1 -> i – 1 và người i sẽ nhìn thấy người này, và không nhìn thấy
những người đứng trước người đó.
Nhận xét: thấy ngay rằng nếu một người j cao nhất từ 1 -> j thì những người sau j sẽ
không nhìn thấy tất cả mọi người trước j.
Từ nhận xét trên ta hình thành cách giải bài toán bằng cấu trúc dữ liệu STACK như sau:
STACK có nhiệm vụ lưu lại chỉ số của dãy người. Sau đó, luôn duy trì STACK ở trạng
thái giảm dần theo chiều cao của mỗi người từ đáy lên đỉnh.
Xét phần tử A[i]:
- Nếu A[i] < A[STACK[top]] thì nạp i vào STACK và kq = kq + 1
- Nếu A[i] = A[STACK[top]] thì đếm tần số xuất hiện của A[i] và tính kq
- Nếu A[i] > A[STACK[top]] thì loại các phần tử ở đỉnh STACK cho đến khi A[i]
Kết quả: Đưa ra file văn bản FROGS.OUT một dòng chứa n số nguyên – độ cao nơi ở
mới của mỗi chú ếch.
Ví dụ:
FROGS.INP

FROGS.OUT
4 5 5 -1 -1 8 8 -1

8
31456238
* Hướng dẫn thuật toán:

Nhận xét: Nếu hai con ếch ở hai vị trí i, j (i < j) cùng nhảy đến vị trí k sau x bước thì
H[i] > H[j], khi đến vị trí k rồi ta sẽ ko quan tâm đến vị trí i, j ban đầu của chúng nữa.

11


Khi đó ta sẽ luôn duy trì một STACK1 (lưu chỉ số của các con ếch) ở trạng thái tăng
dần về độ cao của các bãi rác từ dưới đáy lên trên đỉnh.
Xét tại vị trí bãi rác thứ i: cần tìm phía trước i có những con ếch nào (chưa nhảy hết
bước nhảy của nó) mà có thể nhảy được đến i. Để làm việc này ta sử dụng STACK2 để
lưu lại vị trí của các con ếch chưa nhảy hết các bước nhảy của nó.
Xét bãi rác thứ i:
- Nếu H[i] > H[STACK2[top2]] {nghĩa là vị trí i có độ cao lớn hơn những vị trí của
những con ếch chưa hoàn thành bước nhảy của nó} thì tăng số bước nhảy của mỗi con
ếch này và loại bỏ khỏi ra khỏi STACK2 những con ếch đã hoàn thành số bước nhảy
của nó.
- Nếu H[i]