160929 recipes — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии 2 участников)
Строка 13: Строка 13:
 
* Задача 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.
 +
 
 +
В этой задаче нужно написать две кучи. Как при удалении из первой кучи быстро найти и удалить элемент во второй?
 +
 
 +
Есть два разных способа, один подход будет на лекции в среду, а второй вы уже знаете с прошлой лекции &minus; "обратные ссылки".
 +
 
 +
Нужно отдельно хранить массив <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.