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

И так на 4e7, получилось что оба алгоритма работают приблизительно одинаково около 1,7 секунд.
Из этого вывод что линейный алгоритм хуже,так как он требует массив длинной N типа (INT), тогда как второй алгоритм требует массив длиной N, но типа (BOOL), что сокращает количество памяти в четыре раза.

Ыыыы
Он не может работать быстрее логически. Подумай разумно. Там линейно, тут больше гораздо.
Тогда нужно писать вот так,вместо +, использовать умножить,и это ускорит во много раз твою программу.

int n = (int)1e7;
vector <bool> prime(n+1,true);
for(int i=2;i*i<=n;i++)
    if(prime[i])
        for(int j=i*i;j<=n;j+=i)
            prime[j]=0;

Стой ? Может друг друга не до поняли
Я говорю,что вот задача допустим :
Есть поле,на котором допустим есть связные области ... Их надо замостить плитками 2х1, или 1х2
Причём мы можем определить куда можно положить плитку(то есть как и в задаче выше по окраске подходило и так далее)
Нужно замостить максимальным кол-вом плиток,или просто проверить можно ли это сделать...
Так вот эту задачу можно очень просто решить потоком. Ты про это ?

Может всё таки можно,так как для плиток 2*1 мы умеем,добавить вершин каких-нибудь.
Но лучше ДП, и тем более в твоём сообщении мелькнуло слово "почти" 

Непонятен вопрос, скорректируйте пожалуйста своё сообщение более точнее. P.S. БоТ

и таму и таму
я про себя говорил про точный ответ на запрос )

Ну во первых,в данной задаче можно писать за квадрат не мучать себя.

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

А если время нужно быстрое,и писать время не очень много,то есть альтернатива,которая хорошо будет работать даже при (N <= 100000), просто разобьём всю плоскость на SQRT(N) отрезков, тогда что получается,что бы перекрасить нам нужно максимум SQRT(N) операций,то есть просто пробежаться и покрасить нужные,а ответ на запрос тоже будет за SQRT(N), так как ты тем же пробегом можешь узнать самый длинный на текущий момент,так же для хорошего ускорения можно в процессе объединять отрезки одинакового цвета,что бы цвета чередовались,
и того Memory: O(N), Time: ~O(N * SQRT(N)).

а это расписание это Российское время ???
И ещё можно подсказать стратегию решения задач а то там кординально другая система

Если нужно написать что - то на Паскале попросите у меня,я напишу. Если нужно кучу напишу,только отпишите ещё раз о помощи

Да там всё по простецки-душ,туалет на улице,компьютеры в спортивном зале,и таксофоны стоят