Решение задачи "Сломанная клавиатура" с Codeforces

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


Недавно Поликарп заметил, что некоторые кнопки на его клавиатуре неисправны. Клавиатура Поликарпа содержит 26 кнопок (по кнопке на каждую букву латинского алфавита). Каждая кнопка либо работает исправно, либо сломана.

Для проверки исправности клавиатуры Поликарп понажимал на некоторые кнопки и строка s появилась на экране. Когда Поликарп нажимает на кнопку c, происходит одно из двух событий:

если кнопка работает исправно, то в конец строки просто добавляется символ c;
если кнопка работает неисправно, то ровно два символа c добавляется в конец строки.
Например предположим, что кнопки a и c работают корректно, а кнопка b неисправна. Если Поликарп нажмет на кнопки в порядке a, b, a, c, a, b, a, то строка будет меняться следующим образом: a → abb → abba → abbac → abbaca → abbacabb → abbacabba.

Вам задана строка s, которая появилась на экране после нажатия некоторых кнопок. Помогите Поликарпу определить, какие кнопки точно работают корректно (что означает, что эта строка не могла появиться на экране, если бы эти кнопки работали некорректно).

Обратите внимание, что кнопки не могут ломаться или чиниться в процессе набора текста. Каждая кнопка изначально либо неисправна, либо работает корректно.

Код

#include <bits/stdc++.h>
using namespace std;
void solve(){
	string s;
	cin>>s;
	s+='0';
	s='0'+s;
	set <char> ans;
	for(int i=1; i+1<s.size(); i++){
		int j=i;
		while(s[j+1]==s[i]) j++;
		if((j-i+1)%2) ans.insert(s[i]);
		i=j;
	}
	for(auto c: ans) cout<<c;
	cout<<'\n';
}
int main(){
	int t;
	cin>>t;
	while(t--) solve();
}

         

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


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

Комментарии

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