L'Atelier Monstre

Le hachage de chaînes est une technique algorithmique puissante qui permet de transformer une séquence de caractères en une valeur numérique unique (ou presque). Cette méthode est particulièrement efficace pour effectuer des comparaisons de sous-chaînes en temps constent \(O(1)\) après un prétraitement en \(O(n)\). Elle trouve ses applications ...

Implémentation de base Voici une implémentation typique de l'algorithme de Mo standard. Notez que le tableau des requêtes est trié selon un ordre qui optimise les déplacements successifs. #include #include #include #include const int MAX_N = 200000; int main() { int n, m, blockSize; std::cin >> n; blockSize = static_cast(std::sqrt(n) ...

Introduction à la Décomposition par Centroid La décomposision par centroid est une méthode diviser-pour-régner appliquée aux arbres. Elle est utile pour traiter des problèmes comme compter le nombre de paires de nœuds dont la distance pondérée égale une valeur donnée \(k\). L'idée principale est de récursivement décomposer l'arbre en sous-arbre ...

Cet article présente une récapitulation technique des solutions pour les problèmes de l'AtCoder Beginner Contest 420, avec des explications et des exemples de code réécrits en C++. Problème A Un problème simple qui peut être résolu directement. La solution calcule la valeur modulo 12 après ajustement. #include <iostream> using namespace s ...

Problème A : Maximiser la somme d'une séquence modifiable Étant donné une séquence d'entiers (positifs, négatifs ou nuls), on peut effectuer une opération un nombre illimité de fois : multiplier deux éléments adjacents par -1. L'objectif est de maximiser la somme de tous les éléments. L'approche consiste à analyser la parité du nombre d'élément ...