Codeforces Round 1050 (Div. 4) Фанатский разбор A-G.

--- Всем привет! Давно не было разборов, за что я дико извиняюсь. Но сегодня я хочу сделать разбор на недавний контест Div4. Сразу скажу, что для каждой задачи вы сможете просмотреть код для полной ясности идеи. Так что если то-то непонятно, то смело смотрите код. Удачи)

Задача A

Идея: Если n чётное — все x уничтожатся парами, останется 0. Если n нечётное — один x останется, значит ответ равен x.

Примеры:

n = 4, x = 5 → все уничтожились → 0.
n = 5, x = 7 → остался один → 7.

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.rbegin(),x.rend()
using namespace std;
const ll MOD = 1e9+7;

void bruh(){
  ll a,b; cin >> a >> b;
  if(b%2==0){
    cout << 0 << endl;
  }else{
    cout << a << endl;
  }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t; cin >> t;
    while (t--){
        bruh();
    }
}

Задача B

Идея: Двигаясь по одной оси, мы неизбежно проходим и через вторую. То есть соберём все лазеры — n по оси X и m по оси Y.

Ответ: n + m.

Пример:

n = 3, m = 2 → всего 5.

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.rbegin(),x.rend()
using namespace std;
const ll MOD = 1e9+7;

void bruh(){
  ll n,k,x,y; cin >> n >> k >> x >> y;
  vector<ll> a(n);
  vector<ll> b(k);
  for (ll &x: a){
    cin >> x;
  }
  for (ll &x: b){
    cin >> x;
  }
  cout << n+k << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t; cin >> t;
    while (t--){
        bruh();
    }
}

Задача C

Идея: Введём sign(x) — сторону зала перед минутой x.

Знаки разные (0 1 или 1 0): Пусть x = 2, y = 5, sign = 1 0. Возможная комбинация: 2^0, 3^1, 4^0. Если увеличить y, комбинация не меняется. Вывод: разница (y-x) должна быть нечётной, иначе уменьшаем её на 1.

Знаки одинаковые (0 0 или 1 1): Пусть x = 2, y = 3, sign = 1 1. Возможная комбинация: 2^0, 3^1. Если увеличить y, получится: 2^0, 3^1, 4^0, 5^1. Здесь наоборот: если (y-x) нечётное, уменьшаем на 1.

Также:

Добавляем (0,0) в начало, так как начинаем с минуты 0.
Последняя минута может быть меньше k, поэтому добавляем ещё (k-last).

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.rbegin(),x.rend()
using namespace std;
const ll MOD = 1e9+7;

void bruh(){
  ll n,k; cin >> n >> k;
  vector<pair<ll,ll>> ans;
  ans.pb({0,0});
  for (ll i = 0;i<n;i++){
    ll a,b; cin >> a >> b;
    ans.pb({a,b});
  }
  
  ll sm = 0;
  for (ll i = 0;i+1<n+1;i++){
    ll x = ans[i].s;
    ll y = ans[i+1].s;
    ll diff =(ans[i+1].f-ans[i].f);
    if(ans[i+1].f==ans[i].f){
      if(ans[i+1].s!=ans[i].s){
        sm++;
      }
    }else{
    if(y!=x){
    if(diff%2==0){
      diff--;
    }
      sm+=diff;
    }else{
      if(diff%2==1){
        diff--;
      }
      sm+=diff;
    }
  }}
  if(ans[n].f<k){
    sm+=(k-ans[n].f);
  }
  //cout << sm << endl;
 
  cout << sm << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t; cin >> t;
    while (t--){
        bruh();
    }
}

Задача D

Идея: Газонокосилка меняет состояние только на нечётных элементах.

Начинаем с суммы массива.
Считаем количество нечётных элементов = length.
Влияет только половина — length/2.

Почему? Первое нечётное меняет состояние, второе возвращает, третье снова меняет… Каждая пара компенсируется.

Чтобы уменьшение суммы было минимальным, убираем length/2 наименьших нечётных.

Пример:

a = [3, 5, 2, 4, 7], сумма = 21.
Нечётные = [3, 5, 7], нужно убрать 1 минимальный → 3.
Ответ = 18.

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;
const ll MOD = 1e9+7;

void bruh(){
  ll n; cin >> n;
  vector<ll> a(n);
  ll sm = 0;
  vector<ll> temp;
//  ll cnt = 0;
  for (ll &x: a){
    cin >> x;
    sm+=x;
    if(x%2!=0){
      temp.pb(x);
    }
  }
  if(temp.size()==0){
    cout << 0 << endl;
  }else{
  sort(all(temp));
  ll lim = temp.size()/2;
  ll ne = 0;
  for (ll i = 0;i<lim;i++){
    ne+=temp[i];
  }
  cout << sm-ne << endl;
}}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t; cin >> t;
    while (t--){
        bruh();
    }
}

Задача E

Идея: Определим «потрясающий» отрезок: в нём все элементы встречаются кратно k.

Метод: скользящее окно.

Двигаем правую границу, учитывая количество каждого числа.
Если условие нарушено — двигаем левую границу.
Когда окно «потрясающее», добавляем (r - l + 1) в ответ.

Пример:

a = [1, 2, 1, 2], k = 2.
Окно [1,2] → частоты 1,1, не делятся.
Окно [1,2,1,2] → частоты 2,2, подходят → ответ увеличивается.

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;
const ll MOD = 1e9+7;

void bruh(){
  ll n,k; cin >> n >> k;
  vector<ll> a(n);
  ll sm = 0;
  vector<ll> temp(n+1,0);
  for (ll &x: a){
    cin >> x;
  }
  for (ll i = 0;i<n;i++){
    temp[a[i]]++;
  }
  bool opt  = 1;
  for (ll i = 1;i<=n;i++){
    if(temp[i]%k!=0){
      opt = 0;
      break;
    }
    temp[i] = temp[i]/k;
  }
  if(!opt){
    cout << 0 << endl;
  }else{
  ll st = 0;
  map<ll,ll> mp;
  vector<ll> di(n+1,0);
  for (ll i = 0;i<n;i++){
    di[a[i]]++;
    while (di[a[i]]>temp[a[i]]){
      di[a[st]]--;
      st++;
    }
    sm+=(i-st+1);
  }
  cout << sm << endl;
  }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t; cin >> t;
    while (t--){
        bruh();
    }
}

Задача F

Идея: Нужно симулировать:

Берём лексикографически минимальный массив.
Удаляем все массивы длины ≤ его длины.
У остальных обрезаем первые элементы.

Почему работает:

Сумма длин ≤ 2 * 10^5.
В худшем случае массивы длиной 1, 2, 3, …, x.
Тогда x ≈ 632. Симуляция успевает.

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;
vector<ll> temp;
vector<ll> tree;
const ll MOD = 1e9+7;
void bruh(){
  ll n; cin >> n;
  ll mn = 1e18;
  deque<deque<ll>> gr(n);
  for (ll i = 0;i<n;i++){
    ll x; cin >> x;
    gr[i].resize(x);
    for (ll j = 0;j<x;j++){
      cin >> gr[i][j];
    }
    //mn = min(mn,x);
  }
  sort(all(gr), [](const auto &x, const auto &y){
    return x.size()<y.size();
  });
 
  ll l= 0;
  ll mx = 0;
  vector<ll> temp;
  ll cnt = n;
    bool opt = 1;
  while (gr.size()>=1){
  if(!opt){
    break;
  }
  auto cur = *min_element(all(gr));
  temp.insert(temp.end(),cur.begin(),cur.end());
  while (gr.size()!=0 && gr[0].size()<=cur.size()){
    gr.pop_front();
  }
  for (ll i = 0;i<gr.size();i++){
    for (ll j = 0;j<cur.size();j++){
      gr[i].pop_front();
    }
  }
  }
  

  for (ll x: temp){
    cout << x << " ";
  }cout << endl;
  
  
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t; cin >> t;
    while (t--){
        bruh();
    }
}

Задача G

Идея: Функция g(x) = последний индекс, где gcd уменьшился.

Рассмотрим делители чисел.
Пусть cnt[d] = количество чисел, делящихся на d.

Если cnt[d] ≥ i → gcd массива = d, не подходит.
Если cnt[d] < i → можно обновить максимум.

Пример:

a = [6, 10, 15].
gcd(6,10) = 2, gcd(6,10,15) = 1.
Значит, g(2) = 2.

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;
vector<ll> temp;
vector<ll> tree;
const ll MOD = 1e9+7;
void bruh(){
  ll n; cin >> n;
  vector<ll> a(n);
  //tree.resize(4*n);
  for (ll &x: a){
    cin >> x;
  }
  ll p = 0;
  ll mx = 0;
  vector<ll> d(n+1,0);
  for (ll i = 0;i<n;i++){
    if(p!=gcd(p,a[i])){
     // p = gcd(p,a[i]);
      mx = i;
    }
    p = gcd(p,a[i]);
    for (ll p = 1;p*p<=a[i];p++){
      if(a[i]%p==0){
        d[p]++;
        mx = (d[p]<(i+1)? max(mx,d[p]): mx);
      
      if(p!=a[i]/p){
        d[a[i]/p]++;
        mx = (d[a[i]/p]<(i+1)? max(mx,d[a[i]/p]): mx);
      }
    }}
    cout << mx << " ";
  }
  cout << endl;
  //build(1,0,n-1,a);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t; cin >> t;
    while (t--){
        bruh();
    }
}

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

№	Пользователь	Вклад
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	136
8	BledDest	132
9	maroonrk	131
10	qwexd	129

Блог пользователя Goddless