Wataru

У вас порядок проверок нарушен.

Сначала надо проверить, что знаменатель не ноль, а только потом, что вся дробь неотрицательна.
Для проверки, что логарифм не берется из отрицательного числа надо проверить именно это (что выражение под логарифмом >=0). Вы же почему-то проверяете, что оно равно нулю.

И еще у вас выражение неправильно считается. Надо скобки расставить. (sqrt(X - 5 / X * X - 9) подсчитает корень из x минус 5, деленное на x^x, минус 9 - 3 слагаемых, из которых только второе дробь.

Итого вам надо:
- переставить местами условия, чтобы деление на 0 было первым.
- исправить условие на логарифм из отрицательного числа
- расставить скобки в выражении.

Поменяйте < на > там, где у вас сравниваются элементы. Подсказка: у вас массив передан двумя int указателями. Т.е. сами элементы - это там где вы разименовываете какие-то указатели (это операция *что-то).

Смотрим в документацию.

У шаблона std::priority_queue 3 параметра - тип элемента, контейнер и компаратор.
priority_queue хранит элементы в заданном контейнере, поддерживает там какую-то свою структуру (кучи) используя переданный компаратор для быстрой реализации операций приоритетной очереди.

Дефолтный контейнер - vector и компаратор стандартный std::less, поэтому работает просто priority_queue, например.

Вам может понадобится передавать свой какой-то контейнер, если вы хотите, например, аллокатор поменять. Или вы знаете, что в очереди будет почти всегда ровно K элементов, и вы передаете какой-то свой контейнер, который сразу же один раз выделяет K элементов.

Однако, если вам надо поменять только компаратор (третий параметр), то передать второй параметр тоже придется. Ну, вот перепутали порядок параметров разработчики стандарта. Нельзя задать компаратор, не задав и контейнер. Поэтому, надо писать там vector<> во втором параметре.

Edit. Там же в документации написано, что компаратор должен возвращать true, если первый элемент строго меньше второго. Ваш пример компаратора - похоже правильный. Однако, учтите, что очередь выдает сначала максимальный элемент. Т.е, если вам нужна очередь на минимум, то вам надо поменять знак в компараторе.

Один момент меня смущает: зачем вы внутри DFS не вызываете cycle когда у вас есть ребро в p? Это цикл длины 2 - вполне нормальный цикл. Или по условию задачи такие надо исключить?

А главная ошибка - надо при выходе из dfs помечать вершину другим цветом - как обработанную (например, 2). Чтобы color == 1 только у вершин, которые в стеке. При этом в самом Dfs нужно рекурсивно вызываться только отвершин с color == 0.

Допустим, у вас в графе есть ребро 2->1 и все. Вы вызоветесь от вершины 1 в цикле в main, ничего не найдете. Потом вызоветесь от вершины 2, найдете ребро в уже обработанную вершину и среагируете на это, как на цикл. Хотя это не цикл.

Да, могут быть нужны. Про то, что ограничения порядка 10^5 - это не факт. Может быть и задача, где ограничения меньше, а решение сложнее.

Потом, еще важные алгоритмы - максимальное паросочетание, максимальный поток и максимальный поток минимальной стоимости (в порядке увеличения сложности и уменьшения частоты).

Далее, что за дерево отрезков на графе?! А еще дейкстра может быть написан за (n+m)logn. И форд-беллман работает за nm, а не n^2.

Почему не работает жадность? Вы же сами привели тест, на котором такая жадность не работает.

Могу еше привести пример. В {1, 2, 3, 2, 1} - ответ 3. Тут надо удалить отрезок 1..5, потом 2..4, потом 1 вхождение элемента 3, Если же форма будет немного другая, например {1, 100, 1000, 100, 1} - то ответ 4. После первого удаления отрезка надо удалять числа по одному.

В общем случае, жадное решение не работает, пока не доказанно обратное.
Одно ваше наблюдение, действительно, истинно - в оптимальном решении сначала делаются какие-то удаления отрезков, а потом удаляются целиком оставшиеся элементы по одному.



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

Пока вы так не докажите свой алгоритм, можно смелло считать, что есть еще какой-то тест, где он выдаст не оптимальный ответ.

Подсказка1: посмотрите на ограничения. n всего лишь 5000. Значит, подразумеватся решение за квадрат. Посмотрите на теги.

Подсказка2: Можно смотреть на эту задачу так - есть башенки из кубиков высоты a[i]. Можно за раз или покрасить вертикальный отрезок башни у самого верха, или покрасить какой-то горизонтальный отрезок кубиков. Надо покрасить все кубики за наименьшее количетсво шагов. Тут только неочевидно, почему нужно красить горизонтальные отрезки, ведь несколько операций удаления отрезка могут пересекатся. Но тут поможет рассуждение как выше, через изменение любого ответа. Эти операции можно сложить как доски, в виде пирамид, т.ч. верхние операции целиком лежат в нижних операциях. От этого ответ станет не хуже.

Еще подсказка, подумайте, как можно убрать самый высоко стоящий кубик, какие варианты?

В общем случае, чтобы найти все циклы длины n надо подсчитать Tr(A^n)/n. A - матрица смежности. Tr() - это след (сумма элементов на диаганали). Т.е. возводите матрицу смежности из 0 и 1 в степень n и суммируете элементы по диагонали. Делить на n надо, потому что тут циклы считаются ориентированными и упорядочеными. Т.е. A->B->C посдчитается отдельно от B->C->A. Если граф неориентированный, то надо будет дополнительно поделить на 2 в конце.

Важно, тут будут считаться циклы, ходящие по одним и тем же вершинам и ребрам. Но для n=3 это не важно, если только у вас петель в графе нет.

Для n=3 можно чуть быстрее - возвести матрицу в квадрат и получить матрицу количеств путей длины 2. Потом можно пройтись по всем ребрам и просуммировать все циклы с этим ребром (известное уже количество путей длины 2 между двумя концами ребра). Тут как бы последнее, третье умножение пропускается и вместо него считаются только элементы на диагонали. Потом надо будет поделить на 3, потому что тут вы считаете каждый цикл 3 раза.

Можно воспользоваться быстрым умножением матриц Штрессена или присобачить какое-нибудь битовое сжатие, как я уже советовал вам в этом вопросе.

В зависимости от размерности матрицы (количества вершин) битовое сжатие может быть быстрее Штрассена или какого-либо другого быстрого алгоиртма умножения матриц.

Вам ДАНА матрица. Значит в программе надо
1) прочитать числа N и M (заведите 2 переменные и прочитайте их, через cin)
2) Завести N*M матрицу. В C++ стандартом для массивов является класс vector. Двумерный массив - это вектор векторов.
vector<vector<int>> a(n);
Это создаст вектор из n векторов, но они все будут пустые. Надо во время считывания ( у вас будет 2 вложенных цикла) перед считыванием i-ой строки i-ый вектор отресайзить вызвав a[i].resize(m). И далее можно будет читать a[i][j]
3) Теперь, собственно, алгоритм. Найдите наибольший элемент. Для этого заведите 3 переменные - текущий максимум (можно инициализировать a[0][0]) и его координаты mx и my (инициализируйте нулями). Пройдитесь по матрице двумя вложенными циклами и, если текущий элемент больше максимума - перезапишите максимум и запомните текущие переменные циклов в mx и my.
4) Теперь поменяйте местами 0-ую строку со строкой в которой максимум. Для этого одним циклом пройдитесь по столбцам (от 0 до M-1) и поменяйте местами a[0][j] и a[mx][j].
5) Теперь то же самое, но по столбцам. Цикл от 0 до N-1 и меняйте элементы a[i][0] и a[i][my].
6) В конце выведите матрицу двумя вложенными циклами.

Для смены двух значений нужна временная перменная, например tmp.

Попробуйте читать через scanf.

Я вижу, вы делаете через sync_with_stdio(0), но я не уверен, что это 100% помогает.

Потом, вместо set vis достаточно передавать в dfs предыдущую вершину и не ходить в нее.

А еше у вас ошибка, при делении ребра пополам нельзя делить пополам cnt*w. Если cnt четное, а w нечетное, вы потереяете округление. Надо пихать в кучу пару cnt, w, и брать максимальное cnt*ceil(w/2). И еще, вы пихаете в кучу цену ребра, помноженную на количество листьев по этому ребру и всем предыдущем в текущей вершине! Надо там не cur брать, а значение dfs.

И еще, оно скорее всего виснет из-за переполнения. При умножении cur*c.second может получиться отрицательное число, вы же int-ы перемножаете, и только потом к long long приводите.

Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
Если у вас числа 4,4,4,4,5,6,1,1 - то выгодно брать именно 6, потому что оно сделает второй бит единицей, что никак невозможно сделать, взяв 5.
У вас неправильное решение задачи.

Правильное решение такое: Найдите самый старший бит, в котором нечетное количество единиц в массиве a.

Если таких нет - то ответ Draw. Потому что, если в каком-то разряде единиц четное количество, и x из них достанется первому игроку, то второму достанется 2k-x, что будет иметь ту же четность, что и x. А значит в этом разряде итоговые значения отличаться не могут вообще. Как числа не распределяй, даже если игроки могут делать разное количество ходов.

Теперь мы знаем, что в этом разряде различие точно будет. Потому что нельзя нечетное количество единиц распределить на 2 группы с одинаковой четностью. Победа определяется только этим разрядом, ведь он самый старший из различий. Теперь у нас есть 2k+1 чисел c 1 в этом разряде и n-2k-1 чисел с 0 в этом разряде. На биты дальше смотреть не надо - кто возьмет нечетное количество чисел из 2*k+1 - тот победил.

Т.е. вам дальше надо решить совсем простую задачу: Дана пара чисел (i,j), i - нечетно, есть i нужных объектов и j ненужных, игроки по-очереди берут объекты. Кто возьмет нечетное количество нужных объектов - тот и победил.

Тут для вывода решения можно написать динамическое программирование, которое для пары (i,j) - будет говорить, сможет ли игрок взять четное/нечетное количество нужных чисел, если их i, и еще есть j ненужных. При расчете перебирайте варианты, какой из типов объектов берется и смотрите, а сможет ли оппонент вам четность испортить на меньшей задаче.

Дальше надо посмотреть на паттерн на маленьких числах и составить решение, потому что вся эта динамика у вас по времени не зайдет для данных ограничений.

Мне лень решать дальше задачу, но похоже, что при i=1 ответ - WIN, при i>0 - ответ Win, если i+j=n - четно. Иначе - Lose.

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.

У вас при вычислении cache числа не берутся по модулю. А значит очень быстро переполняют long long и случается фигня. Ведь цикл может начаться на очень больших числах. Вам надо всегда при вычислении брать по модулю m.

И, очевидная оптимизация - так как у вас fib() вызывается от увеличивающихся по порядку индексов, вы вместо функции делайте сразу же seq.push_back((seq[i-2]+seq[i-1]) % m);

Это классическая задача о рюкзаке.

Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
Пересчет:

F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))

Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

Есть одна хитрость при реализации - можно обойтись только одной строкой этой матрицы, если вам не нужно восстанавливать весь набор книг в ответе, а только его лучшее значение (только надо поменять параметры местами - строка размером с максимальную цену). Это сократит потребление памяти в K раз, если у вас K книг. На скорость работы решения это не влияет.

Сначала реализуйте все дп на матрице снизу вверх, двумя циклами.
Теперь, если вы будете гнать внутренний цикл с конца к началу, то вам не понадобится смотреть на уже переписанные на текущей итерации внешнего цикла значения, и можно забить на второй параметр ДП и просто переписывать строку на месте.

Про модули уже отвечено, я расскажу, как решать эту задачу быстрее, чем полным перебором.

Пусть общее количество карт - N.

Для простоты понимания, давайте забудем про колоду, просто карты раздаются как-то в 2 кучки по N/2 карт. Это пригодится попозже. Удобнее не вероятность считать, а количество способов раздать карты. Потом надо будет поделить количество хороших способов на все способы.

Сразу комбинаторно подсчитаем, сколько всего способов есть. Это просто количество всех различных колод. Гуглите "перестановки с повторениями". Формула будет такой:
N!/ a[1]! ... a[n]!
Раз мы на это число в конце будем делить, то сразу же считайте перевернутую формулу: подсчитайте факториал числа всех карт по модулю, обратите, умножьте на все маленькие факториалы.

Теперь самое главное, подсчитаем количество способов раздать карты так, что у всех поровну уникальных карт.
Динамическое программирование DP(k, t, i, j) - сколько способов раздать первые k типов карт так, что у первого игрока t карт всего, из них i уникальных, а у второго игрока j уникальных карт (при этом мы знаем, сколько у него всего карт - a[1]+...+a[k] - t).

База:

DP(0,0,0,0) = 1,
DP(0,*,*,*) = 0

Ответ:
sum {i=1..n} DP(n, N/2, i, i)

Пересчет:

DP(k,t,i,j) = sum{v=0..min(a[k],t)} DP(k-1, t-v, i - {v>0}, j-{v < a[k]}) * C(t, v) * C(a[1]+a[2]+...+a[k]-t, a[k]-v)

Тут надо объяснить: мы перебираем, сколько карт последнего типа досталось первому игроку: v. Это все разные колоды, поэтому их надо суммировать. Как бы убираем все карты этого последнего типа из рассмотрения. Что остается? То же самое ДП, но типов на 1 меньше, у первого игрока на v карт меньше и уникальные карты надо уменьшить на 1, если какому-то игроку хоть одна карта досталась. Но есть еще множители - это количество сочетаний. Эти самые v карт последнего типа могут быть на любом из t мест в колоде у первого игрока. Аналогично для второго игрока. Тут надо умножать, потому что любую колоду из предыдущего состояния ДП можно разбавить картами последнего типа в разных позициях и все эти способы дадут разные результирующие колоды. Надо домножить на оба сочетания, потому что мы независимо можем тасовать карты у первого и второго игрока.

Сочетания считаются факториалами С(n,k) = n!/ k! (n-k)!.
Я бы посоветовал предподсчитать все факториалы до 500 по модулю в массив, а так же обратные к ним.

Еще, если не будет влезать по памяти, обратите внимание, что в ДП достаточно хранить лишь 2 слоя по первому параметру. Т.е. надо места для 2*500*50*50 элементов, что для 4-х байтных значений будет занимать ~10mb памяти. Может даже long long можно хранить. Но тут надо переписать ДП снизу вверх, а не рекурсивно. Просто посмотрите, какие состояния куда плюсуются и с какими множителями. В этом случае вы будете не убирать карты последнего типа, а добавлять карты нового типа. Опять же, перебирайте сколько кому этих карт достанется. Надо только осторожно смотреть множители - С(сколько карт после добавления, сколько добавили).

Теперь прикинем на коленке сложность вычислений таким алгоритмом.
Само ДП имеет состояний 50*500*50*50 и пересчет 11 вариантов. Если все перемножить, получается что-то меньше 700 миллионов - в одну-две секунды должно влезать.

Полный перебор у вас, занимает что-то типа 11^50 - никогда не дождетесь на сколько нибудь не тривиальном тесте.