May 7 2021 at 22:56

C++ 14 с точки зрения олимпиадного программирования

Invite pending

Недавно я, решая очередную задачу на codeforces, я столкнулся с необходимостью написания элементарной функции нахождения НОД, и тогда я задумался: "Неужели нет встроенной функции для его нахождения? Это же базовый алгоритм.". Забредя в дебри интернета, я решил поглубже изучить возможности C++ 14 для лучшего написания олимпиад. Итак, я организую рубрику полезных функций языка с точки зрения олимпиадного программирования.

'

С помощью ',можно обозначать границы числа, не меняя его значения

int x = 1'020'011; // int x = 1020011

Также в переменные можно записывать числа в двоичной системе счисления

int x = 0b0110 // int x = 6

Битовые операции

В C++ есть встроенные битовые операции над числами, которые позволяют быстрее осуществлять некоторые привычные операции.

Основные из них:

k & n - побитовое И
k | n - побитовое ИЛИ
k ^ n - побитовый XOR
k << n - сдвинуть все биты числа k на n битов влево
k >> n - сдвинуть все биты числа k на n битов вправо

Благодаря данным операциям мы можем ускорить наш код:

А давайте быстро умножим/поделим n на степень двойки

n = n << 1; // Умножить n на 2
n = n >> 1; // Разделить n на 2

Проверим-ка чётность числа

В двоичной записи числа четность или нечетность числа определяет последний бит (т.к. только нулевая степень двойки нечетна), тогда если у данного числа в двоичной записи последний бит положителен, то оно нечетна, иначе четно. Такой трюк не сильно лучше получения остатка от деления (%), но работает быстрее с большими числами.

if(n & 1){
  cout << "Нечетное" << endl;
}
else{
  cout << "Четное" << endl;
}

Перестановка двух чисел местами

Нам даже не потребуется третья переменная:

a ^= b;
b ^= a;
a ^= b;

Альтернативный вариант:

a ^= b ^= a ^= b;

Проверка на степень двойки

int isPowerOfTwo(int x){
     return (x & (!(x&(x-1)))); 
}

Если число является степенью двойки, тогда его двоичная запись имеет лишь один активный бит, отнимая один, мы активируем все биты до степени двойки и тогда x & (x-1) = 0, иначе есть активные биты перед самым значимым, а значит он останется активным после x-1 и x & (x-1) > 0

Лямбды

Эта тема стоит отдельного поста (в будущем сделаю), а сейчас расскажу в общих чертах.

Лямбда-выражение - определяет анонимную функцию внутри другой функции. Такие выражения позволяют определить функцию максимально близко к месту её вызова и не захламлять пространство имен лишними несложными выражениями.

Они имеют следующий синтаксис:

[captureClause] (параметры) -> возвращаемый тип {тело лямбды};

Есть два способа объявления лямбды:

auto sum = [](auto a,auto b){return a+b;};
cout << sum(1,2); // 3

find_if(all(arr),
                  [](string str) {
                    return (str.find("nut") != string::npos);
                  });

Данные выражения удобно использовать для обозначения незначимых функций внутри одной, чтобы не громоздить кучу лишних имен функций и кода.

Полезные STL контейнеры

Обычно я пробегался циклом для проверки правильности массива, но, оказывается, есть более простая альтернатива такому методу.

// Проверим все ли элементы правильные
all_of(v.begin,v.end(),isRight());
// Проверим есть ли хотя бы один правильный элемент
any_of(v.begin,v.end(),isRight());
// Проверим все ли элементы НЕ правильные
none_of(v.begin,v.end(),isRight());
// Получим позицию правильного элемента или его отсутствие
find_if(v.begin,v.end(),isRight());
// Если результат = v.end(), значит в данном массиве нет такого элемента

Итог

Это то, что я нашел интересным за последние два дня и решил запечатлеть эти подсказки в виде небольшой статьи. Надеюсь она также будет кому-то полезна.

Hubs: