Когда-нибудь я расположу C и D в правильном порядке :)

675A - Бесконечная последовательность

Во-первых, в случае c = 0 мы должны вывести YES если a = b, иначе вывести NO.

Если b принадлежит последовательности, то b = a + k * c, где k является неотрицательным целым числом.

Поэтому ответ YES если (b - a) / c является неотрицательным целым, иначе ответ NO.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;
 
    if (c == 0) {
        if (a == b) cout << "YESn";
        else cout << "NOn";
    } else {
        if ((b - a) % c == 0 && (b - a) / c >= 0) cout << "YESn";
        else cout << "NOn";
    }
}

675B - Восстановление картины

x a y

b m c

z d w

Число в центре может быть любым от 1 до n, потому что оно лежит внутри всех квадратов 2 × 2. Поэтому мы можем найти ответ с фиксированным числом в центре и потом домножить его на n.

Переберем все возможные x. Суммы в каждом квадрате 2 × 2 одинаковы, поэтому x + b + a + m = y + c + a + m и y = x + b - c.

Аналогично, z = x + a - d и w = a + y - d = z + b - c.

Квадрат с данными числам легален, если 1 ≤ y, z, w ≤ n. Мы должны просто проверить это.

Это было решение за O(n). Существует также решение за O(1).

#include <iostream>

using namespace std;

int main() {
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;

    long long ans = 0;
    for (int x = 1; x <= n; x++) {
        int y = x + b - c;
        int z = x + a - d;
        int w = a + y - d;
        if (1 <= y && y <= n && 1 <= z && z <= n && 1 <= w && w <= n) {
            ans++;
        }
    }
    ans *= n;

    cout << ans << endl;
}

675C - Денежные операции

У нас есть массив a_i и мы должны обнулить все числа внутри него с помощью минимального количества операций. Сумма всех чисел в массиве равна нулю.

Мы можем разделить массив на части с нулевой суммой, состоящие из последовательных элементов (первый и последний элемент считаются последовательными). Если часть имеет длину l, то мы можем обнулить ее с помощью l - 1 операции.

Следовательно, если мы сложим количество операций, то получим, что ответ равен n - k, где k — количество частей. Для того, чтобы ответ был минимальным, мы должны максимизировать k.

Одна из частей состоит из префикса и, возможно, суффикса массива. Остальные части являются подмассивами.

Давайте посчитаем префиксные суммы. Заметим, что префиксные суммы перед частями-подмассивами равны между собой, так как сумма чисел в каждой части равна нулю.

Следовательно, ответ равен n - f, где f — количество вхождений самого частого элемента среди префиксных сумм.

Бонус: как взламывать решения с переполнением?

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    map<long long, int> d;
    long long sum = 0;
    int ans = n - 1;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        sum += t;
        d[sum]++;
        ans = min(ans, n - d[sum]);
    }

    cout << ans << endl;
}

675D - Построение дерева

У нас есть двоичное дерево поиска и мы должны уметь быстро добавлять в него числа.

Пусть сейчас мы должны добавить число x. Найдем ранее добавленные числа l < x < r такие, что l максимально возможное, а r минимально возможное. Если только одно из этих чисел существует, то рассуждения почти не меняются. Мы можем найти l и r, например, с помощью std::set и upper_bound, если вы пишете на C++.

Мы должны сохранять отсортированный обход дерева, так как это свойство двоичного дерева поиска. Поэтому x должно быть правым потомком вершины l или левым потомком вершины r.

Пусть l не имеет правого потомка и r не имеет левого потомка. Тогда наименьший общий предок l и r (lca) не совпадает с l и r. Но тогда lca находится между l и r, а это невозможно, так как l максимально, а r минимально. Получается противоречие, поэтому l имеет правого потомка или r имеет левого потомка. Следовательно, мы точно знаем, кто из них станет предком x.

Это всё. Сложность решения .

#include <iostream>
#include <set>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    set<int> numbers;
    map<int, int> left;
    map<int, int> right;

    int n, v;
    cin >> n >> v;
    numbers.insert(v);
    for (int i = 0; i < n - 1; i++) {
        cin >> v;
        auto it = numbers.upper_bound(v);
        int result;
        if (it != numbers.end() && left.count(*it) == 0) {
            left[*it] = v;
            result = *it;
        } else {
            it--;
            right[*it] = v;
            result = *it;
        }
        numbers.insert(v);
        cout << result;
        if (i == n - 2) cout << 'n';
        else cout << ' ';
    }
}

675E - Электрички и статистика

Введем индексацию с нуля. Уменьшим каждый a_i на единицу. Также сделаем a_n - 1 равным n - 1.

Пусть dp_i — сумма кратчайших путей из i в i + 1... n - 1.

dp_n - 1 = 0

dp_i = dp_m - (a_i - m) + n - i - 1, где m лежит между i + 1 и a_i и a_m максимально. Мы можем найти m с помощью дерева отрезков / дерева Фенвика / разреженной таблицы.

Ответ равен сумме всех dp_i.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1 << 18;
pair<int, int> tree[maxn * 2];

void build(const vector<int> &a, int n) {
    for (int i = 0; i < n; i++) tree[maxn + i] = {a[i], i};
    for (int i = maxn - 1; i > 0; i--)
        tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}

int get(int l, int r) {
    pair<int, int> ans{-1, -1};
    for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans = max(ans, tree[l++]);
        if (r & 1) ans = max(ans, tree[--r]);
    }
    return ans.second;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    a[n - 1] = n - 1;
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
        a[i]--;
    }

    build(a, n);
    vector<long long> dp(n);
    long long ans = 0;
    dp[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) {
        int m = get(i + 1, a[i]);
        dp[i] = dp[m] - (a[i] - m) + n - i - 1;
        ans += dp[i];
    }

    cout << ans << 'n';
}