Всем привет! Сегодня я бы хотел сделать разбор на недавно прошедший контест. Если в разборе что-то непонятно, то можете смело смотреть код)
Полное решение: Давайте заметим, что сделав операцию для какого-то конкретного числа, то мы захватим сразу все его вхождения.
Дальше заметим, что для каждого такого числа нужно как минимум 2 операции, кроме первой операции вначале, поэтому у нас получится что-то вроде 2*cnt-1,
где cnt — кол-во уникальных чисел.
Сложность: O(n).
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
void bruh(){
ll n; cin >> n;
vector<ll> a(n);
for (ll &x: a){
cin >> x;
}
set<ll> st;
for (ll x: a){
st.insert(x);
}
ll sz = st.size();
cout << sz*2-1 << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >>t;
while (t--){
bruh();
}
}
Полное решение: Доран может ходить по диагонали, а значит Доран может захватить площадь размера 3*3, по Круга может ходить только вперед, назад, вниз и вверх. Это дает нам понять, что условие конечное, т.е в какой-то момент Доран настигнет Кругу.
Теперь определим 3 случая:
1 Когда они находятся на одной и той же строке, т.е rk==rd. В этом случае ответ зависит от позиции Круги. Если ее столбец >= столбец Дорана, то единственное место куда она может побежать — n. Поэтому ответ будет n-ck+abs(cd-ck). Иначе ответ: ck+abs(cd-ck), т.к единственное место куда она может пойти это граница 1.
2 Когда они находятся на одном и том же столбце, т.е ck==cd. Т.к n == n, ответ не сильно отличается от 1 случая, а именно: n-rk+abs(rd-rk), для первого случая, и rk+abs(rk-rd) для второго.
3 Когда оба из них не пересекаются, ни столбцом, ни строкой, и находятся в разных местах. Тут мы комбинируем условия из предыдущих случаев, а именно если столбец Дорана находится раньше, чем столбец Круги, то она побежит направо к границе n, ans1 =abs(cd-n), иначе она побежит налево, ans1 = abs(cd-0). Также и со строкой: ans2 = abs(rd-n), ans2 = abs(rd-0) для второго случая.
Выводим наш ответ.
Сложность: O(n).
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
void bruh(){
ll n,rk,ck,rd,cd; cin >> n >> rk >> ck >> rd >> cd;
ll ans = 0;
if(rk==rd){
if(ck>=cd){
ans = n-ck+abs(cd-ck);
}else{
ans = ck+(abs(cd-ck));
}
}else if(ck==cd){
if(rk<rd){
ans = (rk+abs(rd-rk));
}else{
ans = n-rk+abs(rd-rk);
}
}
else{
ans = max(abs(cd-(ck>=cd?n: 0)),abs(rd-(rk>=rd?n: 0)));
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >>t;
while (t--){
bruh();
}
}
Полное решение: В задаче сказано, что числа в массиве могут быть только двух видов: 0 и 1.
А значит возможные комбинации такие:
[1 1 1] [1 0 1] [1 0 0] [0 0 0] [0 1 0] [0 1 1]
Здесь можно заметить, что только в двух случаях ответ может быть 2, а именно если нет таких индексов, что a[i]==a[i+1].
Пример:
Пусть a = [1 0 1 0 1 0] . Как можем видеть у нас нет вышеупомянутых индексов, а значит к ответу добавляется 2. Можно доказать, что больше 2 не может быть.
Также второе наблюдение заключается в том, что ответ больше 1 может быть только на 1 операции, дальше неважно есть ли вышеупомянутые индексы, ответ будет не больше 1. Поэтому остается только посчитать есть ли на отрезке от l, r такие индексы, если есть хоть один такой индекс, то ответ никогда не будет больше 1, иначе это возможно. Ответ можем посчитать так: (r-l+1)/3, если есть такие индексы, иначе ответ ((r-l+1)/3-1)+2.
Стоит упомянуть, если на отрезке кол-во 0 или кол-во 1 не делится на 3, то в итоге разбиение и выполнение операции невозможно, поэтому можно сразу вывести -1.
Сложность: O(q).
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
void bruh(){
ll n,k; cin >> n >> k;
vector<ll> a(n);
for(ll &x: a){
cin >>x;
}
vector<ll> one(n+1,0);
vector<ll> zero(n+1,0);
for (ll i = 1;i<=n;i++){
one[i] = one[i-1]+(a[i-1]==1);
zero[i] = zero[i-1]+(a[i-1]==0);
}
vector<ll> d(n+1);
d[0] = 0;
for (ll i = 1;i<n;i++){
if(a[i]==a[i-1]){
d[i] = d[i-1]+1;
}else{
d[i] = d[i-1];
}
}
d[n] = d[n-1];
ll ans1 = 0;
vector<pair<ll,ll>> track;
for (ll i = 0;i<k;i++){
ll l, r; cin >> l >> r;
track.pb({l,r});
}
for (ll i = 0;i<k;i++){
ll l = track[i].f; ll r = track[i].s;
ll bs1 = (l==0? 0: one[l-1]);
ll bs2= (l==0? 0: zero[l-1]);
ll opt1 = one[r]-one[l-1];
ll opt2 = zero[r]-zero[l-1];
if(opt1%3!=0 || opt2%3!=0){
cout << -1 << endl;
}else{
ll ans = (r-l+1)/2;
if(l+1<=r && (d[r-1]-d[l-1])>0){
cout << (r-l+1)/3 << endl;
}else{
cout << ((r-l+1)/3-1)+2<< endl;
}
}
// auto li = lower_bound(all(one),l);
// auto ri = upper_bound(all(one),r);
// if(li==one.end() || li==ri){
// cout << -1 << endl;
// }else{
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >>t;
while (t--){
bruh();
}
}
