Всем привет! Сегодня раунд получился довольно интересным, поэтому я решил сделать разбор на задачи A–D1. P>S Если вам не понятны какие то части разбора, то смело смотрите код).↵
<p align="center">↵
<img src="https://i.ibb.co.com/7tGX7dh1/1705387659-krots-top-p-milie-animeshnie-kotiki-pinterest-43-1.jpg" width="200" height="200">↵
</p> ↵
↵
↵
<spoiler summary="Задача A"> ↵
**Полное решение:** ↵
Пусть `f(x)` — количество вхождений числа `x` в массив. При построении последовательности мы всегда ограничены минимальным `f(x)` среди выбранных элементов. ↵
↵
Если взять элемент с частотой `f(x)`, то длина последовательности может увеличиться:↵
↵
```↵
mx = max(mx, f(x) * cnt),↵
```↵
↵
где `cnt` — количество уже добавленных элементов, включая текущий.↵
↵
Так последовательно обновляем ответ и выводим `mx`.↵
↵
**Алгоритм:**↵
↵
1. Посчитать частоты `f(x)` для всех чисел.↵
2. Отсортировать или перебрать их по убыванию.↵
3. На каждом шаге обновлять `mx`.↵
4. Вывести максимальный результат.↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll st = 0;↵
map<ll,ll> mp;↵
ll cnt = 0;↵
ll n; cin >> n;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
mp[x]++;↵
}↵
vector<pair<ll,ll>> ans;↵
map<ll,ll> mpp;↵
for (ll x: a){↵
mpp[x]++;↵
if(mpp[x]==1){↵
ans.pb({mp[x],x});↵
}↵
}↵
sort(allr(ans));↵
ll sm = 0;↵
for (ll i = 0;i<ans.size();i++){↵
// cout << ans[i].f << endl;↵
sm = max(sm,ans[i].f*(i+1));↵
}↵
cout << sm << endl;↵
↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Задача B"> ↵
**Полное решение:** ↵
Ответ невозможен, если хотя бы один элемент от `1` до `m` отсутствует во всех множествах. ↵
↵
Теперь рассмотрим множества, где для каждого элемента количество вхождений ≥ 2 (включая учёт подмножеств). Пусть таких множеств `cnt`.↵
↵
Если `cnt ≥ 2`, то мы всегда можем построить как минимум три разные конфигурации:↵
↵
1. взять всё множество + `sx`,↵
2. взять всё множество + `sy`,↵
3. взять всё множество + `sx + sy`.↵
↵
Значит, в этом случае решение существует.↵
↵
**Алгоритм:**↵
↵
1. Проверить, что все элементы от `1` до `m` встречаются.↵
2. Посчитать `cnt` — число множеств, удовлетворяющих условию.↵
3. Если `cnt ≥ 2`, вывести "YES", иначе "NO".↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll a,b; cin >> a >> b;↵
ll cnt = 0;↵
map<ll,ll> mp;↵
map<ll,ll> mpp;↵
vector<vector<ll>> ak(a);↵
for (ll i = 0;i<a;i++){↵
ll x; cin >> x;↵
ak[i].resize(x);↵
// map<ll,ll> mpp;↵
for (ll j = 0;j<x;j++){↵
ll op; cin >> op;↵
ak[i][j] = op;↵
mpp[op]++;↵
}↵
↵
↵
}↵
// ll cnt = 0;↵
for (ll i = 0;i<a;i++){↵
bool check = 1;↵
for (ll j = 0;j<ak[i].size();j++){↵
if(mpp[ak[i][j]]==1){↵
check = 0;↵
break;↵
}↵
}↵
if(check){↵
cnt++;↵
}↵
}↵
bool opt = 1;↵
for (ll i = 1;i<=b;i++){↵
if(mpp[i]==0){↵
opt = 0;↵
break;↵
}↵
}↵
if(!opt){↵
cout << "NO" << endl;↵
}else{↵
↵
cout << (cnt>=2 ?"YES": "NO") << endl;↵
}}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Задача C"> ↵
**Полное решение:** ↵
Разберём, как работает бинарный поиск: ↵
↵
* если `a[m] == i` → элемент найден;↵
* если `a[m] > i` → двигаем правую границу;↵
* если `a[m] < i` → двигаем левую границу.↵
↵
Чтобы `x` был найден, элементы слева должны быть меньше него, а справа — больше.↵
↵
Значит:↵
↵
* если `s[i] == '1'`, можно поставить `ans[i] = i`;↵
* если `s[i] == '0'`, то нужно поставить `ans[i] ≠ i`, сохранив корректность.↵
↵
Простейшее решение — перестановка `[2, 3, ..., n, 1]`. Она гарантирует, что для всех позиций с `0` элемент отличается от индекса. Естественно не стоит забывать про s[i]=='1', тогда ставим ans[i] = i.↵
↵
**Особый случай:** если встречается символ `0`, окружённый единицами (`...101...`), то условие нарушается: элементу придётся соответствовать позиции, но это запрещено. Тогда ответ невозможен.↵
↵
**Алгоритм:**↵
↵
1. Проверить строку на наличие "невозможного" шаблона.↵
2. Если он найден → вывести "NO".↵
3. Иначе построить перестановку `[2, 3, ..., n, 1]`.↵
4. Вывести её как ответ.↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll n; cin >> n;↵
string s; cin >> s;↵
vector<ll> a(n);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='1'){↵
a[i] =(i+1);↵
}↵
}↵
bool opt = 1;↵
map<ll,ll> mp;↵
vector<ll> temp(n);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='0'){↵
}else{↵
temp[i] = i+1;↵
mp[i+1]++;↵
}↵
}↵
ll i = 0;↵
while (i<n){↵
if(s[i]=='1'){↵
i++;↵
continue;↵
}↵
ll j = i;↵
ll op = j;↵
while (j<n && s[j]=='0'){↵
j++;↵
}↵
if(j-i==1){↵
opt = 0;↵
break;↵
}↵
for (ll k = i;k<j-1;k++){↵
temp[k] = k+2;↵
}↵
temp[j-1] = i+1;↵
i = j;↵
}↵
↵
if(!opt){↵
cout << "NO" << endl;↵
}else{↵
cout << "YES" << endl;↵
for (ll x: temp){↵
cout << x << " ";↵
}cout << endl;}↵
//cout << opt << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Задача D1"> ↵
**Полное решение:** ↵
Нужно максимизировать ↵
↵
```↵
Σ (ai OR bi).↵
```↵
↵
Пусть у нас есть перестановка `p`. Несложно заметить, что чтобы сделать сумму максимальной, выгодно каждому числу поставить его **битовую инверсию**.↵
↵
Почему?↵
↵
* Инверсия по битам гарантирует, что при `OR` получится максимальное количество единиц.↵
* Это работает для любого числа в диапазоне.↵
↵
Пример:↵
↵
```↵
x = 9 (1001₂), инверсия = 6 (0110₂).↵
9 OR 6 = 1111₂ = 15.↵
```↵
↵
Значит, при такой паре значение `OR` максимально возможное.↵
Стоит отметить, что если r == 0, то это не сработает, а значит нужно просто вывести↵
0 и 0, как ответ.↵
↵
**Алгоритм:**↵
↵
1. Идём по всем числам от `n` до `1`.↵
2. Для каждого числа `x` считаем его инверсию (по длине битов `n`).↵
3. Сохраняем в `mp[x]`.↵
4. Формируем перестановку:↵
↵
```↵
ans[i] = mp[i]↵
```↵
↵
5. Считаем итоговую сумму и выводим её вместе с перестановкой.↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll a,b; cin >> a >> b;↵
if(b==0){↵
cout << 0 << endl;↵
cout << "0" << endl;↵
}else{↵
vector<ll> temp(b+1);↵
map<ll,ll> mp;↵
for (ll i = b;i>=0;i--){↵
ll k = 32-__builtin_clz(i);↵
ll mask = (1<<k)-1;↵
ll opt = (~i)&mask;↵
if(mp[i]==0 && mp[opt]==0){↵
mp[i] = opt;↵
mp[opt] = i;↵
}↵
// cout << opt << endl;↵
}↵
for (ll i = 0;i<=b;i++){↵
temp[i] = mp[i];↵
}↵
ll sum = 0;↵
vector<ll> ans(b+1);↵
for (ll i = 0;i<=b;i++){↵
ans[i] = i;↵
}↵
for (ll i = 0;i<=b;i++){↵
sum+=temp[i]|ans[i];↵
}↵
cout << sum << endl;↵
for (ll x: temp){↵
cout << x << " ";↵
}cout << endl;}↵
↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
<p align="center">↵
<img src="https://i.ibb.co.com/7tGX7dh1/1705387659-krots-top-p-milie-animeshnie-kotiki-pinterest-43-1.jpg" width="200" height="200">↵
</p> ↵
↵
↵
<spoiler summary="Задача A"> ↵
**Полное решение:** ↵
Пусть `f(x)` — количество вхождений числа `x` в массив. При построении последовательности мы всегда ограничены минимальным `f(x)` среди выбранных элементов. ↵
↵
Если взять элемент с частотой `f(x)`, то длина последовательности может увеличиться:↵
↵
```↵
mx = max(mx, f(x) * cnt),↵
```↵
↵
где `cnt` — количество уже добавленных элементов, включая текущий.↵
↵
Так последовательно обновляем ответ и выводим `mx`.↵
↵
**Алгоритм:**↵
↵
1. Посчитать частоты `f(x)` для всех чисел.↵
2. Отсортировать или перебрать их по убыванию.↵
3. На каждом шаге обновлять `mx`.↵
4. Вывести максимальный результат.↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll st = 0;↵
map<ll,ll> mp;↵
ll cnt = 0;↵
ll n; cin >> n;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
mp[x]++;↵
}↵
vector<pair<ll,ll>> ans;↵
map<ll,ll> mpp;↵
for (ll x: a){↵
mpp[x]++;↵
if(mpp[x]==1){↵
ans.pb({mp[x],x});↵
}↵
}↵
sort(allr(ans));↵
ll sm = 0;↵
for (ll i = 0;i<ans.size();i++){↵
// cout << ans[i].f << endl;↵
sm = max(sm,ans[i].f*(i+1));↵
}↵
cout << sm << endl;↵
↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Задача B"> ↵
**Полное решение:** ↵
Ответ невозможен, если хотя бы один элемент от `1` до `m` отсутствует во всех множествах. ↵
↵
Теперь рассмотрим множества, где для каждого элемента количество вхождений ≥ 2 (включая учёт подмножеств). Пусть таких множеств `cnt`.↵
↵
Если `cnt ≥ 2`, то мы всегда можем построить как минимум три разные конфигурации:↵
↵
1. взять всё множество + `sx`,↵
2. взять всё множество + `sy`,↵
3. взять всё множество + `sx + sy`.↵
↵
Значит, в этом случае решение существует.↵
↵
**Алгоритм:**↵
↵
1. Проверить, что все элементы от `1` до `m` встречаются.↵
2. Посчитать `cnt` — число множеств, удовлетворяющих условию.↵
3. Если `cnt ≥ 2`, вывести "YES", иначе "NO".↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll a,b; cin >> a >> b;↵
ll cnt = 0;↵
map<ll,ll> mp;↵
map<ll,ll> mpp;↵
vector<vector<ll>> ak(a);↵
for (ll i = 0;i<a;i++){↵
ll x; cin >> x;↵
ak[i].resize(x);↵
// map<ll,ll> mpp;↵
for (ll j = 0;j<x;j++){↵
ll op; cin >> op;↵
ak[i][j] = op;↵
mpp[op]++;↵
}↵
↵
↵
}↵
// ll cnt = 0;↵
for (ll i = 0;i<a;i++){↵
bool check = 1;↵
for (ll j = 0;j<ak[i].size();j++){↵
if(mpp[ak[i][j]]==1){↵
check = 0;↵
break;↵
}↵
}↵
if(check){↵
cnt++;↵
}↵
}↵
bool opt = 1;↵
for (ll i = 1;i<=b;i++){↵
if(mpp[i]==0){↵
opt = 0;↵
break;↵
}↵
}↵
if(!opt){↵
cout << "NO" << endl;↵
}else{↵
↵
cout << (cnt>=2 ?"YES": "NO") << endl;↵
}}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Задача C"> ↵
**Полное решение:** ↵
Разберём, как работает бинарный поиск: ↵
↵
* если `a[m] == i` → элемент найден;↵
* если `a[m] > i` → двигаем правую границу;↵
* если `a[m] < i` → двигаем левую границу.↵
↵
Чтобы `x` был найден, элементы слева должны быть меньше него, а справа — больше.↵
↵
Значит:↵
↵
* если `s[i] == '1'`, можно поставить `ans[i] = i`;↵
* если `s[i] == '0'`, то нужно поставить `ans[i] ≠ i`, сохранив корректность.↵
↵
Простейшее решение — перестановка `[2, 3, ..., n, 1]`. Она гарантирует, что для всех позиций с `0` элемент отличается от индекса. Естественно не стоит забывать про s[i]=='1', тогда ставим ans[i] = i.↵
↵
**Особый случай:** если встречается символ `0`, окружённый единицами (`...101...`), то условие нарушается: элементу придётся соответствовать позиции, но это запрещено. Тогда ответ невозможен.↵
↵
**Алгоритм:**↵
↵
1. Проверить строку на наличие "невозможного" шаблона.↵
2. Если он найден → вывести "NO".↵
3. Иначе построить перестановку `[2, 3, ..., n, 1]`.↵
4. Вывести её как ответ.↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll n; cin >> n;↵
string s; cin >> s;↵
vector<ll> a(n);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='1'){↵
a[i] =(i+1);↵
}↵
}↵
bool opt = 1;↵
map<ll,ll> mp;↵
vector<ll> temp(n);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='0'){↵
}else{↵
temp[i] = i+1;↵
mp[i+1]++;↵
}↵
}↵
ll i = 0;↵
while (i<n){↵
if(s[i]=='1'){↵
i++;↵
continue;↵
}↵
ll j = i;↵
ll op = j;↵
while (j<n && s[j]=='0'){↵
j++;↵
}↵
if(j-i==1){↵
opt = 0;↵
break;↵
}↵
for (ll k = i;k<j-1;k++){↵
temp[k] = k+2;↵
}↵
temp[j-1] = i+1;↵
i = j;↵
}↵
↵
if(!opt){↵
cout << "NO" << endl;↵
}else{↵
cout << "YES" << endl;↵
for (ll x: temp){↵
cout << x << " ";↵
}cout << endl;}↵
//cout << opt << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Задача D1"> ↵
**Полное решение:** ↵
Нужно максимизировать ↵
↵
```↵
Σ (ai OR bi).↵
```↵
↵
Пусть у нас есть перестановка `p`. Несложно заметить, что чтобы сделать сумму максимальной, выгодно каждому числу поставить его **битовую инверсию**.↵
↵
Почему?↵
↵
* Инверсия по битам гарантирует, что при `OR` получится максимальное количество единиц.↵
* Это работает для любого числа в диапазоне.↵
↵
Пример:↵
↵
```↵
x = 9 (1001₂), инверсия = 6 (0110₂).↵
9 OR 6 = 1111₂ = 15.↵
```↵
↵
Значит, при такой паре значение `OR` максимально возможное.↵
Стоит отметить, что если r == 0, то это не сработает, а значит нужно просто вывести↵
0 и 0, как ответ.↵
↵
**Алгоритм:**↵
↵
1. Идём по всем числам от `n` до `1`.↵
2. Для каждого числа `x` считаем его инверсию (по длине битов `n`).↵
3. Сохраняем в `mp[x]`.↵
4. Формируем перестановку:↵
↵
```↵
ans[i] = mp[i]↵
```↵
↵
5. Считаем итоговую сумму и выводим её вместе с перестановкой.↵
↵
<spoiler summary="Code:">↵
↵
~~~~~↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#define ll long long ↵
#define pb push_back↵
#define f first ↵
#define s second ↵
#define all(x) x.begin(),x.end()↵
#define allr(x) x.rbegin(),x.rend()↵
using namespace std;↵
//vector<ll> vis;void↵
void bruh(){↵
ll a,b; cin >> a >> b;↵
if(b==0){↵
cout << 0 << endl;↵
cout << "0" << endl;↵
}else{↵
vector<ll> temp(b+1);↵
map<ll,ll> mp;↵
for (ll i = b;i>=0;i--){↵
ll k = 32-__builtin_clz(i);↵
ll mask = (1<<k)-1;↵
ll opt = (~i)&mask;↵
if(mp[i]==0 && mp[opt]==0){↵
mp[i] = opt;↵
mp[opt] = i;↵
}↵
// cout << opt << endl;↵
}↵
for (ll i = 0;i<=b;i++){↵
temp[i] = mp[i];↵
}↵
ll sum = 0;↵
vector<ll> ans(b+1);↵
for (ll i = 0;i<=b;i++){↵
ans[i] = i;↵
}↵
for (ll i = 0;i<=b;i++){↵
sum+=temp[i]|ans[i];↵
}↵
cout << sum << endl;↵
for (ll x: temp){↵
cout << x << " ";↵
}cout << endl;}↵
↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
// cout << dp[3][2] << endl;↵
// for (ll i = 1;)↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
---↵
