Ҷустуҷӯи бинарӣ бо дараҷаҳои дугона - Course 2

Module 1: Scanline

Сканлайн / Коркарди рӯйдодҳо
Problems for practice

Module 2: Introduction to DP

Барномасозии динамикӣ

Module 3: Number theory

Ададҳои аввал ва факторизатсия
Ғалбери Эратосфен

Module 4: Graph traversals

Ҷустуҷӯи амиқ-аввал (DFS)
Ҷустуҷӯи паҳноӣ (BFS)
Санҷиш барои дудолӣ
Ёфтани ҷузъҳои пайвастшуда
Сорткунии топологӣ

Module 5: Shortest paths

Алгоритми Дейкстра
Алгоритми Флойд–Уоршалл
Bellman–Ford algorithm

Module 6: Game Theory - Basics

Асосҳои ҳолатҳои бозӣ

Module 7: Introduction to Geometry

Масоҳати аломатдори секунҷа
Basic Geometry
Bonus Geometry Problems

Module 8: Various types of Binary Search

Ҷустуҷӯи бинарӣ аз рӯи ҷавоб
Ҷустуҷӯи бинарӣ аз рӯи ҷавоби воқеӣ
Ҷустуҷӯи тернарӣ
Ҷустуҷӯи бинарӣ бо дараҷаҳои дугона

Асосӣ Курсҳо Манбаъҳо Масъалаҳо Олимпиадаи миллӣ Мусобиқаҳо Ҷадвали роҳбарон

...

Асосӣ/Courses/Course 2/Module 8: Various types of Binary Search/Ҷустуҷӯи бинарӣ бо дараҷаҳои дугона

Ҷустуҷӯи бинарӣ бо дараҷаҳои дугона

Ҷустуҷӯи бинарӣ бо дараҷаҳои дугона

Идея (аз ҳама содда)

Мо ҷавобро аз рӯи битҳо, аз калонтарин сар карда месозем. Дар ҳар қадам савол медиҳем:

«Оё мумкин аст $2^k$ -ро ба ҷавоби ҷорӣ илова кунем?»

Агар мумкин бошад — илова мекунем, агар не — ба қадами хурдтар мегузарем. Аслан, мо битҳои ҷавобро аз калонтарин то хурдтарин месанҷем.

Шаблон

long long ans = 0;

for (int i = 60; i >= 0; i--) {
    if (check(ans + (1ll << i))) {
        ans += (1ll << i);
    }
}