| | {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] |
