Author |
Message |
23.01.2007 15:51:36
Subject: Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
Both methods immediately leads to a O(nlogn) time solution using balanced binary trees.
Sorry to all the Pascal programmers as STL set gives C++ users a huge advantage should this solution be implemented.
Это цитата из анализа задачи USACO 2007 January Gold: Problem 3. Cow School
|
24.01.2007 07:56:58
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
Under C++, the algorithm can be implemented using the STL priority_queue in O(NlogN) time.
Это цитата из анализа задачи USACO 2006 November Gold: Problem 1: Fence Repair
|
21.03.2007 10:23:18
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
The C++ Standard Template Library has a handy function called next_permutation that takes care of all the work in looping over the possible permutations.
Это цитата из анализа задачи USACO 2007 March Bronze: Problem 3: Cows of the Round Table
|
02.05.2007 09:02:40
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
However, if you really do not like coding data structures from scratch (due to bugs or just plain boredom), then it is worth the effort to learn to use your languages libraries for data structures. Below is a (short) solution from Christos Tzamos that uses STL's map and multiset, which are already sorted containers!
Это цитата из анализа задачи USACO 2007 April Silver: Problem 1: City Horizon
|
11.08.2007 11:52:36
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
Курс лекций по олимпиадному программированию Михаила Густокашина
http://moemesto.ru/tnik222/file/4587241/lection2.pdf
С лекциями, задачами с тестами, и их разборами.
...
Занятие 5: STL
Введение.
Пара (pair).
Стек (stack).
Очередь (queue).
Дек (deque).
Динамически расширяемый массив (vector).
Вектор битов (bit_vector).
Строка (string).
Итераторы.
Хеш-таблица (hash_set).
Хеш-словарь (hash_map).
Алгоритмы в STL.
Использование собственных структур в STL.
|
13.08.2007 11:05:23
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
Хорошая дока по STL (на английском):
http://www.sgi.com/tech/stl/table_of_contents.html
|
13.12.2007 13:41:40
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
Now the problem becomes a data structure problem, we need to support the following operations: insertion, deletion, find the first element with key bigger than a given value and we want to do each operation in O(logn) time This can be done using STL set.
Это цитата из анализа задачи USACO 2007 December Gold: Problem 2: Gourmet Grazers
|
19.01.2008 14:24:56
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
This one is slightly complex owing to the requirement for a 'sort' routine. C and C++ programmers have easily used built-in sort routines (e.g., qsort); Pascal and Java
Это цитата из анализа задачи USACO 2008 January Bronze: Problem 2: Election Time
|
06.12.2009 19:59:29
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
Евгений Грицкевич:
... Есть алгоритм, который позволяет найти K-й по счёту в отсортированном массиве элемент быстрее чем за NLogN (в Си++ это nth_element() ) .
|
10.02.2010 07:37:56
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
Both C++ and Java have priority queues in their standard library.
Это цитата из анализа задачи 2010 February Silver : 2. Chocolate Giving
|
22.10.2010 16:28:14
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
C++.com
|
12.03.2012 14:27:23
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
are stored in a data structure that can quickly find the min and max, such as an STL multiset
2012 March Silver : 2. Flowerpot
|
12.03.2012 14:31:34
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
In C++, one can use the next_permutation() function to generate all N! permutations very easily
2012 March Bronze : 2. Connect the Cows
|
22.11.2013 12:36:30
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
we can use either a priority queue or a set (i.e., a balanced binary search tree)
... in an STL set, for example, we could use the lower_bound method ...
2013 November Silver 2. Crowded Cows
|
22.11.2013 12:39:03
Subject: Re:Преимущества C++ (STL) перед Паскалем
|
Mihail Dolinskiy
Topics: 1985
Messages: 47294
My Profile
|
STL's upper_bound function nicely expresses the binary search.
2013 November Gold: 3. No Change
|
|