Всем привет, извиняюсь, что разбор вышел не в актуальное время, я попросту забыл его выпустить:(↵
↵
P>S: Если какая-то из задач все еще непонятна, то можете просмотреть код для полной ясности.↵
↵
<p align = "center">↵
<img src = "https://i.ibb.co.com/W4Yj3kfv/anime-cartoon-characters-cute-cats-spring-pictures-happy-cute-art-animals-kittens-pets-grap-1141449.jpg" width = "10" height = "10">↵
</p>↵
↵
----↵
↵
<spoiler summary="Задача А:">↵
Полное решение:↵
Давайте заметим, что если есть какое-то четное кол-во (-1), то в итоге все -1 превратятся в ↵
одну положительную единицу. ↵
↵
Поэтому посчитаем все такие (-1), и просто возьмем их кол-во по↵
модулю 2. ↵
↵
Это и будет частью ответа.↵
Дальше заметим, что если есть какое-то кол-во 0, ↵
↵
то с ними мы ничего не сделаем, ↵
а значит ↵
второй частью ответа просто будет кол-во 0.↵
Выведем наш ответ, как cnt1%2+cnt0, ↵
↵
где cnt1 — кол-во -1, а cnt2 — кол-во 0.↵
↵
Сложность: O(n)↵
↵
<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()↵
using namespace std;↵
void bruh(){↵
ll n; cin >> n;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
}↵
ll cnt = 0; ll cntt = 0;↵
for (ll i = 0;i<n;i++){↵
if(a[i]<0){↵
cnt++;↵
}else if(a[i]==0){↵
cntt++;↵
}↵
}↵
cout << (cnt%2)*2+cntt << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача В:">↵
Полное решение:↵
Т.к нам нужно максимизировать наш ответ, ↵
↵
давайте просто возьмем самый максимальный элемент в пару↵
со вторым максимальным, итд.↵
↵
Для этого можно просто отсортировать массив.↵
↵
Выведем наш ответ.↵
↵
Сложность: O(nlogn)↵
↵
<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()↵
using namespace std;↵
void bruh(){↵
ll n; cin >> n;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
}↵
sort(all(a));↵
ll l = 0; ll r = n-1;↵
ll mx = 0;↵
while (r>=0){↵
ll diff = (abs(a[r]-a[r-1]));↵
mx = max(mx,diff);↵
r--;↵
r--;↵
}↵
cout << mx << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача С:">↵
Полное решение:↵
↵
Давайте заметим, что если до требуемого k, нет какого-то числа, то нам не остается ничего, ↵
↵
как просто добавить это число, так же если f(k)!=0, где f(x) —↵
↵
кол-во вхождений числа x в массив, то это число нужно заменить на какое-то другое тоже.↵
↵
Дальше стоит заметить, что вышеуказанные операции могут пересекаться, тогда ответом будет max(cnt,f(k)), где cnt — кол-во таких чисел от 0 до k, ↵
что вхождении в массив у этих элементов равна 0, т.е f(x) == 0.↵
↵
Выведем наш ответ.↵
↵
Сложность: O(n)↵
↵
<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()↵
using namespace std;↵
void bruh(){↵
ll n,k; cin >> n >> k;↵
vector<ll> a(n);↵
map<ll,ll> mp;↵
for (ll i = 0;i<n;i++){↵
cin >> a[i];↵
mp[a[i]]++;↵
}↵
ll cnt = 0;↵
ll mex = 0;↵
for (ll i = 0;i<k;i++){↵
if(mp[i]==0){↵
cnt++;↵
}↵
}↵
↵
cout << max(cnt,mp[k]) << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача D:">↵
Полное решение:↵
↵
Допустим строка такая: ababaaba. Давайте просимулируем процесс для все b, для наглядности.↵
↵
i = 2, нам нужно посчитать кол-во сдвигов слева и справа, т.к слева нет букв б, то берем справа.↵
↵
bab = bba = 1 сдвиг.↵
↵
bbaaab = bbbaaa — 3 сдвига.↵
↵
Заметим, что для каждого b от 0 до і, число сдвигов до і это кол-во букв а от j до і, где j<i.↵
↵
Также для каждого b от і до n, число сдвигов до n, это кол-во букв от і до j, где j>=i.↵
↵
Тут можно заметить, что для каждого i, s[i] == 'b', сумма сдвигов считается как↵
↵
(Lefta — Righta)*p[i]+((sump[n-1]-sump[i-1])-sump[i-1]), ↵
↵
где lefta — кол-во букв а от 0 до і-1, ↵
↵
а rigtha — кол-во букв а от і до n, p[i] — кол-во букв б от 0 до і-1. ↵
↵
Sump[i] — сумма всех p[i] таких индексов, что s[i]=='b'.↵
↵
Для буквы а делаем точно также, только уже с другими префиксами. Для большей наглядности можете просмотреть мой код.↵
↵
Сложность: O(n)↵
↵
<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()↵
using namespace std;↵
bool check(ll k, string s, ll n){↵
for (ll i = 0;i<n;i++){↵
if(k<=0){↵
break;↵
}↵
if(s[i-1]=='a' && s[i]=='b' && s[i+1]=='a' && i-1>=0 && i+1<n || ↵
i==0 && s[i]=='b' && s[i+1] == 'a' && i+1<n){↵
swap(s[i],s[i+1]);↵
k--;↵
}↵
}↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='b' && s[i+1]=='a' && i+1<n){↵
return false;↵
}↵
}↵
return true;↵
}↵
void bruh(){↵
ll n; cin >> n;↵
string s; cin >> s;↵
ll cnt1 = 0;↵
ll cnt2 = 0;↵
ll l = 0;↵
vector<ll> preff(n,0);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='a'){↵
preff[i] = 1;↵
}↵
}↵
vector<ll> p(n);↵
p[0] = preff[0];↵
for (ll i = 1;i<n;i++){↵
p[i] = p[i-1]+preff[i];↵
}↵
vector<ll> pref(n,0);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='b'){↵
pref[i] = 1;↵
}↵
}↵
vector<ll> pp(n);↵
pp[0] = pref[0];↵
for (ll i = 1;i<n;i++){↵
pp[i] = pp[i-1]+pref[i];↵
}↵
vector<ll> sump(n,0);↵
vector<ll> sumpp(n,0);↵
sump[0] = (s[0]=='b'? p[0]: 0);↵
for (ll i = 1;i<n;i++){↵
sump[i] = sump[i-1]+(s[i]=='b'? p[i]: 0);↵
}↵
sumpp[0] = (s[0]=='a'? pp[0]: 0);↵
for (ll i = 1;i<n;i++){↵
sumpp[i] = sumpp[i-1]+(s[i]=='a'? pp[i]: 0);↵
}↵
ll mx = 1e18;↵
for (ll i = 0;i<n;i++){↵
ll cnt = 0;↵
if(s[i]=='b'){↵
ll bas = (i==0? 0: pp[i-1]);↵
ll bs = (i==0? 0: sump[i-1]);↵
cnt = (bas-(pp[n-1]-bas))*p[i]+((sump[n-1]-bs)-bs);↵
}else{↵
ll bas = (i==0? 0: p[i-1]);↵
ll bs = (i==0? 0: sumpp[i-1]);↵
cnt = (bas-(p[n-1]-bas))*pp[i]+((sumpp[n-1]-bs)-bs);↵
}↵
↵
mx = min(mx,cnt);↵
}↵
// cout << cnt1 << " " << cnt2 << endl;↵
cout << mx << endl;↵
//cout << ans << endl;↵
↵
//cout << k << s << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача Е:">↵
Полное решение:↵
↵
Сперва вспомним один из самых важных лайфхаков связанное с работой на отрезках, а именно:↵
↵
`Чтобы найти ответ для отрезка l; r, можно найти ответ для отрезка от 1 до r, и отнять от него ответ для отрезка от 1 до l-1.`↵
↵
Теперь как использовать это для этой задачи? Давайте найдем кол-во отрезков с различными числами <=k, на отрезке от l-1 до r, затем отнимем кол-во отрезков с различными числами <=k-1, на отрезке от l-1 до r. Это и будет нашим ответом для данной задачи. ↵
↵
P.S: Ответ мы можем находить с помощью двух указателей/ sliding window. Для большей ясности можете просмотреть мой код.↵
↵
Выведем наш ответ.↵
↵
Сложность: O(n)*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()↵
using namespace std;↵
ll take(vector<ll> a, ll r, ll k){↵
ll n = a.size();↵
map<ll,ll> mp;↵
ll ans = 0; ll l = 0;↵
ll cnt = 0;↵
for (ll i = 0;i<n;i++){↵
mp[a[i]]++;↵
if(mp[a[i]]==1){↵
cnt++;↵
}↵
while (cnt>k){↵
mp[a[l]]--;↵
if(mp[a[l]]<=0){↵
mp.erase(a[l]);↵
cnt--;↵
}↵
l++;↵
}↵
if(i-r+1<l){↵
ans+=(i-l+1);↵
}else{↵
ans+=(i-(i-r+1)+1);↵
}↵
}↵
return ans;↵
}↵
void bruh(){↵
ll n,k,l,r; cin >> n >> k >> l >> r;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
}↵
cout << ((take(a,r,k))-take(a,l-1,k))-(take(a,r,k-1)-take(a,l-1,k-1)) << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
P>S: Если какая-то из задач все еще непонятна, то можете просмотреть код для полной ясности.↵
↵
<p align = "center">↵
<img src = "https://i.ibb.co.com/W4Yj3kfv/anime-cartoon-characters-cute-cats-spring-pictures-happy-cute-art-animals-kittens-pets-grap-1141449.jpg" width = "10" height = "10">↵
</p>↵
↵
----↵
↵
<spoiler summary="Задача А:">↵
Полное решение:↵
Давайте заметим, что если есть какое-то четное кол-во (-1), то в итоге все -1 превратятся в ↵
одну положительную единицу. ↵
↵
Поэтому посчитаем все такие (-1), и просто возьмем их кол-во по↵
модулю 2. ↵
↵
Это и будет частью ответа.↵
Дальше заметим, что если есть какое-то кол-во 0, ↵
↵
то с ними мы ничего не сделаем, ↵
а значит ↵
второй частью ответа просто будет кол-во 0.↵
Выведем наш ответ, как cnt1%2+cnt0, ↵
↵
где cnt1 — кол-во -1, а cnt2 — кол-во 0.↵
↵
Сложность: O(n)↵
↵
<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()↵
using namespace std;↵
void bruh(){↵
ll n; cin >> n;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
}↵
ll cnt = 0; ll cntt = 0;↵
for (ll i = 0;i<n;i++){↵
if(a[i]<0){↵
cnt++;↵
}else if(a[i]==0){↵
cntt++;↵
}↵
}↵
cout << (cnt%2)*2+cntt << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача В:">↵
Полное решение:↵
Т.к нам нужно максимизировать наш ответ, ↵
↵
давайте просто возьмем самый максимальный элемент в пару↵
со вторым максимальным, итд.↵
↵
Для этого можно просто отсортировать массив.↵
↵
Выведем наш ответ.↵
↵
Сложность: O(nlogn)↵
↵
<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()↵
using namespace std;↵
void bruh(){↵
ll n; cin >> n;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
}↵
sort(all(a));↵
ll l = 0; ll r = n-1;↵
ll mx = 0;↵
while (r>=0){↵
ll diff = (abs(a[r]-a[r-1]));↵
mx = max(mx,diff);↵
r--;↵
r--;↵
}↵
cout << mx << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача С:">↵
Полное решение:↵
↵
Давайте заметим, что если до требуемого k, нет какого-то числа, то нам не остается ничего, ↵
↵
как просто добавить это число, так же если f(k)!=0, где f(x) —↵
↵
кол-во вхождений числа x в массив, то это число нужно заменить на какое-то другое тоже.↵
↵
Дальше стоит заметить, что вышеуказанные операции могут пересекаться, тогда ответом будет max(cnt,f(k)), где cnt — кол-во таких чисел от 0 до k, ↵
что вхождении в массив у этих элементов равна 0, т.е f(x) == 0.↵
↵
Выведем наш ответ.↵
↵
Сложность: O(n)↵
↵
<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()↵
using namespace std;↵
void bruh(){↵
ll n,k; cin >> n >> k;↵
vector<ll> a(n);↵
map<ll,ll> mp;↵
for (ll i = 0;i<n;i++){↵
cin >> a[i];↵
mp[a[i]]++;↵
}↵
ll cnt = 0;↵
ll mex = 0;↵
for (ll i = 0;i<k;i++){↵
if(mp[i]==0){↵
cnt++;↵
}↵
}↵
↵
cout << max(cnt,mp[k]) << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача D:">↵
Полное решение:↵
↵
Допустим строка такая: ababaaba. Давайте просимулируем процесс для все b, для наглядности.↵
↵
i = 2, нам нужно посчитать кол-во сдвигов слева и справа, т.к слева нет букв б, то берем справа.↵
↵
bab = bba = 1 сдвиг.↵
↵
bbaaab = bbbaaa — 3 сдвига.↵
↵
Заметим, что для каждого b от 0 до і, число сдвигов до і это кол-во букв а от j до і, где j<i.↵
↵
Также для каждого b от і до n, число сдвигов до n, это кол-во букв от і до j, где j>=i.↵
↵
Тут можно заметить, что для каждого i, s[i] == 'b', сумма сдвигов считается как↵
↵
(Lefta — Righta)*p[i]+((sump[n-1]-sump[i-1])-sump[i-1]), ↵
↵
где lefta — кол-во букв а от 0 до і-1, ↵
↵
а rigtha — кол-во букв а от і до n, p[i] — кол-во букв б от 0 до і-1. ↵
↵
Sump[i] — сумма всех p[i] таких индексов, что s[i]=='b'.↵
↵
Для буквы а делаем точно также, только уже с другими префиксами. Для большей наглядности можете просмотреть мой код.↵
↵
Сложность: O(n)↵
↵
<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()↵
using namespace std;↵
bool check(ll k, string s, ll n){↵
for (ll i = 0;i<n;i++){↵
if(k<=0){↵
break;↵
}↵
if(s[i-1]=='a' && s[i]=='b' && s[i+1]=='a' && i-1>=0 && i+1<n || ↵
i==0 && s[i]=='b' && s[i+1] == 'a' && i+1<n){↵
swap(s[i],s[i+1]);↵
k--;↵
}↵
}↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='b' && s[i+1]=='a' && i+1<n){↵
return false;↵
}↵
}↵
return true;↵
}↵
void bruh(){↵
ll n; cin >> n;↵
string s; cin >> s;↵
ll cnt1 = 0;↵
ll cnt2 = 0;↵
ll l = 0;↵
vector<ll> preff(n,0);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='a'){↵
preff[i] = 1;↵
}↵
}↵
vector<ll> p(n);↵
p[0] = preff[0];↵
for (ll i = 1;i<n;i++){↵
p[i] = p[i-1]+preff[i];↵
}↵
vector<ll> pref(n,0);↵
for (ll i = 0;i<n;i++){↵
if(s[i]=='b'){↵
pref[i] = 1;↵
}↵
}↵
vector<ll> pp(n);↵
pp[0] = pref[0];↵
for (ll i = 1;i<n;i++){↵
pp[i] = pp[i-1]+pref[i];↵
}↵
vector<ll> sump(n,0);↵
vector<ll> sumpp(n,0);↵
sump[0] = (s[0]=='b'? p[0]: 0);↵
for (ll i = 1;i<n;i++){↵
sump[i] = sump[i-1]+(s[i]=='b'? p[i]: 0);↵
}↵
sumpp[0] = (s[0]=='a'? pp[0]: 0);↵
for (ll i = 1;i<n;i++){↵
sumpp[i] = sumpp[i-1]+(s[i]=='a'? pp[i]: 0);↵
}↵
ll mx = 1e18;↵
for (ll i = 0;i<n;i++){↵
ll cnt = 0;↵
if(s[i]=='b'){↵
ll bas = (i==0? 0: pp[i-1]);↵
ll bs = (i==0? 0: sump[i-1]);↵
cnt = (bas-(pp[n-1]-bas))*p[i]+((sump[n-1]-bs)-bs);↵
}else{↵
ll bas = (i==0? 0: p[i-1]);↵
ll bs = (i==0? 0: sumpp[i-1]);↵
cnt = (bas-(p[n-1]-bas))*pp[i]+((sumpp[n-1]-bs)-bs);↵
}↵
↵
mx = min(mx,cnt);↵
}↵
// cout << cnt1 << " " << cnt2 << endl;↵
cout << mx << endl;↵
//cout << ans << endl;↵
↵
//cout << k << s << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
----↵
↵
<spoiler summary="Задача Е:">↵
Полное решение:↵
↵
Сперва вспомним один из самых важных лайфхаков связанное с работой на отрезках, а именно:↵
↵
`Чтобы найти ответ для отрезка l; r, можно найти ответ для отрезка от 1 до r, и отнять от него ответ для отрезка от 1 до l-1.`↵
↵
Теперь как использовать это для этой задачи? Давайте найдем кол-во отрезков с различными числами <=k, на отрезке от l-1 до r, затем отнимем кол-во отрезков с различными числами <=k-1, на отрезке от l-1 до r. Это и будет нашим ответом для данной задачи. ↵
↵
P.S: Ответ мы можем находить с помощью двух указателей/ sliding window. Для большей ясности можете просмотреть мой код.↵
↵
Выведем наш ответ.↵
↵
Сложность: O(n)*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()↵
using namespace std;↵
ll take(vector<ll> a, ll r, ll k){↵
ll n = a.size();↵
map<ll,ll> mp;↵
ll ans = 0; ll l = 0;↵
ll cnt = 0;↵
for (ll i = 0;i<n;i++){↵
mp[a[i]]++;↵
if(mp[a[i]]==1){↵
cnt++;↵
}↵
while (cnt>k){↵
mp[a[l]]--;↵
if(mp[a[l]]<=0){↵
mp.erase(a[l]);↵
cnt--;↵
}↵
l++;↵
}↵
if(i-r+1<l){↵
ans+=(i-l+1);↵
}else{↵
ans+=(i-(i-r+1)+1);↵
}↵
}↵
return ans;↵
}↵
void bruh(){↵
ll n,k,l,r; cin >> n >> k >> l >> r;↵
vector<ll> a(n);↵
for (ll &x: a){↵
cin >> x;↵
}↵
cout << ((take(a,r,k))-take(a,l-1,k))-(take(a,r,k-1)-take(a,l-1,k-1)) << endl;↵
}↵
int main() ↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
ll t; cin >> t;↵
while (t--){↵
bruh();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
