160929 recipes — различия между версиями
Burunduk (обсуждение | вклад) |
Burunduk (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | * Задача A. Квадратный корень | + | * Задача A. Квадратный корень. |
1. <code>unsigned long long</code> -- всё должно быть именно такого типа. | 1. <code>unsigned long long</code> -- всё должно быть именно такого типа. | ||
| Строка 11: | Строка 11: | ||
5. У вас TL? Может быть, бинпоиск виснет? Может быть, вы не умеете читать файл? | 5. У вас TL? Может быть, бинпоиск виснет? Может быть, вы не умеете читать файл? | ||
| − | * Задача B. | + | * Задача B. Бинпоиск. |
| − | Если вы пользуетесь функциями STL <code>lower_bound/upper_bound</code>, в чём может быть проблема? =) | + | 1. Если вы пользуетесь функциями STL <code>lower_bound/upper_bound</code>, в чём может быть проблема? =) |
| − | 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.
