competitive_programming

Programação e exercícios competitivos

Estas são minhas soluções C ++ de alguns problemas de programação competitivos e vários exercícios. Problemas semelhantes são resolvidos usando diferentes algoritmos e estruturas de dados - às vezes usando os fornecidos pela biblioteca padrão, às vezes usando os próprios.

A maioria das soluções está em C+11 devido à limitação de juízes on-line ex-UV. Alguns deles após o envio bem -sucedido foram modificados para usar os recursos C ++ 14/17.

Problemas ex-uva OJ

Fonte de problemas

EU IA	Título	Categorias
001 08	Soma máxima	Pesquisa linear, subarray máxima da soma, algoritmo de Kadane
001 09	Scud Busters	Casco convexo
001 12	Sumor de árvores	Árvore binária
001 20	Pilhas de flapjacks	Stack, classificação de panquecas
001 22	Árvores no nível	Árvore binária, travessia de ordem de nível, pesquisa pela primeira vez
001 40	Largura de banda	Permutações, retrocesso
001 47	Dólares	Programação dinâmica, mudança de moeda
001 64	Computador de cordas	Programação dinâmica, distância de edição
002 00	Ordem rara	Classificação topológica, Pesquisa em profundidade
002 16	Entrar na fila	Programação dinâmica, caminho hamiltoniano, máscaras de bits
002 18	Erradicação da mariposa	Casco convexo
002 22	Viagens orçamentárias
002 40	Variável Radix Huffman codificando	Huffman Tree, Pesquisa em profundidade
002 59	Alocação de software
002 64	Conte com Cantor
002 70	Alinhando -se
002 94	Divisores
003 34	Identificando eventos simultâneos
003 48	Array ideal mult. Sequência	Programação dinâmica, multiplicação de cadeia matricial
003 50	Pseudo -números aleatórios
003 53	Palíndromos traquinas	Hash rolante polinomial, processamento de string
003 57	Conte os caminhos
003 61	Policiais e ladrões
003 72	Whatfix Notação	Árvore binária, conversão de travessias pré-//pós-ordem
003 74	Grande mod	Exponeção binária, exponenciação modular
004 29	Transformação de palavras
004 37	Torre da Babilônia
004 39	Cavaleiro se move	Pesquisa pela primeira vez
004 54	Anagramas
004 55	Cordas periódicas	Strings, algoritmo Knuth -Morris - Pratt
004 59	Conectividade gráfica	Componentes conectados gráficos, de forma disjunta/união,
004 69	Pântanos da Flórida
004 81	O que sobe	Subsequência crescente mais longa, pesquisa binária
004 82	Matrizes de permutações
005 01	Caixa preta	Árvore AVL, Iterador de Árvore Binária
005 07	Jill monta novamente	Pesquisa linear, subarray máxima da soma, algoritmo de Kadane
005 16	Terra Prime
005 26	Distância da corda	Programação dinâmica, distância de edição
005 36	Recuperação de árvores	Árvore binária, conversão de travessias pré-//pós-ordem
005 40	Fila de equipe
005 43	Conjectura de Goldbach	Números primários
005 48	Árvore
005 51	Bando de suportes de nidificação
005 58	Buracos de minhoca
005 62	Dividindo moedas
005 68	Apenas os fatos	Fatorial, relação de recorrência
005 74	Resumir
005 82	Redes neurais com fio aleatoriamente	Pesquisa em profundidade, componente de gráfico BicoNnected
005 83	Fatores primos
006 12	Classificação de DNA	Fundir classificar, contagem de inversões
006 23	500!	Fatorial, grande número inteiro
006 30	Anagramas
006 39	Não seja estreito
006 74	Mudança de moeda
006 79	Soltando bolas
006 84	Determinante integral	Eliminação gaussiana, algoritmo euclidiano
006 86	Conjectura de Goldbach II	Números primários
007 01	O dilema dos arqueólogos	Logaritmo
007 14	Copiando livros	Particionamento linear, pesquisa binária implícita
007 19	Contas de vidro	Rotação lexicograficamente mínima, algoritmo de Duvan
007 27	Equação	Analisagem de expressão, algoritmo de pátio de desvio
007 29	O problema da distância de hamming	Voltando
007 50	Oito queens problema de xadrez	Voltando
007 87	Produto máximo de sub-sequência	Subarray máxima do produto, grande número inteiro
007 93	Conexões de rede
007 96	Links críticos	Pesquisa em profundidade, ponte gráfica
008 20	Largura de banda da Internet
008 33	A água cai
008 68	Maze numérico	Voltando
008 72	Pedindo
009 08	Reconectando sites de computador
009 29	Número labirinto
009 42	Números cíclicos	Número racional, fração decimal, tabela de hash
009 90	Mergulhar em ouro
009 91	Saudações seguras	Combinatória, relação de recorrência, números catalães
011 21	Subseqüência	Janela deslizante
011 75	Escolha das senhoras	Problema de correspondência estável, algoritmo de hap-shapley
012 10	Soma de números primos consecutivos	Números primários
012 52	Vinte perguntas
012 60	Vendas
012 93	Derivação simbólica	Expressão Parsing, algoritmo de pátio de desvio, avaliação simbólica.
013 72	Salto de log
016 50	String number	Combinatória, relação de recorrência
100 03	Bastões de corte
100 04	Bicoloring
100 18	Inverta e adicione	Inteiros, 196-algoritmo
100 61	Quantos zeros e dígitos?	Fatorial, números primos, fatorização, logaritmo
100 79	Corte de pizza	Combinatória, números poligonais centrais
101 07	Qual é a mediana	Fila prioritária, algoritmos online
101 71	Reunião Prof. Miguel
101 93	Tudo que você precisa é amor	Maior divisor comum
102 20	Eu amo grandes números!	Fatorial, grande número inteiro
102 23	Quantos nós	Combinatória, relação de recorrência, números catalães
102 29	Fibonacci modular	Números de Fibonacci, Exponeção Modular
102 45	O problema mais próximo do par	2D Par mais próximo de pontos
102 68	498-BIS	Regra de Horner
102 82	Babelfish	Tabela de hash
102 98	Cordas de poder
103 05	Pedindo tarefas
103 11	Goldbach e Euler	Números primários
103 19	Manhattan
103 27	Flip Sort	Árvore AVL
103 41	Resolva	Numéricos, método de Newton
103 64	Quadrado	Voltar máscaras de bits
103 82	Rega grama	Cobertura gananciosa de intervalo
104 28	As raízes	Encontrar raiz, método de bissecção
104 54	Trexpressão	Expressão analisando, algoritmo de pátio de desvio, números catalães
104 96	Coleta de bipes
105 33	Primos de dígitos
105 67	Ajudando a encher Bates
105 70	Encontro com alienígenas	Permutação, contagem de swaps, contagem de ciclos
105 76	Y2K Bug contábil
105 86	Permanece polinomial
106 00	Concurso ACM e Blackout
106 04	Reação química
106 51	Pebble Solitaire
106 55	Contemplação! Álgebra	Relação de recorrência, exponenciação modular
106 64	Bagagem
106 84	Jackpot
106 99	Conte os fatores	Números primos, decomposição principal
107 23	Genes Cyborg
107 38	Riemann vs Mertens	Números primos, função möbius, função mertens
108 01	Levante pulando
108 10	Ultra Quicksort	Classificação de mesclagem/inserção, contagem de inversões
108 55	Quadrados girados	Rotação da matriz, transposição da matriz
108 70	Recorrências
109 20	Torneira em espiral	Expressão analítica
109 31	Paridade
109 34	Soltando balões de água
109 35	Jogando cartas fora	Fila, lista de ligações individuais
109 38	Circus de pulga
109 54	Adicione tudo	Pilha
109 57	Verificador su Doku	Volta, máscara de bit
109 94	Adição simples	Expressão analítica
110 57	Soma exata
110 60	Bebidas
110 77	Encontre as permutações	Combinatória, relação de recorrência, números Stirling
111 37	Cubrances ingênuos
111 51	Palíndromo mais longo	Programação dinâmica, processamento de string
111 71	SMS	Programação dinâmica, processamento de string, trie
111 95	Outro problema de N -Queen	Volta, máscara de bit
112 27	A bala de prata
112 35	Valores frequentes
112 36	Bomboneria
112 57	Novo plano de marketing	Polígono, raio de círculo inscrito, fila de prioridade
112 58	Partição de string	Programação dinâmica
112 60	Soma da raiz ímpar	Expressão analítica, impl. Pesquisa binária, aritmética modular
112 71	Rede de resistores	Relação de recorrência, expansão assintótica
112 83	Jogando Boggle	Voltando
112 97	Censo	2d SQRT Decomposição
113 62	Lista de telefone	Trie, correspondência de prefixo
114 13	Encha os recipientes
114 20	Cômoda	Combinatória, relação de recorrência
114 56	Trens sorting
114 61	Números quadrados	Pesquisa binária implícita
114 62	Tipo de idade	Count Sort
114 63	Comandos
114 75	Estenda -se ao palíndromo
115 17	Mudança exata
115 36	Menor sub-matriz	Janela deslizante
115 72	Flocos de neve exclusivos	Pesquisa linear, tabela de hash
115 84	Particionamento por Palindromos
116 21	Pequenos fatores	Logaritmo
116 34	Gerar números aleatórios
116 36	Olá, mundo!	Expressão analítica, logaritmo
116 58	Melhores coalizões
116 86	Pegue palitos
116 91	Teste de alergia
117 03	Sqrt, log, pecado	Relação de recorrência
117 14	Classificação cega	Estatísticas de pedidos (2 nd Maior)
117 33	Aeroportos
119 02	Dominador
119 91	Problema fácil de Rujia Liu?	Classificação, pesquisa binária
119 97	K Menores somas
120 86	Potenciômetros	Fenwick Tree
121 05	Maior é melhor (1)
121 05	Maior é melhor (2)
121 92	Grapevine	Pesquisa binária
122 38	Colônia de formigas
123 47	Árvore de pesquisa binária	Árvore de pesquisa binária, travessia pré/pós-ordem
124 55	Barras	Pesquisa completa, retrocesso
124 58	Oh, minhas árvores!
124 62	Retângulo	Pesquisa linear, pilha, máscara de bit
124 94	Substring distinta	Lex. rotação mínima, algoritmo de Duvan, tabela de hash
125 04	Atualizando um dicionário	Classificação rápida
126 40	Maior jogo de soma	Pesquisa linear, subarray máxima da soma, algoritmo de Kadane
126 97	Comprimento mínimo de subarray	Pesquisa linear, subarray máxima da soma, algoritmo de Kadane
127 02	Dilatação	Morfologia binária, dilatação binária de imagem
129 11	Soma do subconjunto	Soma do subconjunto, pesquisa completa, meet-in-the-middle
130 50	Descobrindo caminhos	Combinatória, relação de recorrência
132 82	Cakey McCakeface (1)	Classificação, pesquisa linear
132 82	Cakey McCakeface (2)	Máscara de bits, balde

Concurso internacional de computação de alto desempenho

Fonte de problemas

EU IA	Título	Categorias
C2	Obtenha a imagem	Fractal, Mandelbrot Set, MPI, std::thread

Outros problemas e exercícios

Problemas diversos de diferentes fontes online.

Título	Categorias
Array para a árvore de busca binária	Árvore de pesquisa binária
Array com unidade adj. Pesquisa de diferença	Pesquisa linear
Ponto de transição de matriz classificada binária	Pesquisa binária
Diâmetro da árvore binária	Árvore binária, traseira de profundidade
Vista superior da árvore binária	Árvore binária, a primeira travessia
Pesquisa de matriz bitônica	Pesquisa binária
Elementos comuns em três matrizes	Pesquisa linear
Ponto de conexão em listas vinculadas em forma de Y	Lista de ligações isoladas
Conte substrings anagrama	Mesa de hash, janela deslizante
Conte elementos menores à direita	Árvore AVL
Contam quadrados em códigos postais	Expressão analítica
Conte os trigêmeos	Pesquisa linear, pesquisa de soma em par
Divisibilidade em um fluxo binário	Aritmética modular, divisibilidade
Ponto de equilíbrio	Pesquisa linear
Gerar parênteses (1)	Combinatória, retrocesso
Tem um subconjunto com uma soma	Programação dinâmica
É uma lista vinculada um palíndroma	Lista de ligações isoladas
É uma subárvore (1)	Árvore binária, traseira de profundidade
K-é	Pilha
Maior número com k swaps	Voltando
Maior retângulo em um histograma	Pesquisa linear, pilha
Maior quadrado de uma matriz booleana	Programação dinâmica, maior submatriz quadrada
Últimos dois dígitos de Fibonacci	Números de Fibonacci, aritmética modular, exponenciação binária
Fusão da lista	Lista de ligações isoladas
Lista Mesclar classificar	Lista de ligações individuais, classificação de mesclagem
Substring mais longa de característica distinta	Pesquisa linear
Substring de soma palindrômica mais longa	Pesquisa linear
Elemento da maioria	Algoritmo de voto da maioria de Boyer -Moor
Fazer a matriz aumentando estritamente	Subsequência crescente mais longa, pesquisa binária
Rotação da matriz	Rotação da matriz, transposição da matriz
Distância máxima entre os elementos classificados	Pesquisa linear
Valor numérico máximo em uma string	Pesquisa linear, comparação lexicográfica
Máximo de cada subarray (1)	Janela deslizante, árvore binária equilibrada
Máximo de cada subarray (1)	Janela deslizante, deque
Produto máximo de 3 elementos	Pesquisa linear
Min Stack	Pilha
Elemento mínimo na matriz girada classificada	Pesquisa binária
Número mínimo de saltos (1)	Programação dinâmica
Número mínimo de saltos (2)	Pesquisa linear
Quase classificado	Classificação da pilha, tipo de inserção
Próximo elemento maior	Pesquisa linear, pilha
Nós na distância k na árvore binária	Árvore binária, traseira de profundidade
Número de caminhos em uma grade	Combinatória
Partição uniforme e nós ímpares	Lista de ligações isoladas
Fila como duas pilhas	Fila, pilha
Remova nós duplicados	Lista de ligações isoladas
Remova o nó do meio	Lista de ligações isoladas
Restaurar um alfabeto de um dicionário	Classificação topológica, algoritmo de Kahn
Reverte uma lista de ligações individuais	Lista de ligações isoladas
Palavras reversas em uma string	Pesquisa linear
Gire uma lista de ligações individuais	Lista de ligações isoladas
Pesquisa de matriz girada	Pesquisa binária, pesquisa linear
Segunda maior	Estatísticas do pedido, segundo maior elemento, contador binário
Defina a linha e a coluna se	Pesquisa linear
Menor número em uma permutação	Pesquisa linear
Classificado subseqüência do tamanho 3	Pesquisa linear
Classificado subseqüência do tamanho 4	Pesquisa linear
Raiz quadrada	Pesquisa binária implícita
Subarray com dada soma	Pesquisa linear
Partição de três vias	Particionamento da matriz
Dois elementos com a soma dada	Pesquisa linear, tabela de hash
Matrizes iguais não ordenadas	Sequência, tabela de hash
Lista vinculada ao XOR	Lista duplamente ligada
Subarray de soma zero	Pesquisa linear, tabela de hash