160929 recipes — различия между версиями
Burunduk (обсуждение | вклад) |
Burunduk (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 16: | Строка 16: | ||
2. TL? Наверное, вы медленно читаете/выводите. | 2. TL? Наверное, вы медленно читаете/выводите. | ||
+ | |||
+ | * Задача C. find3. | ||
+ | |||
+ | Если вы вызываете один бинпоиск, а потом линейно проходите по равным, получите TL. Задача решается за O(log n). | ||
+ | |||
+ | <!-- | ||
+ | небольшим числом вызовов бинпоиска. | ||
+ | 2. Если вы пишете два разных бинпоиска, то задача не будет зачтена!!! | ||
+ | 3. Сделать все одинаковым бинпоиском было бы тяжело, если бы числа в массиве были вещественные. Но они целые. | ||
+ | --> | ||
+ | |||
+ | * Задача D. minmax. | ||
+ | |||
+ | В этой задаче нужно написать две кучи. Как при удалении из первой кучи быстро найти и удалить элемент во второй? | ||
+ | |||
+ | Есть два разных способа, один подход будет на лекции в среду, а второй вы уже знаете с прошлой лекции − "обратные ссылки". | ||
+ | |||
+ | Нужно отдельно хранить массив <code>a[]</code>, а в куче хранить не элементы <code>a[i]</code>, а индексы <code>i</code>. Кроме того для каждого <code>i</code> нужно помнить | ||
+ | <code>pos[i]: heap[pos[i]] = i</code>. | ||
+ | |||
+ | <!-- | ||
+ | heap[i] = j | ||
+ | Если мы помним <code>position[i] </code>, где в куче лежит a[i], то можно из нее удалить. Удалить произвольный элемент почти так же, как вершину (но нужно заметить тонкость). | ||
+ | Меняя элементы местами, не забывайте менять и position. | ||
+ | Для этого нужно и в куче помнить позиции элементов. | ||
+ | --> |
Текущая версия на 21:38, 3 октября 2016
- Задача A. Квадратный корень.
1. unsigned long long
-- всё должно быть именно такого типа.
2. unsigned long long l = 0, r = -1;
// границы бинпоиска,
3. Чтение до конца файла: добавлен специальный пример по C++
4. У вас WA? Вы тестировали? Спокойно сядьте, и вбейте 20 разных тестов, включая максимальные и минимальные.
5. У вас TL? Может быть, бинпоиск виснет? Может быть, вы не умеете читать файл?
- Задача B. Бинпоиск.
1. Если вы пользуетесь функциями STL lower_bound/upper_bound
, в чём может быть проблема? =)
2. TL? Наверное, вы медленно читаете/выводите.
- Задача C. find3.
Если вы вызываете один бинпоиск, а потом линейно проходите по равным, получите TL. Задача решается за O(log n).
- Задача D. minmax.
В этой задаче нужно написать две кучи. Как при удалении из первой кучи быстро найти и удалить элемент во второй?
Есть два разных способа, один подход будет на лекции в среду, а второй вы уже знаете с прошлой лекции − "обратные ссылки".
Нужно отдельно хранить массив a[]
, а в куче хранить не элементы a[i]
, а индексы i
. Кроме того для каждого i
нужно помнить
pos[i]: heap[pos[i]] = i
.