Хотелось бы узнать как решаются задачи A, B, C, D, G, I, J, L, M. Контест прошёл, помогите пожалуйста. Заранее благодарен.
Хотелось бы узнать как решаются задачи A, B, C, D, G, I, J, L, M. Контест прошёл, помогите пожалуйста. Заранее благодарен.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
Пусть F(n) ответ на задачу.Тогда F(1) = 1 и также исходя из условия можем сказать, что длина n-строкофакториала равна сумме длин строк, образованных конкатенацией n-ого множителя и i-ого символа (n-1)-строкофакториала (для всех i=1..n). Поэтому F(n) = F(n-1)*(1+Length(s[n])), где s[n] — n множитель соответственно.
Заметим также что при i = 1..26 Length = 1 ,
i = 27..26*27 Length = 2 ,
i = 26*27+1..MAXN Length = 3.
Длина ответа превышает 5000 цифр, а поэтому, к сожалению =), нужна длинная арифметика.
спасибо
В D просто матрицу в степень возвести, у меня получилась 7x7, на Java не заходит, на плюсах зайдёт наверное.
На плюсах 7*7 тоже не должно зайти. Нужно соптимизировать матрицу до 5*5 хотя бы.
можно поподробнее про матрицу, пожалуйста
Допустим, мы знаем два цвета на первом слое ожерелья. Назовём их 1 и 2. Все остальные цвета будем называть 0.
Тогда можно построить динамику: количество ожерелий, которые на i-том слое содержат 12, 10, 20, 21, 01, 02 или 00 (вот откуда 7*7)
Динамика пересчитывается из предыдущего состояния, так что её можно заменить матрицей переходов и возвести эту матрицу в степень.
Ну а нас в конце концов будут интересовать случаи 20, 21, 01 и 00, которые не содержат одинаковых смежных цветов с 12.
Оптимизировать матрицу до 5*5 просто, если заметить, что там есть пары одинаковых (в смысле пересчёта и количества на каждом шаге) состояний.
В: Кажется, заходил аккуратно написанный квадрат.
С: Понятно что надо на остовном дереве найти длиннейшее расстояние между парами соседних баров на пути с одного бара в другой (он 1, поскольку мин-остов это дерево). Это делается методом двоичного подъёма, аналогично тому как искать LCA.
J. ans=n. Никто же никуда с дерева не улетает.
Поищите статью на кодфорсе о 1/8 чемпионата мира восточного региона Украины этого года http://codeforces.me/blog/entry/4323