Выбор языка
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
‣
queue<int> q;
q.push (s);
vector<bool> used (n);
vector<int> d (n), p (n);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
int v = q.front();
q.pop();
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (!used[to]) {
used[to] = true;
q.push (to);
d[to] = d[v] + 1;
p[to] = v;
}
}
}‣
vector < vector<int> > g; // граф
int n; // число вершин
vector<int> color; // цвет вершины (0, 1, или 2)
vector<int> time_in, time_out; // "времена" захода и выхода из вершины
int dfs_timer = 0; // "таймер" для определения времён
void dfs (int v) {
time_in[v] = dfs_timer++;
color[v] = 1;
for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
if (color[*i] == 0)
dfs (*i);
color[v] = 2;
time_out[v] = dfs_timer++;
}Стандартные структуры данных
- 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";
}
Односвязный список
‣
struct Node {
ll val;
Node* next;
Node(ll _val) : val(_val), next(nullptr) {}
};
struct list {
Node* first;
Node* last;
list() : first(nullptr), last(nullptr) {}
bool is_empty() {
return first == nullptr;
}
void push_back(ll _val) {
Node* p = new Node(_val);
if (is_empty()) {
first = p;
last = p;
return;
}
last->next = p;
last = p;
}
void print() {
if (is_empty()) return;
Node* p = first;
while (p) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
};
