Решение задачи Лиса и имена с Codeforces

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

Лиса Ciel собирается опубликовать статью по ЛИС (Лисооперируемым Интеллектуальным Системам). Она слышала, что список авторов научной статьи всегда сортируется в лексикографическом порядке.

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

Лиса хочет знать, существует ли такой порядок букв латинского алфавита, что имена авторов предлагаемой ею статьи следуют в лексикографическом порядке. Если да, то требуется также найти любой такой порядок.

Лексикографический порядок определяется следующим образом. Мы сравниваем s и t, сперва находя крайнюю левую позицию с различающимися символами: s i ≠ t i. Если такой позиции нет (то есть, s — это префикс t или наоборот), то более короткая строка меньше. В противном случае мы сравниваем символы s i и t i согласно их порядку в алфавите.

Код 

#include<bits/stdc++.h>
using namespace std;

vector<int> g[26];
int vis[26];
stack<char> order;

void dfs(int i){
	if(vis[i] == 1){
		cout << "Impossible" <<  endl;
		exit(0);
	}
	if(vis[i] == 2) return;
	vis[i]=1;
	for(int j:g[i]) dfs(j);
	vis[i]=2;
	order.push(i+'a');
}

int main(){
	int n; cin >> n;
	string s1, s2; cin >> s2;
	for(int i=1; i<n; ++i){
		s1 = s2;
		cin >> s2;
		for(int j=0; j<s1.length(); ++j){
			if(j == s2.length()){
				cout << "Impossible" << endl;
				exit(0);
			}
			if(s1[j] != s2[j]){
				g[s1[j]-'a'].push_back(s2[j]-'a');
				break;
			}
		}
	}
	for(int i=0; i<26; ++i) dfs(i);
	while(!order.empty()){
		cout << order.top();
		order.pop();
	}
	cout << endl;
}

         

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




Комментарии

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


© 2020 HSECODES [email protected] Карта сайта