diff options
Diffstat (limited to 'other')
| -rw-r--r-- | other/bitOps.cpp | 6 | ||||
| -rw-r--r-- | other/other.tex | 74 | ||||
| -rw-r--r-- | other/parser.cpp | 61 |
3 files changed, 124 insertions, 17 deletions
diff --git a/other/bitOps.cpp b/other/bitOps.cpp index 8bad842..ecb94fa 100644 --- a/other/bitOps.cpp +++ b/other/bitOps.cpp @@ -14,3 +14,9 @@ a = -1 a = (1 << n) - 1 // Iteriert über alle Teilmengen einer Bitmaske (außer der leeren Menge). for (int subset = bitmask; subset > 0; subset = (subset - 1) & bitmask) +// Anzahl der gesetzten Bits. +int __builtin_popcount(unsigned int x); +int __builtin_popcountll(unsigned long long x); +// Anzahl der führenden 0-Bits. +int __builtin_clz(unsigned int x); +int __builtin_clzll(unsigned long long x); diff --git a/other/other.tex b/other/other.tex index b275c6e..d9ac362 100644 --- a/other/other.tex +++ b/other/other.tex @@ -6,31 +6,26 @@ \subsection{Bit Operations} \lstinputlisting{other/bitOps.cpp} -\subsection{Fast IO} -\lstinputlisting{other/fastIO.cpp} +% \subsection{Fast IO} +% \lstinputlisting{other/fastIO.cpp} + +\subsection{Rekursiver Abstieg und Abstrakter Syntaxbaum} +\lstinputlisting{other/parser.cpp} \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. +cin.tie(NULL); +// Set mit eigener Sortierfunktion. 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/Float. Muss zum Einlesen/Ausgeben in einen int oder long long gecastet werden. +// 128-Bit Integer/Float. Zum Einlesen/Ausgeben in long long casten. __int128, __float128 \end{lstlisting} @@ -101,6 +96,15 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. [X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} \vert X^g \vert \] + \item \textbf{\textsc{Polya} Counting:} + Sei $\pi$ eine Permutation der Menge $X$. + Die Elemente von $X$ können mit einer von $m$ Farben gefärbt werden. + Die Anzahl der Färbungen, die Fixpunkte von $\pi$ sind, ist $m^{\#(\pi)}$, wobei $\#(\pi)$ die Anzahl der Zyklen von $\pi$ ist. + Die Anzahl der Färbungen von Objekten einer Menge $X$ mit $m$ Farben unter einer Symmetriegruppe $G$ is gegeben durch: + \[ + [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$. @@ -126,7 +130,44 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. 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 Anitkette zu finden. + + \item \textbf{\textsc{Mo}'s Algorithm:} + SQRT-Decomposition auf $n$ Intervall Queries $[l,r]$. + Gruppiere Queries in $\sqrt{n}$ Blöcke nach linker Grenze $l$. + Sortiere nach Block und bei gleichem Block nach rechter Grenze $r$. + Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls. + Laufzeit:~$\mathcal{O}(n\cdot\sqrt{n})$. + (Anzahl der Blöcke als Konstante in Code schreiben.) + + \item \textbf{Centroids of a Tree:} + Ein \emph{Centroid} ist ein Konten, der einen Baum in Komponenten der maximalen Größe $\frac{\vert V \vert}{2}$ splitted. + Es kann $2$ Centroids geben! + \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:~$\mathcal{O}(\vert V \vert \log(\vert V \vert))$. + + \item \textbf{Kreuzprodukt} + \[ + a \times b = + \begin{pmatrix} + a_1 \\ + a_2 \\ + a_3 + \end{pmatrix} + \times + \begin{pmatrix} + b_1 \\ + b_2 \\ + b_3 + \end{pmatrix} + = + \begin{pmatrix} + a_2b_3 - a_3b_2 \\ + a_3b_1 - a_1b_3 \\ + a_1b_2 - a_2b_1 + \end{pmatrix} + \] \end{itemize} \subsection{Tipps \& Tricks} @@ -134,10 +175,10 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. \begin{itemize} \item Run Tim Error: \begin{itemize} - \item Stack Overflow? Evtl. rekurisve Tiefensuche auf langem Pfad? \item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen? \item Abbruchbedingung bei Rekursion? \item Evtl. Memory Limit Exceeded? + \item $n$ und $m$ verwechselt? \end{itemize} \item Gleitkommazahlen: @@ -155,10 +196,9 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. \item Integer Overflow? Teste maximale Eingabegrößen und mache Überschlagsrechnung. \item Einabegrößen überprüfen. Sonderfälle ausprobieren. \begin{itemize} - \item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31}$ + \item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31} = 2147483648$ \item $n$ gerade/ungerade \item Graph ist leer/enthält nur einen Knoten. - \item Liste ist leer/enthält nur ein Element. \item Graph ist Multigraph (enthält Schleifen/Mehrfachkanten). \item Sind Kanten gerichtet/ungerichtet? \item Polygon ist konkav/selbstschneidend. diff --git a/other/parser.cpp b/other/parser.cpp new file mode 100644 index 0000000..94b7829 --- /dev/null +++ b/other/parser.cpp @@ -0,0 +1,61 @@ +struct Token { // In globalem Vektor, Zugriff über globale Variable. + int type; // Definiere Konstanten. + double value; + Token(int type) : type(type) {} + Token(int type, int value) : type(type), value(value) {} +}; + +struct Expression { // Die folgenden Klassen nur für den AST. + virtual ~Expression() {}; + virtual double getValue() = 0; +}; + +struct Atom : public Expression { + double value; + Atom(int value) : value(value) {}; + double getValue() { return value; } +}; + +struct BinaryExpression : public Expression { + Expression *lhs, *rhs; + BinaryExpression(Expression *lhs, Expression *rhs) : lhs(lhs), rhs(rhs) {} + ~BinaryExpression() { delete lhs; delete rhs; } +}; + +struct Addition : public BinaryExpression { + Addition(Expression *lhs, Expression *rhs) : BinaryExpression(lhs, rhs) {} + double getValue() { return lhs->getValue() + rhs->getValue(); } +}; + +Expression* parseF() { + Expression *lhs; + switch(tokens[token].type) { + case NUMBER: return new Atom(tokens[token++].value); + case LEFT_PAR: + token++; + lhs = parseA(); + token++; + return lhs; + default: + return NULL; +}} + +Expression* parseA_(Expression *lhs) { + Expression *plus, *minus; + if (token >= (int)tokens.size()) return lhs; + switch(tokens[token].type) { + case ADDITION: + token++; + plus = new Addition(lhs, parseS()); + return parseA_(plus); + case SUBTRACTION: + token++; + minus = new Subtraction(lhs, parseS()); + return parseA_(minus); + default: + return lhs; +}} + +Expression* parseA() { + Expression *lhs = parseS(); return parseA_(lhs); +} |