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

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

Есть такая задача: дано подвешенное дерево и запросы к нему. Каждый запрос — путь в графе, причём LCA концов границ этого отрезка — одна из этих границ. В каждой вершине написано число от 0 до n. Для каждого запроса в порядке их поступления требуется идя по нему от 1 границы до другой занулить все вершины, которые равны n, исключая края отрезков таких вершин. Иными словами, если на этом пути встречаются несколько подряд идущих вершин равных n, то с первой и последней из них мы ничего не делаем, а остальным присваиваем 0. Я предполагаю, что данную задачу можно решить сканлайном вида "будем обходить дерево DFS-ом и заходя в вершину, из которой начинается отрезок начинаем занулять, проверяя не конец ли текущая вершина", но по неизвестным причинам такой способ получает WA(вероятно из-за порядка запросов, а он, как видно из условия, важен), был бы рад, если бы кто-нибудь поможет с этой задачей. Желательно предоставить конкретную реализацию или доказательство, что моя идея ошибочна.

Полный текст и комментарии »

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

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

Есть матрицы A и B. A=B^n. Как я могу найти n?

Полный текст и комментарии »

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