Competitive Programming Repository

Programação competitiva-repositório

Coleta de algoritmos e estruturas de dados em C ++ amplamente utilizados em concursos de programação competitiva.

Os seguintes tópicos são abordados:

Atualizações e consultas de intervalo

• Consultas agregadas de alcance :
  • Árvores indexadas binárias (BIT) :
    • Consulta de alcance de atualização de pontos
    • Consulta de alcance de atualização de alcance
    • Consulta estatística do pedido
    • Árvores indexadas binárias 2D
  • Árvores de segmento (Segtree) :
    • Consulta de alcance de atualização de pontos
    • Segtrees iterativos rápidos
    • Consulta de ponto de atualização da gama - propogação preguiçosa
    • Soma do subsegmento máximo no intervalo
    • Árvores de segmento 2D
    • Árvores de segmento dinâmico - Inserção/exclusão entre elementos
    • Árvores de segmento dinâmico - reverter um segmento
  • Mesclar árvores de classificação :
    • Mesclar árvores de classificação
    • Mesclar árvores de classificação - Estatísticas de pedidos
  • Tabela esparsa :
    • Perseguição mínima do alcance
  • Algoritmo MO :
    • Algoritmo MO - Matrizes
• Programação dinâmica :
  • Modelos de programação dinâmica :
    • Digit dp / bitwise dp
  • Problemas de DP padrão :
    • Subseqüência crescente mais longa
    • Subsequência palindrômica mais longa
    • LEVENSTEIN Distância / Distância de edição
• Gráficos :
  • Algoritmos de caminho mais curto de fonte única :
    • Dijkstra em gráficos densos
    • Dijkstra usando fila prioritária
    • Kth mais curto caminho entre nós usando Dijkstra
    • Detecção de ciclo negativo Bellman Ford
  • Todos os emparelham o caminho mais curto :
    • Usando exponenciação binária
    • Floyd Warshall
  • Detecção de ciclo :
    • Detecção de ciclo em gráficos não direcionados/direcionados
  • Árvore de abrangência mínima :
    • Algoritmo Kruskal
  • Tipo topológico / componente fortemente conectado :
    • Tipo topológico
    • Componente fortemente conectado
  • Maxflow/correspondência :
    • Hopkroft Karp Max Matching
    • Fluxo max dinic
  • Misc :
    • Pontes no gráfico
    • Conectividade
    • Verificação bipartida
• Árvores :
  • Consultas ancestrais :
    • Ancestral comum mais baixo
    • Kth ancestral
  • Consultas de caminho :
    • Mesa esparsa *
    • Nós pesados ​​de decomposição da luz
    • Bordas ponderadas de decomposição da luz pesada
  • Misc :
    • Diâmetro da árvore
    • Selos de pré -encomenda/pós -encomenda, está na subárvore?
• Exponeção binária :
  • Calcule n^m usando exponenciação binária
  • Resolvendo recorrências lineares
• Strings :
  • Algoritmos de string :
    • Algoritmo Z.
    • Algoritmo KMP
    • Rolling String Hashing
    • Rolling String Hashing para strings dinâmicos
  • Estruturas de dados da string :
    • Array de sufixo *
• Classificação :
  • Mesclar classificar
  • Selecionar rápido
• Entrada/saída rápida, String/Inteiro Conversão :
  • Entrada/saída rápida
  • Conversão de string/número inteiro
• Misc. Estruturas de dados :
  • Conjunto disjunto
  • Conjunto disjunto (suporta operação de desfazer)
  • Fila de prioridade máxima/min
  • Trie binário para maximização/minimização XOR
  • Bigint *
  • Árvore binária aumentada para estatísticas de pedidos e consulta de classificação
  • Fila de prioridade monótona
  • Trie
• Estruturas de dados persistentes :
  • Árvores de segmento persistente (Segtree) :
    • Árvore de segmento persistente
    • Árvore de segmento persistente - Estatísticas de pedido
• Algoritmos de teoria dos números :
  • Verificação da Primalidade :
    • Verificação de Primalidade de Fermat
  • Peneira :
    • Peneira de eratóstenos
    • Peneira segmentada para grandes primos
    • Contando fatores primos
  • Multiplicação Polinomial :
    • Transformação rápida de Fourier
    • Karatsuba
  • Misc :
    • Combinatória e catalão - pré -processamento fatorial
    • Função mobeius
    • Função Totiente Euler
    • Lucas Theorm - Combinatorics
• Geometria computacional :
  • Casco convexo
• Misc :
  • Soma do piso (x) com x = 1: n
  • Soma das funções cíclicas *
  • Elemento maior mais próximo antes/depois de cada elemento
  • Multiplique inteiros longos longos
  • Multiplicar números inteiros longos - detecção de transbordamento
  • Scanline - Mesclar intervalos de cruzamento