Каждая операция увеличивает сумму ровно на $$$x$$$ вне зависимости от индекса, на который была применена операция.

Обозначим $$$A$$$ как изначальную сумму массива $$$a$$$. Каждая операция прибавляет $$$x$$$ к $$$A$$$. Нам нужно проверить, может ли $$$A$$$ стать равным $$$S$$$. Во первых, $$$S$$$ не должен быть меньше, чем $$$A$$$. Во вторых, их разница должна делиться на $$$x$$$, то есть $$$x$$$ должен делить ($$$S-A$$$).

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;

	while( t -- )
	{
		int n, s, x;
		cin >> n >> s >> x;
		int a[n + 5], sum = 0;

		for( int i = 1; i <= n; i ++ ) cin >> a[i], sum += a[i];

		if( sum > s || (s - sum) % x != 0 ) cout << "NO\\n";
		else cout << "YES\\n";
	}
}

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил

Если $$$p_1 = n$$$, то менять его нет смысла. Если $$$p_1 = n$$$ и $$$p_2 = n-1$$$, то и второй элемент менять не нужно и так далее. Таким образом, нам нужно найти первый индекс $$$i$$$, для которого $$$p_i\neq n-i+1$$$ и увеличить его. Наша цель — приравнять $$$p_i$$$ к $$$n-i+1$$$ (тогда перестановка будет максимальна лексикографически). Найдем индекс $$$j$$$ такой, что $$$p_j$$$ равен $$$n-i+1$$$ и сделаем операцию $$$[i, j]$$$.

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;

	while( t -- )
	{
		int n;
		cin >> n;

		int p[n + 5], ind = 1;

		for( int i = 1; i <= n; i ++ )
		{
			cin >> p[i];
		}
		while( ind <= n && p[ind] == n - ind + 1 ) ind ++;
		int id = -1;

		for( int i = ind; i <= n; i ++ )
		{
			if( p[i] == n - ind + 1 ) id = i;
		}
		for( int i = 1; i < ind; i ++ ) cout << p[i] << ' ';

		if( id != -1 )
		{
			for( int i = id; i >= ind; i -- ) cout << p[i] << ' ';
			for( int i = id + 1; i <= n; i ++ ) cout << p[i] << ' ';
		}
		cout << '\\n';
	}
}

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил

Для начала, попытаемся максимизировать все элементы $$$a$$$, а после ответим на запросы.

Для начала, попытаемся максимизировать все элементы $$$a$$$, а после ответим на запросы. Переберем $$$i$$$ от $$$n$$$ до $$$1$$$ и приравняем $$$a_i$$$ к максимуму среди $$$a_i$$$, $$$b_i$$$ и $$$a_{i+1}$$$. Таким образом, каждый $$$a_i$$$ достигает максимального значения. Теперь мы можем написать префиксные суммы на массиве $$$a$$$, чтобы отвечать за $$$O(1)$$$ на каждый запрос.

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
signed main()
{
    int t; cin >> t;
    
    while( t -- )
    {
    	int n, q; cin >> n >> q;
    	int a[n + 5], b[n + 5], pref[n + 5], ans = 0;
    	
    	for( int i = 1; i <= n; i ++ ) cin >> a[i];
    	for( int i = 1; i <= n; i ++ ) cin >> b[i];

	a[n + 1] = 0;

	for( int i = n; i > 0; i -- ) a[i] = max({a[i], a[i + 1], b[i]});
    	
    	pref[0] = 0;
    	for( int i = 1; i <= n; i ++ ) pref[i] = pref[i - 1] + a[i];
    	
    	for( int i = 1; i <= q; i ++ ){
    	    int L, R; cin >> L >> R;
    	    cout << pref[R] - pref[L - 1] << " ";
    	}
    	cout << "\n";
    }
}

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил

Отсортируем все мечи по силе в порядке убывания. Тогда если сложность равна $$$a_i$$$, то количество мечей, которые можно использовать, равно $$$i$$$. По мере уменьшения сложности растет количество мечей, а значит и количество уровней, которые можно пройти. Можно поддерживать указатель на количество уровней и брать максимальный счет среди всех сложностей. Такое решение с указателем работает за $$$O(n)$$$ операций.

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int N = 2e5 + 12;
 
int t, n, a[N], b[N];
 
int main()
{
    cin >> t;
    
    while( t -- )
    {
        cin >> n;
        
        for( int i = 1; i <= n; i ++ ) cin >> a[i];
        for( int i = 1; i <= n; i ++ ) cin >> b[i];
        
        int h = 0, sum = 0; ll ans = 0;
        sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
        
        for( int i = 1; i <= n; i ++ )
        {
            while( h < n && sum + b[h + 1] <= i ) h ++, sum += b[h];
            ans = max(ans, a[i] * 1ll * h);
        }
        cout << ans << '\n';
    }
}

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил

Попробуйте дп подход к задаче.

Будем писать динамику. $$$dp[x]$$$ это ответ для числа $$$x$$$. Изначально $$$dp[a_i] = 1$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$, все остальные элементы $$$dp$$$ будут равны $$$10^9$$$. Переберем $$$x$$$ от $$$1$$$ до $$$n$$$ и рассмотрим переход:

• Переберем все делители $$$y$$$ числа $$$x$$$.
• Обновим $$$dp[x]$$$ на $$$min(dp[x], dp[y] + dp[\frac{x}{y}])$$$.

Заменим все $$$dp[x]$$$ равные $$$10^9$$$ на $$$-1$$$ и выведем все значения $$$dp$$$. В решении мы перебрали все числа от $$$1$$$ до $$$n$$$ и их делителей, суммарно это $$$O(n \log n)$$$ операций.

#include <bits/stdc++.h>
 
using namespace std;
const int maxn = 1'000'012;
 
int a[maxn], dp[maxn];
int n, q;
 
void solve() {
    cin >> n;
 
    for(int i = 1; i <= n; i++) {
        dp[i] = 1e9;
    }
    for(int i = 1; i <= n;i++) {
        cin >> a[i];
        dp[a[i]] = 1;
    }
 
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j += i) {
            dp[j] = min(dp[j], dp[i] + dp[j / i]);
        }
    }
 
    for(int i = 1; i <= n; i++) {
        if(dp[i] == 1e9) {
            dp[i] = -1;
        }
        cout << dp[i] << " \n"[i == n];
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил

Разобьем точки доставки на группы с одинаковым $$$x_i$$$. Пронумеруем группы от $$$0$$$ до $$$m+1$$$ в порядке возрастания $$$x_i$$$, где $$$m$$$ это количество различных $$$x_i$$$. Группа $$$0$$$ это точка старта и группа $$$m+1$$$ это точка финиша.

Поскольку мы не можем делать ходы влево, нужно доставить пиццу во все точки группы $$$i$$$, прежде чем перейти к группе $$$i+1$$$. Обозначим $$$high_i$$$ как точку с максимальным значением $$$y$$$ и $$$low_i$$$ как точку с минимальным значением $$$y$$$ в группе $$$i$$$. Поскольку все точки в группе находятся между ними, для группы, точкой куда доставят пиццу в последнюю очередь, окажется одна из них. Это означает, что переходить из группы $$$i$$$ в группу $$$i+1$$$ мы будем либо через $$$high_i$$$, либо через $$$low_i$$$.

Теперь мы можем написать динамику на задачу. $$$dp[i][0]$$$ это минимальное количество времени для того, чтобы доставить пиццу во все группы от $$$0$$$ до $$$i$$$, последней доставив в точку $$$high_i$$$, и $$$dp[i][1]$$$ с точкой $$$low_i$$$ соответственно. Изначально, $$$dp[0][0] = 0$$$ и $$$dp[0][1] = 0$$$. Для всех других $$$i\gt 0$$$, переходы будут следующие:

• $$$dp[i][0] = min(dp[i - 1][0] + dist(high_{i-1}, low_i), dp[i - 1][1] + dist(low_{i-1}, low_i)) + dist(low_i, high_i);$$$
• $$$dp[i][1] = min(dp[i - 1][0] + dist(high_{i-1}, high_i), dp[i - 1][1] + dist(low_{i-1}, high_i)) + dist(high_i, low_i);$$$

Тут $$$dist(a, b)$$$ означает манхэттенское расстояние между точками $$$a$$$, $$$b$$$. Таким образом, на сортировку всех точек по группам уходит $$$O(n \log n)$$$ операций, а на подсчет динамики $$$O(n)$$$ операций.

#include <bits/stdc++.h>
 
#define F first
#define S second
#define int long long
 
using namespace std;
 
int t, n, ax, ay, bx, by;
 
signed main()
{
    cin >> t;
    
    while( t -- )
    {
        cin >> n >> ax >> ay >> bx >> by;
        vector <int> x(n + 5), y(n + 5), dp[2];
        
        dp[0] = dp[1] = vector <int> (n + 5, 0);
        map <int, int> mx, mn;
        
        mn[ax] = mx[ax] = ay;
        mn[bx] = mx[bx] = by;
        
        for( int i = 0; i < n; i ++ ) cin >> x[i];
        for( int i = 0; i < n; i ++ ) cin >> y[i];
        
        for( int i = 0; i < n; i ++ )
        {
            mx[x[i]] = max(mx[x[i]], y[i]);
            
            if(!mn.count(x[i])) mn[x[i]] = y[i];
            else mn[x[i]] = min(mn[x[i]], y[i]);
        }
        int lst = ax, cnt = 0;
        
        for( auto i : mx )
        {
            if( i.F == ax )
            {
                dp[0][0] = dp[1][0] = 0;
                continue;
            }
            int need = (i.F - lst) + (mx[i.F] - mn[i.F]);
            cnt ++;
            
            dp[0][cnt] = min(dp[0][cnt - 1] + abs(mx[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mx[i.F] - mx[lst])) + need;
            dp[1][cnt] = min(dp[0][cnt - 1] + abs(mn[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mn[i.F] - mx[lst])) + need;
            
            lst = i.F;
        }
        cout << dp[0][cnt] << '\n';
    }
}

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил

Попробуйте разделить вершины по парам и запрашивать у интерактора эти пары.

Для начала, выпишем номера всех вершин дерева в последовательность $$$p$$$ в порядке обхода дфс. Разделим элементы последовательности $$$p$$$ по парам $$$(p_1, p_2)$$$, $$$(p_3, p_4)$$$ и так далее. Если $$$n$$$ нечетный, то временно забудем о последнем элементе.

Переберем $$$i$$$ от 1 до $$$\frac{n}{2}$$$ и будем делать интерактору следующий запрос: $$$?$$$ $$$p_{2i-1}$$$ $$$p_{2i}$$$.

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

Когда $$$n$$$ нечетен, остается одна неопрошенная вершина. Если мы не нашли вершину из скрытого пути ни в одной паре, то однозначно можно сказать, что оставшаяся вершина и есть та, которая лежит на скрытом пути. В итоге мы получаем решение, которое работает ровно за $$$\lfloor\frac{n}{2}\rfloor$$$ + 1 запросов.

#include <bits/stdc++.h>
 
#define sz(x) (int)(x.size())
#define pb push_back
 
using namespace std; 
const int N = 2e5 + 12;
 
int n, x, y, a, b;
vector <int> L, g[N];
 
void dfs( int v, int p = 0 )
{
	L.pb(v);
	
	for( auto to : g[v] )
	{
		if( to != p ) dfs(to, v);
	}
}
int ask( int a, int b )
{
	cout << "? " << a << ' ' << b << endl;
	int res; cin >> res; return res;
}
void solve()
{
	cin >> n;
	
	L.clear();
	for( int i = 1; i <= n; i ++ ) g[i].clear();
	
	for( int i = 1; i < n; i ++ )
	{
		cin >> a >> b;
		g[a].pb(b), g[b].pb(a);
	}
	dfs(1, 0);
	
	for( int i = 0; i < sz(L) - 1; i += 2 )
	{
		a = L[i], b = L[i + 1];
		
		if( ask(a, b) == 1 )
		{
			if( ask(a, a) == 1 ) cout << "! " << a << endl;
			else cout << "! " << b << endl;
			return;
		}
	}
	cout << "! " << L.back() << endl;
}
int main()
{
	int t; cin >> t;
	while( t -- ) solve();
}

##

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил

Для начала возьмем все элементы по модулю $$$2$$$. Теперь все элементы равны единицам и нулям. Можно заметить, что если удалить все $$$a_i$$$, которые равны нулю, то $$$S_v$$$ для других не изменится. Удалим все $$$a_i$$$ равные нулю, у которых изначальный $$$S_v$$$ нечетен, если $$$S_v$$$ равен нулю, то ответа нет. Тех $$$v$$$, у которых $$$S_v$$$ четен, мы удаляем по мере удаления единиц.

Теперь нужно разобраться с единицами. Всех $$$v$$$, у которых $$$a_v$$$ равен нулю, удалим из графа, оставив лес (граф из нескольких несвязных деревьев) из единиц. Решим задачу для каждого нового дерева из единиц. Для какого-то дерева из единиц размера $$$n$$$, ответа нет, когда $$$n$$$ четен. Когда $$$n$$$ четен, количество ребер нечетно, но каждое удаление удаляет одну вершину и четное количество ребер. Отнимая от изначального нечетного количество ребер четные числа, мы никогда не достигнем нуля ребер (то есть пустого графа). Теперь сделаем утверждение — когда $$$n$$$ нечетен, ответ есть всегда.

Скажем, что для пары смежных вершин $$$(v, u)$$$, $$$v$$$ дает вклад в $$$u$$$ тогда, когда при удаление $$$u$$$, компонента вершины $$$v$$$ становится четного размера. Обозначим $$$f(v)$$$ как количество вершин, дающих вклад в $$$v$$$. Можно понять, что удалять нужно ту вершину, у которой $$$f(v)$$$ равен нулю. Компоненты всех соседей у такой вершины нечетного размера, а для получения нечетного $$$n$$$, нам нужно чтобы у нее было четное количество соседей (значит мы однозначно сможем удалить ее из графа). Теперь утверждается, что такая вершина всегда есть.

Можно заметить, что после удаления вершины $$$v$$$, значения $$$f$$$ меняются только для соседей $$$v$$$. Для всех соседей $$$u$$$ вершины $$$v$$$ значение $$$f(u)$$$ уменьшается на $$$1$$$, ведь вклад давался из $$$v$$$ в $$$u$$$. Один раз посчитаем все значения $$$f$$$, и с помощью BFS будем удалять вершины, у которых значения $$$f$$$ равно нулю. Также не будем забывать, что некоторые нулю нужно удалить по мере удаления единиц. Это решение работает за O(n) операций.

Скажем, что корень дерева это вершина $$$1$$$. Будем писать динамику для задачи. Обозначим ее следующим образом:

• $$$dp_v = 0$$$, если вершину $$$v$$$ удалить невозможно
• $$$dp_v = 1$$$, если для удаления вершины $$$v$$$, родитель вершины $$$v$$$ обязательно должен удаляться раньше вершины $$$v$$$.
• $$$dp_v = 2$$$, если для удаления вершины $$$v$$$, вершина $$$v$$$ обязательно должна удаляться раньше своего родителя.
• $$$dp_v = 3$$$, если для удаления вершины $$$v$$$ неважно, удалим мы родителя вершины или саму вершину первой.

Если хотя бы для одного $$$v$$$, $$$dp_v$$$ равен нулю, то ответа не будет. Обозначим $$$p_v$$$ как родителя вершины $$$v$$$ и $$$s_v$$$ как сумму всех значений $$$a_u$$$, где $$$u$$$ это ребенок вершины $$$v$$$ и $$$dp_u$$$ равен $$$1$$$ или $$$3$$$. Для того, чтобы $$$dp_v$$$ был равен $$$1$$$, должно выполняться как минимум одно из двух условий:

• $$$s_v$$$ по четности не равен $$$a_v$$$.
• $$$s_v$$$ по четности равен $$$a_v$$$, но у вершины есть ребенок $$$u$$$, для которого $$$dp_u = 3$$$ и $$$a_u = 1$$$. То есть, мы можем удалить $$$u$$$ раньше, чем $$$v$$$, тем самым изменив четность $$$s_v$$$.

Прибавим $$$a_{p_v}$$$ к $$$s_v$$$ и проверим условия еще раз для $$$dp_v = 2$$$. Если в обоих случаях условия выполняются, то $$$dp_v = 3$$$, а если никакое не выполняется, то $$$dp_v = 0$$$. Осталось просто восстановить ответ по динамике, подробности можете посмотреть в реализации. Асимптотика решения — $$$O(n)$$$.

#include <bits/stdc++.h>
#define ent '\n'
#define int long long
 
using namespace std;
const int maxn = 200012;
const int mod = 1e9 + 7;
 
int cnt[maxn], a[maxn], del[maxn];
int sz[maxn], bad[maxn], used[maxn];
vector<int> g[maxn], e[maxn], g2[maxn];
int n, m;
 
void dfs(int v, int p) {
    sz[v] = 1;
    used[v] = true;
    for(int to : g[v]) {
        if(to == p) {
            continue;
        }
 
        dfs(to, v);
 
        if(sz[to] % 2 == 0) {
            e[to].push_back(v);
            bad[v]++;
        }
        else {
            e[v].push_back(to);
            bad[to]++;
        }
 
        sz[v] += sz[to];
    }
}
 
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= 2;
        del[i] = cnt[i] = sz[i] = 0;
        bad[i] = used[i] = 0;
        g[i].clear();
        g2[i].clear();
        e[i].clear();
    }
 
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
 
        cnt[u] += a[v], cnt[v] += a[u];
 
        if(a[u] && a[v]) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        if( a[u] && !a[v] ) g2[u].push_back(v);
        if( a[v] && !a[u] ) g2[v].push_back(u);
    }
    queue <int> q;
 
    for(int i = 1; i <= n; i++) {
        if(!cnt[i] && !a[i]) {
            cout << "NO\n";
            return;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] && !used[i]) {
            dfs(i, 0);
            if(sz[i] % 2 == 0) {
                cout << "NO\n";
                return;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] && !bad[i]) {
            q.push(i);
        }
    }
    cout << "YES\n";
    int zero[n + 5];
    
    for( int i = 1; i <= n; i ++ ){
        zero[i] = 0;
        
        if( !a[i] && cnt[i] % 2 ) cout << i << ' ';
        else if( !a[i] ) zero[i] = 1;
    }
    while(!q.empty()) {
        int v = q.front(); q.pop();
        cout << v << ' ';
        for(int to : g2[v]){
            if(zero[to]) cout << to << ' ', zero[to] = 0;
        }
        for(int to : e[v]) {
            bad[to]--;
            if(bad[to] == 0) q.push(to);
        }
    }
    cout << ent;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 12;
const int inf = 1e9 + 1;

int n, x, y, a[N], dp[N], cnt[N], par[N];
vector <int> g[N], g2[N]; bool flag, used[N];
pair <int, int> must[N][3]; vector <int> ord;

void dfs( int v, int p = 0 )
{
	int s = 0, ok = 0, id = 0;
	par[v] = p; ord.push_back(v);
	
	for( auto to : g[v] )
	{
		if( to == p ) continue;
		
		dfs(to, v);
		if(!flag) return;
		
		if( dp[to] == 1 || dp[to] == 3 )
		{
			s ^= a[to];
			
			if( dp[to] == 3 && a[to] == 1 )
			{
				if( !ok )
				{
					ok = 1;
					id = to;
				}
			}
			if( dp[to] == 3 && id != to ) dp[to] = 1;
		}
	}
	if( !ok && s == a[v] && (s + a[p]) % 2 == a[v] )
	{
		flag = 0;
		return;
	}
	if( s != a[v] || ok )
	{
		if( s == a[v] ) must[v][1] = {id, 2};
		else if(ok) must[v][1] = {id, 1};
		
		dp[v] = 1;
	}
	s = (s + a[p]) % 2;
	
	if( s != a[v] || ok )
	{
		if( s == a[v] ) must[v][2] = {id, 2};
		else if(ok) must[v][2] = {id, 1};
		
		dp[v] += 2;
	}
}
void dfs2( int v, int tp )
{
	dp[v] = tp, used[v] = 1;
	pair <int, int> p = must[v][tp];
	if( p.first != 0 ) dfs2(p.first, p.second);
}
void solve()
{
	cin >> n;
	flag = 1;
	
	// dp[v] = 1, if p[v] before v
	// dp[v] = 2, if v before p[v]
	
	for( int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		a[i] %= 2;
		
		must[i][1] = must[i][2] = {0, 0};
		dp[i] = cnt[i] = used[i] = 0;
		g[i].clear(), g2[i].clear();
	}
	for( int i = 1; i < n; i ++ )
	{
		cin >> x >> y;
		
		g[x].push_back(y);
		g[y].push_back(x);
	}
	ord.clear();
	dfs(1);
	
	if( !flag )
	{
		cout << "No\n";
		return;
	}
	cout << "Yes\n";
	
	for( auto i : ord )
	{
		if( !used[i] )
		{
			if( dp[i] == 3 ) dfs2(i, 1);
			else dfs2(i, dp[i]);
		}
	}
	for( int v = 2; v <= n; v ++ )
	{
		if( dp[v] == 1 ) cnt[v] ++, g2[par[v]].push_back(v);
		else cnt[par[v]] ++, g2[v].push_back(par[v]);
	}
	queue <int> q;
	
	for( int i = 1; i <= n; i ++ )
	{
		if( cnt[i] == 0 ) q.push(i);
	}
	while( !q.empty() )
	{
		int v = q.front();
		q.pop(); cout << v << ' ';
		
		for( auto to : g2[v] )
		{
			cnt[to] --;
			if( !cnt[to] ) q.push(to);
		}
	}
	cout << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	
	int t; cin >> t;
	while(t --) solve();
}

• Классная задача
• Нормальная задача
• Плохая задача
• Не решил