Если нам нужно проверить был ли пропущен шаг 1, что нам нужно сделать.

Если a[i] = 6, b[i] = 6, то сколько шагов 1 мы пропустили?

В каждой итерации нам нужно рассматривать две операции, но что если обе операции по сути выполняют одну и ту же роль. Допустим число x>y, тогда мы будем уменьшать число x, аналогично для обратного случая, то есть мы как бы хотим сравнять число. Поэтому нам выгодно вообще не рассматривать вторую операцию, и следить только за первой. Поэтому давайте создадим цикл, где мы как бы следим, a[i]>b[i]? Если да, то добавляем к ответу их разницу. Дальше выводим ответ+1, потому что мы как бы всегда начинаем с первой итерации.

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll t; cin >> t;
  while (t--){
    ll n; cin >> n;
    ll ans = 1;
    vector<ll> a(n);
    vector<ll> b(n);
    for (ll i = 0;i<n;i++){
      cin >> a[i];
    }
    for (ll i = 0;i<n;i++){
      cin >> b[i];
    }
    for (ll i = 0;i<n;i++){
      if(a[i]>=b[i]){
      ans+=a[i]-b[i];
      }
    }
    cout << ans << endl;
  }
}

если n == 3, можете ли вы вывести эту последовательность: -1 2 -1? Если нет, то подумайте почему мы не можем этого сделать?

рассматривайте для нечетного n и четного n отдельное решение.

когда n == 2, можем ли использовать ту же логику?

Как я и сказал, это задача скорее про интуицию и контруктивность, чем про знание алгоритмов. В этой задаче нам нужно правильно вывести последовательность, чтобы любой подмассив и его сумма была положительной (x>0). Так же нам говорят, что последовательность должна быть минимальной с лексикографической точки зрения. Первая мысль которая приходит в голову это сделать последовательность что-то по типу этой -1 2 -1 2.... Подойдет ли это? Нет. Потому что мы должны понять, что любой подмассив длины >=2 должна быть положительной, а в данном случае у нас -1 + 2 -1 будет равна 0, что не соответствует нашему условию. Поэтому давайте поставим вместо 2, 3. последовательность меняется на такую, -1 3 -1 3.... Те кто написал это решение и получил ВА на 2 тесте, поздравляю вы не учли одну деталь. А именно, то что для каждой четности мы проблему рассматриваем по разному. Допустим н четное, то если мы поставим ответ так, -1 3 -1 3, то последовательность вроде бы правильная, но есть ответ лучше, а именно -1 3 -1 2. Да, именно так! То есть в конце мы можем просто поставить 2, вместо 3. Для нечетной н, мы можем вывести ту же последовательность. Теперь рассмотрим н равное двойке. Здесь мы не выводим -1 3, потому что так нельзя, поэтому рассмотрим этот случай отдельно. Общий алгоритм таков, для n = 2, просто выводим -1 2. Для n%2==0, выводим до н-1 последовательность -1 3 -1 3...., дальше просто в конце выведем 2. Для n%2==1 выведем до н, такую последовательность -1 3 -1 3 -1 3.... Это наш ответ.

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll t; cin >> t;
  while (t--){
    ll n; cin >> n;
    if(n==2){
      cout << -1 << " " << 2 << endl;
    }else{
      if(n%2==0){
      for (ll i = 0;i<n-1;i++){
        if(i%2==0){
          cout << -1 << " ";
        }else{
          cout << 3 << " ";
        }
      }
      cout << 2 << " ";
      cout << endl;
    }else{
      for (ll i = 0;i<n;i++){
        if(i%2==0){
          cout << -1 << " ";
        }else{
          cout << 3 << " ";
        }
      }
      cout<< endl;
    }}
  }
}

какие у числа x есть две минимальные точки, куда мы можем дойти делая две эти операции:x = abs(x-k),x = x+k?

Эти значения в обоих массивах должны быть равны, не больше не меньше.

Представим наши операции и какое-то число x в виде круга. ** .------0------.** ** .' / \ '.** ** .' (10) / \ (1) '.** ** / / \ ** ** | (9) / \ (2) |** ** | / + \ |** ** | (8) / | \ (3) |** ** \ \ | / /** ** '. (7)\ | /(4) .'** ** '. \ | / .'** ** '------5------'** допустим a = 7, b = 8, k = 5. у а минимальные две точки равны: 2 и 3, сейчас покажу почему. 7-5 = 2. |2-5| = 3. Дальше числа либо будут повторятся, либо будут увеличиватся. Определим для числа б такие же 2 минимальные точки. 8-5=3. |3-5| = 2. Как можем заметить минимальные точки у числа а равны минимальным точка числа б. То есть мы с помощью текущих операции можем как и из числа а превратиться в число б, так и наоборот. Поэтому алгоритм работы прост, просто для каждого числа x в массиве а, в мапе будем хранить два значения, 1 минимальную точку, и вторую соответсвенно. mp[x%k]++, mp[k-(x%k)]++, в массиве б мы должны делать так же, но уже минусовать, делается это для того, чтобы проверить в конце, все ли значения в мпа равны значениям мпб, где мпа = значения минимальных точек в массиве а, мпб = значениям минимальных точек в массиве б. Если равны, то ответ Да, в противном случае ответ Нет. Стоит отметить, что если к равен 0, то никакие операции сделать мы не сможем, соответственно просто нужно отсортировать массив а и б, и проверить равны ли они, если да, то ответ Да, иначе ответ Нет.

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll t; cin >> t;
  while (t--){
    ll n,k; cin >> n >> k;
    vector<ll> a(n);
    vector<ll> b(n);
    map<ll,ll> mp;
    set<ll> st;
    for (ll i = 0;i<n;i++){
      cin >> a[i];
    }
    for (ll i = 0;i<n;i++){
      cin >> b[i];
      mp[b[i]]++;
    }
    if(k==0){
      sort(a.begin(),a.end());
      sort(b.begin(),b.end());
      if(a==b){
        cout << "YES" << endl;
      }else{
        cout << "NO" << endl;
      }
    }else{
    map<ll,ll> mpp;
    vector<pair<ll,ll>> ans;
    for (ll i = 0;i<n;i++){
      ll x = a[i];
      ll y = b[i];
      ans.pb({abs(x-k),x+k});
     // mpp[x+k]++;
     // mpp[abs(x-k)]++;
    }
    for (ll x: a){
      ll diff = x%k;
      if(diff<0){
        diff += k;
      }
      mpp[diff]++;
      mpp[k-diff]++;
      ll mn = min(diff,k-diff);
     // mpp[mn]++;
    }
    for (ll x: b){
      ll diff = x%k;
      if(diff<0){
        diff+=k;
      }
      mpp[diff]--;
      mpp[k-diff]--;
     // ll mn = min(diff,k-diff);
    // / mpp[mn]--;
    }
    ll cnt = 1;
    for (auto [x,y]: mpp){
      if(y!=0){
        cnt = 0;
        break;
      }
    }
    if(cnt==1){
      cout << "YES" << endl;
    }else{
      cout << "NO" << endl;
    }
    //cout << cnt << endl;
    
    
  }}
}

на каждой итерации мы можем закрепить s, затем находить уже непосредственно t, где s, t = двум вершинам, которые нас требует задача.

что такое листья дерева? и зачем они нам пригодятся на этой задаче?

Какой минимальный диаметр у n>=3?

Нас требуют выбрать две такие вершины s,t, затем проделать с ними несколько, возможно ноль операции. Что если мы зафиксируем вершину s, затем просто будем выбирать вершину t. Почему это делается? Дело в том, что выбирая на каждой итерации, две разные вершины каждый раз, не дает нам оптимального ответа в конце. Почему? Потому мы фактически выбираем разные вершины на каждом этапе, и отдаляем наш минимальный диаметр. А фиксируя вершину s, мы как бы можем достигнуть этого минимального диаметра минимальным количеством операции. Теперь создается вопрос. Что делать дальше? Допустим мы выбрали вершину s, и выбираем вершину t. Что если вершина t смежна с нашей вершиной? Тогда ничего не изменится, потому что нам не надо ничего делать. Эта вершина уже закреплена. А если эта вершина не смежна, то придется потратить 1 операцию, чтобы сделать ее смежной. Что нам это дает? Мы можем для каждой вершины, посчитать количество листьев дерева, которые смежны с этой вершиной. Почему? Потому что, делая это, мы как бы складываем наш ответ в уме, что мы потратим общее количество листьев — наше текущее количество листьев смежных с текущей вершиной, потому что надо потратить столько операции. А так как надо нам минимизировать ответ, то просто выбираем самый минимальный ответ. Однако тут нужно быть осторожнее, потому что для n <=2, ответ будет 0, так как мы не можем достичь уже минимального диаметра, соответственно нам нужно сделать 0 операции.

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll t; cin >> t;
  while (t--){
    ll n; cin >> n;
    vector<vector<ll>> gra(n+1);
    for (ll i = 0;i<n-1;i++){
      ll a,b; cin>> a >> b;
      gra[a].pb(b);
      gra[b].pb(a);
    }
    if(n==2){
      cout << 0 << endl;
      continue;
    }
    ll cnt = 0;
    ll mx = 0;
    ll tot = 0;
    for (ll i = 1;i<=n;i++){
      if(gra[i].size()==1){
        tot+=1;
      }
    }
    
    for (ll i = 1;i<=n;i++){
      ll cnt = 0;
      for (ll x: gra[i]){
        if(gra[x].size()==1){
          cnt++;
        }
      }
      mx = max(mx,cnt);
    }
    cout << tot-mx << endl;
    
  }
}

если x==y, где x, y = текущие a[i], b[i], то нам нужно делать какие то дополнительные операции?

если a[n-1] != b[n-1], то ответ Да, или Нет? Почему?

каково конечное значение нашей a[i+1]?

У нас есть два решение для этой задачи, но обе решения имеют одинаковую идею. Дело в том, что мы можем для каждой і сделать операцию с аі+1, то есть каждая аі в итоге равна либо аі либо бі. Первое решение: Мы сначало пройдемся слева направо, с 0 до н-1, и просто реализируем наши операции, если аі == bi то ничего не делаем, так как они уже равны. Затем справо налево сделаем то же самое, с n-1 до 0, но только уже с обновленными значениями аі. Если в конце а не равен б, то ответ Нет, иначе ответ Да. Второе решение: Идем справо налево, с n-1 до 0, наше значение аі+1 можем бть либо аі+1 либо бі+1 в итоге, а значит мы можем обновить аі с аі+1 либо с бі+1, так как аі+1 в итоге будет равна бі+1 по нашей идее. Если a[i]==b[i] or b[i]==a[i]xora[i+1] or b[i]==a[i]xorb[i+1] то ответ Да, иначен ответ Нет. Так же стоит отметить, что ответ не может быть Да, если последний элемент массива а не равен последнему элементу массива б, потому именно на этом индексе мы не можем сделать операцию. Это наше решение. Скажу сразу, решал я по второму решению.

~~~~~

include

include

include

include <bits/stdc++.h>

define ll long long

define pb push_back

using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll t; cin >> t; while (t--){ ll n; cin >> n; vector a(n); vector b(n); for (ll i = 0;i<n;i++){ cin >> a[i]; } for (ll i = 0;i<n;i++){ cin >> b[i]; } if(b[n-1]!=a[n-1]){ cout << "NO" << endl; continue; } bool opt = 0; ll cnt = 0; for (ll i = n-2;i>=0;i--){ ll x = a[i]^a[i+1]; ll y = a[i]^b[i+1]; if(b[i]==x || b[i]==y || a[i]==b[i]){ cnt++; } } if(cnt+1==n){ cout << "YES" << endl; }else{ cout << "NO" << endl; } //cout << cnt+1==n << endl; } }~~~~~

Сможем ли мы "разбить" число >30?

для x>=2 можно заметить некую закономерность, а вы заметили?

Для решения нужно использовать некую структуру f(x), где f(x) равна некому значению операции на x

В этой задача, как я уже и сказал, нужно заметить несколько деталей. Первая деталь, это закономерность, на операции с числами x>=2. Чтобы это заметить возьмем небольше число, допустим 3, и число 4 Давайте "разобьем" числа 3 и 4. 3: 1 2
1: 0 2: 1 1: 0 конечный ответ 3*1*2*1 1: 2 2: 1 3: 1 4: 1 2 3 1: 0 2: 1 1: 0 3: 1 2 1: 0 2: 1 1: 0 конечный ответ 4*1*2*1*3*1*2*1 1: 4 2: 2 3: 1 4: 1 Что же мы такое заметили? начиная от числа x>=2 количество 1 увеличиваеться на количество единиц в f(x-1). Или просто становиться 1<<((x-2)), где 1<<((x-2)) означает 2^(x-2). Так же и с двойкой, правда она становиться уже 2^(x-2-1) итак до того когда значение x-2-t не будет равна 0. Что это нам дает? Благодаря этому наблюдению мы можем быстро посчитать для некого x, f(x) тогда чтобы посчитать воспользуемся этим. f[0] = 1; f[1] = 1; for i in range(2,MXN): ** f[i] = i;** for (ll j = 0;j<i;j++): ** f[i]*=f[j]** Так мы и выяснили f(x). Но не будет ли это слишком долго для большого икс? Да, будет! Поэтому тут мы заметим еще одно наблюдение. Какая максимальная степень 2 допустимого числа? Это 30, верно? значит нам не нужно рассматривать число больше 30, потому что мы не можем разбить число больше 30, это будлет слишком много. Что мы сделаем? Мы сделаем так, если число больше 30 или если 1<<(x-1) больше к, то просто снизим к, и добавим числа от 0 до 30 обратно в массив а. Наверное вы хотите спросить, что же такое 1<<(x-1). Это третье наблюдение, которое тоже важно. Дело в том, что любое x имеет свой скажем так размер. Когда мы разбиваем число x, то его размер определяется так 1<<(x-1) это можно заметить с помощью первого наблюдения, когда мы разбивали числа x. Итоговый алгоритм таков, пока массив а не пуст и к больше 0, то находим минимальный элемент массива а, и делаем операцию с ней, определяем текущий length как length = 1<<(x-1). if (x<=30 && length<=k) ans*=f[x] ans%=MOD; k-=length; else ans*=x for i in range (0,30) a.push_back(i) и делаемм это рекурсивно пока одно из двух изначальных условии не разобьется. Получим наш ответ. Тут главное не забыть про работу с модулями, иначе можно получить неправильно ответ.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pb push_back
using namespace std;

const ll MOD = 1e9+7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll t; cin >> t;
    vector<ll> dp(40);
    dp[0] = 1;
    dp[1] = 1;
    for (ll i = 2;i<40;i++){
      dp[i] = i%MOD;
      for (ll j = 0;j<i;j++){
        dp[i] = dp[i]%MOD*dp[j]%MOD;
      }
    }
    

    while (t--) {
        ll n, k; cin >> n >> k;
        vector<ll> a(n);
        for (ll i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());
        reverse(a.begin(),a.end());
        ll sm = 1;
        while (k>0 && a.size()>=1){
          ll cur = a.back();
          a.pop_back();
          if(cur<=30 && (1<<(cur-1))<=k){
            k-=(1<<(cur-1));
            sm*=dp[cur];
            sm%=MOD;
          }else{
            sm*=cur;
            sm%=MOD;
            for (ll i = min(cur-1,30ll);i>=1;i--){
              a.pb(i);
            }
            k--;
          }
        }
        cout << sm << "\n";
    }
   // return 0;
}