Il y a environ six mois, j'étais satisfait de la couleur bleu clair, donc j'étais loin de la compétition pendant un moment, mais à partir de ABC le 19/05 (Sun), il sera évalué à ~ 2000. J'ai donc pensé à revenir sur cette opportunité, j'ai donc revu l'algorithme qui apparaissait fréquemment dans le problème de 400 points qui a été résolu à ce moment-là et en ai fait un modèle. Les détails de chaque algorithme seront laissés à d'autres pages pour se spécialiser dans la quantité de calcul, l'utilisation et l'explication des modèles. Les étoiles représentent la fréquence (arbitraire).
Même si le problème est inférieur à 400 points, il sortira, mais pour le moment. Vous pouvez calculer l'engagement maximum avec O (log (min (num1, num2))). En passant, vous pouvez calculer le multiple commun minimum avec num1 * num2 / gcd.
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);
}
D'autant que le traitement du mod de 10 ^ 9 + 7 était gênant, j'en ai fait un modèle. Aussi, le calcul de la puissance. Le calcul de puissance est la quantité de calcul de O (logb) avec la base a / exposant b et O (min (k, n-k) * logM) avec 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 ★★★ Le problème de la gestion du regroupement est mortel. Cependant, il est rare de répondre sous cette forme telle quelle, et dans la plupart des cas, il est nécessaire de modifier la structure des données à l'intérieur pour s'adapter au problème. Par exemple, le transformer pour contenir le nombre de nœuds dans le groupe. Comme il est facile de poser des questions sur la bonne capacité d'application dans ce domaine, on vous demandera souvent 400 points. L'extraction des nœuds parents et la jonction de groupes peuvent être effectuées plus rapidement que O (logN).
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 ★ Il s'agit d'une structure de données qui permet l'extraction / l'ajout de somme partielle aux éléments du tableau avec O (logN). Si vous souhaitez uniquement extraire la somme partielle, vous pouvez généralement utiliser la somme cumulée, mais si vous devez ajouter des éléments au tableau entre-temps, c'est plus approprié. Eh bien, je ne vois pas grand-chose.
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;
}
Après cela, je pense que la bibliothèque Java standard fera quelque chose, mais celle que j'utilise souvent est
Vraiment? C'est une méthode pratique qui ajoute des éléments et extrait les éléments maximum / minimum en temps 0 (logN) respectivement. Il est également utilisé dans Dyxtra. Cependant, par défaut, seule l'acquisition de la valeur minimale de type numérique est acceptée, donc si vous souhaitez obtenir la valeur maximale ou insérer un élément autre que le type numérique, définissons vous-même le comparateur. L'exemple est un PriorityQueue défini par Comparator pour insérer le tableau int et obtenir le 0e élément le plus grand.
priority-queue.java
PriorityQueue<int[]> p_que = new PriorityQueue<>((array1,array2)->-array1[0]+array2[0]);
Il est familier avec le problème d'itinéraire le plus court. La quantité de calcul est O (Elog V) avec le nombre de nœuds comme V et le nombre de côtés comme E. Cependant, s'il y a un côté négatif, cela ne fonctionnera pas bien, donc dans ce cas, j'utiliserai Bellman Ford.
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];
}
Cet algorithme est efficace lorsqu'il y a un côté négatif dans le problème de l'itinéraire le plus court. Le montant du calcul est O (EV), ce qui est légèrement inférieur à Dyxtra. Cependant, il y a certaines choses que Dyxtra ne peut pas faire, comme la détection de fermetures négatives. Y a-t-il un côté négatif ou y a-t-il une restriction lâche sur le nombre de nœuds et de côtés pour Dyxtra? Si vous y réfléchissez, c'est peut-être ce modèle.
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];
}
Ceci est utile lorsque le problème d'itinéraire le plus court nécessite la distance la plus courte entre tous les nœuds. Étant donné que la quantité de calcul est lourde comme O (V ^ 3) avec le nombre de nœuds comme V, elle ne peut être utilisée que lorsque la condition de contrainte du nombre de nœuds est de 100 ou moins, mais au contraire, si vous le connaissez, vous pouvez le résoudre dans la plupart des cas, alors rappelez-vous Il n'y a pas de perte.
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;
}
Il est souvent utilisé lorsqu'il y a un problème avec l'arborescence de la superficie minimale. La quantité de calcul est O (Elog V) avec le nombre de nœuds comme V et le nombre de côtés comme E. Union-Find est utilisé pour déterminer l'état de connexion des nœuds (s'ils appartiennent au même groupe).
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;
}
Je ne peux pas modéliser l'algorithme, mais le sujet qui est foiré est comme ça.
--Somme cumulée --DP (planification dynamique) Opération --bit (recherche complète de bits, problème xor)
Comme il ne peut pas être modélisé, il est facile de mesurer la puissance appliquée / la puissance de montage sur place, de sorte qu'elle sortira souvent. Si vous recherchez, vous trouverez de nombreux articles connexes, alors consacrons-nous à ~ 2000 Classé ABC.
Recommended Posts