Организация вывода в множествах

Первый способ, позволяющий вывести все элементы множества:

for (const auto &i:myset)

cout << i << endl;

Другой способ работает через указатели

set<int>::iterator it;

cout << "Множество содержит:";

for (it=myset.begin() ; it != myset.end(); it++ )

cout << " " << *it;

Если необходимо вывести часть элементов множества

set<int>::iterator it;

int n;

cin >> n;

cout << "Первые " << n << " элементов множества:";

for (it = myset.begin() ; it != myset.end() && n; it++, n--)

cout << " " << *it;

В тех случаях, когда необходимо вывести все элементы, за исключением последнего, достаточно перед циклом n заменить на:

n = myset.size() - 1;

Но наиболее простым из всех способов вывода элементов множества является использование итераторов. Рассмотрим это на примере:

#include<iostream>

#include<set>   // заголовочный файл множеств и мультимножеств

#include <iterator> //итераторы

using namespace std;

int main() {

set<int> mySet; // объявили пустое множество

           // добавляем в него элементы

mySet.insert(100);

mySet.insert(12);

mySet.insert(4);

copy(mySet.begin(), mySet.end(),

     ostream_iterator<int> (cout, " "));

}

Нужно только указать, какой тип данных используется в множестве для передачи в ostream.

Операции над множествами

Пересечение

Для простой проверки пересечения двух множеств работает функция set_ intersection, описаннаяв библиотеке algorithm

Реализация пересечения двух множеств целых чисел A и B

#include <bits/stdc++.h>

using namespace std;

int main () {

set<int>a, b;         // множества целых чисел A и B

int n, m, i, x;

cin >> n >> m;        // количество элементов в A и B

for (i = 0; i < n; i++){ // ввод элементов первого множества

   cin >> x;

   a.insert(x);

}

for (i = 0; i < m; i++){ // ввод элементов второго множества

   cin >> x;

   b.insert(x);

}

vector<int> v(max(n,m)); // в этот вектор запишем результат

vector<int>::iterator it; // итератор для элементов вектора

it=set_intersection (a.begin(), a.end(),

                    b.begin(), b.end(), v.begin());                                          

v.resize(it - v.begin()); //отбрасываем лишние эл-ты вектора

for (it=v.begin(); it!=v.end(); ++it)

   cout << *it << ' ';

}

Для массивов это выглядит полностью аналогично. Но в пересечении set_ intersection могут появляться дублирующиеся элементы.

#include <iostream>

#include <algorithm> // std::set_intersection, std::sort

#include <vector>  // std::vector

#define SIZE 10000

using namespace std;

int main () {

int a[SIZE], b[SIZE], n, m, i;

cin >> n >> m;            //число элементов в массивах

for(i = 0; i < n; i++) cin >> a[i]; //ввод элементов массива A

for(i = 0; i < m; i++) cin >> b[i]; //ввод элементов массива B

 

vector<int> v(max(n,m));  //вектор – результат пересечения

vector<int>::iterator it; //итератор элементов вектора

 

sort (a, a + n);

sort (b, b + m);

 

it = set_intersection (a, a + n, b, b + m, v.begin());

v.resize(it - v.begin());

 

for (it = v.begin(); it != v.end(); ++it)

     cout << *it << ' ';

}

Реализовать при помощи STL операцию пересечения двух множеств можно и без set_ intersection. Применим вместо этого контейнер map – ассоциативный массив. Если элемент входит в первый набор, присвоим данному индексу значение 1. Если он встречается и во тором наборе тоже, присвоим значение 2.

#include <bits/stdc++.h>

using namespace std;

int main () {

map<int, int> cnt;    // ассоциативный массив

map<int, int>::iterator it; // и его итератор

 

intn, m, i, x;

scanf("%d%d", &n, &m); // количество элементов в наборах

for (i=0; i<n; i++){  // ввод первого набора

   scanf("%d", &x);

   cnt[x] = 1;

}

for (i=0; i<m; i++){  // ввод второг онабора

   scanf("%d", &x);

   if(cnt[x]) cnt[x] = 2;

}

for (it = cnt.begin(); it != cnt.end(); ++it)   //вывод

   if(it->second == 2) printf("%d ", it->first);

}

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

Задача №174.  Пересечение множеств(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

Входные данные

В первой строке входного файла INPUT.TXT записано через пробел два целых числа N и М (1 ≤ N, М ≤ 300 000) — количество элементов первого и второго наборов, соответственно. В следующих строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами или символами конца строки. Каждое из этих чисел попадает в промежуток от 0 до 10⁵.

Выходные данные

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

Пример

INPUT.TXT	OUTPUT.TXT
11 6 2 4 6 8 10 12 10 8 6 4 2 3 6 9 12 15 18	6 12

Решение

Главную сложность в задаче представляют ограничения. Даже возможностей STL-контейнеров, таких как map или set с их автоматической сортировкой данных окажется недостаточно для того, чтобы обработка двух наборов суммарно составляющих полмиллиарда целых чисел, уложилась в 1 сек. Вместо этого заведём массив на 10⁵ индексов, каждому элементу из которых будем присваивать 1 – если индекс встретился в первом наборе и 2 – если встретился в обоих.

Это не только быстрее само по себе, но и избавляет нас от необходимости упорядочивать получившийся набор.

Для ускорения обработки такого большого объема данных используем библиотеку stdio вместо потокового ввода-вывода.

#include <stdio.h>

int a[100001]={0,}, n, m, x;

int main () {

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

scanf("%d%d", &n, &m);

for (; n--;){        //считывание первого набора

     scanf("%d", &x);

     a[x] = 1;

}

for (; m--;){        //считывание второго набора

     scanf("%d", &x);

     if(a[x]) a[x] = 2; //проверка, было ли число в первом

}

for(x = 0; x<100001; x++) //вывод результата

     if(a[x] == 2) printf("%d ", x);

}

Задачи с множествами

Задача №175.  Баллы

(Время: 1 сек. Память: 16 Мб)

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

Входные данные

В первой строке содержатся натуральные числа N и K (N, K ≤ 200 000) – соответственно количество студентов, подлежащих аттестации, и число запросов декана об успеваемости студентов.

Во второй строке находятся N целых чисел a_i. Эти числа - аттестационные баллы студентов.

В третьей строке располагаются K чисел b_i, определяющие искомый балл. (0 ≤ a_i, b_i ≤ 2³²)

Выходные данные

Выведите для каждого из K запросов через пробел слово «YES», если студент с таким баллом есть, и «NO» в противном случае.

Примеры

№	Ввод	Вывод
1	3  4 1  6  9 7  9  10  1	NO  YES  NO  YES
2	2  2 1  2 1  3	YES NO

Решение

#include <iostream>

#include <set>

typedef long long lol;    // 2^32 не помещается в int

using namespace std;

int main() {

lol n, k, x;

cin >> n >> k;

set<lol> c;           // множество баллов студентов

while(n--){           // ввод оценок студентов

   cin >> x;

   c.insert(x);

}

while(k--){           // запросы декана

   cin >> x;

   cout << (c.count(x) ? "YES" : "NO") << ' ';

}

}

Задача №176.  Циклические сдвиги

Сколько различных строк можно получить из строки S с помощью циклического сдвига на один или несколько символов влево?

Например, из строки abc можно получить три строки: bca, cab, abc

Входные данные

Единственная строка латиницей, не содержащая пробелов и других стоп-символов.

Выходные данные

Одно число – количество различных строк, которое можно получить при помощи циклических сдвигов исходной строки.

Пример

Ввод	Вывод
abbaabbaabba	4

Решение

Удобнее всего будет получать строки, получающиеся циклическим сдвигом исходной, если к исходной строке добавить саму себя, а из полученной строки брать подстроки длины l, где l–длина исходной строки.

Например, для строки “abc” получим “abcabc”, а затем будем поочередно брать из неё подстроки длины 3. Все полученные подстроки поместим во множество.

#include <iostream>

#include <set>  // заголовочный файл множеств и мультимножеств

using namespace std;

int main(){

set<string> mySet; // объявили пустое множество

string s;

cin >> s;

int l = s.length();

s += s;     // удвоили строку s

for(int i = 0; i < l; i++)

   mySet.insert(s.substr(i, l));

cout << mySet.size();

}

Задача №177.  Строки (acmp.ru)

Циклическим сдвигом строки s называется строка s_ks_k+1s_k+2…s_|s|s₁s₂…s_k-1 для некоторого k, здесь |s| - длина строки s. Подстрокой строки s называется строка sisi+1…sj-1sj для некоторых i и j. Вам даны две строки a и b. Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b.

Входные данные

Первая строка входного потока содержит строку a (1 ≤ |a| ≤ 1000). Во второй строке записана строка b (1 ≤ |b| ≤ min(100, |a|)). Обе строки состоят только из символов латинского алфавита и цифр.

Выходные данные

Выведите целое число – ответ на задачу.

Примеры

№	Ввод	Вывод
1	abcabc abc	4
2	abcabc acb	0
3	aaaaaaa aa	6
4	aAaa8aaAa aAa	4

Решение

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

#include <bits/stdc++.h> //подключение стандартных библиотек

using namespace std;

int main() {

set<string> st;  //множество циклических сдвигов

string a, b;

cin >> a >> b;

int lena = b.size(), lenb = a.size(), i, count = 0;

b += b;

for(i = 0; i < lena; i++)

   st.insert(b.substr(i, lena));

for(i = 0; i <= lenb - lena; i++)

   if(st.count(a.substr(i, lena)))count++;

cout << count;

}

Задача №178.  Спамер

(Ограничение времени: 1.0 секунды. Ограничение памяти: 64 Мб)

Среди наших знакомых есть известный спамер. В конце каждого контеста он сабмитит свои неправильные решения со скоростью пулемёта. Кроме того, он ещё и ведёт нечестную игру, всегда используя по несколько отладочных аккаунтов. Жюри наконец-то решило дисквалифицировать спамера. Для этого они сначала хотят определить все его отладочные аккаунты. Известно, какие команды сабмитили свои решения в последние 10 минут контеста. Ваша задача — найти все отладочные аккаунты спамера. Жюри считает аккаунтами спамера всех, кто сабмитил решения больше одного раза в последние 10 минут.

Входные данные

В первой строке записано число N — количество сабмитов в последние 10 минут (0 ≤ N ≤ 100). Следующие N строк содержат названия команд, сабмитивших решения. Названия состоят только из строчных латинских букв и цифр. Длина названий не превосходит 30 символов.

Выходные данные

Выведите все аккаунты, под которыми, по мнению жюри, играет спамер. Порядок вывода не важен.

Пример

Ввод	Вывод
11 naucoder iceman abikbaev abikbaev petr abikbaev abikbaev x abikbaev acrush x	x abikbaev

Источник задачи: XIII командный чемпионат школьников Свердловской области по программированию (14 октября 2006 года)

Решение

Создадим два множества – userlistи spamlist. В spamlistбудет добавляться пользователь, который уже имелся в userlistпри попытке новой отправки решения

#include <iostream>

#include <iterator>

#include <set>

using namespace std;

int main() {

set<string> userlist, spamlist;

int n;

cin >> n;

string user;

for (; n; n--) {

cin >> user;

     if (userlist.count(user)) spamlist.insert(user);

userlist.insert(user);

}

copy(spamlist.begin(), spamlist.end(),

     ostream_iterator<string> (cout, "\n"));

}

Задача №179.  Развлечения с измерителем (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Дима обнаружил у папы на столе специальный чертежный прибор, похожий на циркуль-измеритель. Измеритель отличается от обычного циркуля тем, что в обеих его ножках находятся иголки (у обычного циркуля в одной ножке находится иголка, а в другой – грифель).

Кроме измерителя Дима нашел на столе клетчатый лист бумаги, в углах некоторых клеток которого были нарисованы точки. Так как измеритель служит для измерения расстояний, то Дима решил измерить все попарные расстояния между всеми точками на листе бумаги.

Ваша задача - написать программу, которая по координатам точек определит, сколько различных расстояний встречается среди расстояний, которые измерил Дима.

Входные данные

Первая строка содержит число n – количество точек (2 ≤ n ≤ 50). Следующие n строк содержат по два целых числа – координаты точек. Координаты не превышают 10⁴ по абсолютной величине.

Выходные данные

На первой строке выведите k – количество различных расстояний, которые измерил Дима. Следующие k строк должны содержать по одному вещественному числу – сами расстояния. Расстояния должны быть выведены в возрастающем порядке. Каждое число должно быть выведено с точностью не менее чем 10^-9.

Пример

Ввод	Вывод
4 0  0 1  1 1  0 0  1	2 1.0 1.414213562373

Решение

#include <iostream>

#include <iomanip>

#include <cmath>

#include <set>

#include <iterator>

using namespace std;

 

int main () {

int n, x[50], y[50], i, j;

double d;

set<double> s;

cin >> n;

for(i = 0; i < n; i++){

   cin >> x[i] >> y[i];

      for(j = 0; j < i; j++){

       d = sqrt((x[i]-x[j])*(x[i]-x[j])

               + (y[i]-y[j])*(y[i]-y[j]));

       s.insert(d);

   }

}

cout << s.size() << endl << fixed << setprecision(10);

copy(s.begin(), s.end(),

ostream_iterator<double> (cout, "\n"));

}

Задача №180.  Экзамен по истории

(Ограничение времени: 1.5 секунды. Ограничение памяти: 64 МБ)

Будем справедливы: сессия ставит задачи не только студентам, но и преподавателям. Любой преподаватель обучает немалое количество студентов, а ведь каждого надо еще и проверить. Поэтому один из преподавателей решил принимать экзамен по истории по такой упрощённой процедуре: студент записывает все известные ему «исторические» даты (достаточно, чтобы он написал только года, но, конечно, мог объяснить, чем замечательна та или иная дата). Преподаватель же держит перед глазами список дат, которые студент должен знать. Для оценки знаний студента преподаватель подсчитывает количество чисел в списке студента, которые также есть в списке преподавателя. В зависимости от полученного числа и выставляется итоговая оценка.

Вы должны оказать посильную помощь в автоматизации этого процесса, разработав программу для подсчёта количества совпадений в списках студента и преподавателя.

Входные данные

В первой строке содержится число N — количество записей в списке преподавателя. 1 ≤ N ≤ 15000. Затем идет N строк, содержащих список преподавателя, по одной дате в строке. Записаны только года. Каждый год — целое число в пределах от 1 до 10⁹. В следующей после списка строке содержится число M — количество записей в списке студента, 1 ≤ M ≤ 15000. Затем также M строк с датами (записаны только года, каждый год — целое число в пределах от 1 до 10⁹). В списке как студента, так и преподавателя даты могут повторяться.

Выходные данные

Вы должны вывести одно число — количество чисел во втором списке, которые также содержатся в первом.

Пример

Ввод	Вывод
3 1054 1492 1492 4 1492 65536 1492 100 2	2

Решение

Сохраним список дат преподавателя и студента в мультимножествах, а затем воспользуемся операцией пересечения множеств, описанной в библиотеке algorithm.

#include <iostream>

#include <set>       // multiset

#include <algorithm> // set_intersection, inserter

using namespace std;

int main() {

multiset<int> teacher, student, common;

int n, date;

cin >> n;

for (; n; n--) {

   cin >> date;

   teacher.insert(date);

}

cin >> n;

for (; n; n--) {

   cin >> date;

   student.insert(date);

}

set_intersection(teacher.begin(), teacher.end(),

               student.begin(), student.end(),

               inserter(common, common.end()));

cout << common.size()<<"\n";

}

Задача №181.  Jивой Jурнал(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Программист Саша участвует в создании блог-сервиса Jивой Jурнал. Планируется, что этот сервис будет предоставлять гораздо больше возможностей, чем известный всем LiveJournal. В настоящее же время проблему составляет реализация всех базовых возможностей LiveJournal’а. Одной из таких возможностей является поддержка списков друзей для пользователей.

Заданы: список пользователей, являющихся друзьями данного пользователя, и список пользователей, у которых данный пользователь содержится в списке друзей.

Необходимо получить список друзей данного пользователя (Friends), список его взаимных друзей (MutualFriends), и список тех пользователей, у кого данный пользователь содержится в списке друзей, но которые не являются его взаимными друзьями (AlsoFriendof).

Входные данные

Первая строка содержит число n (0 ≤ n ≤ 200) друзей данного пользователя. Следующие n строк содержат каждая по одному имени пользователя, который является другом данного. (n + 2)-ая строка содержит число m (0 ≤ m ≤ 200) пользователей, у которых данный содержится в списке друзей. Далее заданы имена пользователей, у которых данный находится в списке друзей. Эти пользователи заданы в том же формате, что и друзья данного.

Имена пользователей - строки длиной не более 20 символов, содержащие только строчные буквы латинского алфавита и символы тире ("-"). Каждый пользователь указан не более одного раза в каждом из списков.

Выходные данные

Выведите список друзей данного пользователя (Friends), список его взаимных друзей (Mutual Friends), и список тех пользователей, у кого данный пользователь содержится в списке друзей, но которые не являются его взаимными друзьями (Also Friend of). В каждом списке пользователи должны быть отсортированы по алфавиту. Следуйте формату, приведенному в примерах.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	3 vasya-pupkin bill-hates ivan-ivanov 2 vasya-pupkin destroyer	Friends: bill-hates, ivan-ivanov, vasya-pupkin Mutual Friends: vasya-pupkin Also Friend of: destroyer
2	0 0	Friends: Mutual Friends: Also Friend of:

Решение

Данная задача с применением STL-контейнера для множеств решается достаточно тривиально. Единственную сложность представляет организация вывода множеств.

#include<iostream>

#include<set>

using namespace std;

void write(set<string> myset){       //выводмножества

int t = myset.size()-1;

set<string>::iterator it;

for (it = myset.begin(); it != myset.end(); it++, t-- ){

   cout << *it << (t ? ", " : "");

}

cout << endl;

}

int main(){

set<string> friends, mutual, also;

int n;

string name;

cin >> n;

while(n--){                 //заполнение списка пользователя

   cin >> name;

   friends.insert(name);

}

cin >> n;

while(n--){                 //обработка списков его друзей

   cin >> name;

   if (friends.count(name)) mutual.insert(name);

   else also.insert(name);

}

cout << "Friends: ";

write(friends);

cout << "Mutual Friends: ";

write(mutual);

cout << "Also Friend of: ";

write(also);

}

 

Битовые множества

Битовоемножествопредставляет собой контейнер, в котором могут храниться битовые последовательности фиксированной длины. Можно сказать, что оно служит представлением подмножеств фиксированного множества (в математическом смысле), каждому элементу которого соответствует один бит в определенной позиции. Единичный бит означает, что элемент принадлежит подмножеству, нулевой — что он не входит в данное подмножество.

Биты в bitset плотно упакованы, так что информация хранится очень экономно. Однако минимальный физический размер bitset равен 4 байтам — размеру int.