Форум программистов, компьютерный форум CyberForum.ru

Найти пары элементов массива сумма которых является степенью двойки - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Чтение данных из файла последовательного доступа http://www.cyberforum.ru/cpp-beginners/thread1787553.html
Доброго времени суток , столкнулся с такой проблемой. Информация: Данные в файле: 10228 John GREY 5638.5 32255 Alice Nata 1058.46
C++ Спецификатор преобразования Доброго времени суток. Сегодня при изучении материала по работе с файлами натолкнулся на такой вопрос. Программы ниже иллюстрирует чтение данных из файла последовательного доступа. // File Working #include <stdio.h> http://www.cyberforum.ru/cpp-beginners/thread1787548.html
Посчитать, хватит ли поросятам тугриков для подключения к компьютерной сети (задача acmp №57) C++
Задача acmp №57 (Время: 1 сек. Память: 16 Мб Сложность: 33%): Компания «Маша и медведи» является самым крупным интернет-провайдером во всем лесу. Именно поэтому, с просьбой подключить их к интернету обратились N поросят. Домики поросят расположены в различных точках (xi, yi). Ближайшая точка подключения расположена в точке (xnet, ynet). Для того чтобы подключиться к сети всем N поросятам...
Нахождение разбиений числа C++
Все привет, ребят помогите. Суть задания: разбиений числа, есть число, нужно его разбить. Например, {3,1,1} или {3,2} — разбиения числа 5, поскольку 5 = 3 + 1 + 1 = 3 + 2. Всего существует p(5) = 7 разбиений числа 5: {1,1,1,1,1}, {2,1,1,1}, {2,2,1}, {3,1,1}, {3,2}, {4,1}, {5}. Ну вы поняли, и мне надо сделать диапазон, типо что бы пользователь задавал на какие числа он хочет разбить заданное...
C++ Взять элементы из определенного листа http://www.cyberforum.ru/cpp-beginners/thread1787463.html
list<int>route; vector<list<int>>routes; route.push_back(.) routes.push_back(route) for(int start = 0 ; start = routes.size();start++) { for().. for()..
C++ Построить латинский квадрат используя циклический сдвиг Написать программу для решения следующей задачи. построить латинский квадрат,используя циклический сдвиг. Латинский квадрат-матрица размером N x N, элементы которой равны 1,2..N и каждое число встречается только один раз в каждой строке и каждом столбце. Это нужно через объекты делать) Заранее огромное человеческое спасибо!!!)) подробнее

Показать сообщение отдельно
Новичок
Модератор
 Аватар для Новичок
1141 / 712 / 148
Регистрация: 17.07.2012
Сообщений: 4,043
Записей в блоге: 1
Завершенные тесты: 2
31.07.2016, 23:19     Найти пары элементов массива сумма которых является степенью двойки
N <= 105
Очевидно же, что в лоб никак не зайдет. Нужно использовать map, насчитать количество каждого числа, а затем пройтись по нему и вычислить ответ используя комбинаторные формулы. Степени двойки предварительно насчитать. Идем по map и скажем видим число 1, тогда надо найти число 2 - 1 = 1, 4 - 1 = 3, 8 - 1 = 7... И дальше перемножить количества этих чисел и чтоб не было повторений поделить на 2. Если само число является степенью двойки то надо еще в ответ добавить количество комбинаций между равными числами. Ну например есть 3 двойки, 2 + 2 = 4 степень двойки, значит надо добавить в ответ 3 * (3 - 1) / 2. Вот такой код заходит.
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//GNU C++11
#include <bits/stdc++.h>
 
using namespace std;
using int64 = long long;
using uint64 = unsigned long long;
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); // Эти 2 строки для ускорения ввода, порой в олимпиадных задачах без них решение может упасть по времени
    uint64 n;
    cin >> n;
    map <int64, uint64> cnt;
    for (uint64 i = 0; i < n; i++) {
        int64 t;
        cin >> t;
        cnt[t]++;
    }
    vector <int64> pow2;
    for (int64 p = 1, h = 1e18; p <= h; p *= 2) pow2.push_back(p); // Степени двойки
    uint64 ans = 0;
    for (auto& i: cnt) {
        for (auto& j: pow2) {
            if (j == 2 * i.first) {
                ans += i.second * (i.second - 1);
                continue;
            }
            auto it = cnt.find(j - i.first);
            if (it != cnt.end())
                ans += it -> second * i.second;
        }
    }
    cout << ans / 2;
}
 
Текущее время: 23:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru