Всем привет, извиняюсь, что разбор вышел не в актуальное время, я попросту забыл его выпустить:(
P>S: Если какая-то из задач все еще непонятна, то можете просмотреть код для полной ясности.
Полное решение: Давайте заметим, что если есть какое-то четное кол-во (-1), то в итоге все -1 превратятся в одну положительную единицу.
Поэтому посчитаем все такие (-1), и просто возьмем их кол-во по модулю 2.
Это и будет частью ответа. Дальше заметим, что если есть какое-то кол-во 0,
то с ними мы ничего не сделаем, а значит второй частью ответа просто будет кол-во 0. Выведем наш ответ, как cnt1%2+cnt0,
где cnt1 — кол-во -1, а cnt2 — кол-во 0.
Сложность: O(n)
#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();
}
}
Полное решение: Т.к нам нужно максимизировать наш ответ,
давайте просто возьмем самый максимальный элемент в пару со вторым максимальным, итд.
Для этого можно просто отсортировать массив.
Выведем наш ответ.
Сложность: O(nlogn)
#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();
}
}
Полное решение:
Давайте заметим, что если до требуемого k, нет какого-то числа, то нам не остается ничего,
как просто добавить это число, так же если f(k)!=0, где f(x) —
кол-во вхождений числа x в массив, то это число нужно заменить на какое-то другое тоже.
Дальше стоит заметить, что вышеуказанные операции могут пересекаться, тогда ответом будет max(cnt,f(k)), где cnt — кол-во таких чисел от 0 до k, что вхождении в массив у этих элементов равна 0, т.е f(x) == 0.
Выведем наш ответ.
Сложность: O(n)
#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();
}
}
Полное решение:
Допустим строка такая: 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)
#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();
}
}
Полное решение:
Сперва вспомним один из самых важных лайфхаков связанное с работой на отрезках, а именно:
Чтобы найти ответ для отрезка l; r, можно найти ответ для отрезка от 1 до r, и отнять от него ответ для отрезка от 1 до l-1.
Теперь как использовать это для этой задачи? Давайте найдем кол-во отрезков с различными числами <=k, на отрезке от l-1 до r, затем отнимем кол-во отрезков с различными числами <=k-1, на отрезке от l-1 до r. Это и будет нашим ответом для данной задачи.
P.S: Ответ мы можем находить с помощью двух указателей/ sliding window. Для большей ясности можете просмотреть мой код.
Выведем наш ответ.
Сложность: O(n)*4
#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();
}
}
Comments (0)
