Structures de données

Théorie des graphes

Flot maximal

Dinic

Implémentation de l'algorithme de Dinic pour le flot maximal.

int compteurArête = 1, nbNœuds, nbArêtes, flotMax, courant[N], distance[N], source, puits, listeAdjacence[N];
std::queue<int> file;
struct Arête {int dest, capacité, suivante;} arêtes[M*2];

void ajouterArête(int u, int v, int cap) {
    compteurArête++;
    arêtes[compteurArête].dest = v;
    arêtes[compteurArête].capacité = cap;
    arêtes[compteurArête].suivante = listeAdjacence[u];
    listeAdjacence[u] = compteurArête;
}

bool bfs() {
    while (!file.empty()) file.pop();
    for (int i = 1; i <= nbNœuds; i++) {
        courant[i] = listeAdjacence[i];
        distance[i] = 0;
    }
    file.push(source);
    distance[source] = 1;
    while (!file.empty()) {
        int nœud = file.front();
        file.pop();
        for (int i = listeAdjacence[nœud]; i; i = arêtes[i].suivante) {
            int voisin = arêtes[i].dest;
            if (arêtes[i].capacité && !distance[voisin]) {
                distance[voisin] = distance[nœud] + 1;
                if (voisin == puits) return true;
                file.push(voisin);
            }
        }
    }
    return false;
}

int dfs(int nœud, int reste) {
    if (!reste || nœud == puits) return reste;
    int total = 0;
    for (int i = courant[nœud]; i; i = arêtes[i].suivante) {
        int voisin = arêtes[i].dest;
        courant[nœud] = i;
        int flux;
        if (distance[voisin] == distance[nœud] + 1 && (flux = dfs(voisin, std::min(reste, arêtes[i].capacité)))) {
            arêtes[i].capacité -= flux;
            arêtes[i^1].capacité += flux;
            total += flux;
            reste -= flux;
            if (reste == 0) break;
        }
    }
    if (total == 0) distance[nœud] = 0;
    return total;
}

void dinic() {while (bfs()) flotMax += dfs(source, INF);}</int>

Algorithmes pour chaînes de caractères

Représentation minimale

Algorithme pour trouver la rotation cyclique minimale d'une chaîne.

int tableau[2*N];
int longueur;

void initialiser() {
    scanf("%d", &longueur);
    for (int i = 1; i <= longueur; i++) {
        long long valeur;
        scanf("%lld", &valeur);
        tableau[i] = tableau[i + longueur] = valeur;
    }
}

void résoudre() {
    int i = 1, j = 2, k = 0;
    while (i <= longueur && j <= longueur) {
        k = 0;
        while (tableau[i+k] == tableau[j+k] && k < longueur) k++;
        if (tableau[i+k] > tableau[j+k]) i = i + k + 1;
        else j = j + k + 1;
        if (k == longueur) break;
        if (i == j) j++;
    }
    int index = std::min(i, j);
    for (int p = 1; p <= longueur; p++) {
        printf("%d ", tableau[index + p - 1]);
    }
}

Hachage de chaînes

Utilisation de hachage pour comparer des chaînes efficacement.

const unsigned long long base = 998244353;

std::string chaîne;
unsigned long long hashActuel, stockage[100005];
int compteur, résultat, nbChaînes;

void calculerHash() {
    hashActuel = 0;
    unsigned long long puissance = 1;
    for (size_t i = 0; i < chaîne.size(); i++) {
        hashActuel += chaîne[i] * puissance;
        puissance *= base;
    }
}

void comparer() {
    bool trouvé = false;
    for (int i = 1; i <= compteur; i++) {
        if (stockage[i] == hashActuel) {
            trouvé = true;
            break;
        }
    }
    if (!trouvé) {
        résultat++;
        stockage[++compteur] = hashActuel;
    }
}

void traiter() {
    for (int i = 1; i <= nbChaînes; i++) {
        std::cin >> chaîne;
        calculerHash();
        comparer();
    }
    printf("%d", résultat);
}

KMP (Knuth-Morris-Pratt)

Recherche de motif dans une chaîne avec l'algorithme KMP.

char motif[1000005], texte[1000005];
int longueurMotif, longueurTexte;
int bord[1000005];

void lire() {
    std::cin >> (texte+1) >> (motif+1);
    longueurMotif = strlen(motif+1);
    longueurTexte = strlen(texte+1);
}

void prétraitement() {
    bord[1] = 0;
    for (int i = 2, j = 0; i <= longueurMotif; i++) {
        while (j && motif[j+1] != motif[i]) j = bord[j];
        if (motif[j+1] == motif[i]) j++;
        bord[i] = j;
    }
}

void recherche() {
    for (int i = 1, j = 0; i <= longueurTexte; i++) {
        while (j && motif[j+1] != texte[i]) j = bord[j];
        if (motif[j+1] == texte[i]) j++;
        if (j == longueurMotif) printf("%d\n", i - j + 1);
    }
}

void afficherBords() {
    for (int i = 1; i <= longueurMotif; i++) {
        printf("%d ", bord[i]);
    }
}

Extension KMP (Fonction Z)

Algorithme pour calculer les correspondances préfixes étendues.

char source[N], motif[N];
int zTable[N], pTable[N];
int longueurSource, longueurMotif;

void initialiser() {
    std::cin >> (source+1) >> (motif+1);
    longueurSource = strlen(source+1);
    longueurMotif = strlen(motif+1);
}

void calculerZ() {
    zTable[1] = longueurMotif;
    for (int i = 2, gauche = 0, droite = 0; i <= longueurMotif; i++) {
        if (i <= droite) zTable[i] = std::min(zTable[i-gauche+1], droite-i+1);
        while (motif[1+zTable[i]] == motif[i+zTable[i]]) zTable[i]++;
        if (i+zTable[i]-1 > droite) { gauche = i; droite = i+zTable[i]-1; }
    }
}

void calculerP() {
    for (int i = 1, gauche = 0, droite = 0; i <= longueurSource; i++) {
        if (i <= droite) pTable[i] = std::min(zTable[i-gauche+1], droite-i+1);
        while (i+pTable[i] <= longueurSource && 1+pTable[i] <= longueurMotif && source[i+pTable[i]] == motif[1+pTable[i]]) pTable[i]++;
        if (i+pTable[i]-1 > droite) { gauche = i; droite = i+pTable[i]-1; }
    }
}

Manacher

Algorithme pour trouver le plus long palindrome dans une chaîne.

int rayons[2*N];
char entrée[N];
char transformé[2*N];
int longueur;

void préparer() {
    std::cin >> (entrée+1);
    transformé[0] = '$';
    int k = 1;
    transformé[k] = '#';
    longueur = strlen(entrée+1);
    for (int i = 1; i <= longueur; i++) {
        transformé[++k] = entrée[i];
        transformé[++k] = '#';
    }
    longueur = k;
}

void manacher() {
    rayons[1] = 1;
    for (int i = 2, centre = 1, bord = 1; i <= longueur; i++) {
        if (i <= bord) rayons[i] = std::min(rayons[2*centre-i], bord-i+1);
        while (transformé[i+rayons[i]] == transformé[i-rayons[i]]) rayons[i]++;
        if (i+rayons[i]-1 > bord) { centre = i; bord = i+rayons[i]-1; }
    }
}

Arbre préfixe (Trie)

Structure pour stocker et rechercher des chaînes efficacement.

int nbÉléments, nbRequêtes, arbre[N][150], compteurNoeuds, occurrence[N];

inline int encoder(char c) { return c - 'A'; }

void insérer(const std::string& s) {
    int courant = 0;
    for (char ch : s) {
        int code = encoder(ch);
        if (!arbre[courant][code]) arbre[courant][code] = ++compteurNoeuds;
        courant = arbre[courant][code];
    }
    occurrence[courant]++;
}

int rechercher(const std::string& s) {
    int courant = 0;
    for (char ch : s) {
        int code = encoder(ch);
        if (!arbre[courant][code]) return 0;
        courant = arbre[courant][code];
    }
    return occurrence[courant];
}

Arbre XOR 01

Variante de l'arbre préfixe pour opérations sur bits.

int nbÉléments, nbRequêtes, arbre[N][2], compteurNoeuds, compteur[N];

void insérer(int valeur) {
    int courant = 0;
    for (int i = 30; i >= 0; i--) {
        int bit = (valeur >> i) & 1;
        if (!arbre[courant][bit]) arbre[courant][bit] = ++compteurNoeuds;
        courant = arbre[courant][bit];
    }
    compteur[courant]++;
}

int rechercher(int valeur) {
    int courant = 0, résultat = 0;
    for (int i = 30; i >= 0; i--) {
        int bit = (valeur >> i) & 1;
        if (arbre[courant][bit^1]) { courant = arbre[courant][bit^1]; résultat |= (1 << i); }
        else courant = arbre[courant][bit];
    }
    return résultat;
}

Automate Aho-Corasick

Recherche de multiple motifs dans un texte avec l'algorithme Aho-Corasick.

int trie[(int)1e6+6][30], lien[(int)1e6+5], compteur, nbMotifs;
std::string texte, motifs[(int)1e6+6];

void lire();
void ajouterMotif(const std::string& s);
void construireTrie();
std::queue<int> file;
void construireLiens();
int rechercher(const std::string& texte);

int main() {
    lire();
    construireTrie();
    construireLiens();
    std::cout << rechercher(texte);
    return 0;
}

int rechercher(const std::string& s) {
    int total = 0;
    int courant = 0;
    for (char c : s) {
        int idx = c - 'a';
        courant = trie[courant][idx];
        for (int j = courant; compteur[j] != -1 && j; j = lien[j]) {
            total += compteur[j];
            compteur[j] = -1;
        }
    }
    return total;
}

void ajouterMotif(const std::string& s) {
    int courant = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (!trie[courant][idx]) trie[courant][idx] = ++compteur;
        courant = trie[courant][idx];
    }
    compteur[courant]++;
}

void construireTrie() {
    for (int i = 1; i <= nbMotifs; i++) ajouterMotif(motifs[i]);
}

void construireLiens() {
    for (int i = 0; i < 26; i++) {
        if (trie[0][i]) file.push(trie[0][i]);
    }
    while (!file.empty()) {
        int u = file.front();
        file.pop();
        for (int i = 0; i < 26; i++) {
            int v = trie[u][i];
            if (v) {
                lien[v] = trie[lien[u]][i];
                file.push(v);
            } else trie[u][i] = trie[lien[u]][i];
        }
    }
}

void lire() {
    std::cin >> nbMotifs;
    for (int i = 1; i <= nbMotifs; i++) std::cin >> motifs[i];
    std::cin >> texte;
}</int>

Tableau des suffixes (SA)

Construction du tableau des suffixes avec l'algorithme de tri par comptage.

#include <bits>
using namespace std;

const int MAX = 3e6;
int longueur, tailleSeau = 256;
int seau[MAX], temp[MAX], comptage[MAX], sa[MAX], rang[MAX], lcp[MAX];
char chaîne[MAX];

void lire();
void construireSA();
void construireLCP();

int main() {
    lire();
    construireSA();
    for (int i = 1; i <= longueur; i++) printf("%d ", sa[i]);
    printf("\n");
    construireLCP();
    for (int i = 1; i <= longueur; i++) printf("%d ", lcp[i]);
    return 0;
}

void lire() {
    std::cin >> (chaîne+1);
    longueur = strlen(chaîne+1);
}

void construireSA() {
    for (int i = 1; i <= longueur; i++) comptage[seau[i] = chaîne[i]]++;
    for (int i = 1; i <= tailleSeau; i++) comptage[i] += comptage[i-1];
    for (int i = longueur; i >= 1; i--) sa[comptage[seau[i]]--] = i;
    for (int k = 1; k <= longueur; k <<= 1) {
        memset(comptage, 0, sizeof(comptage));
        for (int i = 1; i <= longueur; i++) temp[i] = sa[i];
        for (int i = 1; i <= longueur; i++) comptage[seau[temp[i]+k]]++;
        for (int i = 1; i <= tailleSeau; i++) comptage[i] += comptage[i-1];
        for (int i = longueur; i >= 1; i--) sa[comptage[seau[temp[i]+k]]--] = temp[i];
        memset(comptage, 0, sizeof(comptage));
        for (int i = 1; i <= longueur; i++) temp[i] = sa[i];
        for (int i = 1; i <= longueur; i++) comptage[seau[temp[i]]]++;
        for (int i = 1; i <= tailleSeau; i++) comptage[i] += comptage[i-1];
        for (int i = longueur; i >= 1; i--) sa[comptage[seau[temp[i]]]--] = temp[i];
        tailleSeau = 0;
        for (int i = 1; i <= longueur; i++) temp[i] = seau[i];
        for (int i = 1; i <= longueur; i++) {
            if (temp[sa[i]] == temp[sa[i-1]] && temp[sa[i]+k] == temp[sa[i-1]+k]) seau[sa[i]] = tailleSeau;
            else seau[sa[i]] = ++tailleSeau;
        }
        if (tailleSeau == longueur) break;
    }
}

void construireLCP() {
    for (int i = 1; i <= longueur; i++) rang[sa[i]] = i;
    for (int i = 1, k = 0; i <= longueur; i++) {
        if (rang[i] == 1) continue;
        if (k) k--;
        int j = sa[rang[i]-1];
        while (i+k <= longueur && j+k <= longueur && chaîne[i+k] == chaîne[j+k]) k++;
        lcp[rang[i]] = k;
    }
}</bits>

Automate des suffixes (SAM)

Construction de l'automate des suffixes pour des applications avancées.

#define ll long long
#define MAX_N (int(2e6+6))

int lien[MAX_N], transitions[MAX_N][28], longueur[MAX_N], compteur[MAX_N], idx = 1, courant = 1;
ll résultat;
std::string chaîne;
std::vector<int> arbre[MAX_N];

void étendre(int c);
void parcourir(int u);

int main() {
    std::cin >> chaîne;
    for (char c : chaîne) étendre(c - 'a');
    for (int i = 2; i <= idx; i++) arbre[lien[i]].push_back(i);
    parcourir(1);
    std::cout << résultat;
    return 0;
}

void parcourir(int u) {
    for (int v : arbre[u]) {
        parcourir(v);
        compteur[u] += compteur[v];
    }
    if (compteur[u] > 1) résultat = std::max(résultat, (ll)compteur[u] * longueur[u]);
}

void étendre(int c) {
    int p = courant;
    courant = ++idx;
    longueur[courant] = longueur[p] + 1;
    compteur[courant] = 1;
    for (; p && !transitions[p][c]; p = lien[p]) transitions[p][c] = courant;
    if (!p) lien[courant] = 1;
    else {
        int q = transitions[p][c];
        if (longueur[q] == longueur[p] + 1) lien[courant] = q;
        else {
            int copie = ++idx;
            longueur[copie] = longueur[p] + 1;
            lien[copie] = lien[q];
            lien[q] = lien[courant] = copie;
            for (; p && transitions[p][c] == q; p = lien[p]) transitions[p][c] = copie;
            memcpy(transitions[copie], transitions[q], sizeof(transitions[q]));
        }
    }
}</int>

Théorie des nombres et mathématiques

PGCD optimal

Algorithme rapide pour calculer le plus grand commun diviseur.

ll pgcd(ll a, ll b) {
    while (b) { a %= b; std::swap(a, b); }
    return a;
}

Algorithmes de tri

Tri rapide

Implémentation du tri rapide en place.

int tableau[N];

void triRapide(int gauche, int droite) {
    if (gauche >= droite) return;
    int i = gauche, j = droite;
    int pivot = tableau[gauche];
    while (i < j) {
        while (i < j && tableau[j] >= pivot) j--;
        tableau[i] = tableau[j];
        while (i < j && tableau[i] <= pivot) i++;
        tableau[j] = tableau[i];
    }
    tableau[i] = pivot;
    triRapide(gauche, i-1);
    triRapide(i+1, droite);
}

Tri fusion

Implémantation du tri fusion avec comptage des inversions.

int source[N], buffer[N], inversions;

void triFusion(int gauche, int droite) {
    if (gauche >= droite) return;
    int milieu = (gauche + droite) >> 1;
    triFusion(gauche, milieu);
    triFusion(milieu+1, droite);
    int i = gauche, j = milieu+1, k = gauche;
    while (i <= milieu && j <= droite) {
        if (source[i] <= source[j]) buffer[k++] = source[i++];
        else { buffer[k++] = source[j++]; inversions += milieu - i + 1; }
    }
    while (i <= milieu) buffer[k++] = source[i++];
    while (j <= droite) buffer[k++] = source[j++];
    for (int i = gauche; i <= droite; i++) source[i] = buffer[i];
}

Entrées/Sorties rapides

Lecture et écriture accélérées

Fonctions pour une E/S plus rapide en compétition.

typedef long long lll;

lll lire() {
    bool négatif = false;
    char c = getchar();
    lll résultat = 0;
    while (!isdigit(c) && c != EOF) {
        négatif = (c == '-');
        c = getchar();
    }
    while (isdigit(c) && c != EOF) {
        résultat = (résultat << 3) + (résultat << 1) + (c ^ '0');
        c = getchar();
    }
    return négatif ? -résultat : résultat;
}

int tampon[100];
void écrire(lll x) {
    int i = 0;
    if (x < 0) { x = -x; putchar('-'); }
    if (x == 0) putchar('0');
    while (x) { tampon[++i] = x % 10; x /= 10; }
    while (i) putchar(tampon[i--] + '0');
}