2-деңгээл. Иреттөө жана издөө

Дээрлик ар бир олимпиадалык маселеде кездешүүчү классикалык ыкмалар: иреттөө, эки көрсөткүч, префикстик суммалар жана бинардык издөө.

Бул деңгээлдин төрт ыкмасы — бардык олимпиадалардын жумушчу аттары: курал катары иреттөө, эки көрсөткүч, префикстик суммалар жана бинардык издөө. Баштапкы деңгээлдеги дээрлик ар бир «зээндүүлүккө» деген маселе алардын бири же айкалышы менен чечилет. 3-деңгээлге даярдыктын критерийи: бул ыкмаларды бейтааныш маселелерден тааныйсыз — «иреттелген массив жана түгөйлөр» эки көрсөткүчкө, «көп сумма суроолору» префикстерге, «мүмкүн болгон минималдуу X» жооп боюнча бинардык издөөгө багыттайт.

Бул бөлүмдө

  1. 1
    Иреттөө алгоритмдери

    Иреттөө курал катары: std::sort, компараторлор, структураларды иреттөө.

  2. 2
    Эки көрсөткүч ыкмасы

    Эки көрсөткүч ыкмасы: берилген суммадагы түгөйлөр жана O(n) убакыттагы жылма терезе.

    1 маселе

  3. 3
    Префикстик суммалар

    Префикстик суммалар: «кесиндидеги сумма» суроосуна O(1) убакытта жооп; айырма массиви.

    1 маселе

  4. 4
    Бинардык издөө

    Массив боюнча жана жооп боюнча бинардык издөө: O(log n), инварианттар жана типтүү каталар.

Доска