From 9e8344e44eb06ac4a8618413ff2b2311c6348dad Mon Sep 17 00:00:00 2001 From: MZuenni Date: Fri, 28 Jun 2024 14:54:23 +0200 Subject: polishing --- datastructures/unionFind.cpp | 10 +++++++--- geometry/formulars.cpp | 2 +- geometry/geometry.tex | 4 ++-- geometry/linesAndSegments.cpp | 4 ++-- graph/graph.tex | 4 ++-- math/math.tex | 12 ++++++------ other/other.tex | 18 ++++++++++++------ string/string.tex | 4 ++-- tcr.pdf | Bin 664604 -> 666019 bytes 9 files changed, 34 insertions(+), 24 deletions(-) diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp index 35843cd..68eef86 100644 --- a/datastructures/unionFind.cpp +++ b/datastructures/unionFind.cpp @@ -1,5 +1,5 @@ // unions[i] >= 0 => unions[i] = parent -// unions[i] < 0 => unions[i] = -height +// unions[i] < 0 => unions[i] = -size vector unions; void init(int n) { //Initialisieren @@ -11,12 +11,16 @@ int findSet(int n) { // Pfadkompression return unions[n] = findSet(unions[n]); } -void linkSets(int a, int b) { // Union by rank. +void linkSets(int a, int b) { // Union by size. if (unions[b] > unions[a]) swap(a, b); - if (unions[b] == unions[a]) unions[b]--; + unions[b] += unions[a]; unions[a] = b; } void unionSets(int a, int b) { // Diese Funktion aufrufen. if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b)); } + +int size(int a) { + return -unions[findSet(a)]; +} diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp index e34b3c6..22e9e32 100644 --- a/geometry/formulars.cpp +++ b/geometry/formulars.cpp @@ -34,7 +34,7 @@ bool isCoplanar(pt a, pt b, pt c, pt d) { return abs((b - a) * (c - a) * (d - a)) < EPS; } -// identifiziert winkel zwischen Vektoren u und v +// charakterisiert winkel zwischen Vektoren u und v pt uniqueAngle(pt u, pt v) { pt tmp = v * conj(u); ll g = abs(gcd(real(tmp), imag(tmp))); diff --git a/geometry/geometry.tex b/geometry/geometry.tex index d753ed6..95c0adb 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -17,10 +17,10 @@ \begin{algorithm}{Konvexehülle} \begin{methods} - \method{convexHull}{berechnet Konvexehülle}{n\*\log(n)} + \method{convexHull}{berechnet konvexe Hülle}{n\*\log(n)} \end{methods} \begin{itemize} - \item Konvexehülle gegen den Uhrzeigersinn sortiert + \item Konvexe Hülle gegen den Uhrzeigersinn sortiert \item nur Eckpunkte enthalten(für alle Punkte = im CCW Test entfernen) \item erster und letzter Punkt sind identisch \end{itemize} diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp index c86b331..98fe4dc 100644 --- a/geometry/linesAndSegments.cpp +++ b/geometry/linesAndSegments.cpp @@ -31,12 +31,12 @@ vector lineSegmentIntersection(pt p0, pt p1, pt p2, pt p3) { return result; } -// Entfernung von Punkt p zur Gearden durch a-b. 2d und 3d +// Entfernung von Punkt p zur Geraden durch a-b. 2d und 3d double distToLine(pt a, pt b, pt p) { return abs(cross(p - a, b - a)) / abs(b - a); } -// Projektiert p auf die Gerade a-b +// Projiziert p auf die Gerade a-b pt projectToLine(pt a, pt b, pt p) { return a + (b - a) * dot(p - a, b - a) / norm(b - a); } diff --git a/graph/graph.tex b/graph/graph.tex index 060d157..0f516ac 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -88,7 +88,7 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \min\{a_{ik} \cdot b_{k\smash{j}}\}$ -Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$ +Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} \cdot b_{k\smash{j}}$ \begin{algorithm}{Dynamic Connectivity} \begin{methods} @@ -175,7 +175,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} \end{methods} \begin{itemize} - \item die ersten [0..n) Knoten in \code{adj} sind die linke Seite des Graphen + \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen \end{itemize} \sourcecode{graph/maxCarBiMatch.cpp} \begin{methods} diff --git a/math/math.tex b/math/math.tex index f9a5ea5..dc0eb00 100644 --- a/math/math.tex +++ b/math/math.tex @@ -172,7 +172,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}! \sourcecode{math/linearSieve.cpp} - \textbf{\textsc{Möbius} Funtkion:} + \textbf{\textsc{Möbius}-Funtkion:} \begin{itemize} \item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat \item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat @@ -313,16 +313,16 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/piLehmer.cpp} } -\begin{algorithm}{Lineare-Recurenz} +\begin{algorithm}{Lineare Rekurrenz} \begin{methods} - \method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2} + \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2} \method{}{aus den ersten $2n$ Werte}{} \end{methods} \sourcecode{math/berlekampMassey.cpp} - Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz. + Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Rekurrenz. \begin{methods} - \method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2} + \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2} \end{methods} \sourcecode{math/linearRecurence.cpp} Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: @@ -332,7 +332,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\ 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\ 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\ - 0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\ + \smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\ 0 & \smash{\cdots} & 0 & 1 & 0 \\ \end{pmatrix}^k \times~~ diff --git a/other/other.tex b/other/other.tex index 808d288..a21eb37 100644 --- a/other/other.tex +++ b/other/other.tex @@ -9,7 +9,7 @@ \end{algorithm} \begin{algorithm}{Timed} - Kann benutzt werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen. + Kann benutzt werden um randomisierte Algorithmen so lange wie möglich laufen zu lassen. \sourcecode{other/timed.cpp} \end{algorithm} @@ -23,7 +23,7 @@ Bit an Position j flippen & \code{x ^= (1 << j)} \\ Anzahl an führenden nullen ($x \neq 0$) & \code{__builtin_clzll(x)} \\ Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\ - Anzahl an bits & \code{__builtin_popcountll(x)} \\ + Anzahl an \code{1} bits & \code{__builtin_popcountll(x)} \\ $i$-te Zahl eines Graycodes & \code{i ^ (i >> 1)} \\ \hline \end{tabularx}\\ @@ -259,7 +259,7 @@ \subsection{Tipps \& Tricks} \begin{itemize} - \item Run Time Error: + \item \textbf{Run Time Error:} \begin{itemize} \item Stack Overflow? Evtl. rekursive Tiefensuche auf langem Pfad? \item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen? @@ -267,13 +267,19 @@ \item Evtl. Memory Limit Exceeded? Mit \code{/usr/bin/time -v} erhält man den maximalen Speicherverbrauch bei der Ausführung (Maximum resident set size). \end{itemize} - \item Strings: + \item \textbf{Strings:} \begin{itemize} \item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht? \item bit \code{0x20} beeinflusst Groß-/Kleinschreibung. \end{itemize} + + \item \textbf{Zeilenbasierte Eingabe}: + \begin{itemize} + \item \code{getline(cin, str)} liest Zeile ein. + \item Wenn vorher \code{cin >> ...} benutzt, lese letztes \code{\\n} mit \code{getline(cin, x)}. + \end{itemize} - \item Gleitkommazahlen: + \item \textbf{Gleitkommazahlen:} \begin{itemize} \item \code{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\code{acos(1.00000000000001)}}? \item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden! @@ -281,7 +287,7 @@ \item Kann \code{-0.000} ausgegeben werden? \end{itemize} - \item Wrong Answer: + \item \textbf{Wrong Answer:} \begin{itemize} \item Lies Aufgabe erneut. Sorgfältig! \item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander. diff --git a/string/string.tex b/string/string.tex index 393c2ad..dbea36c 100644 --- a/string/string.tex +++ b/string/string.tex @@ -35,7 +35,7 @@ \begin{algorithm}{\textsc{Manacher}'s Algorithm, Longest Palindrome} \begin{methods} \method{init}{transformiert \code{string a}}{n} - \method{manacher}{berechnet Länge der Palindrome}{n} + \method{manacher}{berechnet Längen der Palindrome in longest}{n} \end{methods} \sourcecode{string/manacher.cpp} \end{algorithm} @@ -90,7 +90,7 @@ \begin{algorithm}{Suffix-Array} \begin{methods} \method{SuffixArray}{berechnet ein Suffix Array}{\abs{s}\*\log^2(\abs{s})} - \method{lcp}{berechnet den longest common prefix}{\log(\abs{s})} + \method{lcp}{berechnet Länge des longest common prefix}{\log(\abs{s})} \method{}{von \code{s[x]} und \code{s[y]}}{} \end{methods} \sourcecode{string/suffixArray.cpp} diff --git a/tcr.pdf b/tcr.pdf index 63ebc4a..7114518 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3