Подсказка
Подсказка
Решение
Подсказка
Решение
1839C - Вставить ноль и инвертировать префикс
Подсказка
Подсказка
Подсказка
Решение
Подсказка
Подсказка
Решение
Подсказка
Подсказка
Подсказка
Подсказка
Решение
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Codeforces Round #876 (Div. 2) Editorial
Первый и последний элементы всегда равны $$$1$$$.
Среди первых
Unable to parse markup [type=CF_MATHJAX]
элементов должно быть хотя бы $$$\lceil \frac{n - 1}{k} \rceil$$$ единиц.Попробуйте решить задачу, если все $$$a_i$$$ равны.
1839C - Вставить ноль и инвертировать префикс
После каждой операции последний элемент $$$b$$$ остается равным $$$0$$$.
Если последний элемент $$$a$$$ равен $$$0$$$, то всегда можно получить $$$b = a$$$ с помощью какой-то последовательности операций.
Попробуйте решить задачу, если $$$a$$$ состоит из $$$k$$$ единиц и одного нуля в конце.
Рассмотрите множество шаров, который никогда не двигались операциями типа $$$2$$$.
Относительный порядок этих шаров никогда не меняется, поэтому их цвета должны образовывать возрастающую последовательность.
Рассмотрите граф с $$$n$$$ вершинами $$$1, 2, \ldots, n$$$, и на каждом раунде игры соединяйте вершины $$$i$$$ и $$$j$$$ ребром. Что можно сказать про этот граф?
Этот граф является деревом.
Вершины дерева можно разделить на два множества, такие, что каждое ребро соединяет вершины из разных множеств.
Если второй игрок выиграл, то суммы элементов в обоих множествах равны в изначальном массиве $$$a$$$.
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
ru3 | valerikk | 2023-06-03 20:11:15 | 0 | (опубликовано) | ||
ru2 | valerikk | 2023-06-03 20:10:56 | 1 | Мелкая правка: 'и первых $$n - 1$ эл' -> 'и первых $n - 1$ эл' | ||
ru1 | valerikk | 2023-06-03 20:10:05 | 2044 | Первая редакция перевода на Русский (сохранено в черновиках) | ||
en11 | valerikk | 2023-06-03 20:01:08 | 0 | (published) | ||
en10 | valerikk | 2023-06-03 19:56:50 | 2 | Tiny change: 'oiler>\n\n[probl' -> 'oiler>\n\n\n[probl' | ||
en9 | valerikk | 2023-06-03 19:54:30 | 17 | Tiny change: 'each round, connect ' -> 'each round of the game, connect ' | ||
en8 | valerikk | 2023-06-03 19:53:26 | 615 | |||
en7 | valerikk | 2023-06-03 19:47:24 | 45 | |||
en6 | valerikk | 2023-06-03 19:46:39 | 298 | |||
en5 | valerikk | 2023-06-03 19:43:25 | 46 | |||
en4 | valerikk | 2023-06-03 19:42:14 | 415 | |||
en3 | valerikk | 2023-06-03 19:39:38 | 172 | |||
en2 | valerikk | 2023-06-03 19:37:02 | 18 | |||
en1 | valerikk | 2023-06-03 19:36:22 | 371 | Initial revision (saved to drafts) |
Name |
---|