Здравствуйте! Недавно пытался сдать простую задачу, в которой нужно было посчитать суфмасс для циклических сдвигов строки, а по нему — lcp. Код построения суфмасса почти идентичен размещенному на e-maxx.ru в соответствующей статье. Lcp строил алгоритмом Касаи, но длительное время получал WA. После того, как я посортил куски суфмасса, находящиеся в одном классе эквивалентности, по убыванию индекса (т.е. по возрастанию длины), решение внезапно получило AC. Позже, я встретил похожую задачу, и опять все повторилось, спас только этот грязный хак с сортировкой. Теперь очень захотелось разобраться, что же я делаю не так. Возможно, это спецэффект Касаи, о котором нигде не написано? Или я криво его пишу? В любом случае, вот мой код. Прошу помочь разобраться!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Здравствуйте! Я думаю, что почти все программисты, пишущие на C++, регулярно используют и STL. Библиотека, безусловно, замечательная, но в ней сокрыто немало тонкостей, которые могут неожиданно вылезти на контесте.
Например, совсем недавно я узнал, что vector<bool> хранит элементы в виде байтов, в каждом из которых содержится по 8 bool'ов, из-за чего не очень быстро (очень не быстро?) работает. Или, например, что вектор в Visual Studio расширяется в 1.5 раза, а вектор в g++ - в 2 раза. Поправьте меня, если я не прав.
Я думаю, что опытные кодеры знают куда больше трюков, и предлагаю в этой теме обменяться опытом использования STL. Интересуют как общие для обоих компиляторов вещи, так и специфичные, потому что контесты приходится зачастую писать в разных средах.
Для начала мне хотелось бы узнать две вещи:
1) За сколько работают методы begin, end, size у сложных структур типо set, map.
2) Как писать лучше и быстрее: set.find(elem) != set.end() или set.count(elem) == 0
3) Правда ли, что stack, queue и deque очень медленно работают?
Здравствуйте! На Тимусе есть такая задача: http://acm.timus.ru/problem.aspx?space=1&num=1158.
Так вот, к ней прилагается 23-ий тест, который моя правильная (я уверен!) программа не может пройти из-за проблем с символами с кодами больше 127 (как я понял из форума, это первый тест где они появляются).
Это очень обидно, так как я долго решал эту непростую задачу, а тут такая подстава. Объясните пожалуйста, почему с этими символами возникают проблемы (я догадываюсь, что из-за того что первые 128 совпадают во всех кодировках, а дальше нет) и что надо сделать на C++, чтобы их решить.
Здравствуйте! Как я успел заметить, на этом сайте достаточно много людей, для которых программирование - не профессия, а хобби, поэтому я и решил задать свой вопрос здесь.
Буквально вчера я закончил 9-ый класс :) . Программированием я занимаюсь еще достаточно недолго (~2 года), к тому же до настоящего времени занимался самостоятельно. В школе учусь в химклассе, у нас замечательный учитель, в этом году я ездил на Всеросс по химии (к сожалению, немного не дотянул до призера). По информатике в этом же году взял призовое место на области, но на Всеросс не прошел.
Сейчас я стал понимать, что для программирования нужна еще и математика, а для химии - физика, причем оба предмета выше уровня школьной программы. Поэтому встал вопрос: куда развиваться дальше, что будет больше востребовано? По химии, как я уже говорил, у нас замечательный преподаватель, готовый с нами заниматься дополнительно, а программирование можно оставить в качестве хобби. По информатике нашу школу любезно согласился тренировать один из членов команды Lynx :) , к тому же я могу перейти в маткласс, который у нас достаточно сильный. То есть существуют возможности для развития в обоих направлениях.
Третий вариант - продолжить изучать оба предмета. Но где можно приложить их одновременно? Единственное, что я нашел - различные виды моделирования процессов в химии, хотя непонятно, насколько там будут нужны различные сложные алгоритмы, которые приходится изучать для информатики.
Здравствуйте! На последнем раунде (#72) для второго дивизиона была отличная для взломов задача B. Но не одного взлома у меня сделать не получилось :(
Что я сделал:
1) Сгенерировал макс. тест вида 100000\n<число 1 100000 раз через пробел>
2) Открыл окно взлома, вставил туда тест, нажал взломать. Мне выдало ошибку, точный текст ее я не помню (кстати, можно ли сейчас это где-нибудь посмотреть?), но было что-то вроде Unexpected character #13, expected ' '. Где он нашел лишний перевод строки - непонятно.
3) Взял генератор, сделал вывод в стандартный поток, отправил код. Результат - ошибка вида Input can't be empty. Может, не в cout нужно выводить?
Собственно, подскажите, как же правильно ломать?
З.Ы.: Когда я хотел написать это через Chrome, вместо русских символов печатались квадратики. Через IE такой проблемы не наблюдается. Это старый баг или мои локальные проблемы?
Здравствуйте! Устрашенный заявлениями подполковника Ferlon'а о "вытирании ног об новичков", я все таки решился создать эту тему. Надеюсь, что еще остались люди, которые считают помощь новичкам нормальным поступком и не думают, что я скоро раскачаюсь и всех "одержу" :D .
Ну это было вступление. Теперь к вопросу: решая эту задачу, я свел ее к следующей проблеме: есть A групп по X человек и B групп по (X+1) человек. Как оптимально разбить эти группы на два больших множества, так чтобы разность между количествами человек в них была минимальной? Как мне кажется, кроме перебора существует и более разумное решение, но его я найти не смог. Придумал только разве что (X * (X+1)) = ((X+1) * X), а значит можно часть групп распределить равномерно, а дальше все равно получается перебор, и я даже не уверен, что это правильно.
Подскажите, пожалуйста, правильную идею!
Здравствуйте! Снова я прошу помощи в решении задачи, на этот раз вот этой. Наверняка ее можно решить динамикой, только я не понимаю, что взять в качестве параметров. Была идея обозначить выбор автобуса первой группы 0, а второй - 1, тогда можно описать целым числом любое состояние, но числа длинноватые получаются и MLE неизбежен. Напишите кто-нибудь разбор, пожалуйста, и объясните, умение решать ДП приходит с опытом или его надо как-то тренировать (кроме простого нарешивания задач)? Опыт у меня прямо сказать небольшой (~1.5 года), и это пока для меня самый сложный тип задач :(
Здравствуйте! Прошу помочь с решением этой непростой для меня задачи.
Несколько наблюдений я все-таки сделал:
- Научился вычислять стоимость с 1 по i веник для любого завода за O(1)
- Динамика, как мне кажется, будет двумерная, строки - кол-во веников, столбцы - использованные заводы с 1..j, ячейка - минимальная стоимость. A[1, j] и A[i, 1] заполняются очевидно.
Здравствуйте! Зарегистрировался только что на топкодере, нашел там Practice Room, догадался что это архив с задачами, открыл самый последний контест из TCHS (#90), как я понял это как раз для школьников, запустил задачу на 250 баллов, начал решать. Создал там этот класс (что за ерунда кстати, даже не потестить нормально, на кодефорсес лучше =) ), написал решение, вроде не сложная задача, тесты все из примеров прошли, нажал сабмит, мне написали:
System> k1r1ch has submitted the 250-point problem for 75.10 points
То есть получается что решение не все тесты прошло? И если да, то можно ли как-нибудь посмотреть на эти тесты? Или там все закрыто?
Конечно наверное это нужно было на их форуме писать, но мне не так просто связно излагать мысли на инглише, да и тем более я думаю здешние почти все на топкодере участвуют...
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.11.2024 06:50:51 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
