java模板【蓝桥杯向】

Nannan Lv5
  2024-03-30 20:54 2024-03-30 20:54 Created   2024-09-30 21:01:40 2024-09-30 21:01:40 Updated      

nannan的板子

eclipse自动导包和自动补全配置：
自动导包
image

自动补全
image

更改主题

image

代码片段1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static void main(String[] args)throws Exception{

    }

    public static int cin() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

}

代码片段2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	static int N = 100010;
	static Scanner cin = new Scanner(System.in);
	static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	public static void main(String[] args) throws Exception {
		
		cout.close();
	}
}

排序

自定义结构体排序

在类里面实现排序方法即可，注意引用Comparable接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static public class Node implements Comparable<Node>{
        int num = 0;
        long k = 0,b = 0;
        public Node(){}
        public Node(int _num,long _k,long _b){
            this.num = _num;
            this.k = _k;
            this.b = _b;
        }

        public int compareTo(Node o) {
            long cost1 = (this.num + 1) * Math.max(0, k * (num + 1) + b) - num * Math.max(0, k * num + b);
            long cost2 = (o.num + 1) * Math.max(0, o.k * (o.num + 1) + o.b) - o.num * Math.max(0, o.k * o.num + o.b);
            return cost1 < cost2 ? 1 : -1;
        }
    }

Arrays.sort

实现Comparator接口实现降序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Main {
    public static void main(String[] args){
      	//不能使用基本数据类型
        Integer[] arr = {5,4,7,9,2,12,54,21,1};
        //降序
        Arrays.sort(arr, new Comparator<Integer>() {
        		//重写compare方法，最好加注解，不加也没事
            public int compare(Integer a, Integer b) {
              	//返回值>0交换
                return b-a;
            }
        });
        System.out.println(Arrays.toString(arr));    
    }   
}

等价于：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Main {
    public static void main(String[] args){
      	//不能使用基本数据类型
        Integer[] arr = {5,4,7,9,2,12,54,21,1};
        //降序
        Arrays.sort(arr, (a, b) -> {
            //返回值>0交换
            return b-a;
        });
        System.out.println(Arrays.toString(arr));
    }
}

还可以：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Main {
    public static void main(String[] args){
        Integer[] arr = {5,4,7,9,2,12,54,21,1};
        //降序
        //重新实现Comparator接口
        Arrays.sort(arr, new compa());
        System.out.println(Arrays.toString(arr));
    }
}

class compa implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
    	// A.compareTo(B) A>B 返回1，A=B 返回0，A<B 返回-1
      	// compareTo()返回值>0就交换
      	// 如果02 > o1 就交换 =>降序
        return o2.compareTo(o1);
    }
}

Collections.sort

Collections.sort用与于集合的排序，比如linked，下面给出排序的形式

1
2
3
4
Collections.sort(S, new Comparator<Student>(){
    public int compare(Student stu1, Student stu2) {
        return stu2.getg()-stu1.getg();
}

浮点数保留2位小数

一、String类的方式

1
2
double testDounle_01 = 123.456;
System.out.println(String.format("%.2f", testDounle_01));

二、BigDecimal类进行数据处理

1
2
3
4
5
6
7
8
9
double testDounle_01 = 123.456;
float testFloat_01 = 456.125f;

/**
*  BigDecimal类进行数据处理
*  */
BigDecimal bigDecimal = new BigDecimal(testDounle_01);
double ans_2 = bigDecimal.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
System.out.println(ans_2);

用Scanner读入Char

Scanner 本身并不支持获取char类型的数据
但是可以通过charAt()方法截取string的首位来获取char类型的数据

1
2
3
import java.util.Scanner;
Scanner scanner = new Scanner(System.in);
char ch = scanner.next().charAt(0);

1.数学

任意进制转换

1
2
3
4
5
6
// 如果题目要进行转化的进制在2~36之间的话直接调用库函数就行了。
String s = in.readLine();	
int a = Integer.parseInt(s, 16); // 将16进制的字符串转化十进制数
//BigInteger a = new BigInteger(s, 16);// 高精度数
out.write(Integer.toString(a, 8));	// 转化为8进制输出

快速幂

1
2
3
4
5
6
7
8
9
10
11
12

static long qmi(long a,long b,long mod){
    long ans = 1 % mod;
    while(b != 0)
    {
        if((b & 1) != 0)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
	return ans;
}

gcd

1
2
3
4
static long gcd(long a,long b)
{
     return b == 0 ? a : gcd(b,a%b);
}

质因数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long []a = new long[N];
long cnt;

void primer(long x)
{
    for (long i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            int s = 0;
            a[++cnt] = i;
            while (x % i == 0)
            {
                x = x / i;
                s++;
            }
        }
    }
    if (x > 1) a[++cnt] = x;
}

分解因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long  n;
n=cin.nextLong();
ArrayList<Long> a=new ArrayList<>();
for(long i=1;i<=Math.sqrt(n);i++)
{
  if(n%i==0) 
  {
      a.add(i);
      if(i!=n/i)
      {
          a.add(n/i);
      }
  }
}

线性筛

例题：P3383 【模板】线性筛素数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static boolean[] is_pri = new boolean[100000010];
static int[] pri = new int[6000010];
static int cnt;

static void init(int n) {
    Arrays.fill(is_pri, true);
    is_pri[1] = false;
    cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (cnt >= 6000000) {
            break;
        }
        if (is_pri[i]) {
            pri[++cnt] = i;
        }
        for (int j = 1; j <= cnt && (long)i * pri[j] <= n; j++) {
            is_pri[i * pri[j]] = false;
            if (i % pri[j] == 0) break;
        }
    }
}

组合数()

1
2
3
4
5
6
7
8
9
10
11
12
13
static int n;
static int c[][];
public static void init(int n,int mod)
{
    for(int i = 0;i <= n; i++)
    {
        for(int j = 0;j <= i; j++)
        {
            if(j==0) c[i][j] = 1;
            else c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
        }
    }
}

对于互质的两个数a和b，其不能组成的最大整数为

2.图论

BFS

例题 

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static Scanner cin = new Scanner(System.in);
	static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	public static class Node {
		Node(int _x, int _y) {
			this.x = _x;
			this.y = _y;
		}

		int x, y;
	}

	static int N = 1010;
	static char[][] a = new char[N][N];
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	static boolean[][] vis = new boolean[N][N];
	static int[][] dist = new int[N][N];
	static int n, m;

	static boolean check(int x, int y) {
		return (x >= 1 && x <= n && y >= 1 && y <= m) && (vis[x][y] == false) && (a[x][y] == '0');
	}

	static void bfs(int sx, int sy) {
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(sx, sy));
		vis[sx][sy] = true;
		dist[sx][sy] = 0;
		while (!q.isEmpty()) {
			Node t = q.poll();
			int x = t.x, y = t.y;
			for (int i = 0; i < 4; i++) {
				int tx = x + dir[i][0];
				int ty = y + dir[i][1];
				if (check(tx, ty)) {
					vis[tx][ty] = true;
					dist[tx][ty] = dist[x][y] + 1;
					q.offer(new Node(tx, ty));
				}
			}
		}
	}

	public static void main(String[] args) {
		n = cin.nextInt();
		m = n;

		for (int i = 1; i <= n; i++) {
			String s = cin.next();
			for (int j = 1; j <= m; j++)
				a[i][j] = s.charAt(j - 1);
		}

		int sx = cin.nextInt();
		int sy = cin.nextInt();
		int ex = cin.nextInt();
		int ey = cin.nextInt();
		bfs(sx, sy);

//		for (int i = 1; i <= n; i++) {
//			for (int j = 1; j <= m; j++) {
//				cout.print(dist[i][j] + " ");
//			}
//			cout.print("\n");
//		}

		cout.print(dist[ex][ey] + "\n");
		cout.close();
	}
}

链式前向星存图

1
2
3
4
5
6
7
8
9
10
//java版本
static int[] head,next,ends;
static long[]weights,dist;
static int n, m, total = 0//++total：记录从第一条边到最后一条边
public static void add(int start, int end, long weight) {//链式前向星的创建方法
    ends[total] = end;
    weights[total] = weight;
    next[total] = head[start];//以start为起点的上一条边的编号，即：与这个边起点相同的上一条边的编号
    head[start] = total++;//更新以start为起点的上一条边的编号
}

dijkatra

例题：P1339 Heat Wave G 

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int[] head,next,ends;
    static long[]weights,dist;
    static int n, m, tot = 0;
    static int st,ed;
    static class Node{
        int id;
        long dis;

        public Node(int _id,long _dis){
            this.id = _id;
            this.dis = _dis;
        }
    }
    public static void add(int u,int v,long w){
        ends[tot] = v;
        weights[tot] = w;
        next[tot] = head[u];
        head[u] = tot++;
    }

    public static void dijkstra(int start) {
        for(int i = 1;i <= n; i++){
            dist[i] = Long.MAX_VALUE;
        }

       Queue<Node> q = new PriorityQueue<>((o1, o2) -> (int) (o1.dis - o2.dis));
        q.offer(new Node(start,0));
        dist[start] = 0;
        while(!q.isEmpty()){
            Node u = q.poll();
            //遍历以当前节点为起点的所有边
            for(int i = head[u.id];i != -1;i = next[i]){
                int v = ends[i];
                if(dist[v] > dist[u.id] + weights[i]){
                    dist[v] = dist[u.id] + weights[i];
                    q.offer(new Node(v,dist[v]));
                }
            }
        }
    }

    public static void main(String[] args) throws Exception{
        Scanner cin = new Scanner(System.in);
        BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
        n = cin.nextInt(); m = cin.nextInt();
        st = cin.nextInt(); ed = cin.nextInt();
        head = new int[m*2 + 1];
        next = new int[m*2 + 1];
        ends = new int[m*2 + 1];
        weights = new long[m*2 + 1];
        dist = new long[n + 1];

        Arrays.fill(head,-1);

        for(int i = 1;i <= m; i++){
            int u, v; long w;
            u = cin.nextInt(); v = cin.nextInt();w = cin.nextLong();
            add(u,v,w);
            add(v,u,w);
        }

        dijkstra(st);



//        for(int i = 1;i <= n; i++)
//        {
//            if(dist[i] == Long.MAX_VALUE)
//                cout.write("-1 ");
//            else cout.write(dist[i] + " ");
//        }

        cout.write(dist[ed]+"\n");

        cout.close();
    }
}

Floyd

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
37
38
39
40
41
42
43
44
45
46
47
48
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	static int N = 100010;
	static Scanner cin = new Scanner(System.in);
	static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	static int[][] d;
	static int n, m;

	public static void floyd() {
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
	}

	public static void main(String[] args) throws Exception {
		n = cin.nextInt();
		m = cin.nextInt();
		d = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j)
					d[i][j] = 0;
				else
					d[i][j] = Integer.MAX_VALUE;
			}
		}
		for (int i = 1; i <= m; i++) {
			int u, v, w;
			u = cin.nextInt();
			v = cin.nextInt();
			w = cin.nextInt();
			d[u][v] = Math.min(d[u][v], w);
		}
		floyd();

		cout.close();
	}
}

3. 数据结构

java自带数据结构

①List

ArrayList(推荐)

虽然空间开销变大，但是时间复杂度小，类似静态数组空间翻倍

  • 初始化
1
List<Integer>arr = new ArrayList<>();
  • 尾部增加数据：
1
arr.add(Integer);
  • 第 个位置插入元素，剩下元素右移：
1
arr.add(pos,Integer);
  • 修改第个位置的值
1
arr.set(pos,Integer);
  • 链表元素个数
1
arr.size();
  • 获取pos位置的值
1
arr.get(pos);
  • 排序

使用 Collections.sort 对链表排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Integer>arr = new ArrayList<>();//创建一个空数组(默认长度是10)
for(int i = 1;i <= 10; i++)
{
    arr.add(i);
}


Collections.sort(arr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
});
for(int i = 0;i < 10; i++)
{
    int t = arr.get(i);
    cout.print(t+" ");
}

输出：

1
10 9 8 7 6 5 4 3 2 1

②Queue

ArrayDeque(基于数组实现)

  1. 插入删除复杂度
  2. 内部是一个循环数组
  • 初始化
1
Deque<Integer>q =new ArrayDeque<>();
  • 获取元素个数
1
q.size();
  • 判断队列是否为空
1
q.isEmpty()
  • 插入元素
1
q.offer(Integer);
  • 观察元素
1
q.peek();
  • 取出元素
1
q.poll();

③PriorityQueue

默认是小顶堆，若要改成大顶堆：

1
PriorityQueue<Integer>q = new PriorityQueue<>((x,y)->{return y-x;});

方法和上面一样。

④Deque

ArrayDeque(基于数组实现)

  1. 插入删除复杂度
  2. 内部是一个循环数组
  • 初始化
1
Deque<Integer>q =new ArrayDeque<>();
  • 获取元素个数
1
q.size();
  • 判断队列是否为空
1
q.isEmpty()
  • 头部插入元素
1
q.offerFirst(Integer);
  • 尾部插入元素
1
q.offerLast(Integer);
  • 头部取出元素
1
q.pollFirst(Integer);
  • 尾部取出元素
1
q.pollLast(Integer);
  • 头部观察元素
1
q.peekFirst(Integer);
  • 尾部观察元素
1
q.peekLast(Integer);

④Stack

Javad堆栈Stack类 已经过时，Java官方推荐使用Deque替代Stack使用

Deque堆栈操作方法：push()、pop()、peek()。

  • 插入元素
1
st.push(Integer);
  • 观察元素
1
st.peek();
  • 取出元素
1
st.pop();

⑤Set

HashSet

HashSet是基于散列表实现的，它不保证元素的顺序。

  • 初始化
1
Set<Integer>s = new HashSet<>();
TreeSet

TreeSet是基于红黑树实现的，它可以保证元素处于有序状态（默认升序）。

若要改为降序：

1
Set<Integer>s = new TreeSet<>((x,y)->{return y-x;});
  • 返回元素个数
1
s.size();
  • 插入元素
1
s.add(Integer);
  • 判断元素是否存在
1
s.contains(Integer);
  • 遍历
1
for(Integer x : s){}

⑥Map

HashMap
  • 初始化
1
Map<Integer,Integer>mp = new HashMap<>();
TreeMap
  • 初始化
1
TreeMap<Key, Value> numbers = new TreeMap<>((x,y)->{return y-x;});
  • 返回元素个数
1
mp.size();
  • 键值对插入
1
mp.put(key,val);

对Map集合中的同一键值key重复赋值会覆盖之前的结果。

  • 判断键是否存在（不存在的话会是null，不能之间加）
1
mp.containKey(key);
1
2
3
4
5
6
7
8
9
10
for(int i = 0;i < s.length(); i++)
{
    if(mp.containsKey(ch[i])){
        int t = mp.get(ch[i]) + 1;
        mp.put(ch[i],t);
        if(t > mx)mx = t;
    }else{
        mp.put(ch[i],1);
    }
}
  • 获取键值
1
mp.get(key);
  • 替换
1
2
3
replace(key, value)-用key新的替换指定映射的值value

replace(key, old, new) -仅当旧值已与指定键关联时，才用新值替换旧值

遍历方法：

  • 按键值遍历
1
mp.forEach((key,val)->{cout.println(key+" "+val);});
  • 按键遍历
1
2
for(char c : mp.keySet()){
 }
  • 按值遍历
1
2
for(int c : mp.values()){
}

特别的

  • 返回最小的大于或等于指定Key的Key，如果没有，则返回null
1
mp.ceilingKey();
  • 返回最大的小于等于指定Key的Key
1
mp.floorKey();

自定义数据结构

①并查集

例题：P3367 【模板】并查集 

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.lang.reflect.Member;
import java.util.Scanner;

public class Main {
    public static class DSU {
        int[] fa, siz;

        void init(int n) {
            fa = new int[n + 10];
            siz = new int[n + 10];
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
                siz[i] = 1;
            }
        }

        int find(int x) {
            if (fa[x] != x) fa[x] = find(fa[x]);
            return fa[x];
        }

        boolean same(int x, int y) {
            return find(x) == find(y);
        }

        void merge(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;
            siz[x] += siz[y];
            fa[y] = x;
        }

        int size(int x) {
            return siz[find(x)];
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner cin = new Scanner(System.in);
        BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
        int n, m;
        n = cin.nextInt();
        m = cin.nextInt();
        DSU d = new DSU();
        d.init(n);
        for(int i = 1;i <= m; i++){
            int op,x,y;
            op =  cin.nextInt();
            x = cin.nextInt();
            y = cin.nextInt();
            if(op==1){
                d.merge(x,y);
            }else{
                cout.write(d.same(x,y)?"Y\n":"N\n");
            }
        }
        cout.close();
    }
}

②树状数组

例题：P3374 【模板】树状数组 1 

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import javax.xml.transform.Templates;
import java.awt.event.MouseEvent;
import java.io.*;
import java.util.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    static int N = 500010;
    static int[] a = new int[N];
    static public class BIT{
        long []c = new long[N];
        int size;
        void resize(int s){size = s;}
        void init(){
            for(int i = 0;i <= N; i++)
                c[i] = 0;
        }
        long quary(int x){//1...x
            assert(x <= size);
            long s = 0;
            for(;x != 0;x -= x & (-x)){
                s += c[x];
            }
            return s;
        }

        void modify(int x,long s){//a[x] += s
            assert(x != 0);
            for(;x <= size; x += x & (-x)){
                c[x] += s;
            }
        }
    }
    public static void main(String[] args) throws Exception {

        int n,m;
        n = cin(); m = cin();
        BIT tr = new BIT();
        tr.resize(n+1);
        for(int i = 1;i <= n; i++){
            a[i] = cin();
            tr.modify(i,a[i]);
        }
        for(int i = 1;i <= m;i++)
        {
            int op; op = cin();
            if(op == 1){
                int x,k;
                x = cin();k = cin();
                tr.modify(x,k);
            }else{
                int x,y;
                x = cin();y = cin();
                cout.println(tr.quary(y)-tr.quary(x-1));
            }
        }


        cout.flush();
    }

    public static int cin() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}

③LCA

P3379 【模板】最近公共祖先（LCA) 

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int N = 1000001;
	static int LOGN = 20;
	static int n, m, root;
	static int[] dep = new int[N];
	static int[][] fa = new int[N][LOGN + 5];
	static Scanner cin = new Scanner(System.in);
	static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	static int[] head, next, ends;
	static int tot = 0;

	public static void add(int u, int v) {
		ends[tot] = v;
		next[tot] = head[u];
		head[u] = tot++;
	}

	public static void dfs(int u, int from) {
		dep[u] = dep[from] + 1;
		for (int i = head[u]; i != -1; i = next[i]) {
			int v = ends[i];
			if (v == from)
				continue;
			fa[v][0] = u;
			dfs(v, u);
		}
	}

	public static void lca_init() {
		for (int j = 1; j <= LOGN; j++)
			for (int i = 1; i <= n; i++)
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
	}

	public static int lca_query(int u, int v) {
		if (dep[u] < dep[v]) {
			int t = u;
			u = v;
			v = t;
		}
		int d = dep[u] - dep[v];
		for (int j = LOGN; j >= 0; j--)
			if ((d & (1 << j)) != 0)
				u = fa[u][j];

		if (u == v)
			return u;
		for (int j = LOGN; j >= 0; j--)
			if (fa[u][j] != fa[v][j]) {
				u = fa[u][j];
				v = fa[v][j];
			}
		return fa[u][0];
	}

	public static void main(String[] args) throws Exception {
		n = cin.nextInt();
		m = cin.nextInt();
		root = cin.nextInt();
		head = new int[N * 2 + 1];
		next = new int[N * 2 + 1];
		ends = new int[N * 2 + 1];
		Arrays.fill(head, -1);
		for (int i = 1; i < n; i++) {
			int u, v;
			u = cin.nextInt();
			v = cin.nextInt();
			add(u, v);
			add(v, u);
		}

		dfs(root, 0);
		lca_init();

		while (m-- > 0) {
			int u, v;
			u = cin.nextInt();
			v = cin.nextInt();
			cout.println(lca_query(u, v));
		}

		cout.close();
	}
}

4.DP

背包

1.01背包

1
2
3
4
for(int i = 1; i <= n; i++)
    for(int j = m; j >= v[i]; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

2.完全背包

1
2
3
4
for(int i = 1; i <= n; i++)
    for(int j = v[i]; j <= m; j++)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

3.多重背包()

1
2
3
4
5
for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++)
        for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

4.分组背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 110;
int n, m;
int f[N], w[N][N], v[N][N], s[N];

void solve()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)   
    {
        cin>>s[i];
        for(int j = 0; j < s[i]; j++)
            cin>>v[i][j]>>w[i][j];
    }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k < s[i]; k++)
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout<<f[m];
}

LCS

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
    if(a[i] == b[j])
        f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}

LIS

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= n; i++) 
{
    f[i] = 1;
    for(int j = 1; j < i; j++)
        if(a[i] > a[j])
            f[i] = max(f[i], f[j] + 1);
}
ans = f[1];
for(int i = 1; i <= n;i++)
    ans = max(ans, f[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int len = 0;
for (int i = 0; i < n; i++)
{
    int l = 0, r = len;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (a[i] > q[mid])  l=mid;
        else r = mid-1;
    }
    len = max(len, r + 1);
    q[r + 1] = a[i];
}
cout << len << endl;

  • Title: java模板【蓝桥杯向】
  • Author: Nannan
  • Created at : 2024-03-30 20:54:00
  • Updated at : 2024-09-30 21:01:40
  • Link: https://redefine.ohevan.com/2024/03/30/java模板/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
java模板【蓝桥杯向】
  1. nannan的板子
    1. 代码片段1
    2. 代码片段2
    3. 排序
      1. 自定义结构体排序
      2. Arrays.sort
      3. Collections.sort
    4. 浮点数保留2位小数
    5. 用Scanner读入Char
    6. 1.数学
      1. 任意进制转换
      2. 快速幂
      3. gcd
      4. 质因数分解
      5. 分解因数
      6. 线性筛
      7. 组合数()
      8. 对于互质的两个数a和b，其不能组成的最大整数为
    7. 2.图论
      1. BFS
      2. 链式前向星存图
      3. dijkatra
      4. Floyd
    8. 3. 数据结构
      1. java自带数据结构
        1. ①List
          1. ArrayList(推荐)
        2. ②Queue
        3. ③PriorityQueue
        4. ④Deque
        6. ④Stack
        7. ⑤Set
          1. HashSet
          2. TreeSet
        8. ⑥Map
          1. HashMap
          2. TreeMap
      2. 自定义数据结构
        1. ①并查集
        2. ②树状数组
        3. ③LCA
    9. 4.DP
      1. 背包
        1. 1.01背包
        2. 2.完全背包
        3. 3.多重背包()
        4. 4.分组背包
      2. LCS
      3. LIS