Тэмцээн 2016 бодолтууд

За тэмцээнд оролцсон бүх оролцогчиддоо их баярлалаа. Сайн байсан шүү та нар бүгдээрэй.



Шууд анализдаа ороё. Мөн C++ код тавьлаа. Аль болох ойлгож мөн хэлнийхээ мэдлэгийг сайжруулах үүднээс ямар асуудлыг яаж шийдэж гэдэг байдлаар код уншаарай. Амжилт



Bodlogo 1

Байж болон хамгийн том тоо 10^9 - г хоёртын тоололруу шилжүүлэхэд 30-н оронтой тоо гарна. Гуравтын тоололд шилжүүлэхэд мөн хамаагүй бага оронтой тоо гарна. Бүх боломжийг шалгахад O(2*30*30) аас ихгүй үйлдэл хийнэ, энэ хугацаандаа хангалттай амжих бодолт. Гол асуудал нь дурын тоо өгөгдөхөд хоёртуу мөн гуравтын тоололруу шилжүүлдэг байх хэрэгтэй.

source



Bodlogo 2

Энэ бас л шууд хэлснийг нь хийхэд болох бодлого. A олонлогоо шууд эрэмблэе. Одоо M тоон дарааллын C урттай дараалалсан гишүүд болгоныг тусад нь эрэмбэлээд A олонлогийн харгалзах дугаартай элементүүдийн зөрүү бүгд тэнцүү байх ёстой. Бодолтын хугацаа O(10*N) = O(N).

source



Bodlogo 3

Рекурс ашиглаад хоёр арлаа 0, 1-ээр ялгаад будчиж чадна. Үүсэх графын хязгаарлалт бага тул шууд бүх хоё 0 1-үүдийн хоорондох зайг олоод хамгийн багыг авчихад болно.

source



Bodlogo 4

Бас л шууд хэлснээр нь хийгээд шалгачина. Нэг асуудал нь тухайн толь дээр хаанаас нь ирснийг мөн ямар толь байвал хаашаа явахыг нь яаж мэдэх вэ? тухайн ямар нэгэн x гэсэн нүдний хувьд чиглэлүүдийг нь дараах байдлаар тодорхойлоё.

  2

3x1

  0

Одоо bounce1[i]=k-аар '/' ингэж тавьсан толинд i чиглэлээс ирэхэд к чиглэлрүү явна гэдэгийг нь тэмдэглэе.  Мөн bounce2[i]=k-аар '\' толинд i чиглэлээс ирэхэд к чиглэлрүү явахыг тэмдэглэе.

Мөн xx[]={1, 0, -1, 0}, yy[]={0, 1, 0, -1} энэ хоёр массивыг ашиглаад x+xx[k], y+yy[k] гэсэн k чиглэлрүү очиж чадна.

source



Bodlogo 5

dictionary дахь үгнүүдийг өөрийх нь байрлалтай нь хамт хадгалаад үгнүүдийх нь хувьд эрэмбэлэе. prefix үг орсон байх үгний хамгийн эхнийхийг нь хоёртын хайлт хийж дугаарыг нь олоод k-г нэмэхэд гарах үгний prefix нь манай хайж байгаа prefix-тэй тэнцүү байна уу гээд шалгачина. Бодолт O(NLogN+q*LogN).

source



Bodlogo 6

Ямар нэгэн түвшинд байгаа (x, y) цэг нь дараагийн түвшиндээ (2*x, 2*y) координадтай болно

source



Bodlogo 7

Энэ бол "two pointers" гэх ангилалд орох сонгодог бодлого. start, end гэх интервал аваад явъя. Тухайн өнгийг одоогийн интервалд хэд орсныг нь мөн тоолно. Бүх өнгө ортол end=end+1 гэе. Одоо start дээр байгаа өнгийг хассан ч бүх өнгө ядаж нэг орсон байвал start=start+1 гээд байя. Одоо end-start манай хариу байж магадгүй тул өмнө олсон хариунаас их бага эсэхийг шалгаад болоо.

source



Дараагийн маш сонирхолтой бодолт бол өнгө болгоны хувьд хамгийн сүүлд олдсон байрлалыг нь хадгалаад явна, A-д хадгалав. Өнгө бүрийн хувьд хамгийн анхны утга нь -INF байг. Одоо бөмбөлөг байгаа цэг бүрийн хувьд эхнээс нь гүйх ба (х цэг) тухайн өнгөний байрлалыг нь шинэчилчээд үүний дараа A-н хамгийн бага утгыг олоод min гэе. x-min манай бодлогын хариу байж магадгүй. Тэгэхээр энэ бодолтын хувьд A-г шинэчлэх мөн хамгийн бага утгыг хангалттай хурдан олж чадвал, heap, O(NLogN)-д бодогдно.

source

Гэвч дээрх хоёр бодолт хоюулаа хамгийн эхний үйлдэл нь цэгүүдээ эрэмбэлэх тул O(NlogN)-г би дурьдсангүй шүү



Bodlogo 8

Энэ бодлогын хариуг бид олохын тулд хоёр зүйлийг минимумчлал ёстой.

1: Аль ч аралд харьяалагдахгүй бүх цэгийн 3-н арал хүртлэх зайнаас хамгийн багыг нь олоё. Үүнийг 3*2500-д олж чадна. Үүнийгээ m1 гэе

2: 1-р арлаас 2-р арал хүртлэх хамгийн богино зайг (1, 2), 2-оос 3-г (2, 3), 1-ээс 3-г (1, 3) гэе. Энэ 3-н аль нэг хоёрын нийлбэр нь мөн манай хариу болж магадгүй, үүнийг m2 гэе. 2500^2-д олж чадна



Бодлогын хариу min(m2, m1).

source



Bodlogo 9

Энэ бол dp. Best[i][j]-ээр i гэсэн тоог 1..j хүртлэх гишүүдийг ашиглан зардал хамгийн бага байлгахыг тэмдэглэе. Тэгвэл Best[i][j] = min(k-A[k])^2+Best[i-k*k][j-1], (1..k k*k<=i)

source



Bodlogo 10

Энэ бодлогыг та бүхнийг өөрсдөө дахин сайн нухаж бодохыг хүсэж байна. Ер нь ямар нэгэн бодлого дээр 24-н цаг суугаагүй л бол хэцүү бодлого гэж хэлэхгүй шүү



За асуух юм байвал комментоор асууж бариараа. Амжилт хүсье.