5-деңгээл. Тереңдетилген темалар

Татаал ДП, кесинди дарагы, саптык алгоритмдер жана сандар теориясы — аймактык олимпиадалардын байге ээлеринин деңгээли.

Өркүндөтүлгөн арсенал: классикалык ДП (рюкзак, LIS), кесинди дарагы, саптык алгоритмдер жана модулдук арифметика. Бул темалар облустук жана республикалык олимпиадалардагы байгелүү орундарга жетиштүү. 6-деңгээлге даярдыктын критерийи: кесинди дарагын шыкааларсыз жазасыз жана «рюкзактык» менен «саптык» маселелерди формулировкасынан тааныйсыз.

Бул бөлүмдө

  1. 1
    Тереңдетилген динамикалык программалоо

    Классикалык ДП: O(n·W) убакыттагы 0/1 рюкзак жана O(n log n) убакыттагы эң узун өсүүчү подпоследовательность.

  2. 2
    Кесинди дарагы

    Кесинди дарагы: кесиндидеги сумма жана чекитти жаңылоо O(log n) убакытта.

  3. 3
    Саптар боюнча алгоритмдер: хэштөө жана KMP

    Сапчаларды O(1) убакытта салыштыруу үчүн полиномдук хештер жана үлгүнү издөө үчүн префикс-функция (KMP).

  4. 4
    Сандар теориясы

    Модулдук арифметика: даражага тез көтөрүү, тескери элемент жана модуль боюнча C(n,k).

Доска