Renamin sonstiges ot other.

5 files changed, 124 insertions, 0 deletions

diff --git a/other/bitOps.cpp b/other/bitOps.cpp
new file mode 100644
index 0000000..b75304f
--- /dev/null
+++ b/other/bitOps.cpp
@@ -0,0 +1,14 @@
+// Bit an Position j auslesen.
+(a & (1 << j)) != 0
+// Bit an Position j setzen.
+a |= (1 << j)
+// Bit an Position j löschen.
+a &= ~(1 << j)
+// Bit an Position j umkehren.
+a ^= (1 << j)
+// Wert des niedrigsten gesetzten Bits.
+(a & -a)
+// Setzt alle Bits auf 1.
+a = -1
+// Setzt die ersten n Bits auf 1. Achtung: Overflows.
+a = (1 << n) - 1
diff --git a/other/josephus2.cpp b/other/josephus2.cpp
new file mode 100644
index 0000000..c0bcc2f
--- /dev/null
+++ b/other/josephus2.cpp
@@ -0,0 +1,8 @@
+int rotateLeft(int n) { // Gibt Index des letzten Überlebenden zurück, 1-basiert.
+	for (int i = 31; i >= 0; i--)
+		if (n & (1 << i)) {
+			n &= ~(1 << i);
+			break;
+		}
+	n <<= 1; n++; return n;
+}
\ No newline at end of file
diff --git a/other/josephusK.cpp b/other/josephusK.cpp
new file mode 100644
index 0000000..8758fee
--- /dev/null
+++ b/other/josephusK.cpp
@@ -0,0 +1,4 @@
+int josephus(int n, int k) { // Gibt Index des letzten Überlebenden zurück, 0-basiert.
+	if (n == 1) return 0;
+	return (josephus(n - 1, k) + k) % n;
+}
\ No newline at end of file
diff --git a/other/other.tex b/other/other.tex
new file mode 100644
index 0000000..6bc4733
--- /dev/null
+++ b/other/other.tex
@@ -0,0 +1,89 @@
+\section{Sonstiges}
+
+\subsection{2-SAT}
+\begin{enumerate}
+	\item Bedingungen in 2-CNF formulieren.
+	\item Implikationsgraph bauen, $\left(a \vee b\right)$ wird zu $\neg a \Rightarrow b$ und $\neg b \Rightarrow a$.
+	\item Finde die starken Zusammenhangskomponenten.
+	\item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt.
+\end{enumerate}
+
+\subsection{Zeileneingabe}
+\lstinputlisting{other/split.cpp}
+
+\subsection{Bit Operations}
+\lstinputlisting{other/bitOps.cpp}
+
+\subsection{Josephus-Problem}
+$n$ Personen im Kreis, jeder $k$-te wird erschossen.
+\begin{description}
+	\item[Spezialfall $k=2$:] Betrachte Binärdarstellung von $n$.
+	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)
+	\lstinputlisting{other/josephus2.cpp}
+	\item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden.
+	Nummeriere die Personen mit $0, 1, \ldots, n-1$.
+	Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$.
+	Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$. 
+	\lstinputlisting{other/josephusK.cpp}
+\end{description}
+\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $1, \ldots, n$ nummeriert sind, im zweiten Fall von $0, \ldots, n-1$!}
+
+\subsection{Gemischtes}
+\begin{itemize}[itemsep=5mm]
+	\item \emph{\textsc{Johnsons} Reweighting Algorithmus:}
+	Füge neue Quelle \lstinline{S} hinzu, mit Kanten mit Gewicht 0 zu allen Knoten.
+	Nutze \textsc{Bellmann-Ford} zum Betsimmen der Entfernungen \lstinline{d[i]} von \lstinline{S} zu allen anderen Knoten.
+	Stoppe, wenn es negative Zyklen gibt.
+	Sonst ändere die gewichte von allen Kanten \lstinline{(u,v)} im ursprünglichen Graphen zu \lstinline{d[u]+w[u,v]-d[v]}.
+	Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden.
+	\item Für ein System von Differenzbeschränkungen:
+	Ändere alle Bedingungen in die Form $a-b \leq c$.
+	Für jede Bedingung füge eine Kante \lstinline{(b,a)} mit Gweicht \lstinline{c} ein.
+	Füge Quelle \lstinline{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0.
+	Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \lstinline{s} aus zu finden.
+	\lstinline{d[v]} ist mögliche Lösung für \lstinline{v}.
+	\item Min-Weight-Vertex-Cover im bipartiten Graph:
+	Partitioniere in \lstinline{A, B} und füge Kanten \lstinline{s -> A} mit Gewicht \lstinline{w(A)} und Kanten  \lstinline{B -> t} mit Gewicht \lstinline{w(B)} hinzu.
+	Füge Kanten mit Kapazität $\infty$ von \lstinline{A} nach \lstinline{B} hinzu, wo im originalen Graphen Kanten waren.
+	Max-Flow ist die Lösung.\newline
+	Im Residualgraphen:
+	\begin{itemize}
+		\item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder}
+		\item Die Knoten in \lstinline{A}, die \emph{nicht} von \lstinline{s} erreichber sind und die Knoten in \lstinline{B}, die von \lstinline{erreichber} sind.
+	\end{itemize}
+	\item Allgemeiner Graph:
+	Das Komplement eines Vertex-Cover ist ein Independent Set.
+	$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.
+	\item Bipartiter Graph:
+	Min Vertex Cover (kleinste Menge Kanten, die alle Knoten berühren) = Max Matching.
+	\item Bipartites Matching mit Gewichten auf linken Knoten.
+	Minimiere Matchinggewicht.
+	Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normlen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn})
+	\item \textbf{Tobi, cool down!}
+\end{itemize}
+
+\subsection{Sonstiges}
+\begin{lstlisting}
+// Alles-Header.
+#include <bits/stdc++.h>
+
+// Setzt das deutsche Tastaturlayout.
+setxkbmap de
+
+// Schnelle Ein-/Ausgabe mit cin/cout.
+ios::sync_with_stdio(false);
+
+// Set mit eigener Sortierfunktion. Typ muss nicht explizit angegeben werden.
+set<point2, decltype(comp)> set1(comp);
+
+// PI
+#define PI (2*acos(0))
+
+// STL-Debugging, Compiler flags.
+-D_GLIBCXX_DEBUG
+#define _GLIBCXX_DEBUG
+
+// 128-Bit Integer. Muss zum Einlesen/Ausgeben in einen int oder long long gecastet werden.
+__int128
+\end{lstlisting}
diff --git a/other/split.cpp b/other/split.cpp
new file mode 100644
index 0000000..ea7d5ff
--- /dev/null
+++ b/other/split.cpp
@@ -0,0 +1,9 @@
+vector<string> split(string &s, string delim) { // Zerlegt s anhand aller Zeichen in delim.
+	vector<string> result; char *token;
+	token = strtok((char*)s.c_str(), (char*)delim.c_str());
+	while (token != NULL) {
+		result.push_back(string(token));
+		token = strtok(NULL, (char*)delim.c_str());
+	}
+	return result;
+}
\ No newline at end of file