Что происходит, если массив уже отсортирован?

Что происходит, если есть такие индексы $$$i$$$ и $$$j$$$, что $$$i > j$$$ и $$$a_i > a_j$$$?

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto& u : a)
            cin >> u;
        if (!is_sorted(a.begin(), a.end()))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

Как изменится стоимость при замене отрезка длины большей $$$1$$$ на отрезки длины $$$1$$$?

Стоимость массива $$$b_1, b_2, \ldots, b_k$$$ равна $$$k + \sum_{i=1}^{k} mex($$${$$$b_i$$$}$$$)$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto& u : a)
            cin >> u;
 
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (i + 1) * (n - i);
            if (a[i] == 0)
                ans += (i + 1) * (n - i);
        }
        cout << ans << '\n';
    }
}

Ответ $$$-1$$$ только в двух случаях. Если $$$n = 3$$$ и $$$a_2$$$ нечётное. А так же если для все $$$1 < i < n$$$: $$$a_i = 1$$$.

Не оптимально прибавлять $$$1$$$ к нечётному числу больше одного раза.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;
 
    if (*max_element(a.begin() + 1, a.end() - 1) == 1 || (n == 3 && a[1] % 2 == 1)) {
        cout << "-1\n";
        return;
    }
 
    long long answer = 0;
    for (int i = 1; i < n - 1; i++)
        answer += (a[i] + 1) / 2;
 
    cout << answer << '\n';
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--)
        solve();
}

Попробуйте упростить формулу стоимости массива.

Суммарная стоимость двух массивов равна $$$(n - 2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$$$.

Найдите все возможные суммы в массиве $$$a$$$ после выполнения нескольких операций.

#include <bits/stdc++.h>
using namespace std;
 
constexpr int MAXSUM = 100 * 100 + 10;
 
int sqr(int x) {
    return x * x;
}
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto& u : a)
        cin >> u;
 
    for (auto& u : b)
        cin >> u;
 
    int sumMin = 0, sumMax = 0, sumSq = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > b[i])
            swap(a[i], b[i]);
 
        sumSq += sqr(a[i]) + sqr(b[i]);
        sumMin += a[i];
        sumMax += b[i];
    }
 
    bitset<MAXSUM> dp;
    dp[0] = 1;
    for (int i = 0; i < n; i++)
        dp |= dp << (b[i] - a[i]);
 
    int ans = sqr(sumMin) + sqr(sumMax);
    for (int i = 0; i <= sumMax - sumMin; i++)
        if (dp[i])
            ans = min(ans, sqr(sumMin + i) + sqr(sumMax - i));
 
    cout << sumSq * (n - 2) + ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
}

Зафиксируйте $$$x$$$ и переберите все $$$cnt_y < cnt_x$$$. Суммарно это работает за $$$O(n)$$$.

Если $$$x$$$ и $$$cnt_y$$$ зафиксированы, то переберём все $$$y$$$ в убывающем порядке, пока $$$x = y$$$ или пара $$$(x, y)$$$ плохая.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    map<int, int> cnt;
    for (auto &x : a) {
        cin >> x;
        cnt[x]++;
    }
 
    vector<pair<int, int>> bad_pairs;
    bad_pairs.reserve(2 * m);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        bad_pairs.emplace_back(x, y);
        bad_pairs.emplace_back(y, x);
    }
    sort(bad_pairs.begin(), bad_pairs.end());
 
    vector<vector<int>> occ(n);
    for (auto &[x, c] : cnt)
        occ[c].push_back(x);
 
    for (auto &v : occ)
        reverse(v.begin(), v.end());
 
    long long answer = 0;
    for (int cnt_x = 1; cnt_x < n; cnt_x++)
        for (int x : occ[cnt_x])
            for (int cnt_y = 1; cnt_y <= cnt_x; cnt_y++)
                for (auto y : occ[cnt_y])
                    if (x != y && !binary_search(bad_pairs.begin(), bad_pairs.end(), pair<int, int>{x, y})) {
                        answer = max(answer, 1ll * (cnt_x + cnt_y) * (x + y));
                        break;
                    }
 
    cout << answer << '\n';
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--)
        solve();
}

Найдите ответ, если высоты всех вершин равны $$$1$$$.

Предположим, что в дереве все высоты равны $$$1$$$ или $$$0$$$. Чему тогда равен ответ?

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
 
using namespace std;
 
typedef long long ll;
 
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
 
ll n;
vector<vector<ll>> gr;
vector<ll> vec;
 
void input() {
	cin >> n;
	vec.resize(n);
	for (auto& c : vec) cin >> c;
 
	gr.resize(n);
 
	for (int i = 0; i < n - 1; i++) {
		ll u, v;
		cin >> u >> v;
		u--; v--;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
}
 
ll sol() {
	ll ans = 0;
 
	set<pair<ll, ll>> leaves;
	vector<pair<ll, ll>> srt;
	vector<ll> degree(n);
 
	srt.push_back({ 0, -1 });
	for (int i = 0; i < n; i++) {
		degree[i] = gr[i].size();
 
		srt.push_back({ vec[i], i });
		if (gr[i].size() == 1) {
			leaves.insert({vec[i], i});
		}
	}
 
	sort(srt.begin(), srt.end());
 
	for (int i = 1; i <= n; i++) {
		while (leaves.size() > 0 && (*leaves.begin()).first < srt[i].first) {
			ll v = (*leaves.begin()).second;
			degree[v] = -2;
			leaves.erase(leaves.begin());
 
			for (auto to : gr[v]) {
				degree[to]--;
				if (degree[to] == 1 || degree[to] == 0) leaves.insert({ vec[to], to });
			}
		}
 
		ans += max(2ll, ll(leaves.size())) * (srt[i].first - srt[i - 1].first);
	}
 
	return ans;
}
 
int main() {
	fastInp;
 
	input();
	cout << sol();
 
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; ++i) cin >> h[i];
  vector<vector<int>> g(n);
  for (int i = 0; i + 1 < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int rt = 0;
  for (int i = 0; i < n; ++i) {
    if (h[i] > h[rt]) {
      rt = i;
    }
  }
  ll ans = 0;
  function<int(int, int)> dfs = [&](int u, int p) {
    int mx1 = 0, mx2 = 0;
    vector<int> have;
    for (auto v : g[u]) {
      if (v != p) {
        int cur = dfs(v, u);
        if (cur > mx1) swap(cur, mx1);
        if (cur > mx2) swap(cur, mx2);
      }
    }
    if (p != -1) {
      int delta = max(0, h[u] - mx1);
      ans += delta;
      mx1 += delta;
    } else {
      ans += max(0, h[u] - mx1) + max(0, h[u] - mx2);
    }
    return mx1;
  };
  dfs(rt, -1);
  cout << ans << '\n';
}

Ответ $$$-1$$$ только если $$$n = 2$$$.

Ответ равен минимальной степени двойки не меньшей $$$n$$$.

Попробуйте преобразовать все числа в степени двоек (необязательно одинаковые).

#include <bits/stdc++.h>
using namespace std;
 
vector<pair<int, int>> ops;
vector<int> a;
 
void rec(int n, int coeff) {
    if (n <= 2) {
        for (int i = 1; i <= n; i++)
            a.push_back(i * coeff);
        return;
    }
 
    int p = 1;
    while (p * 2 <= n) p *= 2;
 
    if (p == n) {
        a.push_back(n * coeff);
        n--, p /= 2;
    }
 
    a.push_back(p * coeff);
    for (int i = p + 1; i <= n; i++) {
        a.push_back(2 * p * coeff);
        ops.emplace_back(i * coeff, (2 * p - i) * coeff);
    }
 
    rec(2 * p - n - 1, coeff);
    rec(n - p, coeff * 2);
}
 
void solve() {
    int n;
    cin >> n;
    if (n == 2) {
        cout << "-1\n";
        return;
    }
 
    ops.clear();
    a.clear();
    rec(n, 1);
    sort(a.begin(), a.end());
 
    int answer = 1;
    while (answer < n)
        answer *= 2;
 
    for (int i = 0;; i++)
        if (a[i] == a[i + 1]) {
            assert(a[i] != answer);
            ops.emplace_back(a[i], a[i]);
            a[i + 1] *= 2;
            a.erase(a.begin() + i);
            break;
        }
 
    for (auto x : a)
        while (x != answer) {
            ops.emplace_back(0, x);
            ops.emplace_back(x, x);
            x *= 2;
        }
 
    ops.emplace_back(0, answer);
    cout << ops.size() << '\n';
    for (auto &[x, y] : ops)
        cout << x << ' ' << y << '\n';
}
 
int main() {
    int tests;
    cin >> tests;
    while (tests--)
        solve();
}

У нас есть доказательство, что для любой длины, если выбранная подпоследовательность оптимальна, то выполнено следующее условие: если взят элемент $$$i$$$, то взяты все элементы $$$j > i$$$ такие, что $$$p_i > p_j$$$.

Пусть $$$d_i$$$ равно числу, на которое уменьшится количество инверсий, если переместить в начало только элемент $$$i$$$. Тогда если выбрана подпоследовательность $$$seq$$$, то количество инверсий равно $$$invs - \sum_{i \in seq} d_i + seqInvs - (\frac{|seq| \cdot (|seq| - 1)}{2} - seqInvs) = invs - \sum_{i \in seq} d_i + 2 \cdot seqInvs - \frac{|seq| \cdot (|seq| - 1)}{2}$$$. Здесь $$$invs$$$ — количество инверсий в исходной перестановке, а $$$seqInvs$$$ — количество инверсий среди элементов в $$$seq$$$.

Предположим, что количество инверсий равно $$$invs - \sum_{i \in seq} c_i - \frac{|seq| \cdot (|seq| - 1)}{2}$$$. Чему равно $$$c_i$$$?

Если $$$i > j$$$ и $$$p_i > p_j$$$, тогда $$$c_i < c_j$$$. Поэтому для длины $$$len$$$ оптимально взять $$$len$$$ максимальных элементов по значению $$$c_i$$$.

#include <bits/stdc++.h>
using namespace std;
 
struct binary_index_tree {
    int n;
    vector<int> bit;
 
    binary_index_tree(int n) : n(n), bit(n + 1) {}
 
    void increase(int pos) {
        for (pos++; pos <= n; pos += pos & -pos)
            bit[pos]++;
    }
 
    int query(int pref) const {
        int sum = 0;
        for (; pref; pref -= pref & -pref)
            sum += bit[pref];
 
        return sum;
    }
};
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> d(n);
    binary_index_tree bit(n);
    long long inversions = 0;
 
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        p--;
 
        d[i] = i - 2 * p;
        inversions += i - bit.query(p);
        bit.increase(p);
    }
    sort(d.rbegin(), d.rend());
 
    cout << inversions;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += d[i];
        cout << ' ' << inversions - sum - 1ll * i * (i + 1) / 2;
    }
 
    cout << '\n';
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
 
    int tests;
    cin >> tests;
    while (tests--)
        solve();
}