Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от brainail
Пишем обычный KMP, или Z-algorithm. Оба алгоритма описаны на сайте, или любой другой алгоритм поиска вхождений строки. Потом легко, в процессе поиска, можно сразу считать только не перекрывающиеся части и прибавлять к ответу.
Сложность : O(N), или O(N*log(N)) смотря как писать и чем.
Эта стандартная задача, запишем начало отрезков как начало события а конец отрезков как конец события в один массив всё.
Отсортируем, далее как в скобочной последовательности, пока последовательность не закрыта прибавляем длины отрезков к ответу. Пишется это пару минут.
Сложность O(NlogN).
Я вот это хотел пометить. Факторизация занимает такое же время,а что бы писать быстрые алгоритмы нужно кучу времени.
Можно ровно за O(sqrt(N)).
Просто перебираем все делители до корня, допустим это I,тогда N / I это тоже нейкий делитель,что бы не было повторов делителей просто припишем условие (I < N / I) тогда N / I тоже делитель.
Так да, и главное точность гораздо выше! 
Вектора ....... Говорю же писал что в голову лезит!
Пусть (X, Y) - сама точка.
(X1, Y1) - точка начала вектора, (X2, Y2) - точка конца вектора, луч (X1, Y1) -> (X2, Y2).
Для начала проверим что точка лежит на прямой (X1, Y1) - (X2, Y2) :
A = Y1 - Y2;
B = X2 - X1;
C = - A * X1 - B * Y1;
if (A * X + B * Y + C != 0) то можно смело говорить что тока не лежит, иначе она лежит но не понятна на какой стороне луча.
Теперь мы точно знаем что точка лежит на прямой, дальше можно действовать многими способами,я пишу что приходит первое в голову.
Проверим для начала что точка уже может лежать в отрезке вектора:
if (X >= MIN(X1, X2)) && (X <= MAX(X1, X2)) && (Y >= MIN(Y1, Y2)) && (Y <= MAX(Y1, Y2)) - то мы точно говорим что лежит,иначе возможен ещё 1 случай =>
Теперь мы проверим на отдалённость конца вектора и самой точки от начала вектора:
if (DIST(X1, Y1, X, Y) >= DIST(X1, Y1, X2, Y2)) то мы точно говорим ответ да, иначе точно ответ нет.
Если в решение требуется некоторая точность, то просто везде добавить проверки на EPS.
A = Y1 - Y2;
B = X2 - X1;
C = - A * X1 - B * Y1;
if (A * X + B * Y + C != 0) return "YES"; else return "NO";
if (X >= MIN(X1, X2)) && (X <= MAX(X1, X2)) && (Y >= MIN(Y1, Y2)) && (Y <= MAX(Y1, Y2)) return "YES";
if (DIST(X1, Y1, X, Y) >= DIST(X1, Y1, X2, Y2)) return "YES";
return "NO".Если делать само тупо, то проверяешь что точка принадлежит прямой вектора, а теперь просто смотришь, что она лежит с той же стороны что и конец вектора относительно начала вектора.
Можно просто перебирать отрезок с которого начнём искать ответ, далее начинаем бежать с этого отрезка постепенно сужая отрезок видимости,как только он стал невидим,значит предыдущий отрезок с отрезком с которого начинали будет некоторый ответ. И так далее. Сложность N^2...
Вот допустим что пишут об этом в википедии..
Симплекс метод
Мы запускаем обычную рекурсию, когда возвращаемся по ребру U -> V, обьеденяем два множества этих, при этом предком множества где лежит V (SET_ID(V)) ставим множество где лежит U (SET_ID(U)) -> P[SET_ID(V)] = SET_ID(U).
Теперь когда всё поддерево даннйо вершины U рассмотрено, мы просто начинаем бежать по запросам, которые связаны с U, Допустим это запрос U -> V, при
том мы смотрим что вершину V лежит в поддереве U,теперь что бы узнать их LCA,мы просто смотрим P[SET_ID(V)],что означает что мы смотрим предка который будем LCA для всего множества SET_ID(V).
Лучше всего написать и тщательно отладить или на листочке нарисовать и проделать ручной проход, тогда всё станет ясным.
Мне кажется здесь будет что-то похожее на динамику по "рваному" профилю.
Да, верно. 
Задача называется действительно комвияжор,и для решения такой задачи с весами рёбер обычно используют динамику описанную выше.
Т.к точек (N <= 20),то можно написать динамику по маскам,а именно
F(I, J) - минимальное время прохождения всех вершин маски I,при этом мы остановились в вершине J.
Дальше мы перебираем вершину которая не помечена ещё в маске,и следовательно переходим в новое состояние
F(newI, newJ) = MIN( F(newI, newJ), F(I, J) + DIST( J, newJ ) / V );
Где DIST( I, J ) - расстояние между точками I и J.
(I <= 2^N, J <= N).
Время работы ~O(2^N * N^2).
Память ~O(2^N * N).
Насчёт такой социальной рекламы - да, хорошая идея
Ну переписывать одно и то же на разные языки я точно не собираюсь, но если у кого-нибудь есть такой интерес - в wiki пожалуйста
А вот рекламы не будет. Точно. Не собираюсь изгаживать сайт этим :-D
Лучшее что я слышал!
Хм.. Я думаю статистика стала бы намного больше если бы каждый сообщил другу что есть такой замечательный сайт !!!
А если бы здесь предлагались коды на разных языках (что могли устроить и сами участники которые посещают сайт),то ещё больше людей
А ещё пихнуть рекламку! И зарабатывать 
Прикольно! Очень интересно! Спасибо!
Да,это я тоже видел,но я не умею нормировать 
у меня голова кружиться
Вроде самый "тупой" способ это что,будем искать (x2,y2) такую что она уже лежит на окружности.
Так как "Касательная к окружности перпендикулярна к радиусу, проведённому в точку касания",то по теореме Пифагора находим (расстояние R2 от (x1,y1) до (x2,y2),две другие стороны нам известны).
Теперь построим окружность (x1,y1,R2). Точки пересечения этой окружности и (x0,y0,R) и будут искомыми,можно выбирать любую (а так же любую точку на прямой касательной).
А как пересечь окружности и найти точки пересечения есть на этом сайте.
A zachem eto nado? Pokashute uslovie,moshet est' bolee vigodnie reshenia,ili voz'mite modul pomen'she (2^63).
http://informatics.mccme.ru/moodle/mod/ … pterid=217
Задачу можно решить методом Динамического программирования.
Допустим что нибудь -
F(i,j) - минимальное кол-во символов которое потребуется что бы забить шаблон первой строки по i-ый символ,
а так же забить этими же символами шаблон второй строки по j-ый символ.
Тогда допустим мы сейчас стоим на состоянии F(i,j),какие у нас есть варианты :
#1. (S1(i) = '?' ,S2(j) = буква) или (S1(i) = буква ,S2(j) = '?') или (S1(i) = '?' ,S2(j) = '?') или
(S1(i) = буква, S2(j) - буква,S1(i) = S2(j)),тогда F(i+1,j+1) = min(F(i+1,j+1),F(i,j)+1);
#2. (S1(i) = '*', S2(j) = '?' или буква),тогда перебираем for q = j+1 .. length(S2) -> F(i,q)=min(F(i,q),F(i,j)+T2(j,q)). (T1(i,j),T2(i,j) - кол-во не '*' в подстроке S1[i..j],S2[i..j] соответственно)
#3. (S1(i) = '?' или буква, S2(j) = '*'),тогда перебираем for q = i+1 .. length(S1) -> F(q,j)=min(F(q,j),F(i,j)+T1(i,q)).
То есть мы моделируем текущую ситуацию,и смотрим что можно поставить в текущий момент.
Ответ можно восстановить по предкам.
Сложность решения ~O(Len^3). (Для Len <= 80 это очень быстро).
Если бы были более большие ограничения,то можно было бы рассказать и идею быстрее,но это не нужно для данной задачи.
Прошу прощения если где допустил ошибку,пишу сонный
Если вам нужно только это...
Тогда можно написать сжатие чисел,чтобы все числа были (X <= N).
Это делается с помощью сортировки всех чисел,и каждому числу даём свой номер,при этом сохраняется соотношение
(X <= Y) -> (newX <= newY).
А теперь просто пишем Сумматор (Фенвика),и всё.
Ой Простите! Сайт долбанный! Конечно это не правильное решение:D *ROFL*
Ну во первых вполне нормальное решение у "chum",строим граф и по графу уже бегаем.
Ну а когда у нас есть граф нам нужно найти радиус графа,а алгоритмов его нахождения не так много хороших как я думаю,один из них лоб,второй вот как "chum",с серединки где нибудь пускать...
А на эту тему думаю в инете можно почитать неплохо статеек и оптимизаций.
MAXimal :: φορυμ » Сообщения от brainail