From 545265f2f3992e15c45f1bbb99e04a27e1fc7856 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 30 Jun 2024 00:26:10 +0200 Subject: improvements --- datastructures/datastructures.tex | 1 + graph/LCA_sparse.cpp | 2 +- graph/cycleCounting.cpp | 2 +- graph/graph.tex | 4 ++-- graph/matching.cpp | 2 +- latexHeaders/commands.sty | 5 +++++ math/discreteNthRoot.cpp | 2 +- math/inversions.cpp | 2 +- math/lgsFp.cpp | 2 +- math/math.tex | 2 +- other/other.tex | 2 +- tcr.pdf | Bin 666019 -> 665586 bytes 12 files changed, 16 insertions(+), 10 deletions(-) diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 1ccefaa..d35dfb0 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -22,6 +22,7 @@ \end{methods} \sourcecode{datastructures/waveletTree.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{Fenwick Tree} \begin{methods} diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp index 2a864c0..649e697 100644 --- a/graph/LCA_sparse.cpp +++ b/graph/LCA_sparse.cpp @@ -2,7 +2,7 @@ struct LCA { vector depth; vector visited, first; int idx; - SparseTable st; //sparse table von oben + SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector>& adj, int root) { depth.assign(2 * sz(adj), 0); diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp index 9772706..bd7a219 100644 --- a/graph/cycleCounting.cpp +++ b/graph/cycleCounting.cpp @@ -39,7 +39,7 @@ struct cylces { //cycle must be constrcuted from base bool isCycle(cycle cur) { if (cur.none()) return false; - init(sz(adj)); // union find + init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ for (int i = 0; i < sz(edges); i++) { if (cur[i]) { cur[i] = false; diff --git a/graph/graph.tex b/graph/graph.tex index 0f516ac..9232090 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -225,7 +225,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} \sourcecode{graph/dinicScaling.cpp} -\vfill* +\vfill\null \columnbreak \optional{ @@ -256,7 +256,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} -\vfill* +\vfill\null \columnbreak diff --git a/graph/matching.cpp b/graph/matching.cpp index f059351..2513604 100644 --- a/graph/matching.cpp +++ b/graph/matching.cpp @@ -12,7 +12,7 @@ int max_matching() { mat[v][u] = rand() % (MOD - 1) + 1; mat[u][v] = MOD - mat[v][u]; }}} - gauss(sz(adj), MOD); //LGS unten + gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ int rank = 0; for (auto& row : mat) { if (*min_element(all(row)) != 0) rank++; diff --git a/latexHeaders/commands.sty b/latexHeaders/commands.sty index da78745..edbba1b 100644 --- a/latexHeaders/commands.sty +++ b/latexHeaders/commands.sty @@ -30,12 +30,17 @@ %\ifthenelse{\equal{#3}{}}{}{\runtime{#3}} \newcommand{\sourcecode}[1]{% + \label{code:#1}% \nobreak% % \needspace{3\baselineskip}% % \nopagebreak% \lstinputlisting{#1}% \penalty -1000% } +\newcommand{\sourceref}[1]{{% + \color{comment}\bfseries\itshape{}Seite \pageref{code:#1}% +}} + \newcommand{\method}[4][]{\texttt{#2}~~#3~~\runtime{#4}#1\par} \newenvironment{methods}[1][lll]{% diff --git a/math/discreteNthRoot.cpp b/math/discreteNthRoot.cpp index 9249f73..7201b2b 100644 --- a/math/discreteNthRoot.cpp +++ b/math/discreteNthRoot.cpp @@ -1,5 +1,5 @@ ll root(ll a, ll b, ll m) { ll g = findPrimitive(m); - ll c = dlog(powMod(g, a, m), b, m); //diskreter logarithmus + ll c = dlog(powMod(g, a, m), b, m); //dLog @\sourceref{math/discreteLogarithm.cpp}@ return c < 0 ? -1 : powMod(g, c, m); } diff --git a/math/inversions.cpp b/math/inversions.cpp index 051408c..9e47f9b 100644 --- a/math/inversions.cpp +++ b/math/inversions.cpp @@ -1,5 +1,5 @@ ll inversions(const vector& v) { - Tree> t; //ordered statistics tree + Tree> t; //ordered statistics tree @\sourceref{datastructures/pbds.cpp}@ ll res = 0; for (ll i = 0; i < sz(v); i++) { res += i - t.order_of_key({v[i], i}); diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp index 7dcd354..7081fea 100644 --- a/math/lgsFp.cpp +++ b/math/lgsFp.cpp @@ -23,4 +23,4 @@ void gauss(int n, ll mod) { takeAll(n, i, mod); done[i] = true; }} -// für Eindeutigkeit, Existenz etc. siehe LGS +// für Eindeutigkeit, Existenz etc. siehe LGS über R diff --git a/math/math.tex b/math/math.tex index dc0eb00..c157e1b 100644 --- a/math/math.tex +++ b/math/math.tex @@ -257,7 +257,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code \sourcecode{math/transforms/fft.cpp} \sourcecode{math/transforms/ntt.cpp} - \vfill* + \vfill\null \columnbreak \sourcecode{math/transforms/bitwiseTransforms.cpp} Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!) diff --git a/other/other.tex b/other/other.tex index a21eb37..38434a5 100644 --- a/other/other.tex +++ b/other/other.tex @@ -227,7 +227,7 @@ \item \textbf{Centroid Decomposition:} Wähle zufälligen Knoten und mache DFS. Verschiebe ausgewählten Knoten in Richtung des tiefsten Teilbaums, bis Centroid gefunden. Entferne Knoten, mache rekursiv in Teilbäumen weiter. Laufzeit:~\runtime{\abs{V} \cdot \log(\abs{V})}. - \item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres verhält sich periodisch alle $400$ Jahre. + \item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres ist alle $400$ Jahre gleich. \item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:} Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von diff --git a/tcr.pdf b/tcr.pdf index 7114518..ec0e434 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3