Сегодня прошел отборочный тур ВКОШП. Задачи тут , пороль на архив "GOOD1024LUCK".
Давайте выкладывайте свои идее решений задач. Думаю это будет полезно всем.
Спасибо за ваш вклад)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 165 |
| 3 | Um_nik | 161 |
| 3 | atcoder_official | 161 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 147 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.01.2025 12:05:40 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Тут же есть разбор.
Добрый день. Я был членом жюри на Кировской олимпиаде, она проходила на этих же задачах. У себя на разборе мы еще рассказывали такое решение.
Выкинем все запросы, длина которых не укладывается в ограничение (левая позиция, правая позиция). Сгруппируем запросы по длинам и будем рассматривать сразу группу. Скидаем (хэш, левая позиция, правая позиция) всех строк-запросов рассматриваемой длины в хэш-таблицу. Причем складывать их туда будем таким образом, чтобы среди запросов с равным хэшем вначале шел тот, у которого левый край меньше.
Мы знаем длину рассматриваемых запросов, будем брать хэш подстроки соответствующей длины из большой строки начиная с первой позиции. Возможны следующие варианты:
1. В таблице нет такого хэша. Ничего не происходит.
2. Запрос с соответствующим хэшем лежит в таблице, его левая позиция не больше, чем начало рассматриваемой подстроки в большой строке, по правой позиции запрос укладывается. Тогда пометим этот запрос знаком "+" и выкинем его из таблицы. Перейдем к рассмотрению следующего элемента таблицы.
3. Запрос есть, но его левая позиция больше. Понятно, что даже если в таблице и есть элементы с таким же хэшем, то их левая позиция будет еще больше (мы их складывали в таблицу в таком порядке). Значит дальше эту подстроку можно не рассматривать.
4. Запрос есть, левая граница не больше, но правая не укладывается. Тогда для этого запроса гарантированно будет "-", выкинем его из таблицы и перейдем к рассмотрению следующего элемента таблицы.
Сложность решения вроде бы O(|s|*sqrt(|t|)), где |s| - длина большой строки, |t| - суммарная длина запросов. Наше решение на тестах жюри работало примерно 0,7 секунды (Pentium 4 3GHz).