Competitive Programming Repository

Repositorio de programación competitiva

La recopilación de algoritmos y estructuras de datos en C ++ se usa ampliamente en concursos de programación competitivos.

Los siguientes temas están cubiertos:

Actualizaciones y consultas de rango

• Consultas agregadas de rango :
  • Árboles indexados binarios (bit) :
    • Consulta de rango de actualización de puntos
    • Consulta de rango de actualización de rango
    • Ordenar consulta estadística
    • Árboles indexados binarios 2d
  • Árboles de segmento (Segtree) :
    • Consulta de rango de actualización de puntos
    • Segrees iterativos rápidos
    • Consulta de punto de actualización de rango - Progación perezosa
    • Suma del subsegmento máximo en el rango
    • Árboles de segmento 2D
    • Árboles de segmento dinámico: inserción/eliminación entre elementos
    • Árboles de segmento dinámico: revertir un segmento
  • Fusionar los árboles de clasificación :
    • Fusionar árboles de clasificación
    • Fusionar árboles de clasificación - Estadísticas de pedido
  • Mesa escasa :
    • Consulta mínima de rango
  • Algoritmo MO :
    • Algoritmo MO - Matrices
• Programación dinámica :
  • Plantillas de programación dinámica :
    • Dígito DP / DP bitwise
  • Problemas DP estándar :
    • La posterior subsecuencia más antigua
    • Subsecuencia palindrómica más larga
    • Distancia de Levenstein / Distancia de edición
• Gráficos :
  • Algoritmos de ruta más corta de fuente única :
    • Dijkstra en gráficos densos
    • Dijkstra usando la cola prioritaria
    • KTH más corta ruta entre nodos usando Dijkstra
    • Detección de ciclo negativo de Bellman Ford
  • Todos los pares más cortos :
    • Uso de exponenciación binaria
    • Floyd Warshall
  • Detección del ciclo :
    • Detección de ciclo en gráficos no dirigidos/dirigidos
  • Árbol de expansión mínimo :
    • Algoritmo de Kruskal
  • Clasificación topológica / componente fuertemente conectado :
    • Topológico
    • Componente fuertemente conectado
  • Maxflow/coincidencia :
    • Hopkroft Karp Max Matching
    • Dinic Max Flow
  • Misc :
    • Puentes en gráfico
    • Conectividad
    • Cheque bipartito
• Árboles :
  • Consultas del antepasado :
    • Antepasado común más bajo
    • KTH antepasado
  • Consultas de ruta :
    • Mesa escasa *
    • Nodos ponderados con descomposición de luz pesada
    • Bordes pesados ​​con descomposición de la luz pesada
  • Misc :
    • Diámetro de árbol
    • Sellos de pedido/poster, ¿está en subárbol?
• Exponencia binaria :
  • Calcular n^m usando exponencia binaria
  • Resolver recurrencias lineales
• Cuerdas :
  • Algoritmos de cadena :
    • Algoritmo z
    • Algoritmo de KMP
    • Grano de cuerda
    • Hortero de cadena para cuerdas dinámicas
  • Estructuras de datos de cadena :
    • Matriz de sufijo *
• Clasificación :
  • Fusionar
  • Seleccionar rápida
• Conversión de entrada/salida rápida, cadena/entero :
  • Entrada/salida rápida
  • Conversión de String/Integer
• Misc. Estructuras de datos :
  • Set de desargento
  • Conjunto de disjunto (admite la operación de deshacer)
  • Cola prioritaria máxima/min con actualización
  • Binary trie para la maximización/minimización de XOR
  • Bigint *
  • Árbol binario aumentado para estadísticas de pedido y consulta de rango
  • Cola prioritaria monótona
  • Trie
• Estructuras de datos persistentes :
  • Árboles de segmento persistentes (Segtree) :
    • Árbol de segmento persistente
    • Árbol de segmento persistente: estadísticas de pedido
• Algoritmos de teoría de números :
  • Verificación de primalidad :
    • Verificación de primalidad de Fermat
  • Tamiz :
    • Tamiz de Eratosthenes
    • Tamiz segmentado para primos grandes
    • Contando factores primos
  • Multiplicación polinomial :
    • Rápido de Fourier TranForm
    • Karatsuba
  • Misc :
    • Combinatorial y catalán - preprocesamiento factorial
    • Función Mobeius
    • Función de Euler Totient
    • Lucas Theorm - Combinatorics
• Geometría computacional :
  • Casco convexo
• Misc :
  • Suma del piso (x) con x = 1: n
  • Suma de funciones cíclicas *
  • Elemento más grande más cercano antes/después de cada elemento
  • Multiplicar enteros largos largos
  • Multiplicar enteros largos largos - detección de desbordamiento
  • Line de escaneo: fusionar intervalos de intersección