123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120 |
- regarder le fichier de christoph fuch_bien.pdf (RMQ, bigint, ... plein de choses à prendre !)
- https://sites.google.com/site/indy256/algo/fenwick_tree
- Big integer
- Faire des algos de flots et de matching plus courts
- Liste des problèmes
- ===================
- Chaînes de caractères
- OK Recherche de motifs (Knuth-Morris-Pratt, Rabin-Karp)
- Arbre lexicographique
- Plus grande période
- Plus long palindrome (Manacher)
- Facteur commun maximal
- Programmation dynamique
- Plus court chemin dans un DAG
- Plus longue sous-séquence commune
- Distance d'édition de Levenshtein
- Plus longue sous-séquence commune
- OK Plus longue sous-séquence croissante
- Stratégie gagnante dans un jeu à deux joueurs
- Multiplication d'une séquence de matrices
- Tableaux
- OK Fusion de listes triées
- Fenêtre avec k éléments distincts
- OK Somme d'un intervalle (différence de sommes prefixes)
- Doublon d'un intervalle
- Plus grande somme d'un intervalle
- OK Requêtes de minimum sur un intervalle (treap, segment tree)
- OK Requêtes de somme sur un intervalle (treap, segment tree)
- Intervalles
- OK Arbre d'intervalles
- Union d'intervalles
- Couverture d'intervalles
- Graphes
- OK DFS : Parcours en profondeur
- OK BFS : Parcours en largeur
- OK Composantes connexes
- OK Composantes biconnexes
- OK Tri topologique
- OK 2-SAT
- OK Composantes fortement connexes
- Cycles
- OK Chemin eulérien
- Problème du postier chinois (Google Hash Code 2014)
- Cycles de ratio poids sur longueur minimal (Karp)
- Cycles de ratio coût sur temps minimal
- Plus courts chemins
- Graphes avec poids 0 ou 1
- OK Graphes avec poids positifs ou nuls (Dijkstra)
- OK Graphes avec poids arbitraires (Bellman-Ford)
- OK Toutes paires source-destination
- Grille (dynamique ?)
- Couplages et flots
- OK Couplage maximum biparti
- OK Couplage parfait de poids maximal (hongrois, Kuhn-Munkres)
- Couplage planaire sans croisement
- OK Mariage stable (Gale-Shapley)
- OK Flot maximal (Ford-Fulkerson, Edmonds-Karp)
- OK Coupe minimale
- Coupe minimale pour graphe planaire (plus court chemin dans le graphe dual)
- Largeur d'un ordre partiel (nombre d'el - couplage max ?)
- Arbres
- OK Arbre couvrant de poids minimal
- Requêtes d'ancêtre commun le plus proche (variante treap : on peut utiliser RMQ)
- OK Plus long chemin dans un arbre (dynamique)
- Ensembles
- Sac à dos
- Rendu de monnaie
- SUBSET-SUM
- k-somme
- Points et polygones
- OK Enveloppe convexe
- OK Paire de points les plus proches
- Polygone rectilinéaire simple
- Rectangles
- OK Plus grand carré dans une grille (dynamique)
- OK Plus grand rectangle dans un histogramme
- OK Plus grand rectangle dans une grille
- Union de rectangles
- Union de rectangles disjoints
- Calculs
- OK PGCD
- OK Bézout
- OK Coefficients binomiaux
- OK Exponentiation rapide
- OK Nombres premiers
- Évaluation d'une expression arithmétique
- Systèmes d'équations linéaires
- Exploration exhaustive
- Sudoku
- OK Énumération de permutations (next_permutation)
- Le compte est bon
|