LogoArhiva Educațională
AcasaUsorMediuDificilAvansatOlimpiada de InformaticaIntroducere în C++AIBacalaureat

Stiva

În multe probleme în care lucrăm cu secvențe de valori, suntem nevoiți să procesăm valorile pe rând, asemenea unui teanc de obiecte. Pentru a formaliza acest proces, vom avea nevoie de o structură de date potrivită. În informatică, numim această structură de date stivă.

Noțiuni introductive

Ce este o stivă?

Stiva (în engleză, stack) este o structură de date liniară abstractă, pentru care sunt definite operațiile de adăugare a unui element și eliminare a unui element și aceste operații se realizează la un singur capăt al structurii, numit vârful stivei. În timpul operațiilor cu stiva avem acces numai la elementul din vârful stivei.

Operațiile pe care o stivă le poate efectua în timp constant sunt:

  1. push(x): Adaugă valoarea xx pe vârful stivei.
  2. top(): Spune care este valoarea de pe vârful stivei.
  3. pop(): Scoate elementul din vârful stivei.
  4. empty(): Spune dacă stiva este goală.

Observație

Valorile vor fi procesate conform principiului LIFO, adică last in, first out.

Probleme de bază

Problema stack

Kilonova

View Problem

Kilonova

Could not fetch problem details

Deschide

Această problemă ne cere să implementăm exact operațiile descrise mai sus.

Pentru a implementa aceste operații, avem două variante posibile:

Implementarea folosind un vector obișnuit

Pentru a implementa aceste operații fără a folosi vreo structură de date dinamică, putem face asta ținând un contor cu numărul de valori care se află la acel moment în stivă, astfel operațiile de ștergere și de verificare a dimensiunii stivei se fac raportându-ne la variabila pospos, iar adăugarea valorii se face pur și simplu crescând valoarea lui pospos.

#include <iostream>
using namespace std;

int stk[100001];

int main() {
    int t;
    cin >> t;

    int pos = 0;
    while (t--) {
        int tip;
        cin >> tip;
        if (tip == 1) {
            cin >> stk[pos++];
        } else {
            if (tip == 2) {
                pos--;
            } else {
                if (tip == 3) {
                    cout << stk[pos - 1] << '\n';
                } else {
                    if (pos == 0) {
                        cout << "YES" << '\n';
                    } else {
                        cout << "NO" << '\n';
                    }
                }
            }
        }
    }
    return 0;
}

Implementarea folosind std::stack

Stiva poate fi implementată și cu funcțiile din STL. Pentru mai multe detalii, vedeți implementarea și funcțiile descrise aici.

Se poate observa faptul că avem nevoie de biblioteca <stack> pentru aceste funcții.

#include <iostream>
#include <stack>

using namespace std;

int main() {
    int t;
    cin >> t;
    stack<int> st;

    while (t--) {
        int tip;
        cin >> tip;
        if (tip == 1) {
            int val;
            cin >> val;
            st.push(val);
        } else {
            if (tip == 2) {
                st.pop();
            } else {
                if (tip == 3) {
                    cout << st.top() << '\n';
                } else {
                    if (st.empty()) {
                        cout << "YES" << '\n';
                    } else {
                        cout << "NO" << '\n';
                    }
                }
            }
        }
    }

    return 0;
}

Problema stack_max_min

Kilonova

View Problem

Kilonova

Could not fetch problem details

Deschide

Problema ne dă un șir de numere și 4 întrebări pentru câte o poziție:

  1. Cel mai apropiat indice la stânga, unde elementul este mai mare decât poziția din întrebare.
  2. Cel mai apropiat indice la stânga, unde elementul este mai mic decât poziția din întrebare.
  3. Cel mai apropiat indice la dreapta, unde elementul este mai mare decât poziția din întrebare.
  4. Cel mai apropiat indice la dreapta, unde elementul este mai mic decât poziția din întrebare.

Vom precalcula, pentru fiecare element, răspunsul la fiecare tip de întrebare. Aici vom descrie algoritmul doar pentru primul tip, deoarece celelalte se rezolvă analog.

Vom parcurge vectorul de la stânga la dreapta, iar pe o stivă vom reține indicii cu elemente mai mici sau egale cu elementul curent. Cu alte cuvinte, pentru fiecare element, scoatem de pe stivă toate elementele mai mici sau egale cu el. Dacă stiva este goală, atunci răspunsul este −1-1, altfel este indicele elementului de pe vârful stivei. Apoi, îl adăugăm pe el însuși în stivă.

Observație

Pe stivă vom reține indici, nu valori. Acest lucru va fi valabil pentru o mare parte din problemele de stivă pe care le rezolvați.

Exemplu

Vom face o simulare a acestui algoritm, folosindu-ne de exemplul din problemă, v=[1 2 3 6 4 5 3 2 1 10]v = [1 \ 2 \ 3 \ 6 \ 4 \ 5 \ 3 \ 2 \ 1 \ 10]. Ca în problemă, vectorul va fi indexat de la 0.

  • Suntem la indicele 0, stiva=[]stiva = []. Răspunsul va fi -1.
  • Suntem la indicele 1, stiva=[0]stiva = [0], dar îl scoatem, iar apoi stiva=[]stiva = []. Răspunsul va fi −1-1.
  • Suntem la indicele 2, stiva=[1]stiva = [1], dar îl scoatem, iar apoi stiva=[]stiva = []. Răspunsul va fi −1-1.
  • Suntem la indicele 3, stiva=[2]stiva = [2], dar îl scoatem, iar apoi stiva=[]stiva = []. Răspunsul va fi −1-1.
  • Suntem la indicele 4, stiva=[3]stiva = [3]. Răspunsul va fi 3.
  • Suntem la indicele 5, stiva=[3 4]stiva = [3 \ 4], dar îl scoatem pe 4. Răspunsul va fi 3.
  • Suntem la indicele 6, stiva=[3 5]stiva = [3 \ 5]. Răspunsul va fi 5.
  • Suntem la indicele 7, stiva=[3 5 6]stiva = [3 \ 5 \ 6]. Răspunsul va fi 6.
  • Suntem la indicele 8, stiva=[3 5 6 7]stiva = [3 \ 5 \ 6 \ 7]. Răspunsul va fi 7.
  • Suntem la indicele 9, stiva=[3 5 6 7 8]stiva = [3 \ 5 \ 6 \ 7 \ 8], dar le scoatem pe toate, iar apoi stiva=[]stiva = []. Răspunsul va fi −1-1.

Această rezolvare are complexitatea O(N)\mathcal{O}(N), pentru că fiecare element va fi pus pe stivă și scos, deci se vor face cel mult două operații pentru fiecare.

Notă

Pentru a înțelege de ce complexitatea este liniară, puteți citi aici mai multe detalii.

Detalii de implementare: vom reține o matrice raspuns[tip−1][i]raspuns[tip - 1][i] care va reprezenta răspunsul la o întrebare de tipul tip itip \ i. De asemenea, vom folosi o santinelă, care va fi o valoare care va fi mereu mai mică (sau mai mare, în funcție de caz) decât orice valoare din vector. Pentru mai multe detalii, vezi implementarea de mai jos.

#include <iostream>

using namespace std;

#define MAXN 200000
#define MAXTIP 4
#define INFINIT 2000000000

int v[MAXN + 2], raspuns[MAXTIP][MAXN + 1], stiva[MAXN + 1];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, sp;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    // santinela
    v[0] = INFINIT;
    stiva[0] = 0;
    sp = 1;

    // intrebari de tip 1
    for (int i = 1; i <= n; i++) {
        // scoatem elementele mai mici sau egale
        while (v[stiva[sp - 1]] <= v[i]) {
            sp--;
        }
        raspuns[0][i] = stiva[sp - 1];  // primul element mai mare
        stiva[sp++] = i;                // adaugam i in stiva
    }

    // santinela
    v[0] = 0;
    stiva[0] = 0;
    sp = 1;

    // intrebari de tip 2
    for (int i = 1; i <= n; i++) {
        // scoatem elementele mai mari sau egale
        while (v[stiva[sp - 1]] >= v[i]) {
            sp--;
        }
        raspuns[1][i] = stiva[sp - 1];  // primul element mai mic
        stiva[sp++] = i;
    }

    // santinela
    v[n + 1] = INFINIT;
    stiva[0] = n + 1;
    sp = 1;

    // intrebari de tip 3
    for (int i = n; i >= 1; i--) {
        // scoatem elementele mai mici sau egale
        while (v[stiva[sp - 1]] <= v[i]) {
            sp--;
        }
        raspuns[2][i] = stiva[sp - 1];  // primul element mai mare
        stiva[sp++] = i;
    }

    // santinela
    v[n + 1] = 0;
    stiva[0] = n + 1;
    sp = 1;

    // intrebari de tip 4
    for (int i = n; i >= 1; i--) {
        // scoatem elementele mai mari sau egale
        while (v[stiva[sp - 1]] >= v[i]) {
            sp--;
        }
        raspuns[3][i] = stiva[sp - 1];
        stiva[sp++] = i;
    }

    int q;
    cin >> q;
    while (q--) {
        int tip, poz;
        cin >> tip >> poz;
        cout << raspuns[tip - 1][poz + 1] - 1 << "\n";
    }

    return 0;
}

Probleme rezolvate

Problema skyline

NerdArena

View Problem

NerdArena
Deschide

Pentru a rezolva această problemă, va trebui să aflăm pentru fiecare valoare care este cea mai apropiată poziție de la stânga și de la dreapta cu o înălțime mai mică decât cea curentă.

După ce aflăm aceste valori, tot ce trebuie să facem este să folosim sume parțiale pentru a calcula aria cerută pentru fiecare poziție.

#include <fstream>

using namespace std;

ifstream fin("skyline.in");
ofstream fout("skyline.out");

const int nmax = 40000;
int length[5 + nmax], height[5 + nmax], l[5 + nmax], stk[5 + nmax];
// l[i] = cel mai mare j < i pentru care height[j] < height[i]

int main() {
    int n;
    fin >> n;
    int ptr = 0;
    for (int i = 1; i <= n; i++) {
        fin >> height[i] >> length[i];
        length[i] += length[i - 1];  // fac sume partiale pe length[]
        while (ptr > 0 && height[stk[ptr - 1]] >= height[i]) {
            ptr--;
        }
        if (ptr == 0) {
            l[i] = 0;
        } else {
            l[i] = stk[ptr - 1];
        }
        stk[ptr++] = i;
    }
    ptr = 0;
    long long ans = 0;
    for (int i = n; i >= 1; i--) {
        while (ptr > 0 && height[stk[ptr - 1]] >= height[i]) {
            ptr--;
        }
        int r;  // r = cel mai mic j > i pentru care height[j] < height[i]
        if (ptr == 0) {
            r = n + 1;
        } else {
            r = stk[ptr - 1];
        }
        stk[ptr++] = i;
        ans = max(ans, 1ll * height[i] * (length[r - 1] - length[l[i]]));
    }
    fout << ans << '\n';
    return 0;
}

Problema unific

Kilonova

View Problem

Kilonova

Could not fetch problem details

Deschide

Mai întâi, vom defini urmatoarele două functii:

  1. canJoin(x,y)=1canJoin(x, y) = 1 dacă putem unifica xx si yy, 0 altfel
  2. join(x,y)=join(x, y) = rezultatul unificării dintre xx si yy

Sa simplificăm enunțul astfel: Găsim primul i(1<i≤n)i (1 < i \leq n) pentru care canJoin(ai−1,ai)=1canJoin(a_{i - 1}, a_i) = 1 (dacă nu există atunci terminăm procedeul). Setăm ai−1a_{i - 1} la join(ai−1,ai)join(a_{i - 1}, a_i) si scoatem aia_i din șir. Acum, dacă i>2i > 2 și canJoin(ai−2,ai−1)=0canJoin(a_{i - 2}, a_{i - 1}) = 0 continuăm căutarea de la i+1i + 1. Altfel, setăm ai−1a_{i - 1} la join(ai−3,ai−1)join(a_{i - 3}, a_{i - 1}) și continuăm tot așa.

Observăm că noi trebuie să scoatem elemente din șir, iar acest lucru nu este ușor într-un vector. Așa că, atunci când ajungem la ii, vom menține într-o stivă grupurile care s-au format până la ii. Apoi, cât timp stiva nu este goală, vom încerca să unificam vârful stivei cu aia_i. Dacă canJoin(top(),ai)=1canJoin(top(), a_i) = 1 atunci setăm aia_i la join(top(),ai)join(top(), a_i) și scoatem vârful. Altfel, adaugăm aia_i in stiva și continuăm cu i+1i + 1.

Sursa de 100 de puncte:

#include <fstream>

const int MAXN = 100'000;
const int MAXCF = 10;
const int FARA_CIFRE = -1;

std::ifstream fin("unific.in");
std::ofstream fout("unific.out");
int n, sp, fr[MAXCF], fra[MAXCF], frb[MAXCF];
long long v[MAXN], stiva[MAXN];

void readArray() {
    int i;
    fin >> n;
    for (i = 0; i < n; i++) {
        fin >> v[i];
    }
}

void getMostFrequent() {
    int i, max;
    long long val;
    for (i = 0; i < n; i++) {
        val = v[i];  // vrem sa pastram valoarea
        while (val > 0) {
            fr[val % 10]++;
            val /= 10;
        }
    }
    max = 0;
    for (i = 1; i < MAXCF; i++) {
        if (fr[i] > fr[max]) {
            max = i;
        }
    }
    fout << max << "\n";
}

void getDigitFrequencies(long long val, int fr[MAXCF]) {
    do {  // tratam si cazul val = 0
        fr[val % 10]++;
        val /= 10;
    } while (val > 0);
}

int canJoin(long long a, long long b) {
    int i;
    for (i = 0; i < MAXCF; i++) {
        fra[i] = frb[i] = 0;
    }
    getDigitFrequencies(a, fra);
    getDigitFrequencies(b, frb);
    i = 0;  // cautam prima cifra care apare la ambii
    while (i < MAXCF && (fra[i] == 0 || frb[i] == 0)) {
        i++;
    }
    return i < MAXCF;  // daca am gasit vreuna
}

long long removeCommonDigits(long long val, int other_fr[]) {
    long long p, rez;
    int cf, has_digits;
    p = 1;
    while (p * 10 <= val) {
        p *= 10;
    }
    rez = has_digits = 0;
    while (p > 0) {
        cf = val / p % 10;
        if (other_fr[cf] == 0) {  // daca nu e comuna
            rez = rez * 10 + cf;  // adaugam cifra
            has_digits = 1;
        }
        p /= 10;
    }
    return has_digits ? rez : FARA_CIFRE;
}

// consideram ca am aplicat inainte canJoin(a, b)
// asta inseamna ca fra si frb sunt calculate deja
long long join(long long a, long long b) {
    long long p, rez;
    a = removeCommonDigits(a, frb);  // numarul nou al lui a
    b = removeCommonDigits(b, fra);  // numarul nou al lui b
    if (a != FARA_CIFRE
        || b != FARA_CIFRE) {   // ambele dispar daca ambele n-au cifre
        if (a == FARA_CIFRE) {  // nu mai conteaza ca nu are cifre
            a = 0;
        }
        p = 1;
        while (p <= b) {
            p *= 10;
        }
        if (b == 0) {
            p = 10;  // si cifra asta trebuie luata in considerare
        }
        if (b == FARA_CIFRE) {  // setam la 0 ca sa nu ne afecteze rezultatul
            b = 0;
        }
        a = a * p + b;  // lipim numerele
    }
    return a;
}

void unifyArray() {
    int i;
    for (i = 0; i < n; i++) {
        while (sp > 0 && v[i] >= 0 && canJoin(stiva[sp - 1], v[i])) {
            v[i] = join(stiva[sp - 1], v[i]);
            sp--;  // scoatem varful din stiva
        }
        if (v[i] != FARA_CIFRE) {  // daca mai are cifre
            stiva[sp++] = v[i];    // adaugam elementul in stiva
        }
    }
    fout << sp << "\n";  // cate sunt
    for (i = 0; i < sp; i++) {
        fout << stiva[i] << " ";
    }
    fout << "\n";
}

int main() {
    readArray();
    getMostFrequent();
    unifyArray();
    return 0;
}

Problema swap

Kilonova

View Problem

Kilonova

Could not fetch problem details

Deschide

Notam cu SS șirul de paranteze. Pentru punctul a), în timp ce parcurgem șirul de paranteze, vom menține o stivă care va conține indicii parantezelor deschise cărora nu le-am găsit încă o pereche. De fiecare dată când dăm peste o paranteză deschisa, îi adaugăm indicele în stivă, iar atunci când dăm peste o paranteză închisă, top()top() va fi perechea ei. Adunăm la răspuns i−top()i - top(), scoatem vârful din stivă și continuăm cu i+1i + 1. Punctele b) și c) pot fi rezolvate împreună. Deducem următoarele trei cazuri:

  1. Si=Si+1S_i = S_{i + 1}, unde ii și i+1i + 1 sunt parantezele interschimbate. Atunci, răspunsul va rămâne exact la fel, deci nu este o operație swap validă
  2. Si=)S_i = \text{)} și Si+1=(S_{i + 1} = (. În acest caz, există un a(a<i)a (a < i) și un b(i−1\<b)b (i - 1 \< b)astfel încâtSa=(S_a = \text{(}, Sb=)S_b = \text{)}, și (a,i)(a, i), respectiv (i+1,b)(i + 1, b)formau perechi. Costurile lor însumate vor fii−a+b−i−1=b−a−1i - a + b - i - 1 = b - a - 1. Când interschimbăm SiS_icu Si+1S_{i + 1}obținem perechile(a,b)(a, b)și(i,i+1)(i, i + 1), ale căror costuri însumate dau b−a+1b - a + 1. Deci răspunsul a crescut cu 2, ceea ce înseamnă că nu este o operație swap validă.
  3. Si=(S_i = \text{(} și Si+1=)S_{i + 1} = \text{)}. Dacă nu există nici un a(a<i)a (a < i) astfel încât Sa=(S_a = \text{(} și perechea lui aa (pe care o notăm cu bb) să fie mai mare ca i−1i - 1, atunci operația nu ar fi validă, deoarece nu am avea pereche pentru SiS_i dacă Si=)S_i = \text{)}. Mai întai, avem perechile (a,b)(a, b) și (i,i+1)(i, i + 1). După cum am văzut la cazul 2, răspunsul ar fi mai mic cu 2 dacă perechile ar fi (a,i)(a, i) și (i + 1, b)\. Deci operația swap este validă.

Observăm că singurul caz în care operația swap este validă este atunci când Si=(,Si+1=)S_i = \text{(}, S_{i + 1} = \text{)} și există un a<ia < i, Sa=(S_a = \text{(}, a cărui pereche bb este mai mare ca i+1i + 1. Acest lucru se poate simplifica astfel: Căutăm un ii care respectă următoarele condiții:

  1. Si=(S_i = \text{(}
  2. Înainte să scoatem perechea lui ii, stiva trebuie să aiba cel puțin 2 elemente
  3. Vârful stivei trebuie să aibă valoarea i−1i - 1.

Deci noi, trebuie să numărăm câți ii respectă cele trei condiții. Dacă găsim vreunul, răspunsul este rez−2rez - 2, unde rezrez este răspunsul de la punctul a. Altfel, răspunsul este −1-1.

Sursa de 100 de puncte:

#include <fstream>

const int MAXN = 90'000;
const char DESCHISA = '(';
const char INCHISA = ')';

std::ifstream fin("swap.in");
std::ofstream fout("swap.out");
int stiva[MAXN], sp;

void calcAnswer() {
    int i, n, ch, cate;
    long long rez;
    fin >> n;
    rez = cate = 0;
    while ((ch = fin.get()) != '(')
        ;  // asta va fi mereu primul caracter
    for (i = 0; i < n; i++) {
        if (ch == DESCHISA) {
            stiva[sp++] = i;           // il adaugam in stiva
        } else {                       // INCHISA
            rez += i - stiva[sp - 1];  // distanta pana la pereche
            if (sp >= 2
                && stiva[sp - 1] == i - 1) {  // conditia sa fie valida operatia
                cate++;
            }
            sp--;  // scoatem perechea din stiva
        }
        ch = fin.get();
    }
    fout << rez << "\n" << (cate > 0 ? rez - 2 : -1) << "\n" << cate << "\n";
}

int main() {
    calcAnswer();
    return 0;
}

Problema Ehab and Prefix MEXs

Codeforces

View Problem

Codeforces

Could not fetch problem details

Deschide

Să presupunem că suntem la un indice ii și am reușit să construim tot prefixul [1,i−1][1, i - 1]. Dacă ai−1=aia_{i - 1} = a_i, atunci bib_i poate fi orice valoare mai mare ca aia_i. Vom ține elementele care au ai−1=aia_{i - 1} = a_i într-o stivă, deoarece ele pot lua orice valoare mai mare ca aia_i. Când ai−1<aia_{i - 1} < a_i, vom putea folosi elementele din stivă pentru a acoperi intervalul [ai−1,ai][a_{i - 1}, a_i]. Dacă în stivă sunt mai puțin de ai−ai−1−1a_i - a_{i - 1} - 1 elemente, atunci nu putem forma prefixul [1,i][1, i] și atunci răspunsul va fi −1-1. Altfel, setăm bib_i la ai−1a_{i - 1}. Apoi luăm primele ai−ai−1−1a_i - a_{i - 1} - 1 elemente, le setăm la ai−1+1,ai−1+2,..,ai−1a_{i - 1} + 1, a_{i - 1} + 2, .., a_i - 1 și apoi le scoatem din stivă. Restul elementelor, care au rămas în stivă după ce am trecut prin tot șirul, pot fi setate la n+1n + 1 sau la orice valoare mai mare ca nn.

Codul de Accepted:

#include <iostream>

const int MAXN = 100'000;
const int CANNOT = -1;

int n, a[MAXN + 1], answer[MAXN + 1], stiva[MAXN];

void readArray() {
    int i;
    std::cin >> n;
    for (i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
}

void buildAnswer() {
    int i, sp, pot, j;
    sp = 0;
    pot = i = 1;
    while (i <= n && pot) {
        if (a[i] == a[i - 1]) {
            stiva[sp++] = i;                    // il adaugam in stiva
        } else if (a[i] - a[i - 1] > sp + 1) {  // nu avem destule elemente
            pot = 0;
        } else {
            answer[i] = a[i - 1];
            for (j = a[i - 1] + 1; j < a[i]; j++) {
                // folosim elementul si il scoatem
                answer[stiva[--sp]] = j;
            }
        }
        i++;
    }
    while (sp > 0) {
        // setam restul elementelor la ceva care nu conteaza
        answer[stiva[--sp]] = n + 1;
    }
    if (pot == 0) {
        answer[0] = CANNOT;
    }
}

void writeAnswer() {
    int i;
    if (answer[0] == CANNOT) {
        std::cout << CANNOT << "\n";
    } else {
        for (i = 1; i <= n; i++) {
            std::cout << answer[i] << " ";
        }
        std::cout << "\n";
    }
}

int main() {
    readArray();
    buildAnswer();
    writeAnswer();
    return 0;
}

Concluzii

După cum se poate observa, odată ce deprindeți tehnicile folosite la problemele prezentate mai sus, soluțiile devin mult mai ușor de conceput, existând foarte multe similarități între problemele care implică folosirea stivei.

Probleme suplimentare

Bibliografie și lectură suplimentară

Coada

Previous Page

Analiza amortizată

Next Page

On this page

Noțiuni introductiveProbleme de bazăProblema stackImplementarea folosind un vector obișnuitImplementarea folosind std::stackProblema stack_max_minProbleme rezolvateProblema skylineProblema unificProblema swapProblema Ehab and Prefix MEXsConcluziiProbleme suplimentareBibliografie și lectură suplimentară