Pagini recente » Diferente pentru heapuri intre reviziile 58 si 59 | Sandbox | Diferente pentru utilizator/zamorzaev intre reviziile 2 si 1 | Monitorul de evaluare | Diferente pentru siruri-de-sufixe intre reviziile 31 si 30
Nu exista diferente intre titluri.
Diferente intre continut:
$k = 1: 9 - - 1 5 - - 1 1 => d = 3, nu este bine;$
Cea mai mica valoare a lui $k$ pentru care distanta $d$ este suficient de mica reprezinta lungimea sablonului cautat (in cazul precedent $k = 5$). Pentru a obtine un algoritm de complexitate buna trebuie ca acest pas sa fie eficient; putem sa folosim un arbore de intervale, sa folosim un contor cu $k$ care variaza de la $1$ la $n$ si sa eliminam din arbore elemente de marime mai mica decat $k$ si, la fiecare pas, sa actualizam arborele pentru a putea raspunde la interogari de genul: _care este distanta maxima intre doua elemente care exista acum in structura_. Algoritmul are complexitatea $O(N log N)$. Pentru o prezentare amanuntita a arborilor de intervale, va recomand [9] si [10].
Cea mai mica valoare a lui $k$ pentru care distanta $d$ este suficient de mica reprezinta lungimea sablonului cautat (in cazul precedent $k = 5$). Pentru a obtine un algoritm de complexitate buna trebuie ca acest pas sa fie eficient; putem sa folosim un arbore de intervale, sa folosim un contor cu $k$ care variaza de la $1$ la $n$ si sa eliminam din arbore elemente de marime mai mica decat $k$ si, la fiecare pas, sa actualizam arborele pentru a putea raspunde la interogari de genul: _care este distanta maxima intre doua elemente care exista acum in structura_. Algoritmul are complexitatea $O(N log N)$. Pentru o prezentare amanuntita a arborilor de intervale, va recomand $[9]$ si $[10]$.
h3. *Problema 9* (Olimpiada Baltica de Informatica, 2004)
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.