蓝桥杯算法记录

算法记录

因为最近快到蓝桥杯了 所以跟练了几道题 今天就来记录一下

信号覆盖

信号覆盖
解题思路：这题将输入的x,y的进行储存 然后将每个点用check方法进行检测

int t1=x-X[i];
 int t2=y-Y[i];
 //用这个进行判断
 t1*t1+t2*t2<=r*r
1
2
3
4

答案

import java.util.Scanner;

// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {

  static int[] X = new int[101];
  static int[] Y = new int[101];
  static int n = 0;
  static int r = 0;

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int w = scan.nextInt();
    int h = scan.nextInt();
    n = scan.nextInt();
    r = scan.nextInt();
    for (int i = 0; i < n; i++) {
      X[i] = scan.nextInt();
      Y[i] = scan.nextInt();
    }
    scan.close();
    int res = 0;
    for (int i = 0; i <= w; i++) {
      for (int j = 0; j <= h; j++) {
        if (check(i, j)) {
          res++;
        }
      }
    }
    System.out.println(res);
  }

  public static boolean check(int x, int y) {
    for (int i = 0; i < n; i++) {
      int t1 = x - X[i];
      int t2 = y - Y[i];
      if (t1 * t1 + t2 * t2 <= r * r) {
        return true;
      }
    }
    return false;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

并查集

幼儿园
第一个是初始化
将数组初始化下标为本身

  for(int i=1;i<arr.length;i++){
              arr[i]=i;
            }
1
2
3

合并 如果他俩不是一个父节点再将

public static void merge(int x,int y){
          int prex=findRoot(x);
          int prey=findRoot(y);
          if(prex!=prey){
            arr[prey]=prex;
          }
1
2
3
4
5
6

查找
传入查找的数字 不然继续往下查找

 public static int findRoot(int key){
          if(key==arr[key]){
            return key;
          }
          return arr[key]=findRoot(arr[key]);
        }
1
2
3
4
5
6

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

public class Main {
    private static int[] arr = null;
    public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int n=scan.nextInt();
            int m=scan.nextInt();
            arr=new int[n+1];
            for(int i=1;i<arr.length;i++){
              arr[i]=i;
            }
            while(m-->0){
              int op=scan.nextInt();
              int x=scan.nextInt();
              int y=scan.nextInt();
              if(op==1){
                merge(x,y);
              }else{
                int x1=findRoot(x);
                int y1=findRoot(y);
                if(x1!=y1){
                  System.out.println("NO");
                }else{
                  System.out.println("YES");
                }
              }
            }
            scan.close();
        }
        public static int findRoot(int key){
          if(key==arr[key]){
            return key;
          }
          return arr[key]=findRoot(arr[key]);
        }
        public static void merge(int x,int y){
          int prex=findRoot(x);
          int prey=findRoot(y);
          if(prex!=prey){
            arr[prey]=prex;
          }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

简单的动态规划

台阶问题
答案：
动态规划是这次的状态由前几次状态或者上次状态推导出来的
阶 走法
1 1
2 2
3 4
4 7
5 13
看出 f(n) = f(n-1) + f(n-2) + f(n-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();
        int []dp=new int[n+1];
        if(n<=0){
         System.out.println(0);
         return;
        }
        if(n<=2){
         System.out.println(n);
         return;
        };
        if(n==3){
         System.out.println(4);
         return;
        }
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4;i<=n;i++){
          dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        System.out.println(dp[n]);
        scan.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

二分求区间最大值的最小值

跳石头
这题思路是在起点和终点之间不断地寻找缩小范围 如果当前每次记录下来的的值进入 check方法进行判断
如果当前的距离小于最小值搬去不做影响 对搬去的数字++ 否则就从此处开始计算后续的有没有距离更小的

 static boolean check(int d){
      int cnt=0,pos=0;
      for(int i=0;i<n;i++){
        if(arr[i]-pos<d){
          cnt++;
        }else{
          pos=arr[i];
        }
      }
      if(cnt<=m){
        return true;
      }
      return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

答案

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

public class Main {
   static int l,n,m;
    static int[] arr;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        l = scan.nextInt();
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = scan.nextInt();
        }
        int left=0,right=l;
        int mid,result=0;
        while(left<=right){
          mid=(left+right)>>1;
          if(check(mid)){
            result=mid;
            left=mid+1;
          }else{
            right=mid-1;
          }
        }
         System.out.println(result);
        scan.close();
    }
    static boolean check(int d){
      int cnt=0,pos=0;
      for(int i=0;i<n;i++){
        if(arr[i]-pos<d){
          cnt++;
        }else{
          pos=arr[i];
        }
      }
      if(cnt<=m){
        return true;
      }
      return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

总结

直播挺难写的 算法也挺难写的 感觉算法基础还是不行 但是面试也要问 还是每天多写点吧