8063591564

1.4. Nagłówki

Wszystkie programy w tej książce są zaimplementowane w języku C++, z wykorzystaniem biblioteki STL. Ponieważ podczas zawodów bardzo istotne jest, aby kody źródłowe implementowanych programów były jak najkrótsze, dlatego wielu zawodników stosuje pewne skróty dla najczęściej występujących w programach konstrukcji językowych. Podczas zawodów ACM ICPC, w ciągu pięciogodzinnych sesji, do rozwiązania jest 7 do 10 zadań, zatem opłaca się na początku konkursu przepisać najważniejsze instrukcje, a następnie wykorzystywać je we wszystkich pisanych programach. Instrukcje te nazywamy mianem nagłówków — zawierają one zarówno listę najczęściej dołączanych do programów bibliotek, jak i często wykorzystywane makra. Listing 1.1 przedstawia zbiór podstawowych nagłówków pochodzących z biblioteczki algorytmicznej mojego zespołu wraz z komentarzami opisującymi ich wykorzystanie. Na listingu 1.2 przedstawione zostały te same nagłówki po usunięciu komentarzy.

Listing 1.1: Nagłówki z komentarzami

01    #include <cstdio>

02    #include <iostream>

03    #include <algorithm>

04    #include <string>

05    #include <vector>

06    using namespace std;

// Dwa z najczęściej używanych typów o długich nazwach - ich skrócenie jest bardzo // istotne

07    typedef vector<int> VI;

08    typedef łong long LL;

// W programach bardzo rzadko można znaleźć w pełni zapisaną instrukcję pętli.

// Zamiast niej, wykorzystywane są trzy następuj ące makra:

// FOR - pętla zwiększająca zmienną z od b do e włącznie

09    #define FOR(x, b, e) for(int x = b; x <= (e); +-|-x)

// FORD - pętla zmniejszająca zmienną x od b do e włącznie

10    #define FORD(x, b, e) for(int x = b; x >= (e); —x)

// REP - pętla zwiększająca zmienną z od 0 do n. Jest ona bardzo // często wykorzystywana do konstruowania i przeglądania struktur danych

11    #define REP(x, n) for(int x = 0; x < (n); +-t-x)

// Makro VAR(v,n) deklaruje nową zmienną o nazwie v oraz typie i wartości // zmiennej n. Jest ono często wykorzystywane podczas operowania na iteratorach // struktur danych z biblioteki STL, których nazwy typów są bardzo długie

12    #define VAR(v, n) _typeof(n) v = (n)

// ALL(c) reprezentuje parę iteratorów wskazujących odpowiednio na pierwszy i // za ostatni element w strukturach danych STL. Makro to jest bardzo przydatne // chociażby w przypadku korzystania z funkcji sort, która jako parametry // przyjmuje parę iteratorów reprezentujących przedział elementów do posortowania.

13    #define ALL(c) (c).begin(), (c).end()

// Poniższe makro służy do wyznaczania rozmiaru struktur danych STL. Używa się go //w programach, zamiast pisać po prostu x.size() z uwagi na fakt, iż wyrażenie // x.size() jest typu unsigned int i w przypadku porównywania z typem // int, w procesie kompilacji generowane jest ostrzeżenie.

14    #define SIZE(x) ((int)(x).size())

// Bardzo pożyteczne makro, służące do iterowania po wszystkich elementach w