| {quote} |
| set - множество - хранит упорядоченные по возрастанию элементы в виде дерева каждый ровно один раз |
| multiset - мультимножество - хранит упорядоченные по неубыванию элементы в виде дерева |
| каждый элемент может встречаться несколько раз |
| {quote} |
| Объявление |
| {quote} |
| set<string> s; // множество строк, строки упорядочены по возрастанию |
| // добавление одинаковых игнорируется |
| // каждое строка может встречаться один раз |
| multiset<int, greater<int> > s; // множество чисел, числа упорядочены по убыванию |
| // одинаковые числа добавляются |
| // каждое число может встречаться несколько раз |
| {quote} |
| Использование |
| {quote} |
| s.insert(t) // вставить элемент t в множество s |
| s.find(t) // найти t в s |
| проверить, есть ли элемент t во множестве s |
| нет, если s.find(t)==s.end() |
| есть, если s.find(t)\!=s.end() |
| s.end - адрес "сразу за последним элементом " |
| s.erase(s.find(h)) // найти в s элемент h и удалить его |
| s.erase(h) // в multiset удаляет все элементы со значением h |
| s.clear() // удалить все элементы из s |
| s.empty() // множество пустое? |
| s.size() // количество элементов в s |
| |
| \*s.begin() // взять первый - наименьший элемент из s (если элементы хранятся по возрастанию) |
| // - наибольший элемент из s (если элементы хранятся по убыванию) |
| \*s.rbegin() // взять последний |
| \*--s.end() // взять последний - наибольший элемент из s (если элементы хранятся по возрастанию) |
| // - наименьший элемент из s (если элементы хранятся по убыванию) |
| // s.end - адрес "сразу за последним элементом" |
| {quote} |
| Заметим, что первый, последний элементы и empty берутся за O(1), |
| |
| а insert, find, erase выполняются за O(LogN) |
| {code:title=part.cpp|borderStyle=solid} |
| set <pair< pair<int,int> , pair<int,int> > > s; // множество четвёрок чисел |
| set <pair< pair<int,int> , pair<int,int> > >::iterator is; // итератор по множеству |
| for (is=s.begin(); is!=s.end(); is++) |
| for (is=s.begin(); is!=s.end(); is++) |
| { |
| int x1,y1,x2,y2; |
| x1=is->first.first; // обращение к элементам четвёрки |
| y1=is->first.second; // с помощью итератора |
| x2=is->second.first; |
| y2=is->second.second; |
| {code} |
| Задача из курса "Методы алгоритмизации" |
| Олимпиады по информатике\Стек\07_Rub6 - "aPhone |
| [http://dl.gsu.by/task.jsp?nid=256579&cid=15] |
| |
| Решение |
| |
| Можно симулировать процесс, описанный в условии задачи. |
| |
| А можно заметить, что если сначала все строки прочитать, |
| а потом обрабатывать их с конца, то задача может существенно упроститься |
| Список строк пустой |
| Пока не обработали все строки |
| - если текущей строки нет, |
| Тогда выводим её, и заносим её в список |
| иначе пропускаем |
| Довыводим <Empty> если нужно |
| |
| Для того, чтобы не писать самим процедуры |
| добавления строки в список проверки и проверки наличия строки в списке |
| (а также для ускорения этих процедур) можно |
| определить тип множество строк (set<string> s) |
| и использовать стандартные функции. |
| s.insert(t) - вставить строку t в множество s |
| s.find(t) - проверить, есть ли строка t во множестве s |
| есть, если s.find(t)==s.end() |
| {code:title=prog.cpp|borderStyle=solid} |
| #include <bits/stdc++.h> |
| using namespace std; |
| string x[1000]; |
| set<string> s; |
| int main() |
| { |
| freopen("aphone.in","r",stdin); |
| freopen("aphone.out","w",stdout); |
| int n,m,i; |
| cin >> m >> n; |
| for (i=0; i<n; i++) cin >> x[i]; |
| for (i=n-1; (i>=0) && (m>0); i--) |
| if (s.find(x[i])==s.end()) |
| { s.insert(x[i]); cout << x[i] << endl; m--;}; |
| for (i=0; i<m; i++) cout << "<Empty>" << endl; |
| } |
| {code} |
| Подробнее о set |
| [http://informatics.mccme.ru/mod/book/view.php?id=492&chapterid=215] |