【蓝桥杯算法模板题--蓝桥题库Java】

PDF下载地址：点击即可

算法模板

1 排序（ArrayList，sort）

题目描述

给定一个长度为 N 的数组 A，请你先从小到大输出它的每个元素，再从大到小输出它的每个元素。

输入描述

第一行包含一个整数 N。

第二行包含 N 个整数 a1,…,an，表示数组 A 的元素。

1≤N≤5×10^5，−109≤ai≤10^9。

输出描述

输出共两行，每行包含 N 个整数，表示答案。

输入输出样例

示例 1

输入

5
1 3 2 6 5

输出

1 2 3 5 6
6 5 3 2 1

运行限制

• 最大运行时间：3s
• 最大运行内存: 128M

难度: 简单 标签: sort

import java.util.Scanner;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int len = scan.nextInt();
        ArrayList<Integer> num1 = new ArrayList<>();
        for(int i = 0; i<len;i++){
            num1.add(scan.nextInt());
        }
        //由小到大
        num1.sort((o1,o2)->o1-o2);
        for(int i = 0;i<len;i++) {
            System.out.print(num1.get(i)+" ");
        }
        System.out.println();
        //由大到小
        num1.sort((o1,o2)->o2-o1);
        for(int i = 0;i<len;i++) {
            System.out.print(num1.get(i)+" ");
        }
        scan.close();
    }
}

import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int a=scan.nextInt();
        int[] b = new int[a];
        for(int i =0;i<b.length;i++){
            b[i]=scan.nextInt();
        }
        Arrays.sort(b);
        for(int i =0;i<b.length;i++){
            System.out.print(b[i]+" ");

        }
        System.out.println("\t");

        for(int i=b.length-1;i>=0;i--){
            System.out.print(b[i]+" ");
        }
        scan.close();
    }
}

2 小明的彩灯（差分）

算法介绍：(2条消息) 差分算法介绍_笑看江湖路6的博客-CSDN博客_差分算法

输入输出样例

示例 1

输入

5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100

输出

0 5 5 6 10

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

难度: 简单 标签: 差分

import java.util.Scanner;
import java.util.*;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
  static int N = (int)(5*10e5+10);
  static long[] a=new long[N];
  static long[] b=new long[N]; 
    public static void main(String[] args) throws IOException{
        //在此输入您的代码...
        String[] str = cin.readLine().split(" ");
        int n=Integer.parseInt(str[0]);
        int q=Integer.parseInt(str[1]);
        str = cin.readLine().split(" ");
        a[0] = 0;
        for(int i=1;i<=n;i++){
            a[i]=Long.parseLong(str[i-1]);
            //差分
            b[i]=a[i]-a[i-1];
        }
        for(int i=0;i<q;i++) {
            str = cin.readLine().split(" ");
            int l=Integer.parseInt(str[0]);
            int r=Integer.parseInt(str[1]);
            long c=Long.parseLong(str[2]);
            //差分算法核心：开头＋，结尾+1后减
            b[l]+=c;
            if(r<n)b[r+1]-=c;
        }
        for(int j=1;j<=n;j++) a[j]=a[j-1]+b[j];
        for(int i=1;i<=n;i++){
            if(a[i]<0)a[i]=0;
            cout.write(a[i]+" ");
        }
        cout.flush();
        cin.close();
        cout.close();
    }
}

3 绝世武功（二阶差分算法）

算法介绍：(2条消息) 二阶差分（注意数据范围）_AC-PEACE的博客-CSDN博客

输入输出样例

示例 1

输入

6 2
1 5 2 10
2 4 1 1

输出

33

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

难度: 简单 标签: 二阶差分

import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
  static int N = (int)(1e7+10);
  static long[] c = new long[N];
  static long sum=0;
    public static void main(String[] args) throws IOException {
        String[] str = cin.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        for(int i=0;i<m;i++){
          str = cin.readLine().split(" ");
          int l = Integer.parseInt(str[0]);
          int r = Integer.parseInt(str[1]);
          int s = Integer.parseInt(str[2]);
          int e = Integer.parseInt(str[3]);
          //公差
          int d = (int)(e-s)/(r-l);
          //二阶差分核心公式
          c[l] +=s;
          c[l+1] += d-s;
          c[r+1] -= d+e;
          c[r+2] += e;
        }
        //求一阶的变化
        for(int i=1;i<=n;i++){
          c[i] += c[i-1];
        }
        //求原始的变化
        for(int i=1;i<=n;i++){
          c[i] += c[i-1];
          sum += c[i];
        }
        cout.write(sum+"");
        cout.flush();
    }
}

4 走迷宫（动态规划dp,bfs广度优先搜索）

输入输出样例

示例 1

输入

5 5 
1 0 1 1 0
1 1 0 1 1 
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5 

输出

8

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

难度: 简单 标签: bfs

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static class Node {
        int x;
        int y;
        int path;
        public Node(int x, int y, int path) {
            this.x = x;
            this.y = y;
            //当前路径数
            this.path = path;
        }
    }
    //方向数组
    static int[] r = {-1,1,0,0};
    static int[] c = {0,0,-1,1};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[][] graph = new int[n][m];
        int[][] visited = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                graph[i][j] = scan.nextInt();
            }
        }
        int x1 = scan.nextInt()-1;
        int y1 = scan.nextInt()-1;
        int x2 = scan.nextInt()-1;
        int y2 = scan.nextInt()-1;
        LinkedList<Node> queue = new LinkedList<>();
        //标记走过的位置
        visited[x1][y1] = 1;
        queue.add(new Node(x1, y1, 0));
        while(!queue.isEmpty()) {
            Node t = queue.poll();
            int x = t.x;
            int y = t.y;
            int path = t.path;
            if(x == x2 && y == y2) {//出口
                System.out.println(path);
                return;
            }
            for(int i = 0; i < 4; i++) {
                int x3 = x + r[i];
                int y3 = y + c[i];
                if(x3 >=0 && x3 <= n-1 && y3 >=0 && y3 <= m-1 && graph[x3][y3] == 1&& visited[x3][y3] != 1) {
                    //每层扩展就加1
                    queue.add(new Node(x3, y3, path + 1));
                    visited[x3][y3] = 1; 
//                    System.out.println(path);
                }
            }
        }
    System.out.println(-1);
    }
}

5 小明的背包1（dp，01背包）

输入输出样例

示例 1

输入

5 20
1 6
2 5
3 8
5 15
3 3 

输出

37

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

难度: 简单 标签: dp, 背包, 01背包

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int N = scan.nextInt();
        int V = scan.nextInt();
        int[] vn = new int[N+1];
        int[] val = new int[N+1];
        int[] dp = new int[V+1];
        for(int i=1;i<=N;i++){
          vn[i] = scan.nextInt();
          val[i] = scan.nextInt();
        }
        scan.close();
        for(int i = 1;i<=N;i++){
            //01背包
          for(int j=V;j>=vn[i];j--){
              //dp算法核心
            dp[j] = Math.max(dp[j],(dp[j-vn[i]]+val[i]));
          }
        }
        System.out.println(dp[V]);
    }
}

6 小明背包2（dp，完全背包）

输入输出样例

示例 1

输入

5 20
1 6
2 5
3 8
5 15
3 3 

输出

120

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

难度: 简单 标签: DP, 背包, 完全背包

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        String[] str = scan.nextLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int V = Integer.parseInt(str[1]);
        int[] w = new int[N+1];
        int[] v = new int[N+1];
        int[] dp = new int[V+1];
        for(int i=1;i<=N;i++){
          str = scan.nextLine().split(" ");
          w[i] = Integer.parseInt(str[0]);
          v[i] = Integer.parseInt(str[1]);
        }
        for(int i=1;i<=N;i++ ){
            //完全背包
          for(int j=w[i];j<=V;j++){
            dp[j] = Math.max(dp[j],(dp[j-w[i]]+v[i]));
          }
        }
        System.out.println(dp[V]);
        scan.close();
    }
}

7 小明的衣服（哈夫曼树）

输入输出样例

示例 1

输入

5
5 1 3 2 1 

输出

25

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

难度: 简单 标签: 哈夫曼树, 贪心

import java.util.Scanner;
import java.util.PriorityQueue;
// 1:无需package
// 2: 类名必须Main, 不可修改
/*
贪心的最优策略： 
1、每次染一件路费最贵的。 
2、最贵的只染一次（只运送一次），其次2次，以此类推，最小的要一直运送即需要加n次。
3、优先队列，每次选最小的两个数的和累加，并把这个和再加入队列中！
*/
public class Main {
  static long sum=0;
  //最优队列，也称哈夫曼树
  static PriorityQueue<Long> a = new PriorityQueue<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int N = scan.nextInt();
        for(int i=0;i<N;i++){
          a.add(scan.nextLong());
        }
        while(a.size()!=1){
          Long val1 = a.poll();
          Long val2 = a.poll();
          sum+=val1+val2;
          a.add(val1+val2);
        }
        System.out.println(sum+"");
        scan.close();
    }
}

8 百亿富翁(单调栈)

输入输出样例

示例 1

输入

5
3 1 2 5 4 

输出

-1 1 1 -1 4
4 3 4 -1 -1

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

难度: 简单 标签: 单调栈

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int N = scan.nextInt();
        int[] h = new int[N];
        int[] l = new int[N];
        int[] r = new int[N];
        // String[] str = scan.nextLine().split(" ");
        // for(int i=0;i<N;i++){
        //   h[i] = Integer.parseInt(str[i]);
        // }
         for(int i=0;i<N;i++){
          h[i] = scan.nextInt();
        }
        //判断左边第一个比自己高的编号
        for(int i=0;i<N;i++){
          if(i==0) {
            l[i] = -1;
          }
            //从i-1开始，到0结束
          for(int j=i-1;j>=0;j--){
            if(h[j]>h[i]){
              l[i] = j+1;
              break;
            }else{
              l[i] = -1;
            }
          }
          System.out.print(l[i]+" ");
        }
        System.out.println();
		//判断右边第一个比自己高的编号
        for(int i=0;i<N;i++){
          if(i==N-1){
            r[i]=-1;
          }
          for(int j=i+1;j<N;j++){
            if(h[j]>h[i]){
              r[i] = j+1;
              break;
            }else{
              r[i]=-1;
            }
          }
          System.out.print(r[i]+" ");
        }
        scan.close();
    }
}

9 排个序（冒泡排序）

输入输出样例

示例 1

输入

3 2
3 2 1
1 2

输出

YES

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

难度: 简单 标签: 冒泡排序

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * 思路：两个数组，用第二个数组里面的数能否将第一个数排好序,给的数据是从1开始的
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //输入数据
        int n = scan.nextInt();
        int p = scan.nextInt();
        int[] arr = new int[n+1];
        for (int i=1; i<=n; i++) {
            arr[i] = scan.nextInt();
        }
        //存放排序数组的
        ArrayList arrayList = new ArrayList();
        for (int i=0; i<p; i++) {
            arrayList.add(scan.nextInt() );
        }
        //根据给的数组下标。排序
        for (int i=1; i < n; i++) {
            int t=0;
            for (int j=1; j <= n-i; j++) {
                if (arrayList.contains(j) ) {
                    if (arr[j] > arr[j+1]) {
                        t = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = t;
                    }
                }
            }
        }
        //判断是否排好序了
        boolean flag = true;
        for (int i=1; i < n; i++) {
            if (arr[i] > arr[i+1]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

10 解立方根（Math.cbrt(x)）(BigDecimal)

输入输出样例

示例 1

输入

3
0
1
8

输出

0.000
1.000
2.000

运行限制

• 最大运行时间：5s
• 最大运行内存: 128M

import java.util.*;
import java.math.BigDecimal;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner (System.in);
      int n = sc.nextInt();
      for(int i = 0; i<n; i++){
        int a = sc.nextInt();
        System.out.printf("%.3f",Math.cbrt(a));
        System.out.println();
      }
    }
}

11 回文判定（尺取法，双指针）

输入输出样例

示例 1

输入

abcba

输出

Y

示例 2

输入

abcbb

输出

N

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        String str = scan.nextLine();
        scan.close();
        for(int i = 0;i<str.length()/2;i++){
          if(str.charAt(i) != str.charAt(str.length()-1-i)){
            System.out.println("N");
            return;
          }
        }
        System.out.println("Y");
    }
}

12 最长公共子序列（dp，LCS）

输入输出样例

示例 1

输入

5 6
1 2 3 4 5
2 3 2 1 4 5

输出

4

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static int N = 1000+5;
  static int[][] lcs = new int[N][N];
  static int[] a;
  static int[] b;
  static void LCS(int n,int m){
    for(int i = 0;i<n;i++) lcs[i][0] = 0;
    for(int i = 0;i<n;i++) lcs[0][i] = 0;
      for(int i =1;i<=n;i++){
          for(int j= 1;j<=m;j++){
              if(a[i]==b[j]) {
                  lcs[i][j] = lcs[i-1][j-1]+1;
              }else if(a[i]!=b[j]){
                  if(lcs[i-1][j]>lcs[i][j-1]){
                      lcs[i][j]=lcs[i-1][j];
                  }else{
                      lcs[i][j]=lcs[i][j-1];
                  }
                  //lcs[i][j] = Math.max(lcs[i-1][j],lcs[i][j-1]);
              }
          }
      }
  }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        int m = scan.nextInt();
        a = new int[n+1];
        b = new int[m+1];
        for(int i = 1;i<=n;i++){
          a[i] = scan.nextInt();
        }
        for(int i = 1;i<=m;i++){
          b[i] = scan.nextInt();
        }
        LCS(n,m);
        System.out.println(lcs[n][m]);

        scan.close();
    }
}

13 蓝桥骑士（dp，LIS）

输入输出样例

示例 1

输入

6
1 4 2 2 5 6

输出

4

运行限制

难度: 中等 标签: dp, LIS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int)in.nval;
        int[] nums = new int[n];
        for(int i=0; i<n; i++){
          in.nextToken();
          nums[i] = (int)in.nval;
        }
        System.out.print(LengthOfLIS2(nums));
    }

    /*
     * 动态规划算法
     * 时间复杂度：O(n²)
     * 空间复杂度：O(n)
     */
    public static int LengthOfLIS(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for(int i=1; i<nums.length; ++i) {
            dp[i] = 1;
            for(int j=0; j<i; ++j) {
                if(nums[i]>nums[j]) {
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }

    /*
     * 二分法+贪心法
     * 时间复杂度：O(n*log(n) )
     * 空间复杂度：O(n)
     */
    public static int LengthOfLIS2(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        //tails数组是以当前长度连续子序列的最小末尾元素
        //如tail[0]是求长度为1的连续子序列时的最小末尾元素
        //例：在 1 6 4中 tail[0]=1 tail[1]=4 没有tail[2] 因为无法到达长度为3的连续子序列
        int tails[] = new int[nums.length];
        //注意：tails一定是递增的 因为看题解那个动画 我们最开始的那个元素一定找的是该数组里最小的 不然如果不是最小 由于我们需要连续 后面的数一定会更大（这样不好的原因是 数越小 我们找到一个比该数大的数的几率肯定会更大）
        int res=0;
        for(int num : nums) {
            //每个元素开始遍历 看能否插入到之前的tails数组的位置 如果能 是插到哪里
            int i=0, j=res;
            while(i<j) {
                int m = (i+j)/2;
                if(tails[m] < num) {
                    i = m+1;
                }else {
                    j = m;
                }
            }
             //如果没有到达j==res这个条件 就说明tail数组里只有部分比这个num要小 那么就把num插入到tail数组合适的位置即可 但是由于这样的子序列长度肯定是没有res长的 因此res不需要更新
            tails[i] = num;
            //j==res 说明目前tail数组的元素都比当前的num要小 因此最长子序列的长度可以增加了 
            if(j == res) {
                res++;
            }
        }
        return res;
    }
}

14 小明背包3（dp，多重背包）

输入输出样例

示例 1

输入

3 30
1 2 3
4 5 6
7 8 9

输出

39

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int N,V;
    static int[] wi;
    static int[] vi;
    static int[] si;
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        String[] first = cin.readLine().split(" ");
        N = Integer.parseInt(first[0]);
        V = Integer.parseInt(first[1]);
        wi = new int[N+1];
        vi = new int[N+1];
        si = new int[N+1];
        int[] dp = new int[V+1];
        for(int i = 1; i<= N; i++) {
            first = cin.readLine().split(" ");
            wi[i] = Integer.parseInt(first[0]);
            vi[i] = Integer.parseInt(first[1]);
            si[i] = Integer.parseInt(first[2]);
        }
        
        for(int i=1;i<=N;i++) {
            for(int j=V;j>=0;j--) {
                for(int k=0;k<=Math.min(si[i],j/wi[i]);k++) {
                    dp[j] = Math.max(dp[j], dp[j-k*wi[i]]+k*vi[i]);
                }
            }
        }
        System.out.println(dp[V]);
    }

}

15 蓝桥幼儿园（并查集）

输入输出样例

示例 1

输入

5 5 
2 1 2
1 1 3
2 1 3
1 2 3 
2 1 2

输出

NO
YES
YES

运行限制

• 最大运行时间：5s
• 最大运行内存: 256M

import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static BufferedReader buffin = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter buffout = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N = (int)(2e5+10);
    static int[] p = new int[N];
    //初始化
    public static void pInit(){
      for(int i=0;i<N;i++){
          p[i] = i;
        }
    }
    //查询
    public static int find(int x){
      if (p[x]!=x){
        p[x] = find(p[x]);
       }
       return p[x];
    }
    public static void main(String[] args) throws IOException{
        // pInit();
        String[] str = buffin.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++){
          p[i] = i;
        }
        while(m-->0){
          int op,x,y;
          str = buffin.readLine().split(" ");
          op = Integer.parseInt(str[0]);
          x = Integer.parseInt(str[1]);
          y = Integer.parseInt(str[2]);
          if(op==1){//合并
            p[find(x)] = find(y);
          } 
          else{//查询
            if(find(x) == find(y)){
              buffout.write("YES"+"\n");
            }else{
              buffout.write("NO"+"\n");
            }
          }
        }
        buffout.flush();
        
    }
    
}

16 蓝桥侦探（种类并查集）

输入输出样例

示例 1

输入

4 5 
1 2
1 3 
2 3 
3 4
1 4

输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
  static int N = (int)(5*10e5+10);
  static int[] p = new int[2*N];
  static int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
  }
  static void union(int x,int y){
    int fx = find(x),fy=find(y);
    p[fx] = fy;
  }
    public static void main(String[] args) throws IOException {
        //在此输入您的代码...
        String[] str = cin.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        for(int i = 0; i<2*n; i++){
          p[i] = i;
        }
        int x,y;
        while(m-->0){
          str = cin.readLine().split(" ");
          x = Integer.parseInt(str[0]);
          y = Integer.parseInt(str[1]);
          if(find(x)!=find(y)){
            union(x+n,y);
            union(x,y+n);
          }else{
            cout.write(x+"");
            break;
          }
        }
        cout.flush();
    }
}

17 期望DP

输入输出样例

示例 1

输入

2
1
12

输出

1.00
37.24

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
  static int N = (int)1e3+10;
  static double[] dp = new double[N];
    public static void main(String[] args)throws IOException {
        //在此输入您的代码...
        int t = Integer.parseInt(cin.readLine());
        for(int j=t;j>0;j--){
          int n = Integer.parseInt(cin.readLine());
          dp[n] = 0;
          for(int i=n-1; i>=0; i--){
            dp[i] = dp[i+1] + 1.0 * n/(n-i);
          }
          System.out.printf("%.2f\n",dp[0]);
        }
    }
}

18 最大公约数&最小公倍数（GCD&LCM）

输入输出样例

示例 1

输入

5
2 4
3 7
5 10
6 8
7 9

输出

2
1
5
2
1

运行限制

• 最大运行时间：2s
• 最大运行内存: 128M

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        //在此输入您的代码...
        int N = Integer.parseInt(cin.readLine());
        for(int i = 0; i < N; i++){
          String[] str = cin.readLine().split(" ");
          int A = Integer.parseInt(str[0]);
          int B = Integer.parseInt(str[1]);
          System.out.println(getGCD(A,B));
        }
    }
    static int getGCD(int n,int m){
      if(n==0) return m;
      return getGCD(m%n,n);
    }
    //两个数的最小公倍数 等于 两数之积除以他们的最大公约数
	// lcm(a, b) = (a * b) / lcd(a, b)
 	static int getLCM(int a, int b) {
		return (a*b) / getGCD(a,b);
 	}
    
}

19 数的次幂（快速幂）

输入输出样例

示例 1

输入

3
2 3 7
4 5 6
5 2 9

输出

1
4
7

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        //在此输入您的代码...
        int T = Integer.parseInt(cin.readLine());
        
        for(int i = 0; i< T; i++){
          String[] str = cin.readLine().split(" ");
          long N = Long.parseLong(str[0]);
          long M = Long.parseLong(str[1]);
          long P = Long.parseLong(str[2]);
          long res=FastPow(N,M,P);
          System.out.println(res);
        }
        cin.close();
    }
    static long FastPow(long a,long b,long c){
        long res=1;
        while (b>0){
            if (b%2==1) res=res*a%c;
            a = a*a%c;
            b=b/2;
        }
        return res;
    }
}

20 快速幂

输入输出样例

示例

输入

2 10 9

输出

7

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.Scanner;
import java.math.BigInteger;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        long a = scan.nextLong();
        long d = scan.nextLong();
        long c = scan.nextLong();
        BigInteger b = BigInteger.valueOf(a);
        BigInteger p = BigInteger.valueOf(d);
        BigInteger k = BigInteger.valueOf(c);
        // public BigInteger modPow(BigInteger exponent, BigInteger m)
        // 返回一个 BigInteger，其值为 (this的exponent次方 mod m)。 与 pow 不同，此方法允许使用负指数。
        BigInteger bigInteger = b.modPow(p, k);//mod意为取模
        System.out.println(bigInteger);
        scan.close();
    }
}

21 ST线性表

问题描述

问题描述：小蓝有一个序列 a[1], a[2], …, a[n]。
　　给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a[i-k], a[i-k+1], …, a[i+k] 这 2k+1 个数中的最小值是多少？
当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。
输入格式
　　输入的第一行包含一整数 n。
　　第二行包含 n 个整数，分别表示 a[1], a[2], …, a[n]。
　　第三行包含一个整数 k 。
输出格式
　　输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。

样例输入

5
5 2 7 4 3
1

样例输出

2 2 2 3 3

评测用例规模与约定

对于 30% 的评测用例，1 <= n <= 1000，1 <= a[i] <= 1000。
　　对于 50% 的评测用例，1 <= n <= 10000，1 <= a[i] <= 10000。
　　对于所有评测用例，1 <= n <= 1000000，1 <= a[i] <= 1000000。

/**
	* 问题描述
	　　问题描述：小蓝有一个序列 a[1], a[2], …, a[n]。
	　　给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a[i-k], a[i-k+1], …, a[i+k] 这 2k+1 个数中的最小值是多少？
	当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。
	输入格式
	　　输入的第一行包含一整数 n。
	　　第二行包含 n 个整数，分别表示 a[1], a[2], …, a[n]。
	　　第三行包含一个整数 k 。
	输出格式
	　　输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。
	样例输入
	5
	5 2 7 4 3
	1
	样例输出
	2 2 2 3 3
	评测用例规模与约定
　　对于 30% 的评测用例，1 <= n <= 1000，1 <= a[i] <= 1000。
　　对于 50% 的评测用例，1 <= n <= 10000，1 <= a[i] <= 10000。
　　对于所有评测用例，1 <= n <= 1000000，1 <= a[i] <= 1000000。
 *
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;


public class Main {
	static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
	static int n,k,f;
	static int[] arr;
	static int[][] ST;
	static int N = (int)(1e3+10);
	static int[] dp = new int[N];
	public static void main(String[] args) throws IOException{
		n = Integer.parseInt(cin.readLine());
		f = (int) Math.ceil(Math.log(n) / Math.log(2));
		arr = new int[n];
		ST = new int[n][f];
		String[] str = cin.readLine().split(" ");
		for(int i=0; i<str.length;i++) {
			arr[i] = Integer.parseInt(str[i]);
		}
		k = Integer.parseInt(cin.readLine());
		
		init();
		
		for(int i=0;i<n;i++) {
			int begin = Math.max(i-k, 0);
			int end = i+k<n ? i+k : n-1;
			System.out.print(query(begin,end)+" ");
			
		}
	}
	//初始化
	static void init() {
		for(int i=0;i<n;i++) {
			ST[i][0]=arr[i];
		}
		for(int j=1;j<f;j++) {
			for(int i=0;i+(1<<j)<=n;i++) {
				ST[i][j] = Math.min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
			}
		}
	}
	//查询
	static int query(int l,int r) {
		int len = r - l + 1;
		int k = (int)(Math.log(len) / Math.log(2));
		return Math.min(ST[l][k], ST[r - (1 << k) + 1][k]);
	}

}

训练：

输入输出样例

示例 1

输入

5 3
5 3 2 4 1

输出

2
2
1

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
  static int[] temp;
    public static void main(String[] args) throws IOException{
      String[] str = cin.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        temp = new int[n+1];
        int[] a = new int[n+1];
        str = cin.readLine().split(" ");
        for(int i=1;i<=n;i++){
          a[i] = Integer.parseInt(str[i-1]);
        }
//求最小
        //hh为队头索引（最左边），tt为队尾索引（最右边）
        int hh=0,tt=-1;
        for(int i = 1;i<=n;i++){
          if(hh<=tt && temp[hh]<i-m+1){
            hh++;
          } 
          while(hh<=tt && a[temp[tt]]>=a[i]){
            tt--;
          } 
          tt++;
          temp[tt]=i;
          if(i>=m){
            cout.write(a[temp[hh]]+"\n");
          } 
        }

      cout.flush();
    }
}

22 区间最大值（ST表）

输入输出样例

示例 1

输入

5 5
1 2 3 4 5
1 1 
1 2 
1 3
3 4
2 5

输出

1
2
3
4
5

运行限制

• 最大运行时间：3s
• 最大运行内存: 512M

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
  static int N,Q,f;
  static int[] arr;
  static int[][] ST;
    public static void main(String[] args)throws IOException{
        //在此输入您的代码...
        String[] first = cin.readLine().split(" ");
        N = Integer.parseInt(first[0]);
        Q = Integer.parseInt(first[1]);
        arr = new int[N];
        f = (int) Math.ceil(Math.log(N) / Math.log(2));
        ST = new int[N][f];
        first = cin.readLine().split(" ");
        for(int i = 0; i < N; i++){
          arr[i] = Integer.parseInt(first[i]);
          
        }
        init();
        for(int i = 0; i < Q; i++){
          first = cin.readLine().split(" ");
          int L = Integer.parseInt(first[0]);
          int R = Integer.parseInt(first[1]);
          // if(L==R){
          //   System.out.println(arr[L]);
          // }else{
            System.out.println(query(L-1,R-1));
          // }

        }
    }
    static void init(){
      for(int i=0;i<N;i++){
        ST[i][0] = arr[i];
      }
      for(int j=1;j<f;j++){
        for(int i=0;i+(1<<j)<=N;i++){
          ST[i][j] = Math.max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
        }
      }
    }
    static int query(int l, int r){
      int len = r - l + 1;
      int k = (int)(Math.log(len) / Math.log(2));
      return Math.max(ST[l][k],ST[r-(1<<k)+1][k]);
    }
}

23 美丽的区间（尺取法）

输入输出样例

示例 1

输入

5 6
1 2 3 4 5

输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

总通过次数: 1016 | 总提交次数: 1226 | 通过率: 82.9%

难度: 简单 标签: 尺取法

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        int S = scan.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
          a[i] = scan.nextInt();
        }
        int sum=0;
        int k = 10*n;
        for(int i=0,j=0;i<n;i++){
          sum +=a[i];
          while((sum-a[j]>=S)&&j<n){
            sum = sum-a[j];
            j++;
              //k表示区间长度
            if(i-j+1<k) k = i-j+1;
              //或者 k = Math.min(k,i-j+1);
          }
        }
        if(k==10*n){
          //表示不存在美丽区间
          System.out.println("0");
        }else{
          System.out.println(k);
        }

        scan.close();
    }
}

24 三角形的面积

输入输出样例

示例 1

输入

2
0 1
1 0
1 1
0 0
1 1
2 2

输出

0.50
0.00

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 824 | 总提交次数: 1052 | 通过率: 78.3%

难度: 简单 标签: 计算几何基础

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int N = scan.nextInt();
        for(int i=0;i<N;i++){
          double x1 = scan.nextDouble();
          double y1 = scan.nextDouble();
          double x2 = scan.nextDouble();
          double y2 = scan.nextDouble();
          double x3 = scan.nextDouble();
          double y3 = scan.nextDouble();
          double S = Math.abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2);
          System.out.printf("%.2f",S/2);
          System.out.println();
        }
        scan.close();
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            double x1 = sc.nextDouble();
            double y1 = sc.nextDouble();
            double x2 = sc.nextDouble();
            double y2 = sc.nextDouble();
            double x3 = sc.nextDouble();
            double y3 = sc.nextDouble();
            point temp = new point(x2-x1,y2-y1);
            point temp1 = new point(x3-x1,y3-y1);
            double s = cross(temp,temp1);
            System.out.println(String.format("%.2f",s/2));

        }
    }
    private static double cross(point A,point B){
        return Math.abs(A.x*B.y - A.y*B.x);
    }
}
class point{
    double x;
    double y;
    public point(double a,double b){
        this.x = a;
        this.y = b;
    }


}

25 蓝桥公园（Floyd）

输入输出样例

示例 1

输入

3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3

输出

1
3
2

运行限制

总通过次数: 676 | 总提交次数: 863 | 通过率: 78.3%

难度: 简单 标签: Floyd

import java.util.Scanner;
import java.io.*;
//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
static long MaxValue = 0x3f3f3f3f3f3f3f3fL;
static void flody(long[][] matrix){
 for(int m = 0;m<matrix.length;m++){
   for(int i=0;i<matrix.length;i++){
     for(int j = 0;j<matrix.length;j++){
       if((matrix[i][m] + matrix[m][j]) < matrix[i][j])
         matrix[i][j] = matrix[i][m]+matrix[m][j];
         //matrix[i][j] = Math.min(matrix[i][j],matrix[i][m]+matrix[m][j]);
     }
   }
 }
}
 public static void main(String[] args) throws IOException{
     String[] str1 = cin.readLine().split(" ");
     int N = Integer.parseInt(str1[0]);
     int M = Integer.parseInt(str1[1]);
     int Q = Integer.parseInt(str1[2]);
     long[][] matrix = new long[N+1][N+1];
     //初始化邻接矩阵
     for(int i=0;i<=N;i++){
       for(int j=0;j<=N;j++){
         matrix[i][j] = MaxValue;
       }
     }

     //初始化边权值
     for(int i =0;i<M;i++){
       String[] str2 = cin.readLine().split(" ");
       int u = Integer.parseInt(str2[0]);
       int v = Integer.parseInt(str2[1]);
       long w = Integer.parseInt(str2[2]);
         //注意重复路径，取最小
       matrix[u][v] = Math.min(matrix[u][v],w);
       matrix[v][u] = Math.min(matrix[v][u],w);
     }
     //调用Floyd 算法计算最短路径
     flody(matrix);
     //找出最短路程
     for(int i=0;i<Q;i++){
       String[] str3 = cin.readLine().split(" ");
       int st = Integer.parseInt(str3[0]);
       int ed = Integer.parseInt(str3[1]);
       if(st!=ed){
         if(matrix[st][ed]==MaxValue){
           cout.write("-1"+"\n");
         }else{
             cout.write(matrix[st][ed]+"\n");
         }
      }else{
        cout.write("0"+"\n");
      }
    }
    cout.flush();
    cin.close();
    cout.close();
 }
}

26 递增序列

对于下面的 3030 行 5050 列的矩阵，请问总共有多少个递增序列？

VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

总通过次数: 9357 | 总提交次数: 11225 | 通过率: 83.4%

难度: 简单 标签: 填空题, 2019, 国赛

import java.util.*;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.setIn(Main.class.getResourceAsStream("inc.txt"));
	    Scanner sc = new Scanner(System.in);
	    char[][] data = new char[30][50];
	    for (int i = 0; i < 30; i++) {
	      data[i] = sc.nextLine().toCharArray();
	      System.out.print(data[i]);
	      System.out.println();
	    }
	    int ans = 0;
	    int dir[][] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}};// 右下，右上，左下，右，下
	    for (int i = 0; i < 30; i++) {
	      for (int j = 0; j < 50; j++) {///举例每个字符
	        for (int k = 0; k < 5; k++) {///五个方向
	          int x = i, y = j;
	          while (true) {
	            x += dir[k][0];
	            y += dir[k][1];
	            if (x < 0 || x >= 30 || y < 0 || y >= 50) break;//越界
	            if (data[x][y] > data[i][j]) ans++;///符合条件
	          }
	        }
	      }
	    }
	    System.out.println(ans);
	    sc.close();
	}

}

//52800

27 点和直线的关系

输入输出样例

示例 1

输入

3
0 1
1 0
1 1
0 0
1 1
2 2
0 0
0 1
1 0

输出

L
IN
R

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

总通过次数: 229 | 总提交次数: 242 | 通过率: 94.6%

难度: 简单 标签: 计算几何基础

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        //在此输入您的代码...
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i=0;i<T;i++) {
          double xa = sc.nextDouble();
          double ya = sc.nextDouble();
          double xb = sc.nextDouble();
          double yb = sc.nextDouble();
          double xc = sc.nextDouble();
          double yc = sc.nextDouble();
          Point temp = new Point(xb-xa,yb-ya);
          Point temp1 = new Point(xc-xb,yc-yb);
          double crossVal = cross(temp,temp1);
          System.out.println(crossVal==0?"IN":(crossVal>0 ? "L":"R"));
        }
        sc.close();
    }
    
    //叉积，为正时角度方向是逆时针，为负时角度方向为顺时针
    //同时，叉积的模也是两条向量为边组成平行四边形的面积
    static double cross(Point p1,Point p2){
      return p1.x*p2.y - p2.x*p1.y;
    }
}
class Point{
      double x;
      double y;
      Point (double a, double b){
        this.x = a;
        this.y = b;
      }
    }

28 LCIS(最大公共递增子序列)

输入输出样例

示例 1

输入

5 6
1 3 2 4 5
2 3 1 4 5 6

输出

3

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

总通过次数: 355 | 总提交次数: 409 | 通过率: 86.8%

难度: 简单 标签: dp, LCIS

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static int[] a;
  static int[] b;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //在此输入您的代码...
        int n = sc.nextInt();
        int m = sc.nextInt();
        a = new int[n+1];
        b = new int[m+1];
        for(int i=1;i<=n;i++){
          a[i] = sc.nextInt();
        }
        for(int i=1;i<=m;i++){
          b[i] = sc.nextInt();
        }
        int[][] dp = new int[n + 1][m + 1];// 表示a的前i个数到b以j为结尾的数的最长子序列
        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
            dp[i][j] = dp[i-1][j];
            if(a[i] == b[j]){//有相等的至少为1
              dp[i][j] = Math.max(dp[i][j],1);
                //判断是否时递增
                  for(int k=1;k<j;k++){
                    if(b[k] < b[j]){
                      dp[i][j] = Math.max(dp[i][j], dp[i-1][k]+1);
                    }
                  }
            }
          }
        }
        int max = 0;
        for(int col=1;col<=m;col++){
          max = Math.max(max,dp[n][col]);
        }
        System.out.println(max);
        sc.close();
    }
}