С++ для спортивного программирования

1.

Факультет социально-экономических и
компьютерных наук
С++ для спортивного
программирования.
Гарифуллин Александр Михайлович
Программная инженерия
Пермь 2022

2.

Программная инженерия
С++ для спортивного
программирования
ФСП
БАЗА
2 / 67

3.

Программная инженерия
С++ для спортивного
программирования
Среда для программирования
ФСП
3 / 67

4.

Программная инженерия
Структура программы
<bits/stdc++.h> волшебная библиотека
С++ для спортивного
программирования
ФСП
4 / 67

5.

Программная инженерия
С++ для спортивного
программирования
ФСП
Ввод и вывод 1
Ввод данных в консоль
Приведение типов в выводе
5 / 67

6.

Программная инженерия
С++ для спортивного
программирования
6 / 67
ФСП
Ввод и вывод 2
Исправление вывода
Ускорение вывода
Ускорение ввода

7.

Программная инженерия
С++ для спортивного
программирования
ФСП
Типы данных 1. Логический. bool
7 / 67

8.

Программная инженерия
С++ для спортивного
программирования
ФСП
Типы данных 2. Целый. int ; long long
Min int = -2147483748 = -2 31
Max int = 2147483747 = 231 - 1
Min long long = -9223372036854775808 = -2 63
Max long long = 9223372036854775807 = 2 63 -1
8 / 67

9.

Программная инженерия
С++ для спортивного
программирования
ФСП
Типы данных 3. Вещественный. float, double, long double
Min float = -/+ 1.17549e-38
Max float = -/+ 3.40282e+38
Min double = -/+ 2.22507e-308
Max double = -/+ 1.79769e+308
Min long double = -/+ 3.3621e-4932
Max long double = -/+ 1.18973e+4932
9 / 67

10.

Программная инженерия
С++ для спортивного
программирования
ФСП
Типы данных 4. Символы и строки. Char ; String
10 / 67

11.

Программная инженерия
С++ для спортивного
программирования
ФСП
Типы данных 5. pair <T1,T2>
11 / 67

12.

Программная инженерия
С++ для спортивного
программирования
ФСП
Типы данных 6. auto
Автоматически определяет тип.
12 / 67

13.

Программная инженерия
С++ для спортивного
программирования
ФСП
13 / 67
Условные выражения и логические операции
== “равно”
> “больше чем”
< “меньше чем”
<= “меньше или равно”
>= “больше или равно”
!= “не равно”
! (отрицание)
&& / & (конъюнкция, логическое умножение, “И”)
|| / | (дизъюнкция, логическое сложение, “ИЛИ”)
^ (XOR, сложение по модулю 2, исключающее или, «ЛИБО»)
Приоритет:
1. Инверсия !
2. Конъюнкция &
3. Сложение по модулю 2 ^
4. Дизъюнкция |

14.

Программная инженерия
С++ для спортивного
программирования
14 / 67
ФСП
Побитовые операции
Операции сдвига / умножение или деление на 2 в n степени
<< - сдвиг влево
Int a = 2 << 2 // 10 –> 1000 – 8 (умножили на 4)
>> - сдвиг вправо
Int b = 16 >> 3 // 10000 -> 10 – 2 (разделили на 8)
Поразрядные операции
Сокращения
Int a = 6;
a <<= 3; <---> a = a << 3;
a >>= 3; <---> a = a >> 3;
a &= 2;
<---> a = a & 3;
a |= 2;
<---> a = a | 3;
a ^= 2;
<---> a = a ^ 3;
& - поразрядная конъюнкция (операция И или поразрядное умножение)
Int a = 6 & 2 // 110 & 010 = 10 -> 2
| - поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение
Int b = 5 | 2 // 101 | 010 = 111 -> 7
^ - поразрядная исключающее ИЛИ.
int c = 5 ^ 2 // 101 ^ 010 = 111 -> 7
~ - поразрядное отрицание или инверсия
Int d = ~9 // 0 000 0000 0000 1001 - > 1 111 1111 1111 0110 (-10 в дополнительном коде) (10 – 1010 – 0 000 0000 0000 1010 инвертируем и
добавляем единицу, чтобы получить дополнительный код)

15.

Программная инженерия
С++ для спортивного
программирования
ФСП
Арифметические операции
+
/
auto a = 3 / 2 // -> 1;
auto a = 3.0 / 2 // -> 1.5;
%
Int x = 3 % 2 // -> 1;
Префиксный инкремент
Int a;
++a;
Постфиксный инкремент
a++;
Префиксный декремент
--a;
Постфиксный декремент
a--;
Приоритет операций:
1. ++ ; --; (префиксные)
2. * ; / ; %;
3. + ‘ –
4. ++ ; -- (постфиксные)
15 / 67

16.

Программная инженерия
С++ для спортивного
программирования
16 / 67
ФСП
Математические операции <cmath>
Тригонометрия: (возвращает в радинах, чтобы перевести в градусы: * 180 / PI
cos
sin
tan
acos
asin
atan
M_PI – получить число пи
Логарифмические и экспоненциальные:
exp
log
log10
log2
Степенные:
pow
sqrt
cbrt
Округление:
ceil
floor
round
trunc
Еще:
abs
fmod
и т.д.

17.

Программная инженерия
С++ для спортивного
программирования
ФСП
Условные конструкции
If (условие) {…}
If (условие) {…} else {…}
If (условие) {…} else if {…} else {…}
switch(выражение)
{
case const1: … break;
case const2: … break;
default: … break;
}
Тернарный оператор
[условие] ? [верно] : [неверно]
17 / 67

18.

Программная инженерия
С++ для спортивного
программирования
18 / 67
ФСП
Циклы
while (условие)
{
…
}
do
{
…
} while (условие);
for (выражение_1; выражение 2; выражение_3)
{
…
}
continue – переход к следующей итерации
break – выход из цикла

19.

Программная инженерия
С++ для спортивного
программирования
19 / 67
ФСП
Функции 1
тип имя_функции (параметры)
{
…
}
Передача аргументов по значению и по ссылке
Прототипы
функций

20.

Программная инженерия
С++ для спортивного
программирования
ФСП
20 / 67
Функции 2
Локальные объекты
Глобальные объекты
Статические объекты

21.

Программная инженерия
С++ для спортивного
программирования
ФСП
Функции 3
Анонимные функции / Лямбда-функции
[] (параметры, которые принимает функция) { тело функции};
21 / 67

22.

Программная инженерия
С++ для спортивного
программирования
ФСП
22 / 67
Функции 4
Анонимные функции / Лямбда-функции
[&a] – получить объект из внешнего контекста по ссылке (считывать и изменять)
[a] – получить значение объекта (считать)
[&a, b] – а по ссылке, b по значению
[&] – захват всех переменных по ссылке
[=] – захват всех переменных по значению
[=]()mutable / [a, b]() mutable – можно считывать и изменять внутри функции, при этом «снаружи» переменные
не изменятся
[]()-> int{} - указать тип возвращаемого значения

23.

Программная инженерия
С++ для спортивного
программирования
ФСП
STL
23 / 67

24.

Программная инженерия
С++ для спортивного
программирования
ФСП
24 / 67
Итераторы 1
Итератор – это объект, который может перебирать элементы в контейнеры стандартной библиотеки С++ и
предоставлять доступ к отдельным элементам.
Для получения итераторов используют begin() и end()
Операции с итераторами:
*iter – получение элемента, на который указывает
итератор
++iter перемещение итератора вперед
--iter перемещение итератора назад
iter1 == iter2 два итератора равны, если указывают
на один и тот же элемент
iter1 != iter2 два итератора не равны, если указывают
на разные элементы
Итераторы позволяют получать и изменять элементы

25.

Программная инженерия
С++ для спортивного
программирования
ФСП
Итераторы 2
Константные итераторы: можно считать элементы контейнера, но не изменять их
Контейнер – константа // const vector <int> v = {1, 2, 3};
cbegin(), cend() – возвращают константные итераторы, даже если контейнер не константа
Реверсивные итераторы: позволяют перебирать элементы контейнера в обратном направлении.
rbegin(), rend()
crbegin(), crend()
25 / 67

26.

Программная инженерия
С++ для спортивного
программирования
ФСП
26 / 67
Итераторы 3
Дополнительные операции:
iter + n: возвращает итератор, который смещен от итератора iter на n позиций вперед
iter – n: возвращает итератор, который смещен от итератора iter на n позиций назад
iter += n: перемещает итератор iter на n позиций вперед
iter -= n: перемещает итератор iter на n позиций назад
iter1 – iter2: возвращает количество позиций между итераторами iter1 и iter2
>, >=, <. <= : операции сравнения. Один итератор больше другого, если указывает на элемент, который
ближе к концу

27.

Программная инженерия
С++ для спортивного
программирования
ФСП
27 / 67
Контейнеры
последовательности

28.

Программная инженерия
С++ для спортивного
программирования
ФСП
array / #include <array> / статический непрерывный массив
Объявление
array<int,3> a1 {1, 2 ,3}
array<int,3> a2 = {1, 2 ,3}
array<int,3> a3
array<int,3> a4 {}
Доступ к элементам
at / O(1)
operator[] / O(1)
front / O(1)
back / O(1)
Размер
size / O(1)
max_size / O(1)
empty / O(1)
Модификаторы
fill / O(N)
swap / O(N)
28 / 67

29.

Программная инженерия
С++ для спортивного
программирования
vector
#include <vector>
динамический непрерывный
массив
ФСП
29 / 67

30.

Программная инженерия
С++ для спортивного
программирования
30 / 67
ФСП
vector / #include <vector> / динамический непрерывный массив
Объявление
vector<int> v;
vector <int> v(n);
vector <vector<int>> = {{4,2,5},{1},{0,-1}};
Доступ к элементам
at / O(1)
operator[] / O(1)
front / O(1)
back / O(1)
Размер
size / O(1)
max_size / O(1)
resize / O(N)
capacity / O(1)
empty / O(1)
reserve / O(N)
shrink_to_fit / O(1)
Модификаторы
assign / O(N)
swap / O(1)
push_back / O(1) – O(N)
pop_back / O(1)
insert / O(1) - O(N)
erase / O(N)
clear / O(N)
emplace / O(N)
emplace_back / O(1)

31.

Программная инженерия
С++ для спортивного
программирования
deque
#include <deque>
двусторонняя очередь
ФСП
31 / 67

32.

Программная инженерия
С++ для спортивного
программирования
deque
#include <deque>
двусторонняя очередь
ФСП
32 / 67

33.

Программная инженерия
С++ для спортивного
программирования
33 / 67
ФСП
deque / #include <deque> / двусторонняя очередь
Объявление
deque<int> dq;
deque <int> dq(n);
deque<int> dq= {5,2,7};
Доступ к элементам
at / O(1)
operator[] / O(1)
front / O(1)
back / O(1)
Размер
size / O(1)
max_size / O(1)
empty / O(1)
shrink_to_fit / O(1)
resize / O(N)
Модификаторы
assign / O(N)
swap / O(1)
push_back / O(1) – O(N)
pop_back / O(1)
push_front / O(1)
pop_front / O(1)
insert / O(1) - O(N)
erase / O(N)
clear / O(N)
emplace / O(N)
emplace_back / O(1)
emplace_front / O(1)

34.

Программная инженерия
С++ для спортивного
программирования
forward_list
#include < forward_list >
односвязный список
ФСП
34 / 67

35.

Программная инженерия
С++ для спортивного
программирования
35 / 67
ФСП
forward_list / #include <forward_list> / односвязный список
Объявление
forward_list<int> fl;
forward_list <int> fl(n);
forward_list<int> fl= {4,1,5};
Доступ к элементам
front / O(1)
Размер
max_size / O(1)
empty / O(1)
resize / O(N)
Модификаторы
assign / O(N)
swap / O(1)
clear / O(N)
insert_after / O(N)
emplace_after / O(N)
erase_after / O(N)
push_front / O(1)
pop_front / O(1)
emplace_front / O(1)

36.

Программная инженерия
list
#include <list>
двусвязный список
С++ для спортивного
программирования
ФСП
36 / 67

37.

Программная инженерия
С++ для спортивного
программирования
37 / 67
ФСП
list / #include <list> / двусвязный список
Объявление
list<int> list1;
list <int> list2(n);
list <int> list3 = {4,1,5};
Доступ к элементам
front / O(1)
Размер
max_size / O(1)
size / O(1)
empty / O(1)
resize / O(N)
Модификаторы
assign / O(N)
swap / O(1)
clear / O(N)
insert / O(N)
emplace / O(1)
push_back / O(1)
emplace_back / O(1)
pop_back / O(1)
push_front / O(1)
emplace_front / O(1)
pop_front / O(1)

38.

Программная инженерия
С++ для спортивного
программирования
ФСП
Ассоциативные
контейнеры
38 / 67

39.

Программная инженерия
set
#include < set>
множество
С++ для спортивного
программирования
ФСП
39 / 67

40.

Программная инженерия
С++ для спортивного
программирования
40 / 67
ФСП
set/ #include <set> / множество
Объявление
set<int> st(n);
set<int> st;
set<int, classcomparer> st = {5,31,6};
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(Log)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log)

41.

Программная инженерия
map
#include <map>
словарь
С++ для спортивного
программирования
ФСП
41 / 67

42.

Программная инженерия
С++ для спортивного
программирования
42 / 67
ФСП
map/ #include <map> / словарь
Объявление
map<int,int> mp;
map <int,int,classcomp> mp;
Доступ к элементам:
at / O(Log)
[] / O(Log)
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(Log)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log)

43.

Программная инженерия
multiset
#include <multiset>
мультимножество
С++ для спортивного
программирования
ФСП
43 / 67

44.

Программная инженерия
С++ для спортивного
программирования
44 / 67
ФСП
multiset/ #include < multiset > / мультимножество
Объявление
multiset<int> st(n);
multiset<int> st;
multiset<int, classcomparer> st = {5,31,6};
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(Log)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log)

45.

Программная инженерия
multimap
#include < multimap >
мультисловарь
С++ для спортивного
программирования
ФСП
45 / 67

46.

Программная инженерия
С++ для спортивного
программирования
46 / 67
ФСП
multimap/ #include < multimap > / мультисловарь
Объявление
multimap<int,int> mp;
multimap <int,int,classcomp> mp;
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(Log)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log)

47.

Программная инженерия
С++ для спортивного
программирования
ФСП
Неупорядочные
ассоциативные
контейнеры
47 / 67

48.

Программная инженерия
С++ для спортивного
программирования
unordered_set
#include <unordered_set>
неупорядочное множество
ФСП
48 / 67

49.

Программная инженерия
С++ для спортивного
программирования
49 / 67
ФСП
unordered_set/ #include < unordered_set> / неупорядочное множество
Объявление
unordered_set<int> st(n);
unordered_set <int> st;
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(N)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log) / O(N)

50.

Программная инженерия
С++ для спортивного
программирования
unordered_map
#include <unordered_map>
неупорядочный словарь
ФСП
50 / 67

51.

Программная инженерия
С++ для спортивного
программирования
51 / 67
ФСП
unordered_map/ #include <unordered_map> / неупорядочный словарь
Объявление
unordered_map<int,int> mp;
Доступ к элементам:
at / O(Log)
[] / O(Log)
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(Log)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log)

52.

Программная инженерия
С++ для спортивного
программирования
unordered_multiset
#include <unordered_multiset>
неупорядочное мультимножество
ФСП
52 / 67

53.

Программная инженерия
С++ для спортивного
программирования
53 / 67
ФСП
unordered_multiset/ #include < unordered_multiset> / неупорядочное
мультимножество
Объявление
unordered_multiset<int> st(n);
unordered_multiset <int> st;
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(N)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log) / O(N)

54.

Программная инженерия
С++ для спортивного
программирования
unordered_multimap
#include <unordered_multimap>
неупорядочный мультисловарь
ФСП
54 / 67

55.

Программная инженерия
С++ для спортивного
программирования
55 / 67
ФСП
unordered_map/ #include <unordered_map> / неупорядочный словарь
Объявление
unordered_multimap<int,int> mp;
Доступ к элементам:
at / O(Log)
[] / O(Log)
Размер
max_size / O(1)
empty / O(1)
size / O(1)
Модификаторы
insert / O(1) / O(Log)
erase / O(1) / O(Log) / O(N)
swap / O(1)
clear / O(N)
emplace / O(Log)

56.

Программная инженерия
С++ для спортивного
программирования
ФСП
Адаптеры
контейнеров
56 / 67

57.

Программная инженерия
stack
#include <stack>
стек
LIFO
LAST-IN-FIRST-OUT
С++ для спортивного
программирования
ФСП
57 / 67

58.

Программная инженерия
С++ для спортивного
программирования
58 / 67
ФСП
stack/ #include < stack> / стек
Объявление
stack<int> st;
stack<int,vector<int>> st;
Размер
max_size / O(1)
size / O(1)
Доступ к элементам
top / O(1)
Контейнеры для стека
Vector
Deque – по умолчанию
List
Модификаторы (Сложность как у
контейнера, от которого произошел)
push
emplace
pop
swap

59.

Программная инженерия
queue
#include <queue>
очередь
FIFO
FIRST-IN-FIRST-OUT
С++ для спортивного
программирования
ФСП
59 / 67

60.

Программная инженерия
С++ для спортивного
программирования
60 / 67
ФСП
queue/ #include < queue> / очередь
Объявление
queue<int> qu;
queue <int,list<int>> qu;
Размер
max_size / O(1)
size / O(1)
Доступ к элементам
front / O(1)
back / O(1)
Контейнеры для стека
Deque – по умолчанию
List
Модификаторы (Сложность как у
контейнера, от которого произошел)
push
emplace
pop
swap

61.

Программная инженерия
С++ для спортивного
программирования
priority_queue
#include <priority_queue>
очередь с приоритетом
ФСП
61 / 67

62.

Программная инженерия
С++ для спортивного
программирования
ФСП
62 / 67
priority_queue/ #include < priority_queue > / очередь с приоритетом
Объявление
priority_queue<int> qu;
priority_queue <int,deque<int>> qu;
Размер
max_size / O(1)
size / O(1)
Доступ к элементам
top / O(1)
Контейнеры для стека
Deque
vector – по умолчанию
Модификаторы (Сложность как у
контейнера, от которого произошел)
push
emplace
pop
swap

63.

Программная инженерия
С++ для спортивного
программирования
ФСП
Перебор элементов / range-based for loop
63 / 67

64.

Программная инженерия
С++ для спортивного
программирования
ФСП
Библиотека
алгоритмов
64 / 67

65.

Программная инженерия
С++ для спортивного
программирования
ФСП
65 / 67
Алгоритмы 1
Vector <int> v = {7,0,3,-3,6,2}
Сортировка
sort // sort(v.begin(), v.end()) // sort(v.begin(), v.end(), myfunc)
is_sorted
Минимум и максимум
Возвращают значения:
min
max
minmax
Возвращают итераторы:
min_element
max_element
minmax_element
Бинарный поиск
lower_bound – первый итератор, не
меньший чем заданное значение
upper_bound – первый итератор, который
больше заданного значения
equal_range - диапазон элементов,
соответствующих ключу
binary_search –проверяет, существует ли
элемент в диапазоне

66.

Программная инженерия
С++ для спортивного
программирования
ФСП
Алгоритмы 2
Поиск
find
find_if
find_if_not
find_end
find_first_of
Счетчики
count
count_if
Модификаторы
copy
copy_if
replace
replace_if
remove
remove_if
reverse
rotate
66 / 67

67.

Программная инженерия
С++ для спортивного
программирования
ФСП
Документации по плюсам:
https://ru.cppreference.com/w/
https://cplusplus.com/
Алгоритмы:
http://e-maxx.ru/algo/
https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных
Задачи решать на Codeforces, leetcode, timus
67 / 67