Tetris 2D – omówienie zadania

Tetris 2D – omówienie zadania

Szczegółowe omówienie zadania Tetris 2D:

Link do powyższego omówienia zadania Tetris 2D:
https://youtu.be/w9hcR2ZYsPc?t=987

Link do treści zadania Tetris 2D oraz możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/-0A1PC3fNc2RK-qvoUQKGGLl/site


Zadanie Tetris 2D jest szkoleniowym zadaniem pokazującym drzewa przedział-przedział:
https://youtu.be/hHNjFBxNO54?t=2197
Drzewa przedziałowe to sumy prefiksowe z mała obserwacją:
https://youtu.be/hHNjFBxNO54?t=2159
Wszystko jesteśmy w stanie udoskonalić:
https://youtu.be/hHNjFBxNO54?t=29


Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625


Kod C++ programu Tetris 2D, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;

const int MAX_ROZMIAR_DRZEWA = 1<<21;
int drzewo_max[MAX_ROZMIAR_DRZEWA];
int na_pozniej[MAX_ROZMIAR_DRZEWA];

int ZnajdzNajblizszaWiekszaPotegeDwojki (int liczba) {
 int najblizsza_potega_dwojki;

 najblizsza_potega_dwojki = 1;
 while (najblizsza_potega_dwojki < liczba)
    najblizsza_potega_dwojki <<= 1;

 return najblizsza_potega_dwojki;
}

void ZaktualizujSynow (int v) {
 if (na_pozniej[v] == 0)
    return;
 drzewo_max[2*v] = na_pozniej[v];
 drzewo_max[2*v + 1] = na_pozniej[v];
 na_pozniej[2*v] = na_pozniej[v];
 na_pozniej[2*v + 1] = na_pozniej[v];
 na_pozniej[v] = 0;
}

int ObliczMaksNaPrzedziale (int p, int k, int v, int a, int b) {
 int maks_syna_lewego;
 int maks_syna_prawego;

//pytanie poza przedziaem wierzchoka
 if ( (a > k) || (b < p) )
     return 0;

//wierzchoek cakowicie w pytanym przedziale
 if ( (a >= p) && (b <= k) )
     return drzewo_max[v];

//wierzchoek czesciowo w pytanym przedziale
 ZaktualizujSynow (v);
 maks_syna_lewego = ObliczMaksNaPrzedziale(p, k, 2*v, a, (a + b)/2);
 maks_syna_prawego = ObliczMaksNaPrzedziale(p, k, 2 * v + 1, (a + b)/2+1, b);
 return max(maks_syna_lewego, maks_syna_prawego);
}

void UstawMaksNaPrzedziale (int p, int k, int v, int a, int b, int wartosc) {
//pytanie poza przedziaem wierzchoka
 if ( (a > k) || (b < p) )
     return;

//wierzchoek cakowicie w pytanym przedziale
 if ( (a >= p) && (b <= k) ) {
     drzewo_max[v] = wartosc;
     na_pozniej[v] = wartosc;
     return;
 }

//wierzchoek czesciowo w pytanym przedziale
 ZaktualizujSynow (v);
 UstawMaksNaPrzedziale(p, k, 2*v, a, (a + b) / 2, wartosc);
 UstawMaksNaPrzedziale(p, k, 2*v + 1, (a + b) / 2 + 1, b, wartosc);
 drzewo_max[v] = max(drzewo_max[2*v], drzewo_max[2*v + 1]);
}

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

 int liczba_klockow, rozmiar_planszy;
 int liczba_przechowywanych_elementow, rozmiar_drzewa;
 int max_na_przedziale;
 int numer_poczatkowy_klocka, numer_koncowy_klocka, dlugosc_klocka;
 int i;

 cin >> rozmiar_planszy >> liczba_klockow;
 liczba_przechowywanych_elementow = ZnajdzNajblizszaWiekszaPotegeDwojki (rozmiar_planszy);
 rozmiar_drzewa = 2 * liczba_przechowywanych_elementow;

 for (i = 0; i < liczba_klockow; i++) {
    cin >> dlugosc_klocka >> numer_poczatkowy_klocka;
    --dlugosc_klocka;
    numer_koncowy_klocka = numer_poczatkowy_klocka + dlugosc_klocka;
    max_na_przedziale = ObliczMaksNaPrzedziale(numer_poczatkowy_klocka, numer_koncowy_klocka, 1, 0, liczba_przechowywanych_elementow-1);
    UstawMaksNaPrzedziale(numer_poczatkowy_klocka, numer_koncowy_klocka, 1, 0, liczba_przechowywanych_elementow-1, max_na_przedziale + 1);	
 }
 
 cout << ObliczMaksNaPrzedziale(0, liczba_przechowywanych_elementow-1, 1, 0, liczba_przechowywanych_elementow-1) << "\n";
 return 0;

}
Kod C++ programu Tetris 2D, który jest omówiony w powyższym filmie i który otrzymuje 100%

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz