Спасибо за участие! Надеемся, что вам понравились задачи!
1805A - Нам нужен ноль
Идея и разработка: Alexdat2000
Подсказка 1
Вспомните основные свойства операции $$$\oplus$$$: $$$A \oplus 0 = A$$$, $$$A \oplus A = 0$$$, $$$A \oplus B = B \oplus A$$$.
Подсказка 2
Рассмотрите случаи чётной и нечётной длины массива.
Разбор
Tutorial is loading...
Решение
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
xor = 0
for x in a:
xor ^= x
if xor == 0:
print(0)
else:
if n % 2 == 1:
print(xor)
else:
print(-1)
1805B - У строки есть цель
Идея и разработка: Alexdat2000
Подсказка 1
Какой должен быть первый символ, если мы пытаемся сделать строку лексикографически минимальной?
Подсказка 2
Рассмотрим строку «baba». Если выбрать $$$i=2$$$, то получится строка «abba», а если выбрать $$$i=4$$$, то получится «abab». Попробуйте обобщить эти рассуждения на любую строку.
Разбор
Tutorial is loading...
Решение
for _ in range(int(input())):
n = int(input())
s = input()
ind = s.rfind(min(s)) # Find the last ind such that s[ind] = min(s)
print(s[ind] + s[:ind] + s[ind + 1:])
1805C - Места для селфи
Идея и разработка: Alexdat2000
Подсказка 1
Заметим, что расстояние между прямой и параболой тоже будет параболой. Тогда какое условие на то, что прямая и парабола не имеют общих точек?
Подсказка 2
Вспомним формулу дискриминанта из школы: Если дана парабола $$$ax^2 + bx + c$$$, то вычислим $$$D=b^2 - 4ac$$$ (дискриминант). Тогда, если $$$D > 0$$$, то у параболы $$$2$$$ корня, если $$$D=0$$$, то один корень, если $$$D<0$$$, то корней нет.
Подсказка 3
Если мы выберем параболу $$$ax^2 + bx + c$$$, то не имеют с ней общих точек прямые с таким коэффициентом $$$k$$$, что $$$(b-k)^2<4ac$$$. Как найти такое $$$k$$$ среди данных?
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector <int> lines(n);
for (int i = 0; i < n; i++) {
cin >> lines[i];
}
sort(lines.begin(), lines.end());
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
int ind = lower_bound(lines.begin(), lines.end(), b) - lines.begin();
if (ind < n && (lines[ind] - b) * (lines[ind] - b) < 4 * a * c) {
cout << "YES\n" << lines[ind] << "\n";
continue;
}
if (ind > 0 && (lines[ind - 1] - b) * (lines[ind - 1] - b) < 4 * a * c) {
cout << "YES\n" << lines[ind - 1] << "\n";
continue;
}
cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q = 1;
cin >> q;
while (q--) {
solve();
}
return 0;
}
1805D - Широкий-преширокий граф
Идея: FairyWinx, разработка: Alexdat2000
Подсказка 1
При каком максимальном $$$k$$$ граф $$$G_k$$$ не распадается на одиночные компоненты? Что будет происходить, если уменьшать $$$k$$$ на $$$1$$$?
Подсказка 2
Рассмотрим какой-то диаметр дерева (путь самой большой длины). Если в графе $$$G_k$$$ вершина имеет соседа, то она также соединена ребром с одним из концов диаметра. Как можно использовать этот факт для поиска ответа для $$$k$$$, если мы знаем компоненты графа $$$G_{k+1}$$$?
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const int N = 1e5 + 228;
vector<int> G[N];
void dfs(int v, int par, int h, vector<int> &d) {
d[v] = h;
for (int i : G[v]) {
if (i != par) {
dfs(i, v, h + 1, d);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
G[a - 1].push_back(b - 1);
G[b - 1].push_back(a - 1);
}
vector<int> d1(n), d2(n);
dfs(0, -1, 0, d1);
int a = max_element(all(d1)) - d1.begin();
dfs(a, -1, 0, d1);
int b = max_element(all(d1)) - d1.begin();
dfs(b, -1, 0, d2);
for (int i = 0; i < n; ++i) {
d2[i] = max(d2[i], d1[i]);
}
sort(all(d2));
int ans = 0;
for (int i = 1; i <= n; ++i) {
while (ans < n && d2[ans] < i) {
++ans;
}
cout << min(n, ans + 1) << ' ';
}
cout << '\n';
}
1805E - Максимумов должно быть много
Идея и разработка: Alexdat2000
Подсказка 1
Пусть $$$M$$$ — значение $$$MAD$$$ всего дерева. Чему будет равен ответ, если вершин со значением $$$M$$$ много в дереве?
Подсказка 2
Заметим, что для многих рёбер ответом будет $$$M$$$. А для каких рёбер это не так?
Подсказка 3
Пусть в дереве есть всего две вершины со значением $$$M$$$. Тогда для рёбер не на пути между ними мы знаем ответ. А что делать с путём между двумя вершинами $$$M$$$? Можно ли пройти по нему, посчитав ответ для всех вершин?
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
vector <pair <int, int>> g[N];
int val[N];
vector <int> ans;
map <int, int> cnt1, cnt2;
set <int> mad1, mad2;
vector <int> path, path_ind;
bool used[N];
bool dfs(int v, int tar) {
used[v] = true;
path.push_back(v);
if (v == tar) {
return true;
}
for (auto [i, ind] : g[v]) {
if (!used[i]) {
path_ind.push_back(ind);
if (dfs(i, tar)) {
return true;
}
path_ind.pop_back();
}
}
path.pop_back();
return false;
}
int mad() {
int mx = 0;
if (!mad1.empty()) {
mx = max(mx, *mad1.rbegin());
}
if (!mad2.empty()) {
mx = max(mx, *mad2.rbegin());
}
return mx;
}
void recalc(int v, int ban1, int ban2) {
cnt1[val[v]]++;
if (cnt1[val[v]] == 2) {
mad1.insert(val[v]);
}
cnt2[val[v]]--;
if (cnt2[val[v]] == 1) {
mad2.erase(val[v]);
}
for (auto [i, _] : g[v]) {
if (i != ban1 && i != ban2) {
recalc(i, v, -1);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
map <int, vector <int>> ind;
for (int i = 0; i < n; i++) {
cin >> val[i];
ind[val[i]].push_back(i);
cnt2[val[i]]++;
if (cnt2[val[i]] == 2) {
mad2.insert(val[i]);
}
}
while (!ind.empty() && ind.rbegin() -> second.size() == 1) {
ind.erase(prev(ind.end()));
}
if (ind.empty()) {
for (int i = 0; i < n - 1; i++) {
cout << "0\n";
}
return 0;
} else if (ind.rbegin()->second.size() > 2) {
for (int i = 0; i < n - 1; i++) {
cout << ind.rbegin() -> first << "\n";
}
return 0;
}
int a = ind.rbegin()->second[0], b = ind.rbegin()->second[1];
dfs(a, b);
ans.assign(n - 1, ind.rbegin() -> first);
recalc(path[0], path[1], -1);
ans[path_ind[0]] = mad();
for (int i = 1; i + 1 < path.size(); i++) {
recalc(path[i], path[i - 1], path[i + 1]);
ans[path_ind[i]] = mad();
}
for (int i : ans) {
cout << i << "\n";
}
return 0;
}
1805F2 - Выживание слабейших (сложная версия)
Идея и разработка: sevlll777
Подсказки для простой версии:
Подсказка 1
Придумайте как реализовать функцию $$$F$$$ за $$$O(n log n)$$$
Подсказка 1.1
Понадобится $$$std::priority\_queue$$$ или $$$std::set$$$
Подсказка 2
Если $$$n - 1$$$ раз запустить функцию $$$F$$$ за $$$O(n log n)$$$ мы получим решение за $$$O(n^2 log n)$$$. Однако, числа в массиве могут расти очень быстро. Можете ли вы как-то модифицировать числа в массиве, чтобы $$$F$$$ изменилась предсказуемым образом?
Подсказка 2.2
$$$F([a_1, a_2, \ldots, a_n]) = F([a_1 - x, a_2 - x, \ldots, a_n - x]) + x \cdot 2^{n-1}$$$
Подсказки для сложной версии:
Подсказка 3
Как решать задачу если $$$a_i \leq 1$$$? $$$\leq 2$$$? Можете ли вы что-то заметить про эти решения?
Подсказка 4
Если $$$n$$$ достаточно велико, то $$$F(F(\ldots F([a_1, a_2, \ldots, a_n])\ldots)) = F(F( \ldots F([a_1, a_2, \ldots, a_{n-1}, X])\ldots))$$$ где $$$X$$$ любое число $$$\geq a_{n-1}$$$, другими словами: наибольший элемент бесполезен для финального ответа
Подсказка 5
Только небольшое количество наименьших элементов изначального массива повлияют на ответ
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define all(x) x.begin(), (x).end()
using namespace std;
const int M = 1000000007;
long long ans = 0;
int real_len = 0;
long long binpow(long long a, int x) {
long long ans0 = 1;
while (x) {
if (x % 2) {
ans0 *= a;
ans0 %= M;
}
a *= a;
a %= M;
x /= 2;
}
return ans0;
}
void chill(vector<int> &b) {
int mn = b[0];
ans += (int) ((long long) mn * binpow(2, real_len - 1) % M);
if (ans >= M) {
ans -= M;
}
for (auto &x : b) {
x -= mn;
}
}
void F(vector<int> &b, int sub = 0) {
--real_len;
vector<int> cnd;
for (int i = 0; i < b.size(); i++) {
for (int j = i + 1; j < b.size(); j++) {
if (i * j >= b.size()) break;
cnd.push_back(b[i] + b[j]);
}
}
sort(all(cnd));
vector<int> b2((int) b.size() - sub);
for (int i = 0; i < (int) b.size() - sub; i++) {
b2[i] = cnd[i];
}
chill(b2);
b = b2;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(all(a));
int L = 64;
vector<int> b(min(n, L));
for (int i = 0; i < min(n, L); i++) {
b[i] = a[i];
}
real_len = n;
chill(b);
while (b.size() < real_len) {
if (b[1] + b[2] > b.back()) {
F(b, 1);
F(b, 1);
} else {
F(b);
}
}
while (real_len > 1) {
F(b, 1);
}
ans += b[0];
ans %= M;
cout << ans << '\n';
}
