Всем привет! Сегодня я бы хотел написать разбор на вчерашний edu div2. Приятного чтения:)
Полное решение:
У этой задачи есть 2 решения:
Простой брутфорс. Пусть
x= префикс,y= середина,z= суффикс. При маленьких ограничениях наnможно написать кубический перебор. Поддерживаемl, r, гдеx = [1,l],y = [l+1,r],z = [r+1,n]. Перебираем все такие пары(l,r)и считаем суммы дляx, y, z. Это решение работает заO(n³).Конструктив. Заметим: сумма
x+y+zпри правильном разбиении должна делиться на 3. Возможные варианты:[1,1,1],[0,1,2],[1,0,2],[2,1,0]. То есть условие корректности: либо все три суммы равны, либо все попарно различны. Тогда можно просто взятьx = [1,1],y = [2,n-1],z = [n,n]. В этом случае получится корректное разбиение. То есть выбираемl = 1, r = n-1. Если жеsum(x,y,z) % 3 != 0, то правильного разбиения не существует, и нужно вывести0 0. Иначе выводим найденное разбиение.
#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);
for (ll &x: a){
cin >> x;
}
ll l = 0;
ll sm = 0;
ll r = 0;
bool opt = 0;
for (ll i = 1;i<n-1;i++){
for (ll j = i+1;j<n;j++){
ll sm1 = 0;
ll sm2 = 0;
ll sm3 = 0;
for (ll k = 0;k<i;k++){
sm1+=a[k];
}
sm1%=3;
for (ll k = i;k<j;k++){
sm2+=a[k];
}
sm2%=3;
for (ll k = j;k<n;k++){
sm3+=a[k];
}
sm3%=3;
if((sm1==sm3 && sm1==sm2) || (sm1!=sm2 && sm2!=sm3 && sm1!=sm3)){
l = i; r = j;
opt= 1;
break;
}
}
}
if(!opt){
cout << 0 << " " << 0 << endl;
}else{
// cout << l
cout << l << " " << r << endl;}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
#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);
ll sm = 0;
for (ll &x: a){
cin >> x;
}
for (ll i = 0;i<n;i++){
sm+=a[i]%3;
}
if(sm%3!=0){
cout << 0 << " " << 0 << endl;
}else{
cout << 1 << " " << n-1 << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея: Нужно сделать как можно больше элементов «не на своём месте» по сравнению с отсортированным вариантом. Нули можно заменить на отсутствующие элементы так, чтобы они оказались максимально вне своих целевых индексов.
Подход:
- Построить отсортированную версию массива (целевая позиция для каждого значения).
- Собрать все отсутствующие в исходном элементы — кандидаты для подстановки в нули. Лучше брать наибольшие отсутствующие.
- Заполнить нули этими значениями.
- После замены задача сводится к поиску максимальной длины отрезка, в котором a[i] != target_pos_of(a[i]). Это решается двумя указателями: расширяем правый, пока условие выполняется, при нарушении сдвигаем левый.
Сложность: сортировка + два указателя → O(n log 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;
vector<ll> temp;
vector<ll> tree;
const ll MOD = 1e9+7;
void bruh(){
ll n; cin >> n;
vector<ll> a(n);
map<ll,ll> mp;
for (ll &x: a){
cin >> x;
mp[x]++;
}
vector<ll> temp;
for (ll i = 1;i<=n;i++){
if(mp[i]==0){
temp.pb(i);
}
}
for (ll i = 0;i<n;i++){
if(a[i]==0){
a[i] = temp.back();
temp.pop_back();
}
}
map<ll,ll> mpp;
for (ll i = 0;i<n;i++){
mpp[a[i]] = a[i]-1;
}
ll mx = 0;
ll cnt = 0;
for (ll i = 0;i<n;i++){
if(mpp[a[i]]==i){
mx = max(mx,cnt);
cnt = 0;
}
cnt++;
}
ll l = 0; ll r = n-1;
while (l<=r){
if(l==mpp[a[l]] && r==mpp[a[r]]){
l++;
r--;
}else if(l==mpp[a[l]]){
l++;}
else if(r==mpp[a[r]]){
r--;}else{
break;}
// l++;r--;
}
cout << (l>r? 0: (r-l+1)) << endl; //l << " " << r <<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея (динамика по позиции и состоянию swap): На каждом индексе можно либо сделать swap между a[i] и b[i], либо не делать. Включение индекса в хорошее множество зависит от соседних сравнений. Поэтому держим два состояния для позиции i:
dp[i][0] — количество способов (или достижимость), если на i не сделали swap. dp[i][1] — если на i сделали swap.
Переходы (условия): Чтобы перейти в dp[i][1], нужно, сравнив с i-1, чтобы условия после и перед swap'ов выполнялись: — если и на i-1 была swap: b[i-1] <= a[i] и a[i-1] <= b[i] — если на i-1 не было swap: a[i-1] <= a[i] и b[i-1] <= b[i] Аналогичные проверки для dp[i][0].
Таким образом на каждом i обновляем dp[i][0] и dp[i][1] суммируя допустимые переходы из i-1. Не забываем про модуль, если нужно считать числа способов.
Выведем наш ответ, как dp[n][0]+dp[n][1].
#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;
}
vector<ll> b(n);
for (ll &x: b){
cin >> x;
}
vector<vector<ll>> dp(n,vector<ll>(3,0));
dp[0][1] = 1;
dp[0][2] = 1;
for (ll i = 1;i<n;i++){
if(a[i-1]<=a[i] && b[i-1]<=b[i]){
dp[i][1] = (dp[i][1]+dp[i-1][1])%MOD;
}
if(b[i-1]<=a[i] && a[i-1]<=b[i]){
dp[i][1] = (dp[i][1]+dp[i-1][2])%MOD;
}
if(b[i-1]<=b[i] && a[i-1]<=a[i]){
dp[i][2] = (dp[i][2]+dp[i-1][2])%MOD;
}
if(b[i-1]<=a[i] && a[i-1]<=b[i]){
dp[i][2] = (dp[i][2]+dp[i-1][1])%MOD;
}
}
cout << (dp[n-1][1]+dp[n-1][2])%MOD << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея: Если фиксировать d, итоговые значения группируются по диапазонам длины d: [1..d], [d+1..2d], ... Для каждого диапазона все числа переходят в одно значение (value_level).
Алгоритм:
- Посчитать частоты каждого числа до mx = max(a).
- Построить префикс частот pref, чтобы быстро получить количество элементов в любом числовом диапазоне [L..R] как pref[R] — pref[L-1].
- Для каждого d от 1 до mx: — Итерируем по диапазонам длины d: [1..d], [d+1..2d], ... — Через pref получаем количество элементов cnt в каждом диапазоне. — Вычисляем вклад диапазона в итоговую сумму: cnt * value_level (value_level = (R)/d округлённо вверх или по нужной формуле). — Если есть лишние элементы, которые нельзя покрыть (d — cnt), учитываем штраф/уменьшение.
- Для каждого d суммируем вклад по всем диапазонам и обновляем максимум.
Почему это быстро: суммарно для всех d работа примерно mx * (1 + 1/2 + 1/3 + ...) = mx * log(mx).
Сложность: ~ O(mx * log mx), где mx = max(a), с O(mx) памяти на частоты и префиксы.
#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,k; cin >> n >> k;
vector<ll> a(n);
ll mx = 0;
vector<ll> mp(2e5+110,0);
for (ll &x: a){
cin >> x;
mx = max(mx,x+1);
mp[x]++;
}
vector<ll> preff(2e5+11,0);
for (ll i = 1;i<=2e5;i++){
preff[i] = preff[i-1]+mp[i];
}
// cout << preff[51]-preff[48]-mp[17] << endl;
ll sm = -1e18;ll ans = 0;
for (ll d = 2;d<=2e5;d++){
ll sum = 0;
for(ll j = 1;j<=2e5;j+=d){
ll l = j;
ll r = min(d+j-1,(ll)2e5);
ll cnt = max(0LL,((preff[r]-preff[l-1])-mp[(j+d-1)/d]))*k;
ll opt = (preff[r]-preff[l-1])*((j+d-1)/d);
sum+=opt;
sum-=cnt;
}
// if(d==2){
// cout << sum << endl;
// }
sm = max(sm,sum);
}
cout << sm << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
