Блог пользователя Sereja

Пятая индивидуальная интернет-олимпиада
Автор Sereja, 16 лет назад, По-русски
Сегодня прошла пятая индивидуальная интернет-олимпиада на сайте neerc.ifmo.ru/school. Давайте здесь обсуждать решения задач.
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Давайте.
Кто как решал задачи C и D?
→ Ответить
  • 16 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +1 Проголосовать: не нравится
    Я свел C к тому чтобы найти длину самого длинного отрезка на котором сумма 0. Отнимем от всех чисел K и найдем такой отрезок - это и будет ответ.
    → Ответить
    • 16 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      → Ответить
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      а как искать отрезок с заданной суммой?
      → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +2 Проголосовать: не нравится
        Предподсчитаем суммы на префиксах. Получаем массив sum от 0 до n. Сумма на отрезке [l..r]=sum[r]-sum[l-1]. Нужно найти в массиве два числа с заданной разницей (в данном случае - два равных). Бежим справа налево и делаем пометки в массиве (или заносим в set) числа, которые уже были. Когда наткнулись на число, прибавили к нему требуемую сумму на отрезке и посмотрели, были ли такие числа. Если надо найти макс. по длине отрезок - храним только самое правое.
        → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +1 Проголосовать: не нравится
        С суммой 0 можно map-ом или сортировкой+дихотомией. В map-е храним когда первый раз встретился префикс с такой суммой. Потом перебираем правую границу. Пусть сумма до нашей правой границы равна X. Тогда левая граница это следующий за наименьшим по длине таким префиксом, сумма которого равна X.
        → Ответить
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    не решал, посмотрел условия... По С идея такая...
    Считаем отклонения от среднего и храним в мапе последний номер на котором получается данное значение. Для первого ищем положение Z=0, для второго Z = Z - K + A[1] и тд... Получаем O(n*log(n))
    → Ответить
16 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +6 Проголосовать: не нравится
Напишу про свои решение(не знаю будет ли у меня по всем 100, но вроде должно быть):
1я задача:
когда идем по строке , просто смотрим был-ли у нас такой символ раньше, если был то не делаем ничего , иначе к ответ добавляем этот символ и помечаем его
2я задача:
Написал скольжение , но походу можно было делать и так:
пишем перебор для маленьких , и видим что ответа для Н=9 уже нету, то есть там нужно всего несколько забить в константу.
3я задача:
Сначала напишем такое решение:
Sn=A1+A2+...+An
отрезок [j+1;i] подходит если (Si-Sj)/(i-j)=k => Si-Sj=k*i-k*j => Si-k*i=Sj-k*j,
то есть все что нужно сделать, так это отсортировать все такие значения, и для равных найти мин/мах номер, зная их знаем решение.
ну и 4я задача:
сначала посчитал для каждого кол-ва гласных, можно-ли его получить. Потом нашел все "нужные" суффиксы и отсортировал их . Если в какой-то группе равных суффиксов есть два возможных "окончания", то беру их и строю с ними в конце. Посмотреть можно или нет, поставить что-то в конец делаю с помощью того пред посчитанного массива , можно-ли получить какую-то сумму. За это задачу как-раз сомневаюсь больше всего...

→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Выбирал между ней и CF55Div2, в итоге выбрал второе. Как оказалось, не зря)
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
В 4-й задаче надо было использовать обязательно все слова?
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Странно что никто не спрашивает.
А где результаты ? 
Вроде день прошел, а их все нет и нет :)
→ Ответить