темы в памяти.
Лучшая, на мой взгляд, книга по работе с Cи — это второе издание C Programming: A Modern Approach К.Н. Кинга (K. N. King). Даже если вы хорошо знакомы с Cи, все равно рекомендую ее прочесть. Она оказывается отличным помощником, когда особенности этого языка вызывают сложности в понимании кода.
6 Ұнайды
Почему я применил именно умножение на 39 и добавление символа? Дело в том, что такой вариант не вызывал коллизий в тестовых примерах Codeforces. Да, я понимаю, что это неудовлетворительное решение.
3 Ұнайды
Введение
Я предполагаю, что вы знакомы с такими языками, как Cи, C++, Java или Python… и разбираетесь в теме. Тяжело объяснять людям, незнакомым с программированием, почему написание кода для решения задач является настолько захватывающим.
Я также надеюсь, что вы готовы поднять свои навыки программирования на новый уровень. Для меня будет честью помочь вам в этом.
Я мог бы начать с разъяснения всяких изощренных техник, рассказывая о том, какие они полезные, и сравнивая их с другими изощренными техниками. Но я не буду этого делать. Такие знания очень недолго хранятся в памяти, ожидая возможности применения на практике (которая порой так и не появляется).
Вместо этого я на протяжении всей книги буду ставить конкретные трудные задачи. Надеюсь, что вы не сможете справиться с ними сразу, используя знакомые вам подходы. Вы — программист. Вам нужно решать задачи. Пришло время освоить хитрые техники. Книга построена на постановке сложных задач с их последующим решением, при этом вы будете пополнять имеющиеся у вас знания.
Здесь вы не увидите типичных задачек из учебников, не будете искать оптимальный путь умножения последовательности матриц или вычисления чисел Фибоначчи. Я обещаю, что вы не будете решать и головоломку ханойской башни. Существует множество прекрасных учебников, где все это прописано, но я подозреваю, что немногих из вас такие головоломки действительно мотивируют.
Мой подход предполагает использование задач, которые вы ранее вряд ли встречали. Каждый год тысячи людей участвуют в соревнованиях по программированию, и для этих соревнований постоянно требуются новые задачи, чтобы оценивать реальные навыки участников, а не способность быстрее всех переделывать старое на новый лад или гуглить решение. Эти задачи удивительны, они базируются на классических подходах, но вносят в них изменения и интересный контекст, подталкивая людей к поиску новых решений. В таких задачах заключается практически безграничный объем знаний по программированию и вычислениям.
Начнем с основ. Структура данных — это способ организации данных для быстрого выполнения нужных операций. Алгоритм — это последовательность шагов при решении задачи. Иногда можно создать быстрый алгоритм без применения сложных структур данных. В других же случаях правильно подобранная структура может существенно ускорить решение. Моя задача — не сделать из вас участника соревнований по программированию, хотя это было бы хорошим бонусом, а научить работать со структурами данных и алгоритмами на примерах интересно поданных задач спортивного программирования. Пишите мне об успехах в своем обучении. Пишите также, если материалы этой книги заставят вас улыбнуться.
2 Ұнайды
инкрементные хеш-функции, которые очень быстро генерируют хеш-код для элемента, похожего на ранее хешированный. Например, если у меня уже есть хеш-код для abcde, то вычисление хеш-кода для abcdef с помощью инкрементной хеш-функции будет очень быстрым, так как она может опереться на уже проделанную работу, а не начинать все сначала.
В задаче даются две строки (слова), первая из которых имеет на один символ больше, чем вторая. Цель — определить количество способов, которыми можно удалить один символ из первой строки, чтобы получить вторую строку. Например, существует только один способ получить из favour слово favor — удалить из первой строки u. Но есть три способа получить из abcdxxxef слово abcdxxef — удалить любой из символов x в первой строке.
Хеш-таблицы не поддерживают сортировку — они просто разбрасывают элементы по разным местам
Входные данные содержат одно слово на строку в алфавитном порядке. Максимальное число строк — 120 000.
Дан список слов, в котором каждое слово представлено в виде строки в нижнем регистре. Например, список, содержащий строки crea, create, open и te. Поставлена задача определить, какие из них являются сложносоставными словами, то есть представляют конкатенацию двух других строк из списка. В приведенном примере данному условию удовлетворит только строка create, потому что состоит из crea и te.
Первая строка входных данных является целым числом n, описывающим количество сравниваемых снежинок. Значение n будет находиться в диапазоне от 1 до 100 000. Каждая из следующих n строк характеризует одну снежинку: содержит шесть целых чисел, каждое из которых может иметь значение в диапазоне от 0 до 10 000 000.