1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
\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{Linear time sorting}
\begin{lstlisting}
int p[10] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
int get_i_th_digit(int digit, int i) {
return (digit / p[i]) % 10;
}
void sortLinear(vector<int> &s) {
int max_digit;
for(int i = 0; i < s.size(); i++) {
int digit = ceil(log10(s[i]));
if(digit > max_digit)
max_digit = digit;
}
for(int d = 0; d < max_digit; d++) {
vector<vector<int>> bucket(10);
for(int i = 0; i < s.size(); i++)
bucket[get_i_th_digit(s[i],d)].push_back(s[i]);
s.clear();
for(int i = 0; i < 10; i++)
copy(bucket[i].begin(), bucket[i].end(), back_inserter(s));
}
}
\end{lstlisting}
|
