Archive

Archive for the ‘C++’ Category

Розв’язання задачі 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++, Перекладені Позначки:,

Код на c++11 для китайської теореми про залишки

Припускають, що назва “китайська теорема про залишки” з’явилась від такого запитання: Як багато солдатів в армії Хан Сінга, якщо вишикувати їх у три шереги, то два солдати залишаться зайвими, якщо вишикувати у п’ять шерег, то три солдати не в шерегах і якщо вишикувати у сім шерег, то два солдати зайві.

Наводжу код на с++11 для розв’язання задач за китайською теоремою про залишки:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<class T> void ex_al_eu_in(const T &r1, const T &r2, const T &x1, const T &x2, const T &y1, const T &y2, T &gcd, T &a, T &b) {
    T r3 = r1 - r2 * (r1 / r2);
    T x3 = x1 - x2 * (r1 / r2);
    T y3 = y1 - y2 * (r1 / r2);
    if (0 != r3)
        ex_al_eu_in(r2, r3, x2, x3, y2, y3, gcd, a, b);
    else {
        gcd = r2;
        a = x2;
        b = y2;
    }
}

template<class T> void ex_al_eu(const T &r1, const T &r2, T &gcd, T &a, T &b) {
    if (0 == r1 || 0 == r2)
        gcd = a = b = 0;
    else
        ex_al_eu_in(r1 > r2 ? r1 : r2, r1 < r2 ? r1 : r2, T(1), T(0), T(0), T(1), gcd, r1 > r2 ? a : b, r1 < r2 ? a : b);
}

vector<int> modules = {3,5,7};
vector<int> remainders = {2,3,2};
vector<int> ys(remainders.size());

int main() {
    int m_big = 1;
    for(int r : modules) { m_big *= r; };
    int answer = 0;
    transform(modules.begin(), modules.end(), modules.begin(), ys.begin(), [m_big](int mod, int y){ 
            int gcd, f;
            int m = m_big / mod;
            ex_al_eu(mod, m, gcd, f, y);
            return y*m; 
        });
    cout << inner_product(remainders.begin(), remainders.end(), ys.begin(), 0) << endl;
    return 0;
}

Компілюємо так:
g++ ім’я.cpp -std=c++0x

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