Chữa đề thi thử THPT lần 1 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
• và đổ nước
• [âm nhạc]
• đi và M
• và chúng ta cần tìm cái cặp AB
• với cặp AB thì chúng ta có 2 nhân x cộng
• với cả b x y lại phải nhỏ hơn hoặc bằng
• m yêu cầu Nó là đưa ra
• a nhân x cộng với cả B nhân y
• đạt giá trị là lớn nhất nhưng mà vẫn
• phải đảm bảo điều kiện là nhỏ nhưng mà
• trong cái bài này chúng ta sẽ thấy m
• chúng ta là nhỏ hơn bằng 1000 thôi
• cái điều kiện này rất thuận lợi cho
• chúng ta có thể dùng cách làm trâu bò
• đơn giản
• Bài này là bài đổ sữa ngoài kia mới là
• Đổ nước 2 cái bên đấy thì ở đây chúng ta
• sẽ
• dùng bằng cách là chúng ta duyệt cả hai
• cái biến AB này sao cho nó nhỏ bằng 1000
• [âm nhạc]
• ta đơn giản là chúng ta chỉ dùng a từ 0
• cho đến m
• và b
• từ 0 cho đến 3
• kiểm tra nếu như
• a nhân x b x y nhỏ hơn bằng m
• thì cái kết quả của chúng ta sẽ bằng
• kết quả với
• a nhân x
• Mình
• thì cái độ phức tạp bài này nó bình
• phương
• thứ hai vòng vào nhau là chúng ta làm
• đúng không Chúng ta
• đấy là cái bài thứ nhất bài rất là dễ
• chưa đến đây nhé chắc là không Ai thắc
• mắc gì có ai hỏi gì không
• Đây là Cách thứ nhất à Đây là cái bài
• thứ nhất nhé trong bài thứ hai
• bài này thầy thấy lạ là không ai phụ
• được điểm bài này
• chắc là đây nhiều bạn là dùng kiểu mát
• trong cái bài này và thấy nói trước là
• dùng cái map chạy không nhanh
• mát thì thuận lợi thôi nhưng mà không
• nhanh
• trong trường hợp dữ liệu lớn là như thế
• nào thì câu hỏi là như thế nào
• cái này thì chúng ta sẽ
• phía sau thực ra thì dưới lượng lớn thì
• chúng ta
• cái bài toán Nếu mà em m chúng ta có thể
• quy về bài toán này về một vòng lặp thôi
• cũng được
• nhưng mà Thầy nghĩ là nếu mà em mà lớn
• quá là không không đủ chạy được đâu
• giải ra mà m quá lớn là không không chạy
• được vì a chúng ta ít nhất là phải chạy
• từ không đến mờ
• vì không có cái ràng buộc gì giữa hai và
• b cả nên là chúng ta bắt buộc ít nhất là
• ai phải chạy thử không nên mở nên là bài
• này dữ liệu lớn là không giải được nếu
• em mở quá lớn M đến tầm 10 mũ 6 thì may
• ra có thể giải được
• [âm nhạc]
• sao cho là thỏa mãn điều kiện căn bậc
• hai của x y - y - xj cả bình phương cộng
• với cả
• chúng ta sẽ đến cặp này để thỏa mãn cái
• điều kiện để bài đây đúng không
• [âm nhạc]
• [âm nhạc]
• đặt điểm tối đa và đa số là chúng ta ăn
• điểm bởi vì cách trâu bò đấy
• gầy và giải đáp làm gì nữa bài số 1 thì
• vừa giải đáp rồi
• thì cái cách 1 là cái cách trâu bò bằng
• hai cái vòng lặp for như gì chúng ta sẽ
• thấy sẽ không chữa được nhất các bạn là
• cách một cách trâu bò các bạn tự làm nhé
• bạn sẽ tự làm nhé chúng ta dùng hai cái
• lò xo và Fuji để chúng ta tìm Thôi
• thì chúng ta sẽ nói đến cách thứ hai
• và cách thứ ba hai cái cách này Thực ra
• nó chung ý tưởng nó chỉ khác về cách mà
• chúng ta tổ chức dữ liệu để chúng ta lấy
• được điểm tối đa
• ở đây thì các bạn sẽ để ý rằng là cái từ
• cái phương trình này
• để chúng ta bình phương hai vế lên chúng
• ta bình phương hai vế chúng ta sẽ được
• là x y trừ đi xj
• tất cả bình phương cộng với cả II trừ đi
• ij cả bình phương sẽ bằng xy - x y bình
• phương cộng với 2 lần nhân với trị tuyệt
• đối của x y - x nhân giá
• cộng tiếp
• là II trừ đi ij tất cả bình phương thế
• thì chúng ta sẽ thấy là chúng ta có hoàn
• toàn có thể rút gọn được những cái vế
• bên trái này vào chúng ta suy ra được là
• 2 lần trị tuyệt đối xy - X J
• nhân với cả II trừ đi J là bằng 0
• bây giờ chúng ta quy về cái bài Toán khi
• đó thì chúng ta sẽ quy về cái bài toán
• đến với Cặp easy
• đến gặp easy sao cho
• thỏa mãn cái điều kiện trên này sao cho
• là xy = xj hoặc yy bằng ij
• đây đến đây là chúng ta đã có một cái
• bước đầu thành công trong cái việc phân
• tích bài toán
• rồi đến đây thì chúng ta sẽ tổ chức vào
• mặt dữ liệu để chúng ta làm thì đa số
• mình thấy các bạn ấy làm đến đây là các
• bạn hay dùng cái
• cái kiểu dữ liệu mát để các bạn làm
• thì đầu tiên chúng ta sẽ ý tưởng chúng
• ta sẽ làm như thế này
• đầu tiên là chúng ta sẽ đếm số lượng
• đếm cặp ej sao cho nó là xy = x y
• [âm nhạc]
• và nhớ rằng ta gọi cái cặp này là D1
• Sau đó chúng ta đếm cặp tiếp
• sao cho
• và đến với Cặp này ta gọi là D2
• nhé thì chúng ta sẽ thấy ngay là thực ra
• Các bạn nhìn thấy ngay trong cái tập hợp
• này ấy các bạn sẽ có
• Đây là cái tập hợp mà II
• và tập hợp này là yy bằng II
• đây là tập hợp mà
• x y = x y và y = easy
• các bạn sẽ phải bây giờ các bạn nhiệm vụ
• các bạn phải tìm tiếp có bao nhiêu cặp
• ej thỏa mãn đến
• DJ mà nó phải thỏa mãn hai điều kiện là
• x y = x y và yy bằng y J ta gọi là D3
• Vậy thì kết quả chúng ta sẽ chính là
• bằng d1 + d2 trừ đi D3
• thì đầu tiên là chúng ta sẽ phải có cái
• tư duy này trước tức là về mặt ý tưởng
• là chúng ta phải nghĩ đến cái chiến lược
• này
• các bạn sẽ
• nghĩ đến cái chiến lược này nhé thì các
• bạn sẽ giải quyết nó bằng cách như thế
• nào các bạn hầu hết các bạn đều sử dụng
• kiểu dữ liệu mát để tính cặp này nhiều
• bạn đã ra được ý tưởng này rồi nhưng mà
• tính D1 tính d2 và tính D3 đều bằng kiểu
• dữ liệu Map là để các bạn thì như vậy
• các bạn chỉ ăn được điểm của cái phần ý
• thứ hai thì sắc Thứ hai này thôi
• điểm đến đây
• còn 20% này là các bạn
• không ăn được hết
• để ăn 20% này chúng ta sẽ phải xử lý như
• thế nào thầy đã chúng ta dùng map nhé
• chúng ta sẽ có
• ý tưởng đó là chúng ta có cái cặp
• đây là first này thì
• sẽ lưu giá trị x y và đây là tần số của
• x y đúng không ta gọi là tần số
• [âm nhạc]
• Tức là số lượng ta gọi là tần số thì gọi
• là cnt
• Chắc là cái map này rồi sẽ dùng để chúng
• ta tính cái cái D1 đúng không nhiều bạn
• nó sẽ dùng cái mắt này tính D1
• thì các bạn dùng duyệt max để chúng ta
• tính
• Thế còn cái Cách thứ hai
• cái map này để tính cái D1 cái map Thứ
• hai chúng ta tính d2
• tính tần số mà cái thứ hai này
• chúng ta lưu cái giá trị y
• và tần số xuất hiện của nó
• Thế thì kế cái D1 của chúng ta nó sẽ tự
• tính bằng cái công thức là bằng D1
• nhân lên 1 cộng với cả
• ta gọi là cái này là mb1
• thì là m
• B1 của
• xmp1
• của x trừ 1 cho nó là tất cả chúng ta sẽ
• chia cho 2 cái công thức này thì các bạn
• học về tổ hợp nếu các bạn học tổ hợp thì
• các bạn đã biết còn nếu các bạn chưa học
• tổ hợp thì các bạn có thể dùng kiến thức
• một chút kiến thức toán các bạn có thể
• chứng minh được cái công thức này
• tương tự như thế thì đây 2 thì chúng ta
• sẽ được nhé
• còn D3 thì chúng ta sẽ là gì
• mb2
• còn một cái MP3 nữa
• thì cái kiểu dữ liệu này chúng ta sẽ
• phải lưu ở dạng kiểu p kiểu P
• để chúng ta lưu cả tần số
• easy
• x và y
• và đây là tần số xuất hiện của cái cặp
• xy giống nhau để chúng ta đến với D3
• thì cái D3 của chúng ta thì sẽ bằng D3
• cộng với cả mb3
• MP3
• đối với sinh cộng cộng thì các bạn làm
• như thế này
• thì các bạn sẽ phải
• code bằng
• kiểu từ điển kiểu định
• cách tường cách dùng nick này nó tương
• đương với tương đối giống với cả khách
• tương đối giống với map như vậy cấu trúc
• nó khác nhau
• thì chúng ta sẽ dùng tương đương như
• tương tự như vậy Chứ còn đối Pascal thì
• bài này thì thầy chưa dạy không biết là
• có kiểu thế nào để cho nó phù hợp với
• chúng ta dùng cái cấu trúc dữ liệu như
• thế này thì với Pascal thì thì không có
• được
• chúng ta sẽ nếu chúng ta xử lý được
• không đủ chúng ta không đủ trình độ để
• code thì cái cái cây cái cấu trúc của
• cái map hay là kiểu cái nick này là
• chúng ta không chưa đủ trình độ để chúng
• ta có được cái đấy
• Và nếu có già thì nó rất là dài với
• Pascal mà cốt ra cái này nó dài lắm
• và dài video này thì lại code dẫn đến là
• code nhầm code sai
• nên mày mình mình thấy mới nói là trong
• ba ngôn ngữ lập trình thì
• chúng ta thi học sinh giỏi không nên
• dùng bát can
• không nên dùng bát can
• bởi vì có nhiều bài Ví dụ như bài này nó
• phải code như này Pascal không Cốt nổi
• không Cốt được Nếu có được thì nó rất là
• dài
• thứ hai là cũng gọi là tạm dừng tạm dừng
• pet thon
• tạm dùng nữa nhé
• bạn nào mà dùng tay thon mà muốn muốn
• thi và chọn đội tuyển quốc gia thì các
• bạn gần như không có cơ hội Nếu các bạn
• dùng tay Thoan gần như các bạn không có
• cơ hội
• bởi vì đề thi
• để chọn đội tuyển quốc gia nó rất là khó
• mà khai thon khó có thể biểu diễn Được
• cấu trúc
• từ
• giải được
• giải quyết được bài thứ hai là thi học
• sinh giỏi quốc gia là người ta không
• biết năm nay có thi không nhưng những
• năm trước là người ta không Thi phải
• không cho thi một bài thôi
• Đây là những bạn nào mà muốn xin cấp
• tỉnh chúng ta có thể tạm dùng được My
• thon nhưng các bạn chấp nhận là chậm hơn
• người khác và chậm hơn thì hiển nhiên là
• điểm nó sẽ thấp hơn thấp hơn thì
• điểm thấp hơn thì chúng ta giải nó sẽ
• thấp hơn thôi
• còn khuyến khích là dùng sử dụng cộng
• tính cách các bạn nên học sử dụng cộng
• Để thì trường sinh giỏi
• xương + cos vừa ngắn
• khắc phục được nhược điểm của Pascal
• chạy nhanh lại khắc phục được cả nhược
• điểm của
• iTunes nên là những bạn nào năm nay đang
• dùng tay thon các bạn cố gắng dùng nốt
• sang năm Nếu có cơ hội thi lại các bạn
• nên chuyển sang Python để các bạn Xin
• lỗi sang sử dụng cộng để các bạn học thì
• những bạn Mà đang học cấp 3 thì các bạn
• Nếu bạn này có bạn nào mới vào lớp 10
• thì các bạn có nhiều cơ hội lớp 10 và
• lớp 11 vẫn có thể có cơ hội
• bây giờ chúng ta sẽ làm theo cách nào để
• chúng ta có thể ăn được điểm hết những
• bài này bởi vì cái bài này Map của chúng
• ta là không không được điểm đâu nhé mình
• mát là cũng không phun được vì bản thân
• mát nó cũng tương đối là chậm mà dữ liệu
• chúng ta đây là tận 10 mũ 6 nên là hơi
• khó để phun được thì cái cách làm chúng
• ta đơn giản như thế này nhé
• đó là với cũng ý tưởng ở trên Nhưng bây
• giờ chúng ta cách tổ chức của chúng ta
• không dùng mát nữa mà chúng ta sẽ sắp
• xếp
• tăng dần theo ý
• nếu x bằng nhau
• thì sắp xếp theo đi
• tăng dần
• không nhanh ngang được đâu bạn ạ
• thầy chấm máy này đây Máy thầy rồi không
• phải cấu hình yếu đâu nhá máy này là i7
• thế
• và
• khi 7 thế 10 vế RAM là 12G đấy
• Máy không phải là cấu hình thấp đâu
• nhưng mà dùng tay thon bài này thì có
• bay thon bài này không phun được điểm
• mặc dù cùng có ý tưởng cùng cái cách
• code giống như nhau nhưng không phun
• được vẫn bị được có 80% rồi
• nên là cái cái máy của thầy không phải
• là máy cấu hình thấp máy cấu hình cao
• đấy
• các bạn đừng đừng nghĩ là tất cả đều
• thấy hết mà không không tai thon không
• bao giờ nhanh được bằng sự Cộng cả Mặc
• dù máy của thầy là cũng sử dụng cái
• chương trình
• [âm nhạc]
• chúng ta sẽ thấy
• những phần tử giống nhau Nó sẽ ở gần
• nhau ấy thì cái việc mà chúng ta đến
• những phần tử nó giống nhau này nó trở
• nên rất là đơn giản đúng không
• đầu tiên là chúng ta sẽ đếm chúng ta
• chia ra thành 3 cái khúc Như này
• Đầu tiên là chúng ta đếm cái D1 đếm xem
• là có bao nhiêu cái x giống nhau sau đó
• là đếm tiếp cái Dy và đếm tiếp cái cặp
• này
• thì bước đầu tiên nhé Bước 1
• đầu tiên chúng ta tính D1 khởi tạo bằng
• 0
• thì bây giờ chúng ta chỉ việc Ford
• chúng ta
• giải quyết những cái bài toán ấy là thầy
• sẽ dùng một cái mảng là gọi là mảng
• Fx
• Fx là không thì bằng 0 này chúng ta dùng
• nhúng một tí mình động vào
• fx1 fx1 = 1
• đây là chúng ta trở thành cái bài toán
• là
• đến những cái phần tử
• đếm những cái đoạn giống nhau
• ở trên một cái mảng
• này là chúng ta tính theo cái giá trị x
• với cái đoạn giống nhau
• riêng cái phần tử x cuối cùng là chúng
• ta sẽ đặt Nó là một cái số không bao giờ
• bằng những cái số bên cạnh được nó là số
• dương vô cùng
• để nó không bao giờ bằng nhiều số bên
• cạnh
• ta sẽ pho y từ 2 cho đến n kiểm tra nếu
• như
• mà x y
• bằng với cả X của y - 1
• Nếu bằng nhau thì chúng ta sẽ có lại f
• của X
• Y sẽ bằng f của x y
• - 1 + 1
• ngược lại thì chúng ta sẽ có chúng ta sẽ
• giải chúng ta sẽ phải tính là
• D1 của chúng ta sẽ bằng D1 cộng với cả f
• của x y - 1 nhân với cả f của x y - 1
• - 1 ngoài này nữa nó chia 2 và sẽ gán
• tiếp làm hai việc này
• thì đây là cái bài toán tìm bạn con mà
• có tổng mà có các cái giá trị giống nhau
• thì chúng ta có thể dùng quyết định kiểu
• như thế này mình động này dạng là đơn
• giản thôi thì đây này
• Nó khá là đơn giản
• tính D2 chúng ta làm tương tự
• tức là chúng ta sẽ có fxd là bằng 1 của
• 1 sẽ bằng 1
• chúng ta cũng Ford bắt đầu từ 2
• cho đến n
• để chúng ta kiểm tra nếu như mà
• xy = với cả X của y - 1
• và
• y bằng khi có y trừ 1
• thì FX
• sẽ bằng FX của y - 1 + 1
• ngược lại thì các bạn cũng sẽ làm hai
• việc
• việc thứ nhất đó là chúng ta sẽ gắn D2
• trước
• thì D3 chúng ta sẽ bằng
• D3 cộng với cả FX
• trừ 1 nhân với cả f x y
• - 1
• trừ 1 như thế này chia 2 và chúng ta đầu
• tiên chúng sau đó chúng ta gắn Fi của I
• là bằng 1
• thế Bây giờ tính D3 nhé Giờ mới tính thứ
• hai
• chúng ta nhớ là tính D2 thì lúc này
• trước khi tính D2 là chúng ta sẽ phải
• sắp xếp lại
• chúng ta nhớ là vì cái sắp xếp ở trên là
• chỉ sắp xếp theo x tăng dần
• bây giờ chúng ta phải sắp xếp lại tăng
• dần theo y
• là xác suất làm tăng dần theo ích
• thì bây giờ chúng ta mới xét tiếp đó là
• Fi
• của một thì bằng 1
• cho đến n kiểm tra nếu như mà Fi nó sẽ
• nói là II
• và bằng với cả y của y - 1
• thì chúng ta sẽ có Fi
• của Y = F y của y - 1 + 1
• ngược lại thì f chúng ta sẽ làm cũng làm
• hai việc
• chúng ta cũng làm hai việc đó là tính
• cái giá trị Fi
• D3 D2
• cộng với cả f khi cũng y trừ 1
• nhân với cả f y của y - 1 - 1 chia 2
• và chúng ta được fp của y này bằng 1
• vậy kết quả chúng ta cuối cùng chính là
• D1 cộng với cả D2 - D3
• của thầy để nó tường minh ra hẳn K3 bước
• cho các bạn dễ hình dung còn cái cốt
• tham khảo thầy thì thầy vừa gộp luôn cái
• tính d1 và D3 và một lúc một chỗ thầy
• gộp luôn
• thì còn đây là thầy Thích tách riêng ra
• cho nó dễ dễ nhìn cho các bạn đấy thì
• kết quả chúng ta sẽ ra được hình ảnh
• sao cái công thức này không hiểu là các
• bạn có hiểu về công thức vì sao nó ra
• như này không
• bây giờ chúng ta cứ giả sử như là các
• giá trị x của chúng ta Đây là 2 2 2 5 5
• 5 đúng không 7 chẳng hạn
• Đúng rồi Thế các bạn đưa ra cái công
• thức đó là tổ hợp chọn 2 trong n số của
• lớp 10 lớp 10 bây giờ học cái này rồi À
• thầy không biết Tại vì thầy ngày xưa học
• cái này từ năm này học lớp 12 cơ lớp 12
• mới học và tổ hợp chỉnh hợp bây giờ chắc
• là lớp 10 các bạn đã được học rồi
• [âm nhạc]
• Nhưng cái này thầy nghĩ là cái công thức
• này nó không cần dùng tổ hợp là chúng ta
• dùng Toán phổ thông Bình thường ta cũng
• có thể chứng minh được những công thức
• này không dùng đến tổ hợp cũng có thể
• chứng minh được
• chúng ta đã biết rồi thì thôi
• bài này thì độ phức tạp nhé riêng cái độ
• phức tạp của phần sắp xếp này là chúng
• ta mất là ô n lúc nào
• còn độ phức tạp ở phía dưới này là chúng
• ta mất là
• onl như vậy thì Tóm lại đối với bài bài
• này
• Thế tại sao cái cách làm này nó lại
• nhanh hơn Mặc dù cái cách làm mà chúng
• ta dùng map nó cũng vứt lộn phức tạp với
• mát nhé chúng ta cũng mất độ phức tạp là
• ô nào
• về độ phức tạp là như nhau
• về cái đích Nó là kiểu nó có độ phức tạp
• là onl o1 để đọc dữ liệu tuy nhiên là
• cái đích cái Paypal
• rất là chậm riêng cái phần đọc dữ liệu
• nó đã làm kéo dài cái thời gian rồi các
• bạn rồi
• cái bài này nó nó chắc ở cái chỗ đọc dữ
• liệu ấy chứ không phải là nó chắc ở cái
• chỗ xử lý
• Nên là các bạn chết ở cái bài này là cái
• chỗ đó chỗ đọc dữ liệu Python ở dữ liệu
• rất là chậm càng dữ liệu càng lớn thì
• đọc càng chậm đặc biệt là những cái dữ
• liệu mà lại còn cặp phần tử kiểu như này
• [âm nhạc]
• Thế đã gửi cho các thầy cô giáo dạy cho
• em rồi đấy
• Cái Cách thứ mà chúng ta dùng map đấy
• đối với cả Python là c++, bị Cũ lúc nào
• nhưng mà nó lại chậm ở chỗ là vì cái
• việc truy cập vào map này nó chậm
• nên là mới bị chậm như thế
• nên là chúng ta chú ý là chúng ta tránh
• dùng map tránh dùng xét
• Tránh những cái kiểu dữ liệu đó
• Khi nào bắt dùng thì phải dùng
• thì là bắt dùng thì phải dùng
• ăn no được mát và siêu và Python ý của
• pitton là kiểu dis và ăn no được mát
• là hai kiểu dữ liệu giống nhau
• tương đương nhau tức là đều cùng đều sử
• dụng một cái gọi cái cấu trúc dữ liệu
• gọi là bảng băm
• Tuy nhiên sử dụng hai này thì rất dễ bị
• sai về mặt kết quả Bởi vì trong bảng B
• nó có một cái
• cái cái sai của nó đó là cái mặt đụng độ
• về mặt dữ liệu các bạn có thể đọc thêm
• về bảng băm
• về cấu trúc dữ liệu bằng băm các bạn sẽ
• thấy là trong bảng B này là nó
• nó sai trong trường hợp mà bị đụng độ về
• mặt dữ liệu
• tung độ về trong bảng B này có hai cái
• thông tin đó là key
• và value
• asmart
• [âm nhạc]
• Tất nhiên là trường hợp sai thì nó sẽ ít
• xảy ra thôi nhưng nó vẫn có nhé vẫn có
• cái điều này là nó vẫn có xảy ra nhưng
• mà ít
• đấy là cái bài số 2 nhé bài số 3
• chúng ta xem bài số 3
• này là một trong
• mà chúng ta có các cái cặp AB
• thì chúng ta sẽ phải
• cái này hơi khó giải thích là tìm cái
• giá trị B Min
• trong số
• các cái đoạn
• lr thỏa mãn
• [âm nhạc]
• cho trước
• đồng thời thì
• giá trị B mất
• trong phạm vi từ BL đến b r
• và với những kết quả như thế này với cái
• giá trị như này ta gọi là giá trị
• với nhiều cái cặp
• ở đây chúng ta có thể nhìn thấy ví dụ
• đây
• trong ví dụ là chúng ta có n = 5 còn M10
• nhé
• chúng ta sẽ thấy ngay là tổng hai bé giá
• trị này hai cái A này
• là bằng
• 10 như vậy thỏa mãn điều kiện nếu bằng
• 10
• khi đó thì cái cái giá trị của chúng ta
• sẽ bằng 15 là số lớn nhất trong hai số
• này
• tiếp tục thì chúng ta sẽ có
• nếu chúng ta có tổng cả 3 phần này
• thì giá trị chúng ta vẫn là 15 đúng
• không
• Nhưng làm Nếu như chúng ta có tổng cái
• đoạn từ đây đến đây
• bằng 10 cũng bằng 10
• Tính giá trị của lúc này chúng ta sẽ
• bằng 9
• số đầu tiên này
• bằng 9 và kết quả chúng ta sẽ phải lấy
• hai cái số là cái giá trị nhỏ nhất trong
• những cái giá trị ở đây
• kết quả chúng ta sẽ bằng Min
• cái bài này nếu mà để tóm tắt đề thì nó
• hơi hơi khó tóm tắt nhưng mà chúng ta
• lại đọc cái đề bài thì sao mới hiểu là
• vì sao Kết quả này ra bằng 9
• Các bạn nhớ là
• hết rồi đã từng gặp đã giải bài này rồi
• thì các bạn sẽ thấy ngay kết quả nó sẽ
• vì sao ra bằng chính
• bài này thì chúng ta thấy ngay là
• ý thứ nhất
• 30% test với mn
• [âm nhạc]
• chúng ta sẽ thấy là dễ dàng chúng ta sẽ
• tính được một cái tổng Nếu mà chúng ta
• sẽ dùng mảng cộng dồn đúng không
• chúng ta sẽ dùng mảng cộng dồn là py
• sẽ bằng A1 + A2
• khi đó thì chúng ta sẽ xét
• hai cái đoạn L bằng 1 cho đến n và r
• bằng l cộng 1 nghe là cho đến n
• thì chúng ta sẽ có được là giá trị ta
• tính x
• k bằng với Al
• bằng tổng từ a l
• cộng với a rồi thì nó sẽ chính là bằng t
• của
• R - R đúng không Hay là -1
• hoặc là đây chúng ta
• cứ tính như bình thường thôi
• chúng ta sẽ tính t tại công sức không
• dùng cái mảng tổng cộng
• chúng ta sẽ có t = 0 Sau đó chúng ta kho
• cho set
• R = L cho đến n thì chúng ta sẽ có T = T
• + với cả AR
• thì chúng ta sẽ đi tính tổng t này chúng
• ta kiểm tra nếu như
• cái tổng t này
• đây mắt bằng không Này
• Và nếu như t lớn
• giữa kết quả với Dmax
• đồng thời
• tức là chúng ta sẽ phát ra khỏi tế bào
• sau của cái r này
• chúng ta bình phương điểm
• còn trường hợp thứ hai cách hai
• trong cái sắp Thứ hai này nó là cái mảng
• B của chúng ta thì lại được sắp xếp một
• cách trình tự tăng dần
• và cái này thì rất là thuận lợi rồi Cái
• này thì còn thật là dễ hơn cách ở trên
• với cái dãy đó
• chúng ta chỉ cần tính tổng từ A1 cho đến
• ai
• Nếu như cái tổng này mà lớn hơn hoặc
• bằng m thì chúng ta có thể suy ra được
• kết quả chính là bằng Bi luôn
• bởi cái y Chúng ta đã được sắp xếp tăng
• dần rồi
• chúng ta hình dung ra không
• Rõ ràng cái đoạn đầu tiên này chúng ta
• mà nếu thỏa mãn thì cái đoạn này Từ Bi
• nằm ở đây thì cái y chính là cái giá trị
• lớn nhất trong cái phạm vi từ đây đến B1
• đúng không
• và chắc chắn là nó sẽ nhỏ hơn cái phần
• phía sau này
• Nên là nếu như cái đoạn này mà cộng với
• A2 cộng đến 2y mà lớn hơn hoặc bằng MX
• thì cái kết quả chúng ta chính là Bi này
• chúng ta có thêm cái phần tử này vào thì
• cái Ai là lớn hơn m nó vẫn lớn hơn mờ
• thôi
• Đến Đây nó vẫn mờ Tuy nhiên thì cái B
• của chúng ta cái kết quả chúng ta nó lại
• nằm ở chỗ này
• kết quả là chúng ta lại nằm ở đây thì so
• với cả kết quả cũ nằm ở đây thì kết quả
• này nó tối ưu hơn
• thì trong cái trường hợp này chúng ta
• đơn giản là chúng ta chỉ cần bo một cái
• vòng lặp thôi và t = 0
• for y từ 1 cho đến n
• sau đó là t = t +
• axt lớn hơn bằng m
• thì chúng ta sẽ có hai việc là kết quả
• chúng ta sẽ gắn bằng Bi và
• còn kế Cách thứ ba cách này thì chúng ta
• ăn được full điểm
• chúng ta phải dùng cách này
• đối với cách này thì các bạn phải biết
• đến một cái cấu trúc dữ liệu gọi là cấu
• trúc dữ liệu hàng đã hai đầu
• trong siêu cấp thì chúng ta có cấu trúc
• này
• chúng ta có cái dữ liệu
• chúng ta làm như bình thường
• cái dữ liệu
• này là một kiểu dữ liệu như thế nào
• chúng ta để kêu này là một cái hàng đợi
• hai đầu
• chúng ta có thể
• đẩy một phần tử và về này
• hoặc là chúng ta có thể đẩy phần thưởng
• đầu này
• hoặc là lấy dữ liệu từ đầu này ra
• hoặc là chúng ta lấy dữ liệu từ đầu này
• ra
• và cái bài toán chúng ta làm với được
• yêu này thì rất phù hợp để giải các bài
• toán có liên quan đến tìm đoạn min max
• tìm min max trên một đoạn tịnh tiến
• dùng để kêu
• để giải các bài toán
• tìm một cái giá trị min hoặc là giá trị
• Max
• ở trên các bạn tìm kiếm
• trên các bạn tiên tiến thì cái dòng Dùng
• để kêu này nó rất phù hợp để giải cái
• bài toán này
• thì rõ ràng cái bài toán chúng ta đang
• xét ở đây nó là cái bài toán mà các cái
• giá trị của chúng ta sẽ tịnh tiến lên
• các cái chỉ số chúng ta bắt đầu tịnh
• tiến
• chúng ta sử dụng kỹ thuật 2 con trỏ hai
• con trỏ thì các bạn nó sẽ tiến lên thôi
• Thế bây giờ các bạn sẽ hình dung như này
• thầy sẽ làm mẫu cho các bạn cùng xem một
• pha một cái ví dụ để các bạn sẽ hình
• dung ra cái cách sử dụng
• như thế nào
• [âm nhạc]
• Giả sử m chúng ta là bằng 10
• chúng ta sẽ sử dụng hai con trỏ để chúng
• ta tịnh tiến các cái đoạn như sau
• chúng ta sử dụng hai cái biến y và j là
• hai con trỏ để chúng ta tịnh tiến
• chúng ta sẽ có một cái tổng t ta gọi với
• tổng t này
• đầu tiên hai con trỏ này được chỉ vào
• cái vị trí là 11 và tổng T của chúng ta
• là chính là bằng 4 cái tổng t này chính
• là bằng tổng của a2 cho đến A Di
• các bạn hình dung nhé tổng Tên này là
• đoạn từ ID nó ra gì Như vậy y nút này
• đang bằng 1 cùng là bằng 1 đấy thì rõ
• ràng tổng t chúng ta bằng 4
• chúng ta sẽ đẩy cái
• hàng đợi chúng ta sẽ có một cái hang
• động cái hàng đã ưu tiên dq
• vào cũng là sẽ có giá trị là 4
• giá trị là 6 chúng ta dùng hàng đợi này
• để chúng ta lưu cái giá trị của cái bảng
• B là 6 cái này chúng ta Tức là lúc này
• trong cái đoạn từ A1 đến A1
• ai đến A Di thì cái giá trị lớn nhất của
• nó sẽ là 6 đúng không từ A1 đến A1 lúc
• này
• thì bây giờ bắt đầu nhé chúng ta sẽ thấy
• cái tổng tổng tên của chúng ta
• nhỏ hơn 10
• Như vậy tổng t là nhỏ hơn 10 thì chúng
• ta sẽ cần phải bổ sung thêm một cái món
• ăn bên cạnh vào để cho chúng ta mong
• muốn cho cái tổng tên nó lớn hơn tổng
• tên lớn hơn thì mới có hi vọng là lớn
• hơn 10 được
• thế thì chúng ta sẽ có gì bằng 2 tổng
• tên lúc này bằng 6
• và hàng đợi chúng ta sẽ đẩy thêm giá trị
• 1 vào
• cái giá trị lớn nhất của của khách hàng
• được ưu tiên này nó vẫn nằm ở đầu này
• chúng ta chú ý là cái giá trị lớn nhất
• nó luôn luôn nằm ở đầu đầu rãnh
• tiếp tục chúng ta sẽ xét về tổng t chúng
• ta vẫn nhỏ hơn 10 nên chúng ta phải xét
• thêm chúng ta phải bổ sung thêm vào đây
• là bằng
• y = 3 và tổng t chúng ta sẽ là bằng 11
• Tuy nhiên khi chúng ta xét đến cái phần
• tử 2 này để chúng ta đẩy vào trong hàng
• đợi ấy thì chúng ta sẽ thấy ngay là hai
• thì lớn hơn 1
• 2 lớn 1 Vậy thì
• thằng 1 này giá trị 1 này không thể là
• ứng cử viên cho giá trị lớn nhất ở phần
• phía sau này có thể nó chắc chắn là nó
• không thể là giá trị lớn nhất ở cái phần
• phía sau được bởi vì nó nó bị chặn bởi
• hai này
• ở phía sau
• thế nên ở đây kết quả ở đây chúng ta sẽ
• sẽ lưu lại chỗ này là bằng chúng ta sẽ
• đẩy cái giá trị đuổi thằng giá trị 1 này
• đi và chúng ta đẩy hai vào đây
• mẹ cho hàng đợi ưu tiên chúng ta chỉ có
• 62 thôi
• ở đây Có lẽ chúng ta cho một cái giá trị
• khác 7 đi cho nó nhỏ hơn
• đến đây thì các bạn sẽ thấy ngay là tạm
• thời kết quả của chúng ta ấy nó chính là
• bằng 6 tạm thời nhé đáp án của chúng ta
• là bằng 6
• bởi vì 3 phần tử này là tổng lớn hơn
• bằng m rồi
• và phần tử lớn nhất của chúng ta vào
• bằng 6 trong cái đoạn này
• nó chính là mở đầu hàng đợi này
• [âm nhạc]
• đến đây thì chúng ta sẽ thấy là cái tổng
• này lớn hơn 10 thì bây giờ chúng ta sẽ
• tìm cách loại bỏ bởi vì chúng ta sẽ thấy
• ngay rằng nếu như chúng ta còn
• còn cố tình bổ sung thêm phần tử này vào
• trong dãy bổ sung thêm phần tử ở trong
• dãy
• thì nó sẽ khả năng nó sẽ xảy ra như này
• có bổ sung vào ấy thì kết quả chúng ta
• vẫn giữ nguyên là 6 thôi Bởi vì 4 vẫn
• nhỏ hơn 6 đúng không kết quả vẫn là 6
• thôi nhưng nếu Giả sử chỗ này không phải
• là 64 mà là 7 nhưng vừa nãy thì cái tổng
• thì cái dãy của chúng ta lớn nhất cái
• đoạn từ đây đây là nhất là 7 mà lớn nhất
• là 7 thì chắc chắn nó cũng không vẫn
• không thể tối ưu hơn giá trị 6 trước đấy
• được vì giá trị 6 chúng ta tối ưu hơn
• đúng không nên là tốt nhất
• đến lúc này khi mà tổng là lớn hơn bằng
• m rồi Lớn bằng m rồi thì chúng ta sẽ
• loại bỏ cái phần tử ở đầu dãy này đi
• loại bỏ từ đầu ra đi chúng ta mới khóa
• học loại bỏ được cái giá trị 6 này đi để
• chúng ta tìm được cái đoạn con phía sau
• ấy nó có giá trị nhỏ hơn
• nó có giá trị mắc nhưng mà nhỏ hơn 6
• các bạn sẽ hình dung như thế vậy thì khi
• đó loại bỏ đi hết chúng ta sẽ tăng chúng
• ta sẽ trừ đi phần tử loại bỏ phần tử này
• đi chúng ta sẽ loại bỏ nó phần từ 4 Vậy
• thì nếu mà loại bỏ 4 thì cái tổng từ
• chúng ta sẽ là lấy
• khi là loại bỏ 4 thì chúng ta tất nhiên
• phải trừ cái tổng này đi rồi chỉ còn lại
• 7 thôi
• và do cái vị trí 6 này nó nằm chung với
• cả vị trí 4 nên nó cũng sẽ bị xóa ra
• khỏi hàng đợi này nó sẽ không còn ở đây
• nữa
• tiếp tục nhé sau đó thì chúng ta sẽ thấy
• ngay là chúng ta sau khi đấy thì chúng
• ta sẽ dịch Y lên đây
• bằng 2
• tổng lúc này bằng 7 rõ ràng vẫn nhỏ hơn
• m nên là chúng ta sẽ phải tăng di lên
• thành 4 và tổng ta thành 10
• khi đó chúng ta có 4 ngày được đưa vào
• trong hàng đợi thì 4 này lớn hơn 2 4 lớn
• hơn 2 nên là 2 bị đuổi ra bởi vì hai
• chắc chắn không thể là ứng cử viên lớn
• nhất trong cái đoạn này được vì nó còn
• nhỏ hơn 4 mà nên là nó sẽ bị đuổi ra
• ngoài thấy ra ngoài mà chúng ta đẩy 4
• vào
• lúc này
• đầu hàng đợi chúng ta phải là giá trị 4
• đến đây thì kết quả chúng ta lớn hơn
• bằng 10 rồi
• Vậy thì cái cách xin lỗi tổng chúng ta
• lớn bằng 10 rồi Như vậy thì kết quả
• chúng ta chính là nằm ở đầu hàng đợi này
• so với cả kết quả cũ thì đầu kết quả mới
• là tối ưu hơn
• vẫn theo cái quy tắc cũ đó là tổng lớn
• hơn bằng m thì chúng ta sẽ phải loại bỏ
• đầu à đầu hàng đợi đi hàng đầu dãy của
• chúng ta đi Tức là chúng ta sẽ loại bỏ
• phần tử 2 này đi loại bỏ phần từ 2 này
• thì dãy của chúng ta lúc này Chỉ còn kết
• quả là 8
• chúng ta tăng I đến đây thành 3
• lúc này 8 thì nhỏ hơn 10 nên là chúng ta
• phần bổ sung thêm một phần tử ở đây nữa
• thành 5 tổng là bằng 9
• và chúng ta đẩy ba vào
• ba nhỏ hơn 4 nên là chúng ta không được
• đuổi thằng 4 này đi vì ba này bị thằng 4
• này nó vẫn là phần tử lớn nhất trong
• trong cái đoạn mà nó đang xét còn 3 này
• Tại sao không Không vẫn nhảy vào đây bởi
• vì 73 để chờ chờ xem là phía sau này
• liệu nó có thể là nó là cái phần tử lớn
• nhất ở cái đoạn phía sau nó không thể là
• đoạn lớn nhất của đoạn phía trước nhưng
• vẫn có thể là chờ ở cái đoạn phía sau nó
• có thể là lớn nhất nên chúng ta vẫn nhét
• ba vào
• chúng ta tiếp tục di là tổng 9 thì vẫn
• nhỏ 10 nên chúng ta sẽ đặt vào đây tiếp
• chúng ta sẽ tiếp đến đây thì nó sẽ là 5
• sẽ là 6 tổng sẽ là 10
• thì lớn bằng mở
• thì chúng ta vẫn nhét 5 vào đây nhé 5
• chúng ta nhét vào thì bây giờ nhét là
• khi cho 5 vào thì các bạn sẽ thấy là 5
• lớn hơn 3 và đều và lớn hơn 4 như vậy cả
• hai thằng này đều bị đuổi ra khỏi đợi và
• chúng ta đẩy Nam vào đợi chúng ta đẩy 5
• vào
• khi mà m chúng ta lớn bằng 10 rồi thì
• giá trị 5 của chúng ta đây này giá trị
• lớn nhất trong cái đoạn này hiện nay nó
• là lớn nhất trong giai đoạn này
• thì tạm thời kết quả nó sẽ bằng 5 nhưng
• so với cả cái kết quả cũ của chúng ta
• bằng 4 thì kết quả cũ vẫn tối ưu hơn nên
• là cái trường hợp này chúng ta không lấy
• năm
• Vì lúc này chúng ta sẽ thấy là 10 thì
• nhỏ hơn nhỏ lớn hơn lớn 10 rồi nên là
• theo quy tắc đấy chúng ta lại loại bỏ
• cái phần tử ở đầu này đi loại bỏ phần tử
• 5 này đi
• lại bỏ năm thì chúng ta chỉ còn lại kết
• quả bằng 5
• Sau đó chúng ta sẽ có tiếp là tăng I lên
• đây
• là thành 4
• tổng này vẫn nhỏ hơn 10 nên là chúng ta
• cộng thêm cộng thêm 4 vào chúng ta dịch
• J đến đây Thành 7 cộng thêm 4 thành 9
• tổng này vẫn nhỏ hơn 10 nên chúng ta sẽ
• dịch gì lên đây
• bằng 8 Nhưng mà khi mà ghi bằng 8 có
• nghĩa là lớn hơn khỏi vượt ra khỏi cái
• dãy của chúng ta rồi vượt ra giới hạn
• của cái dãy thì lúc này chúng ta dừng
• nhé thì nó lại dừng
• kết quả chúng ta sẽ lấy ra 9 giờ bằng 4
• này chính là cái đoạn mà chúng ta cần
• tìm Đây nó chính là đoạn này
• cái chỗ này bạn này chúng ta dùng kỹ
• thuật hay quan trọng kết hợp với cả ưu
• tiên
• 6 này có phải là cộng với 5 đâu Đây có
• phải là 6 + 5 đâu
• 6 này không phải là là để cộng vào trong
• dãy nhé 6 này không phải được cộng vào
• tổng
• mà 6 này là được lưu vào trong cái hàng
• đấy hàng đợi của chúng ta
• lưu vào trong hàng đợi hai đầu này này
• chứ nó không phải là được cộng vào 6 + 5
• thành 11 đâu nhé không phải đâu là loại
• bỏ thì loại bỏ cái giá trị 4 này
• trừ đi 4 thì nó thành 7 viết tổng nó
• đang làm bằng 11 đây này khi chúng ta
• loại bỏ phần tử 4 này đi thì nó sẽ làm
• bằng 7
• thì đây là cái lời giải nó nhé thì chúng
• ta sẽ sử dụng kỹ thuật hay quan trỏ ở
• đây
• thì chúng ta sẽ gán ban đầu là bằng y =
• z = 1
• và T thì sẽ bằng A1
• sẽ chứa giá trị là cũng là A1
• [âm nhạc]
• của thầy
• như sau khi nào mà di của chúng ta
• kiểm tra nếu như t lớn hơn 1 nếu như t
• lớn hơn m bằng m
• thì cái ans cái kết quả chúng ta sẽ bằng
• mắt
• ans với cả PQ dq
• đồng thời chúng ta sẽ loại bỏ nó đi
• Thực ra đây chúng ta sẽ lưu là lưu cái
• chúng ta không lưu giá trị mà chúng ta
• lưu chỉ số chúng ta không lưu B1 mà
• chúng ta sẽ lưu số 1 sẽ lưu chỉ số ở đây
• và chỗ này sẽ là
• ở vị trí này
• thì nó lưu chỉ số lên là chúng ta sẽ
• viết là a ở vị trí này
• thì bây giờ chúng ta sẽ loại bỏ dãy này
• ra nhé loại bỏ dãy ra chúng ta sẽ kiểm
• tra là nếu như
• Nếu như cái vị trí Y của chúng ta là vị
• trí loại bỏ rồi bị loại bỏ hết Nó trùng
• với cả vị trí ở France
• thì chúng ta sẽ gán thì chúng ta sẽ cũng
• đành cái loại đã loại bỏ gì cũng sẽ loại
• bỏ cái phần tử trong
• loại bỏ cái phần tử ở đầu sau đó thì
• tăng I lên một đơn vị
• sau đó là chúng ta tăng in lên một đơn
• vị
• chúng ta sẽ khi mà chúng ta tăng dư lên
• đấy thì chúng ta nhớ rằng là khi tăng di
• lên một vị trí nào đấy
• thì chúng ta sẽ cần truyền kiểm tra xem
• là cái phần tử
• nó nó có lớn hơn những cái phần tử đứng
• sau ở trong hàng đợi đấy không Nếu nó
• lớn hơn
• khi nào chúng ta sẽ dùng một cái phòng
• này khi nào
• mà thằng Lợi của chúng ta khác rỗng
• và
• A và B ở vị trí là
• PQ chấm back
• nhỏ hơn
• nhỏ hơn hoặc bằng
• thì chúng ta sẽ có là PQ
• pq.
• tức là loại bỏ phần tử ở cuối
• sau khi lại bỏ phần tử cuối rồi chúng ta
• mới đẩy nó vào trong
• là
• [âm nhạc]
• dqs
• đẩy vào cuối của hàng đợi ưu tiên này
• Đồng thời chúng ta sẽ khám t bằng t cộng
• với cả BJ ta cộng với aj
• thì cái đoạn code Đây là thời gian là
• bạn có mô phỏng Thôi về chúng ta sẽ phải
• tự biến đổi như một tí
• đối từng với ngôn ngữ cho nó phù hợp
• chúng này ở đây chúng ta sẽ hiểu rằng có
• những cái
• mà đầu nhé phía đầu
• hàng đợi dq
• rồi là chúng ta có pop
• fan
• loại bỏ phần tử ở đầu dq
• Bách
• là loại bỏ phần tử ở cuối
• thế quy
• thì chúng ta sẽ căn cứ vào đó thì chúng
• ta có thể về Cốt lại cho nó phù hợp hoặc
• các bạn có thể tham khảo cái cốt của
• thầy ở trong lớp 9 sử dụng cộng và
• Python
• Thực ra bài này là một cái bài khó đấy
• Thực ra nếu các bạn không biết về là hài
• về về
• hai con trỏ hoặc là không biết dùng biết
• không biết dùng để cứu này là các bạn sẽ
• không giải cái bài này
• có ai hỏi gì nữa không
• thực hành khó hiểu quá thì phải tự
• nghiên cứu cốt Thôi
• tự nghiên cứu thôi chứ còn để mà hiểu
• được thì cần phải có những kỹ năng Cốt
• và tư duy cốt nữa
• để có được các bạn đều phải biết là mình
• phải có tư duy để tư duy lập trình này
• cộng với kỹ năng này kỹ năng lập trình
• này nó lấy ra hai cái yếu tố Nếu như các
• bạn mà bị yếu một trong hai yếu tố này
• thì thì các bạn sẽ khó để có thể code
• được
• hoặc là sẽ khó mà có thể hiểu ngay được
• cái code của người ta nên các bạn phải
• về nghiên cứu lại cái code mẫu đấy
• Từ ý tưởng mình đã nói là từ thầy nói là
• từ ý tưởng để đi thuyền code một bài
• toán
• nó là cả một quãng đường dài
• nó là cả quãng đường dài chứ không phải
• là nghĩ ra ý tưởng là xong nó không như
• các môn Toán những cái môn học khác sản
• phẩm của chúng ta là một cái chương
• trình đúng không cái chương trình này để
• thể hiện cái ý tưởng của chúng ta Còn
• nếu như mà chúng ta chỉ có ý tưởng mà
• chúng ta không có sản phẩm thì chúng ta
• cũng không giải quyết được cái bài gì
• vấn đề gì cả vì người ta chấm là chấm
• trên sản phẩm sản phẩm của chúng ta
• chính là cái chương trình này này
• là chúng ta phải lưu ý cho thầy
• là chúng ta cần phải rèn luyện kỹ năng
• về code kỹ năng lập trình
• thực ra các bạn Nếu mà đi thi mà được
• giải hộ sinh giỏi cấp tỉnh thì các bạn
• rất là thuận lợi trong việc vào lại
• thẳng đại học
• chắc là các bạn nghe qua cái vấn đề trên
• vừa rồi đấy Các trường đại học bây giờ
• người ta không cần cái điểm tốt nghiệp
• của các bạn đâu
• điểm cao mấy các bạn vẫn chưa chắc đã đỗ
• được vào những trường tốt đầu
• nhưng mà người ta lại cần những cái giải
• học sinh giỏi Ví dụ như sinh sản môn Tin
• là một thứ mà các cái ngành về công nghệ
• thông tin người ta rất cần
• người ta cần người phù hợp với cái
• chuyên ngành của người ta chứ người ta
• không cần người giỏi trong những thời
• thiếu nghiệp đấy nên các bạn phải lưu ý
• Nếu các bạn muốn vào những cái chuyên
• ngành top đầu cố gắng mà thi lấy giải
• sinh giỏi
• 24
• bài 4 này có vẻ là một cái bài hơi khác
• lạ
• Nhưng mà thực ra nó cũng là một bài quen
• với các bạn thôi không phải là lạ đâu
• nếu các bạn đã được học về
• Quỳnh động
• và các bạn đã
• giải được một số bài toán cơ động cơ bản
• đã học được học những cái bài toán huy
• động cơ bản như là bài toán cái túi bài
• toán sinh ra mọi tầng
• hay là bài toán tìm một cái đoạn con có
• tổng bằng S thì cái bài toán này nó là
• áp dụng kiểu bài đấy thôi
• chúng ta có n Quân Domino đúng không và
• các Quân Domino này chúng ta thì chúng
• ta đã biết là Domino hay là những mắc cờ
• mà nó có
• nó vào cái hình chữ nhật kích thước là 2
• x 1 và trên này thì có
• ta gọi là ai
• các cái dấu chấm ở đây
• kiểu như này đúng không Ví dụ là 123 như
• này
• thì khi mà người ta xếp các quân cờ và
• thành một cái hàng ngang
• và người ta tính tổng phần tử của cái
• hàng ghế trên và tổng hàng phía dưới ta
• gọi là T1 và T2
• vấn đề của chúng ta đặt ra câu hỏi của
• đặt ra đó là chúng ta cần phải xoay các
• quân cờ domino này theo một cái góc 180
• độ tức là xoay ngược lại
• với số lần xoay ít nhất chúng ta sẽ chọn
• ít quân cờ domino nhất để xoay sao cho
• tổng hàng trên và tổng hàng dưới là
• chênh lệch càng ít càng tốt
• bây giờ chúng ta chỉ cần xoay một tuần
• trong đề bài này chúng ta có quân thôi
• đó là chúng ta sẽ xoay đến cái Quân cuối
• cùng này
• ta sẽ thấy ngay cái hàng trên chúng ta
• là 6 hàng dưới là 1 1 5 1 3 1 2 tổng lúc
• này bằng 9
• còn tổng dưới này là 11 đúng không
• Thì nó sẽ trở thành 2 1
• 10 như vậy cũng chênh lệch là bằng 0 và
• chúng ta cần phải xoay ra một quân cờ
• kết quả chúng ta là 0 1
• [âm nhạc]
• thì đầu tiên nhé chúng ta sẽ có cách
• như sau phương pháp bị động chúng ta sẽ
• giải như thế
• chúng ta gọi fij
• một cái mảng 3 chiều như thế này Tí nữa
• chúng ta sẽ có kích thước này xuống
• là bằng
• số quân cờ domino xoay ít nhất
• xoay ít nhất
• khi xét đến quân cờ Thử Y
• và tạo ra tổng
• ở trên bằng di
• tổng ở dưới
• là k
• và f ij bằng số quân cờ domino xoay ít
• nhất khi xét đến quân cờ thú y
• và cho ra được cái tổng ở phía trên đầu
• J và tổng ở phía dưới là k
• cải tạo ban đầu thì chúng ta có f00
• là bằng 0 đúng không còn tất cả những
• giá trị fica khác là bằng dương vô cùng
• em không không có nghĩa là chúng ta
• không có quân cờ domino nào
• để tạo ra tổng bằng không và
• tổng trên bằng 0 và tổng thể bằng 0 đúng
• không Đây là kết quả để chúng ta không
• phải xoay con cờ domino nào cả
• Bây giờ chúng ta xét
• Quân cả Domino hội thiếu nhi n
• và chúng ta xét cái Quân xét cái tổng Di
• bằng 1 cho đến
• 6 x n chúng ta sẽ thấy ngay là tổng ở
• phía trên ấy tổng hàng trên ấy thì nó sẽ
• tối đa là đến
• 6 x n đúng không tổng phía trên là tối
• đa 60n và tổng ở phía dưới K chúng ta
• cũng xét là từ 1 đến 6 nhân n ở phía
• dưới
• chúng ta kiểm tra là nếu như fijk
• nhỏ hơn dương vô cùng
• xảy ra có nghĩa là chúng ta có thể đã
• xoay được một cái quân cờ nào đó hoặc là
• chưa Xoay được quân cờ nào Nhưng mà
• khi đói chúng ta sẽ có
• fy + 1
• chúng ta sẽ có hai trường hợp nhé Trường
• hợp là xoay mà không say
• Nếu không xoay
• quân cờ domino này chúng ta sẽ có f i +
• 1
• Nếu không xoay thì chúng ta sẽ tạo ra
• thì khi chúng ta có được quân cờ domino
• từ k + y + 1 đấy thì chúng ta sẽ
• đâu nhỉ
• thì nó sẽ bằng cái
• fijk này
• còn nếu xoay
• Nếu xoay thì lúc này Fi +
• 1B nó sẽ nằm ở phía trên
• và nó sẽ bằng fijk cộng 1 đơn vị
• mà ra được như này rồi thì chúng ta cái
• kết quả chúng ta sẽ là cái gì
• sau khi tính xong hết rồi thì chúng ta
• duyệt cái vòng là for
• Nếu Như
• F là njk
• [âm nhạc]
• tức là chúng ta nhỏ hơn dương vô cùng
• ở đây chủ nghĩa là chúng ta xét đến ghế
• rồi thì bây giờ chúng ta chỉ cần duyệt
• các cái tổng này và tổng là nhỏ âm dương
• vô cùng Có nghĩa là nó nó có thể tạo ra
• được cái tổng này nếu mà bằng dương vô
• cùng có nghĩa là không được tạo ra
• thì khi đó
• chúng ta sẽ kiểm tra là nếu lúc này ars
• của chúng ta là cái luật chênh lệch
• chúng ta sẽ đặt là dương vô cùng arf này
• chính là độ chênh lệch giữa hai phần y
• và j nhé chúng ta kiểm tra là nếu
• ans chúng ta mà lớn hơn trị tuyệt đối
• của j - k đây là chính là độ chênh lệch
• giữa hai phần đấy thì lúc này ans
• sẽ bằng J trị tuyệt đối của j - k
• Và khi đó thì cái xoay của chúng ta cái
• kết quả số lượng xoay của chúng ta nó sẽ
• bằng f ijk fn JK
• Còn nếu Ngược lại
• nếu như ans mà chúng ta bằng với cả
• nếu điều này xảy ra mà bạn
• thì khi đó
• chúng ta sẽ có sai số lượng xay chúng ta
• phải là ít nhất mà sẽ bằng min của xoay
• với fnjk
• và kết quả của chúng ta thì chúng ta in
• ra
• ans và giá trị số lượng quân cờ Xoay
• về mặt kích thước chúng ta sẽ thấy cái
• bảng của chúng ta cái bài toán này thì
• độ phức tạp nó sẽ là
• n nhân với cả
• 6 lần n
• nhân với 6 lần n tức là bằng
• 36 lần của n mũ 3
• thứ nhất cái thứ hai thứ hai là chúng ta
• sẽ thấy ngay là cái
• cái kích thước của cái bảng của chúng ta
• cũng tương đối là lớn chúng ta cũng có 3
• chiều một chiều là n một chiều là 6 lần
• n một chiều nữa là 6 lần như vậy về kích
• thước cũng là mất 6 lần n mũ 3
• Vậy thì cách này của chúng ta mặc dù nó
• đúng đấy nhưng mà nó không tối ưu được
• thứ nhất là không tối ưu về mặt không
• gian bộ nhớ của máy tính thứ hai là
• không tối ưu được về mặt thời gian
• vậy thì chúng ta cần phải giảm cái kích
• thước thì chúng ta phải tìm cách là tăng
• cải tiến cái cái bài bán này đi để cho
• chúng ta nó có cái bài toán nó tốt hơn
• cách giải nó tốt hơn
• chúng ta sẽ xem đến Cách thứ hai
• hàng trên và hàng dưới
• chúng ta sẽ thấy là nếu
• biết được tổng trên
• thì suy ra được tổng dưới
• tức là nếu chúng ta biết được thì chúng
• ta sẽ có thể suy ra được ngay ở tầng
• dưới
• khi đó trường quy định chúng ta sẽ được
• giảm như sau chúng ta gọi
• fij
• số Quân Domino size ít nhất
• để tổng hàng trên là bằng gì
• khi xét đến quân cờ Thử Y
• ES
• thì khởi tạo ban đầu là
• f00 thì cũng bằng 0 thôi Còn tất cả
• những cái giá trị f ij khác đều đều bằng
• dương vô cùng
• để chúng ta pho chúng ta duyệt
• các quân cờ i từ
• 1 cho đến con cờ thấy n
• sau đó là chúng ta duyệt tiếp
• giá trị J chúng ta cũng bằng 1
• Thực ra chúng ta cần
• duyệt từ 1
• chúng ta duyệt thẳng từ ai
• cho đến n đây trường hợp này trường hợp
• là không xoay
• quân cờ
• nhất
• không say thì không say thì chúng ta sẽ
• tính của ai nhé Ai lúc này là nó vẫn nằm
• ở hàng trên
• đầu tiên bước đầu tiên là chúng ta sẽ
• không xoay nhé thì chúng ta sẽ tính ở
• trên khi đó thì do không xoay nên là F
• ij
• của y - 1
• Duy trừ đi ai
• trường hợp là xoay thì chúng ta lại
• duyệt một lần nữa là di từ bằng bi
• đến 6 lần n đây trường hợp là xoay quanh
• cơ
• y trong trường hợp này thì chúng ta có f
• ij
• -1
• di trừ đi bi
• và chúng ta cộng thêm một con cờ xanh cờ
• thú y
• Nếu không xoay thì nó sẽ như thế là xoay
• thì nó sẽ là giữ ở dưới
• thì khi đó chúng ta sau khi xong rồi
• chúng ta sẽ duyệt Tiếp Để Tìm kết quả
• nhé Bây giờ chúng ta xong cái quy động
• Đây Rồi bây giờ chúng ta sẽ duyệt các
• quân cờ chuyển các cái tổng của Tổng di
• từ 1 cho đến 6n
• thì đối với tổng gì thì chúng ta sẽ có
• cái giá trị tổng ở dưới hàng dưới là k
• bằng f - DJ
• và chúng ta kiểm tra nếu như
• kết quả chúng ta mà lớn hơn trị tuyệt
• đối của Duy trừ K
• thì chúng ta sẽ làm hai việc đó là ans
• chúng ta sẽ bằng trị tuyệt đối của j - k
• độ chênh lệch Còn cái số lượng quân cờ
• xoay nó chính là bằng f ở vị trí ng
• ở đây chúng ta quên mất là chúng ta phải
• kiểm tra là nếu như ép
• n y nj là nhỏ hơn dương vô cùng
• trường hợp ngược lại là nếu như
• ans của chúng ta mà bằng với trị tuyệt
• đối của Duy trừ K ấy thì lúc này là
• chúng ta sẽ phải tìm số quân cờ xoay ít
• nhất đúng không
• sai sẽ bằng
• min của
• xoay với fnc
• kết quả chúng ta sẽ in ra
• alf và
• số từ Cần Xoay
• đấy chính là cái bài toán cực động giải
• dài về toán này đa số các bạn đều Chưa
• giải được cái bài toán này
• chúng ta sẽ có một cái
• [âm nhạc]
• chúng ta sẽ là 01234
• 1234567
• 8
• 9 10 11 12
• đầu tiên nếu như chúng ta mà xoay mà
• không xoay nó nhé Nếu không xoay thì kết
• quả tại cái dòng này nó sẽ bằng một là
• bằng không chỗ này
• thì cái tổng phía trên nó bằng 6 mà tổng
• là ô phía trên nó sẽ là 6 vì
• tổng ở phía trên nó sẽ bằng 6 về không
• xoay
• thì rõ ràng là lúc này là F16 là bằng
• không xoay con cờ này nhưng nếu chúng ta
• xoay thì phải tổng phía trên ấy lúc này
• nó chỉ bằng một thôi thì chúng ta xoay
• lại con cờ này thì dưới là một hay lên
• trên thì lúc này tại cái dòng tại cái
• cột 1 này nó sẽ bằng 1
• ở đây mình quên mất là có một cái
• điều kiện đó là nếu chỗ này nữa nhé
• tạo thêm một cái điều kiện đây là fg-
• Nếu ép
• nhỏ hơn bằng 0 và nhỏ hơn giữa vô cùng
• ở dưới này là Fi
• trừ 1
• Dưới đây sẽ là f i trừ 1 của
• J -by
• Chan ở đây nó đây là đơn giản nó hơi khó
• nhìn một tí các bạn cố gắng theo dõi
• vô cùng
• trường hợp thứ hai dòng thứ Hai
• nhé Nếu nó không say thì nó không xoay
• thì chúng ta sẽ thấy ngay là chúng ta có
• thể tạo ra tổng bằng 7
• tức là lấy 6 này cộng với 1 này thì
• chúng ta không say nào cả Đúng không
• hoặc là chúng ta sẽ có thể tạo ra tổng ở
• phía trên là bằng 2
• tức là gì Tức là chúng ta đã xoay con cờ
• phía trên này thành một 6 bây giờ chúng
• ta sẽ cộng thêm với con g này vào nữa
• thì có thể là tổng bằng 2 không đúng
• không có nghĩa là lúc này chúng ta xoay
• một con cờ đi
• xay là xay của cánh cửa từ trên nhé Thế
• còn nếu chúng ta xoay con cờ này thì 51
• Nếu chúng ta xoay bên cửa 51 thì chúng
• ta sẽ ra được tổng bằng
• Nếu chúng ta xoay quanh cờ này nhưng
• không xoay Chân Quân Cờ Không xoay ở đây
• thì chúng ta sẽ được là 6 cộng với 5
• thành 11 tức là chúng ta sẽ mất một lần
• xoay
• xoay là Xoay cái quân cờ phía dưới này
• này
• hoặc là chúng ta xoay ở bên cà phía trên
• và xoay cả con cả phía dưới thì tổng sẽ
• là bằng 6 thì ta mất 2 lần sai sai cả
• trên ở dưới
• áp dụng đúng cái công thức như thế này
• thì chúng ta sẽ điền ở một cái bảng này
• bây giờ giải thích cái bảng này điền như
• thế nào thì nó sẽ rất mất thời gian nếu
• không say nhé Nếu không xoay chúng ta sẽ
• được là 11 cộng với cả 10 cộng với 1 này
• thành 12 thì chúng ta sẽ được là bằng 0
• này bằng 1 này chúng ta đang nói không
• sai nhé Còn chỗ này sẽ là bằng 7 + 1 8
• là sẽ bằng 0 này tại dòng cái cột số 8
• này còn nếu là nếu không xoay tại cái
• cột Thứ 7 này thì sẽ là 2 cộng với là 6
• cộng với 1 thì bằng 7 thì ta xoay mất
• hai quân cờ Nếu chúng ta sẽ quân cờ thì
• chúng ta sẽ được là 1 + 5 + 1 đây mà
• chúng ta sẽ mất 2 con cờ đến đây thì
• chúng ta sẽ say mất một quân cờ tổng sự
• vòng 3
• xin lỗi thảo mộc cái cột 3 này
• nếu như chúng ta xoay nó thành 31
• thì chúng ta sẽ lấy là 11 này cộng với
• cả 3 thì 14 Vậy chúng ta xoay 2 quân
• chúng ta lấy là 11 cộng với cả 3 thành
• 14 nhé Còn ô này sẽ là 7 + 13 thành 10
• thì ta không Chúng ta say mất một quân
• chỗ này sẽ là 6 cộng với 3 thành 9
• xoay 3 quân ô này ô này là hai cộng với
• cả ba bằng 5
• ta sẽ có được là xoay hai quân
• thứ tư Nếu không xoay không xoay thì
• tổng sẽ là bằng
• set Cái ô này
• muốn cộng với một thành 15 thì chúng ta
• không xoay thì chúng ta sẽ mất xoay hai
• quân cờ ở phía trên
• đến ô này là 12 cộng với cả 1 thành 13
• thì 1 chúng ta say một quân cờ ở phía
• trên phía ô này thì tổng là 10 cộng với
• cả 1 thành 11 và chúng ta xoay một công
• thợ phía trên
• ô này chúng ta có tổng
• chúng ta chỗ này phải là Min
• giữa
• chị này với cả FPT
• đây là Min Fi
• nếu mất cái chỗ Min này nữa
• thì các bạn cái điện vào cái công thức
• này thôi Đến ô này thế này là 9 cộng với
• cả 10 Thành
• 9 + 1 thành 10 thì hôm này chúng ta sẽ
• xoay 3 phân ở phía trên đây là chúng ta
• không xoay quân nào cả 8 + 19
• [âm nhạc]
• thực tế cả hai thành 12 là mất xe mất 2
• Quân thì ông này là 9 cộng với 2 thì 11
• Thì xoay mất 4 Quân thì so với cả một cũ
• thì một tốt cũ tốt hơn
• chỗ ô này là 88 cộng với cả 10 8 cộng
• với 2 thì bằng 10 Thì xoay mất một quân
• một thì tốt hơn cũ giá trị cũ là bằng 3
• thì chúng ta cứ điền vào thôi ô này là
• bằng 2 cộng với cả hai nữa thì bằng 4
• bằng xin lỗi là 7 + 12 = 9 thì chúng ta
• xoay mất 3 Quân nhưng mà so với giá trị
• không thì không tốt hơn đấy tương tự như
• thế Chúng ta sẽ điền nốt ở chỗ này là 5
• + 2 = 7 thì chúng ta xoay là 3 này 3 +
• này chúng ta say là 2 này thì kết quả
• chúng ta sẽ nằm ở đây này Kết quả nào
• dưới đây lúc này là giá trị J là giá trị
• mà độ chênh lệch là nhỏ nhất tại vị trí
• này là chúng ta có một Quân bị xoay và
• độ chênh lệch giữa hai bên là bằng 0
• vì tổng là bằng 20 20 và cái độ chênh
• lệch tại lúc này thì chúng ta say mất
• một quân lệch thì bằng 0 hoặc ta xoay
• một cân này
• Nói chung là các bạn phải hiểu là cái ý
• tưởng này trước
• Đây là cái bài thực hành
• khó hiểu thì bây giờ phải về nhà mà xem
• lại thôi
• việc đọc là như thế mà nếu mà không hiểu
• về
• nếu mà sinh ra được các cái tổ hợp chập
• K của n trong trường hợp là
• sinh ra Nhị sâu nhị phân nhé thì chúng
• ta ăn được 50% điểm
• 50% điểm tức là chúng ta cắt sâu nhị
• phân
• với các sâu nhị phân thì các bạn sẽ
• sinh ra các show nhiệt phân với nghĩa
• như thế này
• trong đó thì xy = 0 Nếu mà không xoay
• còn XY = 1 có nghĩa là xoay luôn
• cái là xoay hay là không xoay
• có vẻ bạn học sinh động chưa đến nơi rồi
• chưa đến nơi
• đối với quê động là có hai cái hai cách
• làm một là cách triển khai từ trên xuống
• dưới và cách triển khai từ dưới lên trên
• các bạn bạn mới học theo một cách nào đó
• thôi cái cách dùng pi để quy thôi và
• cách dùng bằng dq này thì là rất là khó
• ở mức được
• rất là khó để mất Chỉ khi nào thật thành
• thạo về
• lệ quy bạn mới có thể code bằng định quy
• được
• còn cách dùng bạn bao giờ cũng dễ tốt
• hơn
• bao giờ dễ có hơn và dễ đập bất Nếu mà
• có sai thì ta tìm lỗi nó cũng dễ dễ hơn
• cái đệ Quy nó có cái nhược điểm lớn đó
• là chúng ta rất khó ở Bắc để tìm lỗi
• và có lẽ là bạn học vẫn chưa tới nơi để
• trốn về bị động nên bạn nghĩ là tự động
• nó chỉ có mỗi người dùng đệ quy
• dùng đệ quy đó là cách phân tích từ trên
• xuống dưới đó là cách người ta gọi là
• cách top down còn một cách khác đó là
• tiếp cận theo từ dưới lên trên và bắt
• từng áp nó là dùng Chính là dùng mạng
• hoặc Đây là cách triển khai dùng mảng là
• cách triển khai dễ dễ dàng hơn rất nhiều
• so với Cách triển khai bằng đệ quy
• Nếu các bạn code sai cái là thì các bạn
• sẽ không khó để mà có thể đã mất để tìm
• ra lỗi đấy là cái khó của đệ quy
• các bạn sẽ còn vấn đề gì không
• và các bạn đã biết là Lệ Quyên thường là
• chạy rất là chậm rồi
• chạy rất là chậm vì Lệ Quyên nó sẽ hết
• cả các trạng thái
• Thầy đã gửi code và test cho các thầy cô
• giáo của các em nhé
• các em cứ hỏi các thầy cô giáo của các
• em thôi thầy cô giáo em đã nhận được
• test và nhận được code Thầy gửi rồi đấy
• trong cái test mà của thầy thì có cốt
• kèm theo rồi
• đường phố
• [âm nhạc]
• [âm nhạc]