L'Atelier Monstre

Problème 1 : Fréquence du mode dans un tableau Étant donné un tableau d'entiers, déterminer la fréquence maximale d'un élément, c'est-à-dire le nombre d'occurrences de la valeur la plus courante. Approche : Utiliser un tableau de comptage pour enregistrer la fréquence de chaque élément, puis identifier le maximum. #include <iostream> #in ...

La programmation 0/1, ou programmation fractionnaire 0/1, est une classe de problèmes d'optimisation. Elle implique la sélection d'un sous-ensemble d'éléments, où chaque élément a deux attributs, disons \(a_i\) et \(b_i\). L'objectif est de maximiser (ou minimiser) le ratio \(\frac{\sum a_i \times d_i}{\sum b_i \times d_i}\), sous certaines con ...

L'algorithme du plus ancêtre commun (LCA) est une technique fondamentale pour résoudre des problèmes de distance ou de relations dans des arbres. Cet article présente plusieurs problèmes d'entraînement pour maîtriser le LCA, avec des explications et des implémentations en C++. Problème 1 : Distance entre maisons Lien : HDU 2586 Description : Un ...

Considérons une hiérarchie familiale modélisée par un arbre généalogique. L'objectif est de déterminer, pour chaque niveau de profondeur depuis la racine, le nombre de membres sans enfants (nœuds feuilles). Spécification d'entrée : Chaque cas de test débute par une ligne contenant deux entiers N et M. N représente le nombre total de nœuds dans ...

Principe fondamental Transformer un arbre en une séquence linéaire où n'importe quel chemin correspond à au plus O(log n) segments consécutifs. Définitions essentielles Fils lourd : enfant dont la sous-arbre contient le plus de nœuds Fils léger : tout enfant n'étant pas fils lourd Arête lourde : reliant un nœud à son fils lourd Arête légère : ...