Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Активные темы Темы без ответов
Настройки поиска (Страница 1 из 2)
Темы от MSDN Расширенный поиск
Сообщений найдено [ с 1 по 25 из 38 ]
Oleg пишет:Решил SKYLINE деревом отрезков. Кроме height еще сохраняй minValue и maxValue.
Скопировал в http://ideone.com/Njt4I если не разберешься.
Спасибо огромное.
Вообще была такая идея, ну или подобная. Но я ее откинул потому что тест можно придумать - типа "зубья", то есть сначала идет очень высокий прямоугольник, потом очень низкий, потом снова высокий и т.д. А потом можно добавить прямоугольник (по высоте выше низких и ниже высоких), который пересекает все эти "зубья" и получается что обновление произойдет за линейное время.
Здравствуйте!
Есть вопросы по нескольким задачам
SKYLINE
http://acmicpc-live-archive.uva.es/nuev … php?p=4108
Собственно похоже что задача на дерево отрезков... но вот как решать так и не придумал.
TUSK
http://acmicpc-live-archive.uva.es/nuev … php?p=4107
Вроде написал выметание... но потом понял что решение не канает вкорне.
Спасибо 
Здравствуйте!
http://acmicpc-live-archive.uva.es/nuev … php?p=4041
Как собственно решать данную задачу?
Судя по рейту - она должна быть простой... но чего то не могу придумать
Очень большое значение имеет величина потока. Мы вот недавно пропихнули поток на графе в 10000 вершин фордом фалкерсоном (всегда его пишем - просто в прикольной реализации)... потому что поток не большой был
Спасибо сдал Sky Code
Sky Code
То есть по сути если присмотреться получаеться формула включений и исключений. То есть генерим решетом все простые числа... затем считаем сколько всего способов набрать 4 числа из всех чисел... затем отнимаем числа которые состоят из одного простого числа (в смысле количество четверок чисел которые делятся на одно и тоже простое число), затем прибавляем которые состоят из двух, потом отнимаем из трех... и т.д.
А вот такой вопрос вы к этому решению пришли из каких то соображений теории чисел или нет? Просто может теорема какая нибудь есть....
По поводу Quick answer
Спасибо не заметил в условии строчку про то что при дисконекте, связи других компов не разрываются - так действительно все просто....
Здравствуйте!
У меня вопросы по нескольким задачам.
Sky code
http://acmicpc-live-archive.uva.es/nuev … php?p=4184
Собственно нашел на топ кодере обсуждение небольшое данной задачи... но все что я из него понял это то что нужно считать четверки чисел у которых НОД больше 1. Это значит что у всех четырех чисел есть как минимум один общий простой делитель...
GCD Determinant
http://acmicpc-live-archive.uva.es/nuev … php?p=4190
Нашел код решение этой задачи. Там просто перемножается все значения функций эйлера для всех чисел множества.... Собственно объяснения почему именно это будет ответом не нашел....
Quick answer
http://acmicpc-live-archive.uva.es/nuev … php?p=4188
Собственно сразу подумал про систему не пересекающихся множеств, но вот как реализовать действие изоляции одной вершины?
Именно фундаментальные циклы... Ищи баг..
Может правда там еще какие подводные камни есть... точно не помню... Но то что я ее фундаментальными циклами сдал эт точно... Можь там на связность проверь....
Здравствуйте!
http://acm.sgu.ru/problem.php?contest=0&problem=307
Задача похожа на 2-SAT, но вот не могу представить зависимость в 2-cnf форме.... То есть как бы СКНФ и СДНФ я выписал, но вот потом привести чего то так и не смог.... Либо очень долго и много выражений получается. Вообще есть алгоритм приведения к 2-cnf форме?
Спасибо. буду рисовать
Проверил - все верно. Формула такая же, просто ты грамотно обозначения ввел.
Спасибо что добавил...
Здравствуйте!
Почитал http://e-maxx.ru/algo/diofant_1_equation
Мне кажется необходимо добавить весьма важную вещь - решение может быть не единственно в кольце вычетов по модулю N. А именно количество решений будет либо 0 либо gcd(A,N). Ну и как их все найти:
d=gcd(A,N);
Если B%d!=0 То решений нет
Иначе
Xi = ((A/d)^-1)*(B/d) + i * (N/d)) mod N , где i принадлежит [0;d-1]
Xi - решение i-ое
(A/d)^-1 - обратный элемент в кольце
Мы тут про такой алгоритм и говорили... Просто его можно ускорить (немного) - Чтобы по каждой вершине не ходить по 100 раз, можно замемоизировать - то есть хранить список достижимых вершин из данной. Как это сделать эффективнее чем в лоб написано выше
Не ну как бы да если без карт битовых то P(n) = N
тогда время кубическое.....
Почему? Мы же каждую вершину обходим ровно 1 раз. То есть как бы обход запускаем много раз - но обойдет он в сумме ровно N вершин.
Асимптотика O(N+M*P(n)) где P(n) - время сливания двух битовых карт.
Ну вот у меня только такая мысль.... Найти для каждой вершины множество достижимых из нее вершин. Но! Хранить это можно эффективно - в виде битовой карты. То есть скажем множество из 1000 вершин можно представить не больше чем 20 числами типа long long.
Все это можно сделать за один проход в глубину. Обновление тоже очень быстро как битовая операция "или" для массива в 20 чисел.....
По поводу http://acm.tju.edu.cn/toj/showp3502.html
Мне кажется это больше похоже на бфс по состояниям, чем на минкост.... Для минкоста ограничения большие получаются.... Или может я не так решаю задачу?
Как бы в самом поганом случае получается N*N/2 вершин, то есть 450, для минкоста многовато. Я думал над тем чтобы уменьшить число вершин скажем представлять вершину как пересечение строки и столбца - но чего то так и не придумал ничего путнего....
Здравствуйте!
Я вот тут изучил эту штуку замечательную... Решил пару задач, с тимуса про фараонов по моему...
Народ пожалуйста киньте ссылок на задачи на эту тему... Так сказать чтоб закрепить
Здравствуйте!
http://acm.timus.ru/problem.aspx?space=1&num=1655
Собственно вопрос как решать? Дело в том что не первый раз встречаю данную задачу (похожие очень есть) и вот как ее решать эффективно не знаю....
Сконденсируем граф. Далее если в конденсации есть ровно 1 вершина со степенью входа 0, то это - база. База - множество вершин в графе из которых достижимы все вершины в графе. Но если вершин со степенью входа 0, больше одной - то базы нет. На самом деле очевидно почему.... так как из одной вершины со степенью входа 0 нельзя достичь другой такой же.
Аналогично - если в графе есть ровно одна вершина со степенью выхода 0, то это - антибаза. Антибаза - множество вершин доступное из всех вершин графа. Также если их больше одной то антибазы нету...
Re: Цикл (3 ответов, оставленных в Algo)
http://www.fi.muni.cz/ceoi1999/trip/TRIP.C - O(N^3)
вот так еще можно, тут кстати мне кажется константа поменьше будет... Так как в описаном алгоритме при помоще дерева кратчайших путей, нужно каждый раз еще перебирать все ребра не вошедшие в дерево.... а здесь практически чистый куб...
Здравствуйте!
http://acm.timus.ru/problem.aspx?space=1&num=1609
Собственно сначала естественно возникла мысль решать как то через динамику по профилю, но чего то так и не придумал ничего...
Потом подумал что можно на это дело посмотреть с точки зрения теории графов, а именно стандартно клетки образуют двудольный граф. В первую долу засовываем все клетки с нечетной суммой координат, а во вторую долу с четной, ребра есть между соседними клетками. Теперь укладка всего поля плиткой равносильна совершенному парасочетанию на данном графе, а наша задача сводиться к такой - зафиксировать минимальное количество ребер так чтобы совершенное паросочетание на оставшейся части графа было единственно... Собственно как это реализовать эффективно придумать немогу...
Спасибо. А можно если не трудно пояснить из каких соображений это вытекает?
Сообщений найдено [ с 1 по 25 из 38 ]