Рассмотрим остаток от деления $$$n$$$ на $$$3$$$ до первого хода. Если он равен $$$1$$$ или $$$2$$$, то Ваня за первый ход может сделать число $$$n$$$ кратным $$$3$$$, то есть он побеждает. Пусть остаток равен $$$0$$$, тогда Ваня обязан изменить число, после чего оно не будет делиться на $$$3$$$. Тогда Вова может сделать тоже самое действие, что и Ваня, и сделать его снова делящимся на $$$3$$$. Так может продолжаться до бесконечности, поэтому выигрывает Вова.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    if (n % 3) {
        cout << "First\n";
    } else {
        cout << "Second\n";
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Решение №1:

Поскольку $$$k$$$ является делителем $$$n$$$, то существует $$$O(\sqrt[3]{n})$$$ таких $$$k$$$. Можно перебрать все k, посчитать за $$$O(n)$$$ заданное значение и взять максимальное из них. Общая сложность — $$$O(n \cdot \sqrt[3]{n})$$$.

Решение №2:

Не используя факт, что $$$k$$$ является делителем $$$n$$$, можно просто перебрать $$$k$$$, а затем посчитать искомые значения, используя префиксные суммы, и в конце проверить, что в каждом отрезке ровно $$$k$$$ элементов. Такое решение работает за $$$O(\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}) = O(n \log n)$$$.

#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define all(x) x.begin(), x.end()
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    ll ans = -1;
    for (int d = 1; d <= n; ++d) {
        if (n % d == 0) {
            ll mx = -1e18, mn = 1e18;
            for (int i = 0; i < n; i += d) {
                ll sm = 0;
                for (int j = i; j < i + d; ++j) {
                    sm += a[j];
                }
                mx = max(mx, sm);
                mn = min(mn, sm);
            }
            ans = max(ans, mx - mn);
        }
    }
    cout << ans << '\n';
}
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) solve();
}

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

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

Общая сложность — $$$O(n)$$$.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = a[0];
    int mn = min(0, a[0]), sum = a[0];
    for (int i = 1; i < n; ++i) {
        if (abs(a[i] % 2) == abs(a[i - 1] % 2)) {
            mn = 0;
            sum = 0;
        }
        sum += a[i];
        ans = max(ans, sum - mn);
        mn = min(mn, sum);
    }
    cout << ans << endl;
}
 
int main() {
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

В задаче требуется посчитать количество пар индексов $$$(i, j)$$$ ($$$i < j$$$) таких, что $$$(2^a)^{(2^b)} = (2^b)^{(2^a)}$$$, где $$$a = b_i, b = b_j$$$. Очевидно, что при $$$a = b$$$ данное равенство выполняется. Пусть $$$a \neq b$$$, тогда перепишем равенство: $$$(2^a)^{(2^b)} = (2^b)^{(2^a)} \Leftrightarrow 2^{(a \cdot 2^b)} = 2^{(b \cdot 2^a)} \Leftrightarrow a \cdot 2^b = b \cdot 2^a \Leftrightarrow \frac{a}{b} = \frac{2^a}{2^b}$$$. Очевидно, что $$$a$$$ и $$$b$$$ должны отличаться в степень двойки, иначе равенство не может быть выполнено, так как справа стоит отношение степеней двойки. Не теряя общности, предположим, что $$$b = a \cdot 2^k$$$ ($$$k > 0$$$), тогда уравнение принимает вид $$$\frac{a}{a \cdot 2^k} = \frac{2^a}{2^{a \cdot 2^k}} \Leftrightarrow \frac{1}{2^k} = \frac{1}{2^{(2^k - 1)a}} \Leftrightarrow 2^k = 2^{(2^k - 1)a}$$$. Если $$$k = 1$$$, то $$$a = 1$$$, $$$b = 2$$$. Если $$$k > 1$$$, то $$$2^k - 1 > k$$$, а значит равенство не может выполняться.

Таким образом, единственные возможные варианты, когда равенство выполняется, это если $$$b_i = b_j$$$ или $$$b_i = 1, b_j = 2$$$ (и наоборот). Посчитать количество таких пар можно за $$$O(n \log n)$$$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& x : a) cin >> x;
	ll ans = 0;
	map<int, int> cnt;
	for (int i = 0; i < n; i++) {
		ans += cnt[a[i]];
		if (a[i] == 1) ans += cnt[2];
		else if (a[i] == 2) ans += cnt[1];
		cnt[a[i]]++;
	}
	cout << ans << "\n";
}
 
signed main() {
	int t;
	cin >> t;
	while (t--) solve();
}

Рассмотрим позицию первого минимума в массиве, пусть она равна $$$k$$$. Все элементы, стоящие на позициях меньших, чем $$$k$$$, строго больше, значит, с ними необходимо применить операции, так как иначе массив не будет отсортирован. Пусть мы применили операции ко всем таким элементам, они заняли какие-то позиции после $$$k$$$ (так как они строго больше минимума), то есть сейчас в начале массива стоит минимальный элемент, перешедший с позиции $$$k$$$. Если применить к нему операцию, то он вернется на своё текущее место, так как он меньше либо равен всех элементов массива, то есть массив не изменится.

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

Тогда, если часть массива, находящаяся после позиции $$$k$$$, не отсортирована, то ответ равен $$$-1$$$, так как изменить порядок элементов в ней невозможно. В противном случае, ответ равен количеству элементов, стоящих до первого минимума, так как с ними необходимо применить операцию, и они окажутся на нужном месте в правой части. Общая сложность — $$$O(n)$$$.

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    fm = 0
    for i in range(n):
        if a[i] < a[fm]:
            fm = i
    for i in range(fm + 1, n):
        if a[i] < a[i - 1]:
            print(-1)
            return
    print(fm)
 
 
for _ in range(int(input())):
    solve()

Эту задачу можно решать несколькими похожими способами, один из них приведён ниже. Во-первых, за изначальное дерево удобнее всего взять бамбук — вершины от $$$1$$$ до $$$n$$$, соединённые по порядку. Далее, будем поддерживать следующую конструкцию. В каждый момент времени вершины $$$1$$$ и $$$2$$$ будут соединены ребром, от вершины $$$2$$$ будет отходить не более двух веток, представляющих из себя последовательно соединённые вершины (бамбук). Таким образом, в каждый момент времени в дереве будет не более трёх листов, один из которых вершина $$$1$$$.

Будем поддерживать вершины из двух веток в двух массивах. Тогда, пусть текущее число из запроса равно $$$d$$$. Если расстояние от какого-то из листов до вершины $$$1$$$ равно $$$d$$$, то операцию выполнять не надо. Иначе, сделаем такую операцию, чтобы расстояние от листа из, например, первой ветки до вершины $$$1$$$ было равно $$$d$$$. Если текущее расстояние больше $$$d$$$, то уберем лишние вершины в конец второй ветки, а иначе добавим нужные из конца второй ветки. Таким образом, после каждой операции расстояние от вершины $$$1$$$ до какого-то из листов будет равно $$$d$$$.

Преобразования можно делать полностью перенося вершины, тогда общая сложность — $$$O(nq)$$$.

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

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> b1, b2;
		for (int i = 0; i < n; ++i) {
			b1.push_back(i);
		}
		b2.push_back(1);
		for (int i = 1; i < n; ++i) {
			cout << i << ' ' << i + 1 << endl;
		}
		int q;
		cin >> q;
		while (q--) {
			int d;
			cin >> d;
			d++;
			if (b1.size() == d) {
				cout << "-1 -1 -1\n";
			} else if (b1.size() < d) {
				d = d - b1.size();
				vector<int> qq(b2.end() - d, b2.end());
				int u = b2[b2.size() - d];
				int v1 = b2[b2.size() - d - 1];
				int v2 = b1.back();
				cout << u + 1 << ' ' << v1 + 1 << ' ' << v2 + 1 << '\n';
				for (int i = 0; i < d; ++i) b2.pop_back();
				for (auto i : qq) b1.push_back(i);
			} else {
				d = b1.size() - d;
				vector<int> qq(b1.end() - d, b1.end());
				int u = b1[b1.size() - d];
				int v1 = b1[b1.size() - d - 1];
				int v2 = b2.back();
				cout << u + 1 << ' ' << v1 + 1 << ' ' << v2 + 1 << '\n';
				for (int i = 0; i < d; ++i) b1.pop_back();
				for (auto i : qq) b2.push_back(i);
			}
		}
	}
}

Запустим обход в глубину из вершины $$$1$$$ и выпишем времена входа и выхода для каждой вершины. Тогда, то что вершина $$$b$$$ является потомком вершины $$$a$$$ равносильно тому, что $$$\mathrm{tin}[a] \leq \mathrm{tin}[b] \leq \mathrm{tout}[b] \leq \mathrm{tout}[a]$$$, где $$$\mathrm{tin}$$$ и $$$\mathrm{tout}$$$ — времена входа и выхода соответственно. Тогда, создадим массив $$$a$$$, где $$$a_i = \mathrm{tin}[p_i]$$$, тогда задача свелась к тому, чтобы проверить, что на отрезке c $$$l$$$ по $$$r$$$ в массиве $$$a$$$ есть хотя бы одно число, принадлежащее отрезку $$$[\mathrm{tin}[x]; \mathrm{tout}[x]]$$$. Это можно сделать, например, с помощью Merge Sort Tree, тогда общая сложность будет $$$O(n \log n + q \log^ 2 n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
 
struct SegmentTree {
    int n;
    vector<vector<int>> tree;
 
    void build(vector<int> &a, int x, int l, int r) {
        if (l + 1 == r) {
            tree[x] = {a[l]};
            return;
        }
 
        int m = (l + r) / 2;
        build(a, 2 * x + 1, l, m);
        build(a, 2 * x + 2, m, r);
        merge(all(tree[2 * x + 1]), all(tree[2 * x + 2]), back_inserter(tree[x]));
    }
 
    SegmentTree(vector<int>& a) : n(a.size()) {
        int SIZE = 1 << (__lg(n) + bool(__builtin_popcount(n) - 1));
        tree.resize(2 * SIZE - 1);
        build(a, 0, 0, n);
    }
 
    int count(int lq, int rq, int mn, int mx, int x, int l, int r) {
        if (rq <= l || r <= lq) return 0;
        if (lq <= l && r <= rq) return lower_bound(all(tree[x]), mx) - lower_bound(all(tree[x]), mn);
 
        int m = (l + r) / 2;
        int a = count(lq, rq, mn, mx, 2 * x + 1, l, m);
        int b = count(lq, rq, mn, mx, 2 * x + 2, m, r);
        return a + b;
    }
 
    int count(int lq, int rq, int mn, int mx) {
        return count(lq, rq, mn, mx, 0, 0, n);
    }
};
 
vector<vector<int>> g;
 
vector<int> tin, tout;
int timer;
void dfs(int v, int p) {
    tin[v] = timer++;
    for (auto u : g[v]) {
        if (u != p) {
            dfs(u, v);
        }
    }
    tout[v] = timer;
}
 
void solve() {
    int n, q;
    cin >> n >> q;
    
    g.assign(n, vector<int>());
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    timer = 0;
    tin.resize(n);
    tout.resize(n);
    dfs(0, -1);
    
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
 
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = tin[p[i] - 1];
    SegmentTree ST(a);
 
    for (int i = 0; i < q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        l--; x--;
        if (ST.count(l, r, tin[x], tout[x])) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}
 
int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
        if(tests > 0) cout << "\n";
    }
    return 0;
}