Заповеди
Daniel DankoСначала прочитай, как переводить туториалы
Pre S. Если будет мало того, что внизу, просмотри этот классный онлайн-учебник
Pre S.S. Если ты фанатик, открой Тору
Pre S.S.S Смотри в @problems_cpp книжки по СП
Pre S.S.S.S А вот все туториалы с Codeforces
Тут будут перечислены приемы, темы из спортивного программирования, на которые натыкаются прогеры и говорят "Боже, почему ты не рассказал мне об этом раньше??7".
Фичи будут сопровождаться объяснением и n задачами c Codeforces, где n ->0.
Найти задачу можно, заменив части адреса https://codeforces.com/contest/1105/problem/D
Шаблон начала программы
Можешь использовать мой
Как работают все функции для дебага, написано здесь
Основные фишки
++min(a, b), max(a, b) возвращает минимум/максимум из a и b; можно вкладывать: min(a, max(b, c))
ЗАДАЧИ: 479A, 581A
++abs(a) возвращает значение числа без знака
ЗАДАЧИ: 515A
++a % b дает остаток от деления a на b
ЗАДАЧИ: 270A, 577A
++цикл без дополнительных счетчиков
while(t--){/*какой-то код*/;}
for(;t--;){/*какой-то код*/;}
Цикл завершается, когда t становится равным 0. Проработает ровно t раз благодаря постфиксному декременту
Что такое декремент и в чем разница постфиксного от префиксного?
++бесконечные циклы
while(true){/*какой-то код*/;}
for(;;){/*какой-то код*/;}
++Проверка числа a на простоту
bool is_prime(int a){
if((a % 2 == 0 and a > 2) or (a <= 1)) return 0;
for(int i = 3; i * i <= a; i += 2)
if(a % i == 0)
return 0;
return 1;
}
ЗАДАЧИ:
++const int N = 1e5+42;
Объяви до main() константу для размера массива, который будешь использовать. Оставь небольшой запас, чтобы случайно не выйти за пределы. Теперь, если тебе нужно будет увеличить массив, достаточно будет изменить значение константы в коде.
ЗАДАЧИ:
++Массив для заметок - если нужно запомнить какую-нибудь инфу о числе a, можно записать ее в ячейку массива arr[a]
for(int i = 1; i <= n; ++i)
if(is_prime(i))
arr[i] = 1;
is_prime(i) - ваша функция, проверяющая число i на простоту.
ЗАДАЧИ: 577C, 583A
++Подотрезки массива - если смотреть на кусок массива, в котором ячейки с номерами l, l+1, l+2, ... , r, это и будет отрезок массива, или подмассив
Нельзя записать отрезок, но пройти по нему и просмотреть его ячейки можно так:
for(int i = l; i <= r; ++i)
cout << arr[i] << ' ';
ЗАДАЧИ: 580A
++Перебор - иногда математика не спасает, или лень думать, поэтому нужно смотреть на все различные пары ячеек массива/элементов какого-нибудь контейнера. Порядок индексов в паре не имеет значения
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
ans = max(ans, arr[i]*arr[j]);
этот код ищет максимальное произведение чисел в 2 различных ячейках массива arr[]
ЗАДАЧИ: 263B
++gcd(a, b) - возвращает наибольший общий делитель(НОД) a и b. Можно вкладывать gcd(a, gcd(b, c)). До С++17 работала функция __gcd(a, b). Наибольший общий делитель(НОК = lcm) - a/gcd(a, b)*b
ЗАДАЧИ: 660A
++bitset - массив битов.
Посмотреть двоичное представление числа - bitset<20>(42)
Базовые алгоритмы
++решето Эратосфена
Нужно для нахождения всех простых чисел до 3e8(TL - 2 сек.)/5e8(TL - 3 сек.)
ЗАДАЧИ: 113C
++бинарный поиск
альтернативно:
Пусть ответ находится где-то на отрезке [l;r) и key - число, которое мы ищем в v:
vector<int> v{3,7,23,25,56,56,34};
int key = 25;
int l = 0, r = size(v);
while(r-l>1){
int mid = (l+r)/2;
if(v[mid] <= key) l = mid;
else r = mid;
}
dbg(l);
Тогда, как видно из проверки if(v[mid] <= key) l = mid;, на позиции l в конце концов будет элемент, <= key - то, что нам нужно
Если нам нужен элемент, >= key, сделаем наоборот: будем искать key на отрезке (l;r] и получим ответ на индексе r.
vector<int> v{3,7,23,25,56,56,34};
int key = 25;
int l = -1, r = size(v)-1;
while(r-l>1){
int mid = (l+r)/2;
if(v[mid] >= key) r = mid;
else l = mid;
}
dbg(l);
++бинарное возведение в степень - возводит число a в степень n по модулю M за lg(n)
Как пишется:
ll M = 1e9+7;
ll pw(ll P, ll n){
ll ans = 1;
for(; n; P = (P * P) % M, n >>= 1){
if(n&1) ans = (P * ans) % M;
}
return ans;
};
ЗАДАЧИ: 678D
++рекурсия
++графы
++поиск в глубину
ЗАДАЧИ: 687A
++поиск в ширину
ЗАДАЧИ: 687A
Структуры данных
++бор
ЗАДАЧИ: 665Е, туториал
++дерево отрезков
++convex hull trick
Аккуратная реализация
ЗАДАЧИ: в туториале
Контейнеры
++информация о любом контейнере:
vector<int> v{1,5,3,4,6,2};
set<int> s{2,7,2,8,93,55};
deque<int> d{3,8,1,5,3,8,2,6};
string ss = "Gulobod scotch";
int a[] = {3,6,8,2,7,4,7};
// размер контейнера
// С++17 - можно применять одну и ту же функцию к чему угодно
dbgs(size(v), size(s), size(d), size(ss), size(a));
// C++11,14,17 - для массива придется вычислять размер
dbgs(v.size(), s.size(), d.size(), ss.size(), sizeof(a)/sizeof(a[0]));
// итератор на начало/за-конец
//C++11,14,17
begin(v), end(v);
begin(s), end(s);
begin(d), end(d);
begin(ss), end(ss);
begin(a), end(a);