diff options
Diffstat (limited to 'content/other/other.tex')
| -rw-r--r-- | content/other/other.tex | 35 |
1 files changed, 16 insertions, 19 deletions
diff --git a/content/other/other.tex b/content/other/other.tex index 191a6da..8896962 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -18,9 +18,9 @@ \begin{expandtable}
\begin{tabularx}{\linewidth}{|lR|}
\hline
- Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\
- Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\
- Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\
+ Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\
+ Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\
+ Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\
\hline
\end{tabularx}
\end{expandtable}
@@ -30,9 +30,9 @@ \begin{expandtable}
\begin{tabularx}{\linewidth}{|Ll|}
\hline
- Bit an Position j lesen & \code{(x & (1 << j)) != 0} \\
- Bit an Position j setzten & \code{x |= (1 << j)} \\
- Bit an Position j löschen & \code{x &= ~(1 << j)} \\
+ Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\
+ Bit an Position j setzen & \code{x |= (1 << j)} \\
+ Bit an Position j löschen & \code{x \&= ~(1 << j)} \\
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)} \\
@@ -67,9 +67,7 @@ \paragraph{Quadrangle inequality} Die Bedingung $\forall a\leq b\leq c\leq d:
C[a][d] + C[b][c] \geq C[a][c] + C[b][d]$ ist hinreichend für beide Optimierungen.
- \paragraph{Sum over Subsets DP} $\text{res}[\text{mask}]=\sum_{i\subseteq\text{mask}}\text{in}[i]$.
- Für Summe über Supersets \code{res} einmal vorher und einmal nachher reversen.
- \sourcecode{other/sos.cpp}
+ \paragraph{Sum over Subsets DP} Siehe \emph{or} Transform, Seite \pageref{fft}.
\end{algorithm}
\begin{algorithm}{Fast Subset Sum}
@@ -82,12 +80,12 @@ \sourcecode{other/pbs.cpp}
\end{algorithm}
+\columnbreak
\begin{algorithm}{Josephus-Problem}
$n$ Personen im Kreis, jeder $k$-te wird erschossen.
\begin{description}
\item[Spezialfall $\boldsymbol{k=2}$:] Betrachte $n$ Binär.
- Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n1$ die Position des letzten Überlebenden.
- (Rotiere $n$ um eine Stelle nach links)
+ Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n0$ die Position des letzten Überlebenden.
\end{description}
\sourcecode{other/josephus2.cpp}
@@ -98,7 +96,6 @@ Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$.
\end{description}
\sourcecode{other/josephusK.cpp}
- \textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
\end{algorithm}
\begin{algorithm}[optional]{Zeileneingabe}
@@ -127,7 +124,7 @@ c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x
\end{align*}
Löse Fluss auf $G'$ mit \textsc{Dinic's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
- \item \textbf{\textsc{Johnsons} Reweighting Algorithmus:}
+ \item \textbf{\textsc{Johnson}s Reweighting Algorithm:}
Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen.
Falls es einen negativen Zyklus gibt abrrechen.
Sonst ändere die Gewichte von allen Kanten \texttt{(u,v)} im ursprünglichen Graphen zu \texttt{d[u]+w[u,v]-d[v]}.
@@ -186,8 +183,8 @@ [X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} m^{\#(g)}
\]
- \item \textbf{Verteilung von Primzahlen:}
- Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n \leq p \leq 2n$.
+ \item \textbf{\textsc{Bertrand}sches Postulat:}
+ Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$.
\item \textbf{Satz von \textsc{Kirchhoff}:}
Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten.
@@ -199,7 +196,7 @@ \newline
Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.
- \item \textbf{\textsc{Dilworths}-Theorem:}
+ \item \textbf{\textsc{Dilworth}'s Theorem:}
Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).
Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$.
Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist.
@@ -211,15 +208,15 @@ Berechnung: Maximales Matching in bipartitem Graphen.
Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.
Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.
- Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden.
+ Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Antikette zu finden.
- \item \textbf{\textsc{Turan}'s-Theorem:}
+ \item \textbf{\textsc{Tur\'an}'s Theorem:}
Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist:
\begin{align*}
ext(n, K_{x+1}) &= \binom{n}{2} - \left[\left(x - (n \bmod x)\right) \cdot \binom{\floor{\frac{n}{x}}}{2} + \left(n\bmod x\right) \cdot \binom{\ceil{\frac{n}{x}}}{2}\right]
\end{align*}
- \item \textbf{\textsc{Euler}'s-Polyedersatz:}
+ \item \textbf{\textsc{Euler}scher Polyedersatz:}
In planaren Graphen gilt $n-m+f-c=1$.
\item \textbf{\textsc{Pythagoreische Tripel}:}
|