Мэдээлэл зүйн улсын олимпиад, сурагчидын 2 дугаар өдрийн бодлогын бодолтууд

Бүх оролцогчидод баяр хүргье. Мундаг байсан шүү та нар.



Өөрийн бодолтоо анализын хамт сонирхуулая:



1-р бодлого:

Өгүүлбэр: Утгаараа мянгаас хэтрэхгүй N (N<=10^6) ширхэг тоон дараалал өгөгдсөн. Q (Q<=10^1) ширхэг хүсэлтэнд хариулах ба энэ нь дээрх дарааллын A, B индэкс завсарт байрлаж байгаа тоонууд дунд хамгийн их давтагдсан, хамгийн бага давтагдсан мөн нийт хичнээн ялгаатай тоо байгааг олох юм байна. Жишээнээс тодорхой форматыг нь харна уу

input:

10

5 5 5 5 6 4 1 2 20

3

mn 1 10

mx 1 10

ct 1 10

output:

1

5

7



Анализ:

Миний хувьд энэ бол хоёр дахь өдрийн хамгийн хүнд бодлого. Гэхдээ, нийт хүсэлтийн тоо хамгийн ихдээ 10, утгаараа тоонууд нь мянгаас бага гэхээр хүсэлт болгонд A-аас B дунд гүйгээд тоолчиж болно. Тоолохдоо a[1000] урттай массив авж байгаад i гэсэн тоо орж ирвэл a[i]++ нэмээд байна гэсэн үг. Хүсэлт болгонд A=1, B=10^6 байж болох тул O(N)-д хариулна. Нийт бодолтын үнэлгээ O(Q*N) буюу 10-н сая үйлдэл хангалттай 0.3 секундэд амжиж байгаа юмшиг байна.

O(M*Q*logN) бодолт сонирхоё, мөн бичихэд маш хурдан нь.

1...M ширхэг массив авая. Тухайн k дугаар дахь массив бүрт уг к тоо маань хэд хэд гэсэн индекст байрлаж байгааг нь хадгалчия. Яг орж ирсэн дарааллаар нь массивын араас нь элементээ нэмээд явахад эрэмблэгдсэн массив үүснэ. Тэгвэл одоо хүсэлт A B орж ирэхэд бүх массив дотор хоёртын хайлт хийнэ. Ойлгомжтой болгохын үүднээс зөвхөн макс-г нь олоё. lower_bound(left, right, k) функц нь к дахь массивт (left, right) завсарт багтах тоонуудын хамгийн багых нь дугаарыг олно.

upper_bound(left, right, k) нь уг завсарт багтах тоонуудаас хамгийн ихийх нь дугаарыг олно.

Одоо ингээд dif = upper_bound(left, right, k)-lower_bound(left, right, k) - г бүх k-н хувьд минимумчилна гэсэн үг.

source - хоёртын хайлтыг чөлөөтэй бичдэг байх хэрэгтэй шүү!



Бодлого 2:

Өгүүлбэр: дараах байдлаар нийлбэрийг задласан юм байна. Аль нэгэн нийлбэр нь өгөгдөхөд доорх нийлбэрийг нь ол.

Анализ: нийлбэр үүсгэж байгаа гишүүдийг нь эхнээс нь массивт хийцэн гэж үзье. Зөрөө нь хоёроос их байх хамгийн эхний дараалсан хоёр гишүүний олъё k, k+1 гэе. Уг хоёр гишүүн хүртлэх гишүүдийн нийлбэрийг мэднэ гэж үзье. Одоо к дахь гишүүнээ нэгээр нэмэгдүүлээд уг хоёр гишүүн хүртлэх гишүүдийн нийлбэрийг бүх гишүүдийн нийлбэрээс хасая diff гэе. Одоо бид diff-г аль болох урт мөн хамгийн эхний гишүүн нь k дахь гишүүнтэй тэнцүү байхаар задлана гэсэн үг. Бодолтоос дэлгэрэнгүй харна уу.

source

Бодлого 3:

Зөвхөн N ширхэг 1 байхад хэд гэсэн тоог гаргаж авч чадах вэ? N*(N-1)/2

Зөвхөн M ширхэг -1 байхад хэд гэсэн тоог гаргаж авч чадав вэ? M*(M-1)/2

Одоо тэгвэл N ширхэг 1 мөн M ширхэг -1 байхад хэд гэсэн тоог гаргаж авч чадах вэ?

N*(N-1)/2 + M*(M-1)/2 - N*M.

S өгөгдөхөд S=N*(N-1)/2 + M*(M-1)/2 - N*M байх M-г ол гэсэн бодлого. N, S-г мэдэж байгаа тул квадрат тэгшитгэл бодоод M-г олно. Гарсан хоёр язгуурын аль нь манай хариу болж болох бол? бодоод үзээрэй.

source



За нэг иймэрхүү. Надад эхний өдрийн бодлогууд олдвол ингээд анализ хийчиж болох л байх.