3-деңгээл. Маалымат структуралары жана ач көз алгоритмдер

Стек, кезек, көптүктөр жана сөздүктөр, рекурсия, ач көз алгоритмдер жана DSU — орто деңгээлдеги маселелердин куралдары.

Куралдар деңгээли: стек жана кезек, set жана map, рекурсивдүү кыдыруу, ач көз алгоритмдер жана DSU. Андан кийин маселени массивге ылайыкташтырбастан, маселеге маалымат структурасын тандай аласыз. 4-деңгээлге даярдыктын критерийи: DSU менен артка кайтуулуу толук кыдырууну жаттан жазасыз, ал эми ач көз чечим үчүн анын ЭМНЕГЕ туура экенин түшүндүрө аласыз.

Бул бөлүмдө

  1. 1
    Стек жана кезек

    Стек (LIFO) жана кезек (FIFO): кашаа ырааттуулуктары жана иштетүү тартиби.

  2. 2
    Көптүктөр жана сөздүктөр: set жана map

    set жана map: таандыктыкты тез текшерүү, ар түрдүүлөрдү жана жыштыктарды O(log n) убакытта эсептөө.

  3. 3
    Рекурсия жана толук издөө

    Рекурсия жана толук кыдыруу: подмножестволор, орун алмаштыруулар жана варианттар дарагы.

  4. 4
    Ач көз алгоритмдер

    Ач көз алгоритмдер: жергиликтүү эң жакшы кадам, кесилишпеген интервалдар маселеси, колдонуу чектери.

  5. 5
    Кесилишпеген көптүктөр системасы (DSU)

    Кесилишпеген көптүктөр системасы: жолдорду кысуу менен find жана union — дээрлик O(1).

Доска