Vor ungefähr einem halben Jahr war ich mit der hellblauen Farbe zufrieden, so dass ich eine Weile vom Wettbewerbsprofi weg war, aber von ABC am 19.5. (So) wird es ~ 2000 bewertet. Also dachte ich darüber nach, zu dieser Gelegenheit zurückzukehren, und überprüfte den Algorithmus, der häufig in dem damals gelösten 400-Punkte-Problem auftrat, und machte ihn zu einer Vorlage. Die Details der einzelnen Algorithmen werden anderen Seiten überlassen, um sich auf den Umfang der Berechnung, Verwendung und Erläuterung von Vorlagen zu spezialisieren. Sterne repräsentieren die Frequenz (willkürlich).
Selbst wenn das Problem weniger als 400 Punkte beträgt, wird es vorerst herauskommen. Sie können die maximale Verpflichtung mit O berechnen (log (min (num1, num2))). Übrigens können Sie das minimale gemeinsame Vielfache mit num1 * num2 / gcd berechnen.
gcd.java
//return gcd O(logN)
public static int gcd(int num1,int num2) {
if(num2==0) return num1;
else return gcd(num2,num1%num2);
}
Besonders da die Mod-Verarbeitung von 10 ^ 9 + 7 mühsam war, habe ich es zu einer Vorlage gemacht. Auch die Leistungsberechnung. Die Leistungsberechnung ist der Berechnungsbetrag von O (logb) mit der Basis a / Exponent b und O (min (k, n-k) * logM) mit nCk (mod M).
combination.java
//return nCk mod M (M must be prime number) O(min(k,n-k)*logM)
public static int nCk(int n,int k,int M) {
long ret = 1;
int min = Math.min(k, n-k);
for(int i=1;i<=min;i++) {
ret = (ret * pow(i,M-2,M)) % M;
}
for(int i=n-min+1;i<=n;i++) {
ret = (ret * i) % M;
}
return (int)ret;
}
//return a^b mod M O(logB)
public static long pow(long a,long b,int M) {
long ret = 1;
long tmp = a;
while(b>0) {
if((b&1)==1) ret = (ret * tmp) % M;
tmp = (tmp * tmp) % M;
b = b>>1;
}
return ret;
}
Union-Find ★★★ Das Problem der Verwaltung der Gruppierung ist tödlich. Es ist jedoch selten, so zu antworten, wie es ist, und in den meisten Fällen ist es erforderlich, die Datenstruktur im Inneren zu ändern, um sie an das Problem anzupassen. Beispiel: Transformieren Sie es so, dass es die Anzahl der Knoten in der Gruppe enthält. Da es einfach ist, nach der richtigen Bewerbungsfähigkeit in diesem Bereich zu fragen, werden Sie häufig mit 400 Punkten gefragt. Sowohl das Extrahieren übergeordneter Knoten als auch das Verbinden von Gruppen kann schneller als O (logN) durchgeführt werden.
union-find.java
//return root node idx O(a(N)) ( O(1)<O(a(N))<O(logN) )
public static int find(int[] tree,int idx) {
if(tree[idx]==idx) return idx;
else return tree[idx] = find(tree,tree[idx]);
}
//union idx2 tree to idx1 tree O(a(N))
public static void union(int[] tree,int idx1,int idx2) {
int root1 = find(tree,idx1);
int root2 = find(tree,idx2);
tree[root2] = root1;
}
BinaryIndexedTree ★ Dies ist eine Datenstruktur, die eine teilweise Summenextraktion / -addition zu Array-Elementen mit O (logN) ermöglicht. Wenn Sie nur die Teilsumme extrahieren möchten, können Sie normalerweise die kumulative Summe verwenden. Dies ist jedoch besser geeignet, wenn Sie die Array-Elemente in der Zwischenzeit hinzufügen müssen. Nun, ich sehe nicht viel.
binary-indexed-tree.java
//add value at idx on bit O(logN)
public static void add(int[] bit,int idx,int value) {
for(int i=idx;i<bit.length;i+=(i&-i)) bit[i] += value;
}
//return sum [1,idx] O(logN)
public static int sum(int[] bit,int idx) {
int ret = 0;
for(int i=idx;i>0;i-=(i&-i)) ret += bit[i];
return ret;
}
Danach denke ich, dass die Standard-Java-Bibliothek etwas tun wird, aber die, die ich oft benutze, ist
Ist es? Es ist praktisch, Elemente hinzuzufügen und maximale / minimale Elemente in 0 (logN) Zeit zu extrahieren. Es wird auch in Dyxtra verwendet. Standardmäßig wird jedoch nur die Minimalwerterfassung des numerischen Typs akzeptiert. Wenn Sie also den Maximalwert erhalten oder ein anderes Element als den numerischen Typ einfügen möchten, definieren Sie den Komparator selbst. Das Beispiel ist eine PriorityQueue, die von Comparator definiert wurde, um das int-Array einzufügen und das 0. größte Element zu erhalten.
priority-queue.java
PriorityQueue<int[]> p_que = new PriorityQueue<>((array1,array2)->-array1[0]+array2[0]);
Es ist ein Vertrauter mit dem kürzesten Routenproblem. Der Berechnungsbetrag ist O (Elog V) mit der Anzahl der Knoten als V und der Anzahl der Seiten als E. Wenn es jedoch eine negative Seite gibt, wird es nicht gut funktionieren, also werde ich in diesem Fall Bellman Ford verwenden.
dijkstra.java
//return min distance from start to end O(ElogV) (negative cost is prohibited)
//edge is int[3] array {from,to,cost}
//edges is edge list from specific node
//all_edges is Map<from node number,edges>
public static int dijkstra(Map<Integer,List<int[]>> all_edges,int start,int end,int max_node_number) {
int[] distance = new int[max_node_number+1];
for(int i=0;i<distance.length;i++) distance[i] = -1;
PriorityQueue<int[]> p_que = new PriorityQueue<>((a,b)->((distance[a[0]]+a[2])-(distance[b[0]]+b[2])));
distance[start] = 0;
List<int[]> edges = all_edges.get(start);
for(int i=0;i<edges.size();i++) p_que.add(edges.get(i));
while(distance[end]<0) {
int[] nearest_edge = p_que.poll();
if(distance[nearest_edge[1]]<0) {
distance[nearest_edge[1]] = distance[nearest_edge[0]] + nearest_edge[2];
if(all_edges.containsKey(nearest_edge[1])) {
edges = all_edges.get(nearest_edge[1]);
for(int i=0;i<edges.size();i++) {
int[] edge = edges.get(i);
if(distance[edge[1]]<0) p_que.add(edge);
}
}
}
}
return distance[end];
}
Dieser Algorithmus ist effektiv, wenn das Problem der kürzesten Route eine negative Seite aufweist. Der Berechnungsbetrag ist O (EV), was Dyxtra etwas unterlegen ist. Es gibt jedoch einige Dinge, die Dyxtra nicht tun kann, z. B. das Erkennen negativer Verschlüsse. Gibt es eine negative Seite oder gibt es eine lose Beschränkung der Anzahl der Knoten und Seiten für Dyxtra? Wenn Sie darüber nachdenken, kann es dieses Muster sein.
bellman-ford.java
//return min distance from start to end O(EV) (negative cost is possible)
//edge is int[3] array {from,to,cost}
//edges is edge list from specific node
//all_edges is Map<from node number,edges>
public static int bellmanFord(Map<Integer,List<int[]>> all_edges,int start,int end,int max_node_number) {
int[] distance = new int[max_node_number+1];
int INF = Integer.MAX_VALUE;
for(int i=0;i<distance.length;i++) {
distance[i] = INF;
}
distance[start] = 0;
int counter = all_edges.size();
while(counter>0) {
boolean updated = false;
for(List<int[]> edges: all_edges.values()) {
if(distance[edges.get(0)[0]]==INF) continue;
for(int[] edge: edges) {
if(distance[edge[0]]+edge[2] < distance[edge[1]]) {
distance[edge[1]] = distance[edge[0]]+edge[2];
updated = true;
}
}
}
if(!updated) break;
counter--;
}
return counter==0?Integer.MIN_VALUE:distance[end];
}
Dies ist nützlich, wenn das Problem der kürzesten Route den kürzesten Abstand zwischen allen Knoten erfordert. Da der Rechenaufwand so hoch wie O (V ^ 3) ist und die Anzahl der Knoten V beträgt, kann er nur verwendet werden, wenn die Randbedingung für die Anzahl der Knoten 100 oder weniger beträgt. Im Gegenteil, wenn Sie ihn kennen, können Sie ihn in den meisten Fällen lösen. Denken Sie also daran Es gibt keinen Verlust.
warshall-floyd.java
//return new distance matrix O(logV^3)
public static int[][] warshallFloyd(int[][] distance){
int node_number = distance.length;
int[][] min_distance = new int[node_number][node_number];
for(int i=0;i<node_number;i++) {
for(int j=0;j<node_number;j++) {
min_distance[i][j] = distance[i][j];
}
}
for(int via=0;via<node_number;via++) {
for(int from=0;from<node_number;from++) {
for(int to=0;to<node_number;to++) {
min_distance[from][to] = Math.min(min_distance[from][to], min_distance[from][via]+min_distance[via][to]);
}
}
}
return min_distance;
}
Es wird häufig verwendet, wenn ein Problem mit dem Baum mit der minimalen Fläche vorliegt. Der Berechnungsbetrag ist O (Elog V) mit der Anzahl der Knoten als V und der Anzahl der Seiten als E. Union-Find wird verwendet, um den Verbindungsstatus von Knoten zu bestimmen (ob sie zur selben Gruppe gehören).
kruskal.java
//return min cost for union all nodes O(ElogV)
//edge is int[3] array {node1,node2,cost}
//edges is edge list
public static int kruskal(List<int[]> edges,int max_node_number) {
edges.sort((a,b)->(a[2]-b[2]));
int[] uft = new int[max_node_number+1];
for(int i=0;i<uft.length;i++) {
uft[i] = i;
}
int cost_sum = 0;
for(int[] edge: edges) {
if(find(uft,edge[0])!=find(uft,edge[1])) {
union(uft,edge[0],edge[1]);
cost_sum += edge[2];
}
}
return cost_sum;
}
public static int find(int[] tree,int idx) {
if(tree[idx]==idx) return idx;
else return tree[idx] = find(tree,tree[idx]);
}
public static void union(int[] tree,int idx1,int idx2) {
int root1 = find(tree,idx1);
int root2 = find(tree,idx2);
tree[root2] = root1;
}
Ich kann den Algorithmus nicht vorlegen, aber das Thema, das durcheinander kommt, ist wie folgt.
Da es nicht als Vorlage verwendet werden kann, ist es einfach, die angelegte Leistung / Montageleistung vor Ort zu messen, sodass es häufig herauskommt. Wenn Sie nachschlagen, finden Sie viele verwandte Artikel. Lassen Sie uns also ~ 2000 Rated ABC widmen.
Recommended Posts