Competitive Programming Repository

Programmation concurrentielle

Collecte des algorithmes et des structures de données en C ++ utilisés largement dans les concours de programmation compétitifs.

Les sujets suivants sont couverts:

Mises à jour et requêtes de la plage

• Range des requêtes d'agrégation :
  • Arbres binaires indexés (bit) :
    • Requête de plage de mise à jour ponctuelle
    • Range Mise à jour Requête de plage
    • Commandez la requête statistique
    • Arbres binaires binaires 2D
  • Arbres de segment (Segtree) :
    • Requête de plage de mise à jour ponctuelle
    • Ségtreres itératifs rapides
    • Range de mise à jour Point Query - propogation paresseuse
    • Sum de sous-segment maximum dans la plage
    • Arbres de segment 2D
    • Dynamic Segment Trees - Insertion / Suppression entre les éléments
    • Dynamic Segment Trees - Inversez un segment
  • Fusion des arbres :
    • Fusion des arbres
    • Fusion des arbres de tri - Commandez des statistiques
  • Tableau clairsemé :
    • Plage de requête minimale
  • Algorithme MO :
    • Algorithme MO - Tableaux
• Programmation dynamique :
  • Modèles de programmation dynamique :
    • Nigit dp / bitwise dp
  • Problèmes DP standard :
    • La plus longue subséquence croissante
    • La plus longue subséquence palindromique
    • Distance de Levenstein / Distance de modification
• Graphiques :
  • Algorithmes de chemin le plus court à la source unique :
    • Dijkstra en graphiques denses
    • Dijkstra en utilisant la file d'attente prioritaire
    • Kth le plus court chemin entre les nœuds utilisant dijkstra
    • Détection du cycle négatif de Bellman Ford
  • Tous les deux chemins le plus court :
    • Utilisation de l'exponentiation binaire
    • Floyd Warshall
  • Détection du cycle :
    • Détection du cycle dans des graphiques non dirigés / dirigés
  • Arbre couvrant minimum :
    • Algorithme de Kruskal
  • Toi topologique / composant fortement connecté :
    • Tri topologique
    • Composant fortement connecté
  • Maxflow / correspondance :
    • Hopkroft karp max correspondant
    • Dinic Max Flow
  • Misc :
    • Ponts en graphique
    • Connectivité
    • Chèque bipartite
• Arbres :
  • Requêtes d'ancêtre :
    • Ancêtre commun le plus bas
    • Kth ancêtre
  • Requêtes de chemin :
    • Table clairsemée *
    • Nœuds pondérés de décomposition de lumière lourde
    • Bords pondérés de décomposition de lumière lourde
  • Misc :
    • Diamètre de l'arbre
    • Tampons de précommande / post-ordre, est-ce en sous-arbre?
• Exponentiation binaire :
  • Calculer n ^ m en utilisant l'exponentiation binaire
  • Résolution de récidives linéaires
• CORDES :
  • Algorithmes de chaîne :
    • Algorithme z
    • Algorithme KMP
    • Hachage de corde à rouler
    • Hachage de cordes roulant pour les chaînes dynamiques
  • Structures de données de chaîne :
    • Array du suffixe *
• Tri :
  • Fusion
  • Sélection rapide
• Entrée / sortie rapide, conversion de chaîne / entier :
  • Entrée / sortie rapide
  • Conversion de chaîne / entier
• Mis. Structures de données :
  • Ensemble disjoint
  • Set disjoint (prend en charge une opération d'annulation)
  • Fitrance de priorité max / min avec mise à jour
  • Trie binaire pour la maximisation / minimisation XOR
  • Bigint *
  • Arbre binaire augmenté pour les statistiques de commande et les requêtes de rang
  • File d'attente de priorité monotone
  • Faire un coup de pouce
• Structures de données persistantes :
  • Arbres de segment persistants (Segtree) :
    • Arbre de segment persistant
    • Arbre de segment persistant - Statistiques de commande
• Algorithmes de théorie des nombres :
  • Vérification de la primalité :
    • Vérification de la primalité de Fermat
  • Tamis :
    • Tamis d'eratosthène
    • Tamis segmenté pour les grands nombres premiers
    • Compter les facteurs premiers
  • Multiplication polynomiale :
    • Fourier rapide Tranform
    • Karatsuba
  • Misc :
    • Combinatoire et catalan - prétraitement factoriel
    • Fonction Mobeius
    • Fonction Euler Totient
    • Lucas Theorm - Combinatorics
• Géométrie informatique :
  • Coque convexe
• Misc :
  • Somme du sol (x) avec x = 1: n
  • Somme des fonctions cycliques *
  • Élément plus grand le plus proche avant / après chaque élément
  • Multiplier les entiers longs longs
  • Multiplier des entiers longs longs - Détection de débordement
  • Intervalles d'intervalle d'intersection fusion