Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Активные темы Темы без ответов
Настройки поиска (Страница 1 из 2)
Темы от Zayakin_Andrey Расширенный поиск
Сообщений найдено [ с 1 по 25 из 28 ]
Tranvick пишет:Разбирал статью про теорему Шпрага-Гранди, но на эту задачу всё время выдает WA. Подскажите кто-нибудь, что у меня тут неправильно. Код: http://pastebin.com/m5vGBMvF Задача: acm.timus.ru/problem.aspx?space=1&num=1540
Расскажите лучше решение, код написан не сильно красиво, поэтому не очень хочется его читать.
Была тема на кодфорцес, можно разделить запрещенные слова на группы, для каждой группы по очереди построить бор, и для каждого бора сделать проход по тексту.
2rf пишет:А нету какого-нибудь простого алгоритма именно для LCP в отсортированном массиве циклических сдвигов, а не суффиксов?
Можно хешами за O(logN) - lcp двух соседних сдвигов.
Задача :
дан направленный взешенный граф без кратных ребер и петель (V <= 200, E <= 20000). Нужно покрыть его ориентированными циклами так чтобы каждая вершина принадлежала ровно одному циклу и сумма весов всех циклов была минимальна.
Решение :
построим двудольный граф, где в правой доле будут копии вершин. Если в графе было ребро (u; v) с весом w, проведем ребро из u первой доли в v второй доли c весом w. Теперь найдем максимальное паросочетание минимального веса. Если количество ребер равно количеству вершин исходного графа, то граф покрывается циклами и вес этого паросочетания равен искомой величине, иначе покрытия не существует.
Объясните, почему это правильно.
vanla пишет:Кстати, мне не очень понятно, почему размер массива должен быть в 4 раза больше количества элементов. Ведь, кажется, из самого построения алгоритма видно, что вершин в дереве 2n - 1. В чем я неправ?
В лучшем случае будет нужно 2n-1 памяти -- когда размер исходного массива степень двойки, вот представьте полное бинарное дерево, и посчитайте сколько оно будет занимать памяти. Если же размер не степень двойки, то размер исходного массива дополняют до степени -- отсюда и такая оценка.
А я в дереве хранил настоящие позиции удаленных комнат, с этой информацией тоже можно отвечать на запросы.
int dm[70000];
void solve() {
int n;
scanf("%d", &n);
memset(dm, 0, sizeof(dm));
dm[0] = 1;
int s = 0;
for(int i = 0; i < n; ++i) {
int w;
scanf("%d", &w);
for(int j = 2000000; j >= 0; --j) {
if (dm[j / 30] & (1 << (j % 30)) && j + w <= 2000000) {
dm[(j + w) / 30] |= (1 << ((j + w) % 30));
}
}
s += w;
}
int res = 3000000;
for(int i = 0; i < 2000001; ++i) {
if ((dm[i / 30] & (1 << (i % 30))) == 0 ) continue;
res = min(res, abs(s - i - i));
}
printf("%d", res);
}
ну перебор подмножест будет со сложностью O(2^n), динамика же O(n * M), где M максимальная сумма всех кучек
ну стандартный рюкзак правда он хуже по времени получается
по Quick Answer удалить значит создать новое множество из одной вершины, идентификатор которой будет M , где M наименьший достпуный идентификатор, и соответственно предыдущий идентификатор вершины уже использовать нельзя.
http://ideone.com/ZovYa
можешь посмотреть код
ну грубо говоря
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
вычислить F(i, j)
Знаю про bacs.cs.istu.ru задача 2097, можно MCF решить
в вершинах пересечние считается?
по-моему это задача называется гамильтонов цикл
brainail пишет:Zayakin_Andrey пишет:Уже была задача, сначала делаем обход из любой вершины, ищем самою дальнюю вершbну от начальной, из неё снова обход, который определит две самые удаленные вершины. сложность O(N)
Данное решение не будет работать на взвешенном дереве!
Оно будет работать если все рёбра по 1!
А что бы написать правильно то нужно писать как я сказал,
можно написать ещё быстрее чем я сказал,но думаю не нужно углубляться,
если и это вам не понятно,что достаточно при таком N,пустить с каждой вершины очередь или рекурсию и всё.
сори не заметил что граф взвешанный
Уже была задача, сначала делаем обход из любой вершины, ищем самою дальнюю вершbну от начальной, из неё снова обход, который определит две самые удаленные вершины. сложность O(N)
Уже была задача, сначала делаем обход из любой вершины, ищем самою дальнюю вершуну от начальной, из неё снова обход, который определит две самые удаленные вершины. сложность O(N)
Re: ДП (7 ответов, оставленных в Algo)
http://acm.timus.ru/problem.aspx?space=1&num=1087
В чем ошибка моего решения?
m[k] - по сколько можно брать
dp[ i ] - показывает выйгрышна, проигрышна или пока неизвестно про кучу с i камнями.
dp[0] - выйгрышна
для каждого m[k]
двигаемся по dp слева на право счетчиком i :
если dp[ i ] - проигрышна, то dp[i + m[k]] - выйгрышна
елси dp[ i ] - выйгрышна,
то если про dp[i + m[k]] неизвестно или она проигрышная,
то dp[i + m[k]] - проигрышная,
иначе ( dp[i + m[k]] - была выйгрышной )
dp[i + m[k]] - выйшрышная
затем смотрим на dp[n] и делаем вывод, если выйгрышная то первый выйграл, иначе второй выйграл.
Тема: ДП (7 ответов, оставленных в Algo)
В чем суть динамики по дереву? Где и когда применима ?
помогло только написание кучи
Ну сначала писалась обычная...
посмотрите кому не лень https://www.spoj.pl/problems/SHPATH/
я решал алгоритмом Дейкстры, расстояния хранил в set.
Получаю TL.
Что можете посоветовать?
Сообщений найдено [ с 1 по 25 из 28 ]