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

Версия 15:34, 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.

1. Если вы вызываете один бинпоиск, а потом линейно проходите по равным, получите TL. Задача решается небольшим числом вызовов бинпоиска.

2. Если вы пишете два разных бинпоиска, то задача не будет зачтена!!!

3. Сделать все одинаковым бинпоиском было бы тяжело, если бы числа в массиве были вещественные. Но они целые.

• Задача D. minmax.

Есть два разных способа синхронизировать две кучи. Один подход будет на лекции в среду.

А второй уже был на лекции. Если мы помним position[i], где в куче лежит a[i], то можно из нее удалить. Удалить произвольный элемент почти так же, как вершину (но нужно заметить тонкость).

Меняя элементы местами, не забывайте менять и position.

Для этого нужно и в куче помнить позиции элементов.