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

Автор Felix_Mate, история, 7 лет назад, По-русски

Хотелось бы узнать решения задач

http://acm.timus.ru/problem.aspx?space=1&num=1890

http://acm.timus.ru/problem.aspx?space=1&num=1839

http://acm.timus.ru/problem.aspx?space=1&num=2022

http://acm.timus.ru/problem.aspx?space=1&num=1655

везде имею WA

1890 решаю так: строю HLD; имею 2 дерева отрезков: для суммы прибавок в департаментах (до корня) (с запросами изменить значение элемента и найти сумму на отрезке) и для суммы всех индивидуальных прибавок сотрудникам в корне с заданной вершиной (с запросами найти суммарную прибавку в элементе и прибавить значение на отрезок). есть подозрения, что плохо считываю данные или имею переполнение типов код(WA2): https://ideone.com/fork/hprg2R

1839 решаю так: перебираю дуги и для каждой ищу рожицы: во-первых отсеим все неподходящие точки без условия 4); получим претендентов Pret; теперь проблема только с условием 4). Рассмотрим очередную точку Х из Pret; для неё нужно найти все такие Y из Pret, что cos(YRP)<cos(XRP) и cos(YPR)>cos(XPR); это можно сделать за логарифм для каждой точки Х с помощью ДО. Код(WA3): https://ideone.com/fork/HmAhfk

2022 решаю так:пусть T-момент прыжка; до него движение описывается так: x(t)=vx * t, y(t)=vy * t — g*t*t/2; чтобы прыжок можно было совершить, необходимы условия: x(T)<L, y(T)>0, T>0, откуда получаем интервал для T; далее полёт описывается так: x(t')=x(T) + (vx+ux) * t', y(t')=y(T) + (vy-g*T+uy)*t' — g*t'*t'/2; теперь необходимые условия пролёта через дырку выглядят так: в момент пролёта t1 через стену (т.е. когда x(t1)=x(T)+(vx+ux)*t1=L) в т. L нужно h<y(t1)<h+d, в момент пролёта t2 через стену (т.е. когда x(t2)=x(T)+(vx+ux)*t2=L+l) в т. L+l нужно h<y(t2)<h+d, (3) а также если максимальная высота ф-ии y(t') достигается на [t1, t2], то max(t')<h+d. В итоге получаем некоторые интервалы решений (возникающие при решении неравенств), их пересекаем; потом (если выполняется (3), то некоторые из них обрезаем. Ответ=середина интервала длины не меньше 0.000001 Код(WA3) : писать не буду, т.к. сдавал без (3), а с (3) даже инпут не прохожу.

1655 решаю так: пишу ДП: dp[i][j][0]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции i (где находится i корабль), dp[i][j][1]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции j (где находится j корабль). Особо пояснять нечего. Единственное, в реализации вместо делений на скорость я все числа умножал на неё. Код (WA8):https://ideone.com/GPQRO8

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Felix_Mate (предыдущая версия, новая версия, сравнить).

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1890 — одно дерево отрезков с прибавлением на отрезке :) Нужно просто вспомнить, что поддерево вершины — непрерывный отрезок обхода дерева.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо за отклик, но подсказка мне не поможет: это лишь немного другой способ реализации того же самого. Хотелось бы узнать, где моя ошибка в логике или другой способ решения(без HLD). sqrt-декомпозиция,наверное, даст TL.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А где тут HLD-то?)

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Наверно,я не понял предыдущий комментарий. Т.е. предлагается одно ДО не в HLD использовать, а обойти DFS-ом дерево, построив массив посещённых вершин и его использовать на запросы?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Да, именно так.

          Если построить массив в порядке обхода dfs и запомнить для каждой вершины ее положение в обходе pos[v] и размер поддерева s[v], то подотрезок, соответствующий поддереву v — это [pos[v]..pos[v] + s[v]).

          Тогда сумму в точке и сумму в поддереве считать довольно-таки просто)