ACM
Навігація
Теми форуму
Чи знали ви, що... ? (beta)
Коли ми гладимо кота, у нас знижується частота серцебиття і кров’яний тиск. А люди з сердечно-судинними захворюваннями мають шанс прожити довше, якщо у них є кіт, на відміну від тих, хто не має ні кота, ні собаки.
Події
Пн Вт Ср Чт Пт Сб Нд
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Birthday(s):
Перегляд теми
Автор
MAP
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 28-02-2010 22:36
Можете хтось коротко пояснити тип даних map і розказати, де він застосовується і які задачки ним можна розвязати? Будь ласка...
Автор
RE: MAP
webmaster
Головний Адміністратор
Повідомлень: 1136
Зареєстрований: 17.03.07
Опубліковано 28-02-2010 22:59
Мап - ніби масив, але індексація може відбуватися не тільки цілими числами а будь яким типом даним (навіть вашим власним).
також може бути довільна кількість елементів, тобто можна додавати і викидати із мап (як у Сет).
Тобто Мап - це поєднання Масиву і Сету.
всередині Мапу сидить АВЛ (або червоно-чорне дерево), тому складність операцій орієнтовно O(logN) за кожну операцію (додавання, взяти, видалити).
зразки коду:
//перший тип це ключ, другий значення
//можуть бути довільні (є тільки невеличке обмеження на ключ, компілятор підскаже)
map<int,string> mapa;
//map<myClass,mySecondClass> mapa2;
mapa.insert ( make_pair( 23 ,"dfdfd" ) ) ;
//аналогічно можна зробити так
mapa[ 23 ] = "dfdfd" ;
if ( mapa.find ( 23 ) == mapa.end ( ) )
//якщо немає такого ключа
;
if ( mapa.find ( 23 ) != mapa.end ( ) )
//якщо існує такий ключ
;
//видаляємо елемент із ключем
mapa.erase ( 23 ) ;
Змінив(ла) webmaster , 28-02-2010 23:02
Автор
RE: MAP
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 01-03-2010 20:27
Ага... Спасибі... Дуже чітко і ясно...
Хм.. мій багаж знань трішки поповнився. А не підкажете, які задачки можна цим способом робити? На цьому сайті є шось такого типу?
Я думаю, шо "Колобка" можна цим способом зробити. Я правий?
Автор
RE: MAP
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 01-03-2010 20:30
Хах.. На днях дивився фільм "Номер 23", де головного героя переслідувало це число. А в тебе в зрвзку всюди число 23 xDD Містика, однако...
Автор
RE: MAP
webmaster
Головний Адміністратор
Повідомлень: 1136
Зареєстрований: 17.03.07
Опубліковано 02-03-2010 00:11
Про "23", у мене просто як руки на клавіатуру впали так і написав.
Не правильно говорити "способом", оскільки це не спосіб а тільки структура даних, така як int, double, масив, сет і т.д. А от де вже бачете, що це Вам дасть зможу реалізувати задуманий алгоритм легше це вже інше питання.
"Колобок" можна і за допомогою цієї структури розв'язати, але є простіша структура (яка згадувалась вище).
Відразу прийшла у голову інша подібна задачі.
Порахувати скільки разів кожне слово зустрічається.
орієнтовно код буде наступний:
map<string,int> m;
for ( int i=0 ; i<N; i++)
{
cin >> s;
m[ s] ++;
}
Перейти на форум:
Робота сайту
Тестувалка
Стаття: Шлях до перемоги
Стаття: Львів’яни взяли "золото". Газета "Каменяр".
Обговорення новин
Статті Михайла Медведєва
Обговорення статтей
TCO 2007
Корисна інформація
SRM
TCHS SRM
Інші конкурси
TCCC 2007
TCO 2008
TCO 2009
TCO
acm.timus.ru
acm.uva.es
acm.tju.edu.cn
acm.lviv.ua
ttb.by
Засідання
Задачі
LNU Practice Session '08
Онсайт змагання
Онлайн змагання
Тренування
Зимові збори в Петрозаводську - 2008
ACM ICPC World Finals 2008
Всеукраїнська олімпіада школярів 2008
KPI-Open
Google Code Jam 2008
ІІІ етап Всеукраїнської учнівської олімпіади з інформатики 2009 року
ACM ICPC World Finals
Всеукраїнська учнівська олімпіада з інформатики 2010
Всеукраїнська учнівська олімпіада з інформатики 2011
Рейтинг "Найкоротший код"
Google Code Jam
ACM SouthEastern European Region
Всеукраїнська учнівська олімпіада з інформатики 2012
South-Eastern European Programming Contest
DE:CODED
Про глобальні питання
Теревені
Про АСМ
Гумор
Міні-чат
Зараз на сайті
Гостей: 2
На сайті немає зареєстрованних користувачів
Користувачів: 5,103
новачок:
NataEvgten