Выбор языка
Python:
- Бекенд
- Код на доске
- Длинная арифметика (?)
C++:
- Пишешь контесты
- Нужна скорость
- Нужно научиться алгоритмам
Фильм “Прометей”
Базовые приемы
#include <bits/stdc++.h>
#define MAX 1e10
#define forn(i, n) for (int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define int long long
typedef long long ll;
typedef vector<vector<ll> > vv;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie();
cout.tie();Указатели
int main()
{
int value = 5;
int *ptr = &value; // инициализируем ptr адресом значения переменной
cout << &value << '\n'; // выводим адрес значения переменной value
cout << ptr << '\n'; // выводим адрес, который хранит ptr
return 0;
}
Передача по ссылке в функцию
void fun(auto& v){
pass;
}
fun(v);
void fun(auto v){
pass;
}
fun(&v);2 человека для реализации BFS и DFS
‣
‣
Стандартные структуры данных
- stask<int>
- queue<int>
- deque<int>
- set<int>
- map<int, string>
- multiset<int>
- multimap<int, string>
Чем отличается set в Python и C++?
Реализация очереди под капотом
- Делаем обычный вектор. Проблема: изъятие происходит за О(n).
- Вводим указатели (left, right) на начало и на конец данных. При изъятии смещаем left на 1. Проблема: очередь постоянно увеличивается.
- Зацикливаем очередь. При достижении конца очереди индекс right = 0 переходит в начало. Проблема: что делать когда количество элементов заполнит массив?
- Создаем массив в 2х раза больший по величине и копируем туда исходный.
unordered_map/unordered_set
Реализованы через хештаблицу
unordered_map<string, string> u;
for(const auto& [key, value] : u) {
cout << "Key:[" << key << "] Value:[" << value << "]\n";
}
Односвязный список
‣
