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

Зачем за O(sqrt(n))?
Как минимум, тут можно бинпоиском с проверкой за O(1).

Но вообще, зная количество чисел на каждой диагонали(1,2,3,...), т.е. нам надо найти последнюю полную диагональ(такую которая лежит перед нашим числом). Получаем:

n*(n+1)<=a*2
n^2+n-a*2<=0

Решаем это неравенство и получаем номер диагонали за O(1).

Да тут походу и макс. паросочетание прокатит...
Но если в плитках будет более двух клеток, то этот метод работать не будет.

Я почти уверен что потоком тут никак нельзя, т.к. поток может делиться, а следовательно, нам не удастся плитку положить сразу на несколько клеточек, не ломая ее.

В этом куске кода:

forr(j,l,r) {
   w=f[j].x*a[i].x+f[j].y;
   if(w<fc || fc<0) { fc=w; l=j; } else break;
  }

Предполагается что если если A это номер участка f[j] в массиве a, то a(A).y=max(a(A).y,...,a(i).y), т.к. умножая на f[j].x мы умножаем на максимальную высоту участка от A до i. А почему тогда между A и i не может быть участка выше?

Спасибо за код. Избавление от ненужных это понятно. Я не могу понять как избавиться тут:

ans(i)=min(max(length[j],..,length[i])*width[i]+ans(j-1)) по всем 1<=j<=i

от

max(length[j],..,length[i])

Почему куб? Если без длинной арифметики(к примеру вывести ответ по какому-то модулю), то можно к примеру за O(NM).
f(i,j) это количество способов выбрать первые j символов строки s(в нужном порядке) в первых i символах text.
Тогда:
Если text(i)!=s(j), то f(i,j)=f(i-1,j)
Если text(i)==s(j), то f(i,j)=f(i-1,j)+f(i-1,j-1)

Диаметр дерева находится так(без доказательства):
Выбираем любую вершину, пускаем от нее поиск в ширину. Затем выбираем вершину, которая находится на наибольшем удалении от стартовой вершины. Утверждается, что она будет одним из концов диаметра. Чтобы найти второй конец диаметра - запустим поиск в ширину от первого и выберем самую удаленную вершину от него.

Сложность выходит О(Н).

Вместо сета лучше использовать priority_queue.

Ну как минимум, можно упростить эту реализацию используя обычный pair<int,int> и чтобы не засовывать в кучу отрицательное расстояние используя обычный оператор <, лучше объявить ее так:

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q.

Тогда просто

pair<int,int> a=make_pair(dist,num); 
Q.push(a);