L'Atelier Monstre

Le concours Lanqiao, en particulier pour le Groupe B (destiné aux étudiants de premier cycle), exige un équilibre précis entre la maîtrise de la syntaxe et la résolution de problèmes complexes. Les épreuves se composent généralement de 6 à 8 problèmes à résoudre en 4 heures. La difficulté suit une progression constante : des manipulations de ba ...

Introduction à l'arbre de préfixes L'arbre de préfixes, communément appelé Trie, est une structure de données arborescente spécialisée dans la gestion et la recherche de chaînes de caractères. Contrairement à une table de hachage classique, le Trie exploite les préfixes communs entre les clés pour optimiser l'espace mémoire et la vitesse de rec ...

Le problème du déport maximal de cartes explore la distance maximale à laquelle une pile de cartes peut dépasser le bord d'une table. En supposant que les cartes sont toujours perpendiculaires à la table, une seule carte peut déborder d'une lognueur équivalente à la moitié de sa propre longueur. Lorsque deux cartes sont utilisées, la carte supé ...

Fondamentaux et Template L'implémentation classique de l'algorithme de Kruskal repose sur deux piliers : le tri des arêtes par poids et la gestion des composantes connexes via une structure Union-Find (Disjoint Set Union - DSU). Pour des problèmes compétitifs exigeants, il est crucial d'optimiser ces opérations. Premièrement, la fonction de rec ...

Liste Simplement Chaînée Cette implémentation utilise des tableaux statiques pour simuler une liste chaînée, ce qui est particulièrement efficace en programmation compétitive pour éviter les allocations dynamiques coûteuses. // tete : indice du premier élément // val[] : stocke les données // suivant[] : pointeur vers l'indice suivant // curseu ...

Problème A : Validation de sous-chaîne de mot de passe L'énoncé demande s'il est possible de modifier un mot de passe de longueur $m$ pour qu'il devienne une sous-chaîne d'une chaîne cible de longueur $n$. Puisque nous pouvons modifier n'importe quel caractère du mot de passe (sans changer sa longueur), la seule contrainte réelle est la dimensi ...

Mise en place de la structure de données Avant d'initier le processus récursif, il est impératif de construire correctement la topologie de l'arbre. Cela implique généralement de lire les relations de parenté et de stocker les successeurs de chaque sommet. Une étape préliminaire courante consiste à déterminer les propriétés statiques de chaque ...

Caractéristiques des talbeaux Un tableau stocke des éléments de même type dans des emplacements mémoire contigus. L'accès se fait via un indice entier commençant à 0. Les éléments ne peuvent pas être supprimés physiquement ; on ne peut que les écraser. Recherche binaire (LeetCode 704) Rechercher une valeur cible dans un tableau trié en temps O( ...

Sommes前缀es ============= 1.1 Principe fondamental La somme前缀e constitue une technique permettant de mémoriser le cumul des éléments précédents dans une structure de données. Cette approche offre une complexité temporelle constante O(1) pour récupérer la somme de n'importe quel intervalle donné. Tableau unidimensionnel Pour calculer la som ...

Problème (LeetCode 704) Étant donné un tableau d'entiers nums trié par ordre croissant contenant n éléments, et un entier target, écrivez une fonction qui recherche target dans nums. Si target existe, retournez son indice ; sinon, retournez -1. Exemple 1 : Entrée : nums = [-1,0,3,5,9,12], target = 9 Sortie : 4 Explication : La valeur 9 se trouv ...