competitive_programming

Programación y ejercicios competitivos

Estas son mis soluciones C ++ de algunos problemas de programación competitivos y varios ejercicios. Se resuelven problemas similares utilizando diferentes algoritmos y estructuras de datos, a veces utilizando los proporcionados por la biblioteca estándar, a veces utilizando mis propias.

La mayoría de las soluciones están en C+11 debido a la limitación ex-UVA en línea de jueces. Algunos de ellos después de la presentación exitosa se modificaron para usar características de C ++ 14/17.

ex-UVA OJ Problemas

Fuente de problemas

IDENTIFICACIÓN	Título	Categorías
001 08	Suma máxima	Búsqueda lineal, subarrray de suma máxima, algoritmo de Kadane
001 09	Scud busters	Casco convexo
001 12	Suming de árboles	Árbol binario
001 20	Pilas de flapjacks	Pila, clasificación de panqueques
001 22	Árboles en el nivel	Árbol binario, recorrido de orden de nivel, búsqueda de amplitud
001 40	Ancho de banda	Permutaciones, retroceso
001 47	Dólares	Programación dinámica, cambio de monedas
001 64	String Computer	Programación dinámica, distancia de edición
002 00	Orden raro	Clasificación topológica, búsqueda de profundidad primero
002 16	Ponerse en línea	Programación dinámica, ruta hamiltoniana, máscaras de bits
002 18	Erradicación de la polilla	Casco convexo
002 22	Viaje presupuestario
002 40	Codificación variable de Radix Huffman	Huffman Tree, búsqueda de profundidad
002 59	Asignación de software
002 64	Cuenta con Cantor
002 70	Alineado
002 94	Divisores
003 34	Identificar eventos concurrentes
003 48	Array óptima Mult. secuencia	Programación dinámica, multiplicación de cadena de matriz
003 50	Números pseudo aleatorios
003 53	Palindromos molestos	Hash rodante polinomial, procesamiento de cadenas
003 57	Contar las formas
003 61	Policías y ladrones
003 72	WhatFix Notation	Árbol binario, conversión previa/posterior a los recorridos posteriores a la orden
003 74	Gran mod	Exponencia binaria, exponencia modular
004 29	Transformación de palabras
004 37	Torre de Babilonia
004 39	Caballero se mueve	Búsqueda de la primera
004 54	Anagramas
004 55	Cadenas periódicas	Cuerdas, algoritmo Knuth - Morris - Pratt
004 59	Conectividad gráfica	Componentes disjuntos de set/sindical
004 69	Humedales de Florida
004 81	Lo que sube	La posterior subsecuencia más antigua, búsqueda binaria
004 82	Matrices de permutaciones
005 01	Caja negra	Árbol avl, iterador de árbol binario
005 07	Jill viaja de nuevo	Búsqueda lineal, subarrray de suma máxima, algoritmo de Kadane
005 16	Tierra principal
005 26	Distancia de cuerda	Programación dinámica, distancia de edición
005 36	Recuperación de árboles	Árbol binario, conversión previa/posterior a los recorridos posteriores a la orden
005 40	Cola de equipo
005 43	Conjetura de Goldbach	Números primos
005 48	Árbol
005 51	Anidando un montón de soportes
005 58	Agujeros
005 62	Monedas divisorias
005 68	Solo los hechos	Factorial, relación de recurrencia
005 74	Resumir
005 82	Redes neuronales con cable al azar	Búsqueda de profundidad primero, componente de gráfico biconectado
005 83	Factores primos
006 12	Clasificación de ADN	Fusionar clasificando, contado por inversiones
006 23	¡500!	Factorial, gran entero
006 30	Anagramas
006 39	No te rompan
006 74	Cambio de monedas
006 79	Bolas de caída
006 84	Determinante integral	Eliminación gaussiana, algoritmo euclidiano
006 86	Goldbach Conjetura II	Números primos
007 01	El dilema de los arqueólogos	Logaritmo
007 14	Copiar libros	División lineal, búsqueda binaria implícita
007 19	Cuentas de vidrio	Rotación lexicográficamente mínima, algoritmo de Duvan
007 27	Ecuación	Animación de expresión, algoritmo de patio de derivación
007 29	El problema de la distancia de hamming	Retroceso
007 50	Problema de ajedrez de ocho reinas	Retroceso
007 87	Producto de subsecuencia máxima	Subarrray de productos máximos, entero grande
007 93	Conexiones de red
007 96	Enlaces críticos	Búsqueda de profundidad primero, puente gráfico
008 20	Ancho de banda de Internet
008 33	Caídas de agua
008 68	Laberinto numérico	Retroceso
008 72	Pedido
009 08	Reconectar sitios de computadora
009 29	Laberinto numérico
009 42	Números cíclicos	Número racional, fracción decimal, tabla hash
009 90	Bucear por oro
009 91	Saludos seguros	Combinatoria, relación de recurrencia, números catalán
011 21	Subvención	Ventana corredera
011 75	Elección de mujeres	Problema de correspondencia estable, algoritmo Gale-Shapley
012 10	Suma de números primos consecutivos	Números primos
012 52	Veinte preguntas
012 60	Ventas
012 93	Derivación simbólica	Análisis de expresión, algoritmo de patio de derivación, evaluación simbólica.
013 72	Salto de registro
016 50	Cadena numérica	Combinatoria, relación de recurrencia
100 03	Palos de corte
100 04	Bicolor
100 18	Revertir y agregar	Enteros, 196-algoritmo
100 61	¿Cuántos ceros y dígitos?	Factorial, números primos, factorización, logaritmo
100 79	Pizza	Combinatoria, números poligonales centrales
101 07	¿Cuál es la mediana?	Cola prioritaria, algoritmos en línea
101 71	Conocer profesor. Miguel
101 93	Todo lo que necesitas es amor	El mayor divisor común
102 20	¡Me encantan los grandes números!	Factorial, gran entero
102 23	Cuantos nodos	Combinatoria, relación de recurrencia, números catalán
102 29	Fibonacci modular	Números de fibonacci, exponencia modular
102 45	El problema de la pareja más cercana	2d par de puntos más cercano
102 68	498-bis	Regla de Horner
102 82	BabeLel	Mesa de hash
102 98	Cuerdas de poder
103 05	Tareas de pedido
103 11	Goldbach y Euler	Números primos
103 19	Manhattan
103 27	Sort de flip	Árbol AVL
103 41	Resolverlo	Numéricos, el método de Newton
103 64	Cuadrado	Retroceso, máscaras de bits
103 82	Hierba riega	Codicioso, cubierta de intervalo
104 28	Las raíces	Hallazgo de raíz, método de bisección
104 54	Trexpresión	Análisis de expresión, algoritmo de patio de derivación, números catalán
104 96	Coleccionando Beepers
105 33	Primos de dígitos
105 67	Ayudando a llenar a Bates
105 70	Reunión con extraterrestres	Permutación, conteo de swaps, ciclos Contado
105 76	Error contable Y2K
105 86	Restos polinómicos
106 00	Concurso ACM y apagón
106 04	Reacción química
106 51	Solitario de guijarros
106 55	¡Contemplación! Álgebra	Relación de recurrencia, exponencia modular
106 64	Equipaje
106 84	Bote
106 99	Cuenta los factores	Números primos, descomposición principal
107 23	Genes cyborg
107 38	Riemann vs Mertens	Números primos, función möbius, función mertens
108 01	Salto de ascensor
108 10	Ultra Quicksort	Sorteo de fusión/inserción, Contado de inversiones
108 55	Cuadrados girados	Rotación de matriz, transposición de matriz
108 70	Recurrencias
109 20	Toque espiral	Expresión analítica
109 31	Paridad
109 34	Dejar caer globos de agua
109 35	Lanzando cartas	Cola, lista de enlaces individuales
109 38	Circo de pulgas
109 54	Agregar todo	Montón
109 57	Su Doku Checker	Retroceso, máscara de bits
109 94	Adición simple	Expresión analítica
110 57	Suma exacta
110 60	Bebidas
110 77	Encuentra las permutaciones	Combinatoria, relación de recurrencia, números de Stirling
111 37	Cubrencia ingeniosa
111 51	Palindromo más largo	Programación dinámica, procesamiento de cadenas
111 71	SMS	Programación dinámica, procesamiento de cadenas, Trie
111 95	Otro problema de N -Queen	Retroceso, máscara de bits
112 27	La bala de plata
112 35	Valores frecuentes
112 36	Tienda de comestibles
112 57	Nuevo plan de marketing	Polígono, radio círculo inscrito, cola prioritaria
112 58	Partición de cadena	Programación dinámica
112 60	Suma de raíz extraña	Expresión analítica, impl. búsqueda binaria, aritmética modular
112 71	Red de resistencias	Relación de recurrencia, expansión asintótica
112 83	Jugando a Boggle	Retroceso
112 97	Censo	Descomposición 2d SQRT
113 62	Lista de teléfonos	Trie, coincidencia de prefijo
114 13	Llenar los contenedores
114 20	Cajón	Combinatoria, relación de recurrencia
114 56	Aturdir
114 61	Números cuadrados	Búsqueda binaria implícita
114 62	Clasificación de edad	Clasificar
114 63	Comandos
114 75	Extenderse a Palindrome
115 17	Cambio exacto
115 36	Subrainal	Ventana corredera
115 72	Copos de nieve únicos	Búsqueda lineal, tabla hash
115 84	Partición por palíndromos
116 21	Pequeños factores	Logaritmo
116 34	Generar números aleatorios
116 36	¡Hola Mundo!	Expresión analítica, logaritmo
116 58	Mejores coaliciones
116 86	Recoger palos
116 91	Prueba de alergia
117 03	Sqrt, registro, pecado	Relación de recurrencia
117 14	Clasificación ciega	Estadísticas de pedido ( 2º más grande)
117 33	Aeropuerto
119 02	Dominante
119 91	¿Problema fácil de Rujia Liu?	Clasificación, búsqueda binaria
119 97	K sumas más pequeñas
120 86	Potenciómetros	Árbol de fenwick
121 05	Más grande es mejor (1)
121 05	Más grande es mejor (2)
121 92	Vid	Búsqueda binaria
122 38	Colonia de hormigas
123 47	Árbol de búsqueda binario	Árbol de búsqueda binaria, transversal previo/posterior a la orden
124 55	Verja	Búsqueda completa, retroceso
124 58	¡Oh, mis árboles!
124 62	Rectángulo	Búsqueda lineal, pila, máscara de bits
124 94	Subcadena distinta	Lex. Rotación mínima, algoritmo de Duvan, tabla hash
125 04	Actualización de un diccionario	Clasificación rápida
126 40	Juego de suma más grande	Búsqueda lineal, subarrray de suma máxima, algoritmo de Kadane
126 97	Longitud de subarrías mínima	Búsqueda lineal, subarrray de suma máxima, algoritmo de Kadane
127 02	Dilatación	Morfología binaria, dilatación de la imagen binaria
129 11	Suma de subconjunto	Suma de subconjunto, búsqueda completa, reunión en el medio
130 50	Descubriendo caminos	Combinatoria, relación de recurrencia
132 82	Cakey McCakeface (1)	Clasificación, búsqueda lineal
132 82	Cakey McCakeface (2)	Máscara de bits, bucketing

Concurso internacional de computación de alto rendimiento

Fuente de problemas

IDENTIFICACIÓN	Título	Categorías
C2	Obtener la imagen	Fractal, Mandelbrot Set, MPI, std::thread

Otros problemas y ejercicios

Problemas varios de diferentes fuentes en línea.

Título	Categorías
Array al árbol de búsqueda binario	Árbol de búsqueda binario
Matriz con unidad adj. búsqueda de diferencia	Búsqueda lineal
Punto de transición de matriz ordenada binaria	Búsqueda binaria
Diámetro de árbol binario	Árbol binario, atravesante de profundidad
Vista de los árboles binarios	Árbol binario, atravesante de amplitud
Bitonic Array Search	Búsqueda binaria
Elementos comunes en tres matriz	Búsqueda lineal
Punto de conexión en listas vinculadas en forma de Y	Lista de enlaces individuales
Subcandres de anagrama de cuenta	Mesa de hash, ventana deslizante
Cuente elementos más pequeños a la derecha	Árbol AVL
Cuente cuadrados en códigos postales	Expresión analítica
Cuenta los trillizos	Búsqueda lineal, búsqueda de suma de par
Divisibilidad en una corriente binaria	Aritmética modular, divisibilidad
Punto de equilibrio	Búsqueda lineal
Generar paréntesis (1)	Combinatoria, retroceso
Tiene un subconjunto con una suma	Programación dinámica
Es una lista vinculada un palíndromo	Lista de enlaces individuales
Es un subárbol (1)	Árbol binario, atravesante de profundidad
K-th elemento en la matriz ordenada de columna de fila	Montón
El número más grande con k swaps	Retroceso
Rectángulo más grande en un histograma	Búsqueda lineal, pila
Cuadro más grande una matriz booleana	Programación dinámica, submatriz cuadrado más grande
Últimos dos dígitos de Fibonacci	Números de fibonacci, aritmética modular, exponencia binaria
Fusionar la lista	Lista de enlaces individuales
Lista de fusiones de fusión	Lista vinculada individualmente, fusionar clasificando
Subcadena de caracteres más largos	Búsqueda lineal
Subcadena de suma palindrómica más larga	Búsqueda lineal
Elemento mayoritario	Algoritmo de voto mayoritario de Boyer -Moore
Haga que la matriz sea estrictamente aumentada	La posterior subsecuencia más antigua, búsqueda binaria
Rotación de matriz	Rotación de matriz, transposición de matriz
Distancia máxima entre elementos ordenados	Búsqueda lineal
Valor numérico máximo en una cadena	Búsqueda lineal, comparación lexicográfica
Máximo de cada subarray (1)	Ventana corredera, árbol binario equilibrado
Máximo de cada subarray (1)	Ventana corredera, deque
Producto máximo de 3 elementos	Búsqueda lineal
Mínimo	Pila
Elemento mínimo en una matriz rotada ordenada	Búsqueda binaria
Número mínimo de saltos (1)	Programación dinámica
Número mínimo de saltos (2)	Búsqueda lineal
Casi ordenado	Clasificación de montón, clasificación de inserción
Siguiente elemento mayor	Búsqueda lineal, pila
Nodos a la distancia K en el árbol binario	Árbol binario, atravesante de profundidad
Número de caminos en una cuadrícula	Combinatorio
Partición uniforme y nodos impares	Lista de enlaces individuales
Cola como dos pilas	Cola, pila
Eliminar nodos duplicados	Lista de enlaces individuales
Eliminar el nodo medio	Lista de enlaces individuales
Restaurar un alfabeto de un diccionario	Clasificación topológica, algoritmo de Kahn
Revertir una lista vinculada por un solo	Lista de enlaces individuales
Reverse las palabras en una cadena	Búsqueda lineal
Gire una lista vinculada por un solo	Lista de enlaces individuales
Búsqueda de matriz rotada	Búsqueda binaria, búsqueda lineal
Segundo más grande	Estadísticas de pedido, segundo elemento más grande, contador binario
Establecer fila y columna si	Búsqueda lineal
El número más pequeño en una permutación	Búsqueda lineal
Subevencia ordenada del tamaño 3	Búsqueda lineal
Subevencia ordenada del tamaño 4	Búsqueda lineal
Raíz cuadrada	Búsqueda binaria implícita
Subarrray con suma dada	Búsqueda lineal
Partición de tres vías	División de matriz
Dos elementos con la suma dada	Búsqueda lineal, tabla hash
Matrices iguales desordenadas	Secuencia, tabla hash
Xor Lista vinculada	Lista doblemente vinculada
Subarray de suma cero	Búsqueda lineal, tabla hash