| |  | *Краткая справка о map* |
| | |
| | | *Краткая справка о map*\\ |
| | {quote} |
| | map<int, int> cou; // Объявление cou типа "отображение числа на число" |
| | // Для каждой x координаты массив cou |
| | // будет содержать, сколько было различных точек с такой x-координатой |
| | |
| | if (cou\[x\] == 0) // проверить есть ли х в cou (==0 значит нет) |
| | |
| | cou\[x\] = cou\[x\] + 1; // инкрементировать значение по ключу x |
| | cou\[x\] = cou\[x\] - 1; // декрементировать значение по ключу x |
| | |
| | cou.clear(); // инициализируем map нулями |
| | |
| | map<int, int> m; |
| | m.size() // количество элементов, которые заносились в map |
 | | m.erase(\x); // удалить элемент из map элемент с индексом x |
| | | m.erase( x ); // удалить элемент из map элемент с индексом x |
| | // только после этой операции size уменьшается на 1 |
| | |
| | maxp=m.begin()->first; // максимальный индекс |
| | maxk=m.begin()->second; // значение по максимальному индексу |
| | |
| | minp=m.rbegin()->first; // минимальный индекс |
| | mink=m.rbegin()->second; // значение по минимальному индексу |
| | |
| | map<int,int>::iterator im; // итератор |
| | im=m.begin(); |
| | maxp=im->first; |
| | maxk=im->second; |
| | |
| | map<int,int> H; |
| | map<int,int>::reverse_iterator im; // объявление обратного итератора для map |
| | for (im=H.rbegin(); im\!=H.rend(); im++) |
| | |
| | map<int, pair <int,int> > BD; // "отображение числа на пару чисел" |
| | map<int, pair <int,int> >::iterator im; // объявление итератора для map |
| | |
| | BD\[A\]=make_pair(B,kk); // число A отображается на пару B,kk |
| | {quote}\\ |
| | \\ |
| | \\ |
| | {code:title=vivod.cpp|borderStyle=solid} |
| | // вывод содержания map вместе номерами в map |
| | i0=1; |
| | for (im=BD.begin(); im!=BD.end(); im++) |
| | { |
| | Mon =(*im).first; |
| | MaxM=(*im).second.first; |
| | nom =(*im).second.second; |
| | cout << i0 << ' ' << Mon << ' ' << MaxM << ' ' << nom << endl; |
| | i0++; |
| | } |
| | {code} |
| | {quote} |
| | map<int, pair <int,int> > BD[10]; // Массив MAP |
| | map<int, pair <int,int> >::iterator im; // итератор |
| | BD\[nBD\]\[A\]=make_pair(B,kk); // присваивание |
| | BD\[nBD\].erase(A); // удаление |
| | \!BD\[nBD\].empty() // проверка на пустоту |
| | Д\[nBD\].size() // вычисление размера |
| | for (im=BD\[nBD\].begin(); im\!=BD\[nBD\].end(); im++) // цикл по всем элементам |
| | |
| | map<int,map<int,int> > mat; // объявление mat как отображение пары на число |
| | // хранение "разряжённого" двумерного массива |
| | mat\[y\]\[x\]=1; // занесение значения в разряжённый массив |
| | |
| | map<int,map<int,int> > BD; // объявление BD как отображение пары на число |
| | map<int,map<int,int> >::iterator im; // итератор по первому индексу |
| | map<int,int>::iterator im2; // итератор по второму индексу |
| | |
| | BD.clear(); // обнулить двумерный массив BD |
| | |
| | BD\[A\]\[B\]=BD\[A\]\[B\]+1; // инкрементировать элемент двумерного массива |
| | {quote} |
| | {code:title=p.cpp|borderStyle=solid} |
| | for (im=BD.begin(); im!=BD.end(); im++) // двойной цикл по двумерному массиву |
| | { // проверка массива на симметричность |
| | A = im->first; |
| | for (im2 = im->second.begin(); im2 != im->second.end(); im2++) |
| | { |
| | B = im2->first; |
| | C = im2->second; |
| | if (BD[B][A]!=C) { yes=false; break; }; |
| | } |
| | }; |
| | if (yes) cout << "Yes"; else cout << "No"; |
| | |
| | map<int,vector<pair<int,int> > >::iterator im; // объявление итератора для map |
| | {code} |
| | 12_AprB. 3Lines |
| | [http://dl.gsu.by/task.jsp?nid=1422499&cid=15] |
| | |
| | Имеется N (1 <= N <= 50,000), точек с целочисленными координатами |
| | (x_i, y_i) (все в диапазоне 0...1,000,000,000); никакие две точки |
| | не расположены в одной и той же позиции. |
| | |
| | Требуется выяснить, существуют ли три прямые (каждая из которых |
| | параллельна одной из осей координат), такие, что каждая из точек |
| | лежит хотя бы на одной из этих прямых. |
| | |
| | Формат ввода |
| | * Строка 1: Целое число N. |
| | * Строки 2..1+N: Строка i+1 содержит разделенные пробелом целые числа |
| | x_i y_i , определяющие координаты точки i. |
| | |
| | Формат вывода |
| | * Строка 1: Выведите 1, если существует требуемая тройка прямых, |
| | и выведите 0 в противном случае. |
| | |
| | Пример ввода |
| | 6 |
| | 1 7 |
| | 0 0 |
| | 1 2 |
| | 2 0 |
| | 1 4 |
| | 3 4 |
| | |
| | Пояснения |
| | Всего есть 6 точек, в позициях (1,7), (0,0), (1,2), (2,0), (1,4), (3,4). |
| | |
| | Пример вывода |
| | 1 |
| | |
| | Пояснения: |
| | Прямые y=0, x=1, y=4 "покрывают" N точек. |
| | |
| | Идея решения: |
| | |
| | Фактически требуется узнать, расположены ли все точки на трёх прямых, |
| | параллельных осям координат. Проверим, могут ли они все лежать на трёх |
| | прямых, параллельных оси X или на двух прямых, параллельных оси X |
| | и одной параллельной оси Y (с помощью функции Good), если да \-выводим |
| | ответ 1, иначе меняем местами координаты X и Y всех точек и снова |
| | вызываем функцию Good. Соответствующая главная программа выглядит |
| | следующим образом: |
| | {code:title=mainpart.cpp|borderStyle=solid} |
| | int main() { |
| | freopen("lines.in", "r", stdin); |
| | freopen("lines.out", "w", stdout); |
| | cin >> n; |
| | for(int i = 0; i < n; ++i) |
| | cin >> lis[i].first >> lis[i].second; |
| | if (Good()) cout << "1"; |
| | else { |
| | for(int i = 0; i < n; ++i) |
| | swap(lis[i].first, lis[i].second); |
| | if (Good()) cout <<"1"; |
| | else cout <<"0"; |
| | } |
| | } |
| | {code} |
| | В коде ниже используется STL map, чтобы хранить "гистограмму", сколько |
| | раз появилась каждая x-координата, а также общее количество различных |
| | x - координат. Когда точка добавляется в эту структуру данных, этот |
| | счётчик увеличивается (а если количество было равно нулю, |
| | инкрементируется также общее количество различных координат). Когда |
| | точка удаляется из этой структуры данных, счётчик уменьшается, а если |
| | равен нулю - то уменьшается и общее количество различных координат. |
| | Для того, чтобы проверить, могут ли все точки быть покрыты тремя |
| | горизонтальными прямыми, мы добавляем их в нашу структуру |
| | и проверяем что общее количество различных не более 3. Чтобы |
| | проверить, покрываем ли мы всё двумя горизонтальными и одной |
| | вертикальной, мы сортируем точки по x и для каждой x-координаты |
| | временно удаляем все точки с такой x-координатой и проверяем, что |
| | оставшиеся точки имеют не более 2 различных y-координат. |
| | |
| | Более подробные пояснения: |
| | {quote} |
| | pair<int,int> lis\[MAXN\]; // массив пар координат всех точек |
| | map<int, int> cou; // Для каждой x координаты массив cou |
| | // содержит, сколько было различных точек с такой x-координатой |
| | {quote} |
| | Функции инкремента и декремента |
| | {code:title=inc.cpp|borderStyle=solid} |
| | void inc(int x) |
| | { |
| | if (cou[x] == 0) distinct++; // если в cou не было x-координаты, |
| | // то инкрементируем количество различных x-координат |
| | cou[x] = cou[x] + 1; // инкрементируем количество точек с координатой x |
| | } |
| | |
| | void dec(int x) |
| | { |
| | cou[x] = cou[x] - 1; // декрементируем количество точек с координатой x |
| | if(cou[x] == 0) distinct--; // если колво=0, декремент к-во различных x-координат |
| | } |
| | {code} |
| | Функция Good |
| | {code:title=good.cpp|borderStyle=solid} |
| | sort(lis, lis + n); // Сортируем по возрастанию x при равенстве x - по y |
| | distinct = 0; |
| | cou.clear(); // инициализируем map нулями |
| | for (int i = 0; i < n; ++i) |
| | inc(lis[i].second); // добавляем точки в map |
| | if(distinct <= 3) return 1; // если количество различных x<=3 ответ 1 |
| | |
| | int i = 0, i1 = 0; |
| | while(i < n) // перебор по всем точкам |
| | { |
| | while(i1 < n && lis[i].first == lis[i1].first) i1++; // считаем в i1 кол-во с |
| | // текущим одинаковым x |
| | for(int i2 = i; i2 < i1; ++i2) |
| | dec(lis[i2].second); // временно удаляем точки c таким x |
| | if(distinct <= 2) return 1; // если кол-во различных <=2 ответ 1 |
| | for(int i2 = i; i2 < i1; ++i2) |
| | inc(lis[i2].second); // возвращаем точки в map |
| | i = i1; // продолжаем с первой точки с другим x |
| | } |
| | return 0; |
| | } |
| | {code} |
| | Полный текст решения |
| | {code:title=all.cpp|borderStyle=solid} |
| | #include <bits/stdc++.h> |
| | using namespace std; |
| | const int MAXN = 50000; |
| | |
| | pair<int,int> lis[MAXN]; |
| | map<int, int> cou; |
| | int distinct; |
| | int n; |
| | void inc(int x) |
| | { |
| | if(cou[x] == 0) distinct++; |
| | cou[x] = cou[x] + 1; |
| | } |
| | |
| | void dec(int x) |
| | { |
| | cou[x] = cou[x] - 1; |
| | if(cou[x] == 0) distinct--; |
| | } |
| | |
| | int Good() { |
| | sort(lis, lis + n); |
| | distinct = 0; |
| | cou.clear(); |
| | for(int i = 0; i < n; ++i) inc(lis[i].second); |
| | if(distinct <= 3) return 1; |
| | int i = 0, i1 = 0; |
| | while(i < n) |
| | { |
| | while(i1 < n && lis[i].first == lis[i1].first) i1++; |
| | for(int i2 = i; i2 < i1; ++i2) |
| | dec(lis[i2].second); |
| | if(distinct <= 2) return 1; |
| | for(int i2 = i; i2 < i1; ++i2) inc(lis[i2].second); |
| | i = i1; |
| | } |
| | return 0; |
| | } |
| | |
| | int main() { |
| | freopen("lines.in", "r", stdin); |
| | freopen("lines.out", "w", stdout); |
| | cin >> n; |
| | for(int i = 0; i < n; ++i) |
| | cin >> lis[i].first >> lis[i].second; |
| | if (Good()) cout << "1"; |
| | else { |
| | for(int i = 0; i < n; ++i) |
| | swap(lis[i].first, lis[i].second); |
| | if (Good()) cout <<"1"; |
| | else cout <<"0"; |
| | } |
| | } |
| | {code} |
