Всем привет! Просим прощения за задержку >_<
Надеемся, что вам понравились наши задачи! Извините за то, что лимиты по времени и памяти в некоторых задачах были слишком жесткими и решения на Java не проходили С (кстати, у одного из авторов бывшый ник — "java." :D). Постараемся не допустить таких ошибок вновь.
Оставляйте впечатления и пожелания в комментариях! Спасибо за участие!
1867A — green_gold_dog, массив и перестановка
Автор: green_gold_dog
Из минимального числа вычтем $$$n$$$, из следующего $$$n - 1$$$, из следующего $$$n - 2$$$, $$$\ldots$$$, из максимального $$$1$$$. Тогда количество различных элементов будет $$$n$$$. Очевидно лучшего результа достичь невозможно.
Докажем, что количество различных элементов будет равно $$$n$$$. Допустим $$$c_i = c_j$$$, тогда без ограничения общности скажем, что $$$b_i > b_j$$$, тогда $$$a_i \leq a_j$$$, значит $$$c_i = a_i - b_i$$$ < $$$a_j - b_j = c_j$$$. Противоречие.
Асимптотика: $$$O(n \log n)$$$ на набор входных данных.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
ll n;
cin >> n;
vector<pair<ll, ll>> arr(n);
for (ll i = 0; i < n; i++) {
ll x;
cin >> x;
arr[i].first = x;
arr[i].second = i;
}
vector<ll> ans(n);
sort(arr.begin(), arr.end());
reverse(arr.begin(),arr.end());
for (ll i = 0; i < n; i++) {
ans[arr[i].second] = i + 1;
}
for (auto i : ans) {
cout << i << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
cin >> t;
for (ll i = 0; i < t; i++) {
solve();
}
}
Автор: ace5
Во-первых, строка является палиндромом если и только если для любого $$$i$$$ ($$$1 \leq i \leq n$$$) $$$s_i = s_{n-i+1}$$$ (потому что при развороте $$$s_i$$$ становится $$$s_{n-i+1}$$$).
Мы можем разбить символы на пары, где в паре будут $$$s_i$$$ и $$$s_{n-i+1}$$$. Если $$$s_i = s_{n-i+1}$$$, то нам нужно иметь $$$l_i = l_{n-i+1}$$$, чтобы после ксора получились равные элементы. Поэтому либо $$$l_i = l_{n-i+1} = 0$$$ ($$$0$$$ единиц) либо $$$l_i = l_{n-i+1} = 1$$$ ($$$2$$$ единицы). Если же $$$s_i \neq s_{n-i+1}$$$, то должно быть $$$l_i \neq l_{n-i+1}$$$ ($$$1$$$ единица в любом случае). Дополнительно, если $$$n$$$ нечетное, то $$$l_{n/2+1}$$$ может быть либо $$$0$$$, либо $$$1$$$ ($$$0$$$ или $$$1$$$ единица).
Мы можем перебрать, сколько пар где $$$l_i = l_{n-i+1}$$$ будут иметь две единицы а также будет единица по центру или нет, так мы сможем получить все возможные количества единиц в $$$l$$$, то есть все хорошие $$$i$$$.
Асимптотика: $$$O(n)$$$ на набор входных данных.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
string s;
cin >> s;
string t(n+1,'0');
int ans = 0;
int max_1 = 0;
int max_2 = 0;
for(int i = 0;i <= n/2-1;++i)
{
if(s[i] == s[n-i-1])
max_2++;
else
ans++;
}
if(n%2 == 1)
max_1++;
for(int j = 0;j <= max_2;++j)
{
for(int k = 0;k <= max_1;++k)
{
t[ans + j*2 + k] = '1';
}
}
cout << t << "\n";
}
}
Автор: salyg1n
Правильной стратегией за Алису является добавление в множество $$$S$$$ числа $$$\operatorname{MEX}(S)$$$ на первом ходу, и добавление последнего удаленного числа на оставшихся ходах.
Пусть m = $$$\operatorname{MEX}(S \cup {\operatorname{MEX}(S)})$$$, на момент начала игры. Иначе говоря m равняется второму $$$\operatorname{MEX}$$$ множества $$$S$$$. $$$m \geq 1$$$.
Заметим, что после первого хода выполнится $$$\operatorname{MEX}(S) = m$$$, а дальше что бы не удалил Боб, мы вернем это число в множество, а значит результат игры всегда будет равен $$$m$$$.
Докажем, что при оптимальной игре боба мы не сможем получить результат больше m.
Заметим, что $$$\operatorname{MEX}$$$ множества — это наибольшее число k, такое что все числа от $$$0$$$ до $$$k-1$$$ включительно содержатся в этом множестве.
Пусть $$$p_i$$$ равно количеству чисел от $$$0$$$ до $$$i-1$$$ включительно встречающихся в множестве $$$S$$$. Тогда $$$\operatorname{MEX}(S)$$$ равен максимальному $$$i$$$ такому, что $$$p_i = i$$$.
Если Боб во время своего хода удалит число $$$y$$$, он уменьшит на $$$1$$$ все значения $$$p_i$$$, где $$$i > y$$$. Тогда если $$$y = \operatorname{min}(S)$$$, боб уменьшит на $$$1$$$ все ненулевые значения $$$p_i$$$.
Алиса может в свой ход увеличить некоторые значения $$$p_i$$$ на $$$1$$$. Значит после первого хода Алисы, $$$\operatorname{MEX}(S)$$$ уже не будет увеличиваться, если Боб будет удалять минимум, т.к. никакие ненулевые $$$p_i$$$ не будут увеличиваться (Боб их уменьшать на $$$1$$$, а Алиса увеличивать не более чем на $$$1$$$).
Очевидно, что чтобы Алисе максимизировать $$$\operatorname{MEX}(S)$$$ после первого хода, ей необходимо добавить в множество $$$S$$$ число $$$\operatorname{MEX}(S)$$$.
Мы доказали, что $$$R \leq m$$$ и предоставили стратегию которая получает результат $$$m$$$.
Асимптотика: $$$O(n)$$$ на набор входных данных.
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> s(n);
for (int i = 0; i < n; ++i)
cin >> s[i];
int mex = -1;
for (int i = 0; i < n; ++i) {
if (i == 0 && s[i] != 0) {
mex = 0;
break;
}
if (i > 0 && s[i] != s[i - 1] + 1) {
mex = s[i - 1] + 1;
break;
}
}
if (mex == -1)
mex = s[n - 1] + 1;
cout << mex << endl;
int y;
cin >> y;
while (y != -1) {
cout << y << endl;
cin >> y;
}
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Автор: ace5
Если $$$k = 1$$$ то мы можем менять $$$b_i$$$ на $$$i$$$, поэтому ответ YES только если $$$b_i = i$$$, иначе ответ NO.
Иначе, построим неориентированный граф на $$$n$$$ вершинах с ребрами ($$$i, b_i$$$). Любая компонента этого графа будет выглядеть как цикл(возможно из $$$1$$$ вершины) к каждой вершине которого подвешено дерево(возможно, пустое).
Пусть в компоненте $$$x$$$ вершин, тогда в ней и $$$x$$$ ребер(так как из каждой вершины выходит одно ребро). Мы можем построить дерево обхода dfs этой компоненты, в нем будет $$$x - 1$$$ ребро. Теперь, когда мы добавим оставшееся ребро ($$$u, v$$$), в компоненте образуется один цикл(образованный ребром ($$$u, v$$$) и путем между $$$u$$$ и $$$v$$$ в дереве обхода dfs). К каждой вершине будет подвешено дерево, потому что до добавления ребра у нас было дерево.
Теперь утверждается, что если цикл в каждой компоненте имеет размер ровно $$$k$$$, то ответ YES, а иначе NO.
Для начала рассмотрим ситуацию, где в какой-то компоненте размер цикла не $$$k$$$. Пусть цикл содержит вершины $$$v_1, v_2, \cdots, v_x$$$ в таком порядке. Тогда посмотрим на последнюю операцию, в которой одно из $$$l_i$$$ было равно какому-то элементу из цикла. Если размер цикла меньше $$$k$$$, то в последней операции будет хотя бы одна вершина не из цикла, значит хотя бы одна вершина из цикла заменится на номер вершины не из цикла, что неверно, ведь каждая вершина из цикла должна заменится на номер следующей после нее вершины. Если размер цикла больше $$$k$$$, то у нас будет вершина из цикла, которая заменится не на следующую вершину из цикла(иначе мы бы поиспользовали все вершины цикла, а их больше чем $$$k$$$). Следовательно в любом случае корректной последней операции с вершинами из цикла не существует, поэтому ответ NO.
Если в компоненте размер цикла равен $$$k$$$, то мы можем применить следующий алгоритм:
Пока в компоненте есть хотя бы одна вершина $$$v$$$, которая является листом, мы будем делать операцию с $$$l = [v, b_v, b_{b_v}, \cdots]$$$ (все элементы различны так как мы придем в цикл а он размера $$$k$$$). После этой операции у нас станет $$$a_v = b_v$$$, и мы можем убрать вершину $$$v$$$(из нее шло только $$$1$$$ ребро).
Когда останется только цикл, мы можем применить операцию для вершин цикла, сохраняя порядок, после чего для всех вершин компоненты будет $$$a_v = b_v$$$. Проделав это со всеми компонентами получим $$$a = b$$$, что и требовалось, поэтому ответ YES.
Асимптотика: $$$O(n)$$$ на набор входных данных.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
{
int n,k;
cin >> n >> k;
int b[n];
int vis[n];
for(int j = 0;j < n;++j)
{
cin >> b[j];
vis[j] = 0;
}
if(k == 1)
{
int no = 0;
for(int j = 0;j < n;++j)
{
if(b[j] != j+1)
{
no = 1;
}
}
cout << (no ? "NO\n" : "YES\n");
continue;
}
int num[n];
int no = 0;
int tgr = 1;
for(int j = 0;j < n;++j)
{
if(!vis[j])
{
int ind = j;
int cnum = 0;
while(!vis[ind])
{
vis[ind] = tgr;
num[ind] = cnum++;
ind = b[ind]-1;
}
if(vis[ind] != tgr)
{
tgr++;
continue;
}
if(cnum-num[ind] != k)
{
no = 1;
break;
}
tgr++;
}
}
cout << (no ? "NO\n" : "YES\n");
}
}
1867E1-salyg1n и массив (простая версия)
Автор: salyg1n
Сделаем запросы к подотрезкам начинающимся в позициях $$$1$$$, $$$k + 1$$$, $$$2k + 1$$$, $$$\ldots$$$ $$$m \cdot k + 1$$$, пока эти запросы корректны, то есть их правая граница не превосходит $$$n$$$. Сохраним $$$\operatorname{XOR}$$$ всех ответов на эти запросы. Назовем эти запросы первичными.
Теперь будем сдвигать последний подотрезок запроса на единицу вправо и делать новый запрос, пока правая граница не превосходит $$$n$$$. Назовем эти запросы вторичными. Утверждается, что $$$\operatorname{XOR}$$$ всего массива будет равен $$$\operatorname{XOR}$$$'у всех запросов. Докажем это.
Пусть $$$i$$$ "--- позиция в которой начинается первый вторичный запрос. Заметим, что после этого запроса, подотрезок [$i$; $$$i + k - 2$$$] превратится в подотрезок [$$$i + 1$$$; $$$i + k - 1$$$] и развернется. После следующего запроса произойдет то же самое, отрезок сдвинется на единицу вправо и развернется. Значит префиксы длины $$$k-1$$$ каждого вторичного запроса "--- одинаковые, с точностью до разворота, который не влияет на $$$\operatorname{XOR}$$$. Так как количество вторичных запросов равно $$$n \operatorname{mod} k$$$, что является четным числом, $$$\operatorname{XOR}$$$ этих префиксов не будет влиять на $$$\operatorname{XOR}$$$ всех вторичных запросов, который следовательно будет равен $$$\operatorname{XOR}$$$'у элементов [$a_{i + k — 1}$; $a_n$], то есть всех элементов, которых мы не учли в первичных запросах.
Количество первичных запросов равно $$$\lfloor \frac{n}{k} \rfloor \leq k \leq 50$$$, так как. $$$n \leq k^2 \leq 2500$$$.
Количество вторичных запросов равно $$$n \operatorname{mod} k < k <= 50$$$, так как. $$$k^2 \leq 2500$$$.
Итоговое количество запросов не превосходит $$$100$$$.
#include <iostream>
using namespace std;
int ask(int i) {
cout << "? " << i << endl;
int x;
cin >> x;
return x;
}
void solve() {
int n, k;
cin >> n >> k;
int res = 0;
int i;
for (i = 1; i + k - 1 <= n; i += k)
res ^= ask(i);
for (; i <= n; ++i)
res ^= ask(i - k + 1);
cout << "! " << res << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
1867E2-salyg1n и массив (сложная версия)
Автор: salyg1n
Сделаем запросы к подотрезкам начинающимся в позициях $$$1$$$, $$$k + 1$$$, $$$2k + 1$$$, $$$\ldots$$$ $$$m \cdot k + 1$$$, так, чтобы размер непокрытой части был больше $$$2 \cdot k$$$ и не больше $$$3 \cdot k$$$. Иначе говоря $$$2 \cdot k < n - (m + 1) \cdot k \le 3 \cdot k$$$. Сохраним $$$\operatorname{XOR}$$$ всех ответов на эти запросы. Назовем эти запросы первичными.
Пусть размер оставшейся (непокрытой) части равен $$$x$$$ ($$$2 \cdot k < x \le 3 \cdot k$$$). Научимся решать задачу для массива размера $$$x$$$ за три запроса.
Если $$$x = 3 \cdot k$$$ просто сделаем запросы к позициям $$$1$$$, $$$k + 1$$$, $$$2 \cdot k + 1$$$.
Иначе пусть $$$y = x - k$$$. Заметим, что $$$y$$$ "--- четное, так как $$$x$$$ и $$$k$$$ четные.
Сделаем запросы в позициях $$$1$$$, $$$1 + \frac{y}{2}$$$, $$$1 + y$$$.
Заметим, что после этого запроса, подотрезок [$1$; $$$k - \frac{y}{2}$$$] превратится в подотрезок [$$$y/2 + 1$$$; $$$k$$$] и развернется. После следующего запроса произойдет то же самое, отрезок сдвинется на единицу вправо и развернется. Значит префиксы длины $$$k - \frac{y}{2}$$$ каждого запроса "--- одинаковые, с точностью до разворота, который не влияет на $$$\operatorname{XOR}$$$. Так как количество запросов второй группы равно $$$3$$$, что является нечетным числом, $$$\operatorname{XOR}$$$ этих префиксов учтется ровно один раз в $$$\operatorname{XOR}$$$'е всех запросов, который следовательно будет равен $$$\operatorname{XOR}$$$'у элементов.
Количество первичных запросов не превосходит $$$\lfloor \frac{n}{k} \rfloor \leq k \leq 50$$$, так как. $$$n \leq k^2 \leq 2500$$$.
Итоговое количество запросов не превосходит $$$53$$$.
#include <iostream>
using namespace std;
int ask(int i) {
cout << "? " << i << endl;
int x;
cin >> x;
return x;
}
void solve() {
int n, k;
cin >> n >> k;
int res = 0;
int i;
for (i = 1; n - i + 1 >= 2 * k; i += k)
res ^= ask(i);
if (n - i + 1 == k) {
res ^= ask(i);
cout << "! " << res << endl;
return;
}
int y = (n - i + 1 - k) / 2;
res ^= ask(i);
res ^= ask(i + y);
res ^= ask(i + 2 * y);
cout << "! " << res << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
1867F-Максимально не похожее дерево
Автор: green_gold_dog
Скажем, что $$$\it{ответ}$$$ для дерева $$$G'$$$ это количество поддеревьев в $$$P(G')$$$ к которым есть изоморфные в $$$P(G)$$$.
Давайте найдём дерево $$$T$$$ минимально размера, к которому нет изоморфного в $$$P(G)$$$. Скажем, что размер дерева $$$T$$$ это $$$x$$$. Тогда возьмём бамбук размера $$$n - x$$$, подвесим $$$T$$$ к последней вершине бамбука и скажем, что это и есть то дерево $$$G'$$$, которое мы искали (корнем $$$G'$$$ будет первая вершина бамбука). Количество совпадающих поддеревьев будет не больше $$$x - 1$$$, т.к. все поддеревья вершин бамбука (к которому мы подвесили $$$T$$$) и само поддерево $$$T$$$ не будут иметь изоморфные в $$$P(G)$$$, ведь в их поддереве есть поддерево $$$T$$$, к которому нет изоморфного в $$$P(G)$$$, значит ответ не более $$$n - (n - x) - 1 = x - 1$$$.
Докажем почему ответ не может быть меньше $$$x - 1$$$: представим, что существует дерево $$$G*$$$ для которого ответ меньше $$$x - 1$$$. Тогда найдём в нём поддерево минимального размера, размер которого не меньше $$$x$$$ (оно всегда найдётся, ведь как минимум можно взять все дерево), в этом поддереве есть еще хотя бы $$$x - 1$$$ поддерево, у каждого из них размер строго меньше $$$x$$$ (ведь на прошлом шаге мы выбрали поддерево минимального размера не меньшего $$$x$$$), а т.к. ко всем деревьям размера меньше $$$x$$$ есть изоморфные в $$$P(G)$$$ (ведь по определению $$$T$$$ — это дерево минимального размера, к которому нет изоморфного в $$$P(G)$$$, а его размер $$$x$$$) то количество совпадающих поддеревьев в дереве $$$G*$$$ это хотя-бы $$$x - 1$$$, противоречие.
Значит в нашем случае ответ $$$x - 1$$$ и меньше быть не может.
Теперь вторая часть задачи — найти $$$T$$$. Для того чтобы это сделать, давайте найдём сначала все деревья размера 1, потом 2, потом 3, 4, и так далее пока не найдем дерево, которому нет изоморфных в $$$P(G)$$$. Можно заметить, что если сгенерировать все деревья размера не больше 15, то там точно найдется $$$T$$$. Внутри каждого размера пронумеруем деревья в порядке перебора. Для того, чтобы найти все деревья размера $$$x$$$ имея все деревья размера $$$x - 1$$$ или меньше давайте скажем, что размеры детей у корня дерева, которое мы генерируем, должны не убывать, а если размеры совпадают, то номера должны не убывать, тогда можно перебрать первого сына, потом среди меньших и подходящих по размеру второго, потом третьего, и так далее пока размер нашего дерева не станет ровно $$$x$$$, тогда мы переберём все деревья размера $$$x$$$ за их количество (т.к. мы не рассмотрим ни одно дерево дважды и лишних тоже не рассмотрим). Будем это делать пока не найдем дерево, которого нет в $$$P(G)$$$.
Для сравнения деревьев на изоморфность можно использовать хеши. Подробнее прочитайте в блоге:
Асимптотика: $$$O(n \log n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int MAXSZ = 15;
void rec(int ns, int last, vector<int>& now, vector<vector<int>>& aint, vector<int>& col, vector<int>& sz, int& ss, int sns) {
if (ss < 0) {
return;
}
if (ns == 0) {
col.back()++;
aint.push_back(now);
ss -= sns;
return;
}
for (int i = min(last, col[ns] - 1); i >= 0; i--) {
now.push_back(i);
rec(ns - sz[i], i, now, aint, col, sz, ss, sns);
now.pop_back();
}
}
void dfs(int v, int p, vector<vector<int>>& arr, vector<int>& num, map<vector<int>, int>& m, vector<int>& sz) {
vector<int> now;
sz[v] = 1;
for (auto i : arr[v]) {
if (i != p) {
dfs(i, v, arr, num, m, sz);
sz[v] += sz[i];
if (sz[v] <= MAXSZ) {
now.push_back(num[i]);
}
}
}
if (sz[v] > MAXSZ) {
num[v] = -1;
return;
}
stable_sort(now.begin(), now.end());
reverse(now.begin(), now.end());
num[v] = m[now] - 1;
}
void dfs2(int x, int p, vector<vector<int>>& aint, vector<int>& ans) {
if (p >= 0) {
ans.push_back(p);
}
int now = ans.size();
for (auto i : aint[x]) {
dfs2(i, now, aint, ans);
}
}
void solve() {
int n;
cin >> n;
vector<vector<int>> aint(1);
vector<vector<int>> arr(n);
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
arr[a].push_back(b);
arr[b].push_back(a);
}
map<vector<int>, int> m;
vector<int> col(1, 0), sz(1, 1);
col.push_back(1);
for (int i = 2; i <= MAXSZ; i++) {
vector<int> now;
col.push_back(col.back());
int ss = n;
rec(i - 1, aint.size() - 1, now, aint, col, sz, ss, i);
while (sz.size() < col.back()) {
sz.push_back(i);
}
if (ss < 0) {
break;
}
}
for (int i = 0; i < col.back(); i++) {
m[aint[i]] = i + 1;
}
vector<int> num(n), szi(n, 1);
dfs(0, 0, arr, num, m, szi);
set<int> s;
for (int i = 0; i < col.back(); i++) {
s.insert(i);
}
for (auto i : num) {
s.erase(i);
}
int x = *s.begin();
vector<int> ans;
if (sz[x] > n) {
for (int i = 0; i < n; i++) {
for (auto j : arr[i]) {
if (i < j) {
cout << i + 1 << ' ' << j + 1 << '\n';
}
}
}
return;
}
for (int i = 0; i < n - sz[x] - 1; i++) {
ans.push_back(i);
}
dfs2(x, n - sz[x] - 1, aint, ans);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] + 1 << ' ' << i + 2 << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
for (int i = 0; i < t; i++) {
solve();
}
}
