| | *Краткая справка о 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 |
| // только после этой операции 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> > BD10; // Массив 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} |