蓝桥杯考前复习二

1.快速幂

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

2.Java日期类

日期问题暂更

3.日期问题模板

考前更新

4.状态机DP

1.松散子序列 - 蓝桥云课 (lanqiao.cn)

import java.util.Scanner;
 
public class 松散子序列 {
    static int N=1000010;
    static int[][]f=new int[N][2];
 
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s = sc.next();
        int n=s.length();
        s=' '+s;
 
        for (int i = 1; i <=n ; i++) {
            f[i][1]=f[i-1][0]+s.charAt(i)-96;
            f[i][0]=Math.max(f[i-1][0],f[i-1][1]);
        }
 
        System.out.println(Math.max(f[n][0],f[n][1]));
 
    }
}

5.多重背包

1371. 货币系统 - AcWing题库

import java.util.Scanner;
 
public class Main {
	
	//f[i][j]=f[i-1][j]+f[i-1][j-v[i]]+f[i-1][j-2*v[i]]+...
//f[i][j-v[i]=f[i-1][j-v[i]]
	
	static int N = 30, M = 10010;
	static int n, m;
	static long[][] f = new long[N][M];
	static long[] v = new long[N];
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			v[i] = sc.nextLong();
		}
 
		for (int i = 0; i <= n; i++)
			f[i][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
                f[i][j]=f[i-1][j];
                if(j>=v[i]) {
                	f[i][j]+=f[i][(int) (j-v[i])];
                }
			}
		}
		
		System.out.println(f[n][m]);
 
	}
}

重点掌握多重背包的优化；

6.Floyd算法

 
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] = min(d[i][j], d[i][k] + d[k][j]);
}

7.区间合并

给定 n 个区间 [li,ri]]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
	static int N=100010;
     static Node[]A=new Node[N];
	public static void main(String[] args) {
 
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		for(int i=0;i<n;i++) {
			int l=sc.nextInt();
			int r=sc.nextInt();
			A[i]=new Node(l,r);
		}
		
		Arrays.sort(A,0,n);
		
		int start=A[0].l,end=A[0].r;
		int res=1;
		for(int i=1;i<n;i++) {
	      if(A[i].l<=end) {
	    	  end=Math.max(end, A[i].r);
	      }else {
	    	  res++;
	    	  start=A[i].l;
	    	  end=A[i].r;
	    	  
	      }
		}
		
		System.out.println(res);
		
		
		
		
	}
	
	
	static class Node implements Comparable<Node>{
		int l;
		int r;
		
		public Node(int l, int r) {
			super();
			this.l = l;
			this.r = r;
		}
 
		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return this.l-o.l;
		}
	}
 
}

 8.优先队列贪心问题

1.最大开支 - 蓝桥云课 (lanqiao.cn)

 
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class 最大开支 {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
 
		int n = sc.nextInt();
		int m = sc.nextInt();
		long sum = 0;
		for (int i = 0; i < m; i++) {
			int k = sc.nextInt();
			int b = sc.nextInt();
			if (k + b < 0)
				continue;
			pq.offer(new Node(k, b, 1, k+b));
		}
 
		
		for (int i = 1; i <= n; i++) {
			if (pq.peek().c > 0) {
				Node t = pq.poll();
				sum += t.c;
 
				int c = 2 * t.k * t.x + t.k + t.b;
				int x = t.x + 1;
				if (t.c > 0) {
					pq.offer(new Node(t.k, t.b, x, c));
				}
 
			}
 
			else {
				break;
			}
 
		}
		System.out.println(sum);
 
	}
 
	static class Node implements Comparable<Node> {
		int k;
		int b;
		int x;
		int c;
 
		public Node(int k, int b, int x, int c) {
			super();
			this.k = k;
			this.b = b;
			this.x = x;
			this.c = c;
		}
 
		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return o.c - this.c;
		}
	}
 
}

9.路径

3.路径 - 蓝桥云课 (lanqiao.cn)

 
 
import java.util.Arrays;
 
public class 路径 {
	static int N = 3000,n,m,k,INF = 0x3f3f3f3f;
	static int[][] g = new int[N][N];
	static int[] dist = new int[N];
	static boolean[] st = new boolean[N];
 
	public static void main(String[] args) {
 
		for (int i = 1; i <= 2021; i++) {
			for (int j = 1; j <= 2021; j++) {
				if (i == j)
					g[i][j] = 0;
				else if (Math.abs(i - j) > 21)
					g[i][j] = INF;
				else if (Math.abs(i - j) <= 21)
					g[i][j] = lcm(i, j);
			}
		}
		
		System.out.println(dijkstra());
 
	}
 
	public static int dijkstra() {
        n=2021;
		Arrays.fill(dist, INF);
		dist[1] = 0;
 
		for (int i = 0; i <n; i++) {
 
			int t = -1;
 
			for (int j = 1; j <=n; j++) {
				if (!st[j] && ((t == -1) || dist[j] < dist[t])) {
					t = j;
				}
			}
			st[t] = true;
 
			for (int j = 1; j <=n; j++) {
				dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
			}
 
		}
		
		if(dist[n]==INF)return -1;
		else return dist[n];
 
	}
 
	public static int gcd(int a, int b) {
		return b != 0 ? gcd(b, a % b):a;
	}
 
	public static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
 
}

10.双指针

1.完全二叉树的权值 - 蓝桥云课 (lanqiao.cn)

import java.util.Scanner;
 
public class 完全二叉树的权值 {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = sc.nextInt();
		}
		int max = Integer.MIN_VALUE;
		int index = 0;
 
		for (int k = 1, i = 1; i <= n; i *= 2, k++) {
			long sum = 0;
			for (int j = i; j < i+Math.pow(2, k - 1)&&j<=n; j++) {
				sum += a[j];
			}
 
			if (sum > max) {
				max=(int) sum;
				index = k;
			}
 
		}
		System.out.println(index);
 
	}
}