diff options
30 files changed, 648 insertions, 335 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index a2c5ff6..b3683bf 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -5,15 +5,16 @@ \subsection{Segmentbaum} \lstinputlisting{datastructures/segmentTree.cpp} -Mit \lstinline{update()} können ganze Intervalle geändert werden. -Dazu: Offset in den inneren Knoten des Baums speichern. + +\subsection{2D-Segmentbaum} +\lstinputlisting{datastructures/segmentTree2D.cpp} \subsection{Fenwick Tree} \lstinputlisting{datastructures/fenwickTree.cpp} +\lstinputlisting{datastructures/fenwickTreeNiklas.cpp} - -\subsection{Range Minimum Query} -\lstinputlisting{datastructures/RMQ.cpp} +\subsection{Sparse Table} +\lstinputlisting{datastructures/sparseTable.cpp} \subsection{STL-Tree} \lstinputlisting{datastructures/stlTree.cpp} @@ -24,5 +25,5 @@ Dazu: Offset in den inneren Knoten des Baums speichern. \subsection{Treap (Cartesian Tree)} \lstinputlisting{datastructures/treap.cpp} -\subsection{Erste unbenutzte natürliche Zahl} -\lstinputlisting{datastructures/firstUnused.cpp} +\subsection{Skew Heap} +\lstinputlisting{datastructures/skewHeap.cpp} diff --git a/datastructures/fenwickTreeNiklas.cpp b/datastructures/fenwickTreeNiklas.cpp new file mode 100644 index 0000000..032f74c --- /dev/null +++ b/datastructures/fenwickTreeNiklas.cpp @@ -0,0 +1,56 @@ +const int n = 10000; // ALL INDICES START AT 1 WITH THIS CODE!! + +// mode 1: update indices, read prefixes +void update_idx(int tree[], int i, int val) { // v[i] += val + for (; i <= n; i += i & -i) tree[i] += val; +} +int read_prefix(int tree[], int i) { // get sum v[1..i] + int sum = 0; + for (; i > 0; i -= i & -i) sum += tree[i]; + return sum; +} +int kth(int k) { // find kth element in tree (1-based index) + int ans = 0; + for (int i = maxl; i >= 0; --i) // maxl = largest i s.t. (1<<i) <= n + if (ans + (1<<i) <= n && tree[ans + (1<<i)] < k) { + ans += 1<<i; + k -= tree[ans]; + } + return ans+1; +} + +// mode 2: update prefixes, read indices +void update_prefix(int tree[], int i, int val) { // v[1..i] += val + for (; i > 0; i -= i & -i) tree[i] += val; +} +int read_idx(int tree[], int i) { // get v[i] + int sum = 0; + for (; i <= n; i += i & -i) sum += tree[i]; + return sum; +} + +// mode 3: range-update range-query +const int maxn = 100100; +int n; +ll mul[maxn], add[maxn]; + +void update_idx(ll tree[], int x, ll val) { + for (int i = x; i <= n; i += i & -i) tree[i] += val; +} +void update_prefix(int x, ll val) { // v[x] += val + update_idx(mul, 1, val); + update_idx(mul, x + 1, -val); + update_idx(add, x + 1, x * val); +} +ll read_prefix(int x) { // get sum v[1..x] + ll a = 0, b = 0; + for (int i = x; i > 0; i -= i & -i) a += mul[i], b += add[i]; + return a * x + b; +} +void update_range(int l, int r, ll val) { // v[l..r] += val + update_prefix(l - 1, -val); + update_prefix(r, val); +} +ll read_range(int l, int r) { // get sum v[l..r] + return read_prefix(r) - read_prefix(l - 1); +} diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp deleted file mode 100644 index 141eb00..0000000 --- a/datastructures/firstUnused.cpp +++ /dev/null @@ -1,12 +0,0 @@ -// Erste natürliche Zahl nicht im set used. -set<int> used; -int unusedCounter = 1; - -int getFirstUnused() { // Laufzeit: O(log n) amortisiert. - auto it = used.lower_bound(unusedCounter); - while (it != used.end() && *it == unusedCounter) { - it++; - unusedCounter++; - } - return unusedCounter++; // Evtl. neuen Wert noch hinzufügen. -} diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index c810af7..3905151 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -2,8 +2,6 @@ // Berechnet das Maximum im Array. int a[MAX_N], m[4 * MAX_N]; -int gcd(int a, int b) { return b == 0 ? a : gcd (b, a % b); } - int query(int x, int y, int k = 0, int X = 0, int Y = MAX_N - 1) { if (x <= X && Y <= y) return m[k]; if (y < X || Y < x) return -INF; // Ein "neutrales" Element. diff --git a/datastructures/segmentTree2D.cpp b/datastructures/segmentTree2D.cpp new file mode 100644 index 0000000..a9d129b --- /dev/null +++ b/datastructures/segmentTree2D.cpp @@ -0,0 +1,58 @@ +// 1-indiziert. Array t: [4*n][4*m]. Nur die _x-Varianten aufrufen. +// Laufzeit: build: O(n*m), update, sum: O(log(n)*log(m)) +void build_y(int vx, int lx, int rx, int vy, int ly, int ry) { + if (ly == ry) { + if (lx == rx)vt[vx][vy] = a[lx][ly]; + else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy]; + } else { + int my = (ly + ry) / 2; + build_y(vx, lx, rx, vy*2, ly, my); + build_y(vx, lx, rx, vy*2+1, my+1, ry); + t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]; +}} + +void build_x(int vx = 1, int lx = 0, int rx = N-1) { + if (lx != rx) { + int mx = (lx + rx) / 2; + build_x(vx*2, lx, mx); + build_x(vx*2+1, mx+1, rx); + } + build_y(vx, lx, rx, 1, 0, m-1); +} + +int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) { + if (ly > ry) return 0; + if (ly == tly && try_ == ry) return t[vx][vy]; + int tmy = (tly + try_) / 2; + return sum_y(vx, vy*2, tly, tmy, ly, min(ry,tmy)) + + sum_y(vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry); +} + +int sum_x(int vx=1, int tlx=0, int trx=n-1,int lx,int rx,int ly,int ry) { + if (lx > rx) return 0; + if (lx == tlx && trx == rx) return sum_y(vx, 1, 0, m-1, ly, ry); + int tmx = (tlx + trx) / 2; + return sum_x(vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry) + + sum_x(vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry); +} + +void update_y(int vx, int lx, int rx, int vy, int ly, int ry, + int x, int y, int new_val) { + if (ly == ry) { + if (lx == rx) t[vx][vy] = new_val; + else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy]; + } else { + int my = (ly + ry) / 2; + if (y <= my) update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val); + else update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val); + t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]; +}} + +void update_x(int vx=1, int lx=0, int rx=n-1, int x, int y, int new_val) { + if (lx != rx) { + int mx = (lx + rx) / 2; + if (x <= mx) update_x(vx*2, lx, mx, x, y, new_val); + else update_x(vx*2+1, mx+1, rx, x, y, new_val); + } + update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val); +} diff --git a/datastructures/skewHeap.cpp b/datastructures/skewHeap.cpp new file mode 100644 index 0000000..ae2cc75 --- /dev/null +++ b/datastructures/skewHeap.cpp @@ -0,0 +1,29 @@ +// Skew Heap, verschmelzbare Priority Queue. +// Laufzeit: Merging, Inserting, DeleteMin: O(log(n)) amortisiert +struct node{ + int key; + node *lc, *rc; + node(int k) : key(k), lc(0), rc(0) {} +} *root = 0; +int size = 0; + +node* merge(node *x, node *y) { + if (!x) return y; + if (!y) return x; + if (x->key > y->key) swap(x,y); + x->rc = merge(x->rc, y); + swap(x->lc, x->rc); + return x; +} + +void insert(int x) { root = merge(root, new node(x)); size++; } + +int delmin() { + if (!root) return -1; + int ret = root->key; + node *troot = merge(root->lc, root->rc); + delete root; + root = troot; + size--; + return ret; +} diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp new file mode 100644 index 0000000..52867de --- /dev/null +++ b/datastructures/sparseTable.cpp @@ -0,0 +1,27 @@ +struct SparseTable { + int st[MAX_N][MAX_LOG + 1], log[MAX_N + 1]; // Achtung: 2^MAX_LOG > MAX_N + vector<int> *a; + + // Funktion muss idempotent sein! Hier Minimum. + bool better(int lidx, int ridx) { return a->at(lidx) <= a->at(ridx); } + + void init(vector<int> *vec) { + a = vec; + for (int i = 0; i < (int)a->size(); i++) st[i][0] = i; + for (int j = 1; j <= MAX_LOG; j++) { + for (int i = 0; i + (1 << j) <= (int)a->size(); i++) { + st[i][j] = better(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]) + ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1]; + }} + + log[1] = 0; + for (int i = 2; i <= MAX_N; i++) log[i] = log[i/2] + 1; + } + + // Gibt Index des Ergebnisses in [l,r]. Laufzeit: O(1) + int queryIdempotent(int l, int r) { + int j = log[r - l + 1]; + return better(st[l][j], st[r - (1 << j) + 1][j]) + ? st[l][j] : st[r - (1 << j) + 1][j]; + } +}; diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp deleted file mode 100644 index b26ec75..0000000 --- a/datastructures/unionFind2.cpp +++ /dev/null @@ -1,27 +0,0 @@ -vector<int> uf; - -init(int N) { - uf.assign(N,-1); //-1 indicates that every subset has size 1 -} - -int findSet(int i) { - if(uf[i] < 0) return i; //If uf[i] < 0 we have reach a root - uf[i] = findSet(uf[i]); //Path-Compression - return uf[i]; -} - -void linkSets(int i, int j) { - //Take |uf[i]|, where i must be a root, to get the size - //of the subset - if(abs(uf[i]) < abs(uf[j])) { //Union-by-size. - uf[j] += uf[i]; uf[i] = j; - } else { - uf[i] += uf[j]; uf[j] = i; - } -} - -void unionSets(int i, int j) { - if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j)); -} - - diff --git a/graph/LCA.cpp b/graph/LCA.cpp deleted file mode 100644 index c79cc5c..0000000 --- a/graph/LCA.cpp +++ /dev/null @@ -1,21 +0,0 @@ -vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); -vector<vector<int>> graph(MAX_N); - -// Funktioniert nur mit von der Wurzel weggerichteten Kanten. -// Falls ungerichtete Kanten, visited-check einführen. -void initLCA(int gi, int d, int &c) { // Laufzeit: O(n) - visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++; - for(int gn : graph[gi]) { - initLCA(gn, d+1, c); - visited[c] = gi, depth[c] = d, c++; -}} - -int getLCA(int a, int b) { // Laufzeit: O(1) - return visited[queryRMQ( - min(first[a], first[b]), max(first[a], first[b]))]; -} - -// Benutzung: -int c = 0; -initLCA(0, 0, c); -initRMQ(); // Ersetze das data im RMQ-Code von oben durch depth. diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index e7139d0..fba08bb 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -23,7 +23,7 @@ void findArticulationPoints() { counter = 0; low.resize(adjlist.size()); d.assign(adjlist.size(), 0); - isArtPoint.assign(adjlist.size(), false); + isArt.assign(adjlist.size(), false); bridges.clear(); //nur fuer Bruecken for (int v = 0; v < (int)adjlist.size(); v++) { if (!d[v]) { diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index 9e4fac1..2a8b5f9 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,26 +1,24 @@ // Laufzeit: O(n^2) -vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten. -vector<vector<double>> dp; +vector<vector<double>> dp, dist; // Entfernungen zwischen Punkten. double get(int p1, int p2) { - int v = max(p1, p2) + 1; - if (v == dist.size()) return dist[p1][v - 1] + dist[p2][v - 1]; - if (dp[p1][p2] >= 0.0) return dp[p1][p2]; - double tryLR = dist[p1][v] + get(v, p2), tryRL = dist[p2][v] + get(p1, v); - return dp[p1][p2] = min(tryLR, tryRL); + int v = max(p1, p2) + 1; + if (v == dist.size()) return dist[p1][v - 1] + dist[p2][v - 1]; + if (dp[p1][p2] >= 0.0) return dp[p1][p2]; + double tryLR = dist[p1][v] + get(v, p2); + double tryRL = dist[p2][v] + get(p1, v); + return dp[p1][p2] = min(tryLR, tryRL); } void bitonicTour() { - dp = vector<vector<double>>(dist.size(), vector<double>(dist.size(), -1)); - get(0, 0); - // return dp[0][0]; // Länger der Tour - vector<int> lr = {0}, rl = {0}; - for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) { - if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { - lr.push_back(v); p1 = v; - } else { - rl.push_back(v); p2 = v; + dp.assign(dist.size(), vector<double>(dist.size(), -1)); + get(0, 0); // return dp[0][0]; // Länger der Tour + vector<int> lr = {0}, rl = {0}; + for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) { + if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { + lr.push_back(v); p1 = v; + } else { + rl.push_back(v); p2 = v; }} - lr.insert(lr.end(), rl.rbegin(), rl.rend()); - // return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position. + lr.insert(lr.end(), rl.rbegin(), rl.rend()); // Tour, Knoten 0 doppelt. } diff --git a/graph/graph.tex b/graph/graph.tex index 596c0d6..37356f6 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,34 +1,32 @@ \section{Graphen} -\subsection{Minimale Spannbäume} +% \subsection{Minimale Spannbäume} -\paragraph{Schnitteigenschaft} -Für jeden Schnitt $C$ im Graphen gilt: -Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. -($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) +% \paragraph{Schnitteigenschaft} +% Für jeden Schnitt $C$ im Graphen gilt: +% Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. +% ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) -\paragraph{Kreiseigenschaft} -Für jeden Kreis $K$ im Graphen gilt: -Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. - -\subsubsection{Kruskal} -\lstinputlisting{graph/kruskal.cpp} +% \paragraph{Kreiseigenschaft} +% Für jeden Kreis $K$ im Graphen gilt: +% Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. \subsection{Kürzeste Wege} -\subsubsection{Algorithmus von \textsc{Dijkstra}} -Kürzeste Pfade in Graphen ohne negative Kanten. +% \subsubsection{Algorithmus von \textsc{Dijkstra}} +% Kürzeste Pfade in Graphen ohne negative Kanten. \lstinputlisting{graph/dijkstra.cpp} -\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} -Kürzestes Pfade in Graphen mit negativen Kanten. -Erkennt negative Zyklen. +% \subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +% Kürzestes Pfade in Graphen mit negativen Kanten. +% Erkennt negative Zyklen. \lstinputlisting{graph/bellmannFord.cpp} -\subsubsection{\textsc{Floyd-Warshall}-Algorithmus} -\lstinputlisting{graph/floydWarshall.cpp} +% \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} +% \lstinputlisting{graph/floydWarshall.cpp} +Floyd Warshall: \begin{itemize}[nosep] - \item Nur negative Werte sollten die Nullen überschreiben. + \item Nur negative Werte sollten die Nullen bei Schlingen überschreiben. \item Von parallelen Kanten sollte nur die günstigste gespeichert werden. \item \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist. \item Wenn für \lstinline{c} gilt, dass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz. @@ -60,7 +58,7 @@ VISIT(v): \lstinputlisting{graph/euler.cpp} \subsection{Lowest Common Ancestor} -\lstinputlisting{graph/LCA.cpp} +\lstinputlisting{graph/lca.cpp} \subsection{Max-Flow} @@ -68,9 +66,9 @@ VISIT(v): Gut bei dünn besetzten Graphen. \lstinputlisting{graph/capacityScaling.cpp} -\subsubsection{Push Relabel} -Gut bei sehr dicht besetzten Graphen. -\lstinputlisting{graph/pushRelabel.cpp} +% \subsubsection{Push Relabel} +% Gut bei sehr dicht besetzten Graphen. +% \lstinputlisting{graph/pushRelabel.cpp} \subsubsection{Dinic's Algorithm mit Capacity Scaling} Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling. @@ -103,6 +101,12 @@ Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling. \lstinputlisting{graph/maxCarBiMatch.cpp} \lstinputlisting{graph/hopcroftKarp.cpp} +\subsection{Maximum Weight Bipartite Matching} +\lstinputlisting{graph/maxWeightBipartiteMatching.cpp} + +\subsection{Wert des maximalen Matchings} +\lstinputlisting{graph/matching.cpp} + \subsection{2-SAT} \lstinputlisting{graph/2sat.cpp} diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp deleted file mode 100644 index 0bd2e22..0000000 --- a/graph/kruskal.cpp +++ /dev/null @@ -1,9 +0,0 @@ -// Union-Find Implementierung von oben. Laufzeit: O(|E|*log(|E|)) -sort(edges.begin(), edges.end()); -vector<ii> mst; int cost = 0; -for (auto &e : edges) { - if (findSet(e.from) != findSet(e.to)) { - unionSets(e.from, e.to); - mst.push_back(ii(e.from, e.to)); - cost += e.cost; -}} diff --git a/graph/lca.cpp b/graph/lca.cpp new file mode 100644 index 0000000..d6548e9 --- /dev/null +++ b/graph/lca.cpp @@ -0,0 +1,28 @@ +struct LCA { + vector<int> depth, visited, first; + int idx; + SparseTable st; + + void init(vector<vector<int>> &g, int root) { // Laufzeit: O(|V|) + depth.assign(2 * g.size(), 0); + visited.assign(2 * g.size(), -1); + first.assign(g.size(), 2 * g.size()); + idx = 0; + visit(g, root, 0); + st.init(&depth); + } + + void visit(vector<vector<int>> &g, int v, int d) { + visited[idx] = v, depth[idx] = d, first[v] = min(idx, first[v]), idx++; + + for (int w : g[v]) { + if (first[w] == 2 * (int)g.size()) { + visit(g, w, d + 1); + visited[idx] = v, depth[idx] = d, idx++; + }}} + + int getLCA(int a, int b) { // Laufzeit: O(1) + if (first[a] > first[b]) swap(a, b); + return visited[st.queryIdempotent(first[a], first[b])]; + } +}; diff --git a/graph/matching.cpp b/graph/matching.cpp new file mode 100644 index 0000000..4383330 --- /dev/null +++ b/graph/matching.cpp @@ -0,0 +1,35 @@ +// Fehlerwahrscheinlichkeit: (n / MOD)^I +const int N=200, MOD=1000000007, I=10; +int n, adj[N][N], a[N][N]; + +int rank() { + int r = 0; + for (int j = 0; j < n; j++) { + int k = r; + while (k < n && !a[k][j]) ++k; + if (k == n) continue; + swap(a[r], a[k]); + int inv = powmod(a[r][j], MOD - 2); + for (int i = j; i < n; i++) + a[r][i] = 1LL * a[r][i] * inv % MOD; + for (int u = r + 1; u < n; u++) + for (int v = j; v < n; v++) + a[u][v] = (a[u][v] - 1LL * a[r][v] * a[u][j] % MOD + MOD) % MOD; + ++r; + } + return r; +} + +int max_matching() { + int ans = 0; + for (int _ = 0; _ < I; _++) { + for (int i = 0; i < n; i++) { + for (int j = 0; j < i; j++) { + if (adj[i][j]) { + a[i][j] = rand() % (MOD - 1) + 1; + a[j][i] = MOD - a[i][j]; + }}} + ans = max(ans, rank()/2); + } + return ans; +} diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index e538a19..24aebef 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -14,7 +14,7 @@ bool dfs(int v) { } int kuhn(int n) { // n = #Knoten links. - pairs.assign(NUM_VERTICES, -1); + pairs.assign(adjlist.size(), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. for (int i = 0; i < n; i++) for (auto w : adjlist[i]) diff --git a/graph/maxWeightBipartiteMatching.cpp b/graph/maxWeightBipartiteMatching.cpp new file mode 100644 index 0000000..f734fa4 --- /dev/null +++ b/graph/maxWeightBipartiteMatching.cpp @@ -0,0 +1,54 @@ +// Laufzeit: O(|V|^3) +int costs[N_LEFT][N_RIGHT]; + +// Es muss l<=r sein, ansonsten terminiert der Algorithmus nicht. +int match(int l, int r) { + vector<int> xy(l, -1), yx(r, -1), lx(l), ly(r, 0), augmenting(r); + vector<bool> s(l); + vector<ii> slack(r, ii(0,0)); + + for (int x = 0; x < l; x++) lx[x] = *max_element(costs[x], costs[x] + r); + for (int root = 0; root < l; root++) { + fill(augmenting.begin(), augmenting.end(), -1); + fill(s.begin(), s.end(), false); + s[root] = true; + for (int y = 0; y < r; y++) { + slack[y] = ii(lx[root] + ly[y] - costs[root][y], root); + } + int y = -1; + for (;;) { + int delta = INT_MAX, x = -1; + for (int yy = 0; yy < r; yy++) { + if (augmenting[yy] == -1) { + if (slack[yy].first < delta) { + delta = slack[yy].first; + x = slack[yy].second; + y = yy; + }}} + if (delta > 0) { + for (int x = 0; x < l; x++) if (s[x]) lx[x] -= delta; + for (int y = 0; y < r; y++) { + if (augmenting[y] > -1) ly[y] += delta; + else slack[y].first -= delta; + }} + augmenting[y] = x; + x = yx[y]; + if (x == -1) break; + s[x] = true; + for (int y = 0; y < r; y++) { + if (augmenting[y] == -1) { + ii alt = ii(lx[x] + ly[y] - costs[x][y], x); + if (slack[y].first > alt.first) { + slack[y] = alt; + }}}} + while (y != -1) { + // Jede Iteration vergrößert Matching um 1 (können 0-Kanten sein!). + int x = augmenting[y]; + int prec = xy[x]; + yx[y] = x; + xy[x] = y; + y = prec; + }} + return accumulate(lx.begin(), lx.end(), 0) + + accumulate(ly.begin(), ly.end(), 0); // Wert des Matchings. +} diff --git a/java/java.tex b/java/java.tex deleted file mode 100644 index f64ad32..0000000 --- a/java/java.tex +++ /dev/null @@ -1,55 +0,0 @@ -\section{Java} -\lstset{language=Java} - -\subsection{Introduction} - -\begin{itemize}[nosep] - \item Compilen: \lstinline{javac main.java} - \item Ausführen: \lstinline{java main < sample.in} - \item Eingabe: - \lstinline{Scanner} ist sehr langsam. - Bei großen Eingaben muss ein Buffered Reader verwendet werden. - \begin{lstlisting} -Scanner in = new Scanner(System.in); // java.util.Scanner -String line = in.nextLine(); // Die nächste Zeile. -int num = in.nextInt(); // Das nächste Token als int. -double num2 = in.nextDouble(); // Das nächste Token als double. - \end{lstlisting} - \item Ausgabe: - \begin{lstlisting} -// In StringBuilder schreiben und auf einmal ausgeben ist schneller. -StringBuilder sb = new StringBuilder(); // java.lang.StringBuilder -sb.append("Hallo Welt"); -System.out.print(sb.toString()); - \end{lstlisting} -\end{itemize} - -\subsection{BigInteger} -\begin{lstlisting} -// Berechnet this +,*,/,- val. -BigInteger add(BigInteger val), multiply(BigInteger val), - divide(BigInteger val), substract(BigInteger val) - -// Berechnet this^e. -BigInteger pow(BigInteger e) - -// Bit-Operationen. -BigInteger and(BigInteger val), or(BigInteger val), xor(BigInteger val), - not(), shiftLeft(int n), shiftRight(int n) - -// Berechnet den ggT von abs(this) und abs(val). -BigInteger gcd(BigInteger val) - -// Berechnet this mod m, this^-1 mod m, this^e mod m. -BigInteger mod(BigInteger m), modInverse(BigInteger m), - modPow(BigInteger e, BigInteger m) - -// Berechnet die nächste Zahl, die größer und wahrscheinlich prim ist. -BigInteger nextProbablePrime() - -// Berechnet int/long/float/double-Wert. -// Ist die Zahl zu großen werden die niedrigsten Bits konvertiert. -int intValue(), long longValue(), -float floatValue(), double doubleValue() -\end{lstlisting} -\lstset{language=C++}
\ No newline at end of file diff --git a/latexHeaders/layout.tex b/latexHeaders/layout.tex index b47f1b7..843798a 100644 --- a/latexHeaders/layout.tex +++ b/latexHeaders/layout.tex @@ -18,7 +18,12 @@ % Shift the title up to waste less space. \usepackage{titling} -\setlength{\droptitle}{-8em} +\setlength{\droptitle}{-9em} + +% Reduce spaces around sections and subsections. +\usepackage{titlesec} +\titlespacing*{\section}{0pt}{0pt}{0pt} +\titlespacing*{\subsection}{0pt}{0pt}{0pt} % Nice enumerations without wasting space above and below. \usepackage{enumitem} diff --git a/latexHeaders/listings.tex b/latexHeaders/listings.tex index 02b34bd..135b2af 100644 --- a/latexHeaders/listings.tex +++ b/latexHeaders/listings.tex @@ -20,7 +20,7 @@ breakatwhitespace=false, postbreak=\space, tabsize=2, - basicstyle=\ttfamily\footnotesize, + basicstyle=\ttfamily\small, showspaces=false, showstringspaces=false, extendedchars=true, diff --git a/math/math.tex b/math/math.tex index 1a4a684..7b2481d 100644 --- a/math/math.tex +++ b/math/math.tex @@ -158,6 +158,24 @@ Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: \end{align*} \lstinputlisting{math/legendre.cpp} +\subsection{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion} +\begin{itemize} + \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$. + Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. + \item $\sum_{d \vert n}\mu(d) = + \begin{cases*} + 1 & falls $n = 1$\\ + 0 & sonst + \end{cases*}$ +\end{itemize} +\textbf{Beispiel Inklusion/Exklusion:} +Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline +\textbf{Lösung}: +Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$. +Es gibt $2^{cnt[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten. +Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$. +\lstinputlisting{math/mobius.cpp} + \subsection{Kombinatorik} \begin{flushleft} @@ -275,6 +293,68 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale $\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ \\ \bottomrule \end{tabular} +\vspace{1mm} + +\begin{tabular}{l|l|l} + \toprule + \multicolumn{3}{c}{Reihen} \\ + \midrule + $\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ & + $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(n + 2)}{6}$ & + $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\ + + $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ & + $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ & + $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ \\ + + \multicolumn{2}{l|}{ + $\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$ + } & + $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\ + + $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ & + \multicolumn{2}{l}{ + $\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$ + } \\ + + $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ & + \multicolumn{2}{l}{ + $\sum\limits_{i = 1}^n \binom{i}{m}H_i = + \binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m + 1}\right)$ + } \\ + \bottomrule +\end{tabular} +\vspace{1mm} + +\begin{tabular}{l|r} + \toprule + \multicolumn{2}{c}{ + Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) + } \\ + \midrule + $\E(X + Y) = \E(X) + \E(Y)$ & + $\E(\alpha X) = \alpha \E(X)$ \\ + + $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & + $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\ + + $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ & + $\Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ \\ + \bottomrule +\end{tabular} +\vspace{1mm} + +\begin{tabular}{lr|lr} + \toprule + \multicolumn{4}{c}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ + \midrule + $\#A > k\#B$ & $Pr = \frac{a - kb}{a + b}$ & + $\#B - \#A \leq k$ & $Pr = 1 - \frac{a!b!}{(a + k + 1)!(b - k - 1)!}$ \\ + + $\#A \geq k\#B$ & $Pr = \frac{a + 1 - kb}{a + 1}$ & + $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ \\ + \bottomrule +\end{tabular} \vspace{5mm} \begin{tabular}{c|cccc} @@ -358,36 +438,36 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale \end{flushleft} \vspace{1mm} -\begin{tabular}{l|r} +\begin{tabular}{ll} \toprule - \multicolumn{2}{c}{ - Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) - } \\ + \multicolumn{2}{c}{Verschiedenes} \\ \midrule - $\E(X + Y) = \E(X) + \E(Y)$ & - $\E(\alpha X) = \alpha \E(X)$ \\ + Türme von Hanoi, minimale Schirttzahl: & + $T_n = 2^n - 1$ \\ - $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & - $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\ + \#Regionen zwischen $n$ Gearden & + $\frac{n\left(n + 1\right)}{2} + 1$ \\ - $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ & - $\Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ \\ - \bottomrule -\end{tabular} -\vspace{1mm} + \#geschlossene Regionen zwischen $n$ Geraden & + $\frac{n^2 - 3n + 2}{2}$ \\ -\begin{tabular}{lr|lr} - \toprule - \multicolumn{4}{c}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ - \midrule - $\#A > k\#B$ & $Pr = \frac{a - kb}{a + b}$ & - $\#B - \#A \leq k$ & $Pr = 1 - \frac{a!b!}{(a + k + 1)!(b - k - 1)!}$ \\ + \#markierte, gewurzelte Bäume & + $n^{n-1}$ \\ - $\#A \geq k\#B$ & $Pr = \frac{a + 1 - kb}{a + 1}$ & - $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ \\ + \#markierte, nicht gewurzelte Bäume & + $n^{n-2}$ \\ + + \#Wälder mit $k$ gewurzelten Bäumen & + $\frac{k}{n}\binom{n}{k}n^{n-k}$ \\ + + Derangements & + $!n = (n - 1)(!(n - 1) + !(n - 2))$ \\ + & + $!n = \left\lfloor\frac{n!}{e} + \frac{1}{2}\right\rfloor$ \\ + & + $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ \bottomrule \end{tabular} -\vspace{5mm} \begin{tabular}{p{4.3cm}|p{7cm}} \toprule @@ -485,67 +565,6 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale Periode ab $n = 72$ der Länge $12$.\\ \bottomrule \end{tabular} -\vspace{5mm} - -\begin{tabular}{l|l|l} - \toprule - \multicolumn{3}{c}{Reihen} \\ - \midrule - $\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ & - $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(n + 2)}{6}$ & - $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\ - - $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ & - $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ & - $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ \\ - - \multicolumn{2}{l|}{ - $\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$ - } & - $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\ - - $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ & - \multicolumn{2}{l}{ - $\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$ - } \\ - - $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ & - \multicolumn{2}{l}{ - $\sum\limits_{i = 1}^n \binom{i}{m}H_i = - \binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m + 1}\right)$ - } \\ - \bottomrule -\end{tabular} -\vspace{5mm} - -\begin{tabular}{ll} - \toprule - \multicolumn{2}{c}{Verschiedenes} \\ - \midrule - Türme von Hanoi, minimale Schirttzahl: & - $T_n = 2^n - 1$ \\ - - \#Regionen zwischen $n$ Gearden & - $\frac{n\left(n + 1\right)}{2} + 1$ \\ - - \#abgeschlossene Regionen zwischen $n$ Geraden & - $\frac{n^2 - 3n + 2}{2}$ \\ - - \#markierte, gewurzelte Bäume & - $n^{n-1}$ \\ - - \#markierte, nicht gewurzelte Bäume & - $n^{n-2}$ \\ - - \#Wälder mit $k$ gewurzelten Bäumen & - $\frac{k}{n}\binom{n}{k}n^{n-k}$ \\ - - Dearangements & - $!n = (n - 1)(!(n - 1) + !(n - 2))$ \\ - & - $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ - \bottomrule -\end{tabular} -\subsection{Big Integers} -\lstinputlisting{math/bigint.cpp} +% \subsection{Big Integers} +% \lstinputlisting{math/bigint.cpp} diff --git a/math/mobius.cpp b/math/mobius.cpp new file mode 100644 index 0000000..7830eb1 --- /dev/null +++ b/math/mobius.cpp @@ -0,0 +1,4 @@ +// Laufzeit: O(N*log(log(N))) +int mu[N+1]; mu[1] = 1; +for (int i = 1; i <= N; i++) { + for (int j = 2 * i; j <= N; j += i) mu[j] -= mu[i]; diff --git a/math/phi.cpp b/math/phi.cpp index 492a9d2..f568bba 100644 --- a/math/phi.cpp +++ b/math/phi.cpp @@ -10,3 +10,11 @@ ll phi(ll n) { // Laufzeit: O(sqrt(n)) if(n > 1) result -= result / n; return result; } + +// Sieb, falls alle Werte benötigt werden. Laufzeit: O(N*log(log(N))) +for (int i = 1; i <= N; i++) phi[i] = i; +for (int i = 2; i <= N; i++) if (phi[i] == i) { + for (int j = i; j <= N; j += i) { + phi[j] /= i; + phi[j] *= i - 1; +}} 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); +} diff --git a/string/ahoCorasick.cpp b/string/ahoCorasick.cpp index c283f6f..d221fcb 100644 --- a/string/ahoCorasick.cpp +++ b/string/ahoCorasick.cpp @@ -1,55 +1,57 @@ // Laufzeit: O(n + m + z), n = #Text, m = Summe #Pattern, z = #Matches // Findet mehrere Patterns gleichzeitig in einem String. -// 1) Wurzel erstellen: vertex *automaton = new vertex(); -// 2) Mit addString(automaton, s, idx); Patterns hinzufügen. -// 3) finishAutomaton(automaton) aufrufen. -// 4) Mit automaton = go(automaton, c) in nächsten Zustand wechseln. +// 1) Wurzel erstellen: aho.push_back(vertex()); +// 2) Mit addString(0, pattern, idx); Patterns hinzufügen. +// 3) finishAutomaton(0) aufrufen. +// 4) Mit state = go(state, c) in nächsten Zustand wechseln. // DANACH: Wenn patterns-Vektor nicht leer ist: Hier enden alle // enthaltenen Patterns. // ACHTUNG: Die Zahlenwerte der auftretenden Buchstaben müssen // zusammenhängend sein und bei 0 beginnen! struct vertex { - vertex *next[ALPHABET_SIZE], *failure; - char character; + int next[ALPHABET_SIZE], failure; + int character; vector<int> patterns; // Indizes der Patterns, die hier enden. - vertex() { for (int i = 0; i < ALPHABET_SIZE; i++) next[i] = NULL; } + vertex() { for (int i = 0; i < ALPHABET_SIZE; i++) next[i] = -1; } }; +vector<vertex> aho; -void addString(vertex *v, string &pattern, int patternIdx) { - for (int i = 0; i < (int)pattern.length(); i++) { - if (!v->next[(int)pattern[i]]) { - vertex *w = new vertex(); - w->character = pattern[i]; - v->next[(int)pattern[i]] = w; +void addString(int v, vector<int> &pattern, int patternIdx) { + for (int i = 0; i < (int)pattern.size(); i++) { + if (aho[v].next[pattern[i]] == -1) { + aho[v].next[pattern[i]] = aho.size(); + aho.push_back(vertex()); + aho.back().character = pattern[i]; } - v = v->next[(int)pattern[i]]; + v = aho[v].next[pattern[i]]; } - v->patterns.push_back(patternIdx); + aho[v].patterns.push_back(patternIdx); } -void finishAutomaton(vertex *v) { +void finishAutomaton(int v) { for (int i = 0; i < ALPHABET_SIZE; i++) - if (!v->next[i]) v->next[i] = v; + if (aho[v].next[i] == -1) aho[v].next[i] = v; - queue<vertex*> q; + queue<int> q; for (int i = 0; i < ALPHABET_SIZE; i++) { - if (v->next[i] != v) { - v->next[i]->failure = v; - q.push(v->next[i]); + if (aho[v].next[i] != v) { + aho[aho[v].next[i]].failure = v; + q.push(aho[v].next[i]); }} while (!q.empty()) { - vertex *r = q.front(); q.pop(); + int r = q.front(); q.pop(); for (int i = 0; i < ALPHABET_SIZE; i++) { - if (r->next[i]) { - q.push(r->next[i]); - vertex *f = r->failure; - while (!f->next[i]) f = f->failure; - r->next[i]->failure = f->next[i]; - for (int j = 0; j < (int)f->next[i]->patterns.size(); j++) { - r->next[i]->patterns.push_back(f->next[i]->patterns[j]); + if (aho[r].next[i] != -1) { + q.push(aho[r].next[i]); + int f = aho[r].failure; + while (aho[f].next[i] == -1) f = aho[f].failure; + aho[aho[r].next[i]].failure = aho[f].next[i]; + for (int j = 0; j < (int)aho[aho[f].next[i]].patterns.size(); j++) { + aho[aho[r].next[i]].patterns.push_back( + aho[aho[f].next[i]].patterns[j]); }}}}} -vertex* go(vertex *v, char c) { - if (v->next[(int)c]) return v->next[(int)c]; - else return go(v->failure, c); +int go(int v, int c) { + if (aho[v].next[c] != -1) return aho[v].next[c]; + else return go(aho[v].failure, c); } diff --git a/string/trie.cpp b/string/trie.cpp index 1b5f573..fa9ec49 100644 --- a/string/trie.cpp +++ b/string/trie.cpp @@ -1,20 +1,25 @@ +// Zahlenwerte müssen bei 0 beginnen und zusammenhängend sein. struct node { - node *e[26]; // Implementierung für Kleinbuchstaben. - int c = 0; // Anzahl der Wörter, die an diesem node enden. - node() { for(int i = 0; i < 26; i++) e[i] = NULL; } + int children[ALPHABET_SIZE], c; // c = #Wörter, die hier enden. + node () { + idx = -1; + for (int i = 0; i < ALPHABET_SIZE; i++) children[i] = -1; + } }; +vector<node> trie; // Anlegen mit trie.push_back(node()); -void insert(node *root, string &txt, int s = 0) { // Laufzeit: O(|txt|) - if(s == (int)txt.size()) root->c++; - else { - int idx = (int)(txt[s] - 'a'); - if(root->e[idx] == NULL) root->e[idx] = new node(); - insert(root->e[idx], txt, s+1); -}} +void insert(int vert, vector<int> &txt, int s) { // Laufzeit: O(|txt|) + if (s == (int)txt.size()) { trie[vert].c++; return; } + if (trie[vert].children[txt[s]] == -1) { + trie[vert].children[txt[s]] = trie.size(); + trie.push_back(node()); + } + insert(trie[vert].children[txt[s]], txt, s + 1); +} -int contains(node *root, string &txt, int s = 0) { // Laufzeit: O(|txt|) - if(s == (int)txt.size()) return root->c; - int idx = (int)(txt[s] - 'a'); - if(root->e[idx] != NULL) return contains(root->e[idx], txt, s + 1); - else return 0; +int contains(int vert, vector<int> &txt, int s) { // Laufzeit: O(|txt|) + if (s == (int)txt.size()) return trie[vert].c; + if (trie[vert].children[txt[s]] != -1) { + return contains(trie[vert].children[txt[s]], txt, s + 1); + } else return 0; } Binary files differ@@ -1,4 +1,4 @@ -\documentclass{article} +\documentclass[a4paper,9pt]{scrartcl} % General information. \newcommand{\teamname}{Hello KITty} @@ -9,7 +9,7 @@ \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} -% Include headers. +% Include headers. \input{latexHeaders/layout} \input{latexHeaders/math} \input{latexHeaders/listings} @@ -17,16 +17,16 @@ % Title and author information. \title{Team Contest Reference} \author{\teamname \\ \university} -\date{20. November 2016} +\date{26. November 2017} \begin{document} % Titlepage with table of contents. \maketitle \setlength{\columnsep}{1cm} -\begin{multicols}{2} - \tableofcontents -\end{multicols} -\newpage +% \begin{multicols}{2} +% \tableofcontents +% \end{multicols} +% \newpage % Content. \begin{multicols*}{2} @@ -35,7 +35,6 @@ \input{geometry/geometry} \input{math/math} \input{string/string} - \input{java/java} \input{other/other} \end{multicols*} \end{document} |