L'Atelier Monstre

L'ancêtre commun le plus proche (LCA) de deux nœuds u et v dans un arbre enraciné est le nœud le plus profond qui est un ancêtre à la fois de u et de v. Par exemple, dans l'arbre ci-dessous, LCA(3,7) = 1 et LCA(3,4) = 2. Il existe plusieurs méthodes pour calculer le LCA, classifiées en algorithmes hors ligne (toutes les requêtes sont connues à ...

L'Union-Find est une structure de données efficace pour gérer des ensembles disjoints, souvent utilisée pour modéliser des relatoins entre éléments. Dans cet article, nous explorons son application à deux problèmes classiques : la détermination du nombre maximum de héros dans un scénario de vérité et de mensonge, et la vérification de relations ...

A. Validation d'une chaîne « red » L'objectif est de vérifier si une chaîne de caractères donnée se compose exclusivement des lettres 'r', 'e' et 'd'. Une approche par énumération directe de chaque caractère suffit. #include <iostream> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); ci ...

Introduction aux Ensembles Disjoints La structure de données Union-Find (ou ensembles disjoints) est un type abstrait de données arborescent conçu pour gérer efficacement une collection de partitions. Elle prend en charge deux opérations fondamentales de manière optimale : Union : Fusionner deux ensembles distincts en un seul. Find : Détermine ...

Problème A : Somme de Produits Triangulaires Description : Étant donné trois entiers positifs \(A\), \(B\) et \(C\), calculer la valeur modulo \(998244353\) de la somme triple \(\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} a \times b \times c\). Solution : La somme se factorise en \(\left( \sum_{a=1}^{A} a \right) \times \left( \sum_{b=1}^{B} b ...

Problème 0112G : Sous-séquence et carré de la diversité Énoncé Soit une séquence d'entiers positifs \(A_1, A_2, \dots, A_n\). On définit \(f(l,r)\) comme la taille de l'ensemble distinct \(\{A_l, A_{l+1}, \dots, A_r\}\). Calculer \(\sum_{l=1}^n \sum_{r=l}^n (f(l,r))^2 \mod 10^9+7\). Approche Commençons par le calcul de \(\sum_{l=1}^n\sum_{r=l}^ ...