蓝桥杯备考

数论：判断素数，鸽笼定理，抽屉理论

注意事项：

long类型的数后面要加L
long s = 2658417853L;

保留几位小数：
System.out.printf(“%.2f”, arg);
四舍五入问题：比如保留两位小数，就在数的后面再加0.005再保留小数，就不会有截断不入的情况。

BufferedReader和Scanner不能混用

整数转换成小数：1.0 * jigeSum

String转换成字符串数组：S.toCharArray()

long的范围是19位

Java异或：^

尺取法

应用场景：滑动窗口，[L, R]，R随着L增大而增大

记忆化搜索

应用场景：多次查询
多次查询一定要储存

二分查找

应用场景：最小值最大化，最大值最小化
必须有单调性！！

模板题：最终结果取right
三个地方特别容易记混：
1、求mid公式是否+1（这个记因为最小<最大，所以找最小不加，找最大+1）
2、while循环带不带等号（这个自己测试吧实在没想到好的记忆方法）
3、更新high和left哪个+1：这个好理解，哪个满足条件哪个=mid，不满足条件+1
在这里插入图片描述

并查集

1、存储
在这里插入图片描述
2、查询

路径压缩：（记忆化递归）

3、集合合并

在这里插入图片描述

贪心

选择必须无后效性，当前选择不能影响后序选择对结果的影响

注意熟悉结构体排序：

Arrays.sort(goods, (Comparator<Goods>)(Goods x, Goods y) -> {
        	return -Double.compare(x.d, y.d);
        });

快速幂

在这里插入图片描述

最大公约数gcd

辗转相除法
在这里插入图片描述

LCM最小公倍数

在这里插入图片描述

图论

邻接矩阵初始化等于INF的INF取多少合适？
dis[a,b] = dis[a,k] + dis[k,b]
INF = max/2
INF = -1也可以（最好用这个）

邻接矩阵不能存储重边。如果有重边，取最小值

迪杰斯特拉：不能处理负权值
在这里插入图片描述

在这里插入图片描述

Java:
在这里插入图片描述

SPFA:
在这里插入图片描述

Java

排序

import java.util.*;
import java.io.*;
public class 排序 {
	public static void main(String[] args) {
		Integer[] arr = {23,1,14,56,33,7};
		Comparator cmp = new myCompare();
		Arrays.sort(arr, cmp);
		for(Integer i : arr) {
			System.out.println(i);
		}
	}
	
}
class myCompare implements Comparator<Integer> {
	public int compare(Integer o1, Integer o2) {
		return -Integer.compare(o1, o2);
	}
}

        Map<Long, Integer> map = new TreeMap<>(new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return (int)(o1 - o2);
            }
        });