Для тестов до 10 было достаточно повыписывать ответы на листочке.

Для второй группы можно было перебрать все возможные пары $$$i$$$, $$$j$$$ и проверить выполнение условия. $$$O(n^2)$$$

Для третьей группы нужно было понять, что для фиксированного $$$i$$$ $$$j = n - i$$$. $$$O(n)$$$

Для полного решения заметим, что для каждого числа от $$$0$$$ до $$$n$$$ мы сможем найти пару. Тогда ответ это $$$n + 1$$$. Итоговая асимптотика $$$O(1)$$$.

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
      int n;
      scanf("%lld", &n);
      n++;
      printf("%lld", n);
}

Для первой группы было достаточно заметить, что ответ всегда равен $$$k$$$.

Для второй группы необходимо было найти количество единиц и двоек и решить аналогично первому случаю.

Для третьей группы необходимо было уметь искать минимум в массиве.

Для четвёртой группы можно было отсортировать массив за $$$O(n^2)$$$ (например, сортировкой пузырьком) и вывести сумму $$$k$$$ первых элементов.

Для полного решения просто отсортируем массив сортировкой за $$$O(n \log(n))$$$ (своей либо встроенной в ваш язык программирования).

#include<bits/stdc++.h>
#define int int64_t

using namespace std;

int32_t main(){
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int s = 0;
    for (int i = 0; i < k; i++)
        s += a[i];
    cout << s;
}

Для первой группы было достаточно разобрать тесты вручную.

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

Для третьей группы тестов можно было написать алгоритм, который был указан в условии. $$$O(n)$$$

Четвёртая группа тестов является большой подсказкой на полное решение. Просто выводим 0.

Для полного решения совместим обычный перебор из условия и отсечение на то, что $$$p \le n$$$. Асимптотика $$$O(min(p, n))$$$

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
      int n, p;
      cin >> n >> p;
      if (p <= n) {
            cout << 0;
            return 0;
      }
      int ans = 1;
      for (int i = n; i >= 1; i -= 2) {
            ans = ans * i % p;
      }
      cout << ans;
}

Для первой группы проверим то, что $$$|p| \le |s|$$$ ($$$|x|$$$ — длина строки $$$x$$$). Если условие выполняется, выведем $$$|p|$$$, иначе — $$$-1$$$.

Для второй группы можем использовать решение на первую подгруппу, но необходимо дополнительно проверить то, что $$$p$$$ состоит из одинаковых символов, причём таких же, как $$$s$$$.

Для третьей группы нужно было предпросчитать кол-во вхождений каждого символа на префиксе и с помощью этого ответить на запросы.

Для четвёртой группы нужно было уметь находить первое вхождение одного символа. Это можно было сделать, например, предпросчётом.

Для пятой группы мы можем написать проверку <<в лоб>>. $$$O(q \cdot n \cdot \log(n))$$$

Для полного решения необходимо было совместить предпросчёт из третьей группы и бинпоиск либо сохранение в предпросчёте индексов вхождений каждого символа, с помощью чего мы просто решаем задачу нахождения максимума из значений на позициях количества вхождений текущего символа в $$$|p|$$$. Асимптотика $$$O(q \cdot 26)$$$ либо $$$O(q \cdot \log(n) \cdot 26)$$$

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> arr[26];
    for(int i = 0; i < n; i++) {
        arr[s[i] - 'a'].push_back(i + 1);
    }
    int q;
    cin >> q;
    while(q--) {
        int ptr[26]{};
        string nm;
        cin >> nm;
        int ans = 0;
        bool can = true;
        for(int i = 0; i < nm.size(); i++) {
            if (arr[nm[i] - 'a'].size() <= ptr[nm[i] - 'a']) {
                can = false;
                break;
            }
            ans = max(ans, arr[nm[i] - 'a'][ptr[nm[i] - 'a']]);
            ptr[nm[i] - 'a']++;
        }
        if (!can)
            cout << "-1\n";
        else
            cout << ans << '\n';
    }
}

Для первой группы ответ всегда $$$0$$$.

Для второй группы ответ может быть $$$1$$$, если существует $$$2$$$ левее $$$1$$$. Иначе ответ $$$0$$$.

Для третьей группы можно было перебрать все возможные подмножества. $$$O(2^n \cdot n)$$$

Есть несколько вариаций полного решения:

• Заметить, что так как ответ равен сумме разностей соседних в подмножестве, то этот ответ это $$$x - y$$$, где $$$x$$$ — самое левое, а $$$y$$$ — самое правое число подмножества. Далее мы можем находить либо перебором $$$O(n^2)$$$, 60 баллов, либо заметить, что нам фактически надо для фиксированного $$$y$$$ просто поддерживать максимум на префиксе, что умеют делать префиксные суммы.

• Решить методом динамического программирования. $$$dp_i$$$ — ответ для обработанного префикса $$$i$$$. $$$dp_i = \max_{j < i}(dp_j + a_i - a_j)$$$. Получаем решение за $$$O(n^2)$$$, в котором можно было заметить, что $$$a_i$$$ не меняется при изменении $$$j$$$, а поэтому необходимо просто знать максимум на префиксе от $$$dp_j + a_j$$$, что делается аналогично префиксными суммами.

#include<bits/stdc++.h>
#define int int64_t

using namespace std;

int32_t main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int mn = INT_MAX, ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, a[i] - mn);
        mn = min(mn, a[i]);
    }
    cout << ans;
}

Для первых трёх групп было достаточно написать то, что просят в условии <<в лоб>> (добавляя в set и проверяя, что его размер < r — l + 1). $$$O(q \cdot n \cdot \log(n))$$$

Для четвёртой группы подойдёт всё то же решение, но set слишком медленный, поэтому используем хеш-таблицу (unordered set либо gp hash table). $$$O(q \cdot n)$$$

Для следующих двух групп было достаточно решения на четвёртую подгруппу, но ещё необходимо было останавливать алгоритм, как только мы нашли ответ. $$$O(q \cdot min(n, A))$$$.

Для следующей группы необходимо было решать задачу оффлайн: отсортировать запросы в порядке алгоритма Мо и решать задачу с помощью него. Подробнее можете прочитать здесь: https://ru.algorithmica.org/cs/decomposition/mo. $$$O((q + n) \cdot \sqrt n)$$$

Для полного решения необходимо было заметить такой факт:

Давайте для каждого индекса $$$i$$$ найдём такой индекс $$$j$$$, что $$$j < i$$$, $$$a_i = a_j$$$ и $$$|j - i|$$$ минимален. Если такого $$$j$$$ не существует, положим его значение $$$-1$$$. Тогда несложно заметить, что ответ на запрос это проверка на то, что максимум на отрезке $$$[l, r]$$$ в полученном массиве $$$\ge l$$$.

Теперь данную задачу можно решить на 80 баллов обычным деревом отрезков (рекурсивное дерево заходит наравне с нерекурсивным).

Для решения на 100 необходимо было также заметить, что вы на самом деле можете отвечать на запросы не $$$max(l, r) \ge l$$$, а $$$max(0, r) \ge l$$$, потому что отрезок $$$[0, l - 1]$$$ никак не влияет на ответ (максимальное значение там могло быть $$$l - 2$$$). Теперь задача свелась к максимуму на префиксе, что решается обычными префиксными максимумами.

#include<bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5e5 + 1;
const int A = 5e6 + 1;

int n, q;
int a[N];
int last[A];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        int cur = a[i];
        a[i] = max(a[i - 1], last[cur]);
        last[cur] = i;
    }
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << (a[r] >= l ? "Yes\n" : "No\n");
    }
}

Для решения первой подгруппы было достаточно написать то, что написано в условии. Просто переберём все пары и проверим выполнение условия.

Для второй подгруппы повыписываем количество пар для фиксированного $$$i$$$. Заметим, что нестандартное ограничение по $$$j$$$, а также ограничение в виде $$$i$$$ and $$$j = i$$$ позволяет нам заметить то, что количество возможных пар зависит от количества нулевых битов в числе, а именно, для фиксированного $$$i$$$ количество пар равно $$$2^{bit}$$$, где $$$bit = $$$ кол-во нулевых битов.

Для третьей подгруппы достаточно было написать стандартное решение динамическим программированием по цифрам.

Для четвёртой подгруппы заметим следующий факт: разобьём $$$i$$$ на группы $$$[2^k; 2^{k + 1} - 1]$$$. В каждой группе сумма равняется $$$3^{k}$$$.

Для полного решения повыписываем несколько первых ответов для фиксированного $$$i$$$: 1 2 1 4 2 2 1. Заметим некую симметричность в каждой группе, описанной в предыдущем пункте. А именно, если разбить такую группу на две, то сумма в первой половине равна $$$\frac{2}{3}$$$ от суммы группы, а во второй половине $$$\frac{1}{3}$$$ от суммы соответственно. Если продолжать такой спуск, то зависимость сохраняется.

Первая идея полного решения: Давайте решим задачу с помощью длинной арифметики: для младших битов просуммируем геометрическую прогрессию, для старшего сделаем спуск с проверкой на то, что число <= искомой середины. Далее, если спускаемся в левую половину, просто делаем $$$sum := \frac{2}{3} sum$$$. Иначе прибавляем эти $$$\frac{2}{3} sum$$$, $$$sum := \frac{1}{3} sum$$$.

Для более простого решения достаточно было заметить, что число нам задано в двоичной системе счисления. Тогда просто проверка на <= это проверка на значение $$$0 / 1$$$ текущего бита. С одним отличием. Спуск по битам проверяет на <, а не на <=. Для того, чтобы это исправить, просто увеличим исходное число на единицу, что несложно реализуется в двоичной системе.

#include <bits/extc++.h>

#define int int64_t

using namespace std;

const int mod = 1e9 + 7;

int binpow(int x, int y) {
    if (y == 0)
        return 1;
    if (y & 1)
        return binpow(x, y - 1) * x % mod;
    int z = binpow(x, y / 2);
    return z * z % mod;
}

int add(int x, int y) {
    return (x + y + mod) % mod;
}

int mul(int x, int y) {
    return x * y % mod;
}

int divd(int x, int y) {
    return mul(x, binpow(y, mod - 2));
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string l;
    cin >> l;
    int cnt = 0;
    while (!l.empty() && l.back() == '1')
        l.pop_back(), cnt++;
    if (!l.empty())
        l.pop_back();
    l.push_back('1');
    while (cnt--)
        l.push_back('0');
    int ans = 0, cur = 1;
    for (int i = 0; i + 1 < l.size(); i++) {
        ans = add(ans, cur);
        cur = mul(cur, 3);
    }
    for (int i = 1; i < l.size(); i++) {
        if (l[i] == '1') {
            ans = add(ans, mul(divd(cur, 3), 2));
            cur = divd(cur, 3);
        }
        else
            cur = mul(divd(cur, 3), 2);
    }
    cout << ans;
}

Для первой группы тестов достаточно просто рассмотреть несколько вариантов вручную.

Для второй группы можно заметить, что $$$|c - a| + |c - b| = 2 \cdot |c - a|$$$. Т.к. $$$c$$$ мы можем выбирать сами, то достаточно просто выводить 0.

Для третьей группы достаточно просто перебирать $$$c$$$ от $$$1$$$ до $$$10^5$$$.

На полное решение можем построить числовую прямую, на которой найти, что минимальное значение выражения достигается при C, лежащем в диапазоне [$min(a, b), max(a, b)

Unable to parse markup [type=CF_MATHJAX]

Для решения первой группы тестов достаточно просто находить сумму `В лоб': для каждого запроса находим сумму на подматрице последовательно суммируя все её элементы. Асимптотика — $$$O(qnm)$$$.

На вторую группу тестов можно было написать решение, которое по заданным границам находит площадь прямоугольника. Несложно увидеть, что, раз матрица заполнена числами 1, то ответом именно такого вида.

На четвёртую группу тестов можно было написать одномерные префиксные суммы. Асимптотика — $$$O(q \cdot min(n, m))$$$.

На третью группу можно было написать двумерные префиксные суммы, но выводить просто p[i][j], где p — массив префиксных сумм. Для полного решения нужно было догадаться, что ответ равен p[rx][ry] — p[lx — 1][ry] — p[rx][ly — 1] + p[lx — 1][ly — 1]. Только нужно следить за выходом за границы массива. Асимптотика — $$$O(q)$$$

На первую группу тестов достаточно было просто симулировать игру вручную.

На вторую группу тестов достаточно написать рекурсивную реализацию игры. Асимптотика — $$$O(tnlogn)$$$

У многих сегодня упали даже полные решения на последней подгруппе. Это произошло потому, что количество выводимых чисел очень большое, а эти люди пользовались endl вместо $\backslash$n, который с каждым выводом замедлял программу.

1 способ полного решения: напишем ту же рекурсивную реализацию, но только с сохранением уже посчитанных значений (рекурсия с мемоизацией, либо нерекурсивный подсчёт ДП).

2 способ полного решения:

Просчитаем ответ для каждого числа от 0 до 4 (0 — No, 1 — Yes):

0 1 0 1 1

Далее заметим, что для каждого следующего числа будем выводить 1, если оно чётное, либо 0 в противном случае. Почему это работает?

Всё достаточно просто. Если мы находимся в чётном числе, то мы просто отнимем 1. Таким образом противнику ничего не остаётся кроме того, чтобы отнять 1. Таким образом дойдём до числа 4, которое является выигрышным. Если же число нечётное, то теперь мы находимся в зеркальной ситуации и противник дойдёт до 4.

Для первой группы тестов рассмотрим два случая:

Если |p| = 1, s[0] = p[0], то ответ будет 1.

Иначе ответ будет 0.

Для второй группы тестов подсчитаем количество вхождений p[0] в s с помощью простого сохранения счётчика cnt.

Для третьей группы тестов можно рассмотреть два случая:

Если все символы в $$$p$$$ равны, то ответ будет $$$C^{|s|}_{|p|}$$$ по определению.

В любом ином случае ответ будет 0.

Для четвёртой группы можно было фиксировать s[i] и также рассматривать два случая:

Если s[i] = p[0], то к ответу нужно прибавить количество вхождений p[1] на суффиксе [i + 1, |s| — 1]. Количество вхождений можно было просчитать для каждого символа с помощью префиксных сумм.

Иначе к ответу ничего прибавлять не надо.

Полное решение:

Напишем несложное ДП, где dp[i][j] — количество вхождений строки p[j..(|p| — 1)] в строку s[i..(|s| — 1)].

Теперь напишем формулу перехода:

Будем писать рекурсивную реализацию, поэтому далее под count(i, j) подразумевается подсчёт dp[i][j].

Тогда `отщипнём' от строки s i-й символ и прибавим к dp[i][j] count(i + 1, j).

Также нам нужно обрабатывать варианты, когда s[i] = p[j]. В нём мы просто `отщипнём' от строки s i-й символ, от от p j-й символ и прибавим к dp[i][j] count(i + 1, j + 1).

Какая база dp?

Если j == |p|, то мы нашли вхождение, то есть return 1.

Если же i == |s|, то мы не нашли его. то есть return 0.

Асимптотика — $$$O(|s| \cdot |p|)$$$

Заметим, что под кандидаты чисел подходят только квадраты простых чисел. Тогда переберём все простые числа до $$$\sqrt{n}$$$ и проверим, подходят ли они под неравенство $$$l \le cur^2 \le r$$$. Асимптотика — $$$O(\sqrt n loglog(\sqrt n ))$$$

В данной задаче я специально не ставил контртест на это решение, т.к. многие на этом контесте не знают логарифмов.

Мы можем просто посчитать префиксные произведения и перебирать индекс раздела.

Для того, чтобы решение прошло даже с контртестом, сделаем так: нам надо найти отрезок с максимальным значением. Тогда давайте возьмём логарифм произведения. Максимальный отрезок как и был максимальным, так и остался. Воспользуемся интересным свойством: логарифм произведения равен сумме логарифмов. Теперь мы уменьшили числа. Давайте с помощью этого метода логарифмирования найдём отрезок с максимальным значением и уже для исходного массива посчитаем ответ по заданному модулю.

Асимптотика: $$$O(n \cdot log(sum(a)))$$$

Просто переберём все числа на отрезке $$$[l;r]$$$ и с помощью деления чисел на 2, 3, 5 проверить, является ли полученное число единицей. Асимптотика этого решения будет $$$n * \sigma(n)$$$, где $$$\sigma(n)$$$ — количество двоек, троек и пятёрок в факторизации числа.

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

bool f(int n){
    while((n & 1) == 0)
        n >>= 1;
    while(n % 3 == 0)
         n /= 3;
    while(n % 5 == 0)
        n /= 5;
    return n == 1;
}

int32_t main() {
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    for(int i = l; i <= r; i++)
        cnt += f(i);
    cout << cnt;
}

Первая группа тестов:

Напишем перебор. Будем для каждого целого числа $$$x$$$ от $$$l$$$ до $$$r$$$ проверять его на простоту за O($$$\sqrt{x}$$$). Тогда итоговая асимптотика будет O($$$r \sqrt{r}$$$).

Вторая группа тестов:

1. Напишем обыкновенное решето Эратосфена за O($$$n \log n$$$) или за O($$$n \log \log n$$$) в зависимости от реализации.

2. Запустим перебор каждого числа от $$$l$$$ до $$$r$$$. Будем проверять числа на простоту эффективными методами, например вероятностным тестом Ферма за O($$$\log n$$$). Получаем асимптотику O($$$n \log n$$$)

Полное решение:

Напишем решето Эратосфена за O($$$n$$$)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e8;
 
int lp[N + 1];
int pref[N + 1];
int pr[N / 10 + 1];
int r = 0;
 
void precalc(int n) {
    for (int i=2; i<=n; ++i) {
        pref[i] += pref[i - 1];
        if (lp[i] == 0) {
            pref[i]++;
            lp[i] = i;
            pr[r] = i;
            r++;
        }
        for (int j = 0; j < r && pr[j] <= lp[i] && i * pr[j] <= n; ++j)
            lp[i * pr[j]] = pr[j];
    }
}
 
int32_t main(){
    int32_t l, r;
    cin >> l >> r;
    precalc(r);
    cout << pref[r] - pref[l];
}

Давайте научимся узнавать для заданной перестановки, сколько существует перестановок, лексикографически меньших заданной.

Давайте переберём перестановку. Предположим, что мы зафиксировали какой-то элемент $$$p_i$$$, тогда переберём все числа, меньшие $$$p_i$$$, но не использовавшиеся раньше. Правее них мы можем ставить любые числа по определению лексикографически меньшей перестановки.

Количество вариантов для каждого такого числа, меньшего $$$p_i$$$, будет равняться количеству перестановок, то есть $$$(n - i)!$$$ ( в 1-индексации). Асимптотика решения равна $$$O(n^2)$$$.

Используя дерево отрезков или дерево Фенвика можно получить асимптотику $$$O(n \log n)$$$

Зная количество перестановок, лексикографически меньших, мы можем найти номер текущей перестановки, прибавив 1.

#include <bits/stdc++.h>
using namespace std;

long long mod=1000000007;
long long n, fact[100005], perm;
long long fenw[1<<20];

void update(int x){
	while (x!=1<<20){
		fenw[x]++;
		x+=x&-x;
	}
}

long long query(int poz){
	long long ret=0;
	while (poz){
		ret+=fenw[poz];
		poz-=poz&-poz;
	}
	return ret;
}

int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
fact[1]=1;
for (int i=2; i<=n; i++)
	fact[i]=(fact[i-1]*i)%mod;
long long ans=1;
for (int i=1; i<=n; i++){
	cin >> perm;
	long long prev = perm-1-query(perm);
	update(perm);
	ans = (ans + (prev*fact[n-i])%mod)%mod;
} 
cout << ans << endl;
return 0;
}

Задача аналогична предыдущей. Будем восстанавливать сочетание слева направо. Переберём возможные значения текущего элемента и проверим, сколько сочетаний текущий элемент порождает. В зависимости от этого числа или ищем элемент дальше и отнимает полученное число сочетаний, или фиксируем этот элемент и переходим к поиску следующего. Асимптотика — O($$$k^2$$$).

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

int c[100][100];

void precalc(){
    for(int i = 0; i <= 32; i++)
        c[i][0] = 1;
    for(int i = 1; i <= 32; i++)
        for(int j = 1; j <= 32; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}

int32_t main() {
    precalc();
    int n, k, p;
    cin >> n >> k >> p;
    int prev = -1;
    for(int i = 0; i < k; i++){
        for(int j = max(prev + 1, (int)1); j <= n; j++){
            if(p < c[n - j][k - i - 1]){
                prev = j;
                cout << j << ' ';
                break;
            }
            else
                p -= c[n - j][k - i - 1];
        }
    }
}

Первые две группы тестов:

Напишем переборное решение. Просто удаляем ребро из графа для первого запроса, для второго запроса запустим DFS. Итоговая асимптотика — O($$$n^2$$$).

Будем обрабатывать запросы с конца. Тогда у нас есть пустой граф и два вида запросов: merge и ask. На такие запросы умеет отвечать такая структура данных, как СНМ(DSU). Асимптотика — O($$$n \cdot \alpha(n)$$$), где $$$\alpha(n)$$$ можно считать равным 5.

#include <bits/stdc++.h>

using namespace std;


int p[100000];
int rk[100000];

void init_dsu() {
    for (int i = 0; i < 100000; i++) {
        p[i] = i;
        rk[i] = 1;
    }
}

int get_root(int v) {
    if (p[v] == v) {
        return v;
    } else {
        return p[v] = get_root(p[v]);
    }
}

bool merge(int a, int b) {
    int ra = get_root(a), rb = get_root(b);

    if (ra == rb) {
        return false;
    } else {
        if (rk[ra] < rk[rb]) {
            p[ra] = rb;
        } else if (rk[rb] < rk[ra]) {
            p[rb] = ra;
        } else {
            p[ra] = rb;
            rk[rb]++;
        }

        return true;
    }
}

int32_t main() {
    cout.setf(ios::fixed);
    cout.precision(9);
    ios::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    init_dsu();
    while (m--){
        int u, v;
        cin >> u >> v;
    }
    vector<pair<string, pair<int, int>>> q;
    while(k--){
        string s;
        int u, v;
        cin >> s >> u >> v;
        q.emplace_back(s, make_pair(u, v));
    }
    stack<bool> st;
    while(!q.empty()){
        string s = q.back().first;
        int u = q.back().second.first, v = q.back().second.second;
        q.pop_back();
        if(s == "1")
            merge(u, v);
        else
            st.push(get_root(u) == get_root(v));
    }
    while(!st.empty()){
        cout << (st.top() ? "YES\n" : "NO\n");
        st.pop();
    }
}

В задаче требуется найти в массиве четыре таких различных числа a, b, c, d, что $$$a \oplus b \oplus c \oplus d = 0$$$. Переформулируем: $$$a \oplus b = c \oplus d$$$. Пусть k = $$$a \oplus b$$$. Сколько различных значений может принимать k? Самый старший бит $$$10^6$$$ это 16, а $$$2^{17}$$$ — 1 это 131071 — максимальное число, которое можно получить с помощью $$$a \oplus b$$$. Получаем 131072 различных значений $$$a \oplus b$$$. В массиве из n различных элементов, есть $$$\frac{n \cdot (n - 1)}{2}$$$ различных пар, а значит столько же ксоров двух чисел. Решив $$$\frac{n \cdot (n - 1)}{2}$$$ = 131072 и округлив ответ в большую сторону, получаем верхнюю оценку на n — 513. Значит, если размер массива больше или равен 513, то ответ точно Yes. Иначе решаем перебором за $$$n^2$$$.

#pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse", "sse2", "sse3", "sse4")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define orset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define hti cc_hash_table<int, int, hash<int>>
#define htp cc_hash_table<int, pii, hash<int>>
// #define double long double
// #define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define x first
#define y second
#define all(a) (a.begin()), (a.end())
#define gsz(x) ((int)x.size())
#define mat vector<vector<int>>
#define endl "\n"
#define LOCAL
#ifdef LOCAL
#define dbg(x) cerr << #x << ":" << (x) << endl
#define print(x) cerr << (x) << endl
#else
#define dbg(x) 0
#define print(x) 0
#endif

using namespace std;
using namespace __gnu_pbds;

const int N = 1e6 + 10;
const int B = 300;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int n;
int a[N];
bool was[N];

int32_t main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // cout.precision(10);

    cin >> n;

    for(int i = 0; i < n; ++i)
    	cin >> a[i];

    if(n >= 513)
    {
    	cout << "Yes" << endl;
    	return 0;
    }

    for(int i = 0; i < n; ++i)
    	for(int j = i + 1; j < n; ++j)
    		if(was[a[i] ^ a[j]])
    		{
    			cout << "Yes" << endl;
    			return 0;
    		}
    		else
    			was[a[i] ^ a[j]] = true;

    cout << "No" << endl;
}

// n * (n - 1) / 2 = 131072
// n * (n - 1) = 262144
// n^2 - n - 262144 = 0
// d = 1048577
// n = (1 + 1025) / 2 = 513

Давайте добавим дополнительную вершину n + 1, которую мысленно соединим со всеми остальными вершинами. Стоимость каждого полученного ребра $$$(u, n + 1)$$$ будет $$$c_u$$$. Теперь построим MST(Мин остов) по такому графу. Это и будет ответ. Восстанавливать ответ тоже достаточно просто: из тех вершин, из которых MST провёл рёбра в дополнительную вершину, будет электростанция. Асимптотика — O($$$m \log n$$$).

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

struct point{
    int x, y;
};

int32_t main() {
    cout.setf(ios::fixed);
    cout.precision(9);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int g[n + 1][n + 1];
    point a[n];
    for(auto &i: a)
        cin >> i.x >> i.y;
    g[n][n] = 0;
    for(int i = 0; i < n; i++){
        cin >> g[n][i];
        g[i][n] = g[n][i];
    }
    int k[n];
    for(auto &i: k)
        cin >> i;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            g[i][j] = g[j][i] = (abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y)) * (k[i] + k[j]);
    bool used[n + 1];
    memset(used, false, sizeof used);
    int min_e[n + 1];
    for(int i = 0; i <= n; i++)
        min_e[i] = LLONG_MAX;
    int sel_e[n + 1];
    memset(sel_e, -1, sizeof sel_e);
    min_e[0] = 0;
    vector<pair<int, int>> ans;
    for (int i=0; i<=n; ++i) {
        int v = -1;
        for (int j=0; j<=n; ++j)
            if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
                v = j;
        used[v] = true;
        if (sel_e[v] != -1)
            ans.emplace_back(v, sel_e[v]);
        for (int to=0; to<=n; ++to)
            if (!used[to] && v != to && g[v][to] < min_e[to]) {
                min_e[to] = g[v][to];
                sel_e[to] = v;
            }
    }
    int w = 0;
    for(auto i: min_e)
        w += i;
    cout << w << '\n';
    vector<int> f;
    vector<pair<int, int>> s;
    for(auto i: ans) {
        if (i.first == n || i.second == n)
            f.emplace_back(i.first == n ? i.second : i.first);
        else
            s.push_back(i);
    }
    cout << f.size() << '\n';
    for(auto i: f)
        cout << i + 1 << ' ';
    cout << '\n';
    cout << s.size() << '\n';
    for(auto i: s)
        cout << i.first + 1 << ' ' << i.second + 1 << '\n';
}

1, 2 и (3, если написать аккуратно) группа тестов:

1 вариант. Будем добавлять элементы в сет, а на запрос второго вида пройдёмся по сету и посчитаем то, что нас просят. Асимптотика — O($$$n^2$$$).

2 вариант. Будем добавлять элементы в сортированный вектор и поддерживать для него префиксные суммы. Таким образом, асимптотика будет O($$$n \cdot (n + \log n)$$$)

Полное решение:

Нам нужна такая структура данных, которая умеет быстро добавлять элементы и узнавать требуемую сумму. Для данной задачи можно построить декартово дерево, которое может добавлять элементы. Так же будем хранить в вершине дерева сумму на поддереве. Мы можем создать декартово дерево, которое будет поддеревом исходного, которое будет хранить все ключи от $$$l$$$ до $$$r$$$, с помощью операции split. А теперь сумма в корне это и будет требуемая сумма. Главное не забыть в конце объединить декартовы деревья в исходное. Асимптотика — O($$$n \log n$$$)

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> rnd(1, 100000000);

struct node{
    int key, pr;
    node *left, *right;
    int sz, sum;
    node(int k){
        sz = 1;
        key = sum = k;
        pr = rnd(gen);
        left = right = nullptr;
    }
};

int getsize(node* T){
    return T ? T->sz : 0;
}

int getsum(node* T){
    return T ? T->sum : 0;
}

void calc(node* &T){
    if(!T)
        return;
    T->sz = getsize(T->left) + getsize(T->right) + 1;
    T->sum = getsum(T->left) + getsum(T->right) + T->key;
}

pair<node*, node*> split(node* T, int k){
    if(T == nullptr)
        return {nullptr, nullptr};
    else if(T->key <= k){
        auto [T1, T2] = split(T->right, k);
        T->right = T1;
        calc(T);
        return {T, T2};
    }
    else{
        auto [T1, T2] = split(T->left, k);
        T->left = T2;
        calc(T);
        return {T1, T};
    }
}
node* merge(node* T1, node* T2){
    if(!T1)
        return T2;
    if(!T2)
        return T1;
    if(T1->pr > T2->pr){
        T1->right = merge(T1->right, T2);
        calc(T1);
        return T1;
    }
    else{
        T2->left = merge(T1, T2->left);
        calc(T2);
        return T2;
    }
}

bool find(node* T, int k){
    while(T) {
        if (T->key == k)
            return true;
        if(T->key > k)
            T = T->left;
        else
            T = T->right;
    }
    return false;
}
node* insert(node* T, int k){
    if(T == nullptr){
        T = new node(k);
        return T;
    }
    if(find(T, k))
        return T;
    auto [T1, T2] = split(T, k);
    T = merge(merge(T1, new node(k)), T2);
    return T;
}

int sum(node* &T, int l, int r){
    auto [T1, T2] = split(T, l - 1);
    auto [Tl, Tr] = split(T2, r);
    int sum = getsum(Tl);
    T = merge(merge(T1, Tl), Tr);
    return sum;
}

node* root = nullptr;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int sm = 0;
    while(n--){
        string s;
        cin >> s;
        if(s == "+"){
            int x;
            cin >> x;
            root = insert(root, (x + sm) % 1000000000);
            sm = 0;
        }
        else{
            int l, r;
            cin >> l >> r;
            sm = sum(root, l, r);
            cout << sm << '\n';
        }
    }
}

• Перебор:

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

• Динамическое программирование 1:

Создадим dp [n][5], что будет означать количество способов сделать очередь длины $$$n$$$, оканчивающуюся на 1, 2, 3, 4, 5 соответственно: dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = dp[1][5] = 1. Далее довольно простой переход: просто идём туда, куда можем по условию (суммируем значения тех вариантов, откуда могли прийти). Ответом будет сумма по последнему слою ДП.

• Динамическое программирование 2:

Просто будем хранить только последние два слоя ДП.

• Динамическое программирование 3, полное решение:

Представим себе матрицу 5х5, где все ячейки, кроме (3, 4), (3, 5), (5, 4), (5, 5), которые будут нулями, будут единицами, что будет означать возможность существования такой пары. Также изначально у нас есть один вариант для каждого варианта набора, заканчивающегося на патрон силой от 1 до 5 составить очередь длины 1 — взять соответствующий патрон. Тогда у нас есть ещё одна матрица 1x5, заполненная единицами — количество изначальных способов. Если если умножить вторую матрицу на первую, возведённую в степень $$$n-1$$$, то сумма элементов в первой строке полученной матрицы и будет искомым ответом, т. к. мы фактически находим количество для каждого варианта очереди, заканчивающегося на патрон силой от 1 до 5 составить очередь длины $$$n$$$.

#include <bits/stdc++.h>

#define int int64_t
#define double long double

using namespace std;

const int mod = 999999937;

vector<vector<int>> f;
vector<vector<int> > x;
vector<vector<int> > matrix;

vector<vector<int>> mult(vector<vector<int>> a, vector<vector<int>> b) {
    int m = a.size(), n = b.size(), k = b[0].size();
    vector<vector<int>> p(m, vector<int>(k));
    for(int i = 0; i < m; i++)
        for(int j = 0; j < k; j++)
            for(int l = 0; l < n; l++)
                p[i][j] = (p[i][j] + a[i][l] * b[l][j]) % mod;
    return p;
}

vector<vector<int> > binpow(vector<vector<int> > v, int y){
    if(y == 1)
        return v;
    if(y & 1)
        return mult(binpow(v, y - 1), v);
    vector<vector<int>> cur = binpow(v, y>>1);
    return mult(cur, cur);
}

int32_t main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    if (n == 1) {
        cout << 5 << '\n';
        return 0;
    }
    f.assign(1, vector<int>(5, 1));
    matrix.assign(5, vector<int>(5, 1));
    matrix[2][3] = matrix[2][4] = matrix[4][3] = matrix[4][4] = 0;
    x = binpow(matrix, n - 1);
    f = mult(f, x);
    int sum = 0;
    for (auto i: f[0]) {
        sum += i;
        if (sum >= mod)
            sum %= mod;
    }
    cout << sum << '\n';
}

Для первой группы тестов достаточно написать простой перебор за O($$$n^3$$$): добавим каждую подстроку в set и затем выведем размер сета.

Для второй группы можно написать тот же перебор, но с сохранением текущей строки и добавлением туда с перебором правой границы по одному символу. O($$$n^2$$$)

Для третьей группы тестов построим по строке суффиксный массив и насчитаем для него lcp (наибольший обший префикс). Теперь мы фактически просто берём очередной в порядке сортировки суффикс и смотрим, какие его префиксы дают новые подстроки. Текущий суффикс $$$p_i$$$ (где $$$p$$$ — суффиксный массив) даст в качестве новых подстрок все свои префиксы, кроме совпадающих с префиксами суффикса $$$p_{i-1}$$$. Т.е. все его префиксы, кроме $$$lcp_{i-1}$$$ первых, дадут новые подстроки. Тогда ответ на задачу будет $$$\sum_{i = 0}^{n - 1}(n - p_i) - \sum_{i = 0}^{n - 1}lcp_i$$$. Асимптотика — O($$$n \log n$$$).

Также можно решить эту задачу суффиксным деревом или префикс-функцией. Асимптотика — O($$$n$$$)

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

int sum_mod(int x, int y, int mod){
    x += y;
    if(x >= mod)
        x -= mod;
    return x;
}

void sort_cc_sh(string &s, vector<int> &sa) {
    int n = s.size();
    vector<int> a, na;
    vector<int> color, ncolor;
    vector<int> buckets;
    buckets.assign(256, 0);
    for (char c: s)
        buckets[c]++;
    for (int i = 1; i < 256; i++)
        buckets[i] += buckets[i - 1];
    a.assign(n, -1);
    for (int i = n - 1; i >= 0; i--)
        a[--buckets[s[i]]] = i;
    color.assign(n, 0);
    color[a[0]] = 0;
    for (int i = 1; i < n; i++)
        if (s[a[i]] != s[a[i - 1]])
            color[a[i]] = color[a[i - 1]] + 1;
        else
            color[a[i]] = color[a[i - 1]];
    na.assign(n, -1);
    ncolor.assign(n, -1);
    for (int l = 1; l < n; l <<= 1) {
        buckets.assign(n, 0);
        for (int i = 0; i < n; i++)
            buckets[color[i]]++;
        for (int i = 1; i < n; i++)
            buckets[i] += buckets[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            int j = a[i] - l;
            if (j < 0)
                j += n;
            na[--buckets[color[j]]] = j;
        }
        a.swap(na);
        ncolor[a[0]] = 0;
        for (int i = 1; i < n; i++)
            if (color[a[i]] == color[a[i - 1]] && color[sum_mod(a[i], l, n)] == color[sum_mod(a[i - 1], l, n)])
                ncolor[a[i]] = ncolor[a[i - 1]];
            else
                ncolor[a[i]] = ncolor[a[i - 1]] + 1;
        color.swap(ncolor);
    }
    sa = a;
}

void build_suf_array(string &s, vector<int> &sa){
    s.push_back((char)0);
    sort_cc_sh(s, sa);
    s.pop_back();
    sa.erase(sa.begin());
}

void build_lcp(string &s, vector<int> &sa, vector<int> &lcp){
    int n = s.size();
    lcp.assign(n - 1, -1);
    vector<int> pos(n);
    for(int i = 0; i < n; i++)
        pos[sa[i]] = i;
    int k = 0;
    for(int i = 0; i < n; i++){
        if(k > 0)
            k--;
        if(pos[i] == n - 1)
            k = 0;
        else{
            int j = sa[pos[i] + 1];
            while (max(i + k, j + k) < n && s[i + k] == s[j + k])
                k++;
            lcp[pos[i]] = k;
        }
    }
}

int32_t main() {
    string s;
    cin >> s;
    vector<int> sa;
    build_suf_array(s, sa);
    vector<int> lcp;
    build_lcp(s, sa, lcp);
    int sum = 0;
    for(auto i : sa)
        sum += s.size() - i;
    for(auto i: lcp)
        sum -= i;
    cout << sum;
}