--- Всем привет! Давно не было разборов, за что я дико извиняюсь. Но сегодня я хочу сделать разбор на недавний контест 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();
}
}
