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

Задача на динамику с codeforce'a - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не работает реверс строки http://www.cyberforum.ru/cpp-beginners/thread1064994.html
Всем привет, ребятки! Я тут принялся работать с функциями обработки строк, и у меня возник вопрос. Вот вам сначала мой код: #include <iostream> #include <cstdio> #include <cstring> using namespace std; int main() {
C++ Запуск программы без создания окна. Запуск фоновой программы Вопрос, как сделать, чтобы консольное приложение при запуске не создавало окошко консоли. Т.е. запустился процесс, но визуально ничего не появилось. :) Очень криво спросил, но мне кажется понятно, что я имел в виду. интернеты подсказали использовать ShowWindow(GetConsoleWindow(), SW_HIDE); но это естественно не выход: запуск программы, на момент появляется консоль, и тут же... http://www.cyberforum.ru/cpp-beginners/thread1064985.html
Ошибка C++
Пдскажите пожалуйста в чём ошибка. Нужно быдо сделать задание: 27. Среди чисел 1, 1+1/2, 1+1/2+1/3, …найти первое, большее числа n. Вот код: #include <iostream.h> #include <conio.h> #include <math.h> int main () { int n; float result=0, i;
Двойное наследование C++
Доброго времени суток. Я делаю домашнее задание, в котором надо создать класс из него создать два производных класса, а потом из этих двух создать еще один. Только есть маленькая неувязочка. Некоторые методы наследуются из самого первого класса к двум дочернем, а потом к самому последнему и в этом месте получается, что вызывать эти методы нельзя, потому что не ясно из какого класса эти методы...
C++ Чтение из файла и запись числа в массив http://www.cyberforum.ru/cpp-beginners/thread1064961.html
Добрый день, уважаемые. Помогите. Есть файл func.txt, в котором через пробел записаны координаты X и Y точки на плоскости. Также есть функция, область определения которой задана прямоугольным участком: по X от -1 до 2 и по Y от -1 до 6. Чтение из файла я сделал, вывод на консоль тоже. Но вот как сделать проверку: принадлежит ли точка функции или нет? Больше всего не понятно с пробелом,...
C++ Найти количество элементов, встречающихся в обоих массивах Помогите решить хотя бы какую-нибудь задачу пожалуйста можно без инклюдов и прочей фигни просто функцию и массив подробнее

Показать сообщение отдельно
paladinama
0 / 0 / 0
Регистрация: 27.03.2013
Сообщений: 21

Задача на динамику с codeforce'a - C++

07.01.2014, 16:54. Просмотров 781. Ответов 0
Метки (Все метки)

Всем привет! Уже неделю не могу разобраться в решении задачи с codeforce'a. Собственно сама задача. А вот её разбор
Кликните здесь для просмотра всего текста
Есть несколько наблюдений, после которых задача становится очень простой. Первое наблюдение — пикать надо всегда самого сильного героя. А вот про баны ничего такого сказать нельзя, в разных ситуациях могут потребоваться самые разные баны. Самое важное наблюдение, которое поможет решить задачу — то, что рассматривать следует только m сильнейших героев. Действительно, при любой игре, где будут пикаться самые сильные герои в каждый момент времени, никакой герой, кроме первых m, не может быть пикнут вообще никогда. Значит, и банить их никогда не надо. И рассматривать тоже.

В итоге у нас остается в худшем случае 20 героев, а, значит, можно решить задачу динамикой по подмножествам: dpmask — разность между силами команд в ситуации, когда пикнуты либо забанены те и только те герои, чьи биты в маске установлены в единицу. Для переходов перебираем героя, которого команда, чья очередь хода, будет пикать или банить. Проще всего реализовать это с помощью рекурсии с сохранением. Ответ будет храниться в dp2m - 1.

К сожалению, мы неправильно оценили сложность этой задачи (несмотря на простое в реализации решение, придумать его, как выяснилось, было не так то и просто — стандартные 1500 баллов были бы лучше), и выставили неправильный TL (так что многие решения на C++ за m2·2m проходили — следовало опустить ограничение до одной секунды, а то и до 0.75 секунд). Так что если вы решили задачу за m2·2m, считайте, что вам повезло и что ваш вердикт — Time Limit Exceeded.

Почему можно писать это за m·2m? Потому что пропуск бана не имеет смысла: вместо этого можно забанить самого слабого героя из доступных — ведь его точно никто никогда не пикнет.

Здесь тоже были слабые претесты, поэтому можно было ломать тех, у кого в решении не было битмасок, чуть ли не любым большим случайным тестом.


Саму задачу я понял. Первая мысль была полным перебором, но это долго. Посмотрел решения других, но так и не смог понять, почему оно работает.
1. Почему 2m. Точнее почему 2? Если степень я еще могу понять, почему m, то почему 2.
2. Почему через биты. У всех решения через биты, но почему?
3. Да почему оно так должно работать?

Решения других можно посмотреть здесь. В фильтре справа выбрать задачу (E -Captains Mode), а вердикт - полное решение(или accept).

Может кто-нибудь объяснит, почему оно должно работать? =)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru