қазақша
русскийОбластная олимпиада по информатике 2017 г.
Строка считается красивой, если все буквы в ней различны.
Вам дана строка $S$, состоящая из строчных английских букв. Найдите красивую и наименьшую в лексикографическом порядке строку, которую можно получить путем удаления повторяющихся букв строки S так, чтобы каждая уникальная буква строки появлялась один раз и только один раз.
Лексикографический порядок определяется следующим образом. Пусть даны две строки $A = a_1 a_2 \cdots a_n$ и $B = b_1 b_2 \cdots b_m$. Тогда строка $A$ лексикографически меньше строки $B$, если выполняется одно из двух условий:
Вам дана строка $S$, состоящая из строчных английских букв. Найдите красивую и наименьшую в лексикографическом порядке строку, которую можно получить путем удаления повторяющихся букв строки S так, чтобы каждая уникальная буква строки появлялась один раз и только один раз.
Лексикографический порядок определяется следующим образом. Пусть даны две строки $A = a_1 a_2 \cdots a_n$ и $B = b_1 b_2 \cdots b_m$. Тогда строка $A$ лексикографически меньше строки $B$, если выполняется одно из двух условий:
- $n < m$ и при этом $a_i =b_i$ для всех $i \in [1..n]$
- $\exists k≤min(n,m): a_k < b_k$ и при этом $ ∀ j < k$ $a_j =b_j$.
Входные данные
В первой строке следует целое положительное число $K$ ($1 ≤ K ≤ 10^5$) — длина строки $S$. Во второй строке следует строка $S$ длины $K$, состоящая из строчных букв английского алфавита.Выходные данные
Выведите ответ на задачу.Примеры:
Вход:5 yzxyzОтвет:
xyzВход:
8 yxwyzyxyОтвет:
wyzx
Оценивание:
В $20$% тестов: $1 ≤ K ≤ 20$.комментарий/решение(6)
В стране T K − Robots есть $n$ городов. Для удобство пронумеруем их от 1 до n. Из каждого города выходит ровно одна односторонняя дорога. Из i - го города в город $p_i$. В начале в городе i находится $a_i$ роботов. Роботы очень любят путешествовать по стране. За один момент времени, робот находящиеся в городе i пойдет в город $p_i$. Найдите максимальное количество роботов, которые одновременно будут в одном городе.
Во второй строке находятся n целых числа $p_1, p_2, ..., p_n$ ($1 ≤ p_i ≤ n$) и $p_i \ne i$.
В третьей строке находятся n целых числа $a_1, a_2, ..., a_n$ ($0 ≤ a_i ≤ 10^9$), где $a_i$ - количество роботов в i-ом городе.
В 20% тестовых данных: 2 ≤ n ≤ 2000.
В 20% тестовых данных: 2 ≤ n ≤ 105, а также выполняются следующие условия:
Входные данные
В первой строке входных данных находится одно целое число $n$($2 ≤ n ≤ 10^5$) - количество городов.Во второй строке находятся n целых числа $p_1, p_2, ..., p_n$ ($1 ≤ p_i ≤ n$) и $p_i \ne i$.
В третьей строке находятся n целых числа $a_1, a_2, ..., a_n$ ($0 ≤ a_i ≤ 10^9$), где $a_i$ - количество роботов в i-ом городе.
Выходные данные
Выведите одно целое число — максимальное возможное количество роботов, которые будут находиться в одном городе одновременно.Примеры:
1. Вход:3 2 3 1 5 4 8Ответ:
82. Вход:
5 5 3 4 2 1 7 6 0 3 3Ответ:
73. Вход:
7 7 1 1 3 3 7 4 3 1 4 0 2 0 2Ответ:
54. Вход:
12 11 1 6 1 7 8 8 7 7 9 12 11 12 29 7 19 4 8 39 31 22 34 25 40Ответ:
815. Вход:
10 2 1 1 1 3 4 3 6 7 8 2 3 1 4 0 5 1 1 3 0Ответ:
12
Оценивание:
В 8% тестовых данных: $2 ≤ n ≤ 10^5$ , и $p_1, p_2, ..., p_n$ - является перестановкой чисел 1, 2, .., n.В 20% тестовых данных: 2 ≤ n ≤ 2000.
В 20% тестовых данных: 2 ≤ n ≤ 105, а также выполняются следующие условия:
- a) p1 = 2, p2 = 1
- b) Из любого города можно добраться в город с номером 1. В остальных ограничения из условия.
комментарий/решение
Хром очень любит шоколадки. У него есть шоколадка Everest Silver размером $1$ x $n$. На каждом кусочке шоколада написано число $a_i$. Вкусность плитки определяется xor-суммой по числам на её кусочках. Хром хочет съесть весь шоколад. Он может съедать по одному кусочку шоколада в определенном порядке. После каждого съеденного кусочка плитка, которой принадлежал кусочек, поделится на два. Хром хочет знать максимальную вкусность среди оставшихся плиток шоколада после каждого съеденного кусочка. Так как он очень спешит, он просит вас помочь ему.
В 16% тестов: В порядке будут задаваться сперва нечетные в порядке возрастания, а затем четные в порядке возрастания, второй пример соответствует данному условию, $1 ≤ n ≤ 10^5$.
После съедания первого кусочка шоколад поделился на 2 плитки: [1], [5, 4, 3].
Наибольшая вкусность равняется 2 потому что xor-сумма первой плитки равняется - 1, xor-сумма второй равняется 5 xor 4 xor 3 = 2, из них наибольшее - 2.
После исчезновения второго кусочка шоколад поделился на 3 плитки: [1], [5], [3]
Наибольшая вкусность равняется 5.
Побитовое исключающее ИЛИ (xor) — это бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичной записи операндов. Иными словами, если соответствующие биты операндов различны, то соответствующий двоичный разряд результата равен 1; если же биты одинаковые, то двоичный разряд результата равен 0.
Например, если $X = 109_{10} = 1101101_2$, $Y = 41_{10} = 101001_2$ тогда: $X$ xor $Y$ = $68_{10}$ = $1000100_2$. Xor-суммой последовательности называется $xor$ всех элементов последовательности — $a_1 xor a_2 xor ... xor a_{n−1} xor a_n$.
Входные данные
В первой строке находится целое положительное число $n (1 ≤ n ≤ 10^5)$ - длина шоколада. Во второй строке находятся n чисел $a_i (1 ≤ a_i ≤ 10^9)$. В последней строке находятся $n$ целых положительных чисел $x (1 ≤ x ≤ n)$ - номер очередного съеденного кусочка.Выходные данные
Выведите $n$ чисел - наибольшую вкусность по всем плиткам.Система оценки
В 24% тестов: $1 ≤ n ≤ 1000$.В 16% тестов: В порядке будут задаваться сперва нечетные в порядке возрастания, а затем четные в порядке возрастания, второй пример соответствует данному условию, $1 ≤ n ≤ 10^5$.
Примеры:
1. Вход:5 1 2 5 4 3 2 4 1 3 5Ответ:
2 5 5 3 02. Вход:
5 1 2 5 4 3 1 3 5 2 4Ответ:
0 7 4 4 0
Примечание:
Изначально шоколад состоит из 5 кусков: [1, 2, 5, 4, 3].После съедания первого кусочка шоколад поделился на 2 плитки: [1], [5, 4, 3].
Наибольшая вкусность равняется 2 потому что xor-сумма первой плитки равняется - 1, xor-сумма второй равняется 5 xor 4 xor 3 = 2, из них наибольшее - 2.
После исчезновения второго кусочка шоколад поделился на 3 плитки: [1], [5], [3]
Наибольшая вкусность равняется 5.
Побитовое исключающее ИЛИ (xor) — это бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичной записи операндов. Иными словами, если соответствующие биты операндов различны, то соответствующий двоичный разряд результата равен 1; если же биты одинаковые, то двоичный разряд результата равен 0.
Например, если $X = 109_{10} = 1101101_2$, $Y = 41_{10} = 101001_2$ тогда: $X$ xor $Y$ = $68_{10}$ = $1000100_2$. Xor-суммой последовательности называется $xor$ всех элементов последовательности — $a_1 xor a_2 xor ... xor a_{n−1} xor a_n$.
комментарий/решение