Всем, привет! Сегодня контест получился довольно интересным, поэтому я решил сделать разбор на задачи А-С, которые смог решить на самом контесте.
Задача A
Полное решение:
Чтобы выбрать k = 4, нужна последовательность: [x, x, x, x] Для k = 5: [x, x, x, x, x] Для k = 6: [x, x, x, x, x, x] То есть нам нужна непрерывная последовательность длиной k с элементом x.
Формула для элемента:
x = n - k + 1
Алгоритм:
- Начинаем с
k = 1, постепенно увеличиваем. - Для каждого
n - i + 1ищем максимальную непрерывную последовательность. - Проверяем:
- если длина равна
k(i), то уменьшаем всеa[i] == n - i + 1на 1 и идём дальше; - если условие нарушается, то ответ отрицательный;
- иначе ответ положительный.
Выводим результат.
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 = 998244353;
void bruh(){
ll n; cin >> n;
vector<ll> a(n);
for (ll &x: a){
cin >> x;
}
ll l = 0; ll r= n-1;
ll st =1;
bool opt = 1;
for (ll i = 0;i<n;i++){
ll cnt = 0;
ll mx = 0;
for (ll j = 0;j<n;j++){
if(a[j]==n-i){
cnt++;
}else{
mx = max(mx,cnt);
cnt = 0;
}
}
mx = max(mx,cnt);
// cout << mx << endl;
if(mx!=i+1){
opt = 0;
break;
}
for (ll j = 0;j<n;j++){
if(a[j]==n-i){
a[j]--;
}
}
}
// cout << opt << endl;
if(opt){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
//cout << (l>r ) << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Задача B
Полное решение:
Лучше всего брать минимальные купоны, чтобы бесплатно доставались самые дорогие товары.
Пример:
a = [18, 3, 7, 2, 9]
b = [3, 2, 1]
- Купон
3→ берём 18, 9 и бесплатно 7. - Купон
2→ берём 18 и бесплатно 9. - Купон
1→ берём 0 и бесплатно 18.
Решение:
- Отсортировать массивы
aиb. - Для каждого купона
x:
- прибавить
(x−1)максимальных элементов; - сдвинуть индекс
l += x.
- Следить, чтобы не выйти за границы.
- Если остались товары, их придётся купить.
Выводим сумму.
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;
void bruh(){
ll n,k; cin >> n >> k;
vector<ll> a(n);
for (ll &x: a) cin >> x;
vector<ll> b(k);
for (ll &x: b) cin >> x;
sort(allr(a));
sort(all(b));
vector<ll> pref(n+1,0);
for (int i=0;i<n;i++){
pref[i+1] = pref[i] + a[i];
}
ll l = 0;
ll sm = 0;
for (ll x: b){
if (l+x > n){
sm += pref[n] - pref[l];
l+=x;
break;
}else{
if (x != 1){
sm += pref[l+x-1] - pref[l];
}
l += x;
}
}
while (l<n){
sm+=a[l];
l++;
}
cout << sm << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Задача C
Полное решение:
У нас есть x, y и вершины u, v.
Если
p[u] > p[v] → ребро весит x
иначе → ребро весит y
Построение:
- Если
x ≥ y, то строим реброv → u. - Иначе строим
u → v. Получаем ациклический граф (DAG).
Алгоритм:
- Выполнить топологическую сортировку (например, алгоритм Кана).
- Присвоить вершинам значения от
1доnв порядке топологической сортировки. - Заполнить массив:
res[x] = u
Выводим перестановку.
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;
void bruh(){
ll n; cin >> n;
vector<vector<ll>> gra(n+1);
vector<ll> vis(n+1,0);
for (ll i = 0;i<n-1;i++){
ll a,b,c,d; cin >> a >> b >> c >> d;
if(c<d){
gra[b].pb(a);
vis[a]++;
}else{
gra[a].pb(b);
vis[b]++;
}
}
queue<ll> que;
for (ll i = 1;i<=n;i++){
if(vis[i]==0){
que.push(i);
}
}
vector<ll> ans;
while (!que.empty()){
ll u = que.front();
que.pop();
ans.pb(u);
for (ll x: gra[u]){
// u--;
vis[x]--;
if(vis[x]==0){
// vis[x]--;
que.push(x);
}
}
}
vector<ll> res(n+1);
ll cur = n;
for (ll x: ans){
res[x] = cur;
cur--;
}
for (ll i = 1;i<=n;i++){
cout << res[i] << " ";
}cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
