Областная олимпиада по информатике 2019 год
Задача D. Чередующие тренировки
Алан очень сильно любит решать задачи по программированию и играть шахматы. В обоих сферах он хочет преуспеть, стать легендарным гроссмейстером. Айдос как опытный тренер предложил ему у него потренироваться.
У Айдоса определенное расписание на каждый из следующих $n$ дней. В каждый из дней Айдос тренирует только один вид, либо программирование, либо шахматы. Алан хочет выбрать несколько подряд идущих дней для тренировки. Также Алан заметил, что если два дня подряд тренироваться в одной и той же сфере, то он устает, т.е. Алану надо чередовать шахматы и программирование. Помогите Алану выбрать максимальное количество подряд идущих дней так, чтобы он за этот период не устал тренироваться.
Подзадача 1: 2 тестовых примера из условия
Подзадача 2: $n <= 3$. 13 тестов
Подзадача 3: $n <= 100$. 5 тестов
Подзадача 4: $n <= 5000$. 12 тестов
Подзадача 5: $n <= 200000$. 18 тестов
4 0 1010Ответ
4Вход
5 3 01011 1 3 2 5 4 5Ответ
3
Комментарий/решение:
Почему Ошибка Исполнения?
#include <bits/stdc++.h>
using namespace std;
int tl[200005];
int main(){
int n,m;
cin>>n>>m;
string s;
cin>>s;
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
if(l>r){
swap(l,r);
}
tl[l]+=1;
tl[r+1]+=-1;
}
int rev=0;
for(int i=1;i<=n;i++){
rev+=tl[i];
if(rev%2==1){
if(s[i-1]=='0')s[i-1]='1';
else s[i-1]='0';
}
}
int mx=1,cnt=1;
for(int i=1;i<s.size();i++){
if(s[i]!=s[i-1]){
cnt++;
}
else{
mx=max(cnt,mx);
cnt=1;
}
}
mx=max(cnt,mx);
cnt=1;
cout<<mx;
}
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.