competitive_programming

Programmation et exercices compétitifs

Ce sont mes solutions C ++ de certains problèmes de programmation compétitifs et divers exercices. Des problèmes similaires sont résolus en utilisant différents algorithmes et structures de données - parfois en utilisant ceux fournis par la bibliothèque standard, parfois en utilisant mes propres.

La plupart des solutions sont en C + 11 en raison de la limitation des juges en ligne ex-UVA. Certains d'entre eux après une soumission réussie ont été modifiés pour utiliser les fonctionnalités C ++ 14/17.

Problèmes ex-uva oj

Problèmes Source

IDENTIFIANT	Titre	Catégories
001 08	Somme maximale	Recherche linéaire, maximum de sous-réseau, algorithme de Kadane
001 09	Scud Busters	Coque convexe
001 12	Sommage des arbres	Arbre binaire
001 20	Piles de flapjacks	Pile, tri à la crêpe
001 22	Arbres au niveau	Arbre binaire, traversée d'ordre de niveau, étendue première recherche
001 40	Bande passante	Permutations, retour en arrière
001 47	Dollar	Programmation dynamique, changement de pièce
001 64	Chaîne ordinateur	Programmation dynamique, modifier la distance
002 00	Ordre rare	Tri topologique, recherche en profondeur d'abord
002 16	Faire la queue	Programmation dynamique, chemin hamiltonien, masques de bits
002 18	Éradication	Coque convexe
002 22	Voyage à petit budget
002 40	Encodage de Huffman variable Radix	Huffman Tree, recherche en profondeur d'abord
002 59	Allocation logicielle
002 64	Comptez sur Cantor
002 70	Aligner
002 94	Diviseurs
003 34	Identifier les événements simultanés
003 48	Tableau optimal Mult. séquence	Programmation dynamique, multiplication de la chaîne matricielle
003 50	Pseudo nombres aléatoires
003 53	Palindromes embêtants	Hachage de roulement polynôme, traitement des cordes
003 57	Comptez les façons
003 61	Flics et voleurs
003 72	NOTATION DE WHATFIX	Arbre binaire, conversion de traverse pré- / in / post-ordre
003 74	Gros mod	Exponentiation binaire, exponentiation modulaire
004 29	Transformation des mots
004 37	Tour de Babylone
004 39	Knight se déplace	Recherche de largeur
004 54	Anagrammes
004 55	Chaînes périodiques	Strings, algorithme Knuth - Morris - Pratt
004 59	Connectivité graphique	Composants connectés à l'ensemble disjoint / Union, graphique
004 69	Zones humides de Floride
004 81	Ce qui monte	Sous-subséquence la plus longue et la recherche binaire
004 82	Tableaux de permutations
005 01	Boîte noire	Arbre AVL, itérateur binaire
005 07	Jill monte à nouveau	Recherche linéaire, maximum de sous-réseau, algorithme de Kadane
005 16	Terre de premier ordre
005 26	Distance des cordes	Programmation dynamique, modifier la distance
005 36	Récupération des arbres	Arbre binaire, conversion de traverse pré- / in / post-ordre
005 40	File d'attente d'équipe
005 43	Conjecture de Goldbach	Nombres premiers
005 48	Arbre
005 51	Nidification des supports
005 58	Trous de ver
005 62	Pièces en division
005 68	Juste les faits	Relation factorielle et récidive
005 74	Résumer
005 82	Filets neuronaux câblés au hasard	Recherche en profondeur d'abord, composant graphique biconnecté
005 83	Facteurs privilégiés
006 12	Tri d'ADN	Fusion tri, les inversions comptant
006 23	500!	Factorielle, grand entier
006 30	Anagrammes
006 39	Ne vous faites pas faire des lancers
006 74	Changement de pièce
006 79	Bouchage des balles
006 84	Déterminant intégral	Élimination gaussienne, algorithme euclidien
006 86	Conjecture Goldbach II	Nombres premiers
007 01	Le dilemme des archéologues	Logarithme
007 14	Livres de copie	Partionnement linéaire, recherche binaire implicite
007 19	Perles de verre	Rotation lexicographiquement minimale, algorithme de Duvan
007 27	Équation	Analyse d'expression, algorithme de cour shunting
007 29	Le problème de distance de Hamming	Retour en arrière
007 50	Problème d'échecs de huit reines	Retour en arrière
007 87	Produit de sous-séquence maximal	Sous-réseau maximal de produit, grand entier
007 93	Connexions réseau
007 96	Liens critiques	Recherche en profondeur d'abord, pont graphique
008 20	Bande passante sur Internet
008 33	Chutes d'eau
008 68	Labyrinthe numérique	Retour en arrière
008 72	Commande
009 08	Reconnecter les sites informatiques
009 29	Labyrinthe
009 42	Nombres cycliques	Nombre rationnel, fraction décimale, table de hachage
009 90	Plongée pour l'or
009 91	Salutations sûres	Combinatoire, relation de récidive, nombres catalans
011 21	Subséquence	Fenêtre coulissante
011 75	Choix des femmes	Problème d'appariement stable, algorithme Gale-Shapley
012 10	Somme de nombres premiers consécutifs	Nombres premiers
012 52	Vingt questions
012 60	Ventes
012 93	Dérivation symbolique	Analyse d'expression, algorithme de cour shunting, symbolic ev.
013 72	Saut de journal
016 50	Chaîne de numéros	Combinatoire, relation de récidive
100 03	Bâtons de coupe
100 04	Bicoloring
100 18	Inverser et ajouter	Entiers, 196-algorithme
100 61	Combien de zéros et de chiffres?	Factorielle, nombres premiers, factorisation, logarithme
100 79	Coupe de pizza	Combinatoire, nombres polygonaux centraux
101 07	Quelle est la médiane	File d'attente prioritaire, algorithmes en ligne
101 71	Rencontrer le professeur. Miguel
101 93	Tout ce dont vous avez besoin, c'est de l'amour	Plus grand diviseur commun
102 20	J'adore les grands nombres!	Factorielle, grand entier
102 23	Combien de nœuds	Combinatoire, relation de récidive, nombres catalans
102 29	Fibonacci modulaire	Nombres de Fibonacci, Exponentiation modulaire
102 45	Le problème le plus proche de la paire	Paire de points 2D
102 68	498-bis	Rule de Horner
102 82	Babelfish	Table de hachage
102 98	Cordes de puissance
103 05	Commande des tâches
103 11	Goldbach et Euler	Nombres premiers
103 19	Manhattan
103 27	Rallonge	Arbre avl
103 41	Résoudre	Numeric, méthode de Newton
103 64	Carré	Backtracking, masques bits
103 82	Arrosage de l'herbe	Coiffeur gourmand et intervalle
104 28	Les racines	Root Restruction, méthode de bissection
104 54	Expression	Analyse d'expression, algorithme de cour shunting, nombres catalans
104 96	Collecte de biètes
105 33	Primes de chiffres
105 67	Aider à remplir Bates
105 70	Rencontrer des extraterrestres	Permutation, swaps comptage, comptage des cycles
105 76	Bogue comptable Y2K
105 86	Restes polynômes
106 00	Concours ACM et panne d'électricité
106 04	Réaction chimique
106 51	Galet solitaire
106 55	Contemplation! Algèbre	Relation de récidive, exponentiation modulaire
106 64	Bagage
106 84	Cagnotte
106 99	Comptez les facteurs	Nombres premiers, décomposition privilégiée
107 23	Gènes cyborg
107 38	Riemann vs Mertens	Nombres premiers, fonction Möbius, fonction Mertens
108 01	Saut de lifting
108 10	Ultra Quicksort	Tour de fusion / insertion, comptage des inversions
108 55	Carrés tournés	Rotation matricielle, transposition matricielle
108 70	Récidives
109 20	Spirale	Expression analytique
109 31	Parité
109 34	Drop boser les ballons
109 35	Jeter les cartes	File d'attente, liste uniquement liée
109 38	Cirque aux puces
109 54	Ajouter tout	Tas
109 57	Chèque su doku	Retour en arrière, masque de bits
109 94	Ajout simple	Expression analytique
110 57	Somme exacte
110 60	Boissons
110 77	Trouvez les permutations	Combinatoire, relation de récidive, chiffres de Stirling
111 37	Cubrenité ingénieuse
111 51	Le plus long palindrome	Programmation dynamique, traitement des cordes
111 71	SMS	Programmation dynamique, traitement des cordes, Trie
111 95	Un autre problème de N -queen	Retour en arrière, masque de bits
112 27	La solution miracle
112 35	Valeurs fréquentes
112 36	Épicerie
112 57	Nouveau plan marketing	Polygone, rayon du cercle inscrit, file d'attente prioritaire
112 58	Partition de cordes	Programmation dynamique
112 60	Somme racine étrange	Expression analytique, impl. recherche binaire, arithmétique modulaire
112 71	Treillis de résistances	Relation de récidive, expansion asymptotique
112 83	Jouer Boggle	Retour en arrière
112 97	Recensement	2d SQRT Décomposition
113 62	Liste de téléphonie	TRIE, PRÉFIX MATCHING
114 13	Remplissez les conteneurs
114 20	Commode	Combinatoire, relation de récidive
114 56	Sort de trains
114 61	Nombres carrés	Recherche binaire implicite
114 62	Tri	Compter le tri
114 63	Commandos
114 75	S'étendre à Palindrome
115 17	Changement exact
115 36	Les plus petites sous-tableau	Fenêtre coulissante
115 72	Flocons de neige uniques	Recherche linéaire, table de hachage
115 84	Partitionnement par Palindromes
116 21	Facteurs	Logarithme
116 34	Générer des nombres aléatoires
116 36	Bonjour le monde!	Expression analytique, logarithme
116 58	Meilleures coalitions
116 86	Ramasser les bâtons
116 91	Test d'allergie
117 03	Sqrt, journal, péché	Relation de récidive
117 14	Tri aveugle	Statistiques de commande (2 m plus grandes)
117 33	Aéroports
119 02	Dominateur
119 91	Problème facile de Rujia Liu?	Tri, recherche binaire
119 97	K Les plus petites sommes
120 86	Potentiomètres	Arbre de fenwick
121 05	Plus gros c'est mieux (1)
121 05	Plus gros c'est mieux (2)
121 92	Vigne	Recherche binaire
122 38	Colonie des fourmis
123 47	Arbre de recherche binaire	Arbre de recherche binaire, traversée pré / après l'ordre
124 55	Bars	Recherche complète, retour en arrière
124 58	Oh, mes arbres!
124 62	Rectangle	Recherche linéaire, pile, masque de bits
124 94	Substrating distinct	Lex. Rotation minimale, algorithme de Duvan, table de hachage
125 04	Mise à jour d'un dictionnaire	Tri rapide
126 40	Plus grand jeu de somme	Recherche linéaire, maximum de sous-réseau, algorithme de Kadane
126 97	Longueur minimale de la sous-bande	Recherche linéaire, maximum de sous-réseau, algorithme de Kadane
127 02	Dilatation	Morphologie binaire, dilatation de l'image binaire
129 11	Sous-ensemble	Somme de sous-ensemble, recherche complète, rencontre au milieu
130 50	Découvrir des chemins	Combinatoire, relation de récidive
132 82	Cakey McCakeface (1)	Tri, recherche linéaire
132 82	Cakey McCakeface (2)	Masque de bits, seau

Concours international de calcul haute performance

Problèmes Source

IDENTIFIANT	Titre	Catégories
C2	Obtenez l'image	Fractal, Mandelbrot Set, MPI, std::thread

Autres problèmes et exercices

Problèmes divers de différentes sources en ligne.

Titre	Catégories
Arbre de recherche binaire	Arbre de recherche binaire
Tableau avec unité adj. Recherche de différence	Recherche linéaire
Point de transition triée binaire	Recherche binaire
Diamètre de l'arbre binaire	Arbre binaire, profondeur en profondeur de traversée
Vue de dessus de l'arbre binaire	Arbre binaire, largeur de traversée
Recherche de bitonic	Recherche binaire
Éléments communs en trois tableau	Recherche linéaire
Point de connexion dans les listes liées en forme de Y	Liste liée à un seul
Count des sous-chaînes anagrammes	Table de hachage, fenêtre coulissante
Compter les plus petits éléments à droite	Arbre avl
Compter les carrés dans les codes postaux	Expression analytique
Comptez les triplets	Recherche linéaire, recherche de somme de paire
Divisibilité dans un flux binaire	Arithmétique modulaire, divisibilité
Point d'équilibre	Recherche linéaire
Générer des parenthèses (1)	Combinatoire, retour en arrière
A un sous-ensemble avec une somme	Programmation dynamique
Est une liste liée un palindrome	Liste liée à un seul
Est un sous-arbre (1)	Arbre binaire, profondeur en profondeur de traversée
K-tth Element in Row-Colonne Trised Matrix	Tas
Le plus grand nombre avec k swaps	Retour en arrière
Le plus grand rectangle dans un histogramme	Recherche linéaire, pile
Le plus grand carré une matrice booléenne	Programmation dynamique, plus grand sous-subatrice carrée
Deux derniers chiffres de Fibonacci	Nombres de Fibonacci, arithmétique modulaire, exponentiation binaire
Liste de la liste	Liste liée à un seul
Liste du tri de fusion	Liste uniquement liée, fusion
Sous-chaîne à caractère distinct le plus long	Recherche linéaire
La plus longue sous-chaîne palindromique	Recherche linéaire
Élément majoritaire	Algorithme de vote majoritaire de Boyer - Moore
Faire une augmentation strictement augmentée	Sous-subséquence la plus longue et la recherche binaire
Rotation matricielle	Rotation matricielle, transposition matricielle
Distance maximale entre les éléments triés	Recherche linéaire
Valeur numérique maximale dans une chaîne	Recherche linéaire, comparaison lexicographique
Maximum de chaque sous-réseau (1)	Fenêtre coulissante, arbre binaire équilibré
Maximum de chaque sous-réseau (1)	Fenêtre coulissante, Deque
Produit maximum de 3 éléments	Recherche linéaire
Mine	Empiler
Élément minimum dans un tableau rotatif trié	Recherche binaire
Nombre minimum de sauts (1)	Programmation dynamique
Nombre minimum de sauts (2)	Recherche linéaire
Presque trié	Tri tas, tri insertion
Prochain plus grand élément	Recherche linéaire, pile
Nœuds à distance k dans l'arbre binaire	Arbre binaire, profondeur en profondeur de traversée
Nombre de chemins dans une grille	Combinatoire
Partition même et étranges nœuds	Liste liée à un seul
File d'attente comme deux piles	File d'attente, pile
Supprimer les nœuds en double	Liste liée à un seul
Supprimer le nœud intermédiaire	Liste liée à un seul
Restaurer un alphabet d'un dictionnaire	Tri topologique, algorithme de Kahn
Inverser une liste de liaison unique	Liste liée à un seul
Mots inversés dans une chaîne	Recherche linéaire
Faire tourner une liste liée à un seul	Liste liée à un seul
Recherche de tableau tourné	Recherche binaire, recherche linéaire
Deuxième plus grand	Statistiques de commande, deuxième élément le plus grand, comptoir binaire
Réglez la ligne et la colonne si	Recherche linéaire
Le plus petit nombre dans une permutation	Recherche linéaire
Sous-séquence triée de la taille 3	Recherche linéaire
Sous-séquence triée de taille 4	Recherche linéaire
Racine carrée	Recherche binaire implicite
Sous-réseau avec une somme donnée	Recherche linéaire
Partition à trois voies	Partitionnement de la table
Deux éléments avec la somme donnée	Recherche linéaire, table de hachage
Tableaux égaux non ordonnés	Séquence, table de hachage
Liste liée XOR	Liste à double liaison
Sous-traits à somme nulle	Recherche linéaire, table de hachage