Тема: Hash
Кто может посоветовать задачи на хэш?
и вообще хэш часто используют на олимпиадах?
кстати, на с++ - map это и есть hash?
1 2010-08-08 00:55:43 Отредактировано aza_inf (2010-08-08 00:58:16)
Re: Hash
Нет, map это красно-черное дерево, каждая операция на котором гарантированно работает за O(logN). Практически всегда задачи, которые решаются при помощи хеширования можно решить и без него (КМП, суфф. массивом или еще чем-то подобным). Вот несколько задач, которые можно решить хешированием:
http://acm.timus.ru/problem.aspx?space=1&num=1713
http://acm.timus.ru/problem.aspx?space=1&num=1486
http://acm.timus.ru/problem.aspx?space=1&num=1269
Re: Hash
Re: Hash
Вообще часто используется,относительно легко пишется,подходит наверное к любой задаче на поиск.Другое дело,что иногда нужно много памяти,иногда не хочешь рисковать с частными случаями.А вообще советую в Кормене прочитать,там всё хорошо расписано.