123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283 |
- %!TEX TS-program = xelatex
- %!TEX encoding = UTF-8 Unicode
- \documentclass[8pt]{extarticle}
- \usepackage[a4paper]{geometry}
- \usepackage[french]{babel}
- \usepackage{amssymb,amsthm,amsmath}
- \usepackage{xltxtra}
- \usepackage{stmaryrd}
- \usepackage{graphicx}
- \usepackage{listings}
- \usepackage{color}
- \lstset{
- extendedchars=true,
- showstringspaces=false,
- escapeinside=``,
- keywordstyle=\color{blue},
- commentstyle=\color[rgb]{0.133,0.545,0.133},
- columns=flexible,
- language=C++,
- tabsize=2,
- basicstyle=\normalsize\selectfont\ttfamily,
- numbers=left,
- frame=lines,
- breaklines=true
- }
- \geometry{
- left=15mm,
- right=7mm,
- top=7mm,
- bottom=15mm
- }
- \usepackage{multicol}
- \setlength{\columnsep}{1cm}
- \title{ACM Notebook -- SWERC 2015}
- \author{4chan: Thomas Espitau -- Shendan Jin -- Olivier Marty}
- \date\today
- \begin{document}
- \maketitle
- \begin{multicols}{2}
- \tableofcontents
- \end{multicols}
- \begin{multicols}{2}
- %\chapter{ACM Cookbook}
- \section{Algorithmique du texte}
- \subsection{Knuth-Morris-Pratt}
- Temps de cuisson : $O(n)$
- {\scriptsize\lstinputlisting{code/kmp.cpp}} % OK
- \subsection{Rabin-Karp 2D}
- {\scriptsize\lstinputlisting{code/RabinKarp.cpp}} % OK
- \subsection{AC Automaton}
- {\scriptsize\lstinputlisting{code/ACAutomaton.cpp}} % OK
- \subsection{Z-function}
- {\scriptsize\lstinputlisting{code/ZFunction.cpp}}
- \subsection{Hash function for string}
- {\scriptsize\lstinputlisting{code/Hash.cpp}}
- \section{Optimisation}
- \subsection{Sparse max-flow}
- {\scriptsize\lstinputlisting{code/Dinic.cc}} % OK % à supprimer ?
- \subsection{Min-cost max-flow}
- {\scriptsize\lstinputlisting{code/MinCostMaxFlow.cc}} % OK
- \subsection{Push-relabel max-flow}
- {\scriptsize\lstinputlisting{code/PushRelabel.cc}} % OK
- \subsection{Min-cost matching}
- {\scriptsize\lstinputlisting{code/MinCostMatching.cc}} % OK
- \subsection{Max bipartite matching $O(EV)$}
- {\scriptsize\lstinputlisting{code/MaxBipartiteMatching.cc}}
- \subsection{Max bipartite matching $O(E\sqrt V)$}
- {\scriptsize\lstinputlisting{code/MaxBipartiteMatching_sqrt.cc}} % OK
- \subsection{Stable matchings}
- {\scriptsize\lstinputlisting{code/StableMatchings.cpp}}
- \subsection{Global min cut}
- {\scriptsize\lstinputlisting{code/MinCut.cc}}
- \section{Géométrie}
- \subsection{Convex hull}
- {\scriptsize\lstinputlisting{code/ConvexHull.cc}} % OK
- \subsection{Miscellaneous geometry}
- {\scriptsize\lstinputlisting{code/Geometry.cpp}}
- % OK RotateCCW
- % OK ComputeSignedArea
- \subsection{Half-plane intersection}
- {\scriptsize\lstinputlisting{code/HalfPlaneIntersection.cpp}}
- \subsection{Closest Pair}
- {\scriptsize\lstinputlisting{code/ClosestPair.cpp}}
- \subsection{Slow Delaunay triangulation}
- {\scriptsize\lstinputlisting{code/Delaunay.cpp}} % TODO chercher algo en N (incremental flip)
- \section{Algorithmes numériques}
- \subsection{Number theoretic algorithms (modular, Chinese remainder, linear Diophantine)}
- {\scriptsize\lstinputlisting{code/Euclid.cpp}}
- \subsection{Discrete Logarithm $O(\sqrt n\log n)$}
- {\scriptsize\lstinputlisting{code/DiscreteLog.cpp}}
- \subsection{Euler's function}
- {\scriptsize\lstinputlisting{code/Euler.cpp}}
- \subsection{Systems of linear equations, matrix inverse, determinant}
- {\scriptsize\lstinputlisting{code/GaussJordan.cc}}
- \subsection{Reduced row echelon form, matrix rank}
- {\scriptsize\lstinputlisting{code/ReducedRowEchelonForm.cc}}
- \subsection{Fast Fourier transform}
- {\scriptsize\lstinputlisting{code/FFT.cpp}} % OK
- \subsection{Simplex algorithm}
- {\scriptsize\lstinputlisting{code/Simplex.cc}} % OK
- \subsection{Binomial coefficient}
- {\scriptsize\lstinputlisting{code/Binom.cpp}}
- \subsection{BigInt}
- {\scriptsize\lstinputlisting{code/BigInt.cpp}}
- \subsection{Sieve of Eratosthenes}
- {\scriptsize\lstinputlisting{code/Sieve.cpp}}
- \section{Graphes}
- \subsection{Fast Dijkstra's algorithm}
- {\scriptsize\lstinputlisting{code/FastDijkstra.cc}}
- \subsection{Bellman-Ford}
- {\scriptsize\lstinputlisting{code/BellmanFord.cpp}} % OK
- \subsection{Fast Bellman-Ford}
- {\scriptsize\lstinputlisting{code/SPFA.cpp}}
- \subsection{Floyd-Warshall (all shortest path)}
- {\scriptsize\lstinputlisting{code/FloydWarshall.cpp}}
- \subsection{Minimum Spanning Tree -- Kruskal}
- {\scriptsize\lstinputlisting{code/MST.cpp}}
- \subsection{Strongly connected components}
- {\scriptsize\lstinputlisting{code/SCC.cc}}
- \subsection{DFS/BFS}
- {\scriptsize\lstinputlisting{code/BFS_DFS.cpp}} % OK
- \subsection{Topological Sort}
- {\scriptsize\lstinputlisting{code/TopologicalSort.cpp}}
- \subsection{Eulerian Circuit}
- {\scriptsize\lstinputlisting{code/EulerCircuit.cpp}}
- \subsection{Test Bipartite Graph}
- {\scriptsize\lstinputlisting{code/BipartiteTest.cpp}}
- \subsection{Cut vertex / Bridge}
- {\scriptsize\lstinputlisting{code/CutVertexBridge.cpp}}
- \subsection{Biconnected component}
- {\scriptsize\lstinputlisting{code/BCC.cpp}}
- \subsection{Exact Cover}
- {\scriptsize\lstinputlisting{code/ExactCover.cpp}}
- \subsection{Lowest Common Ancestor}
- {\scriptsize\lstinputlisting{code/LCA.cpp}}
- \section{Structures de données}
- \subsection{Suffix arrays}
- {\scriptsize\lstinputlisting{code/SuffixArray.cpp}}
- \subsection{Binary Indexed Tree}
- {\scriptsize\lstinputlisting{code/BIT.cc}}
- \subsection{Union-Find Set}
- {\scriptsize\lstinputlisting{code/UnionFind.cc}}
- \subsection{KD-tree}
- {\scriptsize\lstinputlisting{code/KDTree.cc}}
- \subsection{Segment Tree}
- {\scriptsize\lstinputlisting{code/SegmentTree.cpp}} % OK
- \subsection{Treap}
- {\scriptsize\lstinputlisting{code/Treap.cpp}} % OK
- \subsection{Bits Sets}
- {\scriptsize\lstinputlisting{code/BitSet.cpp}} % OK
- \subsection{RMQ Offline}
- {\scriptsize\lstinputlisting{code/RMQ_offline.cpp}}
- \subsection{Trie}
- {\scriptsize\lstinputlisting{code/Trie.cpp}}
- \subsection{Rank Tree}
- {\scriptsize\lstinputlisting{code/RankTree.cpp}}
- \section{Divers}
- \subsection{Longest increasing subsequence}
- {\scriptsize\lstinputlisting{code/LongestIncreasingSubsequence.cpp}}
- \subsection{Maximum rectangle under an histogram / in a matrix}
- {\scriptsize\lstinputlisting{code/BiggestRectangle.cpp}}
- \subsection{Number of inversions}
- {\scriptsize\lstinputlisting{code/Inversion.cpp}} % OK
- \subsection{Dichotomie}
- {\scriptsize\lstinputlisting{code/Dichotomie.cpp}} % regarder
- \subsection{2 SAT}
- {\scriptsize\lstinputlisting{code/2SAT.cpp}}
- \subsection{Dates}
- {\scriptsize\lstinputlisting{code/Dates.cpp}}
- \subsection{Prime numbers}
- {\scriptsize\lstinputlisting{code/Primes.cc}}
- \subsection{Tips}
- {\scriptsize\lstinputlisting{code/Tips.cpp}}
- \subsection{Skeleton}
- {\scriptsize\lstinputlisting{code/Skeleton.cpp}}
- \end{multicols}
- \renewcommand{\arraystretch}{2} % ver
- \setlength\tabcolsep{2.3em} % hor
- \begin{tabular}{ | l | l | l | l | l | l | l | l | l | l | l | }
- \hline
- & A & B & C & D & E & F & G & H & I & J \\
- \hline
- Ol &&&&&&&&&&\\
- \hline
- Sh &&&&&&&&&&\\
- \hline
- Th &&&&&&&&&&\\
- \hline
- C&&&&&&&&&&\\
- O&&&&&&&&&&\\
- M&&&&&&&&&&\\
- M&&&&&&&&&&\\
- E&&&&&&&&&&\\
- N&&&&&&&&&&\\
- T&&&&&&&&&&\\
- A&&&&&&&&&&\\
- I&&&&&&&&&&\\
- R&&&&&&&&&&\\
- E&&&&&&&&&&\\
- S&&&&&&&&&&\\
- \hline
- \end{tabular}
- \end{document}
|