Tài liệu Bồi dưỡng học sinh giỏi môn tin học chuyên đề ứng dụng stack để giải một số bài toán ôn thi học sinh giỏi

  • Số trang: 12 |
  • Loại file: PDF |
  • Lượt xem: 1685 |
  • Lượt tải: 0

Mô tả:

Ứ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 cấp, anh đã được Đức Vua cử làm đại tướng thống lãnh 3 quân chống lại giặc Ô Qua xâm lăng. Đoàn quân của anh sẽ gồm N đại đội, đại đội i có A[i] (A[i] > 0) người. Quân sỹ trong 1 đại đội sẽ đứng thành 1 cột từ người 1 -> người A[i] , như vậy binh sỹ sẽ đứng thành N cột. Vì Vân Tiên quyết 1 trận sẽ đánh bại quân Ô Qua nên đã cử ra 1 quân đoàn hùng mạnh nhất. Trong sử cũ chép rằng, quân đoàn của Vân Tiên cử ra lúc đó là một nhóm các đại đội có chỉ số liên tiếp nhau (tức là đại đội i , i + 1 , … j) - Vì sử sách thì mối mọt hết cả nên chỉ biết được mỗi thế. Ngoài ra theo giang hồ đồn đại thì sức mạnh của 1 quân đoàn = số người của đại đội ít người nhất * số đại đội được chọn. Nhiệm vụ của bạn là dựa trên các thông số của các nhà khảo cổ có được , hãy cho biết quân đoàn mà Vân Tiên đã chọn ra là từ đại đội nào đến đại đội nào. Chú ý nếu có nhiều phương án thì ghi ra phương án mà chỉ số của đại đội đầu tiên được chọn là nhỏ nhất . Input  Dòng 1 : Số T là số bộ test .  T nhóm dòng tiếp theo , mỗi nhóm dòng mô tả 1 bộ test . Nhóm dòng thứ i : o Dòng 1: N (N <= 30000) o Dòng 2: N số nguyên mô tả N số A[1], A[2], … A[N] (các số nguyên dương <= 30000). . Output  Kết quả mỗi test ghi ra trên 1 dòng, gồm 3 số: sức mạnh quân đoàn mạnh nhất, chỉ số của đại đội đầu tiên và chỉ số của đại đội cuối cùng được chọn. 2 Ví dụ: Input Output 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]] <= A[i]. Với ví dụ: A ={ 3 4 3 1} thì mảng L = {0,1,0,0} Sử dụng STACK để lưu lại các chỉ số của các phần tử trong dãy sao cho luôn duy trì STACK ở trạng thái A[STACK[i]] tăng dần tử đáy lên trên. Xét A[i]: so sánh A[i] với phần tử A[STACK[top]] (trong đó top là phần tử ở đỉnh của STACK). - Nếu A[i] > A[STACK[top]] thì bổ sung i vào STACK và L[i] = STACK[top] - Nếu A[i] <= A[STACK[top]] thì loại dần các phần tử ở đỉnh STACK cho đến khi A[i] > A[STACK[top]]. Lúc đó gán L[i] = STACK[top] 3 + Tương tự gọi R[i] là chỉ số của phần tử A[R[i]] sao cho i < R[i] và R[i] gần với i nhất để A[R[i]] < A[i]. Cách tìm mảng R tương tự như với việc tìm mảng L nhưng theo chiều ngược lại. KQ cuối cùng = max{A[i] * (R[i] – L[i] + 1)} Bài 2. Bán dừa – Nguồn bài: vn.spoj.com Nếu các bạn biết câu chuyện thương tâm "ăn dưa leo trả vàng" của Pirate hẳn đã phải khóc hết nước mắt khi anh ấy, vì lòng thương chim, đã bán rẻ trái dưa leo siêu bự của mình. Dưa leo cũng đã bị chim to lấy đi rồi, Pirate giờ chuyển sang nghề bán dừa để bù lỗ. Bất đắc dĩ thôi, vì trên đảo toàn là dừa... Nhưng mà bán cái gì thì đầu tiên cũng phải có biển hiệu đã. Pirate quyết định lùng sục trên đảo các mảnh ván còn sót lại của những con tàu đắm để ghép lại thành tấm biển. Cuối cùng anh cũng tìm được N tấm ván hình chữ nhật, tấm thứ i có chiều rộng là 1 đơn vị và chiều dài là ai đơn vị. Pirate dựng đứng chúng trên mặt đất và dán lại với nhau để được một mảnh ván to hơn (xem hình minh họa). Việc cuối cùng chỉ là đem mảnh ván này đi cưa thành tấm biển thôi. Nhưng hóa ra đây lại là công việc khó khăn nhất. Pirate rất thích hình vuông và muốn tấm biển của mình càng to càng tốt, nhưng khổ nỗi trên đảo lại không có nhiều dụng cụ đo đạc. Không êke, không thước đo độ, nên Pirate chỉ còn cách dựa vào cạnh của N tấm ván ban đầu để cưa cho thẳng thôi. Pirate chỉ có thể cưa theo những đoạn thẳng chứa một cạnh nào đó (dọc hoặc ngang) của các tấm ván. 4 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: Bài toán giống bài toán “Chiến trường Ô qua” ở trên. Bài 3. Đọng nước – Nguồn bài: vn.spoj.com 5 Năm 2011, tình trạng ngập lụt trong thành phố trở lên nghiêm trọng hơn. Vì vậy, mọi người quyết định xây dựng hệ thống mái che cho toàn thành phố. Mái che có bề rộng là N, được chia làm N phần có độ dài như nhau. Độ cao của mỗi phần là h1, h2, ..., hn. Khi trời mưa, một phần nước sẽ đọng lại trên mái và một phần sẽ thoát ra ngoài theo hai bên trái và phải của mái che. Do đó, thành phố sẽ không phải chịu cảnh mưa lụt như trước. Nhằm mục đích bảo trì mái che, bạn cần viết chương trình tính lượng nước lớn nhất có thể đọng lại trên mái che. Input  Dòng đầu ghi số N. (1 <= N <= 100000)  Dòng sau ghi N số tự nhiên h1, h2, ..., hn. (1 <= hi <= 100000) Output  Gồm một số duy nhất thể hiện lượng nước tìm được. Giới hạn  50% số test có N <= 1000. Ví dụ Input 5 13123 Output 3 * 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 1 13 10 5 2 9 4 6 12 14 16 Phần ở vị trí 11 cao nhất nên mực nước đọng sẽ không thể vượt qua được cột này. Từ đó chia thành 2 thành phần, bên trái cột 11 và bên phải cột 11. Lượng nước đọng sẽ nằm trong các khe của các cột sau: {1 3 7 11}, {16 15 11}, các cột này luôn ở trạng thái tăng dần về độ cao cho đến cột cao nhất. Như vậy cần duy trì một STACK lưu lại chỉ số các cột sao cho A[STACK[i]] tăng dần từ đáy lên đến đỉnh stack. Và lượng nước đọng sẽ nằm trong khe của các cột liên tiếp thuộc STACK. Bài 4. Hình chữ nhật lớn nhất Cho một bảng hình chữ nhật kích thước m x n được chia thành lưới ô vuông đơn vị m hàng, n cột. Các hàng được đánh số từ 1 tới m theo thứ tự từ trên xuống dưới và các cột được đánh số từ 1 tới n theo thứ tự từ trái qua phải. Người ta tiến hành tô màu các ô của bảng theo từng cột: Các ô trên mỗi cột j sẽ được tô từ trên xuống dưới: hj ô màu vàng tiếp đến là m – hj ô màu xanh. Như vậy tình trạng màu trên bảng hoàn toàn xác định nếu ta biết được số hàng m, số cột n và các số nguyên h1, h2, …, hn. Hãy xác định một hình chữ nhật gồm các ô trong bảng đã cho thỏa mãn các yêu cầu sau:  Có cạnh song song với cạnh bảng  Đơn sắc (chỉ gồm các ô vàng hoặc chỉ gồm các ô xanh)  Diện tích lớn nhất có thể 7 Dữ liệu: Vào từ file văn bản RECT.INP  Dòng 1: Chứa hai số nguyên dương m, n (m, n <= 106)  Dòng 2: Chứa n số nguyên h1, h2, …, hn (0 <= hj <= m) Kết quả: Ghi ra file văn bản RECT.OUT  Dòng 1: Ghi diện tích hình chữ nhật tìm được  Dòng 2: Ghi chỉ số hàng và chỉ số cột của ô ở góc trên trái của hình chữ nhật tìm đượ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. 8  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. 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 2 5 1 Output 10 Giải thích ví dụ: - Người ở vị trí thứ 1 có thể nhìn thấy người ở vị trí thứ 2 - Người ở vị trí thứ 2 có thể nhìn thấy người ở vị trí thứ 1,3,4,5,6 - Người ở vị trí thứ 3 có thể nhìn thấy người ở vị trí thứ 2,4 - Người ở vị trí thứ 4 có thể nhìn thấy người ở vị trí thứ 2,3,5,6 - Người ở vị trí thứ 5 có thể nhìn thấy người ở vị trí thứ 2,4,6. - 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: 9 - 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. - 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] <= A[STACK[TOP]], trong quá trình loại các phần tử ở đỉnh STACK thì tăng kq Bài 6. Ếch đột biến gien Cuộc sống an nhàn với thức ăn đầy đủ và đa dạng tại các đống rác thành phố đã sinh ra thế hệ các chú ếch đột biến gen. Trên con đường dẫn đến bải rác thành phố có n đống rác, đánh số bắt đầu từ 0 đến n-1 từ trái qua phải. Đống rác thứ i có độ cao hi (i = 0 ÷ n1, 0 < hi ≤ 109, 0 < n ≤ 106, hi – nguyên). Trên mỗi đống rác hiện có một chú ếch sống. Đến tuổi trưởng thành, mỗi chú ếch đều muốn đi tìm một nơi sống tốt đẹp hơn bằng cách nhảy sang đống rác cao hơn gần nhất bên phải. Chú ếch ở đống rác thứ i có thể thực hiện đươc Ji bước nhảy (0 < Ji < n). Bãi rác thành phố có độ cao lớn hơn mọi đống rác trên đường. Ta ký hiệu độ cao này là -1 (vì không cần và cũng không thể biết chính xác). 10 Ví dụ: có 8 đống rác với độ cao tương ứng từ trái sang phải là 3, 1, 4, 5, 6, 2, 3 và 8. Số bước nhảy mỗi chú ếch có thể thực hiện là 1, 2, 1, 3, 4, 2, 1, 2. Sau khi di chuyển hết khả năng của mình, chú ếch ở đống rác 0 sẽ tới được đống rác 2 với độ cao là 4, còn chú ếch ở đống rác 3 – tới được bải rác thành phố (độ cao -1). Yêu cầu: Hãy xác định độ cao nơi ở mới của mỗi chú ếch. Dữ liệu: Vào từ file văn bản FROGS.INP: • Dòng đầu tiên chứa số nguyên n, • Dòng thứ 2 chứa n số nguyên h0, h1, …, hn-1, • Dòng thứ 3 chứa n số nguyên J0, J1, …, Jn-1. 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 3 1 4 5 623 8 1 2 1 3 421 2 * 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] <= H[STACK1[top1]] {nghĩa là con ếch ở vị trí STACK1[top1] không thể nhảy đến vị trí i} thì đẩy i vào STACK1. - Nếu H[i] > H[STACK1[top1]] {nghĩa là con ếch ở vị trí STACK1[top1] có thể nhảy đến bãi rác i} khi đó sẽ loại bỏ các vị trí ở đỉnh STACK1. Trong quá trình loại bỏ sẽ tăng số bước nhảy của con ếch ở vị trí STACK1[top1] lên 1 đơn vị và gán lại độ cao mới của con ếch ở vị trí STACK1[top1] là vị trí H[i], và xem xét nó đã hoàn thành số bước nhảy chưa: + Nếu đã hoàn thành thì vị trí mới của con ếch ở vị trí STACK1[top1] chính là vị trí i, tức là gán H[STACK1[top1]] = H[i]. + Nếu chưa hoàn thành thì đẩy vị trí của con ếch ở STACK1[top1] sang STACK2. Sau khi xét hết các vị trí của con ếch mà con nào chưa hoàn thành nhiệm vụ nhảy thì đưa ra -1, còn lại đưa ra vị trí mới là H[i]. 12
- Xem thêm -