Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 18:28:57 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Ребят, в арену не заходит :(
Пишет "Error, system is offline".
У меня только что зашло.
Как решать 500(div1)?
Заметим, что пары строк, которые нас интересуют — это такие строки, что одна из них получается циклическим сдвигом из второй. Давайте считать, сколько в алфавите из k букв есть строк длины N с количеством различных циклических сдвигов равных L. Это равносильно тому, что нам нужно посчитать, у скольки строк период равен L. Значит, L — делитель N. Для того, чтобы посчитать количество строк с периодом L, используем что-то вроде принципа включений-исключений:
f(L) = kL-(сумма f(c) таких, что с — делитель L и с меньше L)
Чтобы узнать ответ, суммируем для каждого делителя N значение f(L) * L (для каждой строки ставим в пару ее циклический сдвиг)
а ещё на прямую по принципу включений-исключений
Как решать 950 (div. 2) ?
1000 в див1, верно ли что достаточно завести вектора количества вхождений каждного элемента, и затем их перемножить и найти в какой позиции самое большое число?
Нет конечно. Верно то же удтверждение, если бы произведение 2х чисел было операцией минимума
Как тогда решать? :)
static final int BUBEN = 10;
Объяснять дальше? :-)
У меня в дорешке n * sqrt(n) * log(n) тлешится, чуть-чуть не пролазит в 4 сек на двух тестах. А те кто сдали, с какой ассимптотикой это сделали?
Ну если я понимаю правильно, то решение у Егора такое:
Сначала возьмем каждого числа по одному, и с помощью Фурье (когда чисел по одному, мое утверждение выше с произведением и ответ Егора с минимумом -- это по существу одно и тоже) найдем все их попарные суммы. Затем уменьшим количество вхождений каждого числа на один. Повторим это 10 раз. Остались только числа, которые встречаются по 11 раз и более, их, очевидно, не более 10К, их попарные суммы находятся за квадрат.
Получается 10*n log n + 10K^2.
У меня n^2 в дорешке прошёл...
Можно ли решить 250(div1) через ДП по дереву?
Понятно, что одним ходом можно закончить игру, оставив какой-нибудь лист. Тогда рассмотрим логику первого игрока. Он может всегда взять какой-нибудь лист. Ответ — это вес самого тяжелого листа. Предположим, что первый игрок может взять больше, чем самый тяжелый лист. Тогда он первых ходом не закончить игру, а отрежет кусок дерева. Понятно, что одним разрезом удалить все начальные листья нельзя. Тогда второй игрок своим ходом закончит игру, так как тогда результат будет не больше, чем наибольший лист, а первый игрок хочет больше. Таким образом лучшая стратегия — это первым же ходом отрезать наибольший лист.
Я сдавал такое же решение.
Но интересно можно ли было решить эту задачу именно динамикой по дереву. Вариант перебрать ребро и разбить на 2 подзадачи не срабатывает в данном случае.
Editorial