Решение задачи Задоминированный подмассив с Codeforces

Без пояснения   Просмотров: 865

Назовем массив t задоминированным значением v в следующем случае.

Во-первых, массив t должен состоять хотя бы из 2 элементов. Теперь, давайте посчитаем количество вхождений каждого числа num в t и назовем данное значение occ(num). Тогда, t — задоминирована (числом v) тогда (и только тогда), когда occ(v)>occ(v′) для любого другого числа v′. Например, массивы [1,2,3,4,5,2], [11,11] и [3,2,3,2,3] задоминированы (числами 2, 11 и 3 соответственно), но массивы [3], [1,2] и [3,3,2,2,1] — нет.

Небольшая заметка: так как любой массив может быть задоминирован только одним числом, то мы можем не уточнять данное число и просто говорить, что массив либо задоминирован, либо нет.

Вам задан массив a1,a2,…,an. Определите его самый короткий задоминированный подмассив, либо скажите, что таких нет.

Подмассив массива a — это последовательная часть массива a, другими словами массив ai,ai+1,…,aj для некоторых 1≤i≤j≤n.

Код 

#include <bits/stdc++.h>
using namespace std;
char s[100005];
int main(){
	int T;
	cin >> T;
	while(T--){
		cin >> s+1;
		s[0]=0;
		for(int i=1;s[i];i++){
			if(s[i]!='?') continue;
			for(int j=0;j<=2;j++){
				char tt='a'+j;
				if(tt!=s[i-1]&&tt!=s[i+1]){
					s[i]=tt; break;
				}
			}
		}
		int f=1;
		for(int i=1;s[i+1];i++){
			if(s[i]==s[i+1]) {
				f=0; break;
			}
		}
		if(f)cout << s+1 << endl;
		else cout << -1 << endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp