Codeforces Round #358 (Div. 2) Editorial

Revision ru3, by halin.george, 2016-06-17 23:35:43

682A — Алёна и числа

Переберем первое число пары, пусть оно равно x. Тогда нам нужно посчитать количество чисел от 1 до m с остатком от деления на 5 равным (5 - xmod5)mod5. Например, можно предпосчитать, сколько чисел от 1 до m с каждым остатком от 0 до 4.

682B — Алёна и mex

Отсортируем массив. Заведем переменную cur = 1. Пройдемся по массиву. Посмотрим на очередное число. Если оно больше или равно cur, то увеличим cur на 1. Ответ — это cur.

682C — Алёна и дерево

Будем делать dfs. Пусть мы сейчас стоим в вершине u. Пусть v — это какой-то предок вершины u. Тогда dist(v, u) = dist(1, u) - dist(1, v). Если dist(v, u) > a[u], то вершина u заставляет вершину v грустить. Так что необходимо удалить все поддерево вершины u. Соответственно, в dfs можно поддерживать минимум среди dist(1, v), где v — это предок u(вершина, в которой мы сейчас стоим). И если разность dist(1, u) и этого минимума больше au, то удаляем au вместе со всем поддеревом.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English halin.george 2016-06-18 13:47:05 0 (published)
en10 English halin.george 2016-06-18 13:46:51 821
en9 English halin.george 2016-06-18 13:46:04 75
en8 English halin.george 2016-06-18 13:43:14 462
en7 English halin.george 2016-06-18 13:40:00 451
en6 English halin.george 2016-06-18 13:37:37 1485
en5 English halin.george 2016-06-18 13:31:50 1013
en4 English halin.george 2016-06-18 13:22:26 687
en3 English halin.george 2016-06-18 13:15:54 189
en2 English halin.george 2016-06-18 13:15:31 3663 Tiny change: 'ou can predposchitat how many ' - (saved to drafts)
ru5 Russian halin.george 2016-06-18 12:42:20 5 Мелкая правка: 'i][j][cnt]). То ест' -> 'i][j][cnt][end]). То ест'
en1 English halin.george 2016-06-17 23:57:38 77 Initial revision for English translation
ru4 Russian halin.george 2016-06-17 23:42:10 2256 Мелкая правка: '(v, u) (опубликовано)
ru3 Russian halin.george 2016-06-17 23:35:43 865
ru2 Russian halin.george 2016-06-17 23:31:02 8 Мелкая правка: ' равным $(4 - x mod 5)$. Наприме' -
ru1 Russian halin.george 2016-06-17 23:28:39 371 Первая редакция (сохранено в черновиках)