蓝桥杯（Java）由简到难,助你得省一

2.归并排序AcWing 787. 归并排序AcWing 788. 逆序对的数量3.二分AcWing 789. 数的范围AcWing 503. 借教室（每日一题）AcWing 790. 数的三次方根4.高精度5.前缀和AcWing 795. 前缀和AcWing 796. 子矩阵的和AcWing 562. 壁画（每日一题）6.差分AcWing 797. 差分AcWing 798. 差分矩阵AcWin

qq_44469428

1819人浏览 · 2024-04-15 09:31:04

qq_44469428 · 2024-04-15 09:31:04 发布

1.基础算法

1.快速排序

AcWing 785. 快速排序

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N=(int) (5e6+10);
    static int[] p=new int [N];
    public static void main(String[] args) throws  IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int no=0;
        while(n--!=0) {
            Arrays.fill(p, 0);
            no++;
            int k=Integer.parseInt(br.readLine());
            int r=(k+1)/2;
            int res=0;
            String strings=br.readLine();
            for(int i=0;i<strings.length();i++) {
                p[i+1]+=(p[i]+Integer.parseInt(String.valueOf(strings.charAt(i))));
                if(i+1>=r) {
                    res=Math.max(res, p[i+1]-p[i+1-r]);
                }
            }
            System.out.println("Case #"+no+": "+res);
        }

    }
}

2.归并排序

AcWing 787. 归并排序

AcWing 788. 逆序对的数量

暴力求解

import java.util.Scanner;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        String[] s= reader.readLine().split(" ");
        int[] num=new int[n+1];
        for(int i=0;i<n;i++){
            num[i]=Integer.parseInt(s[i]);
        }
        int max=0;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n;j++){
                if(i==j)continue;;
                if(i<j && num[i]>num[j])max++;
            }
        }
        System.out.println(max);
    }
}

3.二分

AcWing 789. 数的范围

import java.io.BufferedInputStream;
import java.util.*;

class Main {


    public static void main(String[] args) {

        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        int n = scan.nextInt();
        int q = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        while (q-- > 0) {
            int target = scan.nextInt();

            int l = 0;
            int r = nums.length - 1;
            while (l < r) {
                int mid = (l + r >> 1);
                if (nums[mid] >= target) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (nums[l] == target) {
                System.out.print(l + " ");

                l = 0;
                r = nums.length - 1;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (nums[mid] <= target) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                System.out.println(l);
            } else {
                System.out.println(-1 + " " + -1);
            }
        }
    }
}

AcWing 503. 借教室（每日一题）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n;

    static int m;
    static int[] rooms;
    static int[] dj;
    static int[] sj;
    static int[] tj;
    static int[] b;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = reader.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

        String[] room = reader.readLine().split(" ");
        rooms = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            rooms[i] = Integer.parseInt(room[i - 1]);  //每天的教师数量
        }
        dj = new int[m + 1];
        b = new int[n + 10];
        sj = new int[m + 1];
        tj = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            String[] s2 = reader.readLine().split(" ");
            dj[i] = Integer.parseInt(s2[0]); //租借数量
            sj[i] = Integer.parseInt(s2[1]); //开始第几天
            tj[i] = Integer.parseInt(s2[2]); //结束第几天
        }

        //二分求解
        int l = -1, r = m + 1; //对订单数量进行二分
        while (l + 1 != r) {
            int mid = l + (r - l) / 2;
            if (check(mid)) { //如果当前订单能够被满足，左指针往又移动
                l = mid;
            } else {  //不能满足
                r = mid;
            }
        }


        if (l != m) { //左指针不是最后天，说明提前中断了
            System.out.println(-1);
            System.out.print(r-1);
        } else {
            System.out.println(0);
        }
    }

    private static boolean check(int mid) {  
        Arrays.fill(b, 0);
        for (int i = 1; i < mid; i++) {  //遍历前面的订单，并差分
            b[sj[i]] += dj[i];
            b[tj[i] + 1] -= dj[i];
        }
        for (int i = 1; i <= n; i++) { //累加求和
            b[i] += b[i - 1];
            if (b[i] > rooms[i]) { //出现借的教室数量大于当天教室数量
                return false;
            }
        }
        return true;
    }
}

AcWing 790. 数的三次方根

4.高精度

5.前缀和

AcWing 795. 前缀和

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader reader= new BufferedReader(new InputStreamReader(System.in));
        String[] line=reader.readLine().split(" ");
        int n=Integer.parseInt(line[0]);
        int m=Integer.parseInt(line[1]);
        int[] nums=new int[n+1];

        String[] line2=reader.readLine().split(" ");
        int[] s =new int[n+1];
        s[0]=0;
        for(int i=1;i<=n;i++){
            nums[i]=Integer.parseInt(line2[i-1]);
            s[i]=s[i-1]+nums[i];
        }
        while(m-->0){
            String[] line3=reader.readLine().split(" ");
            int l=Integer.parseInt(line3[0]);
            int r=Integer.parseInt(line3[1]);
            System.out.println(s[r]-s[l-1]);
        }
    }
}

AcWing 796. 子矩阵的和

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line = reader.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int q = Integer.parseInt(line[2]);
        int[][] nums=new int[n+1][m+1];
        int[][] s=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            String[] line2 = reader.readLine().split(" ");
            for(int j=1;j<=m;j++){
                nums[i][j]=Integer.parseInt(line2[j-1]);
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+nums[i][j];
            }
        }

        while(q-->0){
            String[] line3=reader.readLine().split(" ");
            int x1=Integer.parseInt(line3[0]);
            int y1=Integer.parseInt(line3[1]);
            int x2=Integer.parseInt(line3[2]);
            int y2=Integer.parseInt(line3[3]);
            System.out.println(s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);

        }


    }
}

AcWing 562. 壁画（每日一题）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N=(int) (5e6+10);
    static int[] p=new int [N];
    public static void main(String[] args) throws  IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int no=0;
        while(n--!=0) {
            Arrays.fill(p, 0);
            no++;
            int k=Integer.parseInt(br.readLine());
            int r=(k+1)/2;
            int res=0;
            String strings=br.readLine();
            for(int i=0;i<strings.length();i++) {
                p[i+1]+=(p[i]+Integer.parseInt(String.valueOf(strings.charAt(i))));
                if(i+1>=r) {
                    res=Math.max(res, p[i+1]-p[i+1-r]);
                }
            }
            System.out.println("Case #"+no+": "+res);
        }

    }
}

6.差分

AcWing 797. 差分

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line = reader.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);

        String[] s=reader.readLine().split(" ");
        int[] b= new int[n+2];
        while(m-->0){
            String[] line2 = reader.readLine().split(" ");
            int l=Integer.parseInt(line2[0])-1;
            int r=Integer.parseInt(line2[1])-1;
            int c=Integer.parseInt(line2[2]);
            sub(b,l,r,c);

        }
for(int i=1;i<b.length;i++){
    b[i]+=b[i-1];
}

       for(int i=0;i<n;i++){
           b[i]+=Integer.parseInt(s[i]);
           System.out.print(b[i]+" ");
       }


    }

    static void sub(int[] b, int l, int r, int c){
        b[l]+=c;
        b[r+1]-=c;
    }
}

AcWing 798. 差分矩阵

import java.util.Scanner;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main{
    static int n, m, q;
    static int N = 1010;
    static int[][] a = new int[N][N], b = new int[N][N];

    public static void insert(int x1, int y1, int x2, int y2, int c){
        b[x1][y1] += c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        q = Integer.parseInt(s[2]);

        for(int i = 1; i <= n; i ++){
            String[] in = br.readLine().split(" ");
            for(int j = 1; j <= m; j ++){
                // a[i][j] = sc.nextInt();
                a[i][j] = Integer.parseInt(in[j - 1]);
            }
        }
        //生成初始化b[i],可以和上面合并
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                insert(i, j, i, j, a[i][j]);
            }
        }
        //按区间进行 + c
        while(q -- != 0){

            String[] info = br.readLine().split(" ");
            int x1 = Integer.parseInt(info[0]);
            int y1 = Integer.parseInt(info[1]);
            int x2 = Integer.parseInt(info[2]);
            int y2 = Integer.parseInt(info[3]);
            int c = Integer.parseInt(info[4]);
            insert(x1, y1, x2, y2, c);
        }

        //前缀和
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
            }
        }
        //可以和上面合并
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                bw.write(b[i][j] + " ");
            }
            bw.write("\n");
        }
        bw.flush();
        br.close();
        bw.close();

    }
}

AcWing 5396. 棋盘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[][] qipan;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        qipan = new int[n + 2][n + 2];
      while(m-->0){
          String[] line = reader.readLine().split(" ");
          int x1 = Integer.parseInt(line[0]);
          int y1 = Integer.parseInt(line[1]);
          int x2 = Integer.parseInt(line[2]);
          int y2 = Integer.parseInt(line[3]);
          insert(x1, y1, x2, y2, 1);
      }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                qipan[i][j] += qipan[i - 1][j] + qipan[i][j - 1] - qipan[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(qipan[i][j] % 2);
            }
            System.out.println();
        }
    }

    private static void insert(int x1, int y1, int x2, int y2, int c) {
        qipan[x1][y1] += c;
        qipan[x2 + 1][y1] -= c;
        qipan[x1][y2 + 1] -= c;
        qipan[x2 + 1][y2 + 1] += c;
    }
}

AcWing 4262. 空调（每日一题）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[] s=new int[100010];
    public static void main(String[] args) throws  IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        String[] line;

        int[] p=new int[n+1];
        int[] t=new int[n+1];
        int[] diff=new int[n+1];
        line=reader.readLine().split(" ");
        for(int i=1;i<=n;i++){
            p[i]=Integer.parseInt(line[i-1]);
        }
        line=reader.readLine().split(" ");
        for(int i=1;i<=n;i++){
            t[i]=Integer.parseInt(line[i-1]);
            diff[i]=t[i]-p[i];

        }
        for(int i=n;i>0;i--){
            diff[i]-=diff[i-1];
//            System.out.println(diff[i]);
        }
        int pos=0;
        int neg=0;
        for(int i=0;i<=n;i++){
            if(diff[i]>0){
                pos+=diff[i];
            }else{
                neg+=Math.abs(diff[i]);
            }
        }
        int res = Math.max(pos, neg);
        System.out.println(res);
    }
}

7.双指针

AcWing 799. 最长连续不重复子序列

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[] a;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());
        String[] s = reader.readLine().split(" ");
        a = new int[num + 1];
        int max=0;
        for (int i = 0; i < num; i++) {
            a[i] = Integer.parseInt(s[i]);
        }
        int[] c= new int[num+1];
        for (int i = 0, j = 0; i < num; i++) {
            c[a[i]]++;
            while (j < i && c[a[i]]>1) {
                c[a[j]]--;
                j++;
            }
            max=Math.max(max,i-j+1);
        }
        System.out.println(max);
    }


}

AcWing 800. 数组元素的目标和

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader reader =new BufferedReader(new InputStreamReader(System.in));
       String[] s=reader.readLine().split(" ");
       int a=Integer.parseInt(s[0]);
       int b=Integer.parseInt(s[1]);
       int x=Integer.parseInt(s[2]);

       String[] a1=reader.readLine().split(" ");
       String[] b1=reader.readLine().split(" ");

       for(int i=0,j=b-1;i<a;i++){
           while(j>0 && Integer.parseInt(a1[i])+Integer.parseInt(b1[j]) > x){
               j--;
           }
           if(Integer.parseInt(a1[i])+Integer.parseInt(b1[j]) == x){
               System.out.println(i + " "+j);
           }
       }

    }
}

AcWing 2816. 判断子序列

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        String[] s1 = reader.readLine().split(" ");
        String[] s2 = reader.readLine().split(" ");

        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s1[i].equals(s2[j])) i++;
            j++;
        }
        if (i == n) System.out.println("Yes");
        else System.out.println("No");
    }
}

8.位运算

AcWing 801. 二进制中1的个数

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
       int n=Integer.parseInt(reader.readLine());
       String[] s=reader.readLine().split(" ");

       for(int i=0;i<s.length;i++){
           String a=Integer.toBinaryString(Integer.parseInt(s[i]));
           int j=0;
           int res=0;
           while(j<a.length()){

               if(a.charAt(j)=='1'){
                   res++;
               }
               j++;
           }
           System.out.print(res+" ");
       }
    }
}

9.离散化

10.区间合并

AcWing 803. 区间合并（算法基础课）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.text.SimpleDateFormat;
import java.util.*;


public class Main {
   private static int N=100010;
   private static int[] a;
   private static ArrayList<int[]> list=new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        for(int i=0;i<n;i++){
            String[] s=reader.readLine().split(" ");
            a=new int[2];
            a[0]=Integer.parseInt(s[0]);
            a[1]=Integer.parseInt(s[1]);
            list.add(a);
        }
        list.sort(Comparator.comparingInt(o -> o[0]));
        int k=0;
        int r=Integer.MIN_VALUE;
        for(int a[]:list){
            if(a[0]>r){
                k++;
            }
            r=Math.max(r,a[1]);
        }
        System.out.println(k);
    }
}

AcWing 1343. 挤牛奶（每日一题）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.text.SimpleDateFormat;
import java.util.*;


public class Main {
   private static int a[];
   private static ArrayList<int[]> list=new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        for(int i=0;i<n;i++){
            a=new int[2];
            String[] s=reader.readLine().split(" ");
            a[0]=Integer.parseInt(s[0]); //开始时间
            a[1]=Integer.parseInt(s[1]); //结束时间
            list.add(a);
        }
        list.sort(Comparator.comparing(o1->o1[0])); //对开始时间进行排序

        int aMax=0;
        int r=list.get(0)[1]; //标记右
        int l=list.get(0)[0]; //标记左
        int bMax=r-l; //第1个区间长度
        for(int i=0;i<n;i++){  //遍历每个区间
            if(list.get(i)[0]<r){  //当前区间的左端点是否小于右标记，说明区间需要合并
                r=Math.max(r,list.get(i)[1]); //重新标记右
            }else{ //说明是新的区间
                aMax=Math.max(list.get(i)[0]-r,aMax);//求最大的间隔区间
                bMax=Math.max(r-l,bMax); //求最大区间
                l=list.get(i)[0]; //重新标记新的左
                r=list.get(i)[1]; //重新标记新的右
            }
        }
        System.out.println(bMax+" "+aMax);
    }
}

AcWing 422. 校门外的树

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt();
        int m = scanner.nextInt();
        List<int[]> list = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int[] a = new int[2];
            a[0] = scanner.nextInt();
            a[1] = scanner.nextInt();
            list.add(a);
        }

        list.sort(Comparator.comparingInt(o -> o[0]));

        int left = list.get(0)[0];
        int right = list.get(0)[1];
        int res = list.get(0)[0]-0; //第一个区间到0的位置之间的间隔
        for (int i = 1; i < list.size(); i++) {
            int[] a = list.get(i);
            if (a[0] <= right) { //区间合并
                right = Math.max(a[1], right);
            } else { //说明是一个新的区间
                res +=(a[0] - right - 1) ; //新的区间到上一个区间之间的间隔
                left = a[0]; //重新标记
                right = a[1];
            }
        }
        res += l - right; //终点到最终区间的距离
        System.out.println(res);
    }
}

11.日期问题

AcWing 3498. 日期差值（每日一题）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.time.temporal.ChronoUnit;
import java.util.Calendar;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        DateTimeFormatter dateTimeFormatter=DateTimeFormatter.ofPattern("yyyyMMdd");
        while(sc.hasNext()){
            String d1=sc.next();
            String d2=sc.next();
            LocalDate date1=LocalDate.parse(d1,dateTimeFormatter);
            LocalDate date2=LocalDate.parse(d2,dateTimeFormatter);
            long diff= ChronoUnit.DAYS.between(date1,date2);
            System.out.println(Math.abs(diff)+1);
        }
    }
}

AcWing 1229. 日期问题（蓝桥杯辅导课）

import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Calendar ca = Calendar.getInstance();
        ca.set(1960, 0, 1);
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String[] a = new String[3];
        a[0] = s.substring(0, 2);
        a[1] = s.substring(3, 5);
        a[2] = s.substring(6, 8);

        for (;;) {
            if(ca.get(Calendar.YEAR)==2059&&ca.get(Calendar.MONTH)==11&&ca.get(Calendar.DAY_OF_MONTH)==31) {
                break;
            }
            SimpleDateFormat format=new SimpleDateFormat("yyyy-MM-dd");
            String day=format.format(ca.getTime());
            String[] b=new String[3];
            b[0]=day.substring(2,4);
            b[1]=day.substring(5,7);
            b[2]=day.substring(8,10);

            if(     (a[0].equals(b[0])&&a[1].equals(b[1])&&a[2].equals(b[2]))
                    ||    (a[0].equals(b[1])&&a[1].equals(b[2])&&a[2].equals(b[0]))
                    ||    (a[0].equals(b[2])&&a[1].equals(b[1])&&a[2].equals(b[0]))
            )
            {
                System.out.println(day);
            }
            ca.add(Calendar.DATE, 1);

        }

    }

}

AcWing 466. 回文日期（蓝桥杯辅导课）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String day1 = reader.readLine();
        Calendar c = Calendar.getInstance();
        Integer year = Integer.parseInt(day1.substring(0, 4));
        Integer month = Integer.parseInt(day1.substring(4, 6));
        Integer d = Integer.parseInt(day1.substring(6, 8));
        c.set(year, month - 1, d);

        String day2 = reader.readLine();
        Calendar c2 = Calendar.getInstance();
        Integer year2 = Integer.parseInt(day2.substring(0, 4));
        Integer month2 = Integer.parseInt(day2.substring(4, 6));
        Integer d2 = Integer.parseInt(day2.substring(6, 8));
        c2.set(year2, month2 - 1, d2);
        SimpleDateFormat format=new SimpleDateFormat("yyyyMMdd");
        int count=0;
        while (c.compareTo(c2) < 0) {
            String s=format.format(c.getTime());
            if(isHui(s)){
                count++;
            }
            c.add(Calendar.DAY_OF_YEAR, 1);
        }
        System.out.println(count);
    }

    private static boolean isHui(String s) {
        for(int i=0;i<s.length()/2;i++){
            if(s.charAt(i)==s.charAt(s.length()-i-1))continue;
            else return false;
        }
        return true;
    }

}

2.数据结构

1.单链表

AcWing 826. 单链表

import java.io.*;
import java.util.Scanner;

public class Main{
    private static int N = 100010;
    private static int head; //tou
    private static int[] e =new int[N];
    private static int[] ne=new int[N];
    private static int idx;
    
    private static void init(){
        head = -1;
        idx =0;
    }
    
    private static void addToHead(int val){
        e[idx]=val;
        ne[idx]=head;
        head=idx++;
    }
    
    private static void remove(int k){
        ne[k]=ne[ne[k]];
    }
    
    private static void add(int k,int val){
        e[idx]=val;
        ne[idx]=ne[k];
        ne[k]=idx;
        idx++;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        int m=Integer.parseInt(reader.readLine());
        init();
        while(m-->0){
            String[] s=reader.readLine().split(" ");
            
            if(s[0].equals("H")){
                int val=Integer.parseInt(s[1]);
                addToHead(val);
            }else if(s[0].equals("I")){
                int k=Integer.parseInt(s[1]);
                int val=Integer.parseInt(s[2]);
                add(k-1,val);
            }else{
                int k=Integer.parseInt(s[1]);
                if(k == 0){
                    head=ne[head];
                }else{
                    remove(k-1);
                }
                
            }
            
        }
         // 打印输出
        for (int i = head; i != -1; i = ne[i]) {
            System.out.print(e[i] + " ");
        }
    }
}

2.双链表

AcWing 827. 双链表

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class Main {
    static final int N = 100010;
    static int[] e = new int[N];
    static int[] l = new int[N];
    static int[] r = new int[N];
    static int idx;

    // 初始化
    static void init() {
        // 0 是左端点，1是右端点
        r[0] = 1;
        l[1] = 0;
        idx = 2;
    }

    // 在下标为k的节点右边插入一个节点
    static void insert(int k, int x) {
        e[idx] = x;
        r[idx] = r[k];
        l[r[k]] = idx;
        r[k] = idx;
        l[idx] = k;
        idx++;
    }

    // 删除下标为k的节点
    static void remove(int k) {
        r[l[k]] = r[k];
        l[r[k]] = l[k];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        int m = Integer.parseInt(in.readLine());
        String[] line;

        init(); // 初始化
        for (int i = 0; i < m; i++) {
            line = in.readLine().split(" ");

            int k, x;
            switch(line[0]) {
            case "L":
                x = Integer.parseInt(line[1]);
                insert(0, x);
                break;
            case "R":
                x = Integer.parseInt(line[1]);
                insert(l[1], x);
                break;
            case "D":
                k = Integer.parseInt(line[1]);
                remove(k + 1);
                break;
            case "IL":
                k = Integer.parseInt(line[1]);
                x = Integer.parseInt(line[2]);
                insert(l[k + 1], x);
                break;
            case "IR":
                k = Integer.parseInt(line[1]);
                x = Integer.parseInt(line[2]);
                insert(k + 1, x);
                break;
            }
        }

        for (int i = r[0]; i != 1; i = r[i]) {
            out.write(e[i] + " ");
        }

        in.close();
        out.close();
    }

}

3.栈

AcWing 828. 模拟栈

import java.io.*;
import java.util.*;

public class Main{
    static int m;
    static int N = 100010;
    static int[] stack = new int[N];
    static int tt = -1;
    public static void main(String[] args) throws IOException{
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer=new BufferedWriter(new OutputStreamWriter(System.out));

        int n=Integer.parseInt(reader.readLine());

        while(n-->0){
            String[] s=reader.readLine().split(" ");

            if(s[0].equals("push")){
                stack[++tt]= Integer.parseInt(s[1]);
            }else if(s[0].equals("pop")){
                tt--;
            }else if(s[0].equals("empty")){
                if(tt>=0){
                    writer.write("NO\n");
                }else{
                    writer.write("YES\n");
                }
            }else{
                writer.write(stack[tt]+"\n");
            }

        }
        writer.flush();

    }

}

4.队列

5.单调栈

6.单调队列

7.KMP

8.Trie

9.并查集

10.堆

11.哈希表

3.搜索与图论

1.DFS

AcWing 842. 排列数字

import java.util.*;

class Main{
    static int n = 0;
    static int q[] = new int[10];
    static int st[] = new int[10];

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs(1); //从1号位置开始排序
    }

    static void dfs(int x){
        if(x > n){ //终点
            for(int i = 1;i <= n;i ++){
                System.out.print(q[i]+" ");
            }
            System.out.println();
            return ;
        }
        for(int i = 1;i <= n;i ++) //遍历1、2、3
        {
            if(st[i] == 0) //遍历的数是否被访问
            {
                st[i] = 1; //遍历的数改为被访问
                q[x] = i; //该位置的数为i
                dfs(x+1); //位置加1
                st[i] = 0;
            }
        }
    }
}

AcWing 843. n-皇后问题

import java.util.Scanner;

public class Main {
    //设置矩阵存放n皇后
    static char[][] grid;
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        grid=new char[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                grid[i][j]='.';
            }
        }
        dfs(0,0,n,0);  //横、竖、皇后、当前皇后数量
    }
    //  s记录所放皇后的个数
    static void dfs(int row,int col,int n,int s){
        //所放皇后满足题目要求，输出矩阵，并退出该层递归
        if(s==n){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    System.out.print(grid[i][j]+" ");
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        //当走完整个棋盘后还没有摆放完n个皇后，则退出该层遍历
        if(row==n-1&&col==n){
            return;
        }
        //当col==n时，则代表已经走完该行，此时要换行和换列
        if(col==n){
            col=0;
            row++;
        }
        //当满足皇后存放条件时，放皇后
        if(sethuanghou(row,col,n)){
            grid[row][col]='Q';
            //满足条件，n皇后数量加一
            dfs(row,col+1,n,s+1);
            grid[row][col]='.';
        }
        //不放皇后，对该行的下一列进行递归
        dfs(row,col+1,n,s);
    }

    //判断该点是否能放皇后
    static boolean sethuanghou(int row,int col,int n){
        for(int i=0;i<n;i++){
            //判断行
            if(grid[row][i]=='Q')return false;
            //判断行
            if(grid[i][col]=='Q')return false;
        }
        //检查左上方是否已经放了皇后
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(grid[i][j]=='Q')return false;
        }
        //检查右上方是否已经放了皇后
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(grid[i][j]=='Q')return false;
        }
        return true;
    }
}

蓝桥–全球变暖

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

public class Main {
   static char[][] a;
    static int n;
    static boolean[][] visited;
    static int[] dx= {0,0,1,-1};
    static int[] dy= {-1,1,0,0};
    static int flag=0;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        a=new char[n][n];
        visited=new boolean[n][n];
        
        for(int i=0;i<a.length;i++) {//输入
            a[i]=sc.next().toCharArray();
        }
        int count=0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(visited[i][j]==false&&a[i][j]=='#') {
                    flag=0;
                    dfs(a,i,j);
                    if(flag==0) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
        
        }
    private static void dfs(char[][] a, int x, int y) {
        // TODO Auto-generated method stub
        visited[x][y]=true;
        if(a[x][y+1]=='#'&&a[x+1][y]=='#'&&a[x-1][y]=='#'&&a[x][y-1]=='#') { //他的四周均为陆地，则不会被淹没l
            flag=1;  //不会被淹没
        }
        for(int i=0;i<4;i++) {
            int nx=dx[i]+x;
            int ny=dy[i]+y;
            if(visited[nx][ny]==false&&a[nx][ny]=='#') //当前位置没有被访问，并且为陆地
                dfs(a,nx,ny);
        }
        
    }
        

    }

蓝桥–小朋友崇拜圈

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

public class Main {
    static int[] arr;
    static boolean[] help;
    static int max = Integer.MIN_VALUE;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n+1];
        help = new boolean[n+1];
        for (int i = 1; i <=n ; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i <=n ; i++) {
            dfs(i);
        }
        System.out.println(max);
    }
    public static void dfs(int p){
        int sum = 0;
        int t = p;
        while (!help[t]){
            help[t] = true;
            t = arr[t];
            sum++;
        }
        if(t==p){
            if(sum>max){
              max =sum;
            }
        }
        help = new boolean[n+1];
    }
}

蓝桥-- 数字三角形

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] arr = new int[N][N];
        int[][] dp = new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<=i;j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        sc.close();
        dp[0][0] = arr[0][0];
        for(int i=1;i<N;i++) {
            dp[i][0] = dp[i-1][0] + arr[i][0]; //dp每行第一个数为当前位置上的数+上一行第一个dp的数
        }
        for(int i=1;i<N;i++) {
            for(int j=1;j<=i;j++) {
                dp[i][j] = arr[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]);//dp等于当前数+上面一个数或者上面一个数的左边那个数h
            }
        }

        if(N%2!=0) {
            System.out.println(dp[N-1][N/2]);
        }else {
            System.out.println(Math.max(dp[N-1][N/2], dp[N-1][N/2-1]));
        }
    }
}

蓝桥–跳跃

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

public class Main {
    static int[][] a;
    static int max = Integer.MIN_VALUE;
    static int[] dx = { 1, 2, 3, 0, 1, 2, 0, 1, 0 };//上左下右都可以走3步
    static int[] dy = { 0, 0, 0, 1, 1, 1, 2, 2, 3 };
    static int n;
    static int m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        dfs(0, 0, a[0][0]); //x,y,当前权值就是第一个数
        System.out.println(max);

    }

    private static void dfs(int x, int y, int res) {
        if (x == n - 1 && y == m - 1) {
            max = Math.max(max, res);
        }
        for (int i = 0; i < dx.length; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                dfs(nx, ny, res + a[nx][ny]);
            }
        }

    }

}

蓝桥–与或异或

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

public class Main {
  static int count=0;
    public static void main(String[] args) {
      int[][] ans=new int[5][5];
      ans[0][0]=1;
      ans[0][1]=0;
      ans[0][2]=1;
      ans[0][3]=0;
      ans[0][4]=1;
      //int count=0;
      dfs(ans,1,0);
     System.out.print(count);
    }
    static void dfs(int[][]ans,int i,int j){//第一步：定变量，定所需值
      if(i==5){             //第二步：终止条件及完成终止条件后更新所求值
        if(ans[4][0]==1){
          count++;//静态变量
//count作为计数的变量，它的值应在递归过程中保持稳定。如果放到dfs（count）中，返回来时count的值也在变化
        }
        return;
      }

      for(int k=0;k<3;k++){//第三步：for循环，遍历可能存在的选项（如|,&,^每次循环选一个）
        if(k==0){
          ans[i][j]=ans[i-1][j]&ans[i-1][j+1];
        }else if(k==1){
          ans[i][j]=ans[i-1][j]|ans[i-1][j+1];
        }else{
          ans[i][j]=ans[i-1][j]^ans[i-1][j+1];
        }

        if(j==4-i){    //第四步：更新该行状态后进入下一行,更新列数
          dfs(ans,i+1,0);
        }else{
          dfs(ans,i,j+1);//更新行数
          }
   
      }

    }
}

2.BFS

AcWing 844. 走迷宫

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {

    static int a;
    static int b;
    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int[][] g, d;
    static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static Queue<Pair> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        a = Integer.parseInt(s[0]);
        b = Integer.parseInt(s[1]);
        g=new int[a][b];
        d=new int[a][b];
        for(int i=0;i<a;i++){
            String[] line=reader.readLine().split(" ");
            for(int j=0;j<b;j++){
                g[i][j]=Integer.parseInt(line[j]);
            }
        }
        System.out.println(bfs());


    }

    private static int bfs() {
        q.offer(new Pair(0,0)); //当前位置放入队列
        while (!q.isEmpty()){ 
            Pair pair=q.poll(); //取队头
            for(int[] dir:dirs){ //遍历该点的4周
                int x=pair.x+dir[0];
                int y=pair.y+dir[1];
                if (x < 0 || y < 0 || x >= a || y >= b || g[x][y] == 1 || d[x][y] != 0) {
                    continue; //g==1是围墙 d!=0说明当前已经有了最短的长度
                }
                d[x][y] = d[pair.x][pair.y] + 1;  //临近点的最短路径加 上当前这个1
                q.offer(new Pair(x, y)); //插入下一个节点
            }
        }
        return d[a-1][b-1];
    }
}

AcWing 845. 八数码

import java.util.*;
import java.io.*;
public class Main{
    static void swap(char c[],int a,int b){//用于交换值来变换状态
        char s=c[a];
        c[a]=c[b];
        c[b]=s;
    }
    static int bfs(String start,String end){

        Queue<String> q=new LinkedList<>();//存储所有状态
        Map<String,Integer> map=new HashMap<>();//存储每个状态得交换次数
        q.offer(start);  map.put(start,0);//存初始状态
        int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0};//四个方向

        while(!q.isEmpty()){//枚举所有状态

            String t=q.poll();//取出头一个状态并向前寻找（t过程中不能修改，因为有四次变化 而位置都是map[t]+1）
            if(t.equals(end)) return map.get(t);//直到找到结束状态为止，此时因为临近扩散原理所以一定是最小值；
            int k=t.indexOf('x');//找到x的坐标
            int x=k/3,y=k%3;//将一维下标转二维坐标利于上下左右改变状态

            for(int i=0;i<4;i++){//每个状态都有四次变化
                int a=x+dx[i],b=y+dy[i];//变化状态之后x的下标
                if(a>=0&&a<3&&b>=0&&b<3){//变化后不出界就是可用的

                    char arr[]=t.toCharArray();//字符串里面不能交换所以就到字符数组里,不直接修改t（以便后续的次数存储直接+1）
                    swap(arr,k,a*3+b);//交换值&变状态（因为前面是一维存储字符串，所以二维坐标转一维下标）
                    String s=new String(arr);//转成字符串，因为定义队列和map是用String的

                    if(map.get(s)==null){//如果这个状态没出现过就存储这个状态
                        q.offer(s);
                        map.put(s,map.get(t)+1);//变化前的次数值加一，因为是+1所以保证四个方向变化的值都是一样的；
                    }
                }
            }
        }
        return -1;
    }
    public static void main(String[] args)throws Exception{
        BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
        String q[]=sc.readLine().split(" ");
        String start="";//因为输入问题所以不能直接给一个字符串
        for(int i=0;i<q.length;i++){
            start+=q[i];
        }
        String end="12345678x";
        System.out.println(bfs(start,end));//从开始状态到结束状态要多少次交换
    }
}

蓝桥–扫雷

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

public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];
        int[][] dp = new int[n][m];
        int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
        int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int count = 0;
                if (a[i][j] == 1)
                    dp[i][j] = 9;
                else {
                    for (int k = 0; k < dx.length; k++) {
                        int nx = dx[k] + i;
                        int ny = dy[k] + j;
                        if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                            continue;
                        else {
                            if (a[nx][ny] == 1)
                                count++;
                        }
                    }
                    dp[i][j] = count;

                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }

}

3.树与图的深度优先遍历

AcWing 846. 树的重心

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static Object[] tree;
    static boolean[] state;
    static  List<Integer> list;
    static int ans;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int c=n;
        ans=n+1;
        tree=new Object[n+1];
        state=new boolean[n+1];
        while (--n>0){
            int a=sc.nextInt();
            int b=sc.nextInt();
            if(tree[a] == null){
                list=new LinkedList<>();
                list.add(b);
                tree[a]=list;
            }else{
                list= (List<Integer>) tree[a];
                list.add(b);
            }

            if (tree[b] == null) {
                list = new LinkedList<>();
                list.add(a);
                tree[b] = list;
            } else {
                list = (List<Integer>) tree[b];
                list.add(a);
            }
        }
        dfs(1,c,tree,state);
        System.out.println(ans);
    }

    private static int dfs(int u, int n, Object[] tree, boolean[] state) {
        state[u] = true;
        list= (List<Integer>) tree[u];
        if(list == null)
            return 1;
        int count=1;
        int res=0;
        for(int i:list){
            if(!state[i]){
                int child=dfs(i,n,tree,state);
                res=Math.max(res,child);
                count+=child;
            }
        }
        res =Math.max(res,n-count);
        ans=Math.min(ans,res);
        return count;
    }


}

4.树与图的广度优先遍历

4.数学知识

1.质数

AcWing 866. 试除法判定质数

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

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        
        while(n-->0){
            int a=Integer.parseInt(reader.readLine());
            if(isPrime(a)) System.out.println("Yes");
            else{
                System.out.println("No");
            }
        }
        
    }

    public static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= n / i; i++) {//推荐这种写法，而不是i * i <= n  或者i <= sqrt(n)
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

AcWing 867. 分解质因数

import java.io.*;

public class Main {
    static int n;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        while(n-- > 0){
            int a = Integer.parseInt(reader.readLine());
            decompose_prime(a);
        }
        writer.flush();
        writer.close();
        reader.close();
    }

    public static void decompose_prime(int n) throws IOException {
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0) {
                int res = 0;//循环整除判断质因子的指数
                while (n % i == 0) {
                    n /= i;
                    res++;
                }
                writer.write(i + " " + res + "\n");
            }
        }
        if (n > 1) {//表示存在一个大于sqrt(n)的质因子存在
            writer.write(n + " 1\n");
        }
        writer.write("\n");
    }
}

AcWing 868. 筛质数

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static boolean[] zishu;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        zishu=new boolean[n+1];
        int index=is_prime(n);
        System.out.println(index);
    }

    private static int is_prime(int n) {
        int count=0;
        for(int i=2;i<=n;i++){
            if(!zishu[i]){
                count++;
                for(int j=i+i;j<=n;j+=i){
                    zishu[j]=true; //不是质数
                }
            }
        }
        return count;
    }
}

2.约数

AcWing 869. 试除法求约数

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static boolean[] zishu;
    public static void main(String[] args) throws IOException {
       BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
       int n=Integer.parseInt(reader.readLine());
       while(n-->0){
           int m=Integer.parseInt(reader.readLine());
           yueshu(m);
           System.out.println();
       }
    }

    private static void yueshu(int n) {
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=1;i<=n/i;i++){
            if(n%i==0){
                list.add(i);
                if(n/i!=i) {
                    list.add(n/i);
                }
            }
        }
        list.sort(Comparator.comparing(o1->o1));
        for(Integer a:list){
            System.out.print(a+" ");
        }
    }


}

AcWing 870. 约数个数

如果 N = p1^c1 * p2^c2 * … *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * … *
(ck + 1) 约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static Map<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long res = 1;
        int mod = 1000000007;
        int n = Integer.parseInt(reader.readLine());
        while (n-- > 0) {
            int a = Integer.parseInt(reader.readLine());
            getNums(a);
        }
        for (int a : map.values()) {
            res = (res * (a + 1)) % mod;
        }
        System.out.println(res);
    }

    private static void getNums(int n) {

        for (int i = 2; i <= n / i; i++) {
            while (n % i == 0) {
                map.put(i, map.getOrDefault(i, 0) + 1); //是约数，加入map中，并指数加1
                n /= i; //连续除以这个约数，得到下一个质数
            }
        }
        if (n > 1) {
            map.put(n, map.getOrDefault(n, 0) + 1); //连除剩下的本身也是一个质数，指数加1
        }
    }
}

蓝桥–质因数个数

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        /**
         *  input 正整数n  
         *  output 质数中n的因数个数
         *  质数：大于1的自然数，除了1和其本身没有其余的因数，2、3、5、7、9、11、13、17、19、23、29、31、37、43、47、51、53、57、59、61
         *  因数：a能够被b整除，则b是a的因数
         */
        Scanner scan = new Scanner(System.in);
        // 唯一分离定律 任何一个数都可以被分解为两个质数相乘的形式
        //所以找质因数 当一个数能
        long n = scan.nextLong();
        int res = 0;
        for (int i = 2; (long)i * i< n; i++) { //396
            if(n%i == 0) { //2、3
                res++;
            }
            while(n%i==0) { //此时n==11是其本身
                n = n/i;
            }
        }
        if(n>1) { 因此这里加1
            res++;
        }
        System.out.println(res);
    }

}

AcWing 871. 约数之和

import java.io.*;
import java.util.*;

class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int t = Integer.valueOf(read.readLine());
        Map<Integer, Integer> map = new HashMap();
        while(t -- > 0){
            Integer a = Integer.valueOf(read.readLine());

            for(int i = 2; i <= a / i; i++){
                if(a % i == 0){
                    int cnt = 0;
                    while(a % i == 0){
                        cnt++;
                        a /= i;
                    }
                    map.put(i, map.getOrDefault(i, 0) + cnt);
                }
            }
            if(a > 1) map.put(a, map.getOrDefault(a, 0) + 1);
        }

        long res = 1;
        int mod = (int)1e9 + 7;
        for(Integer a: map.keySet()){ //a是质数
            long sum = 0;
            int k = map.get(a); //k是指数
            for(int i = 0; i <= k; i++){
                long pow = 1; int tmp = i;
                while(tmp-- > 0) pow = pow * a % mod;  //p1^0  、p1^1 、、、p1^temp
                sum = (sum + pow) % mod; //(p1^0 + p1^1 + ... + p1^c1)
            }
            res = res * sum % mod;
        }
        System.out.println(res);
    }
}

AcWing 872. 最大公约数

import java.util.*;
class Main{
    static int n = 0;
    static int gcd(int a, int b){
        return b != 0 ? gcd(b, a % b) : a;
    }
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while(n -- != 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int res = gcd(a, b);
            System.out.println(res);
        }
    }
}

最小公倍数

 static int gcd(int a, int b){
        return b != 0 ? gcd(b, a % b) : a;
     //5 3
     //3 2
     //2 1
     //1 1
     //1 0
    }

static int beishu(int a,int b){
    return a*b/gcd(a,b);
}

动态规划

蓝桥–买不到的数目

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int max = n * m;  //找不到的数肯定在n*m内
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i * n <= max; i++) { //第一个数
            for (int j = 0; i * n + j * m <= max; j++) { //第二个数
                set.add(i * n + j * m); //存入set中去重
            } 
        }
        for (int i = max - 1; i > -0; i--) { //从后往前找  看看集合中是否是否存在，不存在则输出            if (!set.contains(i)) {
            if (!set.contains(i)) {  
                System.out.println(i);
                return;
            }
        }
    }
}

蓝桥–小明的背包2

每个物品的数量都是无限多个

import java.util.Scanner;

public class Main {
    
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt(); //物品的种类
    int v = scan.nextInt();  //背包的容量
    int dp[][] = new int[n+1][v+1];
    int w[] = new int[n+1];
    int p[] = new int[n+1];
    for(int i = 1 ; i <=n;i++) {
        w[i] = scan.nextInt(); //物品的体积
        p[i] = scan.nextInt(); //物品的价值
    }
    
    for(int i =1; i <= n; i++) { //物品的数量
        for(int j =1; j <=v; j++) { //依次遍历书包的容量
            if(w[i]<=j) {  //当前的物品重量小于书包的容量
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]]+p[i]);
            }else {
                dp[i][j]=dp[i-1][j];
            }
        }
    }
//    for(int i[]:dp) {
//        for(int j:i) {
//            System.out.print(j+" ");
//        }
//        System.out.println();
//    }
    System.out.println(dp[n][v]);
}
}

蓝桥–砝码称重

1.先将第一个数加入集合中
2.遍历后面的每个数，并且和集合中的每个数进行加减（小于0取绝对值），再次加入集合中
注意：加减结果可能为0 直接移除，不能通过set.size()-1这么算

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.*;
public class Main {
  public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        TreeSet<Integer> set=new TreeSet<>();
        for(int i=0;i<n;i++) {
            a[i]=sc.nextInt();
        }
        set.add(a[0]); 
        for(int i=1;i<n;i++) {
            List<Integer> list = new ArrayList<>(set); //当前可以得到的数
            for(int c:list) { //遍历集合中的数
                //将此数与集合中的每个进行加减
                set.add(c+a[i]); 
                set.add(Math.abs(c-a[i]));
                 continue;
            }
            set.add(a[i]); //加上本数
        }
        set.remove(0); //去除重量为0的可能
        System.out.println(set.size());
    }

}

蓝桥–路径

import java.util.Arrays;
public class Main {
    static int[] a = new int[2022];
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Arrays.fill(a, Integer.MAX_VALUE);
        a[1]=0;
        for (int i = 1; i <= 2020; i++) {
            for (int j = i + 1; j <= 2021; j++) {
                if(j-i<=21) {
                    a[j]=Math.min(a[j], a[i]+le(i,j)); //任何点到该点的权值取最小
                }
            }

        }
        System.out.println(a[2021]);

    }
    //最小公倍数=两数之积/最大公约数
    private static int le(int a, int b) {
        // TODO Auto-generated method stub
        return a*b/gcd(a,b);
    }
    //最大公约数
    private static int gcd(int a, int b) { 
        // TODO Auto-generated method stub
        return b != 0 ? gcd(b, a % b) : a;
    }
}

蓝桥–卡片

(x,y) --(1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 。

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int p =sc.nextInt();
    int n=0;
    for (int i = 1; i < Integer.MAX_VALUE; i++){ // x
        for(int j = 1; j <=i; j++){ //y
           n++;
        if(n>=p){
            System.out.println(i);
            return;
        }  
    } 
  }
}
}

蓝桥–最大和

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.Arrays;
public class Main {
   
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] temp=new int[n+1];
        int[] v=new int [n+1];
        Arrays.fill(v, Integer.MIN_VALUE);
        for(int i=1;i<=n;i++) {
            temp[i]=sc.nextInt();
        }
        v[1]=temp[1];
        for(int i=1;i<=n;i++) {
            int next=find(n-i);
            for(int j=1;j<=next;j++) { //可以继续往前走next步
                v[j+i]=Math.max(v[j+i],v[i]+temp[j+i]);
            }
        }
        System.out.println(v[n]);
    }
    //寻找最小的质因数
    private static int find(int index) {
        // TODO Auto-generated method stub
        if(index==1)return index;
        for(int i=2;i<index;i++) {
            if(index%i==0)return i;
        }
        
        return index;
    }

}

蓝桥–有奖问答

public class Main {
    static int N = 35, M=110;
    static long[][] f = new long[N][M]; //（题，分数）
    public static void main(String[] args) {
        int n = 30, m =100;
        f[1][0] = 1; f[1][10] = 1; //第一题答对与否 都只是1种情况
        for(int i=2; i<=n; i++){
            for(int j=0; j<=100; j+=10){
                //得分为0代表至少答错一题，所以这里我们只要最后一题答错就可以了
                if(j==0){
                    for(int k=0; k<=90; k+=10) f[i][j] += f[i-1][k]; //加上上一道题的所有的分数情况
                }else{ //当前分数不为0
                    f[i][j] = f[i-1][j-10];
                }
            }
        }
        long ans = 0;
        for(int i=1; i<=n; i++) ans += f[i][70];
        System.out.println(ans);
    }
}

蓝桥–位数排序

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<int[]> list=new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        int m=Integer.parseInt(reader.readLine());
        for(int i=1;i<=n;i++){
            weishuzhihe(i);
        }
        list.sort(Comparator.comparing(o1->o1[0]));
        System.out.println(list.get(m-1)[1]);
    }

    private static void weishuzhihe(int n) {
        int res=0;
        int t=n;
        while(n>0){
            res+=n%10;
            n/=10;
        }
        list.add(new int[]{res,t});
    }

}

蓝桥–最优清零方案

通过60/100

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] a;
    static int m;
    static int[] b;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        String[] line = reader.readLine().split(" ");
        a = new int[n + 1];
        b = new int[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(line[i]);
        }
        long res=0;
        for (int i = 0; i <= n-m; i++) {
            int min=Integer.MAX_VALUE;
            int t=m;
            while(t-->0) {
                if(min!=0){
                    min=Math.min(min,a[i+t]);
                }
            }
            res+=min;
            for(int j=i;j<i+m;j++){

                a[j]-=min;

            }

        }
        for(int i=0;i<n;i++){

            res+=a[i];
        }
        System.out.println(res);
    }
}