蓝桥杯考前复习二

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]);
}

原文地址：https://blog.csdn.net/m0_74302039/article/details/137057311

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！