Archive

Archive for the ‘C++’ Category

Знаходження кількості простих циклів у неорієнтованому графі

Тут ми розглянемо як порахувати кількість простих циклів у неорієнтованому графі. Один зі способів виконання цієї задачі – це динамічне програмування з бітовими масками. Саме цей спосіб ми тут і розглянемо. Ми припускаємо, що ви вже знайомі із поняттям динамічного програмування.

Огляд ДП з бітовими масками

Якщо говорити про нашу задачу, то динамічне програмування з бітовими масками розглядає всі можливі підмножини вершин графа. Наприклад, якщо граф має три вершини пронумеровані від 1 до 3, то такими підножинами будуть {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. Ці множини зручно представляти у вигляді бітових масок. Таких підмножин буде 2^n, що мовою С++ виглядає як 1 << n, де n – це кількість вершин у графі.

Читати далі…

Advertisements

Стара задача про шляпи

Група чаклунів зібралась на галявині, щоб вирішити питання, що накопичились у магічній країні. Магічна сила чаклунів залежить від їхньої шляпи. Щоб в палу суперечки не спалити один одного своїми закляттями вони вирішили залишити свої шляпи біля сусіднього з галявиною дуба-велетня. Поки вони обговорювали свої питання, впала ніч, тому коли розходились кожен з них взяв першу ліпшу шляпу. Нас цікавить, скільки ж чаклунів повернулись до своїх веж із своїми власними шляпами.

Читати далі…

Розв’язання задачі MappingABC з TopCoder

Тут я розгляну розв’язок задачі MappingABC з TopCoder. Це задача з першого дивізіону другого рівня складності, тому вона вимагає певний рівень учасника для розв’язання.

Основне спостереження, яке допомагає в розв’язанні – це те, що для того, щоб порахувати всі прийнятні рядки ми можемо розбити рядок на три підрядки: до першого A – [0, FA], між першим A і останнім C – [FA, LC] і після останнього C – [LC,t.size()-1]. Ми рахуємо лише ті рядки в яких у [FA, LC] трапляється B.

Введемо дві множини для позначення символів які трапляються лише зовні [FA, LC] і інші, відповідно \mathcal O і \mathcal I. Тоді кількість прийнятних рядків така:
\prod_{s\in \mathcal O}\mbox{bitcount}(s) + \Big( \prod_{s\in \mathcal I}\mbox{bitcount}(s) - \prod_{s\in \mathcal I}\mbox{bitcount}(s \& 5) \Big).

Дивись коментарі в сирцевому коді для подальших роз’яснень.
Читати далі…

Категорії:C++, Комбінаторика Позначки:, ,

Навіщо потрібен make_unique

make_unique завжди варто і завжди правильно використовувати у коді тим більше, що він не має ніякого негативного впливу на швидкодію.
Читати далі…

Категорії:C++ Позначки:,

Досконала переадресація

Загальна форма проблеми переадресації має такий вигляд:

Для заданого виразу E(a1, a2, ..., an), що залежить від (шаблонних) параметрів a1, a2, ..., an, написати функцію (об’єкт) f такий, що виклик f(a1, a2, ..., an) тотожний виклику E(a1, a2, ..., an).

Стандарт C++11 уможливив створення таких функцій (об’єктів) завдяки rvalue посиланням.

Розглянемо просту функцію-фабрику:

template<typename T, typename Arg> 
shared_ptr<T> factory(Arg arg)
{ 
  return shared_ptr<T>(new T(arg));
}

Читати далі…

Категорії:C++ Позначки:, ,

Виняткові ситуації в конструкторах і деструкторах

У програмістів на C++ часто виникають запитання про те, чи можна кидати винятки у конструкторах і деструкторах. У цій статті ми розглянемо обидва питання.
Читати далі…

Категорії:C++ Позначки:

Близько 10 прийомів для зневадження(debugging) у Visual Studio

Знедваження є однією з головних частин процесу розробки. Іноді це виклик, іноді головоломка, одно відомо достеменно – це неминуча частина процесу розробки нетривіальної програми. Розвиток засобів зневадження впродовж останніх років зробив багато задач, які постають під час зневадження, набагато легшими і швидшими.

Ця стаття розглядає десять підходів і прийомів, які ви можете використати під час зневадження і тим самим зберегти час.
Читати далі…

Категорії:C++, Перекладені Позначки:,