Chữa đề thi thử lần 1 THCS năm học 2023 - 2024 SVIP

Văn bản dưới đây là được tạo ra tự động từ nhận diện giọng nói trong video nên có thể có lỗi

• bài số 1 bài đổ
• nước
• à Chúng ta có một cái chúng ta có hai
• cái
• C một cái C hiện nay đang chứa lượng
• nước Là
• a một cái cal Giả sử l lượng nước là b
• giả sử b là đang lớn hơn A ha
• đấy và chúng ta có một cái cốt
• nước cốt nước có thể tích thể tích là
• C và chúng ta cần phải đổ chúng ta múc
• cái cốc ở bên B này và đổ ở bên A đấy
• múc bên B và đổ ở bên A để à múc làm sao
• cho mà chúng ta có thể làm cho hai cái
• bình này bằng nhau
• đấy múc cho hai bình này bằng nhau và
• nhớ rằng là là ở một lần chúng ta có thể
• có thể đổ với một cái lượng nước không
• phải là số nguyên tức là cái một lượng
• nước ví dụ chúng ta có thể đổ 1/3 cái
• cốc C này thôi 1/3 cái cốc C hoặc là 1/5
• cái cốc C này biếtn làm sao cho nó có
• thể đổ được đầy à được hai cái bình này
• AB này bằng nhau đấy mới làm sao đổ cho
• được cái AB này bằng nhau với số lần đổ
• là ít
• nhất
• đ đây chúng ta sẽ nhìn thấy nh nhá Cái
• hướng dẫn
• giải hướng dẫn giải thì chúng ta sẽ Hình
• dung là giả
• sử Giả sử
• là chúng ta sẽ
• múc x
• lần ở bên
• B và đổ sang bên A
• đấy thì chúng ta sẽ Hình dung là giả sử
• chúng ta múc x lần ở đ bên bên B đồ sang
• bên A nhá đấy thì cái lượng nước của sau
• khi đổ ấy của bên A nó sẽ dâng lên đây
• như vậy Chỗ này chính là x lần nhân với
• c Đấy múc x lần tức là x lần nhên bên C
• còn bên này sẽ bị Giảm
• đi Giảm đi một lượng là x lần
• C nhân với c Đấy
• thì nó sẽ có hai cái khả năng xảy ra như
• thế này nhé có hai khả năng như
• này cái khả năng một hai khả năng hai
• trường hợp đấy này rơi vào trường hợp
• 1 trường hợp 1 ấy là sau khi
• đổ quy đổ x lượng X lần
• thì hai bình bằng
• nhau đấy thì hai bình bằng nhau thì
• chúng ta sẽ thấy ngay là cái độ chênh
• lệch ở cái phần mức ở cái mức nước này
• này độ chênh lệch này CH chính ta chính
• là B trừ đi
• a độ chanh lệch mức nước a và b là b - a
• đúng không giữa bình a và bình b đấy thì
• nó là b - a nhá thì sau khi chúng ta đổ
• đổ và nó bằng nhau thì có nghĩa là lúc
• này ấ
• cái giá trị x của chúng ta cả cái phần
• này của chúng ta nó chính là bằng hai
• lần X nh C đúng không Trong trường hợp
• mà mà nó bằng nhau trong trường hợp này
• có nghĩa là B trừ đi a sẽ bằng 2 lần X
• nh C từ đây chúng ta có thể thấy ngay
• được chúng ta sẽ có x chính là bằng B
• trừ đi a trên 2 lần
• c Đấy là trường hợp thứ nhất trường hợp
• thứ hai là chúng
• ta sau x lần đổ thì 2 bình không bằng
• nhau bình nó không bằng
• nhau đấy hai bình không bằng nhau có
• nghĩa là gì có nghĩa là cái phần này này
• chúng ta bên A nó bằng này đấy thì nó
• còn một một tí tẹo Tẹo chỗ này nữa này
• chính là cái phần mà chúng ta sẽ đổ thêm
• một lượng lần cái cốc C này nữa chính là
• chúng ta sẽ đổ một phần nhưng lần này
• chúng ta không đổ đầy cốc C mà chúng ta
• chỉ đổ một phần nào đó để cho hai cái
• phần này nó bằng nhau đấy thì phần này ấ
• thì số lần đổ của chúng ta ấ lúc này số
• lần đổ chúng ta chính là x sẽ bằng B trừ
• đi a tr 2C c+ 1 đấy là số lần
• đổ Vậy thì ở đây chúng ta sẽ thấy ngay
• cái lời giải chúng ta ấy nó sẽ như thế
• này đó là chúng ta chỉ cần kiểm tra nếu
• như Nếu như mà b trừ đi a mà chia hết
• cho
• chia hết cho hai
• lần à c hai lần c thì X của chúng ta sẽ
• chính là b - a chia cho 2 2 lần C còn
• ngược lại
• thì chúng ta sẽ cộng thêm
• 1 đấy thì cái ý tưởng chúng ta là ở cái
• bài này là chúng ta sẽ ra như thế hầu
• hết các bạn đều ph đ cái bài này vì cái
• lời giải của nó khá là
• dễ
• à đấy chúng ta thấy ngay là cái lớp của
• chúng ta đang full 100 người rồi nên là
• có lẽ là sẽ một số người không vào được
• vậy
• thì những ai mà
• đang ở cái nhóm Trung học cơ sở thì ở
• lại trung học phổ thông các thầy cô có
• thể ra để cho nhường cho những người mà
• người ta học cơ sở để người ta vào nghe
• trước nhá
• Đấy xong rồi mình sẽ nhắn lên nhóm cái
• zoom này của mình chỉ được 100 người
• thôi Thế là xong cái bài số 1 nhá bài số
• một mình nghĩ là bài nó rất là dễ bài số
• hai
• bà 2 thì chúng ta sẽ có cái đề bài đó là
• chúng ta có một cái
• dãy A1 đến An này và yêu cầu chúng ta đó
• là tìm cái vị trí
• K sao
• cho tổng từ A1 cộng
• A2 cộng
• AK chênh lệch với cả cái cái tổng bên
• này Đấy trị tuyệt đối
• a K +
• 1 cộng với An Trịnh lệch này sao cho giá
• trị này là là giá trị nhỏ nhất đúng
• không đấy chúng ta sẽ tìm và tìm ra cái
• độ giá trị nhỏ nhất này tìm được kết quả
• này đấy thì cái bài này nó cũng là cái
• bài mình nghĩ là nó không phải là khó
• lắm thì chúng ta sẽ thấy ngay là đầu
• tiên ấy là chúng ta sẽ tính tổng củaở
• cái
• dãy hướng dẫn nhá thì đầu tiên chúng ta
• sẽ có cái tổng dãy là A1 cộng
• [âm nhạc]
• A2 n
• đấy thì chúng
• ta sẽ sẽ tìm cái vị trí K đây là vị trí
• K và tổng t đân đây chênh lệch chênh
• lệch với cả cái đoạn phía sau này là nhỏ
• nhất đúng không Thế thì chúng ta sẽ tình
• một cái biến ta sẽ đi tính tổng t t bằng
• cái tổng từ A1 đến
• AK A1 đến
• AK đấy còn tổng phần còn lại tổng này nó
• chính là s trừ đi t đúng không Chúng ta
• nhìn thấy rõ ràng là tổng này bằng s t
• Vậy thì chúng ta sẽ có cái độ chênh lệch
• cái kết quả chúng
• ta đầu tiên là chúng ta đặt bằng dương
• vô cùng tức là vô cùng lớnở đây chúng ta
• có thể đặt là 2 e9 đề bài chúng ta n như
• thế nào nhỉ Xem cái điều kiện của nó để
• chúng ta viết
• à Ừ kế động chứnh lệch chúng ta khá là
• lớn vậy thì nó phải là
• bằng phải Dương đến 10 mũ 10 15 đấy nó
• tương đương với dương vô cùng thì chúng
• ta sẽ có đó chúng ta sẽ duyệt cái vòng
• lặp để tính t thôi for i từ 1 cho đến n
• -1 Thôi nhá chúng ta nhớ là đến n -1
• thôi đấy thì chúng ta sẽ có ngay là
• t sẽ bằng t cộng với cả
• ay đấy và chúng ta được kế động Chinh
• lệch à kết quả của chúng ta sẽ bằng
• Min giữa
• T giữa kết quả
• với cái độ chanh lạch hai phần này đúng
• không trị tuyệt đối của s trừ t trừ t
• một lần nữa đúng không Tức là bằng hai
• lần t đấy thì kết quả chúng ta sẽ đặt
• bằng như này bài này khá là dễ với độ
• phức tạp chúng ta là ô
• on có chỗ nào các bạn không rõ thì các
• bạn hỏi luôn Ừ đấy cái bài này thì mình
• sẽ sẽ chữa như thế cả Bạn học sinh nhá
• bạn không rõ thế nào các bạn hỏi
• ngay để cái bài này khá là dễ như thế
• hai cái bài đầu của trung học cơ sở là
• là khá dễ coi như để như kểu là để cho
• điểm các bạn
• Thôi thì cách làm này là với độ phức tạo
• là
• on khá là dễ xa đấy là bài thứ hai nhá
• bài thứ
• ba bài thứ ba thì bắ đầu nó khó hơn một
• chút đó là chúng ta có một cái trục
• số trên trục số này chúng ta để một vài
• cái viên bi ở tại những cái tọa độ
• [âm nhạc]
• mà chúng ta đã có trước theo cái input
• của đề
• bài lấy ví dụ đây là
• 1 Đây là
• 4 5 6 7 8 9 9 10 11 12 13 14 15 16
• 17 đây là 2 3 đúng
• không
• 1
• không thì chúng ta chỉ người ta sẽ đưa
• ra cái thông báo là với cái cái vị trí L
• và
• r thì đếm xem là có bao nhiêu viên
• bi thuộc vào trong cái đoạn từ l đến r
• này ví dụ như là l chúng ta là bằng 3 r
• chúng ta bằng 10 thì chúng ta sẽ thấy là
• cái đoạn từ 3 đến 10 này là chúng ta có
• 3 vnb
• đấy chúng ta tắt mic đi giúp
• nhé đấy à thì chúng ta có một loạt các
• cái con cái cái truy vấn với L và r với
• nhiều giá trị l r khác nhau với các cái
• truy vấn như thế này mỗi truy vấn đó thì
• chúng ta phải trả ra được cái kết quả là
• có bao nhiêu vin Bi trong cái đoạn từ l
• đến r
• đó thì mình nghĩ là cái bài này tôi nghĩ
• bài này là cũng là cái cách vận dụng của
• phương pháp t Hưng Tìm kiếm nhễm
• phân đấy phương phát tì phế nhị phân thì
• cái bước đầu tiên ấy và chúng ta sẽ phải
• sắp xếp
• lại tọa
• độ các viên bi tăng
• dần ho phải sắp xếp lại cái tạ độ các
• viên bi này tăng dần
• đấy
• à bước thứ hai thì chúng ta sẽ sử dụng
• cái phương pháp tìm kiếm nhị phân để
• chúng ta tìm ví dụ ở đây chúng ta có cái
• điểm
• là 4 này đấy Lúc này qu chúng ta ví dụ
• là 4 này 6 này 8 này sau khi sắp xếp tă
• dần nhá
• 11 14
• 17 đấy Đây là vị trí 1 2 3 4 5 6
• nhá chúng ta giả sử đây có 6 VB và chúng
• ta chúng ta sẽ phải tìm cái vị trí là l
• và R là left và right Giả sử là chúng ta
• tìm được trong cái đoạn à độ dài là 3
• cho đến 10 Đấy tức là chúng ta sẽ tìm
• cái khoảng từ 3 cho đến đến 10 là trong
• cái vùng
• này nó có ba viên bi thì bước thứ hai là
• chúng ta cần phải tìm cái vị
• trí Chúng ta sẽ tìm vị trí p nhỏ
• nhất ta gọi là p1 nhỏ
• nhất sao cho đây ta gọi là dãy này là
• dãy xì
• sao cho x của
• p1 sẽ lớn
• hơn hoặc bằng cái giá trị l lớn hơn hoặc
• bằng l
• đấy Vậy thì trong cái ví dụ l = 3 l = 3
• thì chúng ta sẽ thấy ngay là cái vị trí
• Cần tìm của chúng ta chính là p1 =
• 1
• đấ cái này thì đối với basc thì các bạn
• phải tự cos bằng phương pháp tình kiếm
• nhị
• phân đấy Tìm kiếm nhị phân à Cái này
• phải tự COD bởi vì bong bcan là chúng ta
• không có hỗ trợ gì
• cả Còn nếu trong c+ C chúng ta sử dụng
• hàm low
• B
• đấy nếu bạn nào chưa biết các bạn phải
• về tìm hiểu hiểu thêm cái hàm này hàm
• này là hàm để giúp cho chúng ta có thể
• tìm được cái vị trí p nhỏ nhất mà thỏa
• mãn điều kiện này cái hàm này Chính là
• dùng để vị Trì vị trí p dùng được cái
• hàm này rồi à đối với
• Python để tìm kiếm nhiệm phân chúng ta
• dùng hàm
• bsc l với ý nghĩa tương tự như là của C
• dụng cộng cái log B cụng cộng có nghĩa
• là nó cũng có thể tìm được vị trí p nhỏ
• nhất mà thỏa mãn đ điều kiện là a là cái
• X và p1 lớn hơn bằng l đấy chúng ta chỉ
• cần gọi hàm ra là nó ra luôn chứ chúng
• ta không cần phải lo cái chuyện là là là
• [âm nhạc]
• nó phải code như thế nào chỉ cần chúng
• ta biết cách sử dụng hàm này là chúng ta
• gọi nó ra là nó nó ra luôn ở cái vị trí
• của chúng ta
• đấy Ở đây chúng ta sẽ phải từng nếu
• không chúng ta phải tìm bằng phương pháp
• tìm kiếm nhị phân ở đây chúng ta sử dụng
• phươ pháp tính kính ngy
• phân đấy đầu tiên là chúng ta tìm vị trí
• l sau với đối với r Còn đối với r nhá
• đối với r chúng ta có r ví dụ là bằng 6
• à bằng bằng 9 đấy bằng 9 thì chúng ta sẽ
• phải tìm cái vị trí p2
• hoặc là có thể chúng ta sẽ tìm đ vị trí
• P1 P2 nó nằm ở đây có hai cách tìm hoặc
• là chúng ta sẽ tìm p2 đây hoặc là p2 ở
• chỗ này chỗ nào cũng được
• đấy chúng ta sẽ tìm vị trí
• p2 p2 là nhỏ
• nhất
• sao
• cho x của p2 cũng lớn hơn hoặc bằng R
• đấy chúng ta có vị trí p nằm ở đây đấy
• vị trí này chúng ta sẽ thấy ngay là p2
• nằm ở đây tức là lúc này chúng ta sẽ
• thấy trong trường hợp này ấ là x của p2
• nó chính là bằng giá trị 11 đấy và lớn
• hơn r bằng 9 đấy hoặc bằng R 19 là bằng
• 99 nhá thì p2 nó sẽ nằm đây Thế để tìm
• nó thì chúng ta cũng làm tương tự như
• trên này chúng ta cũng tìm cái Nhị Phân
• để chúng ta làm bằng phương pháp tính kí
• nhệ phân nhưng là với Pascal chúng ta
• vẫn phải tự cos ra bằng mấy cái đoạn C
• tương đối là dài trong khi đó thì X dộng
• cộng và Python nó được hỗ trợ hai cái
• hàm này nên chúng ta code bằng một dòng
• lệnh trong khi đó Pascal chúng ta phải
• gõ ra một cái khoảng à Chục khoảng 10
• dòng lệnh gì đấy thì chúng ta mới ra
• được còn mà cos trong chi không có còn
• chưa chắc là chính xác Còn với Python và
• S Cộng Nếu chúng ta biết cách dùng thì
• chúng ta chỉ cần gọi nó ra là xong
• đấy sau khi có P1 P2 rồi thì kết quả
• chúng ta chỉ cần in
• ra đó là p2 trừ đi p1 thôi đấy chúng ta
• chỉ cần trừ như thế là xong là ra ở cái
• bài
• này đấy thì mặt về mặt ý tưởng như thế
• còn về mặt cos cụ thể thì các bạn có thể
• tham khảo Cái cos của thầy à đã gửi cho
• các thầy cô giáo phụ trách môn của các
• em mình à code bằng C cộng và Python
• thôi còn pasc thì mình không code thì
• mình thực ra là mình cũng lâu lắm rồi
• mình không dùng đến pasc mà mọi người
• thì không biết là chương trình chúng ta
• bây giờ cũng bỏ bcan rồi đấy Bạn nào mà
• đang dùng bcan là thiệt thòi
• thôi Thực ra thì đối với mình mình đối
• với bản thân mình mình khuyến khích mọi
• người nên dùng sin dộng cộng là tốt
• nhất mọi người nếu các bạn dạy cho học
• sinh các bạn nên dùng sụng cộng thi học
• sinh giỏi thì nên dùng sụng cộng là tốt
• nhất còn bascan hay là Python là các bạn
• tự tự làm khó mình hơn tự chói chân chói
• tay mình lại chứ còn cái c cộng này mới
• là cái mà hỗ trợ cho th sinh giản cực kỳ
• là tốt thuận lợi
• đấ pasc thì C nhiều không có hàm hỗ trợ
• các bạn phải C C từ A đến Z đấy Coi như
• là chúng ta thua về mặt tốc độ cos rồi
• Python thì code ngắn nhưng mà lại chạy
• chậm thế là chúng ta thua về mặt thời
• gian rồi thua về mặt thời gian chạy
• chương trình chỉ có x dộng cộng code vừa
• ngắn chạy vừa nhanh chọn lợi nhất thế
• này chọn lợi nhất là x dụng cộng Còn nếu
• ai mà vẫn dùng bascan hay là dùng C cộng
• à hay dùng Python thì cái điểm của các
• bạn sẽ chấp nhận là sẽ điểm thấp hơn
• những người khác Nếu như các bạn code nó
• không kỹ hoặc là chúng ta biết những cái
• lợi thế của nó không thể bằng C cng
• đấy thấy nhá Đấy Đây là bài số số 3 có
• ai ai không hỏi ai Anh muốn hỏi gì thì
• chúng ta hỏi luôn nhé chúng ta hỏi luôn
• em Thầy em hỏi Ừ em thầy là em code đúng
• cái ý tưởng thế mà sao nó khi chấm mà em
• bị không mà thấy thế thì có nghĩa
• là em cốt em đúng ý tưởng nhưng mà em
• cốt có thể bị sai Kết quả nó sẽ có thể
• ra sai
• đấ
• Ờ nhưng với lại thì nếu mà trường hợp Ví
• dụ như là trường hợp l = 3 r = 10 thì mà
• có mà O3 và o10 xuất hiện viên bi thì nó
• là ch nó ra 4 hay 3 là như thế nào
• nhỉ ví dụ là số 3 nó ví dụ là viên bi nó
• đặt ở vị trí 3 ô số 3 3 đây và vị trí 10
• thì nếu là 3 r bằng 10 thì đáp án nó là
• 4 hay là 3 tất nhiên nó r = 10 chứ gì
• Thì tất nhiên l nó nằm đây đúng không R
• 10 đây đúng
• không 10 thì bây giờ vẫn phải tìm p nó
• ra đây đúng không Thì p nó vẫn ra vị trí
• 11 đúng không Thì đáp án nó vẫn là ra 3
• chứ vẫn là nằm trong vâ Nhưng mà nếu mà
• R là nếu trong trường hợp r bằng 11 thì
• nó là ra 4 V r11 thì là ra 4 là đúng rồi
• vì nó là từ 3 đến b từ 3 đến 11 này có 4
• b bi
• đây 4 V bi là đúng rồi Vâng Ừ đấy nó ra
• vốn là đúng rồi đấy Em có thể ý tưởng em
• đúng như em C có thể bị sai chúng ta
• biết là học mới muốn tin của chúng ta đã
• đi từ ý tưởng đến chương trình nó cả một
• quãng đường dài chứ không phải là chúng
• ta cứ ý tưởng đúng là chúng ta làm được
• đúng đâu đúng
• không
• Ừ
• đấy nhá Còn bài này nếu mà các bạn dùng
• à Dùng map à Mình không biết dùng map
• mọi người dùng kiểu gì thì không rõ
• đấy nhưng mà chỉ biết
• [âm nhạc]
• là dùng map có thể nó bị trậm quá thời
• gian dùng map Mọi người nhớ là Map chạy
• chậm nhá map chạy
• chậm chúng ta không nên lợi dụng quá vào
• những cái cấu trúc dữ liệu là map hay là
• set bởi vì những cái cấu trúc dữ liệu
• này làm làm việc Thực ra là tương đối
• chậm bắt buộc phải dùng thì phải dùng
• thôi còn nếu mà không bắt buộc dùng ấy
• chúng ta nên nghĩ cách khác để chúng ta
• giải quyết Còn cái này nếu bắt buộc phải
• dùng thì chúng ta dùng vì nó chạy rất là
• chậm hai cái cái cấu trúc này chúng ta
• cứ tưởng nó chạy nhanh Thực chất là nếu
• mà dữ liệu là lớn lên tí là chạy rất là
• chậm
• rồi Có lẽ là cái bài hôm trước có cái
• bài
• ấy đây nhá thì chúng ta nhớ nhớ nhá
• những cái cấu trúc dữ liệu cái dữ liệu
• này là tương đối chậm nhá Đấy về mặt lý
• thuyết thì nó nhanh nó là nhanh nhưng mà
• về mặt thực tế là nó nó truy cập ở trên
• con trỏ trong cùng nhớ ấy là là nó sẽ
• chạy là tương đối chậm nên các bạn chú
• ý
• bài số
• 4 bài số
• 4 bài số 4 tắt lại là chúng ta tìm a1a
• cho một cái dãy A1 A2 đến
• An từ A1 Sau đó chúng ta sẽ tìm với mỗi
• cái
• ay chúng ta phải tìm một cái giá trị A
• gần với ai
• nhất sao
• cho là A thì lớn hơn ay nhá Đấy
• À tất cả những cái bài này thầy đều có
• code rồi nên các bạn có thể về tham khảo
• code còn ý tưởng thì thầy chỉ nói ý
• tưởng đây chứ Thầy không hướng dẫn code
• các bạn được nhá vì chúng ta sẽ không đủ
• thời gian để chúng ta có thể hướng dẫn
• code cả tám bài một lúc bốn bài chúng ta
• trong bài này là cũng không kịp đấy nên
• là chỉ có chữa về mặt ý tưởng còn code
• các bạn về có thể tham
• khảo ví dụ dãy của chúng ta là 4 1
• 3 ở đây chúng ta là tìm vị trí J Tìm vị
• trí J nhá sao cho sao cho A gần với y
• nhất và thỏa mãn điều kiện
• này
• đấy ví dụ dãy như này thì kết quả chúng
• ta ấ nó sẽ ra là 4 thì cái giá trị đầu
• tiên này ấy thì bên trái của nó không
• có ở đây là j nó nằm bên trái
• nữa
• A và a bên
• trái bên trái của ay đấy thì chúng ta sẽ
• thấy ngay số 4 này bên trái nó không có
• số nào mà
• lại lớn hơn nó cả nên là bằng 0 này số 1
• thì có có b là cái số mà
• cái 4 mà gần là 1 1 thì có số B gần với
• nó nhất thì là giá trị lớn hơn nó nên là
• chúng ta có kết quả chỗ này là sẽ là 1
• tức là chúng ta sẽ in ra cái vị trí này
• này số 3 thì chúng ta sẽ có có giá trị 4
• Cũng gần với nó nhất mà lại lớn hơn nó
• nên cũng sẽ là 1 số 2 này thì có giá trị
• 3 là lớn hơn nó
• mà gần nó nhất nên sẽ ra là giá trị 3 số
• 7 thì không có cái số nào bên trái mà
• lại gần nó nhất mà lại lớn hơn nó cả nên
• bằng 0 còn số 3 này thì có cái vị trí 5
• này là gần nó nhất mà lớn hơn nó nên
• chúng ta sẽ ra bằng 5 đấy đề bài chúng
• ta sẽ như
• thế đặc điểm và cái dữ liệu cho cái bài
• này thì tương đối là lớn đến tận 10 mũ 6
• sao là 10 mũ 6
• đấy
• ở bài này ấ Thực
• ra chúng ta có thể sử dụng một cái cái
• cách như thế này đó là chúng ta về phần
• hướng dẫn
• này chúng ta sẽ sử dụng một cái ngăn
• set
• ế ta gọi đó là
• stack thì cái hoạt động của stack rất
• đơn giản thôi chúng ta hình cứ hình dung
• như là chúng ta có một cái cái thùng
• thùng đựng sách chẳng hạn thùng lượng
• sách nó như thế này một cái thùng như
• này thì cái ngăn xếp nó sẽ chúng ta sẽ
• Hình dung là chúng ta sẽ cho những quyển
• sách vào trong cái thùng
• này đấy chúng ta sẽ x những quyển sách
• vào thùng
• thì cái quyển nếu cái quyển nào mà được
• xếp sau ấy thì lúc lấy ra sẽ được lấy ra
• trước Quyển này xếp sau cùng nhưng mà
• lúc lấy ra thì lấy ra đầu tiên cái này s
• gần sau cùng thì được lấy ra sau đúng
• không đấy thì cái hoạt động của stack đó
• là cái giá trị được vào trước thì sẽ ra
• sau hoặc là giá trị thì vào sau thì ra
• trước
• hoặc đấy chúng ta sẽ sử dụng cái cái dữ
• liệu này để chúng ta làm cái việc
• đó Bây giờ chúng ta sẽ nói đến cái vấn
• đề là ý tưởng của cái bài này đã trước
• khi chúng ta nói về hoạt động ngă xếp
• cho cái bài này như thế nào thì chúng ta
• sẽ nói ý tưởng cho cái bài này à đầu
• tiên ý chúng ta sẽ Hình dung là cái
• cái người đầu tiên sẽ đứng vào hàng nhá
• chúng ta cái bài toán chúng ta sẽ g về
• cái bài toán xếp
• hàng
• à chúng ta sẽ Hình dung là cái bài này
• nhá
• Ừ bây hiện tại thì cái ngăn xếp của
• chúng ta là à Hiện tại trong hàng Chúng
• ta không có ai cả nên là cái anh số 4 có
• đồ cao 4 này anh sẽ được vào xế vào hàng
• anh này và chúng ta đánh chỉ số anh này
• là bằng 1
• được xếp vào hàng và hiển nhiên thì anh
• này vì không có ai ở phía trước nên anh
• ta sẽ bằng
• 0 à sau đó đến anh số hai được có độ cao
• là 1 sẽ được xếp vào
• hàng và anh này thì khi khi và xếp hàng
• ấ anh ta nhìn thấy cái anh này cao hơn
• anh ta đấy nhìn thấy cái anh số một này
• cao hơn nên là đánh thứ tự và một vào
• đây
• luôn bây giờ đến anh số 3 xếp vào hàng
• Nhưng mà trước khi kh nhìn thấy anh số
• ba khi vào đi vào hàng ấy thì nhìn thấy
• anh số hai này thấp hơn anh ta nên là
• anh ta đuổi ra khỏi hàng như vậy anh số
• hai này bị đuổi ra khỏi hàng đấy bị đuổi
• ra khỏi hàng khi mà anh này bị đuổi ra
• khỏi hàng xong ấy thì anh số số ba đưa
• vào đi vào đây ấ nhìn thấy cái anh số
• một này lại cao hơn anh ta nên anh ta
• không đuổi được anh ta lại tiếp tục xếp
• vào
• đây đây là người số ba vậy người số ba
• này nhìn thấy anh số 1 này cao hơn nên
• sẽ lấy chỉ số là 1 đấy nên chúng ta mới
• có 0 1 1 chỗ này đây đấy là như thế
• à tiếp tục à anh số 4 này vào cái độ cao
• anh số 4 này đang bằng 2 thì anh này xếp
• vào hàng vì anh này nhìn thấy cái anh số
• ba này cao hơn anh ta nên là nên là anh
• ta sẽ xếp vào hàng như thế này Đấy và
• nhìn thấy độ cao cao hơn anh ta nên là
• lấy luôn cái chỉ số này bằng
• 3 đến anh số 7 đến anh số 7 đi vào thì
• anh số 7 đi vào ấy à anh số 5 này đi vào
• có độ cao bằng 7 này thì anh số 5 đi vào
• ấy thì là lập tức là nhìn thấy anh này
• thấp hơn ấ đuổi anh này ra ngoài thế Anh
• này vẫn thấp hơn anh ta đuổi nốt anh này
• ra ngoài thế Anh này thấp hơn thì đuổi
• nốt như vậy Ba anh này bị đuổi hết ra
• khỏi hàng lúc này hàng là rỗng không còn
• gì cả nên anh số 7 cứ xếp vào
• thôi và do hàng này lúc này rỗng nhá Lúc
• này hàng lúc này rỗng thì phía trước anh
• ta lúc này có giá trị bằng 0
• đấy tiếp tục đến anh số 3 đi vào anh số
• 3 đi vào à Anh x anh số sáu đi vào thì
• anh số sáu có có độ cao bằng 3 thì thấy
• cá An độ cao bằng 7 này là cao hơn thì
• chúng ta sẽ lấy luôn cái đâ cái anh thứ
• Năm đúng không nên ta sẽ lấy giá trị
• bằng 5 đấy chúng ta sẽ ý tưởng chúng ta
• là bài toán xếp hàng đấy xếp hàng khi
• xếp hàng ấy ý tưởng xếp hàng nó là như
• thế
• này nếu người
• y xét à chúng ta xét cái người thứ y nhá
• đ chúng ta xét cái người thứ y
• đã từ 1 cho đến n nhá
• Đấy đầu tiên ấy à chúng ta sẽ Giả sử là
• chúng ta sẽ xét cái anh số 0 vào chúng
• ta C coi như cái hàng rỗng thì ban đầu
• ấy thì vẫn có một cái anh gọi là anh số
• 0 anh số 0 là anh này anh là ảo thôi anh
• Này ảo thôi và anh này có độ cao là vô
• cùng lớn và không có anh anh nào có độ
• cao lớn hơn bằng cái anh số 0 này giả sử
• đây là 10 mũ 9
• đấy đầu tiên là coi như chúng ta có một
• cái anh ảo này Đây chỉ annh là cái người
• mà chúng ta tưởng tượng ra thôi nhá chứ
• còn không có thực
• tế ở đây người xét bây giờ xét người thứ
• y Nếu người
• y có chiều cao
• ai
• mà còn lớn hơn hoặc
• bằng chiều
• cao của
• người chúng ta chỗ này phải là khi
• nào khi nào tức là chỗ này chúng ta dùng
• vòng lặp luôn
• ấy khi nào người y có ai lớn hơn bằng
• chiều cao của người cuối
• hàng thì cái người cuối hàng sẽ bị đuổi
• ra khỏi
• hàng
• đấy thì chúng ta thấy là điều này khi nó
• cứ lặp lại bằng một cái vòng lặp chúng
• ta sẽ lặp đi lặp lại
• suốt cho đến khi mà sẽ gặp một cái người
• ở cuối hàng có chiều cao lớn hơn ai này
• thì sẽ dừng đúng không cái vòng lặp này
• nó sẽ lặp cho đến khi mà gặp cái người ở
• cuối hàng mà cao hơn cái ai này thì sẽ
• dừng đấy kh đó thì cái kết quả của người
• thứ y vị trí của người y hay là giá trị
• tại vị trí
• Y
• là bằng cái vị trí của người cối
• hàng bằng vị trí của người cuối hàng sau
• đó thì à tiếp tục cái anh người thứ y
• này xếp vào cuối
• hàng cuối hàng
• đấy
• đây là ý tưởng nhá mọi người nếu mà cần
• có thể lấy thêm một ví dụ khác mình có
• thể lấy ví dụ khác để biểu diễn cho
• chúng ta hiểu rõ hơn có cần thêm một ví
• dụ khác
• không Chúng ta có hiểu cái ý tưởng này
• không nhỉ Thầy
• ơi thế cái ý tưởng khi nào y có ai này
• là dùng vòng lặp vo hả thầy Đúng rồi
• dùng vòng lặp
• wi mỗi một phần tử chúng ta sẽ thấy ng
• là mỗi một phần tử này này nó chỉ được
• xét hai lần một lần thứ nhất là chạy một
• vòng lặp này một lần thứ hai là set ở
• cái vòng y này mỗi phần tử Chỉ tối đa
• được xét hai lần nhân độ phức tạp của cả
• cái thuật toán này nó sẽ là O của 2n
• thôi đấy
• o2n
• nên là nó chạy rất là nhanh Mặc dù là
• chúng ta thấy có hai cái vòng lặp đồng
• vào nhau nhưng thực tế thì nó mỗi một
• cái mỗi một người chỉ được xét hai lần
• một lần ở cái vòng lặc này và một lần
• thì bị sét khi mà anh ta đang ở trong
• hàng đấy tế là anh khi mà anh ta trong
• hàng thì anh ta sẽ bị với người phía sau
• là set xem là có cao hơn anh ta hay
• Không ấ nên là mỗi người chỉ bị set tối
• đa là hai lần thậm chí có người không
• được set lần nào à xt một lần đấy Thực
• ra thì mỗi người tối đa hai lần đúng
• không Vậy thì cái độ phức tạp của chúng
• ta chỉ là là o2n nên là cái thuật toán
• này chạy rất là
• nhanh bài này Mình cài bằng hình như là
• cài bằng Python chạy cũng qua 10 mũ 6
• cũng
• qua ừ rồi đấy Thì ý tưởng chúng ta như
• thế th còn có cần phải lấy một ví dụ
• khác để thể hiện ý tưởng này
• không Thế thì cái cái cách xếp hàng nhá
• cái cách xếp hàng lúc đấy là người ta
• dùng stack này dùng cái ngăn xếp này đấy
• chúng ta sẽ hình dung lúc này những cái
• ngăn xếp của chúng
• ta như thế
• này x nó
• theo mình tưởng tượng là cái ngăn xếp
• này Ấy là cái đầu bên này nó
• rỗng
• đấy ta gọi ngăn xếp là stk cái stack
• viết tắt là ST
• à chúng ta sẽ lấy ví dụ như
• này vẫn là ví dụ nhà chúng ta là
• 4 1
• 3
• 2
• 1
• 3 54 như này nhá Đấy thì đầu tiên ấy
• chúng ta sẽ Hình dung là chúng ta sẽ có
• một thằng người đầu tiên là ở vị trí thứ
• 0 đây là vị trí 1 2 3 4 5 6 7 8 người
• đầu tiên ấy là chúng ta coi như anh này
• là người rất là cao có giá trị là dương
• vô cùng Có lẽ các bạn cấp hai thì chưa
• học được giá trị dương vô cùng Đúng
• không Không biết là học chưa Nhưng mà
• coi như đây chính là 2 nh 10 mũ 9 2
• tỷ Đây là người số 0 và chúng ta cứ đặt
• người số 0 vào đây đấy lấy cái chỉ số
• này đưa
• vào đấy đầu tiên thì chúng ta sẽ có
• stk chúng ta sẽ có một cái biến là biến
• top ở chỗ này biến top nhá biến Top là
• cái biến mà nó sẽ chỉ vào đây gọi là
• biến top khi mà chúng ta thêm một phần
• tử ở đây ấ thì top nó sẽ chuyển sang đây
• cứ thêm một phần tử vào thì top nó sẽ
• chuyển sang Còn nếu mà xóa một phần tử
• đi thì top nó lại Lùi lại
• đấy chúng ta nhớ đều Đấy tức là khi
• chúng ta thêm một phần tử vào thì top nó
• tăng theo cái phần tử đó ví dụ thêm một
• phần tử vào đây thì top tăng lên Thêm
• chỗ này thì top nó tăng lên đây thêm ở
• đây chúng ta top tăng nhưng mà nếu chúng
• ta giảm giảm thì cái top nó cũng sẽ giảm
• xuống chúng ta nhớ như thế nhá Vậy cái
• cái biến top này ấ là cái biến để biểu
• diễn cái phần tử nằm trên đỉnh stack
• đỉnh của ngăn
• xếp thì ban đầu chúng ta sẽ
• có
• s hay là S
• 1 stack 0 này thì
• bằng đây chúng ta tôi
• code Trung Trung thôi nhá Bởi vì cái này
• là chúng ta
• sẽ đây là mu code cho chung cho cả bằng
• ba nguôn ngữ chúng ta code có thể code
• theo đúng như này Đấy đầu tiên là top
• bằng 0
• này
• top bằng 1
• đi Thực ra
• thì đây là mình Đây là tôi đang code cho
• cả pascan cả cụng cộng và
• Python thì nó chung được như thế này Thế
• còn nếu trong C cộ à trong c cộng nó có
• cái cố có một cái cái thư viện chứa được
• cái stack này rồi nên nó sẽ không được
• cần phải hỗ trợ như cái này thì ở đây á
• chúng ta sẽ có như này
• nhá à for
• i từ 1 cho đến
• n đấy sau đó như này
• Why Khi nào stack cò khác rỗng
• đấy Thực ra thì chúng ta không cần cái
• điều kiện đó mà chúng ta chỉ cần là
• khoai khi nào a ở vị trí
• i mà lớn hơn hoặc bằng a ở vị trí stk
• của
• tốt như thế này thì chúng ta
• sẽ loại cái phần tử ở đỉnh chúng ta loại
• phần tử ở đỉnh đi bằng cách là chúng ta
• giảm top
• xuống
• đấy Đây chính là loại chính là bỏ cái
• phần phần tử của cái người cuối cùng ở
• trong stack ra đấy à Sau đó thì chúng ta
• có ngay được kết quả là a à chúng ta chỉ
• cần in ra in ra cái giá trị stk ở vị trí
• tốp đấy sau đó là chúng ta đẩy vào đó là
• s chúng ta tăng Top lên một đơn
• vị sau đó thì chúng ta gán a à stk của
• top thì bằng
• I
• đấy Đây chính là cái người thứ y này sẽ
• xếp được vào cuối hàng đấy xếp vào cuối
• hàng Còn Đây là loại đi những người mà
• cao hơn à Thấp hơn những người y đây
• chính là những người ở ở cuối hàng này
• này mà thấp hơn người ai này thì đều bị
• loại đây chính là để loại đi Sau đó thì
• sau khi ra khỏi phòng loại này thì chắc
• chắn là cái người ở cuối hàng này nó sẽ
• là người cao hơn người Ai khi đó chúng
• ta chỉ viền in ra cái người cuối hàng
• cái chỉ số người cuối hàng sau đó thì
• chúng ta sẽ đẩy xếp cái người thứ y vào
• trong cái cuối của cái hàng Hiện Tại đấy
• là ý tưởng chúng ta có thể thực hiện ý
• tưởng này qua ví dụ như sau chúng ta sẽ
• thấy ngay là chúng ta sẽ đến giá trị 4 4
• thì thấp hơn cái người người A0 đấy thấp
• hơn người A0 nên chúng ta sẽ đặt chỉ số
• đây là 0 và chúng ta đẩy vào đây chỉ số
• 1 chỉ số y này này tiếp theo chúng ta
• xét cái người có chiều cao là 1 này
• chiều cao này 1 này thì lại thấy người
• khối hàng là người A1 A1 này là cao hơn
• anh ta nên là chúng ta sẽ đặt vào đây
• đặt giá trị là 1 và đẩy một vào đây à
• đẩy x nó đẩy hai đây
• đấy nhớ là đẩy vào đây thì top nó chỉ
• sang đây đến người số ba thì thấy cái
• cái người cuối hàng này cái người cuối
• hàng này là thấy là đang A2 này này đang
• thấp hơn người 3 này nên là sẽ bị loại
• rút ra khỏi rút ra khỏi thì tương đương
• với việc là top nó lại lại quay trò vào
• vị trí
• này
• đấy đến đây thì chúng ta có cái Anh A1
• này lại cao hơn anh anh A3 nên là anh a
• a này sẽ lấy giá trị đây là 1 và đẩy 3
• vào đây đẩy chỉ số 3 và tốp lại chỉ vào
• đây tiếp tục anh A4 thấy cái anh A3 đang
• ở cuối hàng này cao hơn anh ta nên là nó
• sẽ lấy giá trị bằng 3 và đẩy tiếp giá
• trị 4 cái vị trí 4 vào đây à anh A1 à
• Xin lỗi anh A5 A5 lại nhìn thấy anh cuối
• hàng là anh A4 cao hơn anh ta nên là
• chúng ta sẽ ra đằng 4 và đẩy tiếp anh 1
• và đây anh n chỗ này
• đấy đến đây nhớ là đến đây thì top Nó
• chỉ vào đây nhá Nó đang top ch chỗ này
• này anh A6 đưa vào đây thì A6 lớn hơn
• lớn hơn cái anh cuối hàng là anh A5 này
• đấy Nên là anh A5 này bị đuổi ra khỏi
• hàng bị đuổi ra khỏi hàng và nhớ rằng là
• khi bị đuổi khỏi hàng ấy thì cái top n
• này chỉ vào đây đấy đến lúc này anh A4
• anh A4 đang có giá trị bằng 2 thì lại
• thấp hơn cái anh A3 anh A6 đá trị bằng 3
• này nên là chúng ta thấy là anh A4 này
• cũng sẽ bị đuổi ra khỏi hàng và nhớ là
• đuổi ra khỏi hàng thì top nó nó lại chỉ
• vào đây đấy đến anh A3 anh A3 này lại
• bằng cao có độ cao bằng anh A6 nên cũng
• bị đuổi ra khỏi hàng vì cao bằng nhau
• thì vẫn bị đuổi phải tìm người cao hơn
• cơ đúng không Đấy là bị đuổi ra khỏi
• tiếp tục Anh A1 này anh cuối hàng thì
• anh A1 là đang bằng 4 à Xin lỗi anh đâu
• nhỉ anh1 đúng không Anh A1 này b bị loại
• bị đuổi rồi
• A1 bị đuổi từ trước rồi đúng không nên
• là à Anh A2 này không không xét rồi Anh
• A1 là vị trí 4 này chứ Anh A1 này vị trí
• 4 này đang cao hơn anh3 anh A6 nên là
• anh A6 sẽ lấy giá trị 1 ở đây Điền đây
• anh và sẽ chuyển vào đây là 6 vào đây
• Đấy top nó lại chỉ vào chỗ này tương tự
• Thế đến đây Thành anh A7 A7 lại thấy
• thằng này cao là thấp hơn anh A6 này
• thấp hơn nên là sẽ đuổi ra khỏi hàng đấy
• tiếp tục thế Anh A1 này thấp hơn cũng
• đuổi nốt ra khỏi
• hàng nhưng mà đến Anh a anh A0 anh A0
• này thì l cao quá tận 2 2 tỷ cơ nên là
• sẽ không bị đuổi ra khỏi hàng và sẽ lấy
• luôn giá trị đâ bằng 0
• và đẩy giá trị 7 vào đây đấy tiếp tục
• với anh này thì thấy giá trị A7 này cao
• hơn anh ta nên là sẽ đẩy tiếp vào
• đây là 8 và giá trị này sẽ nhận ra là 7
• đấy thì chúng ta sẽ thấy này mỗi phần tử
• thì đều có giá trị là cao hơn nó phía
• trước chúng ta vừa tìm được đúng không
• Đây phần tử này th cao hơn nó đây òn đây
• chứ Thằng này đây đúng không Đằng n này
• thì cao nó tận ngoài này
• cơ Thì đấy là cách giải cho cái bài này
• cách giải cho bà
• này các bạn có thắc mắc gì không có hỏi
• gì về cái cách giải của bài này nữa
• không
• hết rồi chứ
• gì
• đấy Nói chung là kết quả của cấp trung
• học cơ sở thì cao hơn C học phổ thông vì
• có lẽ đề cũng cũng nhẹn Nhưng mà dù sao
• thì các bạn nhỏ tuổi hơn thì cũng không
• nói trước được đúng không rất nhiều Bạn
• giỏi kết quả thì thế tương đối là cao
• rồi Thế thì như thế nhá thầy sẽ dừng lại
• cái buổi bài chữa cho bạn Trung học cơ
• sở ở đây nếu các bạn có thắc mắc thì các
• bạn hỏi luôn Nếu không thì chúng ta sẽ
• dừng lại ở đây để thầy chữa cho các Anh
• Trung học phổ thông những bạn nào đang
• trongc cơ sở rồi thì mời các bạn ra khỏi
• nh khỏi cái kế ấy này nhá
• để dừng ghi