Настройки поиска (Страница 1 из 2)

nlast == cur

Можно такую динамику:
f(n, last) = count - количество таких разложений в сумму степеней двоек, что последнее из слагаемых last. Тогда ответ сумма по last для n.
Рекуррентность такая: f(n, last) = sum(f(n - last, i), i <= last и i - степень двойки), база динамики: f(2^i, 2^i) = 1.
Можно ускорить ДП, если считать не количество разложений, что последнее из слагаемых last, а количество разложений, что последнее не больше last.

*Ну и вторым параметром можно просто степень двойки сохранять, а не само число. Сложность будет что-то типа O(N * log(N))

Тест:
Количество вершин = 7, количество ребер 6
Граф:
1 - 2
2 - 3

4 - 5
5 - 6
6 - 7
7 - 5

Вершин со степень 0 нет, количество ребер = количество вершин - 1.
Без проверки на связность видимо никак.

Вот тут метод отжига касательно именно этой задачи http://rain.ifmo.ru/cat/data/theory/uns … rticle.pdf
Может поможет.

A = a * 10^X = 10^(lg(A) - floor(lg(A))) * 10^floor(lg(A))
a = 10^(lg(A) - floor(lg(A)))
вместо 123456 получиться 1.23456 * 10^5

Ответ соответственно будет floor(a * 10^(k - 1))

http://www.cplusplus.com/reference/clib … rt/assert/
http://www.cplusplus.com/reference/clib … ib/malloc/

char s[10];
while(scanf("%s", s) > 0)
{
}

2mincer,
"В разборе написана вот такая формуала:":
Допустим надо посчитать матожидание E[x], количество шагов, что мы куда-то дойдем из вершины X, для простоты положим, что у нас ациклический граф. Пусть из нее исходит набор дуг, скажем в Y1, Y2, Y3 и вероятности переходов p1, p2, p3. И обозначим за P[X, steps] - вероятность дойти куда надо из X за steps шагов. Ну и для простоты положим, что пути максимум длины 2.
Тогда будет что-то такое:
E[x] = p1 * P[Y1, 0] * (1 + 0) + p1 * P[Y1, 1] * (1 + 1) + p1 * P[Y1, 2] * (1 + 2) +
p2 * P[Y2, 0] * (1 + 0) + p2 * P[Y2, 1] * (1 + 1) + p2 * P[Y2, 2] * (1 + 2) +
p3 * P[Y3, 0] * (1 + 0) + p3 * P[Y3, 1] * (1 + 1) + p3 * P[Y3, 2] * (1 + 2)
Теперь несколько упростим выражение (разделим его на части, где наш текущий щаг (1 + ), и ту часть которую мы прошли после того, как перешли по ребру)
E[x] = p1 * P[Y1, 0] * 1 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 1 +
p2 * P[Y2, 0] * 1 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 1 +
p3 * P[Y3, 0] * 1 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 1 +

p1 * P[Y1, 0] * 0 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 2 +
p2 * P[Y2, 0] * 0 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 2 +
p3 * P[Y3, 0] * 0 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 2;

Теперь во второй части, вынесем p1, p2, p3:

E[x] = p1 * P[Y1, 0] * 1 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 1 +
p2 * P[Y2, 0] * 1 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 1 +
p3 * P[Y3, 0] * 1 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 1 +

p1 * (P[Y1, 0] * 0 + P[Y1, 1] * 1 + P[Y1, 2] * 2) +
p2 * (P[Y2, 0] * 0 + P[Y2, 1] * 1 + P[Y2, 2] * 2) +
p3 * (P[Y3, 0] * 0 + P[Y3, 1] * 1 + P[Y3, 2] * 2);

P[Yi, 0] * 0 + P[Yi, 1] * 1 + P[Yi, 2] * 2 -- это мат-ожидание дойти куда надо из Yi. Перепишем выражение с учетом этого:

E[x] = p1 * P[Y1, 0] * 1 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 1 +
p2 * P[Y2, 0] * 1 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 1 +
p3 * P[Y3, 0] * 1 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 1 +

p1 * E[Y1] + p2 * E[Y2] + p3 * E[Y3];

Теперь посмотрим на первую часть -- там сумма вероятностей по _всем_ возможным путям из X до "куда надо дойти", а сумма вероятностей по всем путям = 1
Получаем:
E[x] = 1 + p1 * E[Y1] + p2 * E[Y2] + p3 * E[Y3];

"Еще одна задача, на этот раз с NEERC 2006": Там dp'шкой можно решить, состояния это набор связных компонент, если одна компонента, то E = 0, если несколько, то если добавлять ребро между компонентами, то понятно, как, просто по той формуле, что в картинке, а если ребро в самой компоненте, то получается петля, ее нужно разрешить: скажем у нас С ребер которые мы можем провести и они лежат в какой-то компоненте, а E' = sum(E[состояние после соединения вершин ребром, которые в разных компонентах]), тогда матожидание для всех ребер будет E = 1 + E' + E * p * C => E = (E' + 1) / (1 - C * p)
Вот как-то так.

Возможная идея решения:
1. Зафиксируем какой-то отрезок, тогда каждая параллельная прямая будут давать геометрическое место вершин, которые будут образовывать с отрезком треугольники одной и тойже площади (S = 0.5 * a * h_a). Видно что из таких параллельных прямых нас интересует ближайшая к нашему отрезку и любая точка на этой прямой.
2. Проведем через все точки вертикальные прямые и найдем их порядок, далее будем вращать прямые вокруг точек, их порядок поменяется в случае, когда две какие-то прямые совпадут (на этой прямой будет расположен какой-то отрезок) - эти две прямые просто поменяются местами после совпадения при вращении дальше.
3. Сделаем события -- отрезок, и упорядочим их по углу накланной прямой проведенной через этот отрезок и будем просматривать их в этом порядке. Будем обходить события, поддерживая текущий порядок прямых.
При событии - меняем две соответствующие прямые, а также смотрим первые несовпадающие по одну сторону от прямой и по другую сторону от прямой ((в текущем порядке), для каждого отрезка вершина с минимальной площадью будет лежать на одной из этих прямых - выберем из них минимум для этого отрезка, а затем и минимум по площадям для каждого из отрезков и получим ответ.

2 2rf, pair'ы сравниваются не только по первым элементам, а сначала по первым, а в случае равенства их - по вторым. make_pair(1, 2) < make_pair(1, 3)

Число является полным квадратом, если каждый простой делитель его входит в него с четной степенью.
Разложим все числа Ai на простые делители, тогда нас будут удовлетворять те подмножества чисел, у которых по каждому из простых делителей суммарная степень - четная.
Тогда получаем систему уравнений по модулю 2:
Переменные это x1, .., xn -- используем число или нет, а уравнение это для каждого простого числа p_i сумма по j = 1 .. n: степень p_i в числе a_j * x_j = 0.

Количество решений этой системы минус 1 (это то что непустых множеств) будет ответом задачи.
Количество решений это 2^(n - rankA), где rankA - это ранг матрицы соответствующей системе.