From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- other/bitOps.cpp | 40 ++++--- other/compiletime.cpp | 7 ++ other/divideAndConquer.cpp | 27 +++++ other/fastIO.cpp | 34 +++--- other/josephus2.cpp | 4 +- other/josephusK.cpp | 3 +- other/knuth.cpp | 15 +++ other/other.tex | 260 ++++++++++++++++++++++++++++----------------- other/parser.cpp | 61 ----------- other/pbs.cpp | 32 ++++++ other/pragmas.cpp | 6 ++ other/stuff.cpp | 30 ++++++ other/timed.cpp | 3 + 13 files changed, 324 insertions(+), 198 deletions(-) create mode 100644 other/compiletime.cpp create mode 100644 other/divideAndConquer.cpp create mode 100644 other/knuth.cpp delete mode 100644 other/parser.cpp create mode 100644 other/pbs.cpp create mode 100644 other/pragmas.cpp create mode 100644 other/stuff.cpp create mode 100644 other/timed.cpp (limited to 'other') diff --git a/other/bitOps.cpp b/other/bitOps.cpp index ecb94fa..9666187 100644 --- a/other/bitOps.cpp +++ b/other/bitOps.cpp @@ -1,22 +1,18 @@ -// 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 -// 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); +// Iteriert über alle Teilmengen einer Bitmaske +// (außer der leeren Menge). +for (int subset = bitmask; subset > 0; + subset = (subset - 1) & bitmask) + +// Zählt Anzahl der gesetzten Bits. +int numberOfSetBits(int i) { + i = i - ((i >> 1) & 0x55555555); + i = (i & 0x33333333) + ((i >> 2) & 0x33333333); + return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; +} + +// Nächste Permutation in Bitmaske +// (z.B. 00111 => 01011 => 01101 => ...) +ll nextPerm(ll v) { + ll t = v | (v - 1); + return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctzll(v) + 1)); +} diff --git a/other/compiletime.cpp b/other/compiletime.cpp new file mode 100644 index 0000000..7734806 --- /dev/null +++ b/other/compiletime.cpp @@ -0,0 +1,7 @@ +template +struct Table { + int data[N]; + constexpr Table() : data {} { + for (int i = 0; i < N; i++) data[i] = i; +}}; +constexpr Table<100000> precalculated; \ No newline at end of file diff --git a/other/divideAndConquer.cpp b/other/divideAndConquer.cpp new file mode 100644 index 0000000..92ec0ef --- /dev/null +++ b/other/divideAndConquer.cpp @@ -0,0 +1,27 @@ +vector> dp; +vector> C; + +void rec(int i, int j0, int j1, int k0, int k1) { + if (j1 < j0) return; + int jmid = (j0 + j1) / 2; + + dp[i][jmid] = inf; + int bestk = k0; + for (int k = k0; k < min(jmid, k1 + 1); ++k) { + if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) { + dp[i][jmid] = dp[i - 1][k] + C[k + 1][jmid]; + bestk = k; + }} + + rec(i, j0, jmid - 1, k0, bestk); + rec(i, jmid + 1, j1, bestk, k1); +} + +ll calc(int n, int k) { + dp = vector>(k, vector(n, inf)); + for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; + for (int i = 1; i < k; i++) { + rec(i, 0, n - 1, 0, n - 1); + } + return dp[k - 1][n - 1]; +} diff --git a/other/fastIO.cpp b/other/fastIO.cpp index 0077ce2..63f9ede 100644 --- a/other/fastIO.cpp +++ b/other/fastIO.cpp @@ -1,24 +1,24 @@ -void fastscan(int* number) { - bool negative = false; - register int c; - *number = 0; - c = getchar(); - while(c != '-' && (c < '0' || c > '9')) c = getchar(); - if (c == '-') negative = true, c = getchar(); - for (; c > 47 && c < 58; c = getchar()) *number = *number * 10 + c - 48; - if (negative) *number *= -1; +void fastscan(int& number) { + bool negative = false; + register int c; + number = 0; + c = getchar(); + while(c != '-' && (c < '0' || c > '9')) c = getchar(); + if (c == '-') negative = true, c = getchar(); + for (; c >= '0' && c <= '9'; c = getchar()) number = number * 10 + c - '0'; + if (negative) number *= -1; } void printPositive(int n) { - if (n == 0) return; - print(n / 10); - putchar(n % 10 + '0'); + if (n == 0) return; + printPositive(n / 10); + putchar(n % 10 + '0'); } void fastprint(int n) { - if(n == 0) { putchar('0'); return; } - if (n < 0) { - putchar('-'); - print(-n); - } else print(n); + if(n == 0) {putchar('0'); return;} + if (n < 0) { + putchar('-'); + printPositive(-n); + } else printPositive(n); } diff --git a/other/josephus2.cpp b/other/josephus2.cpp index a973609..5086e13 100644 --- a/other/josephus2.cpp +++ b/other/josephus2.cpp @@ -1,8 +1,8 @@ int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert. - for (int i = 31; i >= 0; i--) + for (int i = 31; i >= 0; i--) { if (n & (1 << i)) { n &= ~(1 << i); break; - } + }} n <<= 1; n++; return n; } diff --git a/other/josephusK.cpp b/other/josephusK.cpp index 522b584..8d4df4d 100644 --- a/other/josephusK.cpp +++ b/other/josephusK.cpp @@ -1,4 +1,5 @@ -int josephus(int n, int k) { // Der letzte Überlebende, 0-basiert. +// Der letzte Überlebende, 0-basiert. +int josephus(int n, int k) { if (n == 1) return 0; return (josephus(n - 1, k) + k) % n; } \ No newline at end of file diff --git a/other/knuth.cpp b/other/knuth.cpp new file mode 100644 index 0000000..f47dbe0 --- /dev/null +++ b/other/knuth.cpp @@ -0,0 +1,15 @@ +ll calc(int n, int k, const vector> &C) { + vector> dp(k, vector(n, inf)); + vector> opt(k, vector(n + 1, n - 1)); + + for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; + for (int i = 1; i < k; i++) { + for (int j = n - 1; j >= 0; --j) { + opt[i][j] = i == 1 ? 0 : opt[i - 1][j]; + for (int k = opt[i][j]; k <= min(opt[i][j + 1], j - 1); ++k) { + if (dp[i][j] <= dp[i - 1][k] + C[k + 1][j]) continue; + dp[i][j] = dp[i - 1][k] + C[k + 1][j]; + opt[i][j] = k; + }}} + return dp[k - 1][n - 1]; +} diff --git a/other/other.tex b/other/other.tex index d9ac362..3a70a36 100644 --- a/other/other.tex +++ b/other/other.tex @@ -1,73 +1,137 @@ \section{Sonstiges} -\subsection{Zeileneingabe} -\lstinputlisting{other/split.cpp} - -\subsection{Bit Operations} -\lstinputlisting{other/bitOps.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 -// Schnelle Ein-/Ausgabe mit cin/cout. -ios::sync_with_stdio(false); -cin.tie(NULL); -// Set mit eigener Sortierfunktion. -set set1(comp); -// PI -#define PI (2*acos(0)) -// STL-Debugging, Compiler flags. --D_GLIBCXX_DEBUG -// 128-Bit Integer/Float. Zum Einlesen/Ausgeben in long long casten. -__int128, __float128 -\end{lstlisting} - -\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$. +\begin{algorithm}[optional]{Zeileneingabe} + \sourcecode{other/split.cpp} +\end{algorithm} + +\begin{algorithm}[optional]{Fast IO} + \sourcecode{other/fastIO.cpp} +\end{algorithm} + +\begin{algorithm}{Pragmas} + \sourcecode{other/pragmas.cpp} +\end{algorithm} + +\begin{algorithm}{Compiletime} + \begin{itemize} + \item überprüfen ob Compilezeit Berechnungen erlaubt sind! + \item braucht \code{c++14} oder höher! + \end{itemize} + \sourcecode{other/compiletime.cpp} +\end{algorithm} + +\begin{algorithm}{Timed} + Kann benutzt werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen. + \sourcecode{other/timed.cpp} +\end{algorithm} + +\begin{algorithm}{Bit Operations} + \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 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)} \\ + \hline + \end{tabularx}\\ + \end{expandtable} + \sourcecode{other/bitOps.cpp} +\end{algorithm} + +\begin{algorithm}{Overflow-sichere arithmetische Operationen} + Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis. + \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)} \\ + \hline + \end{tabularx} + \end{expandtable} +\end{algorithm} + +\begin{algorithm}{Sonstiges} + \sourcecode{other/stuff.cpp} +\end{algorithm} + +\begin{algorithm}{DP Optimizations} + Aufgabe: Partitioniere Array in genau $k$ zusammenhängende Teile mit minimalen Kosten: + $dp[i][j] = \min_{k 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. + Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gweicht \texttt{c} ein. + Füge Quelle \texttt{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0. + Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \texttt{s} aus zu finden. + \texttt{d[v]} ist mögliche Lösung für \texttt{v}. + + \item \textbf{Min-Weight-Vertex-Cover im Bipartiten Graph:} + Partitioniere in \texttt{A, B} und füge Kanten \texttt{s}\,$\rightarrow$\,\texttt{A} mit Gewicht \texttt{w(A)} und Kanten \texttt{B}\,$\rightarrow$\,\texttt{t} mit Gewicht \texttt{w(B)} hinzu. + Füge Kanten mit Kapazität $\infty$ von \texttt{A} nach \texttt{B} hinzu, wo im originalen Graphen Kanten waren. Max-Flow ist die Lösung.\newline Im Residualgraphen: - \begin{itemize}[nosep] + \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. + \item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{erreichbar} sind. \end{itemize} \item \textbf{Allgemeiner Graph:} @@ -75,11 +139,12 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. $\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover. \item \textbf{Bipartiter Graph:} - Min Vertex Cover (kleinste Menge Kanten, die alle Knoten berühren) = Max Matching. + Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching. + Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, makiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die makierten Knoten aus $B$ und die unmakierten Knoten aus $A$. \item \textbf{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}) + Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normalen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn}) \item \textbf{Satz von \textsc{Pick}:} Sei $A$ der Flächeninhalt eines einfachen Gitterpolygons, $I$ die Anzahl der Gitterpunkte im Inneren und $R$ die Anzahl der Gitterpunkte auf dem Rand. @@ -118,7 +183,7 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. \newline Entferne letzte Zeile und Spalte und berechne Betrag der Determinante. - \item \textbf{\textsc{Dilworth}'s-Theorem:} + \item \textbf{\textsc{Dilworths}-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. @@ -130,62 +195,65 @@ $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{Turan}'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:} + In planaren Graphen gilt $n-m+f-c=1$. + + \item \textbf{\textsc{Pythagoreische Tripel}:} + Sei $m>n>0,~k>0$ und $m\not\equiv n \bmod 2$ dann beschreibt diese Formel alle Pythagoreischen Tripel eindeutig: + \[k~\cdot~\Big(~a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2~\Big)\] + \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})$. + Laufzeit:~\runtime{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. + Ein \emph{Centroid} ist ein Knoten, der einen Baum in Komponenten der maximalen Größe $\frac{\abs{V}}{2}$ splitted. Es kann $2$ Centroids geben! - \textbf{Centroid Decomposition:} + + \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:~$\mathcal{O}(\vert V \vert \log(\vert V \vert))$. + 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{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} - \] + \item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:} + Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von + $\runtime{n^2}$ zu $\runtime{n\log n}$ zu verbessern. \end{itemize} \subsection{Tipps \& Tricks} \begin{itemize} - \item Run Tim Error: + \item 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? \item Abbruchbedingung bei Rekursion? \item Evtl. Memory Limit Exceeded? - \item $n$ und $m$ verwechselt? \end{itemize} - + + \item Strings: + \begin{itemize} + \item Soll \lstinline{"aa"} kleiner als \lstinline{"z"} sein oder nicht? + \item bit \code{0x20} beeinflusst Groß-/Kleinschreibung. + \end{itemize} + \item Gleitkommazahlen: \begin{itemize} - \item \lstinline{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \lstinline{acos(1.00000000000001)}? - \item Flasches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden! - \item Output in wissenschaftlicher Notation (\lstinline{1e-25})? + \item \lstinline{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\lstinline{acos(1.00000000000001)}}? + \item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden! + \item genügend Präzision oder Output in wissenschaftlicher Notation (\lstinline{1e-25})? \item Kann \lstinline{-0.000} ausgegeben werden? \end{itemize} @@ -194,11 +262,13 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. \item Lies Aufgabe erneut. Sorgfältig! \item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander. \item Integer Overflow? Teste maximale Eingabegrößen und mache Überschlagsrechnung. - \item Einabegrößen überprüfen. Sonderfälle ausprobieren. + \item Integer Division rundet zur $0$ $\neq$ abrunden. + \item Eingabegrößen überprüfen. Sonderfälle ausprobieren. \begin{itemize} - \item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31} = 2147483648$ + \item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31}$ \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 deleted file mode 100644 index 94b7829..0000000 --- a/other/parser.cpp +++ /dev/null @@ -1,61 +0,0 @@ -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); -} diff --git a/other/pbs.cpp b/other/pbs.cpp new file mode 100644 index 0000000..45577e2 --- /dev/null +++ b/other/pbs.cpp @@ -0,0 +1,32 @@ +// Q = Anzahl der Anfragen +// C = Anzahl der Schritte der Operation + +vector> focus; +vector low, high, ans; + +ans.assign(Q, C + 1); +low.assign(Q, 0); +high.assign(Q, C); +focus.assign(C + 1, vector()); +for (bool changed = true; changed;) { + changed = false; + for (int i = 0; i <= C; i++) focus[i].clear(); + for (int i = 0; i < Q; i++) { + if (low[i] > high[i]) continue; + focus[(low[i] + high[i]) / 2].pb(i); + } + + // Simulation zurücksetzen + + for (int k = 0; k <= C; k++) { + // Simulationsschritt + + for (int q : focus[k]) { + changed = true; + if (/* Eigenschaft schon erfüllt */) { + // Antwort updaten + high[q] = k - 1; + ans[q] = min(ans[q], k); + } else { + low[q] = k + 1; +}}}} diff --git a/other/pragmas.cpp b/other/pragmas.cpp new file mode 100644 index 0000000..f8cf060 --- /dev/null +++ b/other/pragmas.cpp @@ -0,0 +1,6 @@ +#pragma GCC optimize("Ofast") +#pragma GCC optimize ("unroll-loops") +#pragma GCC target("sse,sse2,sse3,ssse3,sse4," + "popcnt,abm,mmx,avx,tune=native") +#pragma GCC target("fpmath=sse,sse2") // no excess precision +#pragma GCC target("fpmath=387") // force excess precision \ No newline at end of file diff --git a/other/stuff.cpp b/other/stuff.cpp new file mode 100644 index 0000000..81286d8 --- /dev/null +++ b/other/stuff.cpp @@ -0,0 +1,30 @@ +// Alles-Header. +#include + +// Setzt das deutsche Tastaturlayout. +setxkbmap de + +// Schnelle Ein-/Ausgabe mit cin/cout. +ios::sync_with_stdio(false); +cin.tie(nullptr); + +// Set mit eigener Sortierfunktion. +// Typ muss nicht explizit angegeben werden. +set set1(comp); + +// 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. +__int128, __float128 + +// float mit Decimaldarstellung +#include +std::decimal::decimal128 + +// 1e18 < INF < Max_Value / 2 +constexpr long long INF = 0x3FFF_FFFF_FFFF_FFFFll; +// 1e9 < INF < Max_Value / 2 +constexpr int INF = 0x3FFF_FFFF; diff --git a/other/timed.cpp b/other/timed.cpp new file mode 100644 index 0000000..20eec70 --- /dev/null +++ b/other/timed.cpp @@ -0,0 +1,3 @@ +int times = clock(); +//run for 900ms +while (clock()-times < 900) {...} -- cgit v1.2.3