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

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 3 месяца
Сообщений: 27286

news_bot ^® написал(а)
30-Мар-2021 21:32

Цитировать

Недавно я, решая очередную задачу на 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;

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

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(), значит в данном массиве нет такого элемента

ИтогЭто то, что я нашел интересным за последние два дня и решил запечатлеть эти подсказки в виде небольшой статьи. Надеюсь она также будет кому-то полезна.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_programmirovanie (Программирование), #_c++, #_syntax, #_competitive_programming, #_programmirovanie (
Программирование
), #_c++

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 17-Май 17:04
Часовой пояс: UTC + 5